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. */
161 #include "basic-block.h"
163 #include "hard-reg-set.h"
165 #include "insn-config.h"
166 #include "insn-attr.h"
171 extern char *reg_known_equiv_p
;
172 extern rtx
*reg_known_value
;
174 #ifdef INSN_SCHEDULING
176 /* target_units bitmask has 1 for each unit in the cpu. It should be
177 possible to compute this variable from the machine description.
178 But currently it is computed by examinning the insn list. Since
179 this is only needed for visualization, it seems an acceptable
180 solution. (For understanding the mapping of bits to units, see
181 definition of function_units[] in "insn-attrtab.c") */
183 static int target_units
= 0;
185 /* issue_rate is the number of insns that can be scheduled in the same
186 machine cycle. It can be defined in the config/mach/mach.h file,
187 otherwise we set it to 1. */
189 static int issue_rate
;
195 /* sched-verbose controls the amount of debugging output the
196 scheduler prints. It is controlled by -fsched-verbose-N:
197 N>0 and no -DSR : the output is directed to stderr.
198 N>=10 will direct the printouts to stderr (regardless of -dSR).
200 N=2: bb's probabilities, detailed ready list info, unit/insn info.
201 N=3: rtl at abort point, control-flow, regions info.
202 N=5: dependences info. */
204 #define MAX_RGN_BLOCKS 10
205 #define MAX_RGN_INSNS 100
207 static int sched_verbose_param
= 0;
208 static int sched_verbose
= 0;
210 /* nr_inter/spec counts interblock/speculative motion for the function */
211 static int nr_inter
, nr_spec
;
214 /* debugging file. all printouts are sent to dump, which is always set,
215 either to stderr, or to the dump listing file (-dRS). */
216 static FILE *dump
= 0;
218 /* fix_sched_param() is called from toplev.c upon detection
219 of the -fsched-***-N options. */
222 fix_sched_param (param
, val
)
225 if (!strcmp (param
, "verbose"))
226 sched_verbose_param
= atoi (val
);
228 warning ("fix_sched_param: unknown param: %s", param
);
232 /* Arrays set up by scheduling for the same respective purposes as
233 similar-named arrays set up by flow analysis. We work with these
234 arrays during the scheduling pass so we can compare values against
237 Values of these arrays are copied at the end of this pass into the
238 arrays set up by flow analysis. */
239 static int *sched_reg_n_calls_crossed
;
240 static int *sched_reg_live_length
;
241 static int *sched_reg_basic_block
;
243 /* We need to know the current block number during the post scheduling
244 update of live register information so that we can also update
245 REG_BASIC_BLOCK if a register changes blocks. */
246 static int current_block_num
;
248 /* Element N is the next insn that sets (hard or pseudo) register
249 N within the current basic block; or zero, if there is no
250 such insn. Needed for new registers which may be introduced
251 by splitting insns. */
252 static rtx
*reg_last_uses
;
253 static rtx
*reg_last_sets
;
254 static regset reg_pending_sets
;
255 static int reg_pending_sets_all
;
257 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
258 static int *insn_luid
;
259 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
261 /* Vector indexed by INSN_UID giving each instruction a priority. */
262 static int *insn_priority
;
263 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
265 static short *insn_costs
;
266 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
268 /* Vector indexed by INSN_UID giving an encoding of the function units
270 static short *insn_units
;
271 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
273 /* Vector indexed by INSN_UID giving each instruction a register-weight.
274 This weight is an estimation of the insn contribution to registers pressure. */
275 static int *insn_reg_weight
;
276 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
278 /* Vector indexed by INSN_UID giving list of insns which
279 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
280 static rtx
*insn_depend
;
281 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
283 /* Vector indexed by INSN_UID. Initialized to the number of incoming
284 edges in forward dependence graph (= number of LOG_LINKS). As
285 scheduling procedes, dependence counts are decreased. An
286 instruction moves to the ready list when its counter is zero. */
287 static int *insn_dep_count
;
288 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
290 /* Vector indexed by INSN_UID giving an encoding of the blockage range
291 function. The unit and the range are encoded. */
292 static unsigned int *insn_blockage
;
293 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
295 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
296 #define ENCODE_BLOCKAGE(U, R) \
297 ((((U) << UNIT_BITS) << BLOCKAGE_BITS \
298 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
299 | MAX_BLOCKAGE_COST (R))
300 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
301 #define BLOCKAGE_RANGE(B) \
302 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
303 | ((B) & BLOCKAGE_MASK))
305 /* Encodings of the `<name>_unit_blockage_range' function. */
306 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
307 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
309 #define DONE_PRIORITY -1
310 #define MAX_PRIORITY 0x7fffffff
311 #define TAIL_PRIORITY 0x7ffffffe
312 #define LAUNCH_PRIORITY 0x7f000001
313 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
314 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
316 /* Vector indexed by INSN_UID giving number of insns referring to this insn. */
317 static int *insn_ref_count
;
318 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
320 /* Vector indexed by INSN_UID giving line-number note in effect for each
321 insn. For line-number notes, this indicates whether the note may be
323 static rtx
*line_note
;
324 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
326 /* Vector indexed by basic block number giving the starting line-number
327 for each basic block. */
328 static rtx
*line_note_head
;
330 /* List of important notes we must keep around. This is a pointer to the
331 last element in the list. */
332 static rtx note_list
;
334 /* Regsets telling whether a given register is live or dead before the last
335 scheduled insn. Must scan the instructions once before scheduling to
336 determine what registers are live or dead at the end of the block. */
337 static regset bb_live_regs
;
339 /* Regset telling whether a given register is live after the insn currently
340 being scheduled. Before processing an insn, this is equal to bb_live_regs
341 above. This is used so that we can find registers that are newly born/dead
342 after processing an insn. */
343 static regset old_live_regs
;
345 /* The chain of REG_DEAD notes. REG_DEAD notes are removed from all insns
346 during the initial scan and reused later. If there are not exactly as
347 many REG_DEAD notes in the post scheduled code as there were in the
348 prescheduled code then we trigger an abort because this indicates a bug. */
349 static rtx dead_notes
;
353 /* An instruction is ready to be scheduled when all insns preceding it
354 have already been scheduled. It is important to ensure that all
355 insns which use its result will not be executed until its result
356 has been computed. An insn is maintained in one of four structures:
358 (P) the "Pending" set of insns which cannot be scheduled until
359 their dependencies have been satisfied.
360 (Q) the "Queued" set of insns that can be scheduled when sufficient
362 (R) the "Ready" list of unscheduled, uncommitted insns.
363 (S) the "Scheduled" list of insns.
365 Initially, all insns are either "Pending" or "Ready" depending on
366 whether their dependencies are satisfied.
368 Insns move from the "Ready" list to the "Scheduled" list as they
369 are committed to the schedule. As this occurs, the insns in the
370 "Pending" list have their dependencies satisfied and move to either
371 the "Ready" list or the "Queued" set depending on whether
372 sufficient time has passed to make them ready. As time passes,
373 insns move from the "Queued" set to the "Ready" list. Insns may
374 move from the "Ready" list to the "Queued" set if they are blocked
375 due to a function unit conflict.
377 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
378 insns, i.e., those that are ready, queued, and pending.
379 The "Queued" set (Q) is implemented by the variable `insn_queue'.
380 The "Ready" list (R) is implemented by the variables `ready' and
382 The "Scheduled" list (S) is the new insn chain built by this pass.
384 The transition (R->S) is implemented in the scheduling loop in
385 `schedule_block' when the best insn to schedule is chosen.
386 The transition (R->Q) is implemented in `queue_insn' when an
387 insn is found to have a function unit conflict with the already
389 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
390 insns move from the ready list to the scheduled list.
391 The transition (Q->R) is implemented in 'queue_to_insn' as time
392 passes or stalls are introduced. */
394 /* Implement a circular buffer to delay instructions until sufficient
395 time has passed. INSN_QUEUE_SIZE is a power of two larger than
396 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
397 longest time an isnsn may be queued. */
398 static rtx insn_queue
[INSN_QUEUE_SIZE
];
399 static int q_ptr
= 0;
400 static int q_size
= 0;
401 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
402 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
404 /* Vector indexed by INSN_UID giving the minimum clock tick at which
405 the insn becomes ready. This is used to note timing constraints for
406 insns in the pending list. */
407 static int *insn_tick
;
408 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
410 /* Data structure for keeping track of register information
411 during that register's life. */
420 /* Forward declarations. */
421 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
422 static void remove_dependence
PROTO ((rtx
, rtx
));
423 static rtx find_insn_list
PROTO ((rtx
, rtx
));
424 static int insn_unit
PROTO ((rtx
));
425 static unsigned int blockage_range
PROTO ((int, rtx
));
426 static void clear_units
PROTO ((void));
427 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
428 static void schedule_unit
PROTO ((int, rtx
, int));
429 static int actual_hazard
PROTO ((int, rtx
, int, int));
430 static int potential_hazard
PROTO ((int, rtx
, int));
431 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
432 static int priority
PROTO ((rtx
));
433 static void free_pending_lists
PROTO ((void));
434 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
435 static void flush_pending_lists
PROTO ((rtx
, int));
436 static void sched_analyze_1
PROTO ((rtx
, rtx
));
437 static void sched_analyze_2
PROTO ((rtx
, rtx
));
438 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
439 static void sched_analyze
PROTO ((rtx
, rtx
));
440 static void sched_note_set
PROTO ((rtx
, int));
441 static int rank_for_schedule
PROTO ((const GENERIC_PTR
, const GENERIC_PTR
));
442 static void swap_sort
PROTO ((rtx
*, int));
443 static void queue_insn
PROTO ((rtx
, int));
444 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
445 static void create_reg_dead_note
PROTO ((rtx
, rtx
));
446 static void attach_deaths
PROTO ((rtx
, rtx
, int));
447 static void attach_deaths_insn
PROTO ((rtx
));
448 static int new_sometimes_live
PROTO ((struct sometimes
*, int, int));
449 static void finish_sometimes_live
PROTO ((struct sometimes
*, int));
450 static int schedule_block
PROTO ((int, int));
451 static void split_hard_reg_notes
PROTO ((rtx
, rtx
, rtx
));
452 static void new_insn_dead_notes
PROTO ((rtx
, rtx
, rtx
, rtx
));
453 static void update_n_sets
PROTO ((rtx
, int));
454 static char *safe_concat
PROTO ((char *, char *, char *));
455 static int insn_issue_delay
PROTO ((rtx
));
456 static int birthing_insn_p
PROTO ((rtx
));
457 static void adjust_priority
PROTO ((rtx
));
459 /* Mapping of insns to their original block prior to scheduling. */
460 static int *insn_orig_block
;
461 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
463 /* Some insns (e.g. call) are not allowed to move across blocks. */
464 static char *cant_move
;
465 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
467 /* Control flow graph edges are kept in circular lists. */
476 static edge
*edge_table
;
478 #define NEXT_IN(edge) (edge_table[edge].next_in)
479 #define NEXT_OUT(edge) (edge_table[edge].next_out)
480 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
481 #define TO_BLOCK(edge) (edge_table[edge].to_block)
483 /* Number of edges in the control flow graph. (in fact larger than
484 that by 1, since edge 0 is unused.) */
487 /* Circular list of incoming/outgoing edges of a block */
488 static int *in_edges
;
489 static int *out_edges
;
491 #define IN_EDGES(block) (in_edges[block])
492 #define OUT_EDGES(block) (out_edges[block])
494 /* List of labels which cannot be deleted, needed for control
495 flow graph construction. */
496 extern rtx forced_labels
;
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
; /* blocks 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]).
526 Note: A basic block is always referred to by either block or b,
527 while its topological order name (in the region) is refered to by
530 static int *block_to_bb
;
532 /* The number of the region containing a block. */
533 static int *containing_rgn
;
535 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
536 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
537 #define BLOCK_TO_BB(block) (block_to_bb[block])
538 #define CONTAINING_RGN(block) (containing_rgn[block])
540 void debug_regions
PROTO ((void));
541 static void find_single_block_region
PROTO ((void));
542 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
543 int *, int *, sbitmap
*));
544 static int too_large
PROTO ((int, int *, int *));
546 extern void debug_live
PROTO ((int, int));
548 /* Blocks of the current region being scheduled. */
549 static int current_nr_blocks
;
550 static int current_blocks
;
552 /* The mapping from bb to block */
553 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
556 /* Bit vectors and bitset operations are needed for computations on
557 the control flow graph. */
559 typedef unsigned HOST_WIDE_INT
*bitset
;
562 int *first_member
; /* pointer to the list start in bitlst_table. */
563 int nr_members
; /* the number of members of the bit list. */
567 static int bitlst_table_last
;
568 static int bitlst_table_size
;
569 static int *bitlst_table
;
571 static char bitset_member
PROTO ((bitset
, int, int));
572 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
574 /* target info declarations.
576 The block currently being scheduled is referred to as the "target" block,
577 while other blocks in the region from which insns can be moved to the
578 target are called "source" blocks. The candidate structure holds info
579 about such sources: are they valid? Speculative? Etc. */
580 typedef bitlst bblst
;
591 static candidate
*candidate_table
;
593 /* A speculative motion requires checking live information on the path
594 from 'source' to 'target'. The split blocks are those to be checked.
595 After a speculative motion, live information should be modified in
598 Lists of split and update blocks for each candidate of the current
599 target are in array bblst_table */
600 static int *bblst_table
, bblst_size
, bblst_last
;
602 #define IS_VALID(src) ( candidate_table[src].is_valid )
603 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
604 #define SRC_PROB(src) ( candidate_table[src].src_prob )
606 /* The bb being currently scheduled. */
607 static int target_bb
;
610 typedef bitlst edgelst
;
612 /* target info functions */
613 static void split_edges
PROTO ((int, int, edgelst
*));
614 static void compute_trg_info
PROTO ((int));
615 void debug_candidate
PROTO ((int));
616 void debug_candidates
PROTO ((int));
619 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
620 typedef bitset bbset
;
622 /* Number of words of the bbset. */
623 static int bbset_size
;
625 /* Dominators array: dom[i] contains the bbset of dominators of
626 bb i in the region. */
629 /* bb 0 is the only region entry */
630 #define IS_RGN_ENTRY(bb) (!bb)
632 /* Is bb_src dominated by bb_trg. */
633 #define IS_DOMINATED(bb_src, bb_trg) \
634 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
636 /* Probability: Prob[i] is a float in [0, 1] which is the probability
637 of bb i relative to the region entry. */
640 /* The probability of bb_src, relative to bb_trg. Note, that while the
641 'prob[bb]' is a float in [0, 1], this macro returns an integer
643 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
646 /* Bit-set of edges, where bit i stands for edge i. */
647 typedef bitset edgeset
;
649 /* Number of edges in the region. */
650 static int rgn_nr_edges
;
652 /* Array of size rgn_nr_edges. */
653 static int *rgn_edges
;
655 /* Number of words in an edgeset. */
656 static int edgeset_size
;
658 /* Mapping from each edge in the graph to its number in the rgn. */
659 static int *edge_to_bit
;
660 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
662 /* The split edges of a source bb is different for each target
663 bb. In order to compute this efficiently, the 'potential-split edges'
664 are computed for each bb prior to scheduling a region. This is actually
665 the split edges of each bb relative to the region entry.
667 pot_split[bb] is the set of potential split edges of bb. */
668 static edgeset
*pot_split
;
670 /* For every bb, a set of its ancestor edges. */
671 static edgeset
*ancestor_edges
;
673 static void compute_dom_prob_ps
PROTO ((int));
675 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
676 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
677 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
678 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
680 /* parameters affecting the decision of rank_for_schedule() */
681 #define MIN_DIFF_PRIORITY 2
682 #define MIN_PROBABILITY 40
683 #define MIN_PROB_DIFF 10
685 /* speculative scheduling functions */
686 static int check_live_1
PROTO ((int, rtx
));
687 static void update_live_1
PROTO ((int, rtx
));
688 static int check_live
PROTO ((rtx
, int));
689 static void update_live
PROTO ((rtx
, int));
690 static void set_spec_fed
PROTO ((rtx
));
691 static int is_pfree
PROTO ((rtx
, int, int));
692 static int find_conditional_protection
PROTO ((rtx
, int));
693 static int is_conditionally_protected
PROTO ((rtx
, int, int));
694 static int may_trap_exp
PROTO ((rtx
, int));
695 static int haifa_classify_insn
PROTO ((rtx
));
696 static int is_prisky
PROTO ((rtx
, int, int));
697 static int is_exception_free
PROTO ((rtx
, int, int));
699 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
700 static void compute_block_forward_dependences
PROTO ((int));
701 static void init_rgn_data_dependences
PROTO ((int));
702 static void add_branch_dependences
PROTO ((rtx
, rtx
));
703 static void compute_block_backward_dependences
PROTO ((int));
704 void debug_dependencies
PROTO ((void));
706 /* Notes handling mechanism:
707 =========================
708 Generally, NOTES are saved before scheduling and restored after scheduling.
709 The scheduler distinguishes between three types of notes:
711 (1) LINE_NUMBER notes, generated and used for debugging. Here,
712 before scheduling a region, a pointer to the LINE_NUMBER note is
713 added to the insn following it (in save_line_notes()), and the note
714 is removed (in rm_line_notes() and unlink_line_notes()). After
715 scheduling the region, this pointer is used for regeneration of
716 the LINE_NUMBER note (in restore_line_notes()).
718 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
719 Before scheduling a region, a pointer to the note is added to the insn
720 that follows or precedes it. (This happens as part of the data dependence
721 computation). After scheduling an insn, the pointer contained in it is
722 used for regenerating the corresponding note (in reemit_notes).
724 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
725 these notes are put in a list (in rm_other_notes() and
726 unlink_other_notes ()). After scheduling the block, these notes are
727 inserted at the beginning of the block (in schedule_block()). */
729 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
730 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
731 static void rm_line_notes
PROTO ((int));
732 static void save_line_notes
PROTO ((int));
733 static void restore_line_notes
PROTO ((int));
734 static void rm_redundant_line_notes
PROTO ((void));
735 static void rm_other_notes
PROTO ((rtx
, rtx
));
736 static rtx reemit_notes
PROTO ((rtx
, rtx
));
738 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
740 static void find_pre_sched_live
PROTO ((int));
741 static void find_post_sched_live
PROTO ((int));
742 static void update_reg_usage
PROTO ((void));
743 static int queue_to_ready
PROTO ((rtx
[], int));
745 static void debug_ready_list
PROTO ((rtx
[], int));
746 static void init_target_units
PROTO ((void));
747 static void insn_print_units
PROTO ((rtx
));
748 static int get_visual_tbl_length
PROTO ((void));
749 static void init_block_visualization
PROTO ((void));
750 static void print_block_visualization
PROTO ((int, char *));
751 static void visualize_scheduled_insns
PROTO ((int, int));
752 static void visualize_no_unit
PROTO ((rtx
));
753 static void visualize_stall_cycles
PROTO ((int, int));
754 static void print_exp
PROTO ((char *, rtx
, int));
755 static void print_value
PROTO ((char *, rtx
, int));
756 static void print_pattern
PROTO ((char *, rtx
, int));
757 static void print_insn
PROTO ((char *, rtx
, int));
758 void debug_reg_vector
PROTO ((regset
));
760 static rtx move_insn1
PROTO ((rtx
, rtx
));
761 static rtx move_insn
PROTO ((rtx
, rtx
));
762 static rtx group_leader
PROTO ((rtx
));
763 static int set_priorities
PROTO ((int));
764 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
765 static void schedule_region
PROTO ((int));
767 #endif /* INSN_SCHEDULING */
769 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
771 /* Helper functions for instruction scheduling. */
773 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
774 static rtx unused_insn_list
;
776 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
777 static rtx unused_expr_list
;
779 static void free_list
PROTO ((rtx
*, rtx
*));
780 static rtx alloc_INSN_LIST
PROTO ((rtx
, rtx
));
781 static rtx alloc_EXPR_LIST
PROTO ((int, rtx
, rtx
));
784 free_list (listp
, unused_listp
)
785 rtx
*listp
, *unused_listp
;
787 register rtx link
, prev_link
;
793 link
= XEXP (prev_link
, 1);
798 link
= XEXP (link
, 1);
801 XEXP (prev_link
, 1) = *unused_listp
;
802 *unused_listp
= *listp
;
807 alloc_INSN_LIST (val
, next
)
812 if (unused_insn_list
)
814 r
= unused_insn_list
;
815 unused_insn_list
= XEXP (r
, 1);
818 PUT_REG_NOTE_KIND (r
, VOIDmode
);
821 r
= gen_rtx_INSN_LIST (VOIDmode
, val
, next
);
827 alloc_EXPR_LIST (kind
, val
, next
)
833 if (unused_expr_list
)
835 r
= unused_expr_list
;
836 unused_expr_list
= XEXP (r
, 1);
839 PUT_REG_NOTE_KIND (r
, kind
);
842 r
= gen_rtx_EXPR_LIST (kind
, val
, next
);
847 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
848 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
849 of dependence that this link represents. */
852 add_dependence (insn
, elem
, dep_type
)
855 enum reg_note dep_type
;
859 /* Don't depend an insn on itself. */
863 /* If elem is part of a sequence that must be scheduled together, then
864 make the dependence point to the last insn of the sequence.
865 When HAVE_cc0, it is possible for NOTEs to exist between users and
866 setters of the condition codes, so we must skip past notes here.
867 Otherwise, NOTEs are impossible here. */
869 next
= NEXT_INSN (elem
);
872 while (next
&& GET_CODE (next
) == NOTE
)
873 next
= NEXT_INSN (next
);
876 if (next
&& SCHED_GROUP_P (next
)
877 && GET_CODE (next
) != CODE_LABEL
)
879 /* Notes will never intervene here though, so don't bother checking
881 /* We must reject CODE_LABELs, so that we don't get confused by one
882 that has LABEL_PRESERVE_P set, which is represented by the same
883 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
885 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
886 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
887 next
= NEXT_INSN (next
);
889 /* Again, don't depend an insn on itself. */
893 /* Make the dependence to NEXT, the last insn of the group, instead
894 of the original ELEM. */
898 #ifdef INSN_SCHEDULING
899 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
900 No need for interblock dependences with calls, since
901 calls are not moved between blocks. Note: the edge where
902 elem is a CALL is still required. */
903 if (GET_CODE (insn
) == CALL_INSN
904 && (INSN_BB (elem
) != INSN_BB (insn
)))
909 /* Check that we don't already have this dependence. */
910 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
911 if (XEXP (link
, 0) == elem
)
913 /* If this is a more restrictive type of dependence than the existing
914 one, then change the existing dependence to this type. */
915 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
916 PUT_REG_NOTE_KIND (link
, dep_type
);
919 /* Might want to check one level of transitivity to save conses. */
921 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
922 LOG_LINKS (insn
) = link
;
924 /* Insn dependency, not data dependency. */
925 PUT_REG_NOTE_KIND (link
, dep_type
);
928 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
929 of INSN. Abort if not found. */
932 remove_dependence (insn
, elem
)
936 rtx prev
, link
, next
;
939 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
941 next
= XEXP (link
, 1);
942 if (XEXP (link
, 0) == elem
)
945 XEXP (prev
, 1) = next
;
947 LOG_LINKS (insn
) = next
;
949 XEXP (link
, 1) = unused_insn_list
;
950 unused_insn_list
= link
;
963 #ifndef INSN_SCHEDULING
965 schedule_insns (dump_file
)
975 #define HAIFA_INLINE __inline
978 /* Computation of memory dependencies. */
980 /* The *_insns and *_mems are paired lists. Each pending memory operation
981 will have a pointer to the MEM rtx on one list and a pointer to the
982 containing insn on the other list in the same place in the list. */
984 /* We can't use add_dependence like the old code did, because a single insn
985 may have multiple memory accesses, and hence needs to be on the list
986 once for each memory access. Add_dependence won't let you add an insn
987 to a list more than once. */
989 /* An INSN_LIST containing all insns with pending read operations. */
990 static rtx pending_read_insns
;
992 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
993 static rtx pending_read_mems
;
995 /* An INSN_LIST containing all insns with pending write operations. */
996 static rtx pending_write_insns
;
998 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
999 static rtx pending_write_mems
;
1001 /* Indicates the combined length of the two pending lists. We must prevent
1002 these lists from ever growing too large since the number of dependencies
1003 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1004 a function of the length of these pending lists. */
1006 static int pending_lists_length
;
1008 /* The last insn upon which all memory references must depend.
1009 This is an insn which flushed the pending lists, creating a dependency
1010 between it and all previously pending memory references. This creates
1011 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1013 This includes all non constant CALL_INSNs. When we do interprocedural
1014 alias analysis, this restriction can be relaxed.
1015 This may also be an INSN that writes memory if the pending lists grow
1018 static rtx last_pending_memory_flush
;
1020 /* The last function call we have seen. All hard regs, and, of course,
1021 the last function call, must depend on this. */
1023 static rtx last_function_call
;
1025 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1026 that does not already cross a call. We create dependencies between each
1027 of those insn and the next call insn, to ensure that they won't cross a call
1028 after scheduling is done. */
1030 static rtx sched_before_next_call
;
1032 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1033 so that insns independent of the last scheduled insn will be preferred
1034 over dependent instructions. */
1036 static rtx last_scheduled_insn
;
1038 /* Data structures for the computation of data dependences in a regions. We
1039 keep one copy of each of the declared above variables for each bb in the
1040 region. Before analyzing the data dependences for a bb, its variables
1041 are initialized as a function of the variables of its predecessors. When
1042 the analysis for a bb completes, we save the contents of each variable X
1043 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1044 copied to bb_pending_read_insns[bb]. Another change is that few
1045 variables are now a list of insns rather than a single insn:
1046 last_pending_memory_flash, last_function_call, reg_last_sets. The
1047 manipulation of these variables was changed appropriately. */
1049 static rtx
**bb_reg_last_uses
;
1050 static rtx
**bb_reg_last_sets
;
1052 static rtx
*bb_pending_read_insns
;
1053 static rtx
*bb_pending_read_mems
;
1054 static rtx
*bb_pending_write_insns
;
1055 static rtx
*bb_pending_write_mems
;
1056 static int *bb_pending_lists_length
;
1058 static rtx
*bb_last_pending_memory_flush
;
1059 static rtx
*bb_last_function_call
;
1060 static rtx
*bb_sched_before_next_call
;
1062 /* functions for construction of the control flow graph. */
1064 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1066 We decide not to build the control flow graph if there is possibly more
1067 than one entry to the function, if computed branches exist, of if we
1068 have nonlocal gotos. */
1071 is_cfg_nonregular ()
1077 /* If we have a label that could be the target of a nonlocal goto, then
1078 the cfg is not well structured. */
1079 if (nonlocal_label_rtx_list () != NULL
)
1082 /* If we have any forced labels, then the cfg is not well structured. */
1086 /* If this function has a computed jump, then we consider the cfg
1087 not well structured. */
1088 if (current_function_has_computed_jump
)
1091 /* If we have exception handlers, then we consider the cfg not well
1092 structured. ?!? We should be able to handle this now that flow.c
1093 computes an accurate cfg for EH. */
1094 if (exception_handler_labels
)
1097 /* If we have non-jumping insns which refer to labels, then we consider
1098 the cfg not well structured. */
1099 /* check for labels referred to other thn by jumps */
1100 for (b
= 0; b
< n_basic_blocks
; b
++)
1101 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1103 code
= GET_CODE (insn
);
1104 if (GET_RTX_CLASS (code
) == 'i')
1108 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1109 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1113 if (insn
== BLOCK_END (b
))
1117 /* All the tests passed. Consider the cfg well structured. */
1121 /* Build the control flow graph and set nr_edges.
1123 Instead of trying to build a cfg ourselves, we rely on flow to
1124 do it for us. Stamp out useless code (and bug) duplication.
1126 Return nonzero if an irregularity in the cfg is found which would
1127 prevent cross block scheduling. */
1130 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1131 int_list_ptr
*s_preds
;
1132 int_list_ptr
*s_succs
;
1140 /* Count the number of edges in the cfg. */
1143 for (i
= 0; i
< n_basic_blocks
; i
++)
1145 nr_edges
+= num_succs
[i
];
1147 /* Unreachable loops with more than one basic block are detected
1148 during the DFS traversal in find_rgns.
1150 Unreachable loops with a single block are detected here. This
1151 test is redundant with the one in find_rgns, but it's much
1152 cheaper to go ahead and catch the trivial case here. */
1153 if (num_preds
[i
] == 0
1154 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1158 /* Account for entry/exit edges. */
1161 in_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1162 out_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1163 bzero ((char *) in_edges
, n_basic_blocks
* sizeof (int));
1164 bzero ((char *) out_edges
, n_basic_blocks
* sizeof (int));
1166 edge_table
= (edge
*) xmalloc ((nr_edges
) * sizeof (edge
));
1167 bzero ((char *) edge_table
, ((nr_edges
) * sizeof (edge
)));
1170 for (i
= 0; i
< n_basic_blocks
; i
++)
1171 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1173 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1174 new_edge (i
, INT_LIST_VAL (succ
));
1177 /* increment by 1, since edge 0 is unused. */
1184 /* Record an edge in the control flow graph from SOURCE to TARGET.
1186 In theory, this is redundant with the s_succs computed above, but
1187 we have not converted all of haifa to use information from the
1191 new_edge (source
, target
)
1195 int curr_edge
, fst_edge
;
1197 /* check for duplicates */
1198 fst_edge
= curr_edge
= OUT_EDGES (source
);
1201 if (FROM_BLOCK (curr_edge
) == source
1202 && TO_BLOCK (curr_edge
) == target
)
1207 curr_edge
= NEXT_OUT (curr_edge
);
1209 if (fst_edge
== curr_edge
)
1215 FROM_BLOCK (e
) = source
;
1216 TO_BLOCK (e
) = target
;
1218 if (OUT_EDGES (source
))
1220 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1221 NEXT_OUT (OUT_EDGES (source
)) = e
;
1222 NEXT_OUT (e
) = next_edge
;
1226 OUT_EDGES (source
) = e
;
1230 if (IN_EDGES (target
))
1232 next_edge
= NEXT_IN (IN_EDGES (target
));
1233 NEXT_IN (IN_EDGES (target
)) = e
;
1234 NEXT_IN (e
) = next_edge
;
1238 IN_EDGES (target
) = e
;
1244 /* BITSET macros for operations on the control flow graph. */
1246 /* Compute bitwise union of two bitsets. */
1247 #define BITSET_UNION(set1, set2, len) \
1248 do { register bitset tp = set1, sp = set2; \
1250 for (i = 0; i < len; i++) \
1251 *(tp++) |= *(sp++); } while (0)
1253 /* Compute bitwise intersection of two bitsets. */
1254 #define BITSET_INTER(set1, set2, len) \
1255 do { register bitset tp = set1, sp = set2; \
1257 for (i = 0; i < len; i++) \
1258 *(tp++) &= *(sp++); } while (0)
1260 /* Compute bitwise difference of two bitsets. */
1261 #define BITSET_DIFFER(set1, set2, len) \
1262 do { register bitset tp = set1, sp = set2; \
1264 for (i = 0; i < len; i++) \
1265 *(tp++) &= ~*(sp++); } while (0)
1267 /* Inverts every bit of bitset 'set' */
1268 #define BITSET_INVERT(set, len) \
1269 do { register bitset tmpset = set; \
1271 for (i = 0; i < len; i++, tmpset++) \
1272 *tmpset = ~*tmpset; } while (0)
1274 /* Turn on the index'th bit in bitset set. */
1275 #define BITSET_ADD(set, index, len) \
1277 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1280 set[index/HOST_BITS_PER_WIDE_INT] |= \
1281 1 << (index % HOST_BITS_PER_WIDE_INT); \
1284 /* Turn off the index'th bit in set. */
1285 #define BITSET_REMOVE(set, index, len) \
1287 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1290 set[index/HOST_BITS_PER_WIDE_INT] &= \
1291 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1295 /* Check if the index'th bit in bitset set is on. */
1298 bitset_member (set
, index
, len
)
1302 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1304 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1305 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1309 /* Translate a bit-set SET to a list BL of the bit-set members. */
1312 extract_bitlst (set
, len
, bl
)
1318 unsigned HOST_WIDE_INT word
;
1320 /* bblst table space is reused in each call to extract_bitlst */
1321 bitlst_table_last
= 0;
1323 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1326 for (i
= 0; i
< len
; i
++)
1329 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1330 for (j
= 0; word
; j
++)
1334 bitlst_table
[bitlst_table_last
++] = offset
;
1345 /* functions for the construction of regions */
1347 /* Print the regions, for debugging purposes. Callable from debugger. */
1354 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1355 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1357 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1358 rgn_table
[rgn
].rgn_nr_blocks
);
1359 fprintf (dump
, ";;\tbb/block: ");
1361 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1363 current_blocks
= RGN_BLOCKS (rgn
);
1365 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1368 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1371 fprintf (dump
, "\n\n");
1376 /* Build a single block region for each basic block in the function.
1377 This allows for using the same code for interblock and basic block
1381 find_single_block_region ()
1385 for (i
= 0; i
< n_basic_blocks
; i
++)
1387 rgn_bb_table
[i
] = i
;
1388 RGN_NR_BLOCKS (i
) = 1;
1390 CONTAINING_RGN (i
) = i
;
1391 BLOCK_TO_BB (i
) = 0;
1393 nr_regions
= n_basic_blocks
;
1397 /* Update number of blocks and the estimate for number of insns
1398 in the region. Return 1 if the region is "too large" for interblock
1399 scheduling (compile time considerations), otherwise return 0. */
1402 too_large (block
, num_bbs
, num_insns
)
1403 int block
, *num_bbs
, *num_insns
;
1406 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1407 INSN_LUID (BLOCK_HEAD (block
)));
1408 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1415 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1416 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1417 loop containing blk. */
1418 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1420 if (max_hdr[blk] == -1) \
1421 max_hdr[blk] = hdr; \
1422 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1423 RESET_BIT (inner, hdr); \
1424 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1426 RESET_BIT (inner,max_hdr[blk]); \
1427 max_hdr[blk] = hdr; \
1432 /* Find regions for interblock scheduling.
1434 A region for scheduling can be:
1436 * A loop-free procedure, or
1438 * A reducible inner loop, or
1440 * A basic block not contained in any other region.
1443 ?!? In theory we could build other regions based on extended basic
1444 blocks or reverse extended basic blocks. Is it worth the trouble?
1446 Loop blocks that form a region are put into the region's block list
1447 in topological order.
1449 This procedure stores its results into the following global (ick) variables
1458 We use dominator relationships to avoid making regions out of non-reducible
1461 This procedure needs to be converted to work on pred/succ lists instead
1462 of edge tables. That would simplify it somewhat. */
1465 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1466 int_list_ptr
*s_preds
;
1467 int_list_ptr
*s_succs
;
1472 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1474 int node
, child
, loop_head
, i
, head
, tail
;
1475 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1476 int num_bbs
, num_insns
, unreachable
;
1477 int too_large_failure
;
1479 /* Note if an edge has been passed. */
1482 /* Note if a block is a natural loop header. */
1485 /* Note if a block is an natural inner loop header. */
1488 /* Note if a block is in the block queue. */
1491 /* Note if a block is in the block queue. */
1494 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1495 and a mapping from block to its loop header (if the block is contained
1496 in a loop, else -1).
1498 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1499 be used as inputs to the second traversal.
1501 STACK, SP and DFS_NR are only used during the first traversal. */
1503 /* Allocate and initialize variables for the first traversal. */
1504 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1505 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1506 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1507 stack
= (int *) alloca (nr_edges
* sizeof (int));
1509 inner
= sbitmap_alloc (n_basic_blocks
);
1510 sbitmap_ones (inner
);
1512 header
= sbitmap_alloc (n_basic_blocks
);
1513 sbitmap_zero (header
);
1515 passed
= sbitmap_alloc (nr_edges
);
1516 sbitmap_zero (passed
);
1518 in_queue
= sbitmap_alloc (n_basic_blocks
);
1519 sbitmap_zero (in_queue
);
1521 in_stack
= sbitmap_alloc (n_basic_blocks
);
1522 sbitmap_zero (in_stack
);
1524 for (i
= 0; i
< n_basic_blocks
; i
++)
1527 /* DFS traversal to find inner loops in the cfg. */
1532 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1534 /* We have reached a leaf node or a node that was already
1535 processed. Pop edges off the stack until we find
1536 an edge that has not yet been processed. */
1538 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1540 /* Pop entry off the stack. */
1541 current_edge
= stack
[sp
--];
1542 node
= FROM_BLOCK (current_edge
);
1543 child
= TO_BLOCK (current_edge
);
1544 RESET_BIT (in_stack
, child
);
1545 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1546 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1547 current_edge
= NEXT_OUT (current_edge
);
1550 /* See if have finished the DFS tree traversal. */
1551 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1554 /* Nope, continue the traversal with the popped node. */
1558 /* Process a node. */
1559 node
= FROM_BLOCK (current_edge
);
1560 child
= TO_BLOCK (current_edge
);
1561 SET_BIT (in_stack
, node
);
1562 dfs_nr
[node
] = ++count
;
1564 /* If the successor is in the stack, then we've found a loop.
1565 Mark the loop, if it is not a natural loop, then it will
1566 be rejected during the second traversal. */
1567 if (TEST_BIT (in_stack
, child
))
1570 SET_BIT (header
, child
);
1571 UPDATE_LOOP_RELATIONS (node
, child
);
1572 SET_BIT (passed
, current_edge
);
1573 current_edge
= NEXT_OUT (current_edge
);
1577 /* If the child was already visited, then there is no need to visit
1578 it again. Just update the loop relationships and restart
1582 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1583 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1584 SET_BIT (passed
, current_edge
);
1585 current_edge
= NEXT_OUT (current_edge
);
1589 /* Push an entry on the stack and continue DFS traversal. */
1590 stack
[++sp
] = current_edge
;
1591 SET_BIT (passed
, current_edge
);
1592 current_edge
= OUT_EDGES (child
);
1595 /* Another check for unreachable blocks. The earlier test in
1596 is_cfg_nonregular only finds unreachable blocks that do not
1599 The DFS traversal will mark every block that is reachable from
1600 the entry node by placing a nonzero value in dfs_nr. Thus if
1601 dfs_nr is zero for any block, then it must be unreachable. */
1603 for (i
= 0; i
< n_basic_blocks
; i
++)
1610 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1611 to hold degree counts. */
1614 /* Compute the in-degree of every block in the graph */
1615 for (i
= 0; i
< n_basic_blocks
; i
++)
1616 degree
[i
] = num_preds
[i
];
1618 /* Do not perform region scheduling if there are any unreachable
1623 SET_BIT (header
, 0);
1625 /* Second travsersal:find reducible inner loops and topologically sort
1626 block of each region. */
1628 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1630 /* Find blocks which are inner loop headers. We still have non-reducible
1631 loops to consider at this point. */
1632 for (i
= 0; i
< n_basic_blocks
; i
++)
1634 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1639 /* Now check that the loop is reducible. We do this separate
1640 from finding inner loops so that we do not find a reducible
1641 loop which contains an inner non-reducible loop.
1643 A simple way to find reducible/natrual loops is to verify
1644 that each block in the loop is dominated by the loop
1647 If there exists a block that is not dominated by the loop
1648 header, then the block is reachable from outside the loop
1649 and thus the loop is not a natural loop. */
1650 for (j
= 0; j
< n_basic_blocks
; j
++)
1652 /* First identify blocks in the loop, except for the loop
1654 if (i
== max_hdr
[j
] && i
!= j
)
1656 /* Now verify that the block is dominated by the loop
1658 if (!TEST_BIT (dom
[j
], i
))
1663 /* If we exited the loop early, then I is the header of a non
1664 reducible loop and we should quit processing it now. */
1665 if (j
!= n_basic_blocks
)
1668 /* I is a header of an inner loop, or block 0 in a subroutine
1669 with no loops at all. */
1671 too_large_failure
= 0;
1672 loop_head
= max_hdr
[i
];
1674 /* Decrease degree of all I's successors for topological
1676 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1677 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1678 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1679 --degree
[INT_LIST_VAL(ps
)];
1681 /* Estimate # insns, and count # blocks in the region. */
1683 num_insns
= (INSN_LUID (BLOCK_END (i
))
1684 - INSN_LUID (BLOCK_HEAD (i
)));
1687 /* Find all loop latches (blocks which back edges to the loop
1688 header) or all the leaf blocks in the cfg has no loops.
1690 Place those blocks into the queue. */
1693 for (j
= 0; j
< n_basic_blocks
; j
++)
1694 /* Leaf nodes have only a single successor which must
1696 if (num_succs
[j
] == 1
1697 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1700 SET_BIT (in_queue
, j
);
1702 if (too_large (j
, &num_bbs
, &num_insns
))
1704 too_large_failure
= 1;
1713 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1715 node
= INT_LIST_VAL (ps
);
1717 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1720 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1722 /* This is a loop latch. */
1723 queue
[++tail
] = node
;
1724 SET_BIT (in_queue
, node
);
1726 if (too_large (node
, &num_bbs
, &num_insns
))
1728 too_large_failure
= 1;
1736 /* Now add all the blocks in the loop to the queue.
1738 We know the loop is a natural loop; however the algorithm
1739 above will not always mark certain blocks as being in the
1748 The algorithm in the DFS traversal may not mark B & D as part
1749 of the loop (ie they will not have max_hdr set to A).
1751 We know they can not be loop latches (else they would have
1752 had max_hdr set since they'd have a backedge to a dominator
1753 block). So we don't need them on the initial queue.
1755 We know they are part of the loop because they are dominated
1756 by the loop header and can be reached by a backwards walk of
1757 the edges starting with nodes on the initial queue.
1759 It is safe and desirable to include those nodes in the
1760 loop/scheduling region. To do so we would need to decrease
1761 the degree of a node if it is the target of a backedge
1762 within the loop itself as the node is placed in the queue.
1764 We do not do this because I'm not sure that the actual
1765 scheduling code will properly handle this case. ?!? */
1767 while (head
< tail
&& !too_large_failure
)
1770 child
= queue
[++head
];
1772 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1774 node
= INT_LIST_VAL (ps
);
1776 /* See discussion above about nodes not marked as in
1777 this loop during the initial DFS traversal. */
1778 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1779 || max_hdr
[node
] != loop_head
)
1784 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1786 queue
[++tail
] = node
;
1787 SET_BIT (in_queue
, node
);
1789 if (too_large (node
, &num_bbs
, &num_insns
))
1791 too_large_failure
= 1;
1798 if (tail
>= 0 && !too_large_failure
)
1800 /* Place the loop header into list of region blocks. */
1802 rgn_bb_table
[idx
] = i
;
1803 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1804 RGN_BLOCKS (nr_regions
) = idx
++;
1805 CONTAINING_RGN (i
) = nr_regions
;
1806 BLOCK_TO_BB (i
) = count
= 0;
1808 /* Remove blocks from queue[] when their in degree becomes
1809 zero. Repeat until no blocks are left on the list. This
1810 produces a topological list of blocks in the region. */
1817 child
= queue
[head
];
1818 if (degree
[child
] == 0)
1821 rgn_bb_table
[idx
++] = child
;
1822 BLOCK_TO_BB (child
) = ++count
;
1823 CONTAINING_RGN (child
) = nr_regions
;
1824 queue
[head
] = queue
[tail
--];
1826 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1827 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1828 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1829 --degree
[INT_LIST_VAL (ps
)];
1840 /* Any block that did not end up in a region is placed into a region
1842 for (i
= 0; i
< n_basic_blocks
; i
++)
1845 rgn_bb_table
[idx
] = i
;
1846 RGN_NR_BLOCKS (nr_regions
) = 1;
1847 RGN_BLOCKS (nr_regions
) = idx
++;
1848 CONTAINING_RGN (i
) = nr_regions
++;
1849 BLOCK_TO_BB (i
) = 0;
1860 /* functions for regions scheduling information */
1862 /* Compute dominators, probability, and potential-split-edges of bb.
1863 Assume that these values were already computed for bb's predecessors. */
1866 compute_dom_prob_ps (bb
)
1869 int nxt_in_edge
, fst_in_edge
, pred
;
1870 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1873 if (IS_RGN_ENTRY (bb
))
1875 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1880 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1882 /* intialize dom[bb] to '111..1' */
1883 BITSET_INVERT (dom
[bb
], bbset_size
);
1887 pred
= FROM_BLOCK (nxt_in_edge
);
1888 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1890 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1893 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1896 nr_rgn_out_edges
= 0;
1897 fst_out_edge
= OUT_EDGES (pred
);
1898 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1899 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1902 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1904 /* the successor doesn't belong the region? */
1905 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1906 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1909 while (fst_out_edge
!= nxt_out_edge
)
1912 /* the successor doesn't belong the region? */
1913 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1914 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1916 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1917 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1921 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1922 and nr_out_edges will be the number of pred out edges not leaving
1924 nr_out_edges
-= nr_rgn_out_edges
;
1925 if (nr_rgn_out_edges
> 0)
1926 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1928 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1929 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1931 while (fst_in_edge
!= nxt_in_edge
);
1933 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1934 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1936 if (sched_verbose
>= 2)
1937 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1938 } /* compute_dom_prob_ps */
1940 /* functions for target info */
1942 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1943 Note that bb_trg dominates bb_src. */
1946 split_edges (bb_src
, bb_trg
, bl
)
1951 int es
= edgeset_size
;
1952 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1955 src
[es
] = (pot_split
[bb_src
])[es
];
1956 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1957 extract_bitlst (src
, edgeset_size
, bl
);
1961 /* Find the valid candidate-source-blocks for the target block TRG, compute
1962 their probability, and check if they are speculative or not.
1963 For speculative sources, compute their update-blocks and split-blocks. */
1966 compute_trg_info (trg
)
1969 register candidate
*sp
;
1971 int check_block
, update_idx
;
1972 int i
, j
, k
, fst_edge
, nxt_edge
;
1974 /* define some of the fields for the target bb as well */
1975 sp
= candidate_table
+ trg
;
1977 sp
->is_speculative
= 0;
1980 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1982 sp
= candidate_table
+ i
;
1984 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1987 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1988 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1993 split_edges (i
, trg
, &el
);
1994 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1995 if (sp
->is_speculative
&& !flag_schedule_speculative
)
2001 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
2002 sp
->split_bbs
.nr_members
= el
.nr_members
;
2003 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
2004 bblst_table
[bblst_last
] =
2005 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2006 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
2008 for (j
= 0; j
< el
.nr_members
; j
++)
2010 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2011 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
2014 for (k
= 0; k
< el
.nr_members
; k
++)
2015 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
2018 if (k
>= el
.nr_members
)
2020 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
2024 nxt_edge
= NEXT_OUT (nxt_edge
);
2026 while (fst_edge
!= nxt_edge
);
2028 sp
->update_bbs
.nr_members
= update_idx
;
2033 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
2035 sp
->is_speculative
= 0;
2039 } /* compute_trg_info */
2042 /* Print candidates info, for debugging purposes. Callable from debugger. */
2048 if (!candidate_table
[i
].is_valid
)
2051 if (candidate_table
[i
].is_speculative
)
2054 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2056 fprintf (dump
, "split path: ");
2057 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2059 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2061 fprintf (dump
, " %d ", b
);
2063 fprintf (dump
, "\n");
2065 fprintf (dump
, "update path: ");
2066 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2068 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2070 fprintf (dump
, " %d ", b
);
2072 fprintf (dump
, "\n");
2076 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2081 /* Print candidates info, for debugging purposes. Callable from debugger. */
2084 debug_candidates (trg
)
2089 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2090 BB_TO_BLOCK (trg
), trg
);
2091 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2092 debug_candidate (i
);
2096 /* functions for speculative scheduing */
2098 /* Return 0 if x is a set of a register alive in the beginning of one
2099 of the split-blocks of src, otherwise return 1. */
2102 check_live_1 (src
, x
)
2108 register rtx reg
= SET_DEST (x
);
2113 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2114 || GET_CODE (reg
) == SIGN_EXTRACT
2115 || GET_CODE (reg
) == STRICT_LOW_PART
)
2116 reg
= XEXP (reg
, 0);
2118 if (GET_CODE (reg
) == PARALLEL
2119 && GET_MODE (reg
) == BLKmode
)
2122 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2123 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2128 if (GET_CODE (reg
) != REG
)
2131 regno
= REGNO (reg
);
2133 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2135 /* Global registers are assumed live */
2140 if (regno
< FIRST_PSEUDO_REGISTER
)
2142 /* check for hard registers */
2143 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2146 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2148 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2150 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
+ j
))
2159 /* check for psuedo registers */
2160 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2162 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2164 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
))
2176 /* If x is a set of a register R, mark that R is alive in the beginning
2177 of every update-block of src. */
2180 update_live_1 (src
, x
)
2186 register rtx reg
= SET_DEST (x
);
2191 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2192 || GET_CODE (reg
) == SIGN_EXTRACT
2193 || GET_CODE (reg
) == STRICT_LOW_PART
)
2194 reg
= XEXP (reg
, 0);
2196 if (GET_CODE (reg
) == PARALLEL
2197 && GET_MODE (reg
) == BLKmode
)
2200 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2201 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2205 if (GET_CODE (reg
) != REG
)
2208 /* Global registers are always live, so the code below does not apply
2211 regno
= REGNO (reg
);
2213 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2215 if (regno
< FIRST_PSEUDO_REGISTER
)
2217 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2220 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2222 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2224 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
+ j
);
2230 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2232 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2234 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
);
2241 /* Return 1 if insn can be speculatively moved from block src to trg,
2242 otherwise return 0. Called before first insertion of insn to
2243 ready-list or before the scheduling. */
2246 check_live (insn
, src
)
2250 /* find the registers set by instruction */
2251 if (GET_CODE (PATTERN (insn
)) == SET
2252 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2253 return check_live_1 (src
, PATTERN (insn
));
2254 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2257 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2258 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2259 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2260 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2270 /* Update the live registers info after insn was moved speculatively from
2271 block src to trg. */
2274 update_live (insn
, src
)
2278 /* find the registers set by instruction */
2279 if (GET_CODE (PATTERN (insn
)) == SET
2280 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2281 update_live_1 (src
, PATTERN (insn
));
2282 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2285 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2286 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2287 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2288 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2292 /* Exception Free Loads:
2294 We define five classes of speculative loads: IFREE, IRISKY,
2295 PFREE, PRISKY, and MFREE.
2297 IFREE loads are loads that are proved to be exception-free, just
2298 by examining the load insn. Examples for such loads are loads
2299 from TOC and loads of global data.
2301 IRISKY loads are loads that are proved to be exception-risky,
2302 just by examining the load insn. Examples for such loads are
2303 volatile loads and loads from shared memory.
2305 PFREE loads are loads for which we can prove, by examining other
2306 insns, that they are exception-free. Currently, this class consists
2307 of loads for which we are able to find a "similar load", either in
2308 the target block, or, if only one split-block exists, in that split
2309 block. Load2 is similar to load1 if both have same single base
2310 register. We identify only part of the similar loads, by finding
2311 an insn upon which both load1 and load2 have a DEF-USE dependence.
2313 PRISKY loads are loads for which we can prove, by examining other
2314 insns, that they are exception-risky. Currently we have two proofs for
2315 such loads. The first proof detects loads that are probably guarded by a
2316 test on the memory address. This proof is based on the
2317 backward and forward data dependence information for the region.
2318 Let load-insn be the examined load.
2319 Load-insn is PRISKY iff ALL the following hold:
2321 - insn1 is not in the same block as load-insn
2322 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2323 - test-insn is either a compare or a branch, not in the same block as load-insn
2324 - load-insn is reachable from test-insn
2325 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2327 This proof might fail when the compare and the load are fed
2328 by an insn not in the region. To solve this, we will add to this
2329 group all loads that have no input DEF-USE dependence.
2331 The second proof detects loads that are directly or indirectly
2332 fed by a speculative load. This proof is affected by the
2333 scheduling process. We will use the flag fed_by_spec_load.
2334 Initially, all insns have this flag reset. After a speculative
2335 motion of an insn, if insn is either a load, or marked as
2336 fed_by_spec_load, we will also mark as fed_by_spec_load every
2337 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2338 load which is fed_by_spec_load is also PRISKY.
2340 MFREE (maybe-free) loads are all the remaining loads. They may be
2341 exception-free, but we cannot prove it.
2343 Now, all loads in IFREE and PFREE classes are considered
2344 exception-free, while all loads in IRISKY and PRISKY classes are
2345 considered exception-risky. As for loads in the MFREE class,
2346 these are considered either exception-free or exception-risky,
2347 depending on whether we are pessimistic or optimistic. We have
2348 to take the pessimistic approach to assure the safety of
2349 speculative scheduling, but we can take the optimistic approach
2350 by invoking the -fsched_spec_load_dangerous option. */
2352 enum INSN_TRAP_CLASS
2354 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2355 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2358 #define WORST_CLASS(class1, class2) \
2359 ((class1 > class2) ? class1 : class2)
2361 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2362 /* some speculatively moved load insn and this one. */
2363 char *fed_by_spec_load
;
2366 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2367 #define IS_REACHABLE(bb_from, bb_to) \
2369 || IS_RGN_ENTRY (bb_from) \
2370 || (bitset_member (ancestor_edges[bb_to], \
2371 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2373 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2374 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2376 /* Non-zero iff the address is comprised from at most 1 register */
2377 #define CONST_BASED_ADDRESS_P(x) \
2378 (GET_CODE (x) == REG \
2379 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2380 || (GET_CODE (x) == LO_SUM)) \
2381 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2382 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2384 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2387 set_spec_fed (load_insn
)
2392 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2393 if (GET_MODE (link
) == VOIDmode
)
2394 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2395 } /* set_spec_fed */
2397 /* On the path from the insn to load_insn_bb, find a conditional branch */
2398 /* depending on insn, that guards the speculative load. */
2401 find_conditional_protection (insn
, load_insn_bb
)
2407 /* iterate through DEF-USE forward dependences */
2408 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2410 rtx next
= XEXP (link
, 0);
2411 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2412 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2413 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2414 && load_insn_bb
!= INSN_BB (next
)
2415 && GET_MODE (link
) == VOIDmode
2416 && (GET_CODE (next
) == JUMP_INSN
2417 || find_conditional_protection (next
, load_insn_bb
)))
2421 } /* find_conditional_protection */
2423 /* Returns 1 if the same insn1 that participates in the computation
2424 of load_insn's address is feeding a conditional branch that is
2425 guarding on load_insn. This is true if we find a the two DEF-USE
2427 insn1 -> ... -> conditional-branch
2428 insn1 -> ... -> load_insn,
2429 and if a flow path exist:
2430 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2431 and if insn1 is on the path
2432 region-entry -> ... -> bb_trg -> ... load_insn.
2434 Locate insn1 by climbing on LOG_LINKS from load_insn.
2435 Locate the branch by following INSN_DEPEND from insn1. */
2438 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2444 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2446 rtx insn1
= XEXP (link
, 0);
2448 /* must be a DEF-USE dependence upon non-branch */
2449 if (GET_MODE (link
) != VOIDmode
2450 || GET_CODE (insn1
) == JUMP_INSN
)
2453 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2454 if (INSN_BB (insn1
) == bb_src
2455 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2456 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2457 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2458 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2461 /* now search for the conditional-branch */
2462 if (find_conditional_protection (insn1
, bb_src
))
2465 /* recursive step: search another insn1, "above" current insn1. */
2466 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2469 /* the chain does not exsist */
2471 } /* is_conditionally_protected */
2473 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2474 load_insn can move speculatively from bb_src to bb_trg. All the
2475 following must hold:
2477 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2478 (2) load_insn and load1 have a def-use dependence upon
2479 the same insn 'insn1'.
2480 (3) either load2 is in bb_trg, or:
2481 - there's only one split-block, and
2482 - load1 is on the escape path, and
2484 From all these we can conclude that the two loads access memory
2485 addresses that differ at most by a constant, and hence if moving
2486 load_insn would cause an exception, it would have been caused by
2490 is_pfree (load_insn
, bb_src
, bb_trg
)
2495 register candidate
*candp
= candidate_table
+ bb_src
;
2497 if (candp
->split_bbs
.nr_members
!= 1)
2498 /* must have exactly one escape block */
2501 for (back_link
= LOG_LINKS (load_insn
);
2502 back_link
; back_link
= XEXP (back_link
, 1))
2504 rtx insn1
= XEXP (back_link
, 0);
2506 if (GET_MODE (back_link
) == VOIDmode
)
2508 /* found a DEF-USE dependence (insn1, load_insn) */
2511 for (fore_link
= INSN_DEPEND (insn1
);
2512 fore_link
; fore_link
= XEXP (fore_link
, 1))
2514 rtx insn2
= XEXP (fore_link
, 0);
2515 if (GET_MODE (fore_link
) == VOIDmode
)
2517 /* found a DEF-USE dependence (insn1, insn2) */
2518 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2519 /* insn2 not guaranteed to be a 1 base reg load */
2522 if (INSN_BB (insn2
) == bb_trg
)
2523 /* insn2 is the similar load, in the target block */
2526 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2527 /* insn2 is a similar load, in a split-block */
2534 /* couldn't find a similar load */
2538 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2539 as found by analyzing insn's expression. */
2542 may_trap_exp (x
, is_store
)
2550 code
= GET_CODE (x
);
2560 /* The insn uses memory */
2561 /* a volatile load */
2562 if (MEM_VOLATILE_P (x
))
2564 /* an exception-free load */
2565 if (!may_trap_p (x
))
2567 /* a load with 1 base register, to be further checked */
2568 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2569 return PFREE_CANDIDATE
;
2570 /* no info on the load, to be further checked */
2571 return PRISKY_CANDIDATE
;
2576 int i
, insn_class
= TRAP_FREE
;
2578 /* neither store nor load, check if it may cause a trap */
2581 /* recursive step: walk the insn... */
2582 fmt
= GET_RTX_FORMAT (code
);
2583 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2587 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2588 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2590 else if (fmt
[i
] == 'E')
2593 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2595 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2596 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2597 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2601 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2606 } /* may_trap_exp */
2609 /* Classifies insn for the purpose of verifying that it can be
2610 moved speculatively, by examining it's patterns, returning:
2611 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2612 TRAP_FREE: non-load insn.
2613 IFREE: load from a globaly safe location.
2614 IRISKY: volatile load.
2615 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2616 being either PFREE or PRISKY. */
2619 haifa_classify_insn (insn
)
2622 rtx pat
= PATTERN (insn
);
2623 int tmp_class
= TRAP_FREE
;
2624 int insn_class
= TRAP_FREE
;
2627 if (GET_CODE (pat
) == PARALLEL
)
2629 int i
, len
= XVECLEN (pat
, 0);
2631 for (i
= len
- 1; i
>= 0; i
--)
2633 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2637 /* test if it is a 'store' */
2638 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2641 /* test if it is a store */
2642 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2643 if (tmp_class
== TRAP_RISKY
)
2645 /* test if it is a load */
2647 WORST_CLASS (tmp_class
,
2648 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2651 tmp_class
= TRAP_RISKY
;
2655 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2656 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2662 code
= GET_CODE (pat
);
2666 /* test if it is a 'store' */
2667 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2670 /* test if it is a store */
2671 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2672 if (tmp_class
== TRAP_RISKY
)
2674 /* test if it is a load */
2676 WORST_CLASS (tmp_class
,
2677 may_trap_exp (SET_SRC (pat
), 0));
2680 tmp_class
= TRAP_RISKY
;
2684 insn_class
= tmp_class
;
2689 } /* haifa_classify_insn */
2691 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2692 a load moved speculatively, or if load_insn is protected by
2693 a compare on load_insn's address). */
2696 is_prisky (load_insn
, bb_src
, bb_trg
)
2700 if (FED_BY_SPEC_LOAD (load_insn
))
2703 if (LOG_LINKS (load_insn
) == NULL
)
2704 /* dependence may 'hide' out of the region. */
2707 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2713 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2714 Return 1 if insn is exception-free (and the motion is valid)
2718 is_exception_free (insn
, bb_src
, bb_trg
)
2722 int insn_class
= haifa_classify_insn (insn
);
2724 /* handle non-load insns */
2735 if (!flag_schedule_speculative_load
)
2737 IS_LOAD_INSN (insn
) = 1;
2744 case PFREE_CANDIDATE
:
2745 if (is_pfree (insn
, bb_src
, bb_trg
))
2747 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2748 case PRISKY_CANDIDATE
:
2749 if (!flag_schedule_speculative_load_dangerous
2750 || is_prisky (insn
, bb_src
, bb_trg
))
2756 return flag_schedule_speculative_load_dangerous
;
2757 } /* is_exception_free */
2760 /* Process an insn's memory dependencies. There are four kinds of
2763 (0) read dependence: read follows read
2764 (1) true dependence: read follows write
2765 (2) anti dependence: write follows read
2766 (3) output dependence: write follows write
2768 We are careful to build only dependencies which actually exist, and
2769 use transitivity to avoid building too many links. */
2771 /* Return the INSN_LIST containing INSN in LIST, or NULL
2772 if LIST does not contain INSN. */
2774 HAIFA_INLINE
static rtx
2775 find_insn_list (insn
, list
)
2781 if (XEXP (list
, 0) == insn
)
2783 list
= XEXP (list
, 1);
2789 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2791 HAIFA_INLINE
static char
2792 find_insn_mem_list (insn
, x
, list
, list1
)
2798 if (XEXP (list
, 0) == insn
2799 && XEXP (list1
, 0) == x
)
2801 list
= XEXP (list
, 1);
2802 list1
= XEXP (list1
, 1);
2808 /* Compute the function units used by INSN. This caches the value
2809 returned by function_units_used. A function unit is encoded as the
2810 unit number if the value is non-negative and the compliment of a
2811 mask if the value is negative. A function unit index is the
2812 non-negative encoding. */
2814 HAIFA_INLINE
static int
2818 register int unit
= INSN_UNIT (insn
);
2822 recog_memoized (insn
);
2824 /* A USE insn, or something else we don't need to understand.
2825 We can't pass these directly to function_units_used because it will
2826 trigger a fatal error for unrecognizable insns. */
2827 if (INSN_CODE (insn
) < 0)
2831 unit
= function_units_used (insn
);
2832 /* Increment non-negative values so we can cache zero. */
2836 /* We only cache 16 bits of the result, so if the value is out of
2837 range, don't cache it. */
2838 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2840 || (~unit
& ((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2841 INSN_UNIT (insn
) = unit
;
2843 return (unit
> 0 ? unit
- 1 : unit
);
2846 /* Compute the blockage range for executing INSN on UNIT. This caches
2847 the value returned by the blockage_range_function for the unit.
2848 These values are encoded in an int where the upper half gives the
2849 minimum value and the lower half gives the maximum value. */
2851 HAIFA_INLINE
static unsigned int
2852 blockage_range (unit
, insn
)
2856 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2859 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2861 range
= function_units
[unit
].blockage_range_function (insn
);
2862 /* We only cache the blockage range for one unit and then only if
2864 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2865 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2868 range
= BLOCKAGE_RANGE (blockage
);
2873 /* A vector indexed by function unit instance giving the last insn to use
2874 the unit. The value of the function unit instance index for unit U
2875 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2876 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2878 /* A vector indexed by function unit instance giving the minimum time when
2879 the unit will unblock based on the maximum blockage cost. */
2880 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2882 /* A vector indexed by function unit number giving the number of insns
2883 that remain to use the unit. */
2884 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2886 /* Reset the function unit state to the null state. */
2891 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2892 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2893 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2896 /* Return the issue-delay of an insn */
2898 HAIFA_INLINE
static int
2899 insn_issue_delay (insn
)
2903 int unit
= insn_unit (insn
);
2905 /* efficiency note: in fact, we are working 'hard' to compute a
2906 value that was available in md file, and is not available in
2907 function_units[] structure. It would be nice to have this
2908 value there, too. */
2911 if (function_units
[unit
].blockage_range_function
&&
2912 function_units
[unit
].blockage_function
)
2913 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2916 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2917 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2918 && function_units
[i
].blockage_function
)
2919 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2924 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2925 instance INSTANCE at time CLOCK if the previous actual hazard cost
2928 HAIFA_INLINE
static int
2929 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2930 int unit
, instance
, clock
, cost
;
2933 int tick
= unit_tick
[instance
]; /* issue time of the last issued insn */
2935 if (tick
- clock
> cost
)
2937 /* The scheduler is operating forward, so unit's last insn is the
2938 executing insn and INSN is the candidate insn. We want a
2939 more exact measure of the blockage if we execute INSN at CLOCK
2940 given when we committed the execution of the unit's last insn.
2942 The blockage value is given by either the unit's max blockage
2943 constant, blockage range function, or blockage function. Use
2944 the most exact form for the given unit. */
2946 if (function_units
[unit
].blockage_range_function
)
2948 if (function_units
[unit
].blockage_function
)
2949 tick
+= (function_units
[unit
].blockage_function
2950 (unit_last_insn
[instance
], insn
)
2951 - function_units
[unit
].max_blockage
);
2953 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2954 - function_units
[unit
].max_blockage
);
2956 if (tick
- clock
> cost
)
2957 cost
= tick
- clock
;
2962 /* Record INSN as having begun execution on the units encoded by UNIT at
2965 HAIFA_INLINE
static void
2966 schedule_unit (unit
, insn
, clock
)
2974 int instance
= unit
;
2975 #if MAX_MULTIPLICITY > 1
2976 /* Find the first free instance of the function unit and use that
2977 one. We assume that one is free. */
2978 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2980 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2982 instance
+= FUNCTION_UNITS_SIZE
;
2985 unit_last_insn
[instance
] = insn
;
2986 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2989 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2990 if ((unit
& 1) != 0)
2991 schedule_unit (i
, insn
, clock
);
2994 /* Return the actual hazard cost of executing INSN on the units encoded by
2995 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2997 HAIFA_INLINE
static int
2998 actual_hazard (unit
, insn
, clock
, cost
)
2999 int unit
, clock
, cost
;
3006 /* Find the instance of the function unit with the minimum hazard. */
3007 int instance
= unit
;
3008 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3012 #if MAX_MULTIPLICITY > 1
3013 if (best_cost
> cost
)
3015 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
3017 instance
+= FUNCTION_UNITS_SIZE
;
3018 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3020 if (this_cost
< best_cost
)
3022 best_cost
= this_cost
;
3023 if (this_cost
<= cost
)
3029 cost
= MAX (cost
, best_cost
);
3032 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3033 if ((unit
& 1) != 0)
3034 cost
= actual_hazard (i
, insn
, clock
, cost
);
3039 /* Return the potential hazard cost of executing an instruction on the
3040 units encoded by UNIT if the previous potential hazard cost was COST.
3041 An insn with a large blockage time is chosen in preference to one
3042 with a smaller time; an insn that uses a unit that is more likely
3043 to be used is chosen in preference to one with a unit that is less
3044 used. We are trying to minimize a subsequent actual hazard. */
3046 HAIFA_INLINE
static int
3047 potential_hazard (unit
, insn
, cost
)
3052 unsigned int minb
, maxb
;
3056 minb
= maxb
= function_units
[unit
].max_blockage
;
3059 if (function_units
[unit
].blockage_range_function
)
3061 maxb
= minb
= blockage_range (unit
, insn
);
3062 maxb
= MAX_BLOCKAGE_COST (maxb
);
3063 minb
= MIN_BLOCKAGE_COST (minb
);
3068 /* Make the number of instructions left dominate. Make the
3069 minimum delay dominate the maximum delay. If all these
3070 are the same, use the unit number to add an arbitrary
3071 ordering. Other terms can be added. */
3072 ncost
= minb
* 0x40 + maxb
;
3073 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3080 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3081 if ((unit
& 1) != 0)
3082 cost
= potential_hazard (i
, insn
, cost
);
3087 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3088 This is the number of cycles between instruction issue and
3089 instruction results. */
3091 HAIFA_INLINE
static int
3092 insn_cost (insn
, link
, used
)
3093 rtx insn
, link
, used
;
3095 register int cost
= INSN_COST (insn
);
3099 recog_memoized (insn
);
3101 /* A USE insn, or something else we don't need to understand.
3102 We can't pass these directly to result_ready_cost because it will
3103 trigger a fatal error for unrecognizable insns. */
3104 if (INSN_CODE (insn
) < 0)
3106 INSN_COST (insn
) = 1;
3111 cost
= result_ready_cost (insn
);
3116 INSN_COST (insn
) = cost
;
3120 /* in this case estimate cost without caring how insn is used. */
3121 if (link
== 0 && used
== 0)
3124 /* A USE insn should never require the value used to be computed. This
3125 allows the computation of a function's result and parameter values to
3126 overlap the return and call. */
3127 recog_memoized (used
);
3128 if (INSN_CODE (used
) < 0)
3129 LINK_COST_FREE (link
) = 1;
3131 /* If some dependencies vary the cost, compute the adjustment. Most
3132 commonly, the adjustment is complete: either the cost is ignored
3133 (in the case of an output- or anti-dependence), or the cost is
3134 unchanged. These values are cached in the link as LINK_COST_FREE
3135 and LINK_COST_ZERO. */
3137 if (LINK_COST_FREE (link
))
3140 else if (!LINK_COST_ZERO (link
))
3144 ADJUST_COST (used
, link
, insn
, ncost
);
3146 LINK_COST_FREE (link
) = ncost
= 1;
3148 LINK_COST_ZERO (link
) = 1;
3155 /* Compute the priority number for INSN. */
3164 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3167 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3169 if (INSN_DEPEND (insn
) == 0)
3170 this_priority
= insn_cost (insn
, 0, 0);
3172 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3177 if (RTX_INTEGRATED_P (link
))
3180 next
= XEXP (link
, 0);
3182 /* critical path is meaningful in block boundaries only */
3183 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3186 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3187 if (next_priority
> this_priority
)
3188 this_priority
= next_priority
;
3190 INSN_PRIORITY (insn
) = this_priority
;
3192 return this_priority
;
3196 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3197 them to the unused_*_list variables, so that they can be reused. */
3200 free_pending_lists ()
3202 if (current_nr_blocks
<= 1)
3204 free_list (&pending_read_insns
, &unused_insn_list
);
3205 free_list (&pending_write_insns
, &unused_insn_list
);
3206 free_list (&pending_read_mems
, &unused_expr_list
);
3207 free_list (&pending_write_mems
, &unused_expr_list
);
3211 /* interblock scheduling */
3214 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3216 free_list (&bb_pending_read_insns
[bb
], &unused_insn_list
);
3217 free_list (&bb_pending_write_insns
[bb
], &unused_insn_list
);
3218 free_list (&bb_pending_read_mems
[bb
], &unused_expr_list
);
3219 free_list (&bb_pending_write_mems
[bb
], &unused_expr_list
);
3224 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3225 The MEM is a memory reference contained within INSN, which we are saving
3226 so that we can do memory aliasing on it. */
3229 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3230 rtx
*insn_list
, *mem_list
, insn
, mem
;
3234 link
= alloc_INSN_LIST (insn
, *insn_list
);
3237 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3240 pending_lists_length
++;
3244 /* Make a dependency between every memory reference on the pending lists
3245 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3249 flush_pending_lists (insn
, only_write
)
3256 while (pending_read_insns
&& ! only_write
)
3258 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3260 link
= pending_read_insns
;
3261 pending_read_insns
= XEXP (pending_read_insns
, 1);
3262 XEXP (link
, 1) = unused_insn_list
;
3263 unused_insn_list
= link
;
3265 link
= pending_read_mems
;
3266 pending_read_mems
= XEXP (pending_read_mems
, 1);
3267 XEXP (link
, 1) = unused_expr_list
;
3268 unused_expr_list
= link
;
3270 while (pending_write_insns
)
3272 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3274 link
= pending_write_insns
;
3275 pending_write_insns
= XEXP (pending_write_insns
, 1);
3276 XEXP (link
, 1) = unused_insn_list
;
3277 unused_insn_list
= link
;
3279 link
= pending_write_mems
;
3280 pending_write_mems
= XEXP (pending_write_mems
, 1);
3281 XEXP (link
, 1) = unused_expr_list
;
3282 unused_expr_list
= link
;
3284 pending_lists_length
= 0;
3286 /* last_pending_memory_flush is now a list of insns */
3287 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3288 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3290 free_list (&last_pending_memory_flush
, &unused_insn_list
);
3291 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3294 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3295 by the write to the destination of X, and reads of everything mentioned. */
3298 sched_analyze_1 (x
, insn
)
3303 register rtx dest
= SET_DEST (x
);
3308 if (GET_CODE (dest
) == PARALLEL
3309 && GET_MODE (dest
) == BLKmode
)
3312 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3313 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3314 if (GET_CODE (x
) == SET
)
3315 sched_analyze_2 (SET_SRC (x
), insn
);
3319 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3320 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3322 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3324 /* The second and third arguments are values read by this insn. */
3325 sched_analyze_2 (XEXP (dest
, 1), insn
);
3326 sched_analyze_2 (XEXP (dest
, 2), insn
);
3328 dest
= SUBREG_REG (dest
);
3331 if (GET_CODE (dest
) == REG
)
3335 regno
= REGNO (dest
);
3337 /* A hard reg in a wide mode may really be multiple registers.
3338 If so, mark all of them just like the first. */
3339 if (regno
< FIRST_PSEUDO_REGISTER
)
3341 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3346 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3347 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3348 reg_last_uses
[regno
+ i
] = 0;
3350 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3351 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3353 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3355 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3356 /* Function calls clobber all call_used regs. */
3357 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3358 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3365 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3366 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3367 reg_last_uses
[regno
] = 0;
3369 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3370 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3372 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3374 /* Pseudos that are REG_EQUIV to something may be replaced
3375 by that during reloading. We need only add dependencies for
3376 the address in the REG_EQUIV note. */
3377 if (!reload_completed
3378 && reg_known_equiv_p
[regno
]
3379 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3380 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3382 /* Don't let it cross a call after scheduling if it doesn't
3383 already cross one. */
3385 if (REG_N_CALLS_CROSSED (regno
) == 0)
3386 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3387 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3390 else if (GET_CODE (dest
) == MEM
)
3392 /* Writing memory. */
3394 if (pending_lists_length
> 32)
3396 /* Flush all pending reads and writes to prevent the pending lists
3397 from getting any larger. Insn scheduling runs too slowly when
3398 these lists get long. The number 32 was chosen because it
3399 seems like a reasonable number. When compiling GCC with itself,
3400 this flush occurs 8 times for sparc, and 10 times for m88k using
3402 flush_pending_lists (insn
, 0);
3407 rtx pending
, pending_mem
;
3409 pending
= pending_read_insns
;
3410 pending_mem
= pending_read_mems
;
3413 /* If a dependency already exists, don't create a new one. */
3414 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3415 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3416 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3418 pending
= XEXP (pending
, 1);
3419 pending_mem
= XEXP (pending_mem
, 1);
3422 pending
= pending_write_insns
;
3423 pending_mem
= pending_write_mems
;
3426 /* If a dependency already exists, don't create a new one. */
3427 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3428 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3429 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3431 pending
= XEXP (pending
, 1);
3432 pending_mem
= XEXP (pending_mem
, 1);
3435 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3436 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3438 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3441 sched_analyze_2 (XEXP (dest
, 0), insn
);
3444 /* Analyze reads. */
3445 if (GET_CODE (x
) == SET
)
3446 sched_analyze_2 (SET_SRC (x
), insn
);
3449 /* Analyze the uses of memory and registers in rtx X in INSN. */
3452 sched_analyze_2 (x
, insn
)
3458 register enum rtx_code code
;
3464 code
= GET_CODE (x
);
3473 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3474 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3475 this does not mean that this insn is using cc0. */
3483 /* User of CC0 depends on immediately preceding insn. */
3484 SCHED_GROUP_P (insn
) = 1;
3486 /* There may be a note before this insn now, but all notes will
3487 be removed before we actually try to schedule the insns, so
3488 it won't cause a problem later. We must avoid it here though. */
3489 prev
= prev_nonnote_insn (insn
);
3491 /* Make a copy of all dependencies on the immediately previous insn,
3492 and add to this insn. This is so that all the dependencies will
3493 apply to the group. Remove an explicit dependence on this insn
3494 as SCHED_GROUP_P now represents it. */
3496 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3497 remove_dependence (insn
, prev
);
3499 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3500 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3509 int regno
= REGNO (x
);
3510 if (regno
< FIRST_PSEUDO_REGISTER
)
3514 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3517 reg_last_uses
[regno
+ i
]
3518 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3520 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3521 add_dependence (insn
, XEXP (u
, 0), 0);
3523 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3524 /* Function calls clobber all call_used regs. */
3525 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3526 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3531 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
, reg_last_uses
[regno
]);
3533 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3534 add_dependence (insn
, XEXP (u
, 0), 0);
3536 /* Pseudos that are REG_EQUIV to something may be replaced
3537 by that during reloading. We need only add dependencies for
3538 the address in the REG_EQUIV note. */
3539 if (!reload_completed
3540 && reg_known_equiv_p
[regno
]
3541 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3542 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3544 /* If the register does not already cross any calls, then add this
3545 insn to the sched_before_next_call list so that it will still
3546 not cross calls after scheduling. */
3547 if (REG_N_CALLS_CROSSED (regno
) == 0)
3548 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3555 /* Reading memory. */
3557 rtx pending
, pending_mem
;
3559 pending
= pending_read_insns
;
3560 pending_mem
= pending_read_mems
;
3563 /* If a dependency already exists, don't create a new one. */
3564 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3565 if (read_dependence (XEXP (pending_mem
, 0), x
))
3566 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3568 pending
= XEXP (pending
, 1);
3569 pending_mem
= XEXP (pending_mem
, 1);
3572 pending
= pending_write_insns
;
3573 pending_mem
= pending_write_mems
;
3576 /* If a dependency already exists, don't create a new one. */
3577 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3578 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3580 add_dependence (insn
, XEXP (pending
, 0), 0);
3582 pending
= XEXP (pending
, 1);
3583 pending_mem
= XEXP (pending_mem
, 1);
3586 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3587 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3589 /* Always add these dependencies to pending_reads, since
3590 this insn may be followed by a write. */
3591 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3594 /* Take advantage of tail recursion here. */
3595 sched_analyze_2 (XEXP (x
, 0), insn
);
3599 /* Force pending stores to memory in case a trap handler needs them. */
3601 flush_pending_lists (insn
, 1);
3606 case UNSPEC_VOLATILE
:
3610 /* Traditional and volatile asm instructions must be considered to use
3611 and clobber all hard registers, all pseudo-registers and all of
3612 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3614 Consider for instance a volatile asm that changes the fpu rounding
3615 mode. An insn should not be moved across this even if it only uses
3616 pseudo-regs because it might give an incorrectly rounded result. */
3617 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3619 int max_reg
= max_reg_num ();
3620 for (i
= 0; i
< max_reg
; i
++)
3622 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3623 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3624 reg_last_uses
[i
] = 0;
3626 /* reg_last_sets[r] is now a list of insns */
3627 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3628 add_dependence (insn
, XEXP (u
, 0), 0);
3630 reg_pending_sets_all
= 1;
3632 flush_pending_lists (insn
, 0);
3635 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3636 We can not just fall through here since then we would be confused
3637 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3638 traditional asms unlike their normal usage. */
3640 if (code
== ASM_OPERANDS
)
3642 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3643 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3653 /* These both read and modify the result. We must handle them as writes
3654 to get proper dependencies for following instructions. We must handle
3655 them as reads to get proper dependencies from this to previous
3656 instructions. Thus we need to pass them to both sched_analyze_1
3657 and sched_analyze_2. We must call sched_analyze_2 first in order
3658 to get the proper antecedent for the read. */
3659 sched_analyze_2 (XEXP (x
, 0), insn
);
3660 sched_analyze_1 (x
, insn
);
3667 /* Other cases: walk the insn. */
3668 fmt
= GET_RTX_FORMAT (code
);
3669 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3672 sched_analyze_2 (XEXP (x
, i
), insn
);
3673 else if (fmt
[i
] == 'E')
3674 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3675 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3679 /* Analyze an INSN with pattern X to find all dependencies. */
3682 sched_analyze_insn (x
, insn
, loop_notes
)
3686 register RTX_CODE code
= GET_CODE (x
);
3688 int maxreg
= max_reg_num ();
3691 if (code
== SET
|| code
== CLOBBER
)
3692 sched_analyze_1 (x
, insn
);
3693 else if (code
== PARALLEL
)
3696 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3698 code
= GET_CODE (XVECEXP (x
, 0, i
));
3699 if (code
== SET
|| code
== CLOBBER
)
3700 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3702 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3706 sched_analyze_2 (x
, insn
);
3708 /* Mark registers CLOBBERED or used by called function. */
3709 if (GET_CODE (insn
) == CALL_INSN
)
3710 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3712 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3713 sched_analyze_1 (XEXP (link
, 0), insn
);
3715 sched_analyze_2 (XEXP (link
, 0), insn
);
3718 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3719 block, then we must be sure that no instructions are scheduled across it.
3720 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3721 become incorrect. */
3725 int max_reg
= max_reg_num ();
3726 int schedule_barrier_found
= 0;
3729 /* Update loop_notes with any notes from this insn. Also determine
3730 if any of the notes on the list correspond to instruction scheduling
3731 barriers (loop, eh & setjmp notes, but not range notes. */
3733 while (XEXP (link
, 1))
3735 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3736 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3737 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3738 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3739 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3740 schedule_barrier_found
= 1;
3742 link
= XEXP (link
, 1);
3744 XEXP (link
, 1) = REG_NOTES (insn
);
3745 REG_NOTES (insn
) = loop_notes
;
3747 /* Add dependencies if a scheduling barrier was found. */
3748 if (schedule_barrier_found
)
3750 for (i
= 0; i
< max_reg
; i
++)
3753 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3754 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3755 reg_last_uses
[i
] = 0;
3757 /* reg_last_sets[r] is now a list of insns */
3758 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3759 add_dependence (insn
, XEXP (u
, 0), 0);
3761 reg_pending_sets_all
= 1;
3763 flush_pending_lists (insn
, 0);
3768 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3770 /* reg_last_sets[r] is now a list of insns */
3771 free_list (®_last_sets
[i
], &unused_insn_list
);
3773 = alloc_INSN_LIST (insn
, NULL_RTX
);
3775 CLEAR_REG_SET (reg_pending_sets
);
3777 if (reg_pending_sets_all
)
3779 for (i
= 0; i
< maxreg
; i
++)
3781 /* reg_last_sets[r] is now a list of insns */
3782 free_list (®_last_sets
[i
], &unused_insn_list
);
3783 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3786 reg_pending_sets_all
= 0;
3789 /* Handle function calls and function returns created by the epilogue
3791 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3796 /* When scheduling instructions, we make sure calls don't lose their
3797 accompanying USE insns by depending them one on another in order.
3799 Also, we must do the same thing for returns created by the epilogue
3800 threading code. Note this code works only in this special case,
3801 because other passes make no guarantee that they will never emit
3802 an instruction between a USE and a RETURN. There is such a guarantee
3803 for USE instructions immediately before a call. */
3805 prev_dep_insn
= insn
;
3806 dep_insn
= PREV_INSN (insn
);
3807 while (GET_CODE (dep_insn
) == INSN
3808 && GET_CODE (PATTERN (dep_insn
)) == USE
3809 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3811 SCHED_GROUP_P (prev_dep_insn
) = 1;
3813 /* Make a copy of all dependencies on dep_insn, and add to insn.
3814 This is so that all of the dependencies will apply to the
3817 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3818 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3820 prev_dep_insn
= dep_insn
;
3821 dep_insn
= PREV_INSN (dep_insn
);
3826 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3827 for every dependency. */
3830 sched_analyze (head
, tail
)
3837 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3839 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3841 /* Make each JUMP_INSN a scheduling barrier for memory references. */
3842 if (GET_CODE (insn
) == JUMP_INSN
)
3843 last_pending_memory_flush
3844 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3845 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3848 else if (GET_CODE (insn
) == CALL_INSN
)
3853 CANT_MOVE (insn
) = 1;
3855 /* Any instruction using a hard register which may get clobbered
3856 by a call needs to be marked as dependent on this call.
3857 This prevents a use of a hard return reg from being moved
3858 past a void call (i.e. it does not explicitly set the hard
3861 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3862 all registers, not just hard registers, may be clobbered by this
3865 /* Insn, being a CALL_INSN, magically depends on
3866 `last_function_call' already. */
3868 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3869 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3871 int max_reg
= max_reg_num ();
3872 for (i
= 0; i
< max_reg
; i
++)
3874 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3875 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3877 reg_last_uses
[i
] = 0;
3879 /* reg_last_sets[r] is now a list of insns */
3880 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3881 add_dependence (insn
, XEXP (u
, 0), 0);
3883 reg_pending_sets_all
= 1;
3885 /* Add a pair of fake REG_NOTE which we will later
3886 convert back into a NOTE_INSN_SETJMP note. See
3887 reemit_notes for why we use a pair of NOTEs. */
3888 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3891 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3892 GEN_INT (NOTE_INSN_SETJMP
),
3897 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3898 if (call_used_regs
[i
] || global_regs
[i
])
3900 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3901 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3902 reg_last_uses
[i
] = 0;
3904 /* reg_last_sets[r] is now a list of insns */
3905 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3906 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3908 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3912 /* For each insn which shouldn't cross a call, add a dependence
3913 between that insn and this call insn. */
3914 x
= LOG_LINKS (sched_before_next_call
);
3917 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3920 LOG_LINKS (sched_before_next_call
) = 0;
3922 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3925 /* In the absence of interprocedural alias analysis, we must flush
3926 all pending reads and writes, and start new dependencies starting
3927 from here. But only flush writes for constant calls (which may
3928 be passed a pointer to something we haven't written yet). */
3929 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3931 /* Depend this function call (actually, the user of this
3932 function call) on all hard register clobberage. */
3934 /* last_function_call is now a list of insns */
3935 free_list(&last_function_call
, &unused_insn_list
);
3936 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3939 /* See comments on reemit_notes as to why we do this. */
3940 /* ??? Actually, the reemit_notes just say what is done, not why. */
3942 else if (GET_CODE (insn
) == NOTE
3943 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3944 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3946 loop_notes
= alloc_EXPR_LIST (REG_DEAD
, NOTE_RANGE_INFO (insn
),
3948 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3949 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3952 else if (GET_CODE (insn
) == NOTE
3953 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3954 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3955 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3956 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3957 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3958 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3960 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3961 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
3963 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3964 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3966 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3975 /* Called when we see a set of a register. If death is true, then we are
3976 scanning backwards. Mark that register as unborn. If nobody says
3977 otherwise, that is how things will remain. If death is false, then we
3978 are scanning forwards. Mark that register as being born. */
3981 sched_note_set (x
, death
)
3986 register rtx reg
= SET_DEST (x
);
3992 if (GET_CODE (reg
) == PARALLEL
3993 && GET_MODE (reg
) == BLKmode
)
3996 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
3997 sched_note_set (XVECEXP (reg
, 0, i
), death
);
4001 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
4002 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
4004 /* Must treat modification of just one hardware register of a multi-reg
4005 value or just a byte field of a register exactly the same way that
4006 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4007 does not kill the entire register. */
4008 if (GET_CODE (reg
) != SUBREG
4009 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
4012 reg
= SUBREG_REG (reg
);
4015 if (GET_CODE (reg
) != REG
)
4018 /* Global registers are always live, so the code below does not apply
4021 regno
= REGNO (reg
);
4022 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
4026 /* If we only set part of the register, then this set does not
4031 /* Try killing this register. */
4032 if (regno
< FIRST_PSEUDO_REGISTER
)
4034 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4037 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4042 /* Recompute REG_BASIC_BLOCK as we update all the other
4043 dataflow information. */
4044 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4045 sched_reg_basic_block
[regno
] = current_block_num
;
4046 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4047 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4049 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
4054 /* Make the register live again. */
4055 if (regno
< FIRST_PSEUDO_REGISTER
)
4057 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4060 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4065 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4071 /* Macros and functions for keeping the priority queue sorted, and
4072 dealing with queueing and dequeueing of instructions. */
4074 #define SCHED_SORT(READY, N_READY) \
4075 do { if ((N_READY) == 2) \
4076 swap_sort (READY, N_READY); \
4077 else if ((N_READY) > 2) \
4078 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4081 /* Returns a positive value if x is preferred; returns a negative value if
4082 y is preferred. Should never return 0, since that will make the sort
4086 rank_for_schedule (x
, y
)
4087 const GENERIC_PTR x
;
4088 const GENERIC_PTR y
;
4090 rtx tmp
= *(rtx
*)y
;
4091 rtx tmp2
= *(rtx
*)x
;
4093 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
4094 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
4097 /* prefer insn with higher priority */
4098 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
4100 return priority_val
;
4102 /* prefer an insn with smaller contribution to registers-pressure */
4103 if (!reload_completed
&&
4104 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4105 return (weight_val
);
4107 /* some comparison make sense in interblock scheduling only */
4108 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4110 /* prefer an inblock motion on an interblock motion */
4111 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4113 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4116 /* prefer a useful motion on a speculative one */
4117 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4120 /* prefer a more probable (speculative) insn */
4121 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4126 /* compare insns based on their relation to the last-scheduled-insn */
4127 if (last_scheduled_insn
)
4129 /* Classify the instructions into three classes:
4130 1) Data dependent on last schedule insn.
4131 2) Anti/Output dependent on last scheduled insn.
4132 3) Independent of last scheduled insn, or has latency of one.
4133 Choose the insn from the highest numbered class if different. */
4134 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4135 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4137 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4142 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4143 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4145 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4150 if ((val
= tmp2_class
- tmp_class
))
4154 /* Prefer the insn which has more later insns that depend on it.
4155 This gives the scheduler more freedom when scheduling later
4156 instructions at the expense of added register pressure. */
4158 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4162 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4165 val
= depend_count2
- depend_count1
;
4169 /* If insns are equally good, sort by INSN_LUID (original insn order),
4170 so that we make the sort stable. This minimizes instruction movement,
4171 thus minimizing sched's effect on debugging and cross-jumping. */
4172 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4175 /* Resort the array A in which only element at index N may be out of order. */
4177 HAIFA_INLINE
static void
4182 rtx insn
= a
[n
- 1];
4185 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4193 static int max_priority
;
4195 /* Add INSN to the insn queue so that it can be executed at least
4196 N_CYCLES after the currently executing insn. Preserve insns
4197 chain for debugging purposes. */
4199 HAIFA_INLINE
static void
4200 queue_insn (insn
, n_cycles
)
4204 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4205 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4206 insn_queue
[next_q
] = link
;
4209 if (sched_verbose
>= 2)
4211 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4213 if (INSN_BB (insn
) != target_bb
)
4214 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4216 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4221 /* Return nonzero if PAT is the pattern of an insn which makes a
4224 HAIFA_INLINE
static int
4225 birthing_insn_p (pat
)
4230 if (reload_completed
== 1)
4233 if (GET_CODE (pat
) == SET
4234 && (GET_CODE (SET_DEST (pat
)) == REG
4235 || (GET_CODE (SET_DEST (pat
)) == PARALLEL
4236 && GET_MODE (SET_DEST (pat
)) == BLKmode
)))
4238 rtx dest
= SET_DEST (pat
);
4241 /* It would be more accurate to use refers_to_regno_p or
4242 reg_mentioned_p to determine when the dest is not live before this
4244 if (GET_CODE (dest
) == REG
)
4247 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4248 return (REG_N_SETS (i
) == 1);
4252 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
4254 int regno
= REGNO (SET_DEST (XVECEXP (dest
, 0, i
)));
4255 if (REGNO_REG_SET_P (bb_live_regs
, regno
))
4256 return (REG_N_SETS (regno
) == 1);
4261 if (GET_CODE (pat
) == PARALLEL
)
4263 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4264 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4270 /* PREV is an insn that is ready to execute. Adjust its priority if that
4271 will help shorten register lifetimes. */
4273 HAIFA_INLINE
static void
4274 adjust_priority (prev
)
4277 /* Trying to shorten register lives after reload has completed
4278 is useless and wrong. It gives inaccurate schedules. */
4279 if (reload_completed
== 0)
4284 /* ??? This code has no effect, because REG_DEAD notes are removed
4285 before we ever get here. */
4286 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4287 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4290 /* Defer scheduling insns which kill registers, since that
4291 shortens register lives. Prefer scheduling insns which
4292 make registers live for the same reason. */
4296 INSN_PRIORITY (prev
) >>= 3;
4299 INSN_PRIORITY (prev
) >>= 2;
4303 INSN_PRIORITY (prev
) >>= 1;
4306 if (birthing_insn_p (PATTERN (prev
)))
4308 int max
= max_priority
;
4310 if (max
> INSN_PRIORITY (prev
))
4311 INSN_PRIORITY (prev
) = max
;
4315 #ifdef ADJUST_PRIORITY
4316 ADJUST_PRIORITY (prev
);
4321 /* Clock at which the previous instruction was issued. */
4322 static int last_clock_var
;
4324 /* INSN is the "currently executing insn". Launch each insn which was
4325 waiting on INSN. READY is a vector of insns which are ready to fire.
4326 N_READY is the number of elements in READY. CLOCK is the current
4330 schedule_insn (insn
, ready
, n_ready
, clock
)
4339 unit
= insn_unit (insn
);
4341 if (sched_verbose
>= 2)
4343 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn
));
4344 insn_print_units (insn
);
4345 fprintf (dump
, "\n");
4348 if (sched_verbose
&& unit
== -1)
4349 visualize_no_unit (insn
);
4351 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4352 schedule_unit (unit
, insn
, clock
);
4354 if (INSN_DEPEND (insn
) == 0)
4357 /* This is used by the function adjust_priority above. */
4359 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4361 max_priority
= INSN_PRIORITY (insn
);
4363 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4365 rtx next
= XEXP (link
, 0);
4366 int cost
= insn_cost (insn
, link
, next
);
4368 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4370 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4372 int effective_cost
= INSN_TICK (next
) - clock
;
4374 /* For speculative insns, before inserting to ready/queue,
4375 check live, exception-free, and issue-delay */
4376 if (INSN_BB (next
) != target_bb
4377 && (!IS_VALID (INSN_BB (next
))
4379 || (IS_SPECULATIVE_INSN (next
)
4380 && (insn_issue_delay (next
) > 3
4381 || !check_live (next
, INSN_BB (next
))
4382 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4385 if (sched_verbose
>= 2)
4387 fprintf (dump
, ";;\t\tdependences resolved: insn %d ", INSN_UID (next
));
4389 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4390 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4392 if (effective_cost
<= 1)
4393 fprintf (dump
, "into ready\n");
4395 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4398 /* Adjust the priority of NEXT and either put it on the ready
4399 list or queue it. */
4400 adjust_priority (next
);
4401 if (effective_cost
<= 1)
4402 ready
[n_ready
++] = next
;
4404 queue_insn (next
, effective_cost
);
4408 /* Annotate the instruction with issue information -- TImode
4409 indicates that the instruction is expected not to be able
4410 to issue on the same cycle as the previous insn. A machine
4411 may use this information to decide how the instruction should
4413 if (reload_completed
&& issue_rate
> 1)
4415 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4416 last_clock_var
= clock
;
4423 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4427 create_reg_dead_note (reg
, insn
)
4432 /* The number of registers killed after scheduling must be the same as the
4433 number of registers killed before scheduling. The number of REG_DEAD
4434 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4435 might become one DImode hard register REG_DEAD note, but the number of
4436 registers killed will be conserved.
4438 We carefully remove REG_DEAD notes from the dead_notes list, so that
4439 there will be none left at the end. If we run out early, then there
4440 is a bug somewhere in flow, combine and/or sched. */
4442 if (dead_notes
== 0)
4444 if (current_nr_blocks
<= 1)
4447 link
= alloc_EXPR_LIST (REG_DEAD
, NULL_RTX
, NULL_RTX
);
4451 /* Number of regs killed by REG. */
4452 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4453 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4454 /* Number of regs killed by REG_DEAD notes taken off the list. */
4458 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4459 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4460 GET_MODE (XEXP (link
, 0))));
4461 while (reg_note_regs
< regs_killed
)
4463 link
= XEXP (link
, 1);
4465 /* LINK might be zero if we killed more registers after scheduling
4466 than before, and the last hard register we kill is actually
4469 This is normal for interblock scheduling, so deal with it in
4470 that case, else abort. */
4471 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4473 else if (link
== NULL_RTX
)
4474 link
= alloc_EXPR_LIST (REG_DEAD
, gen_rtx_REG (word_mode
, 0),
4477 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4478 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4479 GET_MODE (XEXP (link
, 0))));
4481 dead_notes
= XEXP (link
, 1);
4483 /* If we took too many regs kills off, put the extra ones back. */
4484 while (reg_note_regs
> regs_killed
)
4486 rtx temp_reg
, temp_link
;
4488 temp_reg
= gen_rtx_REG (word_mode
, 0);
4489 temp_link
= alloc_EXPR_LIST (REG_DEAD
, temp_reg
, dead_notes
);
4490 dead_notes
= temp_link
;
4495 XEXP (link
, 0) = reg
;
4496 XEXP (link
, 1) = REG_NOTES (insn
);
4497 REG_NOTES (insn
) = link
;
4500 /* Subroutine on attach_deaths_insn--handles the recursive search
4501 through INSN. If SET_P is true, then x is being modified by the insn. */
4504 attach_deaths (x
, insn
, set_p
)
4511 register enum rtx_code code
;
4517 code
= GET_CODE (x
);
4529 /* Get rid of the easy cases first. */
4534 /* If the register dies in this insn, queue that note, and mark
4535 this register as needing to die. */
4536 /* This code is very similar to mark_used_1 (if set_p is false)
4537 and mark_set_1 (if set_p is true) in flow.c. */
4547 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4548 if (regno
< FIRST_PSEUDO_REGISTER
)
4552 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4555 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4556 some_needed
|= needed
;
4557 all_needed
&= needed
;
4561 /* If it wasn't live before we started, then add a REG_DEAD note.
4562 We must check the previous lifetime info not the current info,
4563 because we may have to execute this code several times, e.g.
4564 once for a clobber (which doesn't add a note) and later
4565 for a use (which does add a note).
4567 Always make the register live. We must do this even if it was
4568 live before, because this may be an insn which sets and uses
4569 the same register, in which case the register has already been
4570 killed, so we must make it live again.
4572 Global registers are always live, and should never have a REG_DEAD
4573 note added for them, so none of the code below applies to them. */
4575 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4577 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4578 STACK_POINTER_REGNUM, since these are always considered to be
4579 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4580 if (regno
!= FRAME_POINTER_REGNUM
4581 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4582 && ! (regno
== HARD_FRAME_POINTER_REGNUM
)
4584 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4585 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4587 && regno
!= STACK_POINTER_REGNUM
)
4589 if (! all_needed
&& ! dead_or_set_p (insn
, x
))
4591 /* Check for the case where the register dying partially
4592 overlaps the register set by this insn. */
4593 if (regno
< FIRST_PSEUDO_REGISTER
4594 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4596 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4598 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4601 /* If none of the words in X is needed, make a REG_DEAD
4602 note. Otherwise, we must make partial REG_DEAD
4605 create_reg_dead_note (x
, insn
);
4610 /* Don't make a REG_DEAD note for a part of a
4611 register that is set in the insn. */
4612 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4614 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4615 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4616 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4623 if (regno
< FIRST_PSEUDO_REGISTER
)
4625 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4628 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4633 /* Recompute REG_BASIC_BLOCK as we update all the other
4634 dataflow information. */
4635 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4636 sched_reg_basic_block
[regno
] = current_block_num
;
4637 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4638 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4640 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4647 /* Handle tail-recursive case. */
4648 attach_deaths (XEXP (x
, 0), insn
, 0);
4652 attach_deaths (SUBREG_REG (x
), insn
,
4653 set_p
&& ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4655 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4656 == GET_MODE_SIZE (GET_MODE ((x
))))));
4659 case STRICT_LOW_PART
:
4660 attach_deaths (XEXP (x
, 0), insn
, 0);
4665 attach_deaths (XEXP (x
, 0), insn
, 0);
4666 attach_deaths (XEXP (x
, 1), insn
, 0);
4667 attach_deaths (XEXP (x
, 2), insn
, 0);
4672 && GET_MODE (x
) == BLKmode
)
4674 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4675 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4681 /* Other cases: walk the insn. */
4682 fmt
= GET_RTX_FORMAT (code
);
4683 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4686 attach_deaths (XEXP (x
, i
), insn
, 0);
4687 else if (fmt
[i
] == 'E')
4688 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4689 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4694 /* After INSN has executed, add register death notes for each register
4695 that is dead after INSN. */
4698 attach_deaths_insn (insn
)
4701 rtx x
= PATTERN (insn
);
4702 register RTX_CODE code
= GET_CODE (x
);
4707 attach_deaths (SET_SRC (x
), insn
, 0);
4709 /* A register might die here even if it is the destination, e.g.
4710 it is the target of a volatile read and is otherwise unused.
4711 Hence we must always call attach_deaths for the SET_DEST. */
4712 attach_deaths (SET_DEST (x
), insn
, 1);
4714 else if (code
== PARALLEL
)
4717 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4719 code
= GET_CODE (XVECEXP (x
, 0, i
));
4722 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4724 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4726 /* Flow does not add REG_DEAD notes to registers that die in
4727 clobbers, so we can't either. */
4728 else if (code
!= CLOBBER
)
4729 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4732 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4733 MEM being clobbered, just like flow. */
4734 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4735 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4736 /* Otherwise don't add a death note to things being clobbered. */
4737 else if (code
!= CLOBBER
)
4738 attach_deaths (x
, insn
, 0);
4740 /* Make death notes for things used in the called function. */
4741 if (GET_CODE (insn
) == CALL_INSN
)
4742 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4743 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4744 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4747 /* functions for handlnig of notes */
4749 /* Delete notes beginning with INSN and put them in the chain
4750 of notes ended by NOTE_LIST.
4751 Returns the insn following the notes. */
4754 unlink_other_notes (insn
, tail
)
4757 rtx prev
= PREV_INSN (insn
);
4759 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4761 rtx next
= NEXT_INSN (insn
);
4762 /* Delete the note from its current position. */
4764 NEXT_INSN (prev
) = next
;
4766 PREV_INSN (next
) = prev
;
4768 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4769 immediately after the call they follow. We use a fake
4770 (REG_DEAD (const_int -1)) note to remember them.
4771 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4772 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4773 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4774 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4775 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4776 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4777 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4778 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4780 /* Insert the note at the end of the notes list. */
4781 PREV_INSN (insn
) = note_list
;
4783 NEXT_INSN (note_list
) = insn
;
4792 /* Delete line notes beginning with INSN. Record line-number notes so
4793 they can be reused. Returns the insn following the notes. */
4796 unlink_line_notes (insn
, tail
)
4799 rtx prev
= PREV_INSN (insn
);
4801 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4803 rtx next
= NEXT_INSN (insn
);
4805 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4807 /* Delete the note from its current position. */
4809 NEXT_INSN (prev
) = next
;
4811 PREV_INSN (next
) = prev
;
4813 /* Record line-number notes so they can be reused. */
4814 LINE_NOTE (insn
) = insn
;
4824 /* Return the head and tail pointers of BB. */
4826 HAIFA_INLINE
static void
4827 get_block_head_tail (bb
, headp
, tailp
)
4837 b
= BB_TO_BLOCK (bb
);
4839 /* HEAD and TAIL delimit the basic block being scheduled. */
4840 head
= BLOCK_HEAD (b
);
4841 tail
= BLOCK_END (b
);
4843 /* Don't include any notes or labels at the beginning of the
4844 basic block, or notes at the ends of basic blocks. */
4845 while (head
!= tail
)
4847 if (GET_CODE (head
) == NOTE
)
4848 head
= NEXT_INSN (head
);
4849 else if (GET_CODE (tail
) == NOTE
)
4850 tail
= PREV_INSN (tail
);
4851 else if (GET_CODE (head
) == CODE_LABEL
)
4852 head
= NEXT_INSN (head
);
4861 /* Delete line notes from bb. Save them so they can be later restored
4862 (in restore_line_notes ()). */
4873 get_block_head_tail (bb
, &head
, &tail
);
4876 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4879 next_tail
= NEXT_INSN (tail
);
4880 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4884 /* Farm out notes, and maybe save them in NOTE_LIST.
4885 This is needed to keep the debugger from
4886 getting completely deranged. */
4887 if (GET_CODE (insn
) == NOTE
)
4890 insn
= unlink_line_notes (insn
, next_tail
);
4896 if (insn
== next_tail
)
4902 /* Save line number notes for each insn in bb. */
4905 save_line_notes (bb
)
4911 /* We must use the true line number for the first insn in the block
4912 that was computed and saved at the start of this pass. We can't
4913 use the current line number, because scheduling of the previous
4914 block may have changed the current line number. */
4916 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4919 get_block_head_tail (bb
, &head
, &tail
);
4920 next_tail
= NEXT_INSN (tail
);
4922 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4924 insn
= NEXT_INSN (insn
))
4925 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4928 LINE_NOTE (insn
) = line
;
4932 /* After bb was scheduled, insert line notes into the insns list. */
4935 restore_line_notes (bb
)
4938 rtx line
, note
, prev
, new;
4939 int added_notes
= 0;
4941 rtx head
, next_tail
, insn
;
4943 b
= BB_TO_BLOCK (bb
);
4945 head
= BLOCK_HEAD (b
);
4946 next_tail
= NEXT_INSN (BLOCK_END (b
));
4948 /* Determine the current line-number. We want to know the current
4949 line number of the first insn of the block here, in case it is
4950 different from the true line number that was saved earlier. If
4951 different, then we need a line number note before the first insn
4952 of this block. If it happens to be the same, then we don't want to
4953 emit another line number note here. */
4954 for (line
= head
; line
; line
= PREV_INSN (line
))
4955 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4958 /* Walk the insns keeping track of the current line-number and inserting
4959 the line-number notes as needed. */
4960 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4961 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4963 /* This used to emit line number notes before every non-deleted note.
4964 However, this confuses a debugger, because line notes not separated
4965 by real instructions all end up at the same address. I can find no
4966 use for line number notes before other notes, so none are emitted. */
4967 else if (GET_CODE (insn
) != NOTE
4968 && (note
= LINE_NOTE (insn
)) != 0
4971 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4972 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4975 prev
= PREV_INSN (insn
);
4976 if (LINE_NOTE (note
))
4978 /* Re-use the original line-number note. */
4979 LINE_NOTE (note
) = 0;
4980 PREV_INSN (note
) = prev
;
4981 NEXT_INSN (prev
) = note
;
4982 PREV_INSN (insn
) = note
;
4983 NEXT_INSN (note
) = insn
;
4988 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4989 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4990 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4993 if (sched_verbose
&& added_notes
)
4994 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4997 /* After scheduling the function, delete redundant line notes from the
5001 rm_redundant_line_notes ()
5004 rtx insn
= get_insns ();
5005 int active_insn
= 0;
5008 /* Walk the insns deleting redundant line-number notes. Many of these
5009 are already present. The remainder tend to occur at basic
5010 block boundaries. */
5011 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5012 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5014 /* If there are no active insns following, INSN is redundant. */
5015 if (active_insn
== 0)
5018 NOTE_SOURCE_FILE (insn
) = 0;
5019 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
5021 /* If the line number is unchanged, LINE is redundant. */
5023 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
5024 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
5027 NOTE_SOURCE_FILE (line
) = 0;
5028 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
5035 else if (!((GET_CODE (insn
) == NOTE
5036 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
5037 || (GET_CODE (insn
) == INSN
5038 && (GET_CODE (PATTERN (insn
)) == USE
5039 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
5042 if (sched_verbose
&& notes
)
5043 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
5046 /* Delete notes between head and tail and put them in the chain
5047 of notes ended by NOTE_LIST. */
5050 rm_other_notes (head
, tail
)
5058 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5061 next_tail
= NEXT_INSN (tail
);
5062 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5066 /* Farm out notes, and maybe save them in NOTE_LIST.
5067 This is needed to keep the debugger from
5068 getting completely deranged. */
5069 if (GET_CODE (insn
) == NOTE
)
5073 insn
= unlink_other_notes (insn
, next_tail
);
5079 if (insn
== next_tail
)
5085 /* Constructor for `sometimes' data structure. */
5088 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
5089 struct sometimes
*regs_sometimes_live
;
5093 register struct sometimes
*p
;
5095 /* There should never be a register greater than max_regno here. If there
5096 is, it means that a define_split has created a new pseudo reg. This
5097 is not allowed, since there will not be flow info available for any
5098 new register, so catch the error here. */
5099 if (regno
>= max_regno
)
5102 p
= ®s_sometimes_live
[sometimes_max
];
5105 p
->calls_crossed
= 0;
5107 return sometimes_max
;
5110 /* Count lengths of all regs we are currently tracking,
5111 and find new registers no longer live. */
5114 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
5115 struct sometimes
*regs_sometimes_live
;
5120 for (i
= 0; i
< sometimes_max
; i
++)
5122 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5123 int regno
= p
->regno
;
5125 sched_reg_live_length
[regno
] += p
->live_length
;
5126 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5130 /* functions for computation of registers live/usage info */
5132 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5133 contains the registers that are alive at the entry to b.
5135 Two passes follow: The first pass is performed before the scheduling
5136 of a region. It scans each block of the region forward, computing
5137 the set of registers alive at the end of the basic block and
5138 discard REG_DEAD notes (done by find_pre_sched_live ()).
5140 The second path is invoked after scheduling all region blocks.
5141 It scans each block of the region backward, a block being traversed
5142 only after its succesors in the region. When the set of registers
5143 live at the end of a basic block may be changed by the scheduling
5144 (this may happen for multiple blocks region), it is computed as
5145 the union of the registers live at the start of its succesors.
5146 The last-use information is updated by inserting REG_DEAD notes.
5147 (done by find_post_sched_live ()) */
5149 /* Scan all the insns to be scheduled, removing register death notes.
5150 Register death notes end up in DEAD_NOTES.
5151 Recreate the register life information for the end of this basic
5155 find_pre_sched_live (bb
)
5158 rtx insn
, next_tail
, head
, tail
;
5159 int b
= BB_TO_BLOCK (bb
);
5161 get_block_head_tail (bb
, &head
, &tail
);
5162 COPY_REG_SET (bb_live_regs
, basic_block_live_at_start
[b
]);
5163 next_tail
= NEXT_INSN (tail
);
5165 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5167 rtx prev
, next
, link
;
5170 /* Handle register life information. */
5171 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5173 /* See if the register gets born here. */
5174 /* We must check for registers being born before we check for
5175 registers dying. It is possible for a register to be born and
5176 die in the same insn, e.g. reading from a volatile memory
5177 location into an otherwise unused register. Such a register
5178 must be marked as dead after this insn. */
5179 if (GET_CODE (PATTERN (insn
)) == SET
5180 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5182 sched_note_set (PATTERN (insn
), 0);
5186 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5189 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5190 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5191 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5193 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5197 /* ??? This code is obsolete and should be deleted. It
5198 is harmless though, so we will leave it in for now. */
5199 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5200 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5201 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5204 /* Each call cobbers (makes live) all call-clobbered regs
5205 that are not global or fixed. Note that the function-value
5206 reg is a call_clobbered reg. */
5207 if (GET_CODE (insn
) == CALL_INSN
)
5210 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5211 if (call_used_regs
[j
] && !global_regs
[j
]
5214 SET_REGNO_REG_SET (bb_live_regs
, j
);
5218 /* Need to know what registers this insn kills. */
5219 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5221 next
= XEXP (link
, 1);
5222 if ((REG_NOTE_KIND (link
) == REG_DEAD
5223 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5224 /* Verify that the REG_NOTE has a valid value. */
5225 && GET_CODE (XEXP (link
, 0)) == REG
)
5227 register int regno
= REGNO (XEXP (link
, 0));
5231 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5233 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5236 XEXP (prev
, 1) = next
;
5238 REG_NOTES (insn
) = next
;
5239 XEXP (link
, 1) = dead_notes
;
5245 if (regno
< FIRST_PSEUDO_REGISTER
)
5247 int j
= HARD_REGNO_NREGS (regno
,
5248 GET_MODE (XEXP (link
, 0)));
5251 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5256 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5264 INSN_REG_WEIGHT (insn
) = reg_weight
;
5268 /* Update register life and usage information for block bb
5269 after scheduling. Put register dead notes back in the code. */
5272 find_post_sched_live (bb
)
5279 rtx head
, tail
, prev_head
, next_tail
;
5281 register struct sometimes
*regs_sometimes_live
;
5283 b
= BB_TO_BLOCK (bb
);
5285 /* compute live regs at the end of bb as a function of its successors. */
5286 if (current_nr_blocks
> 1)
5291 first_edge
= e
= OUT_EDGES (b
);
5292 CLEAR_REG_SET (bb_live_regs
);
5299 b_succ
= TO_BLOCK (e
);
5300 IOR_REG_SET (bb_live_regs
, basic_block_live_at_start
[b_succ
]);
5303 while (e
!= first_edge
);
5306 get_block_head_tail (bb
, &head
, &tail
);
5307 next_tail
= NEXT_INSN (tail
);
5308 prev_head
= PREV_INSN (head
);
5310 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, i
,
5312 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5315 /* if the block is empty, same regs are alive at its end and its start.
5316 since this is not guaranteed after interblock scheduling, make sure they
5317 are truly identical. */
5318 if (NEXT_INSN (prev_head
) == tail
5319 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5321 if (current_nr_blocks
> 1)
5322 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5327 b
= BB_TO_BLOCK (bb
);
5328 current_block_num
= b
;
5330 /* Keep track of register lives. */
5331 old_live_regs
= ALLOCA_REG_SET ();
5333 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5336 /* initiate "sometimes" data, starting with registers live at end */
5338 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5339 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5342 = new_sometimes_live (regs_sometimes_live
,
5346 /* scan insns back, computing regs live info */
5347 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5349 /* First we kill registers set by this insn, and then we
5350 make registers used by this insn live. This is the opposite
5351 order used above because we are traversing the instructions
5354 /* Strictly speaking, we should scan REG_UNUSED notes and make
5355 every register mentioned there live, however, we will just
5356 kill them again immediately below, so there doesn't seem to
5357 be any reason why we bother to do this. */
5359 /* See if this is the last notice we must take of a register. */
5360 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5363 if (GET_CODE (PATTERN (insn
)) == SET
5364 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5365 sched_note_set (PATTERN (insn
), 1);
5366 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5368 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5369 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5370 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5371 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5374 /* This code keeps life analysis information up to date. */
5375 if (GET_CODE (insn
) == CALL_INSN
)
5377 register struct sometimes
*p
;
5379 /* A call kills all call used registers that are not
5380 global or fixed, except for those mentioned in the call
5381 pattern which will be made live again later. */
5382 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5383 if (call_used_regs
[i
] && ! global_regs
[i
]
5386 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5389 /* Regs live at the time of a call instruction must not
5390 go in a register clobbered by calls. Record this for
5391 all regs now live. Note that insns which are born or
5392 die in a call do not cross a call, so this must be done
5393 after the killings (above) and before the births
5395 p
= regs_sometimes_live
;
5396 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5397 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5398 p
->calls_crossed
+= 1;
5401 /* Make every register used live, and add REG_DEAD notes for
5402 registers which were not live before we started. */
5403 attach_deaths_insn (insn
);
5405 /* Find registers now made live by that instruction. */
5406 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5409 = new_sometimes_live (regs_sometimes_live
,
5412 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5414 /* Count lengths of all regs we are worrying about now,
5415 and handle registers no longer live. */
5417 for (i
= 0; i
< sometimes_max
; i
++)
5419 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5420 int regno
= p
->regno
;
5422 p
->live_length
+= 1;
5424 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5426 /* This is the end of one of this register's lifetime
5427 segments. Save the lifetime info collected so far,
5428 and clear its bit in the old_live_regs entry. */
5429 sched_reg_live_length
[regno
] += p
->live_length
;
5430 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5431 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5433 /* Delete the reg_sometimes_live entry for this reg by
5434 copying the last entry over top of it. */
5435 *p
= regs_sometimes_live
[--sometimes_max
];
5436 /* ...and decrement i so that this newly copied entry
5437 will be processed. */
5443 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5445 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5446 if (current_nr_blocks
> 1)
5447 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5450 FREE_REG_SET (old_live_regs
);
5451 } /* find_post_sched_live */
5453 /* After scheduling the subroutine, restore information about uses of
5461 if (n_basic_blocks
> 0)
5462 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, regno
,
5464 sched_reg_basic_block
[regno
]
5468 for (regno
= 0; regno
< max_regno
; regno
++)
5469 if (sched_reg_live_length
[regno
])
5473 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5475 ";; register %d life shortened from %d to %d\n",
5476 regno
, REG_LIVE_LENGTH (regno
),
5477 sched_reg_live_length
[regno
]);
5478 /* Negative values are special; don't overwrite the current
5479 reg_live_length value if it is negative. */
5480 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5481 && REG_LIVE_LENGTH (regno
) >= 0)
5483 ";; register %d life extended from %d to %d\n",
5484 regno
, REG_LIVE_LENGTH (regno
),
5485 sched_reg_live_length
[regno
]);
5487 if (!REG_N_CALLS_CROSSED (regno
)
5488 && sched_reg_n_calls_crossed
[regno
])
5490 ";; register %d now crosses calls\n", regno
);
5491 else if (REG_N_CALLS_CROSSED (regno
)
5492 && !sched_reg_n_calls_crossed
[regno
]
5493 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5495 ";; register %d no longer crosses calls\n", regno
);
5497 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5498 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5499 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5501 ";; register %d changed basic block from %d to %d\n",
5502 regno
, REG_BASIC_BLOCK(regno
),
5503 sched_reg_basic_block
[regno
]);
5506 /* Negative values are special; don't overwrite the current
5507 reg_live_length value if it is negative. */
5508 if (REG_LIVE_LENGTH (regno
) >= 0)
5509 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5511 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5512 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5513 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5515 /* We can't change the value of reg_n_calls_crossed to zero for
5516 pseudos which are live in more than one block.
5518 This is because combine might have made an optimization which
5519 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5520 but it does not update them. If we update reg_n_calls_crossed
5521 here, the two variables are now inconsistent, and this might
5522 confuse the caller-save code into saving a register that doesn't
5523 need to be saved. This is only a problem when we zero calls
5524 crossed for a pseudo live in multiple basic blocks.
5526 Alternatively, we could try to correctly update basic block live
5527 at start here in sched, but that seems complicated.
5529 Note: it is possible that a global register became local, as result
5530 of interblock motion, but will remain marked as a global register. */
5531 if (sched_reg_n_calls_crossed
[regno
]
5532 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5533 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5538 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5539 static int clock_var
;
5541 /* Move insns that became ready to fire from queue to ready list. */
5544 queue_to_ready (ready
, n_ready
)
5551 q_ptr
= NEXT_Q (q_ptr
);
5553 /* Add all pending insns that can be scheduled without stalls to the
5555 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5558 insn
= XEXP (link
, 0);
5561 if (sched_verbose
>= 2)
5562 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5564 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5565 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5567 ready
[n_ready
++] = insn
;
5568 if (sched_verbose
>= 2)
5569 fprintf (dump
, "moving to ready without stalls\n");
5571 insn_queue
[q_ptr
] = 0;
5573 /* If there are no ready insns, stall until one is ready and add all
5574 of the pending insns at that point to the ready list. */
5577 register int stalls
;
5579 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5581 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5583 for (; link
; link
= XEXP (link
, 1))
5585 insn
= XEXP (link
, 0);
5588 if (sched_verbose
>= 2)
5589 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5591 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5592 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5594 ready
[n_ready
++] = insn
;
5595 if (sched_verbose
>= 2)
5596 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5598 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5605 if (sched_verbose
&& stalls
)
5606 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5607 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5608 clock_var
+= stalls
;
5613 /* Print the ready list for debugging purposes. Callable from debugger. */
5616 debug_ready_list (ready
, n_ready
)
5622 for (i
= 0; i
< n_ready
; i
++)
5624 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5625 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5626 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5628 fprintf (dump
, "\n");
5631 /* Print names of units on which insn can/should execute, for debugging. */
5634 insn_print_units (insn
)
5638 int unit
= insn_unit (insn
);
5641 fprintf (dump
, "none");
5643 fprintf (dump
, "%s", function_units
[unit
].name
);
5646 fprintf (dump
, "[");
5647 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5650 fprintf (dump
, "%s", function_units
[i
].name
);
5652 fprintf (dump
, " ");
5654 fprintf (dump
, "]");
5658 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5659 of a basic block. If more lines are needed, table is splitted to two.
5660 n_visual_lines is the number of lines printed so far for a block.
5661 visual_tbl contains the block visualization info.
5662 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5663 #define MAX_VISUAL_LINES 100
5668 rtx vis_no_unit
[10];
5670 /* Finds units that are in use in this fuction. Required only
5671 for visualization. */
5674 init_target_units ()
5679 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5681 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5684 unit
= insn_unit (insn
);
5687 target_units
|= ~unit
;
5689 target_units
|= (1 << unit
);
5693 /* Return the length of the visualization table */
5696 get_visual_tbl_length ()
5702 /* compute length of one field in line */
5703 s
= (char *) alloca (INSN_LEN
+ 5);
5704 sprintf (s
, " %33s", "uname");
5707 /* compute length of one line */
5710 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5711 if (function_units
[unit
].bitmask
& target_units
)
5712 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5715 n
+= strlen ("\n") + 2;
5717 /* compute length of visualization string */
5718 return (MAX_VISUAL_LINES
* n
);
5721 /* Init block visualization debugging info */
5724 init_block_visualization ()
5726 strcpy (visual_tbl
, "");
5734 safe_concat (buf
, cur
, str
)
5739 char *end
= buf
+ BUF_LEN
- 2; /* leave room for null */
5748 while (cur
< end
&& (c
= *str
++) != '\0')
5755 /* This recognizes rtx, I classified as expressions. These are always */
5756 /* represent some action on values or results of other expression, */
5757 /* that may be stored in objects representing values. */
5760 print_exp (buf
, x
, verbose
)
5768 char *fun
= (char *)0;
5773 for (i
= 0; i
< 4; i
++)
5779 switch (GET_CODE (x
))
5782 op
[0] = XEXP (x
, 0);
5784 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
, "0x%lx", (long)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 */
6294 /* too. (probably the last "option" should be extended somehow, since */
6295 /* it 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 (INTVAL (XEXP (note
, 0)), 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. */
6619 /* flow block of this bb */
6620 int b
= BB_TO_BLOCK (bb
);
6622 /* target_n_insns == number of insns in b before scheduling starts.
6623 sched_target_n_insns == how many of b's insns were scheduled.
6624 sched_n_insns == how many insns were scheduled in b */
6625 int target_n_insns
= 0;
6626 int sched_target_n_insns
= 0;
6627 int sched_n_insns
= 0;
6629 #define NEED_NOTHING 0
6634 /* head/tail info for this block */
6641 /* We used to have code to avoid getting parameters moved from hard
6642 argument registers into pseudos.
6644 However, it was removed when it proved to be of marginal benefit
6645 and caused problems because schedule_block and compute_forward_dependences
6646 had different notions of what the "head" insn was. */
6647 get_block_head_tail (bb
, &head
, &tail
);
6649 /* Interblock scheduling could have moved the original head insn from this
6650 block into a proceeding block. This may also cause schedule_block and
6651 compute_forward_dependences to have different notions of what the
6654 If the interblock movement happened to make this block start with
6655 some notes (LOOP, EH or SETJMP) before the first real insn, then
6656 HEAD will have various special notes attached to it which must be
6657 removed so that we don't end up with extra copies of the notes. */
6658 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6662 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6663 if (REG_NOTE_KIND (note
) == REG_DEAD
6664 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6665 remove_note (head
, note
);
6668 next_tail
= NEXT_INSN (tail
);
6669 prev_head
= PREV_INSN (head
);
6671 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6672 to schedule this block. */
6674 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6675 return (sched_n_insns
);
6680 fprintf (dump
, ";; ======================================================\n");
6682 ";; -- basic block %d from %d to %d -- %s reload\n",
6683 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
6684 (reload_completed
? "after" : "before"));
6685 fprintf (dump
, ";; ======================================================\n");
6686 fprintf (dump
, "\n");
6688 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6689 init_block_visualization ();
6692 /* remove remaining note insns from the block, save them in
6693 note_list. These notes are restored at the end of
6694 schedule_block (). */
6696 rm_other_notes (head
, tail
);
6700 /* prepare current target block info */
6701 if (current_nr_blocks
> 1)
6703 candidate_table
= (candidate
*) alloca (current_nr_blocks
* 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 next
= NEXT_INSN (insn
);
6782 if (INSN_DEP_COUNT (insn
) == 0
6783 && (SCHED_GROUP_P (next
) == 0
6784 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6785 ready
[n_ready
++] = insn
;
6790 #ifdef MD_SCHED_INIT
6791 MD_SCHED_INIT (dump
, sched_verbose
);
6794 /* no insns scheduled in this block yet */
6795 last_scheduled_insn
= 0;
6797 /* Sort the ready list */
6798 SCHED_SORT (ready
, n_ready
);
6799 #ifdef MD_SCHED_REORDER
6800 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6803 if (sched_verbose
>= 2)
6805 fprintf (dump
, ";;\t\tReady list initially: ");
6806 debug_ready_list (ready
, n_ready
);
6809 /* Q_SIZE is the total number of insns in the queue. */
6814 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6816 /* We start inserting insns after PREV_HEAD. */
6819 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6820 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
6821 ? NEED_HEAD
: NEED_NOTHING
);
6822 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
6823 new_needs
|= NEED_TAIL
;
6825 /* loop until all the insns in BB are scheduled. */
6826 while (sched_target_n_insns
< target_n_insns
)
6832 /* Add to the ready list all pending insns that can be issued now.
6833 If there are no ready insns, increment clock until one
6834 is ready and add all pending insns at that point to the ready
6836 n_ready
= queue_to_ready (ready
, n_ready
);
6841 if (sched_verbose
>= 2)
6843 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6844 debug_ready_list (ready
, n_ready
);
6847 /* Sort the ready list. */
6848 SCHED_SORT (ready
, n_ready
);
6849 #ifdef MD_SCHED_REORDER
6850 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6855 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
6856 debug_ready_list (ready
, n_ready
);
6859 /* Issue insns from ready list.
6860 It is important to count down from n_ready, because n_ready may change
6861 as insns are issued. */
6862 can_issue_more
= issue_rate
;
6863 for (i
= n_ready
- 1; i
>= 0 && can_issue_more
; i
--)
6865 rtx insn
= ready
[i
];
6866 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6870 queue_insn (insn
, cost
);
6871 ready
[i
] = ready
[--n_ready
]; /* remove insn from ready list */
6875 /* an interblock motion? */
6876 if (INSN_BB (insn
) != target_bb
)
6880 if (IS_SPECULATIVE_INSN (insn
))
6883 if (!check_live (insn
, INSN_BB (insn
)))
6885 /* speculative motion, live check failed, remove
6886 insn from ready list */
6887 ready
[i
] = ready
[--n_ready
];
6890 update_live (insn
, INSN_BB (insn
));
6892 /* for speculative load, mark insns fed by it. */
6893 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6894 set_spec_fed (insn
);
6901 while (SCHED_GROUP_P (temp
))
6902 temp
= PREV_INSN (temp
);
6904 /* Update source block boundaries. */
6905 b1
= INSN_BLOCK (temp
);
6906 if (temp
== BLOCK_HEAD (b1
)
6907 && insn
== BLOCK_END (b1
))
6909 /* We moved all the insns in the basic block.
6910 Emit a note after the last insn and update the
6911 begin/end boundaries to point to the note. */
6912 emit_note_after (NOTE_INSN_DELETED
, insn
);
6913 BLOCK_END (b1
) = NEXT_INSN (insn
);
6914 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6916 else if (insn
== BLOCK_END (b1
))
6918 /* We took insns from the end of the basic block,
6919 so update the end of block boundary so that it
6920 points to the first insn we did not move. */
6921 BLOCK_END (b1
) = PREV_INSN (temp
);
6923 else if (temp
== BLOCK_HEAD (b1
))
6925 /* We took insns from the start of the basic block,
6926 so update the start of block boundary so that
6927 it points to the first insn we did not move. */
6928 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6933 /* in block motion */
6934 sched_target_n_insns
++;
6937 last_scheduled_insn
= insn
;
6938 last
= move_insn (insn
, last
);
6941 #ifdef MD_SCHED_VARIABLE_ISSUE
6942 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
, can_issue_more
);
6947 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6949 /* remove insn from ready list */
6950 ready
[i
] = ready
[--n_ready
];
6952 /* close this block after scheduling its jump */
6953 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6961 visualize_scheduled_insns (b
, clock_var
);
6968 fprintf (dump
, ";;\tReady list (final): ");
6969 debug_ready_list (ready
, n_ready
);
6970 print_block_visualization (b
, "");
6973 /* Sanity check -- queue must be empty now. Meaningless if region has
6975 if (current_nr_blocks
> 1)
6976 if (!flag_schedule_interblock
&& q_size
!= 0)
6979 /* update head/tail boundaries. */
6980 head
= NEXT_INSN (prev_head
);
6983 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6984 previously found among the insns. Insert them at the beginning
6988 rtx note_head
= note_list
;
6990 while (PREV_INSN (note_head
))
6992 note_head
= PREV_INSN (note_head
);
6995 PREV_INSN (note_head
) = PREV_INSN (head
);
6996 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6997 PREV_INSN (head
) = note_list
;
6998 NEXT_INSN (note_list
) = head
;
7002 /* update target block boundaries. */
7003 if (new_needs
& NEED_HEAD
)
7004 BLOCK_HEAD (b
) = head
;
7006 if (new_needs
& NEED_TAIL
)
7007 BLOCK_END (b
) = tail
;
7012 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
7013 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
7014 fprintf (dump
, ";; new basic block end = %d\n\n",
7015 INSN_UID (BLOCK_END (b
)));
7018 return (sched_n_insns
);
7019 } /* schedule_block () */
7022 /* print the bit-set of registers, S. callable from debugger */
7025 debug_reg_vector (s
)
7030 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
7032 fprintf (dump
, " %d", regno
);
7035 fprintf (dump
, "\n");
7038 /* Use the backward dependences from LOG_LINKS to build
7039 forward dependences in INSN_DEPEND. */
7042 compute_block_forward_dependences (bb
)
7048 enum reg_note dep_type
;
7050 get_block_head_tail (bb
, &head
, &tail
);
7051 next_tail
= NEXT_INSN (tail
);
7052 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7054 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7057 insn
= group_leader (insn
);
7059 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
7061 rtx x
= group_leader (XEXP (link
, 0));
7064 if (x
!= XEXP (link
, 0))
7067 /* Ignore dependences upon deleted insn */
7068 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
7070 if (find_insn_list (insn
, INSN_DEPEND (x
)))
7073 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
7075 dep_type
= REG_NOTE_KIND (link
);
7076 PUT_REG_NOTE_KIND (new_link
, dep_type
);
7078 INSN_DEPEND (x
) = new_link
;
7079 INSN_DEP_COUNT (insn
) += 1;
7084 /* Initialize variables for region data dependence analysis.
7085 n_bbs is the number of region blocks */
7087 __inline
static void
7088 init_rgn_data_dependences (n_bbs
)
7093 /* variables for which one copy exists for each block */
7094 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
7095 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
7096 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
7097 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
7098 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
7099 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
7100 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
7101 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
7103 /* Create an insn here so that we can hang dependencies off of it later. */
7104 for (bb
= 0; bb
< n_bbs
; bb
++)
7106 bb_sched_before_next_call
[bb
] =
7107 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7108 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7109 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
7113 /* Add dependences so that branches are scheduled to run last in their block */
7116 add_branch_dependences (head
, tail
)
7122 /* For all branches, calls, uses, and cc0 setters, force them to remain
7123 in order at the end of the block by adding dependencies and giving
7124 the last a high priority. There may be notes present, and prev_head
7127 Branches must obviously remain at the end. Calls should remain at the
7128 end since moving them results in worse register allocation. Uses remain
7129 at the end to ensure proper register allocation. cc0 setters remaim
7130 at the end because they can't be moved away from their cc0 user. */
7133 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7134 || (GET_CODE (insn
) == INSN
7135 && (GET_CODE (PATTERN (insn
)) == USE
7137 || sets_cc0_p (PATTERN (insn
))
7140 || GET_CODE (insn
) == NOTE
)
7142 if (GET_CODE (insn
) != NOTE
)
7145 && !find_insn_list (insn
, LOG_LINKS (last
)))
7147 add_dependence (last
, insn
, REG_DEP_ANTI
);
7148 INSN_REF_COUNT (insn
)++;
7151 CANT_MOVE (insn
) = 1;
7154 /* Skip over insns that are part of a group.
7155 Make each insn explicitly depend on the previous insn.
7156 This ensures that only the group header will ever enter
7157 the ready queue (and, when scheduled, will automatically
7158 schedule the SCHED_GROUP_P block). */
7159 while (SCHED_GROUP_P (insn
))
7161 rtx temp
= prev_nonnote_insn (insn
);
7162 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7167 /* Don't overrun the bounds of the basic block. */
7171 insn
= PREV_INSN (insn
);
7174 /* make sure these insns are scheduled last in their block */
7177 while (insn
!= head
)
7179 insn
= prev_nonnote_insn (insn
);
7181 if (INSN_REF_COUNT (insn
) != 0)
7184 if (!find_insn_list (last
, LOG_LINKS (insn
)))
7185 add_dependence (last
, insn
, REG_DEP_ANTI
);
7186 INSN_REF_COUNT (insn
) = 1;
7188 /* Skip over insns that are part of a group. */
7189 while (SCHED_GROUP_P (insn
))
7190 insn
= prev_nonnote_insn (insn
);
7194 /* Compute bacward dependences inside BB. In a multiple blocks region:
7195 (1) a bb is analyzed after its predecessors, and (2) the lists in
7196 effect at the end of bb (after analyzing for bb) are inherited by
7199 Specifically for reg-reg data dependences, the block insns are
7200 scanned by sched_analyze () top-to-bottom. Two lists are
7201 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7202 and reg_last_uses[] for register USEs.
7204 When analysis is completed for bb, we update for its successors:
7205 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7206 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7208 The mechanism for computing mem-mem data dependence is very
7209 similar, and the result is interblock dependences in the region. */
7212 compute_block_backward_dependences (bb
)
7218 int max_reg
= max_reg_num ();
7220 b
= BB_TO_BLOCK (bb
);
7222 if (current_nr_blocks
== 1)
7224 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7225 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7227 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7228 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7230 pending_read_insns
= 0;
7231 pending_read_mems
= 0;
7232 pending_write_insns
= 0;
7233 pending_write_mems
= 0;
7234 pending_lists_length
= 0;
7235 last_function_call
= 0;
7236 last_pending_memory_flush
= 0;
7237 sched_before_next_call
7238 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7239 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7240 LOG_LINKS (sched_before_next_call
) = 0;
7244 reg_last_uses
= bb_reg_last_uses
[bb
];
7245 reg_last_sets
= bb_reg_last_sets
[bb
];
7247 pending_read_insns
= bb_pending_read_insns
[bb
];
7248 pending_read_mems
= bb_pending_read_mems
[bb
];
7249 pending_write_insns
= bb_pending_write_insns
[bb
];
7250 pending_write_mems
= bb_pending_write_mems
[bb
];
7251 pending_lists_length
= bb_pending_lists_length
[bb
];
7252 last_function_call
= bb_last_function_call
[bb
];
7253 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7255 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7258 /* do the analysis for this block */
7259 get_block_head_tail (bb
, &head
, &tail
);
7260 sched_analyze (head
, tail
);
7261 add_branch_dependences (head
, tail
);
7263 if (current_nr_blocks
> 1)
7266 int b_succ
, bb_succ
;
7268 rtx link_insn
, link_mem
;
7271 /* these lists should point to the right place, for correct freeing later. */
7272 bb_pending_read_insns
[bb
] = pending_read_insns
;
7273 bb_pending_read_mems
[bb
] = pending_read_mems
;
7274 bb_pending_write_insns
[bb
] = pending_write_insns
;
7275 bb_pending_write_mems
[bb
] = pending_write_mems
;
7277 /* bb's structures are inherited by it's successors */
7278 first_edge
= e
= OUT_EDGES (b
);
7282 b_succ
= TO_BLOCK (e
);
7283 bb_succ
= BLOCK_TO_BB (b_succ
);
7285 /* only bbs "below" bb, in the same region, are interesting */
7286 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7293 for (reg
= 0; reg
< max_reg
; reg
++)
7296 /* reg-last-uses lists are inherited by bb_succ */
7297 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7299 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_uses
[bb_succ
])[reg
]))
7302 (bb_reg_last_uses
[bb_succ
])[reg
]
7303 = alloc_INSN_LIST (XEXP (u
, 0),
7304 (bb_reg_last_uses
[bb_succ
])[reg
]);
7307 /* reg-last-defs lists are inherited by bb_succ */
7308 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7310 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_sets
[bb_succ
])[reg
]))
7313 (bb_reg_last_sets
[bb_succ
])[reg
]
7314 = alloc_INSN_LIST (XEXP (u
, 0),
7315 (bb_reg_last_sets
[bb_succ
])[reg
]);
7319 /* mem read/write lists are inherited by bb_succ */
7320 link_insn
= pending_read_insns
;
7321 link_mem
= pending_read_mems
;
7324 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7325 bb_pending_read_insns
[bb_succ
],
7326 bb_pending_read_mems
[bb_succ
])))
7327 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7328 &bb_pending_read_mems
[bb_succ
],
7329 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7330 link_insn
= XEXP (link_insn
, 1);
7331 link_mem
= XEXP (link_mem
, 1);
7334 link_insn
= pending_write_insns
;
7335 link_mem
= pending_write_mems
;
7338 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7339 bb_pending_write_insns
[bb_succ
],
7340 bb_pending_write_mems
[bb_succ
])))
7341 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7342 &bb_pending_write_mems
[bb_succ
],
7343 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7345 link_insn
= XEXP (link_insn
, 1);
7346 link_mem
= XEXP (link_mem
, 1);
7349 /* last_function_call is inherited by bb_succ */
7350 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7352 if (find_insn_list (XEXP (u
, 0), bb_last_function_call
[bb_succ
]))
7355 bb_last_function_call
[bb_succ
]
7356 = alloc_INSN_LIST (XEXP (u
, 0),
7357 bb_last_function_call
[bb_succ
]);
7360 /* last_pending_memory_flush is inherited by bb_succ */
7361 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7363 if (find_insn_list (XEXP (u
, 0), bb_last_pending_memory_flush
[bb_succ
]))
7366 bb_last_pending_memory_flush
[bb_succ
]
7367 = alloc_INSN_LIST (XEXP (u
, 0),
7368 bb_last_pending_memory_flush
[bb_succ
]);
7371 /* sched_before_next_call is inherited by bb_succ */
7372 x
= LOG_LINKS (sched_before_next_call
);
7373 for (; x
; x
= XEXP (x
, 1))
7374 add_dependence (bb_sched_before_next_call
[bb_succ
],
7375 XEXP (x
, 0), REG_DEP_ANTI
);
7379 while (e
!= first_edge
);
7382 /* Free up the INSN_LISTs
7384 Note this loop is executed max_reg * nr_regions times. It's first
7385 implementation accounted for over 90% of the calls to free_list.
7386 The list was empty for the vast majority of those calls. On the PA,
7387 not calling free_list in those cases improves -O2 compile times by
7389 for (b
= 0; b
< max_reg
; ++b
)
7391 if (reg_last_sets
[b
])
7392 free_list (®_last_sets
[b
], &unused_insn_list
);
7393 if (reg_last_uses
[b
])
7394 free_list (®_last_uses
[b
], &unused_insn_list
);
7397 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7398 if (current_nr_blocks
> 1)
7400 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
7401 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
7405 /* Print dependences for debugging, callable from debugger */
7408 debug_dependencies ()
7412 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7413 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7421 get_block_head_tail (bb
, &head
, &tail
);
7422 next_tail
= NEXT_INSN (tail
);
7423 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7424 BB_TO_BLOCK (bb
), bb
);
7426 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7427 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7428 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7429 "----", "----", "--", "---", "----", "----", "--------", "-----");
7430 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7435 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7438 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7439 if (GET_CODE (insn
) == NOTE
)
7441 n
= NOTE_LINE_NUMBER (insn
);
7443 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7445 fprintf (dump
, "line %d, file %s\n", n
,
7446 NOTE_SOURCE_FILE (insn
));
7449 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7453 unit
= insn_unit (insn
);
7455 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7456 function_units
[unit
].blockage_range_function (insn
);
7458 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7459 (SCHED_GROUP_P (insn
) ? "+" : " "),
7463 INSN_DEP_COUNT (insn
),
7464 INSN_PRIORITY (insn
),
7465 insn_cost (insn
, 0, 0),
7466 (int) MIN_BLOCKAGE_COST (range
),
7467 (int) MAX_BLOCKAGE_COST (range
));
7468 insn_print_units (insn
);
7469 fprintf (dump
, "\t: ");
7470 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7471 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7472 fprintf (dump
, "\n");
7476 fprintf (dump
, "\n");
7479 /* Set_priorities: compute priority of each insn in the block */
7492 get_block_head_tail (bb
, &head
, &tail
);
7493 prev_head
= PREV_INSN (head
);
7496 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7500 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7503 if (GET_CODE (insn
) == NOTE
)
7506 if (!(SCHED_GROUP_P (insn
)))
7508 (void) priority (insn
);
7514 /* Make each element of VECTOR point at an rtx-vector,
7515 taking the space for all those rtx-vectors from SPACE.
7516 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7517 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7518 (this is the same as init_regset_vector () in flow.c) */
7521 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7528 register rtx
*p
= space
;
7530 for (i
= 0; i
< nelts
; i
++)
7533 p
+= bytes_per_elt
/ sizeof (*p
);
7537 /* Schedule a region. A region is either an inner loop, a loop-free
7538 subroutine, or a single basic block. Each bb in the region is
7539 scheduled after its flow predecessors. */
7542 schedule_region (rgn
)
7546 int rgn_n_insns
= 0;
7547 int sched_rgn_n_insns
= 0;
7549 /* set variables for the current region */
7550 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7551 current_blocks
= RGN_BLOCKS (rgn
);
7553 reg_pending_sets
= ALLOCA_REG_SET ();
7554 reg_pending_sets_all
= 0;
7556 /* initializations for region data dependence analyisis */
7557 if (current_nr_blocks
> 1)
7560 int maxreg
= max_reg_num ();
7562 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7563 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7564 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7565 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7567 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7568 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7569 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7570 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7572 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7573 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7574 bb_pending_write_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7575 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7576 bb_pending_lists_length
= (int *) alloca (current_nr_blocks
* sizeof (int));
7577 bb_last_pending_memory_flush
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7578 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7579 bb_sched_before_next_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7581 init_rgn_data_dependences (current_nr_blocks
);
7584 /* compute LOG_LINKS */
7585 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7586 compute_block_backward_dependences (bb
);
7588 /* compute INSN_DEPEND */
7589 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7590 compute_block_forward_dependences (bb
);
7592 /* Delete line notes, compute live-regs at block end, and set priorities. */
7594 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7596 if (reload_completed
== 0)
7597 find_pre_sched_live (bb
);
7599 if (write_symbols
!= NO_DEBUG
)
7601 save_line_notes (bb
);
7605 rgn_n_insns
+= set_priorities (bb
);
7608 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7609 if (current_nr_blocks
> 1)
7613 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7615 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7616 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7617 for (i
= 0; i
< current_nr_blocks
; i
++)
7619 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7620 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7625 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7626 for (i
= 1; i
< nr_edges
; i
++)
7627 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7628 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7629 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7632 for (i
= 1; i
< nr_edges
; i
++)
7633 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7634 rgn_edges
[rgn_nr_edges
++] = i
;
7637 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7638 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7639 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7640 for (i
= 0; i
< current_nr_blocks
; i
++)
7643 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7644 bzero ((char *) pot_split
[i
],
7645 edgeset_size
* sizeof (HOST_WIDE_INT
));
7647 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7648 bzero ((char *) ancestor_edges
[i
],
7649 edgeset_size
* sizeof (HOST_WIDE_INT
));
7652 /* compute probabilities, dominators, split_edges */
7653 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7654 compute_dom_prob_ps (bb
);
7657 /* now we can schedule all blocks */
7658 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7660 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7667 /* sanity check: verify that all region insns were scheduled */
7668 if (sched_rgn_n_insns
!= rgn_n_insns
)
7671 /* update register life and usage information */
7672 if (reload_completed
== 0)
7674 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7675 find_post_sched_live (bb
);
7677 if (current_nr_blocks
<= 1)
7678 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7679 In practice, this can occur as the result of bugs in flow, combine.c,
7680 and/or sched.c. The values of the REG_DEAD notes remaining are
7681 meaningless, because dead_notes is just used as a free list. */
7682 if (dead_notes
!= 0)
7686 /* restore line notes. */
7687 if (write_symbols
!= NO_DEBUG
)
7689 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7690 restore_line_notes (bb
);
7693 /* Done with this region */
7694 free_pending_lists ();
7696 FREE_REG_SET (reg_pending_sets
);
7699 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7700 needed for the hard register mentioned in the note. This can happen
7701 if the reference to the hard register in the original insn was split into
7702 several smaller hard register references in the split insns. */
7705 split_hard_reg_notes (note
, first
, last
)
7706 rtx note
, first
, last
;
7708 rtx reg
, temp
, link
;
7709 int n_regs
, i
, new_reg
;
7712 /* Assume that this is a REG_DEAD note. */
7713 if (REG_NOTE_KIND (note
) != REG_DEAD
)
7716 reg
= XEXP (note
, 0);
7718 n_regs
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
7720 for (i
= 0; i
< n_regs
; i
++)
7722 new_reg
= REGNO (reg
) + i
;
7724 /* Check for references to new_reg in the split insns. */
7725 for (insn
= last
;; insn
= PREV_INSN (insn
))
7727 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7728 && (temp
= regno_use_in (new_reg
, PATTERN (insn
))))
7730 /* Create a new reg dead note ere. */
7731 link
= alloc_EXPR_LIST (REG_DEAD
, temp
, REG_NOTES (insn
));
7732 REG_NOTES (insn
) = link
;
7734 /* If killed multiple registers here, then add in the excess. */
7735 i
+= HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) - 1;
7739 /* It isn't mentioned anywhere, so no new reg note is needed for
7747 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7748 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7751 new_insn_dead_notes (pat
, insn
, last
, orig_insn
)
7752 rtx pat
, insn
, last
, orig_insn
;
7756 /* PAT is either a CLOBBER or a SET here. */
7757 dest
= XEXP (pat
, 0);
7759 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
7760 || GET_CODE (dest
) == STRICT_LOW_PART
7761 || GET_CODE (dest
) == SIGN_EXTRACT
)
7762 dest
= XEXP (dest
, 0);
7764 if (GET_CODE (dest
) == REG
)
7766 /* If the original insn already used this register, we may not add new
7767 notes for it. One example for a split that needs this test is
7768 when a multi-word memory access with register-indirect addressing
7769 is split into multiple memory accesses with auto-increment and
7770 one adjusting add instruction for the address register. */
7771 if (reg_referenced_p (dest
, PATTERN (orig_insn
)))
7773 for (tem
= last
; tem
!= insn
; tem
= PREV_INSN (tem
))
7775 if (GET_RTX_CLASS (GET_CODE (tem
)) == 'i'
7776 && reg_overlap_mentioned_p (dest
, PATTERN (tem
))
7777 && (set
= single_set (tem
)))
7779 rtx tem_dest
= SET_DEST (set
);
7781 while (GET_CODE (tem_dest
) == ZERO_EXTRACT
7782 || GET_CODE (tem_dest
) == SUBREG
7783 || GET_CODE (tem_dest
) == STRICT_LOW_PART
7784 || GET_CODE (tem_dest
) == SIGN_EXTRACT
)
7785 tem_dest
= XEXP (tem_dest
, 0);
7787 if (!rtx_equal_p (tem_dest
, dest
))
7789 /* Use the same scheme as combine.c, don't put both REG_DEAD
7790 and REG_UNUSED notes on the same insn. */
7791 if (!find_regno_note (tem
, REG_UNUSED
, REGNO (dest
))
7792 && !find_regno_note (tem
, REG_DEAD
, REGNO (dest
)))
7794 rtx note
= alloc_EXPR_LIST (REG_DEAD
, dest
,
7796 REG_NOTES (tem
) = note
;
7798 /* The reg only dies in one insn, the last one that uses
7802 else if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
7803 /* We found an instruction that both uses the register,
7804 and sets it, so no new REG_NOTE is needed for this set. */
7808 /* If this is a set, it must die somewhere, unless it is the dest of
7809 the original insn, and hence is live after the original insn. Abort
7810 if it isn't supposed to be live after the original insn.
7812 If this is a clobber, then just add a REG_UNUSED note. */
7815 int live_after_orig_insn
= 0;
7816 rtx pattern
= PATTERN (orig_insn
);
7819 if (GET_CODE (pat
) == CLOBBER
)
7821 rtx note
= alloc_EXPR_LIST (REG_UNUSED
, dest
, REG_NOTES (insn
));
7822 REG_NOTES (insn
) = note
;
7826 /* The original insn could have multiple sets, so search the
7827 insn for all sets. */
7828 if (GET_CODE (pattern
) == SET
)
7830 if (reg_overlap_mentioned_p (dest
, SET_DEST (pattern
)))
7831 live_after_orig_insn
= 1;
7833 else if (GET_CODE (pattern
) == PARALLEL
)
7835 for (i
= 0; i
< XVECLEN (pattern
, 0); i
++)
7836 if (GET_CODE (XVECEXP (pattern
, 0, i
)) == SET
7837 && reg_overlap_mentioned_p (dest
,
7838 SET_DEST (XVECEXP (pattern
,
7840 live_after_orig_insn
= 1;
7843 if (!live_after_orig_insn
)
7849 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7850 registers modified by X. INC is -1 if the containing insn is being deleted,
7851 and is 1 if the containing insn is a newly generated insn. */
7854 update_n_sets (x
, inc
)
7858 rtx dest
= SET_DEST (x
);
7860 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
7861 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
7862 dest
= SUBREG_REG (dest
);
7864 if (GET_CODE (dest
) == REG
)
7866 int regno
= REGNO (dest
);
7868 if (regno
< FIRST_PSEUDO_REGISTER
)
7871 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
7873 for (i
= regno
; i
< endregno
; i
++)
7874 REG_N_SETS (i
) += inc
;
7877 REG_N_SETS (regno
) += inc
;
7881 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7882 the insns from FIRST to LAST inclusive that were created by splitting
7883 ORIG_INSN. NOTES are the original REG_NOTES. */
7886 update_flow_info (notes
, first
, last
, orig_insn
)
7893 rtx orig_dest
, temp
;
7896 /* Get and save the destination set by the original insn. */
7898 orig_dest
= single_set (orig_insn
);
7900 orig_dest
= SET_DEST (orig_dest
);
7902 /* Move REG_NOTES from the original insn to where they now belong. */
7904 for (note
= notes
; note
; note
= next
)
7906 next
= XEXP (note
, 1);
7907 switch (REG_NOTE_KIND (note
))
7911 /* Move these notes from the original insn to the last new insn where
7912 the register is now set. */
7914 for (insn
= last
;; insn
= PREV_INSN (insn
))
7916 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7917 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
7919 /* If this note refers to a multiple word hard register, it
7920 may have been split into several smaller hard register
7921 references, so handle it specially. */
7922 temp
= XEXP (note
, 0);
7923 if (REG_NOTE_KIND (note
) == REG_DEAD
7924 && GET_CODE (temp
) == REG
7925 && REGNO (temp
) < FIRST_PSEUDO_REGISTER
7926 && HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) > 1)
7927 split_hard_reg_notes (note
, first
, last
);
7930 XEXP (note
, 1) = REG_NOTES (insn
);
7931 REG_NOTES (insn
) = note
;
7934 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7936 /* ??? This won't handle multiple word registers correctly,
7937 but should be good enough for now. */
7938 if (REG_NOTE_KIND (note
) == REG_UNUSED
7939 && GET_CODE (XEXP (note
, 0)) != SCRATCH
7940 && !dead_or_set_p (insn
, XEXP (note
, 0)))
7941 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
7943 /* The reg only dies in one insn, the last one that uses
7947 /* It must die somewhere, fail it we couldn't find where it died.
7949 If this is a REG_UNUSED note, then it must be a temporary
7950 register that was not needed by this instantiation of the
7951 pattern, so we can safely ignore it. */
7954 if (REG_NOTE_KIND (note
) != REG_UNUSED
)
7963 /* If the insn that set the register to 0 was deleted, this
7964 note cannot be relied on any longer. The destination might
7965 even have been moved to memory.
7966 This was observed for SH4 with execute/920501-6.c compilation,
7967 -O2 -fomit-frame-pointer -finline-functions . */
7968 if (GET_CODE (XEXP (note
, 0)) == NOTE
7969 || INSN_DELETED_P (XEXP (note
, 0)))
7971 /* This note applies to the dest of the original insn. Find the
7972 first new insn that now has the same dest, and move the note
7978 for (insn
= first
;; insn
= NEXT_INSN (insn
))
7980 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7981 && (temp
= single_set (insn
))
7982 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
7984 XEXP (note
, 1) = REG_NOTES (insn
);
7985 REG_NOTES (insn
) = note
;
7986 /* The reg is only zero before one insn, the first that
7990 /* If this note refers to a multiple word hard
7991 register, it may have been split into several smaller
7992 hard register references. We could split the notes,
7993 but simply dropping them is good enough. */
7994 if (GET_CODE (orig_dest
) == REG
7995 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
7996 && HARD_REGNO_NREGS (REGNO (orig_dest
),
7997 GET_MODE (orig_dest
)) > 1)
7999 /* It must be set somewhere, fail if we couldn't find where it
8008 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8009 set is meaningless. Just drop the note. */
8013 case REG_NO_CONFLICT
:
8014 /* These notes apply to the dest of the original insn. Find the last
8015 new insn that now has the same dest, and move the note there. */
8020 for (insn
= last
;; insn
= PREV_INSN (insn
))
8022 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8023 && (temp
= single_set (insn
))
8024 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8026 XEXP (note
, 1) = REG_NOTES (insn
);
8027 REG_NOTES (insn
) = note
;
8028 /* Only put this note on one of the new insns. */
8032 /* The original dest must still be set someplace. Abort if we
8033 couldn't find it. */
8036 /* However, if this note refers to a multiple word hard
8037 register, it may have been split into several smaller
8038 hard register references. We could split the notes,
8039 but simply dropping them is good enough. */
8040 if (GET_CODE (orig_dest
) == REG
8041 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8042 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8043 GET_MODE (orig_dest
)) > 1)
8045 /* Likewise for multi-word memory references. */
8046 if (GET_CODE (orig_dest
) == MEM
8047 && SIZE_FOR_MODE (orig_dest
) > UNITS_PER_WORD
)
8055 /* Move a REG_LIBCALL note to the first insn created, and update
8056 the corresponding REG_RETVAL note. */
8057 XEXP (note
, 1) = REG_NOTES (first
);
8058 REG_NOTES (first
) = note
;
8060 insn
= XEXP (note
, 0);
8061 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
8063 XEXP (note
, 0) = first
;
8066 case REG_EXEC_COUNT
:
8067 /* Move a REG_EXEC_COUNT note to the first insn created. */
8068 XEXP (note
, 1) = REG_NOTES (first
);
8069 REG_NOTES (first
) = note
;
8073 /* Move a REG_RETVAL note to the last insn created, and update
8074 the corresponding REG_LIBCALL note. */
8075 XEXP (note
, 1) = REG_NOTES (last
);
8076 REG_NOTES (last
) = note
;
8078 insn
= XEXP (note
, 0);
8079 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
8081 XEXP (note
, 0) = last
;
8086 /* This should be moved to whichever instruction is a JUMP_INSN. */
8088 for (insn
= last
;; insn
= PREV_INSN (insn
))
8090 if (GET_CODE (insn
) == JUMP_INSN
)
8092 XEXP (note
, 1) = REG_NOTES (insn
);
8093 REG_NOTES (insn
) = note
;
8094 /* Only put this note on one of the new insns. */
8097 /* Fail if we couldn't find a JUMP_INSN. */
8104 /* reload sometimes leaves obsolete REG_INC notes around. */
8105 if (reload_completed
)
8107 /* This should be moved to whichever instruction now has the
8108 increment operation. */
8112 /* Should be moved to the new insn(s) which use the label. */
8113 for (insn
= first
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
8114 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8115 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8117 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_LABEL
,
8125 /* These two notes will never appear until after reorg, so we don't
8126 have to handle them here. */
8132 /* Each new insn created, except the last, has a new set. If the destination
8133 is a register, then this reg is now live across several insns, whereas
8134 previously the dest reg was born and died within the same insn. To
8135 reflect this, we now need a REG_DEAD note on the insn where this
8138 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8140 for (insn
= first
; insn
!= last
; insn
= NEXT_INSN (insn
))
8145 pat
= PATTERN (insn
);
8146 if (GET_CODE (pat
) == SET
|| GET_CODE (pat
) == CLOBBER
)
8147 new_insn_dead_notes (pat
, insn
, last
, orig_insn
);
8148 else if (GET_CODE (pat
) == PARALLEL
)
8150 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
8151 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
8152 || GET_CODE (XVECEXP (pat
, 0, i
)) == CLOBBER
)
8153 new_insn_dead_notes (XVECEXP (pat
, 0, i
), insn
, last
, orig_insn
);
8157 /* If any insn, except the last, uses the register set by the last insn,
8158 then we need a new REG_DEAD note on that insn. In this case, there
8159 would not have been a REG_DEAD note for this register in the original
8160 insn because it was used and set within one insn. */
8162 set
= single_set (last
);
8165 rtx dest
= SET_DEST (set
);
8167 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
8168 || GET_CODE (dest
) == STRICT_LOW_PART
8169 || GET_CODE (dest
) == SIGN_EXTRACT
)
8170 dest
= XEXP (dest
, 0);
8172 if (GET_CODE (dest
) == REG
8173 /* Global registers are always live, so the code below does not
8175 && (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
8176 || ! global_regs
[REGNO (dest
)]))
8178 rtx stop_insn
= PREV_INSN (first
);
8180 /* If the last insn uses the register that it is setting, then
8181 we don't want to put a REG_DEAD note there. Search backwards
8182 to find the first insn that sets but does not use DEST. */
8185 if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8187 for (insn
= PREV_INSN (insn
); insn
!= first
;
8188 insn
= PREV_INSN (insn
))
8190 if ((set
= single_set (insn
))
8191 && reg_mentioned_p (dest
, SET_DEST (set
))
8192 && ! reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8197 /* Now find the first insn that uses but does not set DEST. */
8199 for (insn
= PREV_INSN (insn
); insn
!= stop_insn
;
8200 insn
= PREV_INSN (insn
))
8202 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8203 && reg_mentioned_p (dest
, PATTERN (insn
))
8204 && (set
= single_set (insn
)))
8206 rtx insn_dest
= SET_DEST (set
);
8208 while (GET_CODE (insn_dest
) == ZERO_EXTRACT
8209 || GET_CODE (insn_dest
) == SUBREG
8210 || GET_CODE (insn_dest
) == STRICT_LOW_PART
8211 || GET_CODE (insn_dest
) == SIGN_EXTRACT
)
8212 insn_dest
= XEXP (insn_dest
, 0);
8214 if (insn_dest
!= dest
)
8216 note
= alloc_EXPR_LIST (REG_DEAD
, dest
, REG_NOTES (insn
));
8217 REG_NOTES (insn
) = note
;
8218 /* The reg only dies in one insn, the last one
8227 /* If the original dest is modifying a multiple register target, and the
8228 original instruction was split such that the original dest is now set
8229 by two or more SUBREG sets, then the split insns no longer kill the
8230 destination of the original insn.
8232 In this case, if there exists an instruction in the same basic block,
8233 before the split insn, which uses the original dest, and this use is
8234 killed by the original insn, then we must remove the REG_DEAD note on
8235 this insn, because it is now superfluous.
8237 This does not apply when a hard register gets split, because the code
8238 knows how to handle overlapping hard registers properly. */
8239 if (orig_dest
&& GET_CODE (orig_dest
) == REG
)
8241 int found_orig_dest
= 0;
8242 int found_split_dest
= 0;
8244 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8249 /* I'm not sure if this can happen, but let's be safe. */
8250 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
8253 pat
= PATTERN (insn
);
8254 i
= GET_CODE (pat
) == PARALLEL
? XVECLEN (pat
, 0) : 0;
8259 if (GET_CODE (set
) == SET
)
8261 if (GET_CODE (SET_DEST (set
)) == REG
8262 && REGNO (SET_DEST (set
)) == REGNO (orig_dest
))
8264 found_orig_dest
= 1;
8267 else if (GET_CODE (SET_DEST (set
)) == SUBREG
8268 && SUBREG_REG (SET_DEST (set
)) == orig_dest
)
8270 found_split_dest
= 1;
8276 set
= XVECEXP (pat
, 0, i
);
8283 if (found_split_dest
)
8285 /* Search backwards from FIRST, looking for the first insn that uses
8286 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8287 If we find an insn, and it has a REG_DEAD note, then delete the
8290 for (insn
= first
; insn
; insn
= PREV_INSN (insn
))
8292 if (GET_CODE (insn
) == CODE_LABEL
8293 || GET_CODE (insn
) == JUMP_INSN
)
8295 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8296 && reg_mentioned_p (orig_dest
, insn
))
8298 note
= find_regno_note (insn
, REG_DEAD
, REGNO (orig_dest
));
8300 remove_note (insn
, note
);
8304 else if (!found_orig_dest
)
8308 /* Should never reach here for a pseudo reg. */
8309 if (REGNO (orig_dest
) >= FIRST_PSEUDO_REGISTER
)
8312 /* This can happen for a hard register, if the splitter
8313 does not bother to emit instructions which would be no-ops.
8314 We try to verify that this is the case by checking to see if
8315 the original instruction uses all of the registers that it
8316 set. This case is OK, because deleting a no-op can not affect
8317 REG_DEAD notes on other insns. If this is not the case, then
8320 regno
= REGNO (orig_dest
);
8321 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (orig_dest
)) - 1;
8323 if (! refers_to_regno_p (regno
+ i
, regno
+ i
+ 1, orig_insn
,
8331 /* Update reg_n_sets. This is necessary to prevent local alloc from
8332 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8333 a reg from set once to set multiple times. */
8336 rtx x
= PATTERN (orig_insn
);
8337 RTX_CODE code
= GET_CODE (x
);
8339 if (code
== SET
|| code
== CLOBBER
)
8340 update_n_sets (x
, -1);
8341 else if (code
== PARALLEL
)
8344 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8346 code
= GET_CODE (XVECEXP (x
, 0, i
));
8347 if (code
== SET
|| code
== CLOBBER
)
8348 update_n_sets (XVECEXP (x
, 0, i
), -1);
8352 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8355 code
= GET_CODE (x
);
8357 if (code
== SET
|| code
== CLOBBER
)
8358 update_n_sets (x
, 1);
8359 else if (code
== PARALLEL
)
8362 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8364 code
= GET_CODE (XVECEXP (x
, 0, i
));
8365 if (code
== SET
|| code
== CLOBBER
)
8366 update_n_sets (XVECEXP (x
, 0, i
), 1);
8376 /* The one entry point in this file. DUMP_FILE is the dump file for
8380 schedule_insns (dump_file
)
8391 /* disable speculative loads in their presence if cc0 defined */
8393 flag_schedule_speculative_load
= 0;
8396 /* Taking care of this degenerate case makes the rest of
8397 this code simpler. */
8398 if (n_basic_blocks
== 0)
8401 /* set dump and sched_verbose for the desired debugging output. If no
8402 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8403 For -fsched-verbose-N, N>=10, print everything to stderr. */
8404 sched_verbose
= sched_verbose_param
;
8405 if (sched_verbose_param
== 0 && dump_file
)
8407 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
8412 /* Initialize the unused_*_lists. We can't use the ones left over from
8413 the previous function, because gcc has freed that memory. We can use
8414 the ones left over from the first sched pass in the second pass however,
8415 so only clear them on the first sched pass. The first pass is before
8416 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8418 if (reload_completed
== 0 || !flag_schedule_insns
)
8420 unused_insn_list
= 0;
8421 unused_expr_list
= 0;
8424 /* initialize issue_rate */
8425 issue_rate
= ISSUE_RATE
;
8427 /* do the splitting first for all blocks */
8428 for (b
= 0; b
< n_basic_blocks
; b
++)
8429 split_block_insns (b
, 1);
8431 max_uid
= (get_max_uid () + 1);
8433 cant_move
= (char *) xmalloc (max_uid
* sizeof (char));
8434 bzero ((char *) cant_move
, max_uid
* sizeof (char));
8436 fed_by_spec_load
= (char *) xmalloc (max_uid
* sizeof (char));
8437 bzero ((char *) fed_by_spec_load
, max_uid
* sizeof (char));
8439 is_load_insn
= (char *) xmalloc (max_uid
* sizeof (char));
8440 bzero ((char *) is_load_insn
, max_uid
* sizeof (char));
8442 insn_orig_block
= (int *) xmalloc (max_uid
* sizeof (int));
8443 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
8446 for (b
= 0; b
< n_basic_blocks
; b
++)
8447 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8449 INSN_BLOCK (insn
) = b
;
8450 INSN_LUID (insn
) = luid
++;
8452 if (insn
== BLOCK_END (b
))
8456 /* after reload, remove inter-blocks dependences computed before reload. */
8457 if (reload_completed
)
8462 for (b
= 0; b
< n_basic_blocks
; b
++)
8463 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8467 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
8470 link
= LOG_LINKS (insn
);
8473 rtx x
= XEXP (link
, 0);
8475 if (INSN_BLOCK (x
) != b
)
8477 remove_dependence (insn
, x
);
8478 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
8481 prev
= link
, link
= XEXP (prev
, 1);
8485 if (insn
== BLOCK_END (b
))
8491 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
8492 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8493 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8494 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8496 /* compute regions for scheduling */
8497 if (reload_completed
8498 || n_basic_blocks
== 1
8499 || !flag_schedule_interblock
)
8501 find_single_block_region ();
8505 /* verify that a 'good' control flow graph can be built */
8506 if (is_cfg_nonregular ())
8508 find_single_block_region ();
8512 int_list_ptr
*s_preds
, *s_succs
;
8513 int *num_preds
, *num_succs
;
8514 sbitmap
*dom
, *pdom
;
8516 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
8517 * sizeof (int_list_ptr
));
8518 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
8519 * sizeof (int_list_ptr
));
8520 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
8521 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
8522 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8523 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8525 /* The scheduler runs after flow; therefore, we can't blindly call
8526 back into find_basic_blocks since doing so could invalidate the
8527 info in basic_block_live_at_start.
8529 Consider a block consisting entirely of dead stores; after life
8530 analysis it would be a block of NOTE_INSN_DELETED notes. If
8531 we call find_basic_blocks again, then the block would be removed
8532 entirely and invalidate our the register live information.
8534 We could (should?) recompute register live information. Doing
8535 so may even be beneficial. */
8537 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
8539 /* Compute the dominators and post dominators. We don't currently use
8540 post dominators, but we should for speculative motion analysis. */
8541 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
8543 /* build_control_flow will return nonzero if it detects unreachable
8544 blocks or any other irregularity with the cfg which prevents
8545 cross block scheduling. */
8546 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
8547 find_single_block_region ();
8549 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
8551 if (sched_verbose
>= 3)
8554 /* For now. This will move as more and more of haifa is converted
8555 to using the cfg code in flow.c */
8562 /* Allocate data for this pass. See comments, above,
8563 for what these vectors do.
8565 We use xmalloc instead of alloca, because max_uid can be very large
8566 when there is a lot of function inlining. If we used alloca, we could
8567 exceed stack limits on some hosts for some inputs. */
8568 insn_priority
= (int *) xmalloc (max_uid
* sizeof (int));
8569 insn_reg_weight
= (int *) xmalloc (max_uid
* sizeof (int));
8570 insn_tick
= (int *) xmalloc (max_uid
* sizeof (int));
8571 insn_costs
= (short *) xmalloc (max_uid
* sizeof (short));
8572 insn_units
= (short *) xmalloc (max_uid
* sizeof (short));
8573 insn_blockage
= (unsigned int *) xmalloc (max_uid
* sizeof (unsigned int));
8574 insn_ref_count
= (int *) xmalloc (max_uid
* sizeof (int));
8576 /* Allocate for forward dependencies */
8577 insn_dep_count
= (int *) xmalloc (max_uid
* sizeof (int));
8578 insn_depend
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8580 if (reload_completed
== 0)
8584 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
8585 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
8586 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
8587 bb_live_regs
= ALLOCA_REG_SET ();
8588 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
8589 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
8591 for (i
= 0; i
< max_regno
; i
++)
8592 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
8596 sched_reg_n_calls_crossed
= 0;
8597 sched_reg_live_length
= 0;
8600 init_alias_analysis ();
8602 if (write_symbols
!= NO_DEBUG
)
8606 line_note
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8607 bzero ((char *) line_note
, max_uid
* sizeof (rtx
));
8608 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
8609 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
8611 /* Save-line-note-head:
8612 Determine the line-number at the start of each basic block.
8613 This must be computed and saved now, because after a basic block's
8614 predecessor has been scheduled, it is impossible to accurately
8615 determine the correct line number for the first insn of the block. */
8617 for (b
= 0; b
< n_basic_blocks
; b
++)
8618 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
8619 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
8621 line_note_head
[b
] = line
;
8626 bzero ((char *) insn_priority
, max_uid
* sizeof (int));
8627 bzero ((char *) insn_reg_weight
, max_uid
* sizeof (int));
8628 bzero ((char *) insn_tick
, max_uid
* sizeof (int));
8629 bzero ((char *) insn_costs
, max_uid
* sizeof (short));
8630 bzero ((char *) insn_units
, max_uid
* sizeof (short));
8631 bzero ((char *) insn_blockage
, max_uid
* sizeof (unsigned int));
8632 bzero ((char *) insn_ref_count
, max_uid
* sizeof (int));
8634 /* Initialize for forward dependencies */
8635 bzero ((char *) insn_depend
, max_uid
* sizeof (rtx
));
8636 bzero ((char *) insn_dep_count
, max_uid
* sizeof (int));
8638 /* Find units used in this fuction, for visualization */
8640 init_target_units ();
8642 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8643 known why this is done. */
8645 insn
= BLOCK_END (n_basic_blocks
- 1);
8646 if (NEXT_INSN (insn
) == 0
8647 || (GET_CODE (insn
) != NOTE
8648 && GET_CODE (insn
) != CODE_LABEL
8649 /* Don't emit a NOTE if it would end up between an unconditional
8650 jump and a BARRIER. */
8651 && !(GET_CODE (insn
) == JUMP_INSN
8652 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
8653 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
8655 /* Schedule every region in the subroutine */
8656 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
8658 schedule_region (rgn
);
8665 /* Reposition the prologue and epilogue notes in case we moved the
8666 prologue/epilogue insns. */
8667 if (reload_completed
)
8668 reposition_prologue_and_epilogue_notes (get_insns ());
8670 /* delete redundant line notes. */
8671 if (write_symbols
!= NO_DEBUG
)
8672 rm_redundant_line_notes ();
8674 /* Update information about uses of registers in the subroutine. */
8675 if (reload_completed
== 0)
8676 update_reg_usage ();
8680 if (reload_completed
== 0 && flag_schedule_interblock
)
8682 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8690 fprintf (dump
, "\n\n");
8694 free (fed_by_spec_load
);
8695 free (is_load_insn
);
8696 free (insn_orig_block
);
8699 free (insn_priority
);
8700 free (insn_reg_weight
);
8704 free (insn_blockage
);
8705 free (insn_ref_count
);
8707 free (insn_dep_count
);
8710 if (write_symbols
!= NO_DEBUG
)
8714 FREE_REG_SET (bb_live_regs
);
8733 #endif /* INSN_SCHEDULING */