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 rtx regno_use_in
PROTO ((int, rtx
));
452 static void split_hard_reg_notes
PROTO ((rtx
, rtx
, rtx
));
453 static void new_insn_dead_notes
PROTO ((rtx
, rtx
, rtx
, rtx
));
454 static void update_n_sets
PROTO ((rtx
, int));
455 static void update_flow_info
PROTO ((rtx
, rtx
, rtx
, rtx
));
456 static char *safe_concat
PROTO ((char *, char *, char *));
457 static int insn_issue_delay
PROTO ((rtx
));
458 static int birthing_insn_p
PROTO ((rtx
));
459 static void adjust_priority
PROTO ((rtx
));
461 /* Mapping of insns to their original block prior to scheduling. */
462 static int *insn_orig_block
;
463 #define INSN_BLOCK(insn) (insn_orig_block[INSN_UID (insn)])
465 /* Some insns (e.g. call) are not allowed to move across blocks. */
466 static char *cant_move
;
467 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
469 /* Control flow graph edges are kept in circular lists. */
478 static edge
*edge_table
;
480 #define NEXT_IN(edge) (edge_table[edge].next_in)
481 #define NEXT_OUT(edge) (edge_table[edge].next_out)
482 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
483 #define TO_BLOCK(edge) (edge_table[edge].to_block)
485 /* Number of edges in the control flow graph. (in fact larger than
486 that by 1, since edge 0 is unused.) */
489 /* Circular list of incoming/outgoing edges of a block */
490 static int *in_edges
;
491 static int *out_edges
;
493 #define IN_EDGES(block) (in_edges[block])
494 #define OUT_EDGES(block) (out_edges[block])
496 /* List of labels which cannot be deleted, needed for control
497 flow graph construction. */
498 extern rtx forced_labels
;
501 static int is_cfg_nonregular
PROTO ((void));
502 static int build_control_flow
PROTO ((int_list_ptr
*, int_list_ptr
*,
504 static void new_edge
PROTO ((int, int));
507 /* A region is the main entity for interblock scheduling: insns
508 are allowed to move between blocks in the same region, along
509 control flow graph edges, in the 'up' direction. */
512 int rgn_nr_blocks
; /* number of blocks in region */
513 int rgn_blocks
; /* blocks in the region (actually index in rgn_bb_table) */
517 /* Number of regions in the procedure */
518 static int nr_regions
;
520 /* Table of region descriptions */
521 static region
*rgn_table
;
523 /* Array of lists of regions' blocks */
524 static int *rgn_bb_table
;
526 /* Topological order of blocks in the region (if b2 is reachable from
527 b1, block_to_bb[b2] > block_to_bb[b1]).
528 Note: A basic block is always referred to by either block or b,
529 while its topological order name (in the region) is refered to by
532 static int *block_to_bb
;
534 /* The number of the region containing a block. */
535 static int *containing_rgn
;
537 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
538 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
539 #define BLOCK_TO_BB(block) (block_to_bb[block])
540 #define CONTAINING_RGN(block) (containing_rgn[block])
542 void debug_regions
PROTO ((void));
543 static void find_single_block_region
PROTO ((void));
544 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
545 int *, int *, sbitmap
*));
546 static int too_large
PROTO ((int, int *, int *));
548 extern void debug_live
PROTO ((int, int));
550 /* Blocks of the current region being scheduled. */
551 static int current_nr_blocks
;
552 static int current_blocks
;
554 /* The mapping from bb to block */
555 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
558 /* Bit vectors and bitset operations are needed for computations on
559 the control flow graph. */
561 typedef unsigned HOST_WIDE_INT
*bitset
;
564 int *first_member
; /* pointer to the list start in bitlst_table. */
565 int nr_members
; /* the number of members of the bit list. */
569 static int bitlst_table_last
;
570 static int bitlst_table_size
;
571 static int *bitlst_table
;
573 static char bitset_member
PROTO ((bitset
, int, int));
574 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
576 /* target info declarations.
578 The block currently being scheduled is referred to as the "target" block,
579 while other blocks in the region from which insns can be moved to the
580 target are called "source" blocks. The candidate structure holds info
581 about such sources: are they valid? Speculative? Etc. */
582 typedef bitlst bblst
;
593 static candidate
*candidate_table
;
595 /* A speculative motion requires checking live information on the path
596 from 'source' to 'target'. The split blocks are those to be checked.
597 After a speculative motion, live information should be modified in
600 Lists of split and update blocks for each candidate of the current
601 target are in array bblst_table */
602 static int *bblst_table
, bblst_size
, bblst_last
;
604 #define IS_VALID(src) ( candidate_table[src].is_valid )
605 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
606 #define SRC_PROB(src) ( candidate_table[src].src_prob )
608 /* The bb being currently scheduled. */
609 static int target_bb
;
612 typedef bitlst edgelst
;
614 /* target info functions */
615 static void split_edges
PROTO ((int, int, edgelst
*));
616 static void compute_trg_info
PROTO ((int));
617 void debug_candidate
PROTO ((int));
618 void debug_candidates
PROTO ((int));
621 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
622 typedef bitset bbset
;
624 /* Number of words of the bbset. */
625 static int bbset_size
;
627 /* Dominators array: dom[i] contains the bbset of dominators of
628 bb i in the region. */
631 /* bb 0 is the only region entry */
632 #define IS_RGN_ENTRY(bb) (!bb)
634 /* Is bb_src dominated by bb_trg. */
635 #define IS_DOMINATED(bb_src, bb_trg) \
636 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
638 /* Probability: Prob[i] is a float in [0, 1] which is the probability
639 of bb i relative to the region entry. */
642 /* The probability of bb_src, relative to bb_trg. Note, that while the
643 'prob[bb]' is a float in [0, 1], this macro returns an integer
645 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
648 /* Bit-set of edges, where bit i stands for edge i. */
649 typedef bitset edgeset
;
651 /* Number of edges in the region. */
652 static int rgn_nr_edges
;
654 /* Array of size rgn_nr_edges. */
655 static int *rgn_edges
;
657 /* Number of words in an edgeset. */
658 static int edgeset_size
;
660 /* Mapping from each edge in the graph to its number in the rgn. */
661 static int *edge_to_bit
;
662 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
664 /* The split edges of a source bb is different for each target
665 bb. In order to compute this efficiently, the 'potential-split edges'
666 are computed for each bb prior to scheduling a region. This is actually
667 the split edges of each bb relative to the region entry.
669 pot_split[bb] is the set of potential split edges of bb. */
670 static edgeset
*pot_split
;
672 /* For every bb, a set of its ancestor edges. */
673 static edgeset
*ancestor_edges
;
675 static void compute_dom_prob_ps
PROTO ((int));
677 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
678 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (INSN_BLOCK (INSN))))
679 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (INSN_BLOCK (INSN))))
680 #define INSN_BB(INSN) (BLOCK_TO_BB (INSN_BLOCK (INSN)))
682 /* parameters affecting the decision of rank_for_schedule() */
683 #define MIN_DIFF_PRIORITY 2
684 #define MIN_PROBABILITY 40
685 #define MIN_PROB_DIFF 10
687 /* speculative scheduling functions */
688 static int check_live_1
PROTO ((int, rtx
));
689 static void update_live_1
PROTO ((int, rtx
));
690 static int check_live
PROTO ((rtx
, int));
691 static void update_live
PROTO ((rtx
, int));
692 static void set_spec_fed
PROTO ((rtx
));
693 static int is_pfree
PROTO ((rtx
, int, int));
694 static int find_conditional_protection
PROTO ((rtx
, int));
695 static int is_conditionally_protected
PROTO ((rtx
, int, int));
696 static int may_trap_exp
PROTO ((rtx
, int));
697 static int haifa_classify_insn
PROTO ((rtx
));
698 static int is_prisky
PROTO ((rtx
, int, int));
699 static int is_exception_free
PROTO ((rtx
, int, int));
701 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
702 static void compute_block_forward_dependences
PROTO ((int));
703 static void init_rgn_data_dependences
PROTO ((int));
704 static void add_branch_dependences
PROTO ((rtx
, rtx
));
705 static void compute_block_backward_dependences
PROTO ((int));
706 void debug_dependencies
PROTO ((void));
708 /* Notes handling mechanism:
709 =========================
710 Generally, NOTES are saved before scheduling and restored after scheduling.
711 The scheduler distinguishes between three types of notes:
713 (1) LINE_NUMBER notes, generated and used for debugging. Here,
714 before scheduling a region, a pointer to the LINE_NUMBER note is
715 added to the insn following it (in save_line_notes()), and the note
716 is removed (in rm_line_notes() and unlink_line_notes()). After
717 scheduling the region, this pointer is used for regeneration of
718 the LINE_NUMBER note (in restore_line_notes()).
720 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
721 Before scheduling a region, a pointer to the note is added to the insn
722 that follows or precedes it. (This happens as part of the data dependence
723 computation). After scheduling an insn, the pointer contained in it is
724 used for regenerating the corresponding note (in reemit_notes).
726 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
727 these notes are put in a list (in rm_other_notes() and
728 unlink_other_notes ()). After scheduling the block, these notes are
729 inserted at the beginning of the block (in schedule_block()). */
731 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
732 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
733 static void rm_line_notes
PROTO ((int));
734 static void save_line_notes
PROTO ((int));
735 static void restore_line_notes
PROTO ((int));
736 static void rm_redundant_line_notes
PROTO ((void));
737 static void rm_other_notes
PROTO ((rtx
, rtx
));
738 static rtx reemit_notes
PROTO ((rtx
, rtx
));
740 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
742 static void find_pre_sched_live
PROTO ((int));
743 static void find_post_sched_live
PROTO ((int));
744 static void update_reg_usage
PROTO ((void));
745 static int queue_to_ready
PROTO ((rtx
[], int));
747 static void debug_ready_list
PROTO ((rtx
[], int));
748 static void init_target_units
PROTO ((void));
749 static void insn_print_units
PROTO ((rtx
));
750 static int get_visual_tbl_length
PROTO ((void));
751 static void init_block_visualization
PROTO ((void));
752 static void print_block_visualization
PROTO ((int, char *));
753 static void visualize_scheduled_insns
PROTO ((int, int));
754 static void visualize_no_unit
PROTO ((rtx
));
755 static void visualize_stall_cycles
PROTO ((int, int));
756 static void print_exp
PROTO ((char *, rtx
, int));
757 static void print_value
PROTO ((char *, rtx
, int));
758 static void print_pattern
PROTO ((char *, rtx
, int));
759 static void print_insn
PROTO ((char *, rtx
, int));
760 void debug_reg_vector
PROTO ((regset
));
762 static rtx move_insn1
PROTO ((rtx
, rtx
));
763 static rtx move_insn
PROTO ((rtx
, rtx
));
764 static rtx group_leader
PROTO ((rtx
));
765 static int set_priorities
PROTO ((int));
766 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
767 static void schedule_region
PROTO ((int));
768 static void split_block_insns
PROTO ((int));
770 #endif /* INSN_SCHEDULING */
772 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
774 /* Helper functions for instruction scheduling. */
776 /* An INSN_LIST containing all INSN_LISTs allocated but currently unused. */
777 static rtx unused_insn_list
;
779 /* An EXPR_LIST containing all EXPR_LISTs allocated but currently unused. */
780 static rtx unused_expr_list
;
782 static void free_list
PROTO ((rtx
*, rtx
*));
783 static rtx alloc_INSN_LIST
PROTO ((rtx
, rtx
));
784 static rtx alloc_EXPR_LIST
PROTO ((int, rtx
, rtx
));
787 free_list (listp
, unused_listp
)
788 rtx
*listp
, *unused_listp
;
790 register rtx link
, prev_link
;
796 link
= XEXP (prev_link
, 1);
801 link
= XEXP (link
, 1);
804 XEXP (prev_link
, 1) = *unused_listp
;
805 *unused_listp
= *listp
;
810 alloc_INSN_LIST (val
, next
)
815 if (unused_insn_list
)
817 r
= unused_insn_list
;
818 unused_insn_list
= XEXP (r
, 1);
821 PUT_REG_NOTE_KIND (r
, VOIDmode
);
824 r
= gen_rtx_INSN_LIST (VOIDmode
, val
, next
);
830 alloc_EXPR_LIST (kind
, val
, next
)
836 if (unused_expr_list
)
838 r
= unused_expr_list
;
839 unused_expr_list
= XEXP (r
, 1);
842 PUT_REG_NOTE_KIND (r
, kind
);
845 r
= gen_rtx_EXPR_LIST (kind
, val
, next
);
850 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
851 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
852 of dependence that this link represents. */
855 add_dependence (insn
, elem
, dep_type
)
858 enum reg_note dep_type
;
862 /* Don't depend an insn on itself. */
866 /* If elem is part of a sequence that must be scheduled together, then
867 make the dependence point to the last insn of the sequence.
868 When HAVE_cc0, it is possible for NOTEs to exist between users and
869 setters of the condition codes, so we must skip past notes here.
870 Otherwise, NOTEs are impossible here. */
872 next
= NEXT_INSN (elem
);
875 while (next
&& GET_CODE (next
) == NOTE
)
876 next
= NEXT_INSN (next
);
879 if (next
&& SCHED_GROUP_P (next
)
880 && GET_CODE (next
) != CODE_LABEL
)
882 /* Notes will never intervene here though, so don't bother checking
884 /* We must reject CODE_LABELs, so that we don't get confused by one
885 that has LABEL_PRESERVE_P set, which is represented by the same
886 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
888 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
889 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
890 next
= NEXT_INSN (next
);
892 /* Again, don't depend an insn on itself. */
896 /* Make the dependence to NEXT, the last insn of the group, instead
897 of the original ELEM. */
901 #ifdef INSN_SCHEDULING
902 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
903 No need for interblock dependences with calls, since
904 calls are not moved between blocks. Note: the edge where
905 elem is a CALL is still required. */
906 if (GET_CODE (insn
) == CALL_INSN
907 && (INSN_BB (elem
) != INSN_BB (insn
)))
912 /* Check that we don't already have this dependence. */
913 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
914 if (XEXP (link
, 0) == elem
)
916 /* If this is a more restrictive type of dependence than the existing
917 one, then change the existing dependence to this type. */
918 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
919 PUT_REG_NOTE_KIND (link
, dep_type
);
922 /* Might want to check one level of transitivity to save conses. */
924 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
925 LOG_LINKS (insn
) = link
;
927 /* Insn dependency, not data dependency. */
928 PUT_REG_NOTE_KIND (link
, dep_type
);
931 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
932 of INSN. Abort if not found. */
935 remove_dependence (insn
, elem
)
939 rtx prev
, link
, next
;
942 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
944 next
= XEXP (link
, 1);
945 if (XEXP (link
, 0) == elem
)
948 XEXP (prev
, 1) = next
;
950 LOG_LINKS (insn
) = next
;
952 XEXP (link
, 1) = unused_insn_list
;
953 unused_insn_list
= link
;
966 #ifndef INSN_SCHEDULING
968 schedule_insns (dump_file
)
978 #define HAIFA_INLINE __inline
981 /* Computation of memory dependencies. */
983 /* The *_insns and *_mems are paired lists. Each pending memory operation
984 will have a pointer to the MEM rtx on one list and a pointer to the
985 containing insn on the other list in the same place in the list. */
987 /* We can't use add_dependence like the old code did, because a single insn
988 may have multiple memory accesses, and hence needs to be on the list
989 once for each memory access. Add_dependence won't let you add an insn
990 to a list more than once. */
992 /* An INSN_LIST containing all insns with pending read operations. */
993 static rtx pending_read_insns
;
995 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
996 static rtx pending_read_mems
;
998 /* An INSN_LIST containing all insns with pending write operations. */
999 static rtx pending_write_insns
;
1001 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
1002 static rtx pending_write_mems
;
1004 /* Indicates the combined length of the two pending lists. We must prevent
1005 these lists from ever growing too large since the number of dependencies
1006 produced is at least O(N*N), and execution time is at least O(4*N*N), as
1007 a function of the length of these pending lists. */
1009 static int pending_lists_length
;
1011 /* The last insn upon which all memory references must depend.
1012 This is an insn which flushed the pending lists, creating a dependency
1013 between it and all previously pending memory references. This creates
1014 a barrier (or a checkpoint) which no memory reference is allowed to cross.
1016 This includes all non constant CALL_INSNs. When we do interprocedural
1017 alias analysis, this restriction can be relaxed.
1018 This may also be an INSN that writes memory if the pending lists grow
1021 static rtx last_pending_memory_flush
;
1023 /* The last function call we have seen. All hard regs, and, of course,
1024 the last function call, must depend on this. */
1026 static rtx last_function_call
;
1028 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
1029 that does not already cross a call. We create dependencies between each
1030 of those insn and the next call insn, to ensure that they won't cross a call
1031 after scheduling is done. */
1033 static rtx sched_before_next_call
;
1035 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
1036 so that insns independent of the last scheduled insn will be preferred
1037 over dependent instructions. */
1039 static rtx last_scheduled_insn
;
1041 /* Data structures for the computation of data dependences in a regions. We
1042 keep one copy of each of the declared above variables for each bb in the
1043 region. Before analyzing the data dependences for a bb, its variables
1044 are initialized as a function of the variables of its predecessors. When
1045 the analysis for a bb completes, we save the contents of each variable X
1046 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
1047 copied to bb_pending_read_insns[bb]. Another change is that few
1048 variables are now a list of insns rather than a single insn:
1049 last_pending_memory_flash, last_function_call, reg_last_sets. The
1050 manipulation of these variables was changed appropriately. */
1052 static rtx
**bb_reg_last_uses
;
1053 static rtx
**bb_reg_last_sets
;
1055 static rtx
*bb_pending_read_insns
;
1056 static rtx
*bb_pending_read_mems
;
1057 static rtx
*bb_pending_write_insns
;
1058 static rtx
*bb_pending_write_mems
;
1059 static int *bb_pending_lists_length
;
1061 static rtx
*bb_last_pending_memory_flush
;
1062 static rtx
*bb_last_function_call
;
1063 static rtx
*bb_sched_before_next_call
;
1065 /* functions for construction of the control flow graph. */
1067 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
1069 We decide not to build the control flow graph if there is possibly more
1070 than one entry to the function, if computed branches exist, of if we
1071 have nonlocal gotos. */
1074 is_cfg_nonregular ()
1080 /* If we have a label that could be the target of a nonlocal goto, then
1081 the cfg is not well structured. */
1082 if (nonlocal_label_rtx_list () != NULL
)
1085 /* If we have any forced labels, then the cfg is not well structured. */
1089 /* If this function has a computed jump, then we consider the cfg
1090 not well structured. */
1091 if (current_function_has_computed_jump
)
1094 /* If we have exception handlers, then we consider the cfg not well
1095 structured. ?!? We should be able to handle this now that flow.c
1096 computes an accurate cfg for EH. */
1097 if (exception_handler_labels
)
1100 /* If we have non-jumping insns which refer to labels, then we consider
1101 the cfg not well structured. */
1102 /* check for labels referred to other thn by jumps */
1103 for (b
= 0; b
< n_basic_blocks
; b
++)
1104 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1106 code
= GET_CODE (insn
);
1107 if (GET_RTX_CLASS (code
) == 'i')
1111 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1112 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1116 if (insn
== BLOCK_END (b
))
1120 /* All the tests passed. Consider the cfg well structured. */
1124 /* Build the control flow graph and set nr_edges.
1126 Instead of trying to build a cfg ourselves, we rely on flow to
1127 do it for us. Stamp out useless code (and bug) duplication.
1129 Return nonzero if an irregularity in the cfg is found which would
1130 prevent cross block scheduling. */
1133 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1134 int_list_ptr
*s_preds
;
1135 int_list_ptr
*s_succs
;
1143 /* Count the number of edges in the cfg. */
1146 for (i
= 0; i
< n_basic_blocks
; i
++)
1148 nr_edges
+= num_succs
[i
];
1150 /* Unreachable loops with more than one basic block are detected
1151 during the DFS traversal in find_rgns.
1153 Unreachable loops with a single block are detected here. This
1154 test is redundant with the one in find_rgns, but it's much
1155 cheaper to go ahead and catch the trivial case here. */
1156 if (num_preds
[i
] == 0
1157 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1161 /* Account for entry/exit edges. */
1164 in_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1165 out_edges
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1166 bzero ((char *) in_edges
, n_basic_blocks
* sizeof (int));
1167 bzero ((char *) out_edges
, n_basic_blocks
* sizeof (int));
1169 edge_table
= (edge
*) xmalloc ((nr_edges
) * sizeof (edge
));
1170 bzero ((char *) edge_table
, ((nr_edges
) * sizeof (edge
)));
1173 for (i
= 0; i
< n_basic_blocks
; i
++)
1174 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1176 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1177 new_edge (i
, INT_LIST_VAL (succ
));
1180 /* increment by 1, since edge 0 is unused. */
1187 /* Record an edge in the control flow graph from SOURCE to TARGET.
1189 In theory, this is redundant with the s_succs computed above, but
1190 we have not converted all of haifa to use information from the
1194 new_edge (source
, target
)
1198 int curr_edge
, fst_edge
;
1200 /* check for duplicates */
1201 fst_edge
= curr_edge
= OUT_EDGES (source
);
1204 if (FROM_BLOCK (curr_edge
) == source
1205 && TO_BLOCK (curr_edge
) == target
)
1210 curr_edge
= NEXT_OUT (curr_edge
);
1212 if (fst_edge
== curr_edge
)
1218 FROM_BLOCK (e
) = source
;
1219 TO_BLOCK (e
) = target
;
1221 if (OUT_EDGES (source
))
1223 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1224 NEXT_OUT (OUT_EDGES (source
)) = e
;
1225 NEXT_OUT (e
) = next_edge
;
1229 OUT_EDGES (source
) = e
;
1233 if (IN_EDGES (target
))
1235 next_edge
= NEXT_IN (IN_EDGES (target
));
1236 NEXT_IN (IN_EDGES (target
)) = e
;
1237 NEXT_IN (e
) = next_edge
;
1241 IN_EDGES (target
) = e
;
1247 /* BITSET macros for operations on the control flow graph. */
1249 /* Compute bitwise union of two bitsets. */
1250 #define BITSET_UNION(set1, set2, len) \
1251 do { register bitset tp = set1, sp = set2; \
1253 for (i = 0; i < len; i++) \
1254 *(tp++) |= *(sp++); } while (0)
1256 /* Compute bitwise intersection of two bitsets. */
1257 #define BITSET_INTER(set1, set2, len) \
1258 do { register bitset tp = set1, sp = set2; \
1260 for (i = 0; i < len; i++) \
1261 *(tp++) &= *(sp++); } while (0)
1263 /* Compute bitwise difference of two bitsets. */
1264 #define BITSET_DIFFER(set1, set2, len) \
1265 do { register bitset tp = set1, sp = set2; \
1267 for (i = 0; i < len; i++) \
1268 *(tp++) &= ~*(sp++); } while (0)
1270 /* Inverts every bit of bitset 'set' */
1271 #define BITSET_INVERT(set, len) \
1272 do { register bitset tmpset = set; \
1274 for (i = 0; i < len; i++, tmpset++) \
1275 *tmpset = ~*tmpset; } while (0)
1277 /* Turn on the index'th bit in bitset set. */
1278 #define BITSET_ADD(set, index, len) \
1280 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1283 set[index/HOST_BITS_PER_WIDE_INT] |= \
1284 1 << (index % HOST_BITS_PER_WIDE_INT); \
1287 /* Turn off the index'th bit in set. */
1288 #define BITSET_REMOVE(set, index, len) \
1290 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1293 set[index/HOST_BITS_PER_WIDE_INT] &= \
1294 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1298 /* Check if the index'th bit in bitset set is on. */
1301 bitset_member (set
, index
, len
)
1305 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1307 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1308 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1312 /* Translate a bit-set SET to a list BL of the bit-set members. */
1315 extract_bitlst (set
, len
, bl
)
1321 unsigned HOST_WIDE_INT word
;
1323 /* bblst table space is reused in each call to extract_bitlst */
1324 bitlst_table_last
= 0;
1326 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1329 for (i
= 0; i
< len
; i
++)
1332 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1333 for (j
= 0; word
; j
++)
1337 bitlst_table
[bitlst_table_last
++] = offset
;
1348 /* functions for the construction of regions */
1350 /* Print the regions, for debugging purposes. Callable from debugger. */
1357 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1358 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1360 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1361 rgn_table
[rgn
].rgn_nr_blocks
);
1362 fprintf (dump
, ";;\tbb/block: ");
1364 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1366 current_blocks
= RGN_BLOCKS (rgn
);
1368 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1371 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1374 fprintf (dump
, "\n\n");
1379 /* Build a single block region for each basic block in the function.
1380 This allows for using the same code for interblock and basic block
1384 find_single_block_region ()
1388 for (i
= 0; i
< n_basic_blocks
; i
++)
1390 rgn_bb_table
[i
] = i
;
1391 RGN_NR_BLOCKS (i
) = 1;
1393 CONTAINING_RGN (i
) = i
;
1394 BLOCK_TO_BB (i
) = 0;
1396 nr_regions
= n_basic_blocks
;
1400 /* Update number of blocks and the estimate for number of insns
1401 in the region. Return 1 if the region is "too large" for interblock
1402 scheduling (compile time considerations), otherwise return 0. */
1405 too_large (block
, num_bbs
, num_insns
)
1406 int block
, *num_bbs
, *num_insns
;
1409 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1410 INSN_LUID (BLOCK_HEAD (block
)));
1411 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1418 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1419 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1420 loop containing blk. */
1421 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1423 if (max_hdr[blk] == -1) \
1424 max_hdr[blk] = hdr; \
1425 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1426 RESET_BIT (inner, hdr); \
1427 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1429 RESET_BIT (inner,max_hdr[blk]); \
1430 max_hdr[blk] = hdr; \
1435 /* Find regions for interblock scheduling.
1437 A region for scheduling can be:
1439 * A loop-free procedure, or
1441 * A reducible inner loop, or
1443 * A basic block not contained in any other region.
1446 ?!? In theory we could build other regions based on extended basic
1447 blocks or reverse extended basic blocks. Is it worth the trouble?
1449 Loop blocks that form a region are put into the region's block list
1450 in topological order.
1452 This procedure stores its results into the following global (ick) variables
1461 We use dominator relationships to avoid making regions out of non-reducible
1464 This procedure needs to be converted to work on pred/succ lists instead
1465 of edge tables. That would simplify it somewhat. */
1468 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1469 int_list_ptr
*s_preds
;
1470 int_list_ptr
*s_succs
;
1475 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1477 int node
, child
, loop_head
, i
, head
, tail
;
1478 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1479 int num_bbs
, num_insns
, unreachable
;
1480 int too_large_failure
;
1482 /* Note if an edge has been passed. */
1485 /* Note if a block is a natural loop header. */
1488 /* Note if a block is an natural inner loop header. */
1491 /* Note if a block is in the block queue. */
1494 /* Note if a block is in the block queue. */
1497 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1498 and a mapping from block to its loop header (if the block is contained
1499 in a loop, else -1).
1501 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1502 be used as inputs to the second traversal.
1504 STACK, SP and DFS_NR are only used during the first traversal. */
1506 /* Allocate and initialize variables for the first traversal. */
1507 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1508 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1509 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1510 stack
= (int *) alloca (nr_edges
* sizeof (int));
1512 inner
= sbitmap_alloc (n_basic_blocks
);
1513 sbitmap_ones (inner
);
1515 header
= sbitmap_alloc (n_basic_blocks
);
1516 sbitmap_zero (header
);
1518 passed
= sbitmap_alloc (nr_edges
);
1519 sbitmap_zero (passed
);
1521 in_queue
= sbitmap_alloc (n_basic_blocks
);
1522 sbitmap_zero (in_queue
);
1524 in_stack
= sbitmap_alloc (n_basic_blocks
);
1525 sbitmap_zero (in_stack
);
1527 for (i
= 0; i
< n_basic_blocks
; i
++)
1530 /* DFS traversal to find inner loops in the cfg. */
1535 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1537 /* We have reached a leaf node or a node that was already
1538 processed. Pop edges off the stack until we find
1539 an edge that has not yet been processed. */
1541 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1543 /* Pop entry off the stack. */
1544 current_edge
= stack
[sp
--];
1545 node
= FROM_BLOCK (current_edge
);
1546 child
= TO_BLOCK (current_edge
);
1547 RESET_BIT (in_stack
, child
);
1548 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1549 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1550 current_edge
= NEXT_OUT (current_edge
);
1553 /* See if have finished the DFS tree traversal. */
1554 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1557 /* Nope, continue the traversal with the popped node. */
1561 /* Process a node. */
1562 node
= FROM_BLOCK (current_edge
);
1563 child
= TO_BLOCK (current_edge
);
1564 SET_BIT (in_stack
, node
);
1565 dfs_nr
[node
] = ++count
;
1567 /* If the successor is in the stack, then we've found a loop.
1568 Mark the loop, if it is not a natural loop, then it will
1569 be rejected during the second traversal. */
1570 if (TEST_BIT (in_stack
, child
))
1573 SET_BIT (header
, child
);
1574 UPDATE_LOOP_RELATIONS (node
, child
);
1575 SET_BIT (passed
, current_edge
);
1576 current_edge
= NEXT_OUT (current_edge
);
1580 /* If the child was already visited, then there is no need to visit
1581 it again. Just update the loop relationships and restart
1585 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1586 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1587 SET_BIT (passed
, current_edge
);
1588 current_edge
= NEXT_OUT (current_edge
);
1592 /* Push an entry on the stack and continue DFS traversal. */
1593 stack
[++sp
] = current_edge
;
1594 SET_BIT (passed
, current_edge
);
1595 current_edge
= OUT_EDGES (child
);
1598 /* Another check for unreachable blocks. The earlier test in
1599 is_cfg_nonregular only finds unreachable blocks that do not
1602 The DFS traversal will mark every block that is reachable from
1603 the entry node by placing a nonzero value in dfs_nr. Thus if
1604 dfs_nr is zero for any block, then it must be unreachable. */
1606 for (i
= 0; i
< n_basic_blocks
; i
++)
1613 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1614 to hold degree counts. */
1617 /* Compute the in-degree of every block in the graph */
1618 for (i
= 0; i
< n_basic_blocks
; i
++)
1619 degree
[i
] = num_preds
[i
];
1621 /* Do not perform region scheduling if there are any unreachable
1626 SET_BIT (header
, 0);
1628 /* Second travsersal:find reducible inner loops and topologically sort
1629 block of each region. */
1631 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1633 /* Find blocks which are inner loop headers. We still have non-reducible
1634 loops to consider at this point. */
1635 for (i
= 0; i
< n_basic_blocks
; i
++)
1637 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1642 /* Now check that the loop is reducible. We do this separate
1643 from finding inner loops so that we do not find a reducible
1644 loop which contains an inner non-reducible loop.
1646 A simple way to find reducible/natrual loops is to verify
1647 that each block in the loop is dominated by the loop
1650 If there exists a block that is not dominated by the loop
1651 header, then the block is reachable from outside the loop
1652 and thus the loop is not a natural loop. */
1653 for (j
= 0; j
< n_basic_blocks
; j
++)
1655 /* First identify blocks in the loop, except for the loop
1657 if (i
== max_hdr
[j
] && i
!= j
)
1659 /* Now verify that the block is dominated by the loop
1661 if (!TEST_BIT (dom
[j
], i
))
1666 /* If we exited the loop early, then I is the header of a non
1667 reducible loop and we should quit processing it now. */
1668 if (j
!= n_basic_blocks
)
1671 /* I is a header of an inner loop, or block 0 in a subroutine
1672 with no loops at all. */
1674 too_large_failure
= 0;
1675 loop_head
= max_hdr
[i
];
1677 /* Decrease degree of all I's successors for topological
1679 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1680 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1681 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1682 --degree
[INT_LIST_VAL(ps
)];
1684 /* Estimate # insns, and count # blocks in the region. */
1686 num_insns
= (INSN_LUID (BLOCK_END (i
))
1687 - INSN_LUID (BLOCK_HEAD (i
)));
1690 /* Find all loop latches (blocks which back edges to the loop
1691 header) or all the leaf blocks in the cfg has no loops.
1693 Place those blocks into the queue. */
1696 for (j
= 0; j
< n_basic_blocks
; j
++)
1697 /* Leaf nodes have only a single successor which must
1699 if (num_succs
[j
] == 1
1700 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1703 SET_BIT (in_queue
, j
);
1705 if (too_large (j
, &num_bbs
, &num_insns
))
1707 too_large_failure
= 1;
1716 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1718 node
= INT_LIST_VAL (ps
);
1720 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1723 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1725 /* This is a loop latch. */
1726 queue
[++tail
] = node
;
1727 SET_BIT (in_queue
, node
);
1729 if (too_large (node
, &num_bbs
, &num_insns
))
1731 too_large_failure
= 1;
1739 /* Now add all the blocks in the loop to the queue.
1741 We know the loop is a natural loop; however the algorithm
1742 above will not always mark certain blocks as being in the
1751 The algorithm in the DFS traversal may not mark B & D as part
1752 of the loop (ie they will not have max_hdr set to A).
1754 We know they can not be loop latches (else they would have
1755 had max_hdr set since they'd have a backedge to a dominator
1756 block). So we don't need them on the initial queue.
1758 We know they are part of the loop because they are dominated
1759 by the loop header and can be reached by a backwards walk of
1760 the edges starting with nodes on the initial queue.
1762 It is safe and desirable to include those nodes in the
1763 loop/scheduling region. To do so we would need to decrease
1764 the degree of a node if it is the target of a backedge
1765 within the loop itself as the node is placed in the queue.
1767 We do not do this because I'm not sure that the actual
1768 scheduling code will properly handle this case. ?!? */
1770 while (head
< tail
&& !too_large_failure
)
1773 child
= queue
[++head
];
1775 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1777 node
= INT_LIST_VAL (ps
);
1779 /* See discussion above about nodes not marked as in
1780 this loop during the initial DFS traversal. */
1781 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1782 || max_hdr
[node
] != loop_head
)
1787 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1789 queue
[++tail
] = node
;
1790 SET_BIT (in_queue
, node
);
1792 if (too_large (node
, &num_bbs
, &num_insns
))
1794 too_large_failure
= 1;
1801 if (tail
>= 0 && !too_large_failure
)
1803 /* Place the loop header into list of region blocks. */
1805 rgn_bb_table
[idx
] = i
;
1806 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1807 RGN_BLOCKS (nr_regions
) = idx
++;
1808 CONTAINING_RGN (i
) = nr_regions
;
1809 BLOCK_TO_BB (i
) = count
= 0;
1811 /* Remove blocks from queue[] when their in degree becomes
1812 zero. Repeat until no blocks are left on the list. This
1813 produces a topological list of blocks in the region. */
1820 child
= queue
[head
];
1821 if (degree
[child
] == 0)
1824 rgn_bb_table
[idx
++] = child
;
1825 BLOCK_TO_BB (child
) = ++count
;
1826 CONTAINING_RGN (child
) = nr_regions
;
1827 queue
[head
] = queue
[tail
--];
1829 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1830 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1831 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1832 --degree
[INT_LIST_VAL (ps
)];
1843 /* Any block that did not end up in a region is placed into a region
1845 for (i
= 0; i
< n_basic_blocks
; i
++)
1848 rgn_bb_table
[idx
] = i
;
1849 RGN_NR_BLOCKS (nr_regions
) = 1;
1850 RGN_BLOCKS (nr_regions
) = idx
++;
1851 CONTAINING_RGN (i
) = nr_regions
++;
1852 BLOCK_TO_BB (i
) = 0;
1863 /* functions for regions scheduling information */
1865 /* Compute dominators, probability, and potential-split-edges of bb.
1866 Assume that these values were already computed for bb's predecessors. */
1869 compute_dom_prob_ps (bb
)
1872 int nxt_in_edge
, fst_in_edge
, pred
;
1873 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1876 if (IS_RGN_ENTRY (bb
))
1878 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1883 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1885 /* intialize dom[bb] to '111..1' */
1886 BITSET_INVERT (dom
[bb
], bbset_size
);
1890 pred
= FROM_BLOCK (nxt_in_edge
);
1891 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1893 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1896 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1899 nr_rgn_out_edges
= 0;
1900 fst_out_edge
= OUT_EDGES (pred
);
1901 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1902 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1905 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1907 /* the successor doesn't belong the region? */
1908 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1909 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1912 while (fst_out_edge
!= nxt_out_edge
)
1915 /* the successor doesn't belong the region? */
1916 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1917 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1919 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1920 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1924 /* now nr_rgn_out_edges is the number of region-exit edges from pred,
1925 and nr_out_edges will be the number of pred out edges not leaving
1927 nr_out_edges
-= nr_rgn_out_edges
;
1928 if (nr_rgn_out_edges
> 0)
1929 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1931 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1932 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1934 while (fst_in_edge
!= nxt_in_edge
);
1936 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1937 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1939 if (sched_verbose
>= 2)
1940 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1941 } /* compute_dom_prob_ps */
1943 /* functions for target info */
1945 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1946 Note that bb_trg dominates bb_src. */
1949 split_edges (bb_src
, bb_trg
, bl
)
1954 int es
= edgeset_size
;
1955 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1958 src
[es
] = (pot_split
[bb_src
])[es
];
1959 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1960 extract_bitlst (src
, edgeset_size
, bl
);
1964 /* Find the valid candidate-source-blocks for the target block TRG, compute
1965 their probability, and check if they are speculative or not.
1966 For speculative sources, compute their update-blocks and split-blocks. */
1969 compute_trg_info (trg
)
1972 register candidate
*sp
;
1974 int check_block
, update_idx
;
1975 int i
, j
, k
, fst_edge
, nxt_edge
;
1977 /* define some of the fields for the target bb as well */
1978 sp
= candidate_table
+ trg
;
1980 sp
->is_speculative
= 0;
1983 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1985 sp
= candidate_table
+ i
;
1987 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1990 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1991 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1996 split_edges (i
, trg
, &el
);
1997 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1998 if (sp
->is_speculative
&& !flag_schedule_speculative
)
2004 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
2005 sp
->split_bbs
.nr_members
= el
.nr_members
;
2006 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
2007 bblst_table
[bblst_last
] =
2008 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2009 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
2011 for (j
= 0; j
< el
.nr_members
; j
++)
2013 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
2014 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
2017 for (k
= 0; k
< el
.nr_members
; k
++)
2018 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
2021 if (k
>= el
.nr_members
)
2023 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
2027 nxt_edge
= NEXT_OUT (nxt_edge
);
2029 while (fst_edge
!= nxt_edge
);
2031 sp
->update_bbs
.nr_members
= update_idx
;
2036 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
2038 sp
->is_speculative
= 0;
2042 } /* compute_trg_info */
2045 /* Print candidates info, for debugging purposes. Callable from debugger. */
2051 if (!candidate_table
[i
].is_valid
)
2054 if (candidate_table
[i
].is_speculative
)
2057 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2059 fprintf (dump
, "split path: ");
2060 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2062 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2064 fprintf (dump
, " %d ", b
);
2066 fprintf (dump
, "\n");
2068 fprintf (dump
, "update path: ");
2069 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2071 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2073 fprintf (dump
, " %d ", b
);
2075 fprintf (dump
, "\n");
2079 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2084 /* Print candidates info, for debugging purposes. Callable from debugger. */
2087 debug_candidates (trg
)
2092 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2093 BB_TO_BLOCK (trg
), trg
);
2094 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2095 debug_candidate (i
);
2099 /* functions for speculative scheduing */
2101 /* Return 0 if x is a set of a register alive in the beginning of one
2102 of the split-blocks of src, otherwise return 1. */
2105 check_live_1 (src
, x
)
2111 register rtx reg
= SET_DEST (x
);
2116 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2117 || GET_CODE (reg
) == SIGN_EXTRACT
2118 || GET_CODE (reg
) == STRICT_LOW_PART
)
2119 reg
= XEXP (reg
, 0);
2121 if (GET_CODE (reg
) == PARALLEL
2122 && GET_MODE (reg
) == BLKmode
)
2125 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2126 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2131 if (GET_CODE (reg
) != REG
)
2134 regno
= REGNO (reg
);
2136 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2138 /* Global registers are assumed live */
2143 if (regno
< FIRST_PSEUDO_REGISTER
)
2145 /* check for hard registers */
2146 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2149 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2151 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2153 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
+ j
))
2162 /* check for psuedo registers */
2163 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2165 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2167 if (REGNO_REG_SET_P (basic_block_live_at_start
[b
], regno
))
2179 /* If x is a set of a register R, mark that R is alive in the beginning
2180 of every update-block of src. */
2183 update_live_1 (src
, x
)
2189 register rtx reg
= SET_DEST (x
);
2194 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2195 || GET_CODE (reg
) == SIGN_EXTRACT
2196 || GET_CODE (reg
) == STRICT_LOW_PART
)
2197 reg
= XEXP (reg
, 0);
2199 if (GET_CODE (reg
) == PARALLEL
2200 && GET_MODE (reg
) == BLKmode
)
2203 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2204 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2208 if (GET_CODE (reg
) != REG
)
2211 /* Global registers are always live, so the code below does not apply
2214 regno
= REGNO (reg
);
2216 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2218 if (regno
< FIRST_PSEUDO_REGISTER
)
2220 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2223 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2225 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2227 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
+ j
);
2233 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2235 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2237 SET_REGNO_REG_SET (basic_block_live_at_start
[b
], regno
);
2244 /* Return 1 if insn can be speculatively moved from block src to trg,
2245 otherwise return 0. Called before first insertion of insn to
2246 ready-list or before the scheduling. */
2249 check_live (insn
, src
)
2253 /* find the registers set by instruction */
2254 if (GET_CODE (PATTERN (insn
)) == SET
2255 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2256 return check_live_1 (src
, PATTERN (insn
));
2257 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2260 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2261 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2262 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2263 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2273 /* Update the live registers info after insn was moved speculatively from
2274 block src to trg. */
2277 update_live (insn
, src
)
2281 /* find the registers set by instruction */
2282 if (GET_CODE (PATTERN (insn
)) == SET
2283 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2284 update_live_1 (src
, PATTERN (insn
));
2285 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2288 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2289 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2290 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2291 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2295 /* Exception Free Loads:
2297 We define five classes of speculative loads: IFREE, IRISKY,
2298 PFREE, PRISKY, and MFREE.
2300 IFREE loads are loads that are proved to be exception-free, just
2301 by examining the load insn. Examples for such loads are loads
2302 from TOC and loads of global data.
2304 IRISKY loads are loads that are proved to be exception-risky,
2305 just by examining the load insn. Examples for such loads are
2306 volatile loads and loads from shared memory.
2308 PFREE loads are loads for which we can prove, by examining other
2309 insns, that they are exception-free. Currently, this class consists
2310 of loads for which we are able to find a "similar load", either in
2311 the target block, or, if only one split-block exists, in that split
2312 block. Load2 is similar to load1 if both have same single base
2313 register. We identify only part of the similar loads, by finding
2314 an insn upon which both load1 and load2 have a DEF-USE dependence.
2316 PRISKY loads are loads for which we can prove, by examining other
2317 insns, that they are exception-risky. Currently we have two proofs for
2318 such loads. The first proof detects loads that are probably guarded by a
2319 test on the memory address. This proof is based on the
2320 backward and forward data dependence information for the region.
2321 Let load-insn be the examined load.
2322 Load-insn is PRISKY iff ALL the following hold:
2324 - insn1 is not in the same block as load-insn
2325 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2326 - test-insn is either a compare or a branch, not in the same block as load-insn
2327 - load-insn is reachable from test-insn
2328 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2330 This proof might fail when the compare and the load are fed
2331 by an insn not in the region. To solve this, we will add to this
2332 group all loads that have no input DEF-USE dependence.
2334 The second proof detects loads that are directly or indirectly
2335 fed by a speculative load. This proof is affected by the
2336 scheduling process. We will use the flag fed_by_spec_load.
2337 Initially, all insns have this flag reset. After a speculative
2338 motion of an insn, if insn is either a load, or marked as
2339 fed_by_spec_load, we will also mark as fed_by_spec_load every
2340 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2341 load which is fed_by_spec_load is also PRISKY.
2343 MFREE (maybe-free) loads are all the remaining loads. They may be
2344 exception-free, but we cannot prove it.
2346 Now, all loads in IFREE and PFREE classes are considered
2347 exception-free, while all loads in IRISKY and PRISKY classes are
2348 considered exception-risky. As for loads in the MFREE class,
2349 these are considered either exception-free or exception-risky,
2350 depending on whether we are pessimistic or optimistic. We have
2351 to take the pessimistic approach to assure the safety of
2352 speculative scheduling, but we can take the optimistic approach
2353 by invoking the -fsched_spec_load_dangerous option. */
2355 enum INSN_TRAP_CLASS
2357 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2358 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2361 #define WORST_CLASS(class1, class2) \
2362 ((class1 > class2) ? class1 : class2)
2364 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between */
2365 /* some speculatively moved load insn and this one. */
2366 char *fed_by_spec_load
;
2369 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2370 #define IS_REACHABLE(bb_from, bb_to) \
2372 || IS_RGN_ENTRY (bb_from) \
2373 || (bitset_member (ancestor_edges[bb_to], \
2374 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2376 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2377 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2379 /* Non-zero iff the address is comprised from at most 1 register */
2380 #define CONST_BASED_ADDRESS_P(x) \
2381 (GET_CODE (x) == REG \
2382 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2383 || (GET_CODE (x) == LO_SUM)) \
2384 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2385 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2387 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2390 set_spec_fed (load_insn
)
2395 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2396 if (GET_MODE (link
) == VOIDmode
)
2397 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2398 } /* set_spec_fed */
2400 /* On the path from the insn to load_insn_bb, find a conditional branch */
2401 /* depending on insn, that guards the speculative load. */
2404 find_conditional_protection (insn
, load_insn_bb
)
2410 /* iterate through DEF-USE forward dependences */
2411 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2413 rtx next
= XEXP (link
, 0);
2414 if ((CONTAINING_RGN (INSN_BLOCK (next
)) ==
2415 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2416 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2417 && load_insn_bb
!= INSN_BB (next
)
2418 && GET_MODE (link
) == VOIDmode
2419 && (GET_CODE (next
) == JUMP_INSN
2420 || find_conditional_protection (next
, load_insn_bb
)))
2424 } /* find_conditional_protection */
2426 /* Returns 1 if the same insn1 that participates in the computation
2427 of load_insn's address is feeding a conditional branch that is
2428 guarding on load_insn. This is true if we find a the two DEF-USE
2430 insn1 -> ... -> conditional-branch
2431 insn1 -> ... -> load_insn,
2432 and if a flow path exist:
2433 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2434 and if insn1 is on the path
2435 region-entry -> ... -> bb_trg -> ... load_insn.
2437 Locate insn1 by climbing on LOG_LINKS from load_insn.
2438 Locate the branch by following INSN_DEPEND from insn1. */
2441 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2447 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2449 rtx insn1
= XEXP (link
, 0);
2451 /* must be a DEF-USE dependence upon non-branch */
2452 if (GET_MODE (link
) != VOIDmode
2453 || GET_CODE (insn1
) == JUMP_INSN
)
2456 /* must exist a path: region-entry -> ... -> bb_trg -> ... load_insn */
2457 if (INSN_BB (insn1
) == bb_src
2458 || (CONTAINING_RGN (INSN_BLOCK (insn1
))
2459 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2460 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2461 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2464 /* now search for the conditional-branch */
2465 if (find_conditional_protection (insn1
, bb_src
))
2468 /* recursive step: search another insn1, "above" current insn1. */
2469 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2472 /* the chain does not exsist */
2474 } /* is_conditionally_protected */
2476 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2477 load_insn can move speculatively from bb_src to bb_trg. All the
2478 following must hold:
2480 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2481 (2) load_insn and load1 have a def-use dependence upon
2482 the same insn 'insn1'.
2483 (3) either load2 is in bb_trg, or:
2484 - there's only one split-block, and
2485 - load1 is on the escape path, and
2487 From all these we can conclude that the two loads access memory
2488 addresses that differ at most by a constant, and hence if moving
2489 load_insn would cause an exception, it would have been caused by
2493 is_pfree (load_insn
, bb_src
, bb_trg
)
2498 register candidate
*candp
= candidate_table
+ bb_src
;
2500 if (candp
->split_bbs
.nr_members
!= 1)
2501 /* must have exactly one escape block */
2504 for (back_link
= LOG_LINKS (load_insn
);
2505 back_link
; back_link
= XEXP (back_link
, 1))
2507 rtx insn1
= XEXP (back_link
, 0);
2509 if (GET_MODE (back_link
) == VOIDmode
)
2511 /* found a DEF-USE dependence (insn1, load_insn) */
2514 for (fore_link
= INSN_DEPEND (insn1
);
2515 fore_link
; fore_link
= XEXP (fore_link
, 1))
2517 rtx insn2
= XEXP (fore_link
, 0);
2518 if (GET_MODE (fore_link
) == VOIDmode
)
2520 /* found a DEF-USE dependence (insn1, insn2) */
2521 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2522 /* insn2 not guaranteed to be a 1 base reg load */
2525 if (INSN_BB (insn2
) == bb_trg
)
2526 /* insn2 is the similar load, in the target block */
2529 if (*(candp
->split_bbs
.first_member
) == INSN_BLOCK (insn2
))
2530 /* insn2 is a similar load, in a split-block */
2537 /* couldn't find a similar load */
2541 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2542 as found by analyzing insn's expression. */
2545 may_trap_exp (x
, is_store
)
2553 code
= GET_CODE (x
);
2563 /* The insn uses memory */
2564 /* a volatile load */
2565 if (MEM_VOLATILE_P (x
))
2567 /* an exception-free load */
2568 if (!may_trap_p (x
))
2570 /* a load with 1 base register, to be further checked */
2571 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2572 return PFREE_CANDIDATE
;
2573 /* no info on the load, to be further checked */
2574 return PRISKY_CANDIDATE
;
2579 int i
, insn_class
= TRAP_FREE
;
2581 /* neither store nor load, check if it may cause a trap */
2584 /* recursive step: walk the insn... */
2585 fmt
= GET_RTX_FORMAT (code
);
2586 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2590 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2591 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2593 else if (fmt
[i
] == 'E')
2596 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2598 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2599 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2600 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2604 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2609 } /* may_trap_exp */
2612 /* Classifies insn for the purpose of verifying that it can be
2613 moved speculatively, by examining it's patterns, returning:
2614 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2615 TRAP_FREE: non-load insn.
2616 IFREE: load from a globaly safe location.
2617 IRISKY: volatile load.
2618 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2619 being either PFREE or PRISKY. */
2622 haifa_classify_insn (insn
)
2625 rtx pat
= PATTERN (insn
);
2626 int tmp_class
= TRAP_FREE
;
2627 int insn_class
= TRAP_FREE
;
2630 if (GET_CODE (pat
) == PARALLEL
)
2632 int i
, len
= XVECLEN (pat
, 0);
2634 for (i
= len
- 1; i
>= 0; i
--)
2636 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2640 /* test if it is a 'store' */
2641 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2644 /* test if it is a store */
2645 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2646 if (tmp_class
== TRAP_RISKY
)
2648 /* test if it is a load */
2650 WORST_CLASS (tmp_class
,
2651 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2654 tmp_class
= TRAP_RISKY
;
2658 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2659 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2665 code
= GET_CODE (pat
);
2669 /* test if it is a 'store' */
2670 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2673 /* test if it is a store */
2674 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2675 if (tmp_class
== TRAP_RISKY
)
2677 /* test if it is a load */
2679 WORST_CLASS (tmp_class
,
2680 may_trap_exp (SET_SRC (pat
), 0));
2683 tmp_class
= TRAP_RISKY
;
2687 insn_class
= tmp_class
;
2692 } /* haifa_classify_insn */
2694 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2695 a load moved speculatively, or if load_insn is protected by
2696 a compare on load_insn's address). */
2699 is_prisky (load_insn
, bb_src
, bb_trg
)
2703 if (FED_BY_SPEC_LOAD (load_insn
))
2706 if (LOG_LINKS (load_insn
) == NULL
)
2707 /* dependence may 'hide' out of the region. */
2710 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2716 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2717 Return 1 if insn is exception-free (and the motion is valid)
2721 is_exception_free (insn
, bb_src
, bb_trg
)
2725 int insn_class
= haifa_classify_insn (insn
);
2727 /* handle non-load insns */
2738 if (!flag_schedule_speculative_load
)
2740 IS_LOAD_INSN (insn
) = 1;
2747 case PFREE_CANDIDATE
:
2748 if (is_pfree (insn
, bb_src
, bb_trg
))
2750 /* don't 'break' here: PFREE-candidate is also PRISKY-candidate */
2751 case PRISKY_CANDIDATE
:
2752 if (!flag_schedule_speculative_load_dangerous
2753 || is_prisky (insn
, bb_src
, bb_trg
))
2759 return flag_schedule_speculative_load_dangerous
;
2760 } /* is_exception_free */
2763 /* Process an insn's memory dependencies. There are four kinds of
2766 (0) read dependence: read follows read
2767 (1) true dependence: read follows write
2768 (2) anti dependence: write follows read
2769 (3) output dependence: write follows write
2771 We are careful to build only dependencies which actually exist, and
2772 use transitivity to avoid building too many links. */
2774 /* Return the INSN_LIST containing INSN in LIST, or NULL
2775 if LIST does not contain INSN. */
2777 HAIFA_INLINE
static rtx
2778 find_insn_list (insn
, list
)
2784 if (XEXP (list
, 0) == insn
)
2786 list
= XEXP (list
, 1);
2792 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0 otherwise. */
2794 HAIFA_INLINE
static char
2795 find_insn_mem_list (insn
, x
, list
, list1
)
2801 if (XEXP (list
, 0) == insn
2802 && XEXP (list1
, 0) == x
)
2804 list
= XEXP (list
, 1);
2805 list1
= XEXP (list1
, 1);
2811 /* Compute the function units used by INSN. This caches the value
2812 returned by function_units_used. A function unit is encoded as the
2813 unit number if the value is non-negative and the compliment of a
2814 mask if the value is negative. A function unit index is the
2815 non-negative encoding. */
2817 HAIFA_INLINE
static int
2821 register int unit
= INSN_UNIT (insn
);
2825 recog_memoized (insn
);
2827 /* A USE insn, or something else we don't need to understand.
2828 We can't pass these directly to function_units_used because it will
2829 trigger a fatal error for unrecognizable insns. */
2830 if (INSN_CODE (insn
) < 0)
2834 unit
= function_units_used (insn
);
2835 /* Increment non-negative values so we can cache zero. */
2839 /* We only cache 16 bits of the result, so if the value is out of
2840 range, don't cache it. */
2841 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2843 || (~unit
& ((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2844 INSN_UNIT (insn
) = unit
;
2846 return (unit
> 0 ? unit
- 1 : unit
);
2849 /* Compute the blockage range for executing INSN on UNIT. This caches
2850 the value returned by the blockage_range_function for the unit.
2851 These values are encoded in an int where the upper half gives the
2852 minimum value and the lower half gives the maximum value. */
2854 HAIFA_INLINE
static unsigned int
2855 blockage_range (unit
, insn
)
2859 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2862 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2864 range
= function_units
[unit
].blockage_range_function (insn
);
2865 /* We only cache the blockage range for one unit and then only if
2867 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2868 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2871 range
= BLOCKAGE_RANGE (blockage
);
2876 /* A vector indexed by function unit instance giving the last insn to use
2877 the unit. The value of the function unit instance index for unit U
2878 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2879 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2881 /* A vector indexed by function unit instance giving the minimum time when
2882 the unit will unblock based on the maximum blockage cost. */
2883 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2885 /* A vector indexed by function unit number giving the number of insns
2886 that remain to use the unit. */
2887 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2889 /* Reset the function unit state to the null state. */
2894 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2895 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2896 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2899 /* Return the issue-delay of an insn */
2901 HAIFA_INLINE
static int
2902 insn_issue_delay (insn
)
2906 int unit
= insn_unit (insn
);
2908 /* efficiency note: in fact, we are working 'hard' to compute a
2909 value that was available in md file, and is not available in
2910 function_units[] structure. It would be nice to have this
2911 value there, too. */
2914 if (function_units
[unit
].blockage_range_function
&&
2915 function_units
[unit
].blockage_function
)
2916 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2919 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2920 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2921 && function_units
[i
].blockage_function
)
2922 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2927 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2928 instance INSTANCE at time CLOCK if the previous actual hazard cost
2931 HAIFA_INLINE
static int
2932 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2933 int unit
, instance
, clock
, cost
;
2936 int tick
= unit_tick
[instance
]; /* issue time of the last issued insn */
2938 if (tick
- clock
> cost
)
2940 /* The scheduler is operating forward, so unit's last insn is the
2941 executing insn and INSN is the candidate insn. We want a
2942 more exact measure of the blockage if we execute INSN at CLOCK
2943 given when we committed the execution of the unit's last insn.
2945 The blockage value is given by either the unit's max blockage
2946 constant, blockage range function, or blockage function. Use
2947 the most exact form for the given unit. */
2949 if (function_units
[unit
].blockage_range_function
)
2951 if (function_units
[unit
].blockage_function
)
2952 tick
+= (function_units
[unit
].blockage_function
2953 (unit_last_insn
[instance
], insn
)
2954 - function_units
[unit
].max_blockage
);
2956 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2957 - function_units
[unit
].max_blockage
);
2959 if (tick
- clock
> cost
)
2960 cost
= tick
- clock
;
2965 /* Record INSN as having begun execution on the units encoded by UNIT at
2968 HAIFA_INLINE
static void
2969 schedule_unit (unit
, insn
, clock
)
2977 int instance
= unit
;
2978 #if MAX_MULTIPLICITY > 1
2979 /* Find the first free instance of the function unit and use that
2980 one. We assume that one is free. */
2981 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2983 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2985 instance
+= FUNCTION_UNITS_SIZE
;
2988 unit_last_insn
[instance
] = insn
;
2989 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2992 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2993 if ((unit
& 1) != 0)
2994 schedule_unit (i
, insn
, clock
);
2997 /* Return the actual hazard cost of executing INSN on the units encoded by
2998 UNIT at time CLOCK if the previous actual hazard cost was COST. */
3000 HAIFA_INLINE
static int
3001 actual_hazard (unit
, insn
, clock
, cost
)
3002 int unit
, clock
, cost
;
3009 /* Find the instance of the function unit with the minimum hazard. */
3010 int instance
= unit
;
3011 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3015 #if MAX_MULTIPLICITY > 1
3016 if (best_cost
> cost
)
3018 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
3020 instance
+= FUNCTION_UNITS_SIZE
;
3021 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
3023 if (this_cost
< best_cost
)
3025 best_cost
= this_cost
;
3026 if (this_cost
<= cost
)
3032 cost
= MAX (cost
, best_cost
);
3035 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3036 if ((unit
& 1) != 0)
3037 cost
= actual_hazard (i
, insn
, clock
, cost
);
3042 /* Return the potential hazard cost of executing an instruction on the
3043 units encoded by UNIT if the previous potential hazard cost was COST.
3044 An insn with a large blockage time is chosen in preference to one
3045 with a smaller time; an insn that uses a unit that is more likely
3046 to be used is chosen in preference to one with a unit that is less
3047 used. We are trying to minimize a subsequent actual hazard. */
3049 HAIFA_INLINE
static int
3050 potential_hazard (unit
, insn
, cost
)
3055 unsigned int minb
, maxb
;
3059 minb
= maxb
= function_units
[unit
].max_blockage
;
3062 if (function_units
[unit
].blockage_range_function
)
3064 maxb
= minb
= blockage_range (unit
, insn
);
3065 maxb
= MAX_BLOCKAGE_COST (maxb
);
3066 minb
= MIN_BLOCKAGE_COST (minb
);
3071 /* Make the number of instructions left dominate. Make the
3072 minimum delay dominate the maximum delay. If all these
3073 are the same, use the unit number to add an arbitrary
3074 ordering. Other terms can be added. */
3075 ncost
= minb
* 0x40 + maxb
;
3076 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3083 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3084 if ((unit
& 1) != 0)
3085 cost
= potential_hazard (i
, insn
, cost
);
3090 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3091 This is the number of cycles between instruction issue and
3092 instruction results. */
3094 HAIFA_INLINE
static int
3095 insn_cost (insn
, link
, used
)
3096 rtx insn
, link
, used
;
3098 register int cost
= INSN_COST (insn
);
3102 recog_memoized (insn
);
3104 /* A USE insn, or something else we don't need to understand.
3105 We can't pass these directly to result_ready_cost because it will
3106 trigger a fatal error for unrecognizable insns. */
3107 if (INSN_CODE (insn
) < 0)
3109 INSN_COST (insn
) = 1;
3114 cost
= result_ready_cost (insn
);
3119 INSN_COST (insn
) = cost
;
3123 /* in this case estimate cost without caring how insn is used. */
3124 if (link
== 0 && used
== 0)
3127 /* A USE insn should never require the value used to be computed. This
3128 allows the computation of a function's result and parameter values to
3129 overlap the return and call. */
3130 recog_memoized (used
);
3131 if (INSN_CODE (used
) < 0)
3132 LINK_COST_FREE (link
) = 1;
3134 /* If some dependencies vary the cost, compute the adjustment. Most
3135 commonly, the adjustment is complete: either the cost is ignored
3136 (in the case of an output- or anti-dependence), or the cost is
3137 unchanged. These values are cached in the link as LINK_COST_FREE
3138 and LINK_COST_ZERO. */
3140 if (LINK_COST_FREE (link
))
3143 else if (!LINK_COST_ZERO (link
))
3147 ADJUST_COST (used
, link
, insn
, ncost
);
3149 LINK_COST_FREE (link
) = ncost
= 1;
3151 LINK_COST_ZERO (link
) = 1;
3158 /* Compute the priority number for INSN. */
3167 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3170 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3172 if (INSN_DEPEND (insn
) == 0)
3173 this_priority
= insn_cost (insn
, 0, 0);
3175 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3180 if (RTX_INTEGRATED_P (link
))
3183 next
= XEXP (link
, 0);
3185 /* critical path is meaningful in block boundaries only */
3186 if (INSN_BLOCK (next
) != INSN_BLOCK (insn
))
3189 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3190 if (next_priority
> this_priority
)
3191 this_priority
= next_priority
;
3193 INSN_PRIORITY (insn
) = this_priority
;
3195 return this_priority
;
3199 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3200 them to the unused_*_list variables, so that they can be reused. */
3203 free_pending_lists ()
3205 if (current_nr_blocks
<= 1)
3207 free_list (&pending_read_insns
, &unused_insn_list
);
3208 free_list (&pending_write_insns
, &unused_insn_list
);
3209 free_list (&pending_read_mems
, &unused_expr_list
);
3210 free_list (&pending_write_mems
, &unused_expr_list
);
3214 /* interblock scheduling */
3217 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3219 free_list (&bb_pending_read_insns
[bb
], &unused_insn_list
);
3220 free_list (&bb_pending_write_insns
[bb
], &unused_insn_list
);
3221 free_list (&bb_pending_read_mems
[bb
], &unused_expr_list
);
3222 free_list (&bb_pending_write_mems
[bb
], &unused_expr_list
);
3227 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3228 The MEM is a memory reference contained within INSN, which we are saving
3229 so that we can do memory aliasing on it. */
3232 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3233 rtx
*insn_list
, *mem_list
, insn
, mem
;
3237 link
= alloc_INSN_LIST (insn
, *insn_list
);
3240 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3243 pending_lists_length
++;
3247 /* Make a dependency between every memory reference on the pending lists
3248 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3252 flush_pending_lists (insn
, only_write
)
3259 while (pending_read_insns
&& ! only_write
)
3261 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3263 link
= pending_read_insns
;
3264 pending_read_insns
= XEXP (pending_read_insns
, 1);
3265 XEXP (link
, 1) = unused_insn_list
;
3266 unused_insn_list
= link
;
3268 link
= pending_read_mems
;
3269 pending_read_mems
= XEXP (pending_read_mems
, 1);
3270 XEXP (link
, 1) = unused_expr_list
;
3271 unused_expr_list
= link
;
3273 while (pending_write_insns
)
3275 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3277 link
= pending_write_insns
;
3278 pending_write_insns
= XEXP (pending_write_insns
, 1);
3279 XEXP (link
, 1) = unused_insn_list
;
3280 unused_insn_list
= link
;
3282 link
= pending_write_mems
;
3283 pending_write_mems
= XEXP (pending_write_mems
, 1);
3284 XEXP (link
, 1) = unused_expr_list
;
3285 unused_expr_list
= link
;
3287 pending_lists_length
= 0;
3289 /* last_pending_memory_flush is now a list of insns */
3290 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3291 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3293 free_list (&last_pending_memory_flush
, &unused_insn_list
);
3294 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3297 /* Analyze a single SET or CLOBBER rtx, X, creating all dependencies generated
3298 by the write to the destination of X, and reads of everything mentioned. */
3301 sched_analyze_1 (x
, insn
)
3306 register rtx dest
= SET_DEST (x
);
3311 if (GET_CODE (dest
) == PARALLEL
3312 && GET_MODE (dest
) == BLKmode
)
3315 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3316 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3317 if (GET_CODE (x
) == SET
)
3318 sched_analyze_2 (SET_SRC (x
), insn
);
3322 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3323 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3325 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3327 /* The second and third arguments are values read by this insn. */
3328 sched_analyze_2 (XEXP (dest
, 1), insn
);
3329 sched_analyze_2 (XEXP (dest
, 2), insn
);
3331 dest
= SUBREG_REG (dest
);
3334 if (GET_CODE (dest
) == REG
)
3338 regno
= REGNO (dest
);
3340 /* A hard reg in a wide mode may really be multiple registers.
3341 If so, mark all of them just like the first. */
3342 if (regno
< FIRST_PSEUDO_REGISTER
)
3344 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3349 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3350 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3351 reg_last_uses
[regno
+ i
] = 0;
3353 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3354 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3356 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3358 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3359 /* Function calls clobber all call_used regs. */
3360 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3361 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3368 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3369 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3370 reg_last_uses
[regno
] = 0;
3372 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3373 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3375 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3377 /* Pseudos that are REG_EQUIV to something may be replaced
3378 by that during reloading. We need only add dependencies for
3379 the address in the REG_EQUIV note. */
3380 if (!reload_completed
3381 && reg_known_equiv_p
[regno
]
3382 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3383 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3385 /* Don't let it cross a call after scheduling if it doesn't
3386 already cross one. */
3388 if (REG_N_CALLS_CROSSED (regno
) == 0)
3389 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3390 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3393 else if (GET_CODE (dest
) == MEM
)
3395 /* Writing memory. */
3397 if (pending_lists_length
> 32)
3399 /* Flush all pending reads and writes to prevent the pending lists
3400 from getting any larger. Insn scheduling runs too slowly when
3401 these lists get long. The number 32 was chosen because it
3402 seems like a reasonable number. When compiling GCC with itself,
3403 this flush occurs 8 times for sparc, and 10 times for m88k using
3405 flush_pending_lists (insn
, 0);
3410 rtx pending
, pending_mem
;
3412 pending
= pending_read_insns
;
3413 pending_mem
= pending_read_mems
;
3416 /* If a dependency already exists, don't create a new one. */
3417 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3418 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3419 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3421 pending
= XEXP (pending
, 1);
3422 pending_mem
= XEXP (pending_mem
, 1);
3425 pending
= pending_write_insns
;
3426 pending_mem
= pending_write_mems
;
3429 /* If a dependency already exists, don't create a new one. */
3430 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3431 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3432 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3434 pending
= XEXP (pending
, 1);
3435 pending_mem
= XEXP (pending_mem
, 1);
3438 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3439 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3441 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3444 sched_analyze_2 (XEXP (dest
, 0), insn
);
3447 /* Analyze reads. */
3448 if (GET_CODE (x
) == SET
)
3449 sched_analyze_2 (SET_SRC (x
), insn
);
3452 /* Analyze the uses of memory and registers in rtx X in INSN. */
3455 sched_analyze_2 (x
, insn
)
3461 register enum rtx_code code
;
3467 code
= GET_CODE (x
);
3476 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3477 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3478 this does not mean that this insn is using cc0. */
3486 /* User of CC0 depends on immediately preceding insn. */
3487 SCHED_GROUP_P (insn
) = 1;
3489 /* There may be a note before this insn now, but all notes will
3490 be removed before we actually try to schedule the insns, so
3491 it won't cause a problem later. We must avoid it here though. */
3492 prev
= prev_nonnote_insn (insn
);
3494 /* Make a copy of all dependencies on the immediately previous insn,
3495 and add to this insn. This is so that all the dependencies will
3496 apply to the group. Remove an explicit dependence on this insn
3497 as SCHED_GROUP_P now represents it. */
3499 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3500 remove_dependence (insn
, prev
);
3502 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3503 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3512 int regno
= REGNO (x
);
3513 if (regno
< FIRST_PSEUDO_REGISTER
)
3517 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3520 reg_last_uses
[regno
+ i
]
3521 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3523 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3524 add_dependence (insn
, XEXP (u
, 0), 0);
3526 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3527 /* Function calls clobber all call_used regs. */
3528 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3529 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3534 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
, reg_last_uses
[regno
]);
3536 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3537 add_dependence (insn
, XEXP (u
, 0), 0);
3539 /* Pseudos that are REG_EQUIV to something may be replaced
3540 by that during reloading. We need only add dependencies for
3541 the address in the REG_EQUIV note. */
3542 if (!reload_completed
3543 && reg_known_equiv_p
[regno
]
3544 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3545 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3547 /* If the register does not already cross any calls, then add this
3548 insn to the sched_before_next_call list so that it will still
3549 not cross calls after scheduling. */
3550 if (REG_N_CALLS_CROSSED (regno
) == 0)
3551 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3558 /* Reading memory. */
3560 rtx pending
, pending_mem
;
3562 pending
= pending_read_insns
;
3563 pending_mem
= pending_read_mems
;
3566 /* If a dependency already exists, don't create a new one. */
3567 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3568 if (read_dependence (XEXP (pending_mem
, 0), x
))
3569 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3571 pending
= XEXP (pending
, 1);
3572 pending_mem
= XEXP (pending_mem
, 1);
3575 pending
= pending_write_insns
;
3576 pending_mem
= pending_write_mems
;
3579 /* If a dependency already exists, don't create a new one. */
3580 if (!find_insn_list (XEXP (pending
, 0), LOG_LINKS (insn
)))
3581 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3583 add_dependence (insn
, XEXP (pending
, 0), 0);
3585 pending
= XEXP (pending
, 1);
3586 pending_mem
= XEXP (pending_mem
, 1);
3589 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3590 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3592 /* Always add these dependencies to pending_reads, since
3593 this insn may be followed by a write. */
3594 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3597 /* Take advantage of tail recursion here. */
3598 sched_analyze_2 (XEXP (x
, 0), insn
);
3602 /* Force pending stores to memory in case a trap handler needs them. */
3604 flush_pending_lists (insn
, 1);
3609 case UNSPEC_VOLATILE
:
3613 /* Traditional and volatile asm instructions must be considered to use
3614 and clobber all hard registers, all pseudo-registers and all of
3615 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3617 Consider for instance a volatile asm that changes the fpu rounding
3618 mode. An insn should not be moved across this even if it only uses
3619 pseudo-regs because it might give an incorrectly rounded result. */
3620 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3622 int max_reg
= max_reg_num ();
3623 for (i
= 0; i
< max_reg
; i
++)
3625 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3626 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3627 reg_last_uses
[i
] = 0;
3629 /* reg_last_sets[r] is now a list of insns */
3630 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3631 add_dependence (insn
, XEXP (u
, 0), 0);
3633 reg_pending_sets_all
= 1;
3635 flush_pending_lists (insn
, 0);
3638 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3639 We can not just fall through here since then we would be confused
3640 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3641 traditional asms unlike their normal usage. */
3643 if (code
== ASM_OPERANDS
)
3645 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3646 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3656 /* These both read and modify the result. We must handle them as writes
3657 to get proper dependencies for following instructions. We must handle
3658 them as reads to get proper dependencies from this to previous
3659 instructions. Thus we need to pass them to both sched_analyze_1
3660 and sched_analyze_2. We must call sched_analyze_2 first in order
3661 to get the proper antecedent for the read. */
3662 sched_analyze_2 (XEXP (x
, 0), insn
);
3663 sched_analyze_1 (x
, insn
);
3670 /* Other cases: walk the insn. */
3671 fmt
= GET_RTX_FORMAT (code
);
3672 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3675 sched_analyze_2 (XEXP (x
, i
), insn
);
3676 else if (fmt
[i
] == 'E')
3677 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3678 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3682 /* Analyze an INSN with pattern X to find all dependencies. */
3685 sched_analyze_insn (x
, insn
, loop_notes
)
3689 register RTX_CODE code
= GET_CODE (x
);
3691 int maxreg
= max_reg_num ();
3694 if (code
== SET
|| code
== CLOBBER
)
3695 sched_analyze_1 (x
, insn
);
3696 else if (code
== PARALLEL
)
3699 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3701 code
= GET_CODE (XVECEXP (x
, 0, i
));
3702 if (code
== SET
|| code
== CLOBBER
)
3703 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3705 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3709 sched_analyze_2 (x
, insn
);
3711 /* Mark registers CLOBBERED or used by called function. */
3712 if (GET_CODE (insn
) == CALL_INSN
)
3713 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3715 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3716 sched_analyze_1 (XEXP (link
, 0), insn
);
3718 sched_analyze_2 (XEXP (link
, 0), insn
);
3721 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3722 block, then we must be sure that no instructions are scheduled across it.
3723 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3724 become incorrect. */
3728 int max_reg
= max_reg_num ();
3729 int schedule_barrier_found
= 0;
3732 /* Update loop_notes with any notes from this insn. Also determine
3733 if any of the notes on the list correspond to instruction scheduling
3734 barriers (loop, eh & setjmp notes, but not range notes. */
3736 while (XEXP (link
, 1))
3738 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3739 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3740 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3741 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3742 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3743 schedule_barrier_found
= 1;
3745 link
= XEXP (link
, 1);
3747 XEXP (link
, 1) = REG_NOTES (insn
);
3748 REG_NOTES (insn
) = loop_notes
;
3750 /* Add dependencies if a scheduling barrier was found. */
3751 if (schedule_barrier_found
)
3753 for (i
= 0; i
< max_reg
; i
++)
3756 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3757 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3758 reg_last_uses
[i
] = 0;
3760 /* reg_last_sets[r] is now a list of insns */
3761 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3762 add_dependence (insn
, XEXP (u
, 0), 0);
3764 reg_pending_sets_all
= 1;
3766 flush_pending_lists (insn
, 0);
3771 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3773 /* reg_last_sets[r] is now a list of insns */
3774 free_list (®_last_sets
[i
], &unused_insn_list
);
3776 = alloc_INSN_LIST (insn
, NULL_RTX
);
3778 CLEAR_REG_SET (reg_pending_sets
);
3780 if (reg_pending_sets_all
)
3782 for (i
= 0; i
< maxreg
; i
++)
3784 /* reg_last_sets[r] is now a list of insns */
3785 free_list (®_last_sets
[i
], &unused_insn_list
);
3786 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3789 reg_pending_sets_all
= 0;
3792 /* Handle function calls and function returns created by the epilogue
3794 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3799 /* When scheduling instructions, we make sure calls don't lose their
3800 accompanying USE insns by depending them one on another in order.
3802 Also, we must do the same thing for returns created by the epilogue
3803 threading code. Note this code works only in this special case,
3804 because other passes make no guarantee that they will never emit
3805 an instruction between a USE and a RETURN. There is such a guarantee
3806 for USE instructions immediately before a call. */
3808 prev_dep_insn
= insn
;
3809 dep_insn
= PREV_INSN (insn
);
3810 while (GET_CODE (dep_insn
) == INSN
3811 && GET_CODE (PATTERN (dep_insn
)) == USE
3812 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3814 SCHED_GROUP_P (prev_dep_insn
) = 1;
3816 /* Make a copy of all dependencies on dep_insn, and add to insn.
3817 This is so that all of the dependencies will apply to the
3820 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3821 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3823 prev_dep_insn
= dep_insn
;
3824 dep_insn
= PREV_INSN (dep_insn
);
3829 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3830 for every dependency. */
3833 sched_analyze (head
, tail
)
3840 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3842 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3844 /* Make each JUMP_INSN a scheduling barrier for memory references. */
3845 if (GET_CODE (insn
) == JUMP_INSN
)
3846 last_pending_memory_flush
3847 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3848 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3851 else if (GET_CODE (insn
) == CALL_INSN
)
3856 CANT_MOVE (insn
) = 1;
3858 /* Any instruction using a hard register which may get clobbered
3859 by a call needs to be marked as dependent on this call.
3860 This prevents a use of a hard return reg from being moved
3861 past a void call (i.e. it does not explicitly set the hard
3864 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3865 all registers, not just hard registers, may be clobbered by this
3868 /* Insn, being a CALL_INSN, magically depends on
3869 `last_function_call' already. */
3871 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3872 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3874 int max_reg
= max_reg_num ();
3875 for (i
= 0; i
< max_reg
; i
++)
3877 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3878 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3880 reg_last_uses
[i
] = 0;
3882 /* reg_last_sets[r] is now a list of insns */
3883 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3884 add_dependence (insn
, XEXP (u
, 0), 0);
3886 reg_pending_sets_all
= 1;
3888 /* Add a pair of fake REG_NOTE which we will later
3889 convert back into a NOTE_INSN_SETJMP note. See
3890 reemit_notes for why we use a pair of NOTEs. */
3891 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3894 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_DEAD
,
3895 GEN_INT (NOTE_INSN_SETJMP
),
3900 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3901 if (call_used_regs
[i
] || global_regs
[i
])
3903 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3904 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3905 reg_last_uses
[i
] = 0;
3907 /* reg_last_sets[r] is now a list of insns */
3908 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3909 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3911 SET_REGNO_REG_SET (reg_pending_sets
, i
);
3915 /* For each insn which shouldn't cross a call, add a dependence
3916 between that insn and this call insn. */
3917 x
= LOG_LINKS (sched_before_next_call
);
3920 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3923 LOG_LINKS (sched_before_next_call
) = 0;
3925 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3928 /* In the absence of interprocedural alias analysis, we must flush
3929 all pending reads and writes, and start new dependencies starting
3930 from here. But only flush writes for constant calls (which may
3931 be passed a pointer to something we haven't written yet). */
3932 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3934 /* Depend this function call (actually, the user of this
3935 function call) on all hard register clobberage. */
3937 /* last_function_call is now a list of insns */
3938 free_list(&last_function_call
, &unused_insn_list
);
3939 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3942 /* See comments on reemit_notes as to why we do this. */
3943 /* ??? Actually, the reemit_notes just say what is done, not why. */
3945 else if (GET_CODE (insn
) == NOTE
3946 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3947 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3949 loop_notes
= alloc_EXPR_LIST (REG_DEAD
, NOTE_RANGE_INFO (insn
),
3951 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3952 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3955 else if (GET_CODE (insn
) == NOTE
3956 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3957 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3958 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3959 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3960 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3961 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3963 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3964 GEN_INT (NOTE_BLOCK_NUMBER (insn
)),
3966 loop_notes
= alloc_EXPR_LIST (REG_DEAD
,
3967 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3969 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3978 /* Called when we see a set of a register. If death is true, then we are
3979 scanning backwards. Mark that register as unborn. If nobody says
3980 otherwise, that is how things will remain. If death is false, then we
3981 are scanning forwards. Mark that register as being born. */
3984 sched_note_set (x
, death
)
3989 register rtx reg
= SET_DEST (x
);
3995 if (GET_CODE (reg
) == PARALLEL
3996 && GET_MODE (reg
) == BLKmode
)
3999 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
4000 sched_note_set (XVECEXP (reg
, 0, i
), death
);
4004 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == STRICT_LOW_PART
4005 || GET_CODE (reg
) == SIGN_EXTRACT
|| GET_CODE (reg
) == ZERO_EXTRACT
)
4007 /* Must treat modification of just one hardware register of a multi-reg
4008 value or just a byte field of a register exactly the same way that
4009 mark_set_1 in flow.c does, i.e. anything except a paradoxical subreg
4010 does not kill the entire register. */
4011 if (GET_CODE (reg
) != SUBREG
4012 || REG_SIZE (SUBREG_REG (reg
)) > REG_SIZE (reg
))
4015 reg
= SUBREG_REG (reg
);
4018 if (GET_CODE (reg
) != REG
)
4021 /* Global registers are always live, so the code below does not apply
4024 regno
= REGNO (reg
);
4025 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
4029 /* If we only set part of the register, then this set does not
4034 /* Try killing this register. */
4035 if (regno
< FIRST_PSEUDO_REGISTER
)
4037 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4040 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4045 /* Recompute REG_BASIC_BLOCK as we update all the other
4046 dataflow information. */
4047 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4048 sched_reg_basic_block
[regno
] = current_block_num
;
4049 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4050 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4052 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
4057 /* Make the register live again. */
4058 if (regno
< FIRST_PSEUDO_REGISTER
)
4060 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
4063 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4068 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4074 /* Macros and functions for keeping the priority queue sorted, and
4075 dealing with queueing and dequeueing of instructions. */
4077 #define SCHED_SORT(READY, N_READY) \
4078 do { if ((N_READY) == 2) \
4079 swap_sort (READY, N_READY); \
4080 else if ((N_READY) > 2) \
4081 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
4084 /* Returns a positive value if x is preferred; returns a negative value if
4085 y is preferred. Should never return 0, since that will make the sort
4089 rank_for_schedule (x
, y
)
4090 const GENERIC_PTR x
;
4091 const GENERIC_PTR y
;
4093 rtx tmp
= *(rtx
*)y
;
4094 rtx tmp2
= *(rtx
*)x
;
4096 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
4097 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
4100 /* prefer insn with higher priority */
4101 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
4103 return priority_val
;
4105 /* prefer an insn with smaller contribution to registers-pressure */
4106 if (!reload_completed
&&
4107 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4108 return (weight_val
);
4110 /* some comparison make sense in interblock scheduling only */
4111 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4113 /* prefer an inblock motion on an interblock motion */
4114 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4116 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4119 /* prefer a useful motion on a speculative one */
4120 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4123 /* prefer a more probable (speculative) insn */
4124 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4129 /* compare insns based on their relation to the last-scheduled-insn */
4130 if (last_scheduled_insn
)
4132 /* Classify the instructions into three classes:
4133 1) Data dependent on last schedule insn.
4134 2) Anti/Output dependent on last scheduled insn.
4135 3) Independent of last scheduled insn, or has latency of one.
4136 Choose the insn from the highest numbered class if different. */
4137 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4138 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4140 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4145 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4146 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4148 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4153 if ((val
= tmp2_class
- tmp_class
))
4157 /* Prefer the insn which has more later insns that depend on it.
4158 This gives the scheduler more freedom when scheduling later
4159 instructions at the expense of added register pressure. */
4161 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4165 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4168 val
= depend_count2
- depend_count1
;
4172 /* If insns are equally good, sort by INSN_LUID (original insn order),
4173 so that we make the sort stable. This minimizes instruction movement,
4174 thus minimizing sched's effect on debugging and cross-jumping. */
4175 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4178 /* Resort the array A in which only element at index N may be out of order. */
4180 HAIFA_INLINE
static void
4185 rtx insn
= a
[n
- 1];
4188 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4196 static int max_priority
;
4198 /* Add INSN to the insn queue so that it can be executed at least
4199 N_CYCLES after the currently executing insn. Preserve insns
4200 chain for debugging purposes. */
4202 HAIFA_INLINE
static void
4203 queue_insn (insn
, n_cycles
)
4207 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4208 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4209 insn_queue
[next_q
] = link
;
4212 if (sched_verbose
>= 2)
4214 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4216 if (INSN_BB (insn
) != target_bb
)
4217 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
4219 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4224 /* Return nonzero if PAT is the pattern of an insn which makes a
4227 HAIFA_INLINE
static int
4228 birthing_insn_p (pat
)
4233 if (reload_completed
== 1)
4236 if (GET_CODE (pat
) == SET
4237 && (GET_CODE (SET_DEST (pat
)) == REG
4238 || (GET_CODE (SET_DEST (pat
)) == PARALLEL
4239 && GET_MODE (SET_DEST (pat
)) == BLKmode
)))
4241 rtx dest
= SET_DEST (pat
);
4244 /* It would be more accurate to use refers_to_regno_p or
4245 reg_mentioned_p to determine when the dest is not live before this
4247 if (GET_CODE (dest
) == REG
)
4250 if (REGNO_REG_SET_P (bb_live_regs
, i
))
4251 return (REG_N_SETS (i
) == 1);
4255 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
4257 int regno
= REGNO (SET_DEST (XVECEXP (dest
, 0, i
)));
4258 if (REGNO_REG_SET_P (bb_live_regs
, regno
))
4259 return (REG_N_SETS (regno
) == 1);
4264 if (GET_CODE (pat
) == PARALLEL
)
4266 for (j
= 0; j
< XVECLEN (pat
, 0); j
++)
4267 if (birthing_insn_p (XVECEXP (pat
, 0, j
)))
4273 /* PREV is an insn that is ready to execute. Adjust its priority if that
4274 will help shorten register lifetimes. */
4276 HAIFA_INLINE
static void
4277 adjust_priority (prev
)
4280 /* Trying to shorten register lives after reload has completed
4281 is useless and wrong. It gives inaccurate schedules. */
4282 if (reload_completed
== 0)
4287 /* ??? This code has no effect, because REG_DEAD notes are removed
4288 before we ever get here. */
4289 for (note
= REG_NOTES (prev
); note
; note
= XEXP (note
, 1))
4290 if (REG_NOTE_KIND (note
) == REG_DEAD
)
4293 /* Defer scheduling insns which kill registers, since that
4294 shortens register lives. Prefer scheduling insns which
4295 make registers live for the same reason. */
4299 INSN_PRIORITY (prev
) >>= 3;
4302 INSN_PRIORITY (prev
) >>= 2;
4306 INSN_PRIORITY (prev
) >>= 1;
4309 if (birthing_insn_p (PATTERN (prev
)))
4311 int max
= max_priority
;
4313 if (max
> INSN_PRIORITY (prev
))
4314 INSN_PRIORITY (prev
) = max
;
4318 #ifdef ADJUST_PRIORITY
4319 ADJUST_PRIORITY (prev
);
4324 /* Clock at which the previous instruction was issued. */
4325 static int last_clock_var
;
4327 /* INSN is the "currently executing insn". Launch each insn which was
4328 waiting on INSN. READY is a vector of insns which are ready to fire.
4329 N_READY is the number of elements in READY. CLOCK is the current
4333 schedule_insn (insn
, ready
, n_ready
, clock
)
4342 unit
= insn_unit (insn
);
4344 if (sched_verbose
>= 2)
4346 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ", INSN_UID (insn
));
4347 insn_print_units (insn
);
4348 fprintf (dump
, "\n");
4351 if (sched_verbose
&& unit
== -1)
4352 visualize_no_unit (insn
);
4354 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4355 schedule_unit (unit
, insn
, clock
);
4357 if (INSN_DEPEND (insn
) == 0)
4360 /* This is used by the function adjust_priority above. */
4362 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4364 max_priority
= INSN_PRIORITY (insn
);
4366 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4368 rtx next
= XEXP (link
, 0);
4369 int cost
= insn_cost (insn
, link
, next
);
4371 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4373 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4375 int effective_cost
= INSN_TICK (next
) - clock
;
4377 /* For speculative insns, before inserting to ready/queue,
4378 check live, exception-free, and issue-delay */
4379 if (INSN_BB (next
) != target_bb
4380 && (!IS_VALID (INSN_BB (next
))
4382 || (IS_SPECULATIVE_INSN (next
)
4383 && (insn_issue_delay (next
) > 3
4384 || !check_live (next
, INSN_BB (next
))
4385 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4388 if (sched_verbose
>= 2)
4390 fprintf (dump
, ";;\t\tdependences resolved: insn %d ", INSN_UID (next
));
4392 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4393 fprintf (dump
, "/b%d ", INSN_BLOCK (next
));
4395 if (effective_cost
<= 1)
4396 fprintf (dump
, "into ready\n");
4398 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4401 /* Adjust the priority of NEXT and either put it on the ready
4402 list or queue it. */
4403 adjust_priority (next
);
4404 if (effective_cost
<= 1)
4405 ready
[n_ready
++] = next
;
4407 queue_insn (next
, effective_cost
);
4411 /* Annotate the instruction with issue information -- TImode
4412 indicates that the instruction is expected not to be able
4413 to issue on the same cycle as the previous insn. A machine
4414 may use this information to decide how the instruction should
4416 if (reload_completed
&& issue_rate
> 1)
4418 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4419 last_clock_var
= clock
;
4426 /* Add a REG_DEAD note for REG to INSN, reusing a REG_DEAD note from the
4430 create_reg_dead_note (reg
, insn
)
4435 /* The number of registers killed after scheduling must be the same as the
4436 number of registers killed before scheduling. The number of REG_DEAD
4437 notes may not be conserved, i.e. two SImode hard register REG_DEAD notes
4438 might become one DImode hard register REG_DEAD note, but the number of
4439 registers killed will be conserved.
4441 We carefully remove REG_DEAD notes from the dead_notes list, so that
4442 there will be none left at the end. If we run out early, then there
4443 is a bug somewhere in flow, combine and/or sched. */
4445 if (dead_notes
== 0)
4447 if (current_nr_blocks
<= 1)
4450 link
= alloc_EXPR_LIST (REG_DEAD
, NULL_RTX
, NULL_RTX
);
4454 /* Number of regs killed by REG. */
4455 int regs_killed
= (REGNO (reg
) >= FIRST_PSEUDO_REGISTER
? 1
4456 : HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
)));
4457 /* Number of regs killed by REG_DEAD notes taken off the list. */
4461 reg_note_regs
= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4462 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4463 GET_MODE (XEXP (link
, 0))));
4464 while (reg_note_regs
< regs_killed
)
4466 link
= XEXP (link
, 1);
4468 /* LINK might be zero if we killed more registers after scheduling
4469 than before, and the last hard register we kill is actually
4472 This is normal for interblock scheduling, so deal with it in
4473 that case, else abort. */
4474 if (link
== NULL_RTX
&& current_nr_blocks
<= 1)
4476 else if (link
== NULL_RTX
)
4477 link
= alloc_EXPR_LIST (REG_DEAD
, gen_rtx_REG (word_mode
, 0),
4480 reg_note_regs
+= (REGNO (XEXP (link
, 0)) >= FIRST_PSEUDO_REGISTER
? 1
4481 : HARD_REGNO_NREGS (REGNO (XEXP (link
, 0)),
4482 GET_MODE (XEXP (link
, 0))));
4484 dead_notes
= XEXP (link
, 1);
4486 /* If we took too many regs kills off, put the extra ones back. */
4487 while (reg_note_regs
> regs_killed
)
4489 rtx temp_reg
, temp_link
;
4491 temp_reg
= gen_rtx_REG (word_mode
, 0);
4492 temp_link
= alloc_EXPR_LIST (REG_DEAD
, temp_reg
, dead_notes
);
4493 dead_notes
= temp_link
;
4498 XEXP (link
, 0) = reg
;
4499 XEXP (link
, 1) = REG_NOTES (insn
);
4500 REG_NOTES (insn
) = link
;
4503 /* Subroutine on attach_deaths_insn--handles the recursive search
4504 through INSN. If SET_P is true, then x is being modified by the insn. */
4507 attach_deaths (x
, insn
, set_p
)
4514 register enum rtx_code code
;
4520 code
= GET_CODE (x
);
4532 /* Get rid of the easy cases first. */
4537 /* If the register dies in this insn, queue that note, and mark
4538 this register as needing to die. */
4539 /* This code is very similar to mark_used_1 (if set_p is false)
4540 and mark_set_1 (if set_p is true) in flow.c. */
4550 all_needed
= some_needed
= REGNO_REG_SET_P (old_live_regs
, regno
);
4551 if (regno
< FIRST_PSEUDO_REGISTER
)
4555 n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4558 int needed
= (REGNO_REG_SET_P (old_live_regs
, regno
+ n
));
4559 some_needed
|= needed
;
4560 all_needed
&= needed
;
4564 /* If it wasn't live before we started, then add a REG_DEAD note.
4565 We must check the previous lifetime info not the current info,
4566 because we may have to execute this code several times, e.g.
4567 once for a clobber (which doesn't add a note) and later
4568 for a use (which does add a note).
4570 Always make the register live. We must do this even if it was
4571 live before, because this may be an insn which sets and uses
4572 the same register, in which case the register has already been
4573 killed, so we must make it live again.
4575 Global registers are always live, and should never have a REG_DEAD
4576 note added for them, so none of the code below applies to them. */
4578 if (regno
>= FIRST_PSEUDO_REGISTER
|| ! global_regs
[regno
])
4580 /* Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
4581 STACK_POINTER_REGNUM, since these are always considered to be
4582 live. Similarly for ARG_POINTER_REGNUM if it is fixed. */
4583 if (regno
!= FRAME_POINTER_REGNUM
4584 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
4585 && ! (regno
== HARD_FRAME_POINTER_REGNUM
)
4587 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
4588 && ! (regno
== ARG_POINTER_REGNUM
&& fixed_regs
[regno
])
4590 && regno
!= STACK_POINTER_REGNUM
)
4592 if (! all_needed
&& ! dead_or_set_p (insn
, x
))
4594 /* Check for the case where the register dying partially
4595 overlaps the register set by this insn. */
4596 if (regno
< FIRST_PSEUDO_REGISTER
4597 && HARD_REGNO_NREGS (regno
, GET_MODE (x
)) > 1)
4599 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4601 some_needed
|= dead_or_set_regno_p (insn
, regno
+ n
);
4604 /* If none of the words in X is needed, make a REG_DEAD
4605 note. Otherwise, we must make partial REG_DEAD
4608 create_reg_dead_note (x
, insn
);
4613 /* Don't make a REG_DEAD note for a part of a
4614 register that is set in the insn. */
4615 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1;
4617 if (! REGNO_REG_SET_P (old_live_regs
, regno
+i
)
4618 && ! dead_or_set_regno_p (insn
, regno
+ i
))
4619 create_reg_dead_note (gen_rtx_REG (reg_raw_mode
[regno
+ i
],
4626 if (regno
< FIRST_PSEUDO_REGISTER
)
4628 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
4631 SET_REGNO_REG_SET (bb_live_regs
, regno
+ j
);
4636 /* Recompute REG_BASIC_BLOCK as we update all the other
4637 dataflow information. */
4638 if (sched_reg_basic_block
[regno
] == REG_BLOCK_UNKNOWN
)
4639 sched_reg_basic_block
[regno
] = current_block_num
;
4640 else if (sched_reg_basic_block
[regno
] != current_block_num
)
4641 sched_reg_basic_block
[regno
] = REG_BLOCK_GLOBAL
;
4643 SET_REGNO_REG_SET (bb_live_regs
, regno
);
4650 /* Handle tail-recursive case. */
4651 attach_deaths (XEXP (x
, 0), insn
, 0);
4655 attach_deaths (SUBREG_REG (x
), insn
,
4656 set_p
&& ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4658 || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)))
4659 == GET_MODE_SIZE (GET_MODE ((x
))))));
4662 case STRICT_LOW_PART
:
4663 attach_deaths (XEXP (x
, 0), insn
, 0);
4668 attach_deaths (XEXP (x
, 0), insn
, 0);
4669 attach_deaths (XEXP (x
, 1), insn
, 0);
4670 attach_deaths (XEXP (x
, 2), insn
, 0);
4675 && GET_MODE (x
) == BLKmode
)
4677 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4678 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4684 /* Other cases: walk the insn. */
4685 fmt
= GET_RTX_FORMAT (code
);
4686 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4689 attach_deaths (XEXP (x
, i
), insn
, 0);
4690 else if (fmt
[i
] == 'E')
4691 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
4692 attach_deaths (XVECEXP (x
, i
, j
), insn
, 0);
4697 /* After INSN has executed, add register death notes for each register
4698 that is dead after INSN. */
4701 attach_deaths_insn (insn
)
4704 rtx x
= PATTERN (insn
);
4705 register RTX_CODE code
= GET_CODE (x
);
4710 attach_deaths (SET_SRC (x
), insn
, 0);
4712 /* A register might die here even if it is the destination, e.g.
4713 it is the target of a volatile read and is otherwise unused.
4714 Hence we must always call attach_deaths for the SET_DEST. */
4715 attach_deaths (SET_DEST (x
), insn
, 1);
4717 else if (code
== PARALLEL
)
4720 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
4722 code
= GET_CODE (XVECEXP (x
, 0, i
));
4725 attach_deaths (SET_SRC (XVECEXP (x
, 0, i
)), insn
, 0);
4727 attach_deaths (SET_DEST (XVECEXP (x
, 0, i
)), insn
, 1);
4729 /* Flow does not add REG_DEAD notes to registers that die in
4730 clobbers, so we can't either. */
4731 else if (code
!= CLOBBER
)
4732 attach_deaths (XVECEXP (x
, 0, i
), insn
, 0);
4735 /* If this is a CLOBBER, only add REG_DEAD notes to registers inside a
4736 MEM being clobbered, just like flow. */
4737 else if (code
== CLOBBER
&& GET_CODE (XEXP (x
, 0)) == MEM
)
4738 attach_deaths (XEXP (XEXP (x
, 0), 0), insn
, 0);
4739 /* Otherwise don't add a death note to things being clobbered. */
4740 else if (code
!= CLOBBER
)
4741 attach_deaths (x
, insn
, 0);
4743 /* Make death notes for things used in the called function. */
4744 if (GET_CODE (insn
) == CALL_INSN
)
4745 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
4746 attach_deaths (XEXP (XEXP (link
, 0), 0), insn
,
4747 GET_CODE (XEXP (link
, 0)) == CLOBBER
);
4750 /* functions for handlnig of notes */
4752 /* Delete notes beginning with INSN and put them in the chain
4753 of notes ended by NOTE_LIST.
4754 Returns the insn following the notes. */
4757 unlink_other_notes (insn
, tail
)
4760 rtx prev
= PREV_INSN (insn
);
4762 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4764 rtx next
= NEXT_INSN (insn
);
4765 /* Delete the note from its current position. */
4767 NEXT_INSN (prev
) = next
;
4769 PREV_INSN (next
) = prev
;
4771 /* Don't save away NOTE_INSN_SETJMPs, because they must remain
4772 immediately after the call they follow. We use a fake
4773 (REG_DEAD (const_int -1)) note to remember them.
4774 Likewise with NOTE_INSN_{LOOP,EHREGION}_{BEG, END}. */
4775 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4776 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4777 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4778 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4779 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4780 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4781 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4783 /* Insert the note at the end of the notes list. */
4784 PREV_INSN (insn
) = note_list
;
4786 NEXT_INSN (note_list
) = insn
;
4795 /* Delete line notes beginning with INSN. Record line-number notes so
4796 they can be reused. Returns the insn following the notes. */
4799 unlink_line_notes (insn
, tail
)
4802 rtx prev
= PREV_INSN (insn
);
4804 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4806 rtx next
= NEXT_INSN (insn
);
4808 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4810 /* Delete the note from its current position. */
4812 NEXT_INSN (prev
) = next
;
4814 PREV_INSN (next
) = prev
;
4816 /* Record line-number notes so they can be reused. */
4817 LINE_NOTE (insn
) = insn
;
4827 /* Return the head and tail pointers of BB. */
4829 HAIFA_INLINE
static void
4830 get_block_head_tail (bb
, headp
, tailp
)
4840 b
= BB_TO_BLOCK (bb
);
4842 /* HEAD and TAIL delimit the basic block being scheduled. */
4843 head
= BLOCK_HEAD (b
);
4844 tail
= BLOCK_END (b
);
4846 /* Don't include any notes or labels at the beginning of the
4847 basic block, or notes at the ends of basic blocks. */
4848 while (head
!= tail
)
4850 if (GET_CODE (head
) == NOTE
)
4851 head
= NEXT_INSN (head
);
4852 else if (GET_CODE (tail
) == NOTE
)
4853 tail
= PREV_INSN (tail
);
4854 else if (GET_CODE (head
) == CODE_LABEL
)
4855 head
= NEXT_INSN (head
);
4864 /* Delete line notes from bb. Save them so they can be later restored
4865 (in restore_line_notes ()). */
4876 get_block_head_tail (bb
, &head
, &tail
);
4879 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4882 next_tail
= NEXT_INSN (tail
);
4883 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4887 /* Farm out notes, and maybe save them in NOTE_LIST.
4888 This is needed to keep the debugger from
4889 getting completely deranged. */
4890 if (GET_CODE (insn
) == NOTE
)
4893 insn
= unlink_line_notes (insn
, next_tail
);
4899 if (insn
== next_tail
)
4905 /* Save line number notes for each insn in bb. */
4908 save_line_notes (bb
)
4914 /* We must use the true line number for the first insn in the block
4915 that was computed and saved at the start of this pass. We can't
4916 use the current line number, because scheduling of the previous
4917 block may have changed the current line number. */
4919 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4922 get_block_head_tail (bb
, &head
, &tail
);
4923 next_tail
= NEXT_INSN (tail
);
4925 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4927 insn
= NEXT_INSN (insn
))
4928 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4931 LINE_NOTE (insn
) = line
;
4935 /* After bb was scheduled, insert line notes into the insns list. */
4938 restore_line_notes (bb
)
4941 rtx line
, note
, prev
, new;
4942 int added_notes
= 0;
4944 rtx head
, next_tail
, insn
;
4946 b
= BB_TO_BLOCK (bb
);
4948 head
= BLOCK_HEAD (b
);
4949 next_tail
= NEXT_INSN (BLOCK_END (b
));
4951 /* Determine the current line-number. We want to know the current
4952 line number of the first insn of the block here, in case it is
4953 different from the true line number that was saved earlier. If
4954 different, then we need a line number note before the first insn
4955 of this block. If it happens to be the same, then we don't want to
4956 emit another line number note here. */
4957 for (line
= head
; line
; line
= PREV_INSN (line
))
4958 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4961 /* Walk the insns keeping track of the current line-number and inserting
4962 the line-number notes as needed. */
4963 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4964 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4966 /* This used to emit line number notes before every non-deleted note.
4967 However, this confuses a debugger, because line notes not separated
4968 by real instructions all end up at the same address. I can find no
4969 use for line number notes before other notes, so none are emitted. */
4970 else if (GET_CODE (insn
) != NOTE
4971 && (note
= LINE_NOTE (insn
)) != 0
4974 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4975 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4978 prev
= PREV_INSN (insn
);
4979 if (LINE_NOTE (note
))
4981 /* Re-use the original line-number note. */
4982 LINE_NOTE (note
) = 0;
4983 PREV_INSN (note
) = prev
;
4984 NEXT_INSN (prev
) = note
;
4985 PREV_INSN (insn
) = note
;
4986 NEXT_INSN (note
) = insn
;
4991 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4992 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4993 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4996 if (sched_verbose
&& added_notes
)
4997 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
5000 /* After scheduling the function, delete redundant line notes from the
5004 rm_redundant_line_notes ()
5007 rtx insn
= get_insns ();
5008 int active_insn
= 0;
5011 /* Walk the insns deleting redundant line-number notes. Many of these
5012 are already present. The remainder tend to occur at basic
5013 block boundaries. */
5014 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5015 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
5017 /* If there are no active insns following, INSN is redundant. */
5018 if (active_insn
== 0)
5021 NOTE_SOURCE_FILE (insn
) = 0;
5022 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
5024 /* If the line number is unchanged, LINE is redundant. */
5026 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
5027 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
5030 NOTE_SOURCE_FILE (line
) = 0;
5031 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
5038 else if (!((GET_CODE (insn
) == NOTE
5039 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
5040 || (GET_CODE (insn
) == INSN
5041 && (GET_CODE (PATTERN (insn
)) == USE
5042 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
5045 if (sched_verbose
&& notes
)
5046 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
5049 /* Delete notes between head and tail and put them in the chain
5050 of notes ended by NOTE_LIST. */
5053 rm_other_notes (head
, tail
)
5061 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5064 next_tail
= NEXT_INSN (tail
);
5065 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5069 /* Farm out notes, and maybe save them in NOTE_LIST.
5070 This is needed to keep the debugger from
5071 getting completely deranged. */
5072 if (GET_CODE (insn
) == NOTE
)
5076 insn
= unlink_other_notes (insn
, next_tail
);
5082 if (insn
== next_tail
)
5088 /* Constructor for `sometimes' data structure. */
5091 new_sometimes_live (regs_sometimes_live
, regno
, sometimes_max
)
5092 struct sometimes
*regs_sometimes_live
;
5096 register struct sometimes
*p
;
5098 /* There should never be a register greater than max_regno here. If there
5099 is, it means that a define_split has created a new pseudo reg. This
5100 is not allowed, since there will not be flow info available for any
5101 new register, so catch the error here. */
5102 if (regno
>= max_regno
)
5105 p
= ®s_sometimes_live
[sometimes_max
];
5108 p
->calls_crossed
= 0;
5110 return sometimes_max
;
5113 /* Count lengths of all regs we are currently tracking,
5114 and find new registers no longer live. */
5117 finish_sometimes_live (regs_sometimes_live
, sometimes_max
)
5118 struct sometimes
*regs_sometimes_live
;
5123 for (i
= 0; i
< sometimes_max
; i
++)
5125 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5126 int regno
= p
->regno
;
5128 sched_reg_live_length
[regno
] += p
->live_length
;
5129 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5133 /* functions for computation of registers live/usage info */
5135 /* It is assumed that prior to scheduling basic_block_live_at_start (b)
5136 contains the registers that are alive at the entry to b.
5138 Two passes follow: The first pass is performed before the scheduling
5139 of a region. It scans each block of the region forward, computing
5140 the set of registers alive at the end of the basic block and
5141 discard REG_DEAD notes (done by find_pre_sched_live ()).
5143 The second path is invoked after scheduling all region blocks.
5144 It scans each block of the region backward, a block being traversed
5145 only after its succesors in the region. When the set of registers
5146 live at the end of a basic block may be changed by the scheduling
5147 (this may happen for multiple blocks region), it is computed as
5148 the union of the registers live at the start of its succesors.
5149 The last-use information is updated by inserting REG_DEAD notes.
5150 (done by find_post_sched_live ()) */
5152 /* Scan all the insns to be scheduled, removing register death notes.
5153 Register death notes end up in DEAD_NOTES.
5154 Recreate the register life information for the end of this basic
5158 find_pre_sched_live (bb
)
5161 rtx insn
, next_tail
, head
, tail
;
5162 int b
= BB_TO_BLOCK (bb
);
5164 get_block_head_tail (bb
, &head
, &tail
);
5165 COPY_REG_SET (bb_live_regs
, basic_block_live_at_start
[b
]);
5166 next_tail
= NEXT_INSN (tail
);
5168 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5170 rtx prev
, next
, link
;
5173 /* Handle register life information. */
5174 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
5176 /* See if the register gets born here. */
5177 /* We must check for registers being born before we check for
5178 registers dying. It is possible for a register to be born and
5179 die in the same insn, e.g. reading from a volatile memory
5180 location into an otherwise unused register. Such a register
5181 must be marked as dead after this insn. */
5182 if (GET_CODE (PATTERN (insn
)) == SET
5183 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5185 sched_note_set (PATTERN (insn
), 0);
5189 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5192 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5193 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5194 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5196 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5200 /* ??? This code is obsolete and should be deleted. It
5201 is harmless though, so we will leave it in for now. */
5202 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5203 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == USE
)
5204 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 0);
5207 /* Each call cobbers (makes live) all call-clobbered regs
5208 that are not global or fixed. Note that the function-value
5209 reg is a call_clobbered reg. */
5210 if (GET_CODE (insn
) == CALL_INSN
)
5213 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
5214 if (call_used_regs
[j
] && !global_regs
[j
]
5217 SET_REGNO_REG_SET (bb_live_regs
, j
);
5221 /* Need to know what registers this insn kills. */
5222 for (prev
= 0, link
= REG_NOTES (insn
); link
; link
= next
)
5224 next
= XEXP (link
, 1);
5225 if ((REG_NOTE_KIND (link
) == REG_DEAD
5226 || REG_NOTE_KIND (link
) == REG_UNUSED
)
5227 /* Verify that the REG_NOTE has a valid value. */
5228 && GET_CODE (XEXP (link
, 0)) == REG
)
5230 register int regno
= REGNO (XEXP (link
, 0));
5234 /* Only unlink REG_DEAD notes; leave REG_UNUSED notes
5236 if (REG_NOTE_KIND (link
) == REG_DEAD
)
5239 XEXP (prev
, 1) = next
;
5241 REG_NOTES (insn
) = next
;
5242 XEXP (link
, 1) = dead_notes
;
5248 if (regno
< FIRST_PSEUDO_REGISTER
)
5250 int j
= HARD_REGNO_NREGS (regno
,
5251 GET_MODE (XEXP (link
, 0)));
5254 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
+j
);
5259 CLEAR_REGNO_REG_SET (bb_live_regs
, regno
);
5267 INSN_REG_WEIGHT (insn
) = reg_weight
;
5271 /* Update register life and usage information for block bb
5272 after scheduling. Put register dead notes back in the code. */
5275 find_post_sched_live (bb
)
5282 rtx head
, tail
, prev_head
, next_tail
;
5284 register struct sometimes
*regs_sometimes_live
;
5286 b
= BB_TO_BLOCK (bb
);
5288 /* compute live regs at the end of bb as a function of its successors. */
5289 if (current_nr_blocks
> 1)
5294 first_edge
= e
= OUT_EDGES (b
);
5295 CLEAR_REG_SET (bb_live_regs
);
5302 b_succ
= TO_BLOCK (e
);
5303 IOR_REG_SET (bb_live_regs
, basic_block_live_at_start
[b_succ
]);
5306 while (e
!= first_edge
);
5309 get_block_head_tail (bb
, &head
, &tail
);
5310 next_tail
= NEXT_INSN (tail
);
5311 prev_head
= PREV_INSN (head
);
5313 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, i
,
5315 sched_reg_basic_block
[i
] = REG_BLOCK_GLOBAL
;
5318 /* if the block is empty, same regs are alive at its end and its start.
5319 since this is not guaranteed after interblock scheduling, make sure they
5320 are truly identical. */
5321 if (NEXT_INSN (prev_head
) == tail
5322 && (GET_RTX_CLASS (GET_CODE (tail
)) != 'i'))
5324 if (current_nr_blocks
> 1)
5325 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5330 b
= BB_TO_BLOCK (bb
);
5331 current_block_num
= b
;
5333 /* Keep track of register lives. */
5334 old_live_regs
= ALLOCA_REG_SET ();
5336 = (struct sometimes
*) alloca (max_regno
* sizeof (struct sometimes
));
5339 /* initiate "sometimes" data, starting with registers live at end */
5341 COPY_REG_SET (old_live_regs
, bb_live_regs
);
5342 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, 0, j
,
5345 = new_sometimes_live (regs_sometimes_live
,
5349 /* scan insns back, computing regs live info */
5350 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
5352 /* First we kill registers set by this insn, and then we
5353 make registers used by this insn live. This is the opposite
5354 order used above because we are traversing the instructions
5357 /* Strictly speaking, we should scan REG_UNUSED notes and make
5358 every register mentioned there live, however, we will just
5359 kill them again immediately below, so there doesn't seem to
5360 be any reason why we bother to do this. */
5362 /* See if this is the last notice we must take of a register. */
5363 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5366 if (GET_CODE (PATTERN (insn
)) == SET
5367 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
5368 sched_note_set (PATTERN (insn
), 1);
5369 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
5371 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
5372 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
5373 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
5374 sched_note_set (XVECEXP (PATTERN (insn
), 0, j
), 1);
5377 /* This code keeps life analysis information up to date. */
5378 if (GET_CODE (insn
) == CALL_INSN
)
5380 register struct sometimes
*p
;
5382 /* A call kills all call used registers that are not
5383 global or fixed, except for those mentioned in the call
5384 pattern which will be made live again later. */
5385 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5386 if (call_used_regs
[i
] && ! global_regs
[i
]
5389 CLEAR_REGNO_REG_SET (bb_live_regs
, i
);
5392 /* Regs live at the time of a call instruction must not
5393 go in a register clobbered by calls. Record this for
5394 all regs now live. Note that insns which are born or
5395 die in a call do not cross a call, so this must be done
5396 after the killings (above) and before the births
5398 p
= regs_sometimes_live
;
5399 for (i
= 0; i
< sometimes_max
; i
++, p
++)
5400 if (REGNO_REG_SET_P (bb_live_regs
, p
->regno
))
5401 p
->calls_crossed
+= 1;
5404 /* Make every register used live, and add REG_DEAD notes for
5405 registers which were not live before we started. */
5406 attach_deaths_insn (insn
);
5408 /* Find registers now made live by that instruction. */
5409 EXECUTE_IF_AND_COMPL_IN_REG_SET (bb_live_regs
, old_live_regs
, 0, j
,
5412 = new_sometimes_live (regs_sometimes_live
,
5415 IOR_REG_SET (old_live_regs
, bb_live_regs
);
5417 /* Count lengths of all regs we are worrying about now,
5418 and handle registers no longer live. */
5420 for (i
= 0; i
< sometimes_max
; i
++)
5422 register struct sometimes
*p
= ®s_sometimes_live
[i
];
5423 int regno
= p
->regno
;
5425 p
->live_length
+= 1;
5427 if (!REGNO_REG_SET_P (bb_live_regs
, regno
))
5429 /* This is the end of one of this register's lifetime
5430 segments. Save the lifetime info collected so far,
5431 and clear its bit in the old_live_regs entry. */
5432 sched_reg_live_length
[regno
] += p
->live_length
;
5433 sched_reg_n_calls_crossed
[regno
] += p
->calls_crossed
;
5434 CLEAR_REGNO_REG_SET (old_live_regs
, p
->regno
);
5436 /* Delete the reg_sometimes_live entry for this reg by
5437 copying the last entry over top of it. */
5438 *p
= regs_sometimes_live
[--sometimes_max
];
5439 /* ...and decrement i so that this newly copied entry
5440 will be processed. */
5446 finish_sometimes_live (regs_sometimes_live
, sometimes_max
);
5448 /* In interblock scheduling, basic_block_live_at_start may have changed. */
5449 if (current_nr_blocks
> 1)
5450 COPY_REG_SET (basic_block_live_at_start
[b
], bb_live_regs
);
5453 FREE_REG_SET (old_live_regs
);
5454 } /* find_post_sched_live */
5456 /* After scheduling the subroutine, restore information about uses of
5464 if (n_basic_blocks
> 0)
5465 EXECUTE_IF_SET_IN_REG_SET (bb_live_regs
, FIRST_PSEUDO_REGISTER
, regno
,
5467 sched_reg_basic_block
[regno
]
5471 for (regno
= 0; regno
< max_regno
; regno
++)
5472 if (sched_reg_live_length
[regno
])
5476 if (REG_LIVE_LENGTH (regno
) > sched_reg_live_length
[regno
])
5478 ";; register %d life shortened from %d to %d\n",
5479 regno
, REG_LIVE_LENGTH (regno
),
5480 sched_reg_live_length
[regno
]);
5481 /* Negative values are special; don't overwrite the current
5482 reg_live_length value if it is negative. */
5483 else if (REG_LIVE_LENGTH (regno
) < sched_reg_live_length
[regno
]
5484 && REG_LIVE_LENGTH (regno
) >= 0)
5486 ";; register %d life extended from %d to %d\n",
5487 regno
, REG_LIVE_LENGTH (regno
),
5488 sched_reg_live_length
[regno
]);
5490 if (!REG_N_CALLS_CROSSED (regno
)
5491 && sched_reg_n_calls_crossed
[regno
])
5493 ";; register %d now crosses calls\n", regno
);
5494 else if (REG_N_CALLS_CROSSED (regno
)
5495 && !sched_reg_n_calls_crossed
[regno
]
5496 && REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5498 ";; register %d no longer crosses calls\n", regno
);
5500 if (REG_BASIC_BLOCK (regno
) != sched_reg_basic_block
[regno
]
5501 && sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5502 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5504 ";; register %d changed basic block from %d to %d\n",
5505 regno
, REG_BASIC_BLOCK(regno
),
5506 sched_reg_basic_block
[regno
]);
5509 /* Negative values are special; don't overwrite the current
5510 reg_live_length value if it is negative. */
5511 if (REG_LIVE_LENGTH (regno
) >= 0)
5512 REG_LIVE_LENGTH (regno
) = sched_reg_live_length
[regno
];
5514 if (sched_reg_basic_block
[regno
] != REG_BLOCK_UNKNOWN
5515 && REG_BASIC_BLOCK(regno
) != REG_BLOCK_UNKNOWN
)
5516 REG_BASIC_BLOCK(regno
) = sched_reg_basic_block
[regno
];
5518 /* We can't change the value of reg_n_calls_crossed to zero for
5519 pseudos which are live in more than one block.
5521 This is because combine might have made an optimization which
5522 invalidated basic_block_live_at_start and reg_n_calls_crossed,
5523 but it does not update them. If we update reg_n_calls_crossed
5524 here, the two variables are now inconsistent, and this might
5525 confuse the caller-save code into saving a register that doesn't
5526 need to be saved. This is only a problem when we zero calls
5527 crossed for a pseudo live in multiple basic blocks.
5529 Alternatively, we could try to correctly update basic block live
5530 at start here in sched, but that seems complicated.
5532 Note: it is possible that a global register became local, as result
5533 of interblock motion, but will remain marked as a global register. */
5534 if (sched_reg_n_calls_crossed
[regno
]
5535 || REG_BASIC_BLOCK (regno
) != REG_BLOCK_GLOBAL
)
5536 REG_N_CALLS_CROSSED (regno
) = sched_reg_n_calls_crossed
[regno
];
5541 /* Scheduling clock, modified in schedule_block() and queue_to_ready () */
5542 static int clock_var
;
5544 /* Move insns that became ready to fire from queue to ready list. */
5547 queue_to_ready (ready
, n_ready
)
5554 q_ptr
= NEXT_Q (q_ptr
);
5556 /* Add all pending insns that can be scheduled without stalls to the
5558 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
5561 insn
= XEXP (link
, 0);
5564 if (sched_verbose
>= 2)
5565 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5567 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5568 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5570 ready
[n_ready
++] = insn
;
5571 if (sched_verbose
>= 2)
5572 fprintf (dump
, "moving to ready without stalls\n");
5574 insn_queue
[q_ptr
] = 0;
5576 /* If there are no ready insns, stall until one is ready and add all
5577 of the pending insns at that point to the ready list. */
5580 register int stalls
;
5582 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
5584 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
5586 for (; link
; link
= XEXP (link
, 1))
5588 insn
= XEXP (link
, 0);
5591 if (sched_verbose
>= 2)
5592 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
5594 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
5595 fprintf (dump
, "(b%d) ", INSN_BLOCK (insn
));
5597 ready
[n_ready
++] = insn
;
5598 if (sched_verbose
>= 2)
5599 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
5601 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
5608 if (sched_verbose
&& stalls
)
5609 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
5610 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
5611 clock_var
+= stalls
;
5616 /* Print the ready list for debugging purposes. Callable from debugger. */
5619 debug_ready_list (ready
, n_ready
)
5625 for (i
= 0; i
< n_ready
; i
++)
5627 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
5628 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
5629 fprintf (dump
, "/b%d", INSN_BLOCK (ready
[i
]));
5631 fprintf (dump
, "\n");
5634 /* Print names of units on which insn can/should execute, for debugging. */
5637 insn_print_units (insn
)
5641 int unit
= insn_unit (insn
);
5644 fprintf (dump
, "none");
5646 fprintf (dump
, "%s", function_units
[unit
].name
);
5649 fprintf (dump
, "[");
5650 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
5653 fprintf (dump
, "%s", function_units
[i
].name
);
5655 fprintf (dump
, " ");
5657 fprintf (dump
, "]");
5661 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
5662 of a basic block. If more lines are needed, table is splitted to two.
5663 n_visual_lines is the number of lines printed so far for a block.
5664 visual_tbl contains the block visualization info.
5665 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
5666 #define MAX_VISUAL_LINES 100
5671 rtx vis_no_unit
[10];
5673 /* Finds units that are in use in this fuction. Required only
5674 for visualization. */
5677 init_target_units ()
5682 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
5684 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5687 unit
= insn_unit (insn
);
5690 target_units
|= ~unit
;
5692 target_units
|= (1 << unit
);
5696 /* Return the length of the visualization table */
5699 get_visual_tbl_length ()
5705 /* compute length of one field in line */
5706 s
= (char *) alloca (INSN_LEN
+ 5);
5707 sprintf (s
, " %33s", "uname");
5710 /* compute length of one line */
5713 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5714 if (function_units
[unit
].bitmask
& target_units
)
5715 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5718 n
+= strlen ("\n") + 2;
5720 /* compute length of visualization string */
5721 return (MAX_VISUAL_LINES
* n
);
5724 /* Init block visualization debugging info */
5727 init_block_visualization ()
5729 strcpy (visual_tbl
, "");
5737 safe_concat (buf
, cur
, str
)
5742 char *end
= buf
+ BUF_LEN
- 2; /* leave room for null */
5751 while (cur
< end
&& (c
= *str
++) != '\0')
5758 /* This recognizes rtx, I classified as expressions. These are always */
5759 /* represent some action on values or results of other expression, */
5760 /* that may be stored in objects representing values. */
5763 print_exp (buf
, x
, verbose
)
5771 char *fun
= (char *)0;
5776 for (i
= 0; i
< 4; i
++)
5782 switch (GET_CODE (x
))
5785 op
[0] = XEXP (x
, 0);
5787 op
[1] = XEXP (x
, 1);
5790 op
[0] = XEXP (x
, 0);
5792 op
[1] = XEXP (x
, 1);
5796 op
[0] = XEXP (x
, 0);
5798 op
[1] = XEXP (x
, 1);
5802 op
[0] = XEXP (x
, 0);
5803 op
[1] = XEXP (x
, 1);
5807 op
[0] = XEXP (x
, 0);
5810 op
[0] = XEXP (x
, 0);
5812 op
[1] = XEXP (x
, 1);
5815 op
[0] = XEXP (x
, 0);
5817 op
[1] = XEXP (x
, 1);
5821 op
[0] = XEXP (x
, 0);
5822 op
[1] = XEXP (x
, 1);
5825 op
[0] = XEXP (x
, 0);
5827 op
[1] = XEXP (x
, 1);
5831 op
[0] = XEXP (x
, 0);
5832 op
[1] = XEXP (x
, 1);
5836 op
[0] = XEXP (x
, 0);
5837 op
[1] = XEXP (x
, 1);
5841 op
[0] = XEXP (x
, 0);
5842 op
[1] = XEXP (x
, 1);
5846 op
[0] = XEXP (x
, 0);
5847 op
[1] = XEXP (x
, 1);
5851 op
[0] = XEXP (x
, 0);
5852 op
[1] = XEXP (x
, 1);
5856 op
[0] = XEXP (x
, 0);
5859 op
[0] = XEXP (x
, 0);
5861 op
[1] = XEXP (x
, 1);
5864 op
[0] = XEXP (x
, 0);
5866 op
[1] = XEXP (x
, 1);
5869 op
[0] = XEXP (x
, 0);
5871 op
[1] = XEXP (x
, 1);
5874 op
[0] = XEXP (x
, 0);
5876 op
[1] = XEXP (x
, 1);
5879 op
[0] = XEXP (x
, 0);
5881 op
[1] = XEXP (x
, 1);
5884 op
[0] = XEXP (x
, 0);
5886 op
[1] = XEXP (x
, 1);
5889 op
[0] = XEXP (x
, 0);
5891 op
[1] = XEXP (x
, 1);
5894 op
[0] = XEXP (x
, 0);
5896 op
[1] = XEXP (x
, 1);
5900 op
[0] = XEXP (x
, 0);
5904 op
[0] = XEXP (x
, 0);
5908 op
[0] = XEXP (x
, 0);
5911 op
[0] = XEXP (x
, 0);
5913 op
[1] = XEXP (x
, 1);
5916 op
[0] = XEXP (x
, 0);
5918 op
[1] = XEXP (x
, 1);
5921 op
[0] = XEXP (x
, 0);
5923 op
[1] = XEXP (x
, 1);
5927 op
[0] = XEXP (x
, 0);
5928 op
[1] = XEXP (x
, 1);
5931 op
[0] = XEXP (x
, 0);
5933 op
[1] = XEXP (x
, 1);
5937 op
[0] = XEXP (x
, 0);
5938 op
[1] = XEXP (x
, 1);
5941 op
[0] = XEXP (x
, 0);
5943 op
[1] = XEXP (x
, 1);
5947 op
[0] = XEXP (x
, 0);
5948 op
[1] = XEXP (x
, 1);
5951 op
[0] = XEXP (x
, 0);
5953 op
[1] = XEXP (x
, 1);
5957 op
[0] = XEXP (x
, 0);
5958 op
[1] = XEXP (x
, 1);
5961 fun
= (verbose
) ? "sign_extract" : "sxt";
5962 op
[0] = XEXP (x
, 0);
5963 op
[1] = XEXP (x
, 1);
5964 op
[2] = XEXP (x
, 2);
5967 fun
= (verbose
) ? "zero_extract" : "zxt";
5968 op
[0] = XEXP (x
, 0);
5969 op
[1] = XEXP (x
, 1);
5970 op
[2] = XEXP (x
, 2);
5973 fun
= (verbose
) ? "sign_extend" : "sxn";
5974 op
[0] = XEXP (x
, 0);
5977 fun
= (verbose
) ? "zero_extend" : "zxn";
5978 op
[0] = XEXP (x
, 0);
5981 fun
= (verbose
) ? "float_extend" : "fxn";
5982 op
[0] = XEXP (x
, 0);
5985 fun
= (verbose
) ? "trunc" : "trn";
5986 op
[0] = XEXP (x
, 0);
5988 case FLOAT_TRUNCATE
:
5989 fun
= (verbose
) ? "float_trunc" : "ftr";
5990 op
[0] = XEXP (x
, 0);
5993 fun
= (verbose
) ? "float" : "flt";
5994 op
[0] = XEXP (x
, 0);
5996 case UNSIGNED_FLOAT
:
5997 fun
= (verbose
) ? "uns_float" : "ufl";
5998 op
[0] = XEXP (x
, 0);
6002 op
[0] = XEXP (x
, 0);
6005 fun
= (verbose
) ? "uns_fix" : "ufx";
6006 op
[0] = XEXP (x
, 0);
6010 op
[0] = XEXP (x
, 0);
6014 op
[0] = XEXP (x
, 0);
6017 op
[0] = XEXP (x
, 0);
6021 op
[0] = XEXP (x
, 0);
6026 op
[0] = XEXP (x
, 0);
6030 op
[1] = XEXP (x
, 1);
6035 op
[0] = XEXP (x
, 0);
6037 op
[1] = XEXP (x
, 1);
6039 op
[2] = XEXP (x
, 2);
6044 op
[0] = TRAP_CONDITION (x
);
6047 case UNSPEC_VOLATILE
:
6049 cur
= safe_concat (buf
, cur
, "unspec");
6050 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
6051 cur
= safe_concat (buf
, cur
, "/v");
6052 cur
= safe_concat (buf
, cur
, "[");
6054 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6056 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
6057 cur
= safe_concat (buf
, cur
, sep
);
6058 cur
= safe_concat (buf
, cur
, tmp
);
6061 cur
= safe_concat (buf
, cur
, "] ");
6062 sprintf (tmp
, "%d", XINT (x
, 1));
6063 cur
= safe_concat (buf
, cur
, tmp
);
6067 /* if (verbose) debug_rtx (x); */
6068 st
[0] = GET_RTX_NAME (GET_CODE (x
));
6072 /* Print this as a function? */
6075 cur
= safe_concat (buf
, cur
, fun
);
6076 cur
= safe_concat (buf
, cur
, "(");
6079 for (i
= 0; i
< 4; i
++)
6082 cur
= safe_concat (buf
, cur
, st
[i
]);
6087 cur
= safe_concat (buf
, cur
, ",");
6089 print_value (tmp
, op
[i
], verbose
);
6090 cur
= safe_concat (buf
, cur
, tmp
);
6095 cur
= safe_concat (buf
, cur
, ")");
6098 /* Prints rtxes, i customly classified as values. They're constants, */
6099 /* registers, labels, symbols and memory accesses. */
6102 print_value (buf
, x
, verbose
)
6110 switch (GET_CODE (x
))
6113 sprintf (t
, "0x%lx", (long)INTVAL (x
));
6114 cur
= safe_concat (buf
, cur
, t
);
6117 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
6118 cur
= safe_concat (buf
, cur
, t
);
6121 cur
= safe_concat (buf
, cur
, "\"");
6122 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6123 cur
= safe_concat (buf
, cur
, "\"");
6126 cur
= safe_concat (buf
, cur
, "`");
6127 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
6128 cur
= safe_concat (buf
, cur
, "'");
6131 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
6132 cur
= safe_concat (buf
, cur
, t
);
6135 print_value (t
, XEXP (x
, 0), verbose
);
6136 cur
= safe_concat (buf
, cur
, "const(");
6137 cur
= safe_concat (buf
, cur
, t
);
6138 cur
= safe_concat (buf
, cur
, ")");
6141 print_value (t
, XEXP (x
, 0), verbose
);
6142 cur
= safe_concat (buf
, cur
, "high(");
6143 cur
= safe_concat (buf
, cur
, t
);
6144 cur
= safe_concat (buf
, cur
, ")");
6147 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
6149 int c
= reg_names
[ REGNO (x
) ][0];
6150 if (c
>= '0' && c
<= '9')
6151 cur
= safe_concat (buf
, cur
, "%");
6153 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
6157 sprintf (t
, "r%d", REGNO (x
));
6158 cur
= safe_concat (buf
, cur
, t
);
6162 print_value (t
, SUBREG_REG (x
), verbose
);
6163 cur
= safe_concat (buf
, cur
, t
);
6164 sprintf (t
, "#%d", SUBREG_WORD (x
));
6165 cur
= safe_concat (buf
, cur
, t
);
6168 cur
= safe_concat (buf
, cur
, "scratch");
6171 cur
= safe_concat (buf
, cur
, "cc0");
6174 cur
= safe_concat (buf
, cur
, "pc");
6177 print_value (t
, XEXP (x
, 0), verbose
);
6178 cur
= safe_concat (buf
, cur
, "[");
6179 cur
= safe_concat (buf
, cur
, t
);
6180 cur
= safe_concat (buf
, cur
, "]");
6183 print_exp (t
, x
, verbose
);
6184 cur
= safe_concat (buf
, cur
, t
);
6189 /* The next step in insn detalization, its pattern recognition */
6192 print_pattern (buf
, x
, verbose
)
6197 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
6199 switch (GET_CODE (x
))
6202 print_value (t1
, SET_DEST (x
), verbose
);
6203 print_value (t2
, SET_SRC (x
), verbose
);
6204 sprintf (buf
, "%s=%s", t1
, t2
);
6207 sprintf (buf
, "return");
6210 print_exp (buf
, x
, verbose
);
6213 print_value (t1
, XEXP (x
, 0), verbose
);
6214 sprintf (buf
, "clobber %s", t1
);
6217 print_value (t1
, XEXP (x
, 0), verbose
);
6218 sprintf (buf
, "use %s", t1
);
6225 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6227 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6228 sprintf (t3
, "%s%s;", t1
, t2
);
6231 sprintf (buf
, "%s}", t1
);
6238 sprintf (t1
, "%%{");
6239 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6241 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
6242 sprintf (t3
, "%s%s;", t1
, t2
);
6245 sprintf (buf
, "%s%%}", t1
);
6249 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
6254 print_value (buf
, XEXP (x
, 0), verbose
);
6257 print_value (t1
, TRAP_CONDITION (x
), verbose
);
6258 sprintf (buf
, "trap_if %s", t1
);
6264 sprintf (t1
, "unspec{");
6265 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6267 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6268 sprintf (t3
, "%s%s;", t1
, t2
);
6271 sprintf (buf
, "%s}", t1
);
6274 case UNSPEC_VOLATILE
:
6278 sprintf (t1
, "unspec/v{");
6279 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
6281 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
6282 sprintf (t3
, "%s%s;", t1
, t2
);
6285 sprintf (buf
, "%s}", t1
);
6289 print_value (buf
, x
, verbose
);
6291 } /* print_pattern */
6293 /* This is the main function in rtl visualization mechanism. It
6294 accepts an rtx and tries to recognize it as an insn, then prints it
6295 properly in human readable form, resembling assembler mnemonics. */
6296 /* For every insn it prints its UID and BB the insn belongs */
6297 /* too. (probably the last "option" should be extended somehow, since */
6298 /* it depends now on sched.c inner variables ...) */
6301 print_insn (buf
, x
, verbose
)
6309 switch (GET_CODE (x
))
6312 print_pattern (t
, PATTERN (x
), verbose
);
6314 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
6317 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6320 print_pattern (t
, PATTERN (x
), verbose
);
6322 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
6325 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
6329 if (GET_CODE (x
) == PARALLEL
)
6331 x
= XVECEXP (x
, 0, 0);
6332 print_pattern (t
, x
, verbose
);
6335 strcpy (t
, "call <...>");
6337 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
6338 INSN_UID (insn
), t
);
6340 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
6343 sprintf (buf
, "L%d:", INSN_UID (x
));
6346 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
6349 if (NOTE_LINE_NUMBER (x
) > 0)
6350 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
6351 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
6353 sprintf (buf
, "%4d %s", INSN_UID (x
),
6354 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
6359 sprintf (buf
, "Not an INSN at all\n");
6363 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
6367 /* Print visualization debugging info */
6370 print_block_visualization (b
, s
)
6377 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
6379 /* Print names of units */
6380 fprintf (dump
, ";; %-8s", "clock");
6381 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6382 if (function_units
[unit
].bitmask
& target_units
)
6383 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6384 fprintf (dump
, " %-33s", function_units
[unit
].name
);
6385 fprintf (dump
, " %-8s\n", "no-unit");
6387 fprintf (dump
, ";; %-8s", "=====");
6388 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6389 if (function_units
[unit
].bitmask
& target_units
)
6390 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6391 fprintf (dump
, " %-33s", "==============================");
6392 fprintf (dump
, " %-8s\n", "=======");
6394 /* Print insns in each cycle */
6395 fprintf (dump
, "%s\n", visual_tbl
);
6398 /* Print insns in the 'no_unit' column of visualization */
6401 visualize_no_unit (insn
)
6404 vis_no_unit
[n_vis_no_unit
] = insn
;
6408 /* Print insns scheduled in clock, for visualization. */
6411 visualize_scheduled_insns (b
, clock
)
6416 /* if no more room, split table into two */
6417 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6419 print_block_visualization (b
, "(incomplete)");
6420 init_block_visualization ();
6425 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
6426 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
6427 if (function_units
[unit
].bitmask
& target_units
)
6428 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
6430 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
6431 rtx insn
= unit_last_insn
[instance
];
6433 /* print insns that still keep the unit busy */
6435 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
6438 print_insn (str
, insn
, 0);
6439 str
[INSN_LEN
] = '\0';
6440 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
6443 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
6446 /* print insns that are not assigned to any unit */
6447 for (i
= 0; i
< n_vis_no_unit
; i
++)
6448 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
6449 INSN_UID (vis_no_unit
[i
]));
6452 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6455 /* Print stalled cycles */
6458 visualize_stall_cycles (b
, stalls
)
6463 /* if no more room, split table into two */
6464 if (n_visual_lines
>= MAX_VISUAL_LINES
)
6466 print_block_visualization (b
, "(incomplete)");
6467 init_block_visualization ();
6472 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
6473 for (i
= 0; i
< stalls
; i
++)
6474 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
6475 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
6478 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn */
6481 move_insn1 (insn
, last
)
6484 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
6485 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
6487 NEXT_INSN (insn
) = NEXT_INSN (last
);
6488 PREV_INSN (NEXT_INSN (last
)) = insn
;
6490 NEXT_INSN (last
) = insn
;
6491 PREV_INSN (insn
) = last
;
6496 /* Search INSN for fake REG_DEAD note pairs for NOTE_INSN_SETJMP,
6497 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
6498 NOTEs. The REG_DEAD note following first one is contains the saved
6499 value for NOTE_BLOCK_NUMBER which is useful for
6500 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
6501 output by the instruction scheduler. Return the new value of LAST. */
6504 reemit_notes (insn
, last
)
6511 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
6513 if (REG_NOTE_KIND (note
) == REG_DEAD
6514 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6516 int note_type
= INTVAL (XEXP (note
, 0));
6517 if (note_type
== NOTE_INSN_SETJMP
)
6519 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
6520 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
6521 remove_note (insn
, note
);
6522 note
= XEXP (note
, 1);
6524 else if (note_type
== NOTE_INSN_RANGE_START
6525 || note_type
== NOTE_INSN_RANGE_END
)
6527 last
= emit_note_before (note_type
, last
);
6528 remove_note (insn
, note
);
6529 note
= XEXP (note
, 1);
6530 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
6534 last
= emit_note_before (INTVAL (XEXP (note
, 0)), last
);
6535 remove_note (insn
, note
);
6536 note
= XEXP (note
, 1);
6537 NOTE_BLOCK_NUMBER (last
) = INTVAL (XEXP (note
, 0));
6539 remove_note (insn
, note
);
6545 /* Move INSN, and all insns which should be issued before it,
6546 due to SCHED_GROUP_P flag. Reemit notes if needed.
6548 Return the last insn emitted by the scheduler, which is the
6549 return value from the first call to reemit_notes. */
6552 move_insn (insn
, last
)
6557 /* If INSN has SCHED_GROUP_P set, then issue it and any other
6558 insns with SCHED_GROUP_P set first. */
6559 while (SCHED_GROUP_P (insn
))
6561 rtx prev
= PREV_INSN (insn
);
6563 /* Move a SCHED_GROUP_P insn. */
6564 move_insn1 (insn
, last
);
6565 /* If this is the first call to reemit_notes, then record
6566 its return value. */
6567 if (retval
== NULL_RTX
)
6568 retval
= reemit_notes (insn
, insn
);
6570 reemit_notes (insn
, insn
);
6574 /* Now move the first non SCHED_GROUP_P insn. */
6575 move_insn1 (insn
, last
);
6577 /* If this is the first call to reemit_notes, then record
6578 its return value. */
6579 if (retval
== NULL_RTX
)
6580 retval
= reemit_notes (insn
, insn
);
6582 reemit_notes (insn
, insn
);
6587 /* Return an insn which represents a SCHED_GROUP, which is
6588 the last insn in the group. */
6599 insn
= next_nonnote_insn (insn
);
6601 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
6606 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
6607 possibly bringing insns from subsequent blocks in the same region.
6608 Return number of insns scheduled. */
6611 schedule_block (bb
, rgn_n_insns
)
6615 /* Local variables. */
6622 /* flow block of this bb */
6623 int b
= BB_TO_BLOCK (bb
);
6625 /* target_n_insns == number of insns in b before scheduling starts.
6626 sched_target_n_insns == how many of b's insns were scheduled.
6627 sched_n_insns == how many insns were scheduled in b */
6628 int target_n_insns
= 0;
6629 int sched_target_n_insns
= 0;
6630 int sched_n_insns
= 0;
6632 #define NEED_NOTHING 0
6637 /* head/tail info for this block */
6644 /* We used to have code to avoid getting parameters moved from hard
6645 argument registers into pseudos.
6647 However, it was removed when it proved to be of marginal benefit
6648 and caused problems because schedule_block and compute_forward_dependences
6649 had different notions of what the "head" insn was. */
6650 get_block_head_tail (bb
, &head
, &tail
);
6652 /* Interblock scheduling could have moved the original head insn from this
6653 block into a proceeding block. This may also cause schedule_block and
6654 compute_forward_dependences to have different notions of what the
6657 If the interblock movement happened to make this block start with
6658 some notes (LOOP, EH or SETJMP) before the first real insn, then
6659 HEAD will have various special notes attached to it which must be
6660 removed so that we don't end up with extra copies of the notes. */
6661 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
6665 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
6666 if (REG_NOTE_KIND (note
) == REG_DEAD
6667 && GET_CODE (XEXP (note
, 0)) == CONST_INT
)
6668 remove_note (head
, note
);
6671 next_tail
= NEXT_INSN (tail
);
6672 prev_head
= PREV_INSN (head
);
6674 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
6675 to schedule this block. */
6677 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6678 return (sched_n_insns
);
6683 fprintf (dump
, ";; ======================================================\n");
6685 ";; -- basic block %d from %d to %d -- %s reload\n",
6686 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
6687 (reload_completed
? "after" : "before"));
6688 fprintf (dump
, ";; ======================================================\n");
6689 fprintf (dump
, "\n");
6691 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
6692 init_block_visualization ();
6695 /* remove remaining note insns from the block, save them in
6696 note_list. These notes are restored at the end of
6697 schedule_block (). */
6699 rm_other_notes (head
, tail
);
6703 /* prepare current target block info */
6704 if (current_nr_blocks
> 1)
6706 candidate_table
= (candidate
*) alloca (current_nr_blocks
* sizeof (candidate
));
6709 /* ??? It is not clear why bblst_size is computed this way. The original
6710 number was clearly too small as it resulted in compiler failures.
6711 Multiplying by the original number by 2 (to account for update_bbs
6712 members) seems to be a reasonable solution. */
6713 /* ??? Or perhaps there is a bug somewhere else in this file? */
6714 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
6715 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
6717 bitlst_table_last
= 0;
6718 bitlst_table_size
= rgn_nr_edges
;
6719 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6721 compute_trg_info (bb
);
6726 /* Allocate the ready list */
6727 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
6729 /* Print debugging information. */
6730 if (sched_verbose
>= 5)
6731 debug_dependencies ();
6734 /* Initialize ready list with all 'ready' insns in target block.
6735 Count number of insns in the target block being scheduled. */
6737 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6741 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6743 next
= NEXT_INSN (insn
);
6745 if (INSN_DEP_COUNT (insn
) == 0
6746 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6747 ready
[n_ready
++] = insn
;
6748 if (!(SCHED_GROUP_P (insn
)))
6752 /* Add to ready list all 'ready' insns in valid source blocks.
6753 For speculative insns, check-live, exception-free, and
6755 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
6756 if (IS_VALID (bb_src
))
6762 get_block_head_tail (bb_src
, &head
, &tail
);
6763 src_next_tail
= NEXT_INSN (tail
);
6767 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6770 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
6772 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6775 if (!CANT_MOVE (insn
)
6776 && (!IS_SPECULATIVE_INSN (insn
)
6777 || (insn_issue_delay (insn
) <= 3
6778 && check_live (insn
, bb_src
)
6779 && is_exception_free (insn
, bb_src
, target_bb
))))
6784 next
= NEXT_INSN (insn
);
6785 if (INSN_DEP_COUNT (insn
) == 0
6786 && (SCHED_GROUP_P (next
) == 0
6787 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
6788 ready
[n_ready
++] = insn
;
6793 #ifdef MD_SCHED_INIT
6794 MD_SCHED_INIT (dump
, sched_verbose
);
6797 /* no insns scheduled in this block yet */
6798 last_scheduled_insn
= 0;
6800 /* Sort the ready list */
6801 SCHED_SORT (ready
, n_ready
);
6802 #ifdef MD_SCHED_REORDER
6803 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6806 if (sched_verbose
>= 2)
6808 fprintf (dump
, ";;\t\tReady list initially: ");
6809 debug_ready_list (ready
, n_ready
);
6812 /* Q_SIZE is the total number of insns in the queue. */
6817 bzero ((char *) insn_queue
, sizeof (insn_queue
));
6819 /* We start inserting insns after PREV_HEAD. */
6822 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
6823 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
6824 ? NEED_HEAD
: NEED_NOTHING
);
6825 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
6826 new_needs
|= NEED_TAIL
;
6828 /* loop until all the insns in BB are scheduled. */
6829 while (sched_target_n_insns
< target_n_insns
)
6835 /* Add to the ready list all pending insns that can be issued now.
6836 If there are no ready insns, increment clock until one
6837 is ready and add all pending insns at that point to the ready
6839 n_ready
= queue_to_ready (ready
, n_ready
);
6844 if (sched_verbose
>= 2)
6846 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
6847 debug_ready_list (ready
, n_ready
);
6850 /* Sort the ready list. */
6851 SCHED_SORT (ready
, n_ready
);
6852 #ifdef MD_SCHED_REORDER
6853 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
);
6858 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
6859 debug_ready_list (ready
, n_ready
);
6862 /* Issue insns from ready list.
6863 It is important to count down from n_ready, because n_ready may change
6864 as insns are issued. */
6865 can_issue_more
= issue_rate
;
6866 for (i
= n_ready
- 1; i
>= 0 && can_issue_more
; i
--)
6868 rtx insn
= ready
[i
];
6869 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
6873 queue_insn (insn
, cost
);
6874 ready
[i
] = ready
[--n_ready
]; /* remove insn from ready list */
6878 /* an interblock motion? */
6879 if (INSN_BB (insn
) != target_bb
)
6883 if (IS_SPECULATIVE_INSN (insn
))
6886 if (!check_live (insn
, INSN_BB (insn
)))
6888 /* speculative motion, live check failed, remove
6889 insn from ready list */
6890 ready
[i
] = ready
[--n_ready
];
6893 update_live (insn
, INSN_BB (insn
));
6895 /* for speculative load, mark insns fed by it. */
6896 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
6897 set_spec_fed (insn
);
6904 while (SCHED_GROUP_P (temp
))
6905 temp
= PREV_INSN (temp
);
6907 /* Update source block boundaries. */
6908 b1
= INSN_BLOCK (temp
);
6909 if (temp
== BLOCK_HEAD (b1
)
6910 && insn
== BLOCK_END (b1
))
6912 /* We moved all the insns in the basic block.
6913 Emit a note after the last insn and update the
6914 begin/end boundaries to point to the note. */
6915 emit_note_after (NOTE_INSN_DELETED
, insn
);
6916 BLOCK_END (b1
) = NEXT_INSN (insn
);
6917 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6919 else if (insn
== BLOCK_END (b1
))
6921 /* We took insns from the end of the basic block,
6922 so update the end of block boundary so that it
6923 points to the first insn we did not move. */
6924 BLOCK_END (b1
) = PREV_INSN (temp
);
6926 else if (temp
== BLOCK_HEAD (b1
))
6928 /* We took insns from the start of the basic block,
6929 so update the start of block boundary so that
6930 it points to the first insn we did not move. */
6931 BLOCK_HEAD (b1
) = NEXT_INSN (insn
);
6936 /* in block motion */
6937 sched_target_n_insns
++;
6940 last_scheduled_insn
= insn
;
6941 last
= move_insn (insn
, last
);
6944 #ifdef MD_SCHED_VARIABLE_ISSUE
6945 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
, can_issue_more
);
6950 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6952 /* remove insn from ready list */
6953 ready
[i
] = ready
[--n_ready
];
6955 /* close this block after scheduling its jump */
6956 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6964 visualize_scheduled_insns (b
, clock_var
);
6971 fprintf (dump
, ";;\tReady list (final): ");
6972 debug_ready_list (ready
, n_ready
);
6973 print_block_visualization (b
, "");
6976 /* Sanity check -- queue must be empty now. Meaningless if region has
6978 if (current_nr_blocks
> 1)
6979 if (!flag_schedule_interblock
&& q_size
!= 0)
6982 /* update head/tail boundaries. */
6983 head
= NEXT_INSN (prev_head
);
6986 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6987 previously found among the insns. Insert them at the beginning
6991 rtx note_head
= note_list
;
6993 while (PREV_INSN (note_head
))
6995 note_head
= PREV_INSN (note_head
);
6998 PREV_INSN (note_head
) = PREV_INSN (head
);
6999 NEXT_INSN (PREV_INSN (head
)) = note_head
;
7000 PREV_INSN (head
) = note_list
;
7001 NEXT_INSN (note_list
) = head
;
7005 /* update target block boundaries. */
7006 if (new_needs
& NEED_HEAD
)
7007 BLOCK_HEAD (b
) = head
;
7009 if (new_needs
& NEED_TAIL
)
7010 BLOCK_END (b
) = tail
;
7015 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
7016 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
7017 fprintf (dump
, ";; new basic block end = %d\n\n",
7018 INSN_UID (BLOCK_END (b
)));
7021 return (sched_n_insns
);
7022 } /* schedule_block () */
7025 /* print the bit-set of registers, S. callable from debugger */
7028 debug_reg_vector (s
)
7033 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
7035 fprintf (dump
, " %d", regno
);
7038 fprintf (dump
, "\n");
7041 /* Use the backward dependences from LOG_LINKS to build
7042 forward dependences in INSN_DEPEND. */
7045 compute_block_forward_dependences (bb
)
7051 enum reg_note dep_type
;
7053 get_block_head_tail (bb
, &head
, &tail
);
7054 next_tail
= NEXT_INSN (tail
);
7055 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7057 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7060 insn
= group_leader (insn
);
7062 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
7064 rtx x
= group_leader (XEXP (link
, 0));
7067 if (x
!= XEXP (link
, 0))
7070 /* Ignore dependences upon deleted insn */
7071 if (GET_CODE (x
) == NOTE
|| INSN_DELETED_P (x
))
7073 if (find_insn_list (insn
, INSN_DEPEND (x
)))
7076 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
7078 dep_type
= REG_NOTE_KIND (link
);
7079 PUT_REG_NOTE_KIND (new_link
, dep_type
);
7081 INSN_DEPEND (x
) = new_link
;
7082 INSN_DEP_COUNT (insn
) += 1;
7087 /* Initialize variables for region data dependence analysis.
7088 n_bbs is the number of region blocks */
7090 __inline
static void
7091 init_rgn_data_dependences (n_bbs
)
7096 /* variables for which one copy exists for each block */
7097 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
7098 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
7099 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
7100 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
7101 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
7102 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
7103 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
7104 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
7106 /* Create an insn here so that we can hang dependencies off of it later. */
7107 for (bb
= 0; bb
< n_bbs
; bb
++)
7109 bb_sched_before_next_call
[bb
] =
7110 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7111 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7112 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
7116 /* Add dependences so that branches are scheduled to run last in their block */
7119 add_branch_dependences (head
, tail
)
7125 /* For all branches, calls, uses, and cc0 setters, force them to remain
7126 in order at the end of the block by adding dependencies and giving
7127 the last a high priority. There may be notes present, and prev_head
7130 Branches must obviously remain at the end. Calls should remain at the
7131 end since moving them results in worse register allocation. Uses remain
7132 at the end to ensure proper register allocation. cc0 setters remaim
7133 at the end because they can't be moved away from their cc0 user. */
7136 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
7137 || (GET_CODE (insn
) == INSN
7138 && (GET_CODE (PATTERN (insn
)) == USE
7140 || sets_cc0_p (PATTERN (insn
))
7143 || GET_CODE (insn
) == NOTE
)
7145 if (GET_CODE (insn
) != NOTE
)
7148 && !find_insn_list (insn
, LOG_LINKS (last
)))
7150 add_dependence (last
, insn
, REG_DEP_ANTI
);
7151 INSN_REF_COUNT (insn
)++;
7154 CANT_MOVE (insn
) = 1;
7157 /* Skip over insns that are part of a group.
7158 Make each insn explicitly depend on the previous insn.
7159 This ensures that only the group header will ever enter
7160 the ready queue (and, when scheduled, will automatically
7161 schedule the SCHED_GROUP_P block). */
7162 while (SCHED_GROUP_P (insn
))
7164 rtx temp
= prev_nonnote_insn (insn
);
7165 add_dependence (insn
, temp
, REG_DEP_ANTI
);
7170 /* Don't overrun the bounds of the basic block. */
7174 insn
= PREV_INSN (insn
);
7177 /* make sure these insns are scheduled last in their block */
7180 while (insn
!= head
)
7182 insn
= prev_nonnote_insn (insn
);
7184 if (INSN_REF_COUNT (insn
) != 0)
7187 if (!find_insn_list (last
, LOG_LINKS (insn
)))
7188 add_dependence (last
, insn
, REG_DEP_ANTI
);
7189 INSN_REF_COUNT (insn
) = 1;
7191 /* Skip over insns that are part of a group. */
7192 while (SCHED_GROUP_P (insn
))
7193 insn
= prev_nonnote_insn (insn
);
7197 /* Compute bacward dependences inside BB. In a multiple blocks region:
7198 (1) a bb is analyzed after its predecessors, and (2) the lists in
7199 effect at the end of bb (after analyzing for bb) are inherited by
7202 Specifically for reg-reg data dependences, the block insns are
7203 scanned by sched_analyze () top-to-bottom. Two lists are
7204 naintained by sched_analyze (): reg_last_defs[] for register DEFs,
7205 and reg_last_uses[] for register USEs.
7207 When analysis is completed for bb, we update for its successors:
7208 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
7209 ; - USES[succ] = Union (USES [succ], DEFS [bb])
7211 The mechanism for computing mem-mem data dependence is very
7212 similar, and the result is interblock dependences in the region. */
7215 compute_block_backward_dependences (bb
)
7221 int max_reg
= max_reg_num ();
7223 b
= BB_TO_BLOCK (bb
);
7225 if (current_nr_blocks
== 1)
7227 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7228 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
7230 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
7231 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
7233 pending_read_insns
= 0;
7234 pending_read_mems
= 0;
7235 pending_write_insns
= 0;
7236 pending_write_mems
= 0;
7237 pending_lists_length
= 0;
7238 last_function_call
= 0;
7239 last_pending_memory_flush
= 0;
7240 sched_before_next_call
7241 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
7242 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
7243 LOG_LINKS (sched_before_next_call
) = 0;
7247 reg_last_uses
= bb_reg_last_uses
[bb
];
7248 reg_last_sets
= bb_reg_last_sets
[bb
];
7250 pending_read_insns
= bb_pending_read_insns
[bb
];
7251 pending_read_mems
= bb_pending_read_mems
[bb
];
7252 pending_write_insns
= bb_pending_write_insns
[bb
];
7253 pending_write_mems
= bb_pending_write_mems
[bb
];
7254 pending_lists_length
= bb_pending_lists_length
[bb
];
7255 last_function_call
= bb_last_function_call
[bb
];
7256 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
7258 sched_before_next_call
= bb_sched_before_next_call
[bb
];
7261 /* do the analysis for this block */
7262 get_block_head_tail (bb
, &head
, &tail
);
7263 sched_analyze (head
, tail
);
7264 add_branch_dependences (head
, tail
);
7266 if (current_nr_blocks
> 1)
7269 int b_succ
, bb_succ
;
7271 rtx link_insn
, link_mem
;
7274 /* these lists should point to the right place, for correct freeing later. */
7275 bb_pending_read_insns
[bb
] = pending_read_insns
;
7276 bb_pending_read_mems
[bb
] = pending_read_mems
;
7277 bb_pending_write_insns
[bb
] = pending_write_insns
;
7278 bb_pending_write_mems
[bb
] = pending_write_mems
;
7280 /* bb's structures are inherited by it's successors */
7281 first_edge
= e
= OUT_EDGES (b
);
7285 b_succ
= TO_BLOCK (e
);
7286 bb_succ
= BLOCK_TO_BB (b_succ
);
7288 /* only bbs "below" bb, in the same region, are interesting */
7289 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
7296 for (reg
= 0; reg
< max_reg
; reg
++)
7299 /* reg-last-uses lists are inherited by bb_succ */
7300 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
7302 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_uses
[bb_succ
])[reg
]))
7305 (bb_reg_last_uses
[bb_succ
])[reg
]
7306 = alloc_INSN_LIST (XEXP (u
, 0),
7307 (bb_reg_last_uses
[bb_succ
])[reg
]);
7310 /* reg-last-defs lists are inherited by bb_succ */
7311 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
7313 if (find_insn_list (XEXP (u
, 0), (bb_reg_last_sets
[bb_succ
])[reg
]))
7316 (bb_reg_last_sets
[bb_succ
])[reg
]
7317 = alloc_INSN_LIST (XEXP (u
, 0),
7318 (bb_reg_last_sets
[bb_succ
])[reg
]);
7322 /* mem read/write lists are inherited by bb_succ */
7323 link_insn
= pending_read_insns
;
7324 link_mem
= pending_read_mems
;
7327 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7328 bb_pending_read_insns
[bb_succ
],
7329 bb_pending_read_mems
[bb_succ
])))
7330 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
7331 &bb_pending_read_mems
[bb_succ
],
7332 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7333 link_insn
= XEXP (link_insn
, 1);
7334 link_mem
= XEXP (link_mem
, 1);
7337 link_insn
= pending_write_insns
;
7338 link_mem
= pending_write_mems
;
7341 if (!(find_insn_mem_list (XEXP (link_insn
, 0), XEXP (link_mem
, 0),
7342 bb_pending_write_insns
[bb_succ
],
7343 bb_pending_write_mems
[bb_succ
])))
7344 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
7345 &bb_pending_write_mems
[bb_succ
],
7346 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
7348 link_insn
= XEXP (link_insn
, 1);
7349 link_mem
= XEXP (link_mem
, 1);
7352 /* last_function_call is inherited by bb_succ */
7353 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
7355 if (find_insn_list (XEXP (u
, 0), bb_last_function_call
[bb_succ
]))
7358 bb_last_function_call
[bb_succ
]
7359 = alloc_INSN_LIST (XEXP (u
, 0),
7360 bb_last_function_call
[bb_succ
]);
7363 /* last_pending_memory_flush is inherited by bb_succ */
7364 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
7366 if (find_insn_list (XEXP (u
, 0), bb_last_pending_memory_flush
[bb_succ
]))
7369 bb_last_pending_memory_flush
[bb_succ
]
7370 = alloc_INSN_LIST (XEXP (u
, 0),
7371 bb_last_pending_memory_flush
[bb_succ
]);
7374 /* sched_before_next_call is inherited by bb_succ */
7375 x
= LOG_LINKS (sched_before_next_call
);
7376 for (; x
; x
= XEXP (x
, 1))
7377 add_dependence (bb_sched_before_next_call
[bb_succ
],
7378 XEXP (x
, 0), REG_DEP_ANTI
);
7382 while (e
!= first_edge
);
7385 /* Free up the INSN_LISTs
7387 Note this loop is executed max_reg * nr_regions times. It's first
7388 implementation accounted for over 90% of the calls to free_list.
7389 The list was empty for the vast majority of those calls. On the PA,
7390 not calling free_list in those cases improves -O2 compile times by
7392 for (b
= 0; b
< max_reg
; ++b
)
7394 if (reg_last_sets
[b
])
7395 free_list (®_last_sets
[b
], &unused_insn_list
);
7396 if (reg_last_uses
[b
])
7397 free_list (®_last_uses
[b
], &unused_insn_list
);
7400 /* Assert that we won't need bb_reg_last_* for this block anymore. */
7401 if (current_nr_blocks
> 1)
7403 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
7404 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
7408 /* Print dependences for debugging, callable from debugger */
7411 debug_dependencies ()
7415 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
7416 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7424 get_block_head_tail (bb
, &head
, &tail
);
7425 next_tail
= NEXT_INSN (tail
);
7426 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
7427 BB_TO_BLOCK (bb
), bb
);
7429 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7430 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
7431 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
7432 "----", "----", "--", "---", "----", "----", "--------", "-----");
7433 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
7438 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
7441 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
7442 if (GET_CODE (insn
) == NOTE
)
7444 n
= NOTE_LINE_NUMBER (insn
);
7446 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
7448 fprintf (dump
, "line %d, file %s\n", n
,
7449 NOTE_SOURCE_FILE (insn
));
7452 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
7456 unit
= insn_unit (insn
);
7458 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
7459 function_units
[unit
].blockage_range_function (insn
);
7461 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
7462 (SCHED_GROUP_P (insn
) ? "+" : " "),
7466 INSN_DEP_COUNT (insn
),
7467 INSN_PRIORITY (insn
),
7468 insn_cost (insn
, 0, 0),
7469 (int) MIN_BLOCKAGE_COST (range
),
7470 (int) MAX_BLOCKAGE_COST (range
));
7471 insn_print_units (insn
);
7472 fprintf (dump
, "\t: ");
7473 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
7474 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
7475 fprintf (dump
, "\n");
7479 fprintf (dump
, "\n");
7482 /* Set_priorities: compute priority of each insn in the block */
7495 get_block_head_tail (bb
, &head
, &tail
);
7496 prev_head
= PREV_INSN (head
);
7499 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
7503 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
7506 if (GET_CODE (insn
) == NOTE
)
7509 if (!(SCHED_GROUP_P (insn
)))
7511 (void) priority (insn
);
7517 /* Make each element of VECTOR point at an rtx-vector,
7518 taking the space for all those rtx-vectors from SPACE.
7519 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
7520 BYTES_PER_ELT is the number of bytes in one rtx-vector.
7521 (this is the same as init_regset_vector () in flow.c) */
7524 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
7531 register rtx
*p
= space
;
7533 for (i
= 0; i
< nelts
; i
++)
7536 p
+= bytes_per_elt
/ sizeof (*p
);
7540 /* Schedule a region. A region is either an inner loop, a loop-free
7541 subroutine, or a single basic block. Each bb in the region is
7542 scheduled after its flow predecessors. */
7545 schedule_region (rgn
)
7549 int rgn_n_insns
= 0;
7550 int sched_rgn_n_insns
= 0;
7552 /* set variables for the current region */
7553 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
7554 current_blocks
= RGN_BLOCKS (rgn
);
7556 reg_pending_sets
= ALLOCA_REG_SET ();
7557 reg_pending_sets_all
= 0;
7559 /* initializations for region data dependence analyisis */
7560 if (current_nr_blocks
> 1)
7563 int maxreg
= max_reg_num ();
7565 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7566 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7567 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7568 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7570 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
7571 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
7572 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
7573 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
, maxreg
* sizeof (rtx
*));
7575 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7576 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7577 bb_pending_write_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7578 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7579 bb_pending_lists_length
= (int *) alloca (current_nr_blocks
* sizeof (int));
7580 bb_last_pending_memory_flush
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7581 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7582 bb_sched_before_next_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
7584 init_rgn_data_dependences (current_nr_blocks
);
7587 /* compute LOG_LINKS */
7588 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7589 compute_block_backward_dependences (bb
);
7591 /* compute INSN_DEPEND */
7592 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7593 compute_block_forward_dependences (bb
);
7595 /* Delete line notes, compute live-regs at block end, and set priorities. */
7597 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7599 if (reload_completed
== 0)
7600 find_pre_sched_live (bb
);
7602 if (write_symbols
!= NO_DEBUG
)
7604 save_line_notes (bb
);
7608 rgn_n_insns
+= set_priorities (bb
);
7611 /* compute interblock info: probabilities, split-edges, dominators, etc. */
7612 if (current_nr_blocks
> 1)
7616 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
7618 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
7619 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
7620 for (i
= 0; i
< current_nr_blocks
; i
++)
7622 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
7623 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
7628 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
7629 for (i
= 1; i
< nr_edges
; i
++)
7630 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
7631 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
7632 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
7635 for (i
= 1; i
< nr_edges
; i
++)
7636 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
7637 rgn_edges
[rgn_nr_edges
++] = i
;
7640 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
7641 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7642 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
7643 for (i
= 0; i
< current_nr_blocks
; i
++)
7646 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7647 bzero ((char *) pot_split
[i
],
7648 edgeset_size
* sizeof (HOST_WIDE_INT
));
7650 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
7651 bzero ((char *) ancestor_edges
[i
],
7652 edgeset_size
* sizeof (HOST_WIDE_INT
));
7655 /* compute probabilities, dominators, split_edges */
7656 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7657 compute_dom_prob_ps (bb
);
7660 /* now we can schedule all blocks */
7661 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7663 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
7670 /* sanity check: verify that all region insns were scheduled */
7671 if (sched_rgn_n_insns
!= rgn_n_insns
)
7674 /* update register life and usage information */
7675 if (reload_completed
== 0)
7677 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
7678 find_post_sched_live (bb
);
7680 if (current_nr_blocks
<= 1)
7681 /* Sanity check. There should be no REG_DEAD notes leftover at the end.
7682 In practice, this can occur as the result of bugs in flow, combine.c,
7683 and/or sched.c. The values of the REG_DEAD notes remaining are
7684 meaningless, because dead_notes is just used as a free list. */
7685 if (dead_notes
!= 0)
7689 /* restore line notes. */
7690 if (write_symbols
!= NO_DEBUG
)
7692 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
7693 restore_line_notes (bb
);
7696 /* Done with this region */
7697 free_pending_lists ();
7699 FREE_REG_SET (reg_pending_sets
);
7702 /* Subroutine of split_hard_reg_notes. Searches X for any reference to
7703 REGNO, returning the rtx of the reference found if any. Otherwise,
7707 regno_use_in (regno
, x
)
7715 if (GET_CODE (x
) == REG
&& REGNO (x
) == regno
)
7718 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
7719 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0; i
--)
7723 if ((tem
= regno_use_in (regno
, XEXP (x
, i
))))
7726 else if (fmt
[i
] == 'E')
7727 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
7728 if ((tem
= regno_use_in (regno
, XVECEXP (x
, i
, j
))))
7735 /* Subroutine of update_flow_info. Determines whether any new REG_NOTEs are
7736 needed for the hard register mentioned in the note. This can happen
7737 if the reference to the hard register in the original insn was split into
7738 several smaller hard register references in the split insns. */
7741 split_hard_reg_notes (note
, first
, last
)
7742 rtx note
, first
, last
;
7744 rtx reg
, temp
, link
;
7745 int n_regs
, i
, new_reg
;
7748 /* Assume that this is a REG_DEAD note. */
7749 if (REG_NOTE_KIND (note
) != REG_DEAD
)
7752 reg
= XEXP (note
, 0);
7754 n_regs
= HARD_REGNO_NREGS (REGNO (reg
), GET_MODE (reg
));
7756 for (i
= 0; i
< n_regs
; i
++)
7758 new_reg
= REGNO (reg
) + i
;
7760 /* Check for references to new_reg in the split insns. */
7761 for (insn
= last
;; insn
= PREV_INSN (insn
))
7763 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7764 && (temp
= regno_use_in (new_reg
, PATTERN (insn
))))
7766 /* Create a new reg dead note ere. */
7767 link
= alloc_EXPR_LIST (REG_DEAD
, temp
, REG_NOTES (insn
));
7768 REG_NOTES (insn
) = link
;
7770 /* If killed multiple registers here, then add in the excess. */
7771 i
+= HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) - 1;
7775 /* It isn't mentioned anywhere, so no new reg note is needed for
7783 /* Subroutine of update_flow_info. Determines whether a SET or CLOBBER in an
7784 insn created by splitting needs a REG_DEAD or REG_UNUSED note added. */
7787 new_insn_dead_notes (pat
, insn
, last
, orig_insn
)
7788 rtx pat
, insn
, last
, orig_insn
;
7792 /* PAT is either a CLOBBER or a SET here. */
7793 dest
= XEXP (pat
, 0);
7795 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
7796 || GET_CODE (dest
) == STRICT_LOW_PART
7797 || GET_CODE (dest
) == SIGN_EXTRACT
)
7798 dest
= XEXP (dest
, 0);
7800 if (GET_CODE (dest
) == REG
)
7802 /* If the original insn already used this register, we may not add new
7803 notes for it. One example for a split that needs this test is
7804 when a multi-word memory access with register-indirect addressing
7805 is split into multiple memory accesses with auto-increment and
7806 one adjusting add instruction for the address register. */
7807 if (reg_referenced_p (dest
, PATTERN (orig_insn
)))
7809 for (tem
= last
; tem
!= insn
; tem
= PREV_INSN (tem
))
7811 if (GET_RTX_CLASS (GET_CODE (tem
)) == 'i'
7812 && reg_overlap_mentioned_p (dest
, PATTERN (tem
))
7813 && (set
= single_set (tem
)))
7815 rtx tem_dest
= SET_DEST (set
);
7817 while (GET_CODE (tem_dest
) == ZERO_EXTRACT
7818 || GET_CODE (tem_dest
) == SUBREG
7819 || GET_CODE (tem_dest
) == STRICT_LOW_PART
7820 || GET_CODE (tem_dest
) == SIGN_EXTRACT
)
7821 tem_dest
= XEXP (tem_dest
, 0);
7823 if (!rtx_equal_p (tem_dest
, dest
))
7825 /* Use the same scheme as combine.c, don't put both REG_DEAD
7826 and REG_UNUSED notes on the same insn. */
7827 if (!find_regno_note (tem
, REG_UNUSED
, REGNO (dest
))
7828 && !find_regno_note (tem
, REG_DEAD
, REGNO (dest
)))
7830 rtx note
= alloc_EXPR_LIST (REG_DEAD
, dest
,
7832 REG_NOTES (tem
) = note
;
7834 /* The reg only dies in one insn, the last one that uses
7838 else if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
7839 /* We found an instruction that both uses the register,
7840 and sets it, so no new REG_NOTE is needed for this set. */
7844 /* If this is a set, it must die somewhere, unless it is the dest of
7845 the original insn, and hence is live after the original insn. Abort
7846 if it isn't supposed to be live after the original insn.
7848 If this is a clobber, then just add a REG_UNUSED note. */
7851 int live_after_orig_insn
= 0;
7852 rtx pattern
= PATTERN (orig_insn
);
7855 if (GET_CODE (pat
) == CLOBBER
)
7857 rtx note
= alloc_EXPR_LIST (REG_UNUSED
, dest
, REG_NOTES (insn
));
7858 REG_NOTES (insn
) = note
;
7862 /* The original insn could have multiple sets, so search the
7863 insn for all sets. */
7864 if (GET_CODE (pattern
) == SET
)
7866 if (reg_overlap_mentioned_p (dest
, SET_DEST (pattern
)))
7867 live_after_orig_insn
= 1;
7869 else if (GET_CODE (pattern
) == PARALLEL
)
7871 for (i
= 0; i
< XVECLEN (pattern
, 0); i
++)
7872 if (GET_CODE (XVECEXP (pattern
, 0, i
)) == SET
7873 && reg_overlap_mentioned_p (dest
,
7874 SET_DEST (XVECEXP (pattern
,
7876 live_after_orig_insn
= 1;
7879 if (!live_after_orig_insn
)
7885 /* Subroutine of update_flow_info. Update the value of reg_n_sets for all
7886 registers modified by X. INC is -1 if the containing insn is being deleted,
7887 and is 1 if the containing insn is a newly generated insn. */
7890 update_n_sets (x
, inc
)
7894 rtx dest
= SET_DEST (x
);
7896 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
7897 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
7898 dest
= SUBREG_REG (dest
);
7900 if (GET_CODE (dest
) == REG
)
7902 int regno
= REGNO (dest
);
7904 if (regno
< FIRST_PSEUDO_REGISTER
)
7907 int endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
7909 for (i
= regno
; i
< endregno
; i
++)
7910 REG_N_SETS (i
) += inc
;
7913 REG_N_SETS (regno
) += inc
;
7917 /* Updates all flow-analysis related quantities (including REG_NOTES) for
7918 the insns from FIRST to LAST inclusive that were created by splitting
7919 ORIG_INSN. NOTES are the original REG_NOTES. */
7922 update_flow_info (notes
, first
, last
, orig_insn
)
7929 rtx orig_dest
, temp
;
7932 /* Get and save the destination set by the original insn. */
7934 orig_dest
= single_set (orig_insn
);
7936 orig_dest
= SET_DEST (orig_dest
);
7938 /* Move REG_NOTES from the original insn to where they now belong. */
7940 for (note
= notes
; note
; note
= next
)
7942 next
= XEXP (note
, 1);
7943 switch (REG_NOTE_KIND (note
))
7947 /* Move these notes from the original insn to the last new insn where
7948 the register is now set. */
7950 for (insn
= last
;; insn
= PREV_INSN (insn
))
7952 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
7953 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
7955 /* If this note refers to a multiple word hard register, it
7956 may have been split into several smaller hard register
7957 references, so handle it specially. */
7958 temp
= XEXP (note
, 0);
7959 if (REG_NOTE_KIND (note
) == REG_DEAD
7960 && GET_CODE (temp
) == REG
7961 && REGNO (temp
) < FIRST_PSEUDO_REGISTER
7962 && HARD_REGNO_NREGS (REGNO (temp
), GET_MODE (temp
)) > 1)
7963 split_hard_reg_notes (note
, first
, last
);
7966 XEXP (note
, 1) = REG_NOTES (insn
);
7967 REG_NOTES (insn
) = note
;
7970 /* Sometimes need to convert REG_UNUSED notes to REG_DEAD
7972 /* ??? This won't handle multiple word registers correctly,
7973 but should be good enough for now. */
7974 if (REG_NOTE_KIND (note
) == REG_UNUSED
7975 && GET_CODE (XEXP (note
, 0)) != SCRATCH
7976 && !dead_or_set_p (insn
, XEXP (note
, 0)))
7977 PUT_REG_NOTE_KIND (note
, REG_DEAD
);
7979 /* The reg only dies in one insn, the last one that uses
7983 /* It must die somewhere, fail it we couldn't find where it died.
7985 If this is a REG_UNUSED note, then it must be a temporary
7986 register that was not needed by this instantiation of the
7987 pattern, so we can safely ignore it. */
7990 if (REG_NOTE_KIND (note
) != REG_UNUSED
)
7999 /* If the insn that set the register to 0 was deleted, this
8000 note cannot be relied on any longer. The destination might
8001 even have been moved to memory.
8002 This was observed for SH4 with execute/920501-6.c compilation,
8003 -O2 -fomit-frame-pointer -finline-functions . */
8004 if (GET_CODE (XEXP (note
, 0)) == NOTE
8005 || INSN_DELETED_P (XEXP (note
, 0)))
8007 /* This note applies to the dest of the original insn. Find the
8008 first new insn that now has the same dest, and move the note
8014 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8016 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8017 && (temp
= single_set (insn
))
8018 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8020 XEXP (note
, 1) = REG_NOTES (insn
);
8021 REG_NOTES (insn
) = note
;
8022 /* The reg is only zero before one insn, the first that
8026 /* If this note refers to a multiple word hard
8027 register, it may have been split into several smaller
8028 hard register references. We could split the notes,
8029 but simply dropping them is good enough. */
8030 if (GET_CODE (orig_dest
) == REG
8031 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8032 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8033 GET_MODE (orig_dest
)) > 1)
8035 /* It must be set somewhere, fail if we couldn't find where it
8044 /* A REG_EQUIV or REG_EQUAL note on an insn with more than one
8045 set is meaningless. Just drop the note. */
8049 case REG_NO_CONFLICT
:
8050 /* These notes apply to the dest of the original insn. Find the last
8051 new insn that now has the same dest, and move the note there. */
8056 for (insn
= last
;; insn
= PREV_INSN (insn
))
8058 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8059 && (temp
= single_set (insn
))
8060 && rtx_equal_p (SET_DEST (temp
), orig_dest
))
8062 XEXP (note
, 1) = REG_NOTES (insn
);
8063 REG_NOTES (insn
) = note
;
8064 /* Only put this note on one of the new insns. */
8068 /* The original dest must still be set someplace. Abort if we
8069 couldn't find it. */
8072 /* However, if this note refers to a multiple word hard
8073 register, it may have been split into several smaller
8074 hard register references. We could split the notes,
8075 but simply dropping them is good enough. */
8076 if (GET_CODE (orig_dest
) == REG
8077 && REGNO (orig_dest
) < FIRST_PSEUDO_REGISTER
8078 && HARD_REGNO_NREGS (REGNO (orig_dest
),
8079 GET_MODE (orig_dest
)) > 1)
8081 /* Likewise for multi-word memory references. */
8082 if (GET_CODE (orig_dest
) == MEM
8083 && SIZE_FOR_MODE (orig_dest
) > UNITS_PER_WORD
)
8091 /* Move a REG_LIBCALL note to the first insn created, and update
8092 the corresponding REG_RETVAL note. */
8093 XEXP (note
, 1) = REG_NOTES (first
);
8094 REG_NOTES (first
) = note
;
8096 insn
= XEXP (note
, 0);
8097 note
= find_reg_note (insn
, REG_RETVAL
, NULL_RTX
);
8099 XEXP (note
, 0) = first
;
8102 case REG_EXEC_COUNT
:
8103 /* Move a REG_EXEC_COUNT note to the first insn created. */
8104 XEXP (note
, 1) = REG_NOTES (first
);
8105 REG_NOTES (first
) = note
;
8109 /* Move a REG_RETVAL note to the last insn created, and update
8110 the corresponding REG_LIBCALL note. */
8111 XEXP (note
, 1) = REG_NOTES (last
);
8112 REG_NOTES (last
) = note
;
8114 insn
= XEXP (note
, 0);
8115 note
= find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
);
8117 XEXP (note
, 0) = last
;
8122 /* This should be moved to whichever instruction is a JUMP_INSN. */
8124 for (insn
= last
;; insn
= PREV_INSN (insn
))
8126 if (GET_CODE (insn
) == JUMP_INSN
)
8128 XEXP (note
, 1) = REG_NOTES (insn
);
8129 REG_NOTES (insn
) = note
;
8130 /* Only put this note on one of the new insns. */
8133 /* Fail if we couldn't find a JUMP_INSN. */
8140 /* reload sometimes leaves obsolete REG_INC notes around. */
8141 if (reload_completed
)
8143 /* This should be moved to whichever instruction now has the
8144 increment operation. */
8148 /* Should be moved to the new insn(s) which use the label. */
8149 for (insn
= first
; insn
!= NEXT_INSN (last
); insn
= NEXT_INSN (insn
))
8150 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8151 && reg_mentioned_p (XEXP (note
, 0), PATTERN (insn
)))
8153 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_LABEL
,
8161 /* These two notes will never appear until after reorg, so we don't
8162 have to handle them here. */
8168 /* Each new insn created, except the last, has a new set. If the destination
8169 is a register, then this reg is now live across several insns, whereas
8170 previously the dest reg was born and died within the same insn. To
8171 reflect this, we now need a REG_DEAD note on the insn where this
8174 Similarly, the new insns may have clobbers that need REG_UNUSED notes. */
8176 for (insn
= first
; insn
!= last
; insn
= NEXT_INSN (insn
))
8181 pat
= PATTERN (insn
);
8182 if (GET_CODE (pat
) == SET
|| GET_CODE (pat
) == CLOBBER
)
8183 new_insn_dead_notes (pat
, insn
, last
, orig_insn
);
8184 else if (GET_CODE (pat
) == PARALLEL
)
8186 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
8187 if (GET_CODE (XVECEXP (pat
, 0, i
)) == SET
8188 || GET_CODE (XVECEXP (pat
, 0, i
)) == CLOBBER
)
8189 new_insn_dead_notes (XVECEXP (pat
, 0, i
), insn
, last
, orig_insn
);
8193 /* If any insn, except the last, uses the register set by the last insn,
8194 then we need a new REG_DEAD note on that insn. In this case, there
8195 would not have been a REG_DEAD note for this register in the original
8196 insn because it was used and set within one insn. */
8198 set
= single_set (last
);
8201 rtx dest
= SET_DEST (set
);
8203 while (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
8204 || GET_CODE (dest
) == STRICT_LOW_PART
8205 || GET_CODE (dest
) == SIGN_EXTRACT
)
8206 dest
= XEXP (dest
, 0);
8208 if (GET_CODE (dest
) == REG
8209 /* Global registers are always live, so the code below does not
8211 && (REGNO (dest
) >= FIRST_PSEUDO_REGISTER
8212 || ! global_regs
[REGNO (dest
)]))
8214 rtx stop_insn
= PREV_INSN (first
);
8216 /* If the last insn uses the register that it is setting, then
8217 we don't want to put a REG_DEAD note there. Search backwards
8218 to find the first insn that sets but does not use DEST. */
8221 if (reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8223 for (insn
= PREV_INSN (insn
); insn
!= first
;
8224 insn
= PREV_INSN (insn
))
8226 if ((set
= single_set (insn
))
8227 && reg_mentioned_p (dest
, SET_DEST (set
))
8228 && ! reg_overlap_mentioned_p (dest
, SET_SRC (set
)))
8233 /* Now find the first insn that uses but does not set DEST. */
8235 for (insn
= PREV_INSN (insn
); insn
!= stop_insn
;
8236 insn
= PREV_INSN (insn
))
8238 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8239 && reg_mentioned_p (dest
, PATTERN (insn
))
8240 && (set
= single_set (insn
)))
8242 rtx insn_dest
= SET_DEST (set
);
8244 while (GET_CODE (insn_dest
) == ZERO_EXTRACT
8245 || GET_CODE (insn_dest
) == SUBREG
8246 || GET_CODE (insn_dest
) == STRICT_LOW_PART
8247 || GET_CODE (insn_dest
) == SIGN_EXTRACT
)
8248 insn_dest
= XEXP (insn_dest
, 0);
8250 if (insn_dest
!= dest
)
8252 note
= alloc_EXPR_LIST (REG_DEAD
, dest
, REG_NOTES (insn
));
8253 REG_NOTES (insn
) = note
;
8254 /* The reg only dies in one insn, the last one
8263 /* If the original dest is modifying a multiple register target, and the
8264 original instruction was split such that the original dest is now set
8265 by two or more SUBREG sets, then the split insns no longer kill the
8266 destination of the original insn.
8268 In this case, if there exists an instruction in the same basic block,
8269 before the split insn, which uses the original dest, and this use is
8270 killed by the original insn, then we must remove the REG_DEAD note on
8271 this insn, because it is now superfluous.
8273 This does not apply when a hard register gets split, because the code
8274 knows how to handle overlapping hard registers properly. */
8275 if (orig_dest
&& GET_CODE (orig_dest
) == REG
)
8277 int found_orig_dest
= 0;
8278 int found_split_dest
= 0;
8280 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8285 /* I'm not sure if this can happen, but let's be safe. */
8286 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
8289 pat
= PATTERN (insn
);
8290 i
= GET_CODE (pat
) == PARALLEL
? XVECLEN (pat
, 0) : 0;
8295 if (GET_CODE (set
) == SET
)
8297 if (GET_CODE (SET_DEST (set
)) == REG
8298 && REGNO (SET_DEST (set
)) == REGNO (orig_dest
))
8300 found_orig_dest
= 1;
8303 else if (GET_CODE (SET_DEST (set
)) == SUBREG
8304 && SUBREG_REG (SET_DEST (set
)) == orig_dest
)
8306 found_split_dest
= 1;
8312 set
= XVECEXP (pat
, 0, i
);
8319 if (found_split_dest
)
8321 /* Search backwards from FIRST, looking for the first insn that uses
8322 the original dest. Stop if we pass a CODE_LABEL or a JUMP_INSN.
8323 If we find an insn, and it has a REG_DEAD note, then delete the
8326 for (insn
= first
; insn
; insn
= PREV_INSN (insn
))
8328 if (GET_CODE (insn
) == CODE_LABEL
8329 || GET_CODE (insn
) == JUMP_INSN
)
8331 else if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i'
8332 && reg_mentioned_p (orig_dest
, insn
))
8334 note
= find_regno_note (insn
, REG_DEAD
, REGNO (orig_dest
));
8336 remove_note (insn
, note
);
8340 else if (!found_orig_dest
)
8344 /* Should never reach here for a pseudo reg. */
8345 if (REGNO (orig_dest
) >= FIRST_PSEUDO_REGISTER
)
8348 /* This can happen for a hard register, if the splitter
8349 does not bother to emit instructions which would be no-ops.
8350 We try to verify that this is the case by checking to see if
8351 the original instruction uses all of the registers that it
8352 set. This case is OK, because deleting a no-op can not affect
8353 REG_DEAD notes on other insns. If this is not the case, then
8356 regno
= REGNO (orig_dest
);
8357 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (orig_dest
)) - 1;
8359 if (! refers_to_regno_p (regno
+ i
, regno
+ i
+ 1, orig_insn
,
8367 /* Update reg_n_sets. This is necessary to prevent local alloc from
8368 converting REG_EQUAL notes to REG_EQUIV when splitting has modified
8369 a reg from set once to set multiple times. */
8372 rtx x
= PATTERN (orig_insn
);
8373 RTX_CODE code
= GET_CODE (x
);
8375 if (code
== SET
|| code
== CLOBBER
)
8376 update_n_sets (x
, -1);
8377 else if (code
== PARALLEL
)
8380 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8382 code
= GET_CODE (XVECEXP (x
, 0, i
));
8383 if (code
== SET
|| code
== CLOBBER
)
8384 update_n_sets (XVECEXP (x
, 0, i
), -1);
8388 for (insn
= first
;; insn
= NEXT_INSN (insn
))
8391 code
= GET_CODE (x
);
8393 if (code
== SET
|| code
== CLOBBER
)
8394 update_n_sets (x
, 1);
8395 else if (code
== PARALLEL
)
8398 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
8400 code
= GET_CODE (XVECEXP (x
, 0, i
));
8401 if (code
== SET
|| code
== CLOBBER
)
8402 update_n_sets (XVECEXP (x
, 0, i
), 1);
8412 /* Do the splitting of insns in the block b. */
8415 split_block_insns (b
)
8420 for (insn
= BLOCK_HEAD (b
);; insn
= next
)
8422 rtx set
, last
, first
, notes
;
8424 /* Can't use `next_real_insn' because that
8425 might go across CODE_LABELS and short-out basic blocks. */
8426 next
= NEXT_INSN (insn
);
8427 if (GET_CODE (insn
) != INSN
)
8429 if (insn
== BLOCK_END (b
))
8435 /* Don't split no-op move insns. These should silently disappear
8436 later in final. Splitting such insns would break the code
8437 that handles REG_NO_CONFLICT blocks. */
8438 set
= single_set (insn
);
8439 if (set
&& rtx_equal_p (SET_SRC (set
), SET_DEST (set
)))
8441 if (insn
== BLOCK_END (b
))
8444 /* Nops get in the way while scheduling, so delete them now if
8445 register allocation has already been done. It is too risky
8446 to try to do this before register allocation, and there are
8447 unlikely to be very many nops then anyways. */
8448 if (reload_completed
)
8450 PUT_CODE (insn
, NOTE
);
8451 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8452 NOTE_SOURCE_FILE (insn
) = 0;
8458 /* Split insns here to get max fine-grain parallelism. */
8459 first
= PREV_INSN (insn
);
8460 notes
= REG_NOTES (insn
);
8461 last
= try_split (PATTERN (insn
), insn
, 1);
8464 /* try_split returns the NOTE that INSN became. */
8465 first
= NEXT_INSN (first
);
8466 update_flow_info (notes
, first
, last
, insn
);
8468 PUT_CODE (insn
, NOTE
);
8469 NOTE_SOURCE_FILE (insn
) = 0;
8470 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
8471 if (insn
== BLOCK_HEAD (b
))
8472 BLOCK_HEAD (b
) = first
;
8473 if (insn
== BLOCK_END (b
))
8475 BLOCK_END (b
) = last
;
8480 if (insn
== BLOCK_END (b
))
8485 /* The one entry point in this file. DUMP_FILE is the dump file for
8489 schedule_insns (dump_file
)
8500 /* disable speculative loads in their presence if cc0 defined */
8502 flag_schedule_speculative_load
= 0;
8505 /* Taking care of this degenerate case makes the rest of
8506 this code simpler. */
8507 if (n_basic_blocks
== 0)
8510 /* set dump and sched_verbose for the desired debugging output. If no
8511 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
8512 For -fsched-verbose-N, N>=10, print everything to stderr. */
8513 sched_verbose
= sched_verbose_param
;
8514 if (sched_verbose_param
== 0 && dump_file
)
8516 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
8521 /* Initialize the unused_*_lists. We can't use the ones left over from
8522 the previous function, because gcc has freed that memory. We can use
8523 the ones left over from the first sched pass in the second pass however,
8524 so only clear them on the first sched pass. The first pass is before
8525 reload if flag_schedule_insns is set, otherwise it is afterwards. */
8527 if (reload_completed
== 0 || !flag_schedule_insns
)
8529 unused_insn_list
= 0;
8530 unused_expr_list
= 0;
8533 /* initialize issue_rate */
8534 issue_rate
= ISSUE_RATE
;
8536 /* do the splitting first for all blocks */
8537 for (b
= 0; b
< n_basic_blocks
; b
++)
8538 split_block_insns (b
);
8540 max_uid
= (get_max_uid () + 1);
8542 cant_move
= (char *) xmalloc (max_uid
* sizeof (char));
8543 bzero ((char *) cant_move
, max_uid
* sizeof (char));
8545 fed_by_spec_load
= (char *) xmalloc (max_uid
* sizeof (char));
8546 bzero ((char *) fed_by_spec_load
, max_uid
* sizeof (char));
8548 is_load_insn
= (char *) xmalloc (max_uid
* sizeof (char));
8549 bzero ((char *) is_load_insn
, max_uid
* sizeof (char));
8551 insn_orig_block
= (int *) xmalloc (max_uid
* sizeof (int));
8552 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
8555 for (b
= 0; b
< n_basic_blocks
; b
++)
8556 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8558 INSN_BLOCK (insn
) = b
;
8559 INSN_LUID (insn
) = luid
++;
8561 if (insn
== BLOCK_END (b
))
8565 /* after reload, remove inter-blocks dependences computed before reload. */
8566 if (reload_completed
)
8571 for (b
= 0; b
< n_basic_blocks
; b
++)
8572 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
8576 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
8579 link
= LOG_LINKS (insn
);
8582 rtx x
= XEXP (link
, 0);
8584 if (INSN_BLOCK (x
) != b
)
8586 remove_dependence (insn
, x
);
8587 link
= prev
? XEXP (prev
, 1) : LOG_LINKS (insn
);
8590 prev
= link
, link
= XEXP (prev
, 1);
8594 if (insn
== BLOCK_END (b
))
8600 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
8601 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8602 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8603 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
8605 /* compute regions for scheduling */
8606 if (reload_completed
8607 || n_basic_blocks
== 1
8608 || !flag_schedule_interblock
)
8610 find_single_block_region ();
8614 /* verify that a 'good' control flow graph can be built */
8615 if (is_cfg_nonregular ())
8617 find_single_block_region ();
8621 int_list_ptr
*s_preds
, *s_succs
;
8622 int *num_preds
, *num_succs
;
8623 sbitmap
*dom
, *pdom
;
8625 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
8626 * sizeof (int_list_ptr
));
8627 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
8628 * sizeof (int_list_ptr
));
8629 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
8630 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
8631 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8632 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
8634 /* The scheduler runs after flow; therefore, we can't blindly call
8635 back into find_basic_blocks since doing so could invalidate the
8636 info in basic_block_live_at_start.
8638 Consider a block consisting entirely of dead stores; after life
8639 analysis it would be a block of NOTE_INSN_DELETED notes. If
8640 we call find_basic_blocks again, then the block would be removed
8641 entirely and invalidate our the register live information.
8643 We could (should?) recompute register live information. Doing
8644 so may even be beneficial. */
8646 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
8648 /* Compute the dominators and post dominators. We don't currently use
8649 post dominators, but we should for speculative motion analysis. */
8650 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
8652 /* build_control_flow will return nonzero if it detects unreachable
8653 blocks or any other irregularity with the cfg which prevents
8654 cross block scheduling. */
8655 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
8656 find_single_block_region ();
8658 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
8660 if (sched_verbose
>= 3)
8663 /* For now. This will move as more and more of haifa is converted
8664 to using the cfg code in flow.c */
8671 /* Allocate data for this pass. See comments, above,
8672 for what these vectors do.
8674 We use xmalloc instead of alloca, because max_uid can be very large
8675 when there is a lot of function inlining. If we used alloca, we could
8676 exceed stack limits on some hosts for some inputs. */
8677 insn_priority
= (int *) xmalloc (max_uid
* sizeof (int));
8678 insn_reg_weight
= (int *) xmalloc (max_uid
* sizeof (int));
8679 insn_tick
= (int *) xmalloc (max_uid
* sizeof (int));
8680 insn_costs
= (short *) xmalloc (max_uid
* sizeof (short));
8681 insn_units
= (short *) xmalloc (max_uid
* sizeof (short));
8682 insn_blockage
= (unsigned int *) xmalloc (max_uid
* sizeof (unsigned int));
8683 insn_ref_count
= (int *) xmalloc (max_uid
* sizeof (int));
8685 /* Allocate for forward dependencies */
8686 insn_dep_count
= (int *) xmalloc (max_uid
* sizeof (int));
8687 insn_depend
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8689 if (reload_completed
== 0)
8693 sched_reg_n_calls_crossed
= (int *) alloca (max_regno
* sizeof (int));
8694 sched_reg_live_length
= (int *) alloca (max_regno
* sizeof (int));
8695 sched_reg_basic_block
= (int *) alloca (max_regno
* sizeof (int));
8696 bb_live_regs
= ALLOCA_REG_SET ();
8697 bzero ((char *) sched_reg_n_calls_crossed
, max_regno
* sizeof (int));
8698 bzero ((char *) sched_reg_live_length
, max_regno
* sizeof (int));
8700 for (i
= 0; i
< max_regno
; i
++)
8701 sched_reg_basic_block
[i
] = REG_BLOCK_UNKNOWN
;
8705 sched_reg_n_calls_crossed
= 0;
8706 sched_reg_live_length
= 0;
8709 init_alias_analysis ();
8711 if (write_symbols
!= NO_DEBUG
)
8715 line_note
= (rtx
*) xmalloc (max_uid
* sizeof (rtx
));
8716 bzero ((char *) line_note
, max_uid
* sizeof (rtx
));
8717 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
8718 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
8720 /* Save-line-note-head:
8721 Determine the line-number at the start of each basic block.
8722 This must be computed and saved now, because after a basic block's
8723 predecessor has been scheduled, it is impossible to accurately
8724 determine the correct line number for the first insn of the block. */
8726 for (b
= 0; b
< n_basic_blocks
; b
++)
8727 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
8728 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
8730 line_note_head
[b
] = line
;
8735 bzero ((char *) insn_priority
, max_uid
* sizeof (int));
8736 bzero ((char *) insn_reg_weight
, max_uid
* sizeof (int));
8737 bzero ((char *) insn_tick
, max_uid
* sizeof (int));
8738 bzero ((char *) insn_costs
, max_uid
* sizeof (short));
8739 bzero ((char *) insn_units
, max_uid
* sizeof (short));
8740 bzero ((char *) insn_blockage
, max_uid
* sizeof (unsigned int));
8741 bzero ((char *) insn_ref_count
, max_uid
* sizeof (int));
8743 /* Initialize for forward dependencies */
8744 bzero ((char *) insn_depend
, max_uid
* sizeof (rtx
));
8745 bzero ((char *) insn_dep_count
, max_uid
* sizeof (int));
8747 /* Find units used in this fuction, for visualization */
8749 init_target_units ();
8751 /* ??? Add a NOTE after the last insn of the last basic block. It is not
8752 known why this is done. */
8754 insn
= BLOCK_END (n_basic_blocks
- 1);
8755 if (NEXT_INSN (insn
) == 0
8756 || (GET_CODE (insn
) != NOTE
8757 && GET_CODE (insn
) != CODE_LABEL
8758 /* Don't emit a NOTE if it would end up between an unconditional
8759 jump and a BARRIER. */
8760 && !(GET_CODE (insn
) == JUMP_INSN
8761 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
8762 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
8764 /* Schedule every region in the subroutine */
8765 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
8767 schedule_region (rgn
);
8774 /* Reposition the prologue and epilogue notes in case we moved the
8775 prologue/epilogue insns. */
8776 if (reload_completed
)
8777 reposition_prologue_and_epilogue_notes (get_insns ());
8779 /* delete redundant line notes. */
8780 if (write_symbols
!= NO_DEBUG
)
8781 rm_redundant_line_notes ();
8783 /* Update information about uses of registers in the subroutine. */
8784 if (reload_completed
== 0)
8785 update_reg_usage ();
8789 if (reload_completed
== 0 && flag_schedule_interblock
)
8791 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
8799 fprintf (dump
, "\n\n");
8803 free (fed_by_spec_load
);
8804 free (is_load_insn
);
8805 free (insn_orig_block
);
8808 free (insn_priority
);
8809 free (insn_reg_weight
);
8813 free (insn_blockage
);
8814 free (insn_ref_count
);
8816 free (insn_dep_count
);
8819 if (write_symbols
!= NO_DEBUG
)
8823 FREE_REG_SET (bb_live_regs
);
8842 #endif /* INSN_SCHEDULING */