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. */
163 #include "basic-block.h"
165 #include "function.h"
166 #include "hard-reg-set.h"
168 #include "insn-config.h"
169 #include "insn-attr.h"
174 extern char *reg_known_equiv_p
;
175 extern rtx
*reg_known_value
;
177 #ifdef INSN_SCHEDULING
179 /* target_units bitmask has 1 for each unit in the cpu. It should be
180 possible to compute this variable from the machine description.
181 But currently it is computed by examining the insn list. Since
182 this is only needed for visualization, it seems an acceptable
183 solution. (For understanding the mapping of bits to units, see
184 definition of function_units[] in "insn-attrtab.c".) */
186 static int target_units
= 0;
188 /* issue_rate is the number of insns that can be scheduled in the same
189 machine cycle. It can be defined in the config/mach/mach.h file,
190 otherwise we set it to 1. */
192 static int issue_rate
;
198 /* sched-verbose controls the amount of debugging output the
199 scheduler prints. It is controlled by -fsched-verbose-N:
200 N>0 and no -DSR : the output is directed to stderr.
201 N>=10 will direct the printouts to stderr (regardless of -dSR).
203 N=2: bb's probabilities, detailed ready list info, unit/insn info.
204 N=3: rtl at abort point, control-flow, regions info.
205 N=5: dependences info. */
207 #define MAX_RGN_BLOCKS 10
208 #define MAX_RGN_INSNS 100
210 static int sched_verbose_param
= 0;
211 static int sched_verbose
= 0;
213 /* nr_inter/spec counts interblock/speculative motion for the function. */
214 static int nr_inter
, nr_spec
;
217 /* Debugging file. All printouts are sent to dump, which is always set,
218 either to stderr, or to the dump listing file (-dRS). */
219 static FILE *dump
= 0;
221 /* fix_sched_param() is called from toplev.c upon detection
222 of the -fsched-***-N options. */
225 fix_sched_param (param
, val
)
226 const char *param
, *val
;
228 if (!strcmp (param
, "verbose"))
229 sched_verbose_param
= atoi (val
);
231 warning ("fix_sched_param: unknown param: %s", param
);
235 /* Element N is the next insn that sets (hard or pseudo) register
236 N within the current basic block; or zero, if there is no
237 such insn. Needed for new registers which may be introduced
238 by splitting insns. */
239 static rtx
*reg_last_uses
;
240 static rtx
*reg_last_sets
;
241 static rtx
*reg_last_clobbers
;
242 static regset reg_pending_sets
;
243 static regset reg_pending_clobbers
;
244 static int reg_pending_sets_all
;
246 /* Vector indexed by INSN_UID giving the original ordering of the insns. */
247 static int *insn_luid
;
248 #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
250 /* To speed up the test for duplicate dependency links we keep a record
251 of true dependencies created by add_dependence when the average number
252 of instructions in a basic block is very large.
254 Studies have shown that there is typically around 5 instructions between
255 branches for typical C code. So we can make a guess that the average
256 basic block is approximately 5 instructions long; we will choose 100X
257 the average size as a very large basic block.
259 Each insn has an associated bitmap for its dependencies. Each bitmap
260 has enough entries to represent a dependency on any other insn in the
262 static sbitmap
*true_dependency_cache
;
264 /* Vector indexed by INSN_UID giving each instruction a priority. */
265 static int *insn_priority
;
266 #define INSN_PRIORITY(INSN) (insn_priority[INSN_UID (INSN)])
268 static short *insn_costs
;
269 #define INSN_COST(INSN) insn_costs[INSN_UID (INSN)]
271 /* Vector indexed by INSN_UID giving an encoding of the function units
273 static short *insn_units
;
274 #define INSN_UNIT(INSN) insn_units[INSN_UID (INSN)]
276 /* Vector indexed by INSN_UID giving each instruction a
277 register-weight. This weight is an estimation of the insn
278 contribution to registers pressure. */
279 static int *insn_reg_weight
;
280 #define INSN_REG_WEIGHT(INSN) (insn_reg_weight[INSN_UID (INSN)])
282 /* Vector indexed by INSN_UID giving list of insns which
283 depend upon INSN. Unlike LOG_LINKS, it represents forward dependences. */
284 static rtx
*insn_depend
;
285 #define INSN_DEPEND(INSN) insn_depend[INSN_UID (INSN)]
287 /* Vector indexed by INSN_UID. Initialized to the number of incoming
288 edges in forward dependence graph (= number of LOG_LINKS). As
289 scheduling procedes, dependence counts are decreased. An
290 instruction moves to the ready list when its counter is zero. */
291 static int *insn_dep_count
;
292 #define INSN_DEP_COUNT(INSN) (insn_dep_count[INSN_UID (INSN)])
294 /* Vector indexed by INSN_UID giving an encoding of the blockage range
295 function. The unit and the range are encoded. */
296 static unsigned int *insn_blockage
;
297 #define INSN_BLOCKAGE(INSN) insn_blockage[INSN_UID (INSN)]
299 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
300 #define ENCODE_BLOCKAGE(U, R) \
301 (((U) << BLOCKAGE_BITS \
302 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
303 | MAX_BLOCKAGE_COST (R))
304 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
305 #define BLOCKAGE_RANGE(B) \
306 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
307 | ((B) & BLOCKAGE_MASK))
309 /* Encodings of the `<name>_unit_blockage_range' function. */
310 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
311 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
313 #define DONE_PRIORITY -1
314 #define MAX_PRIORITY 0x7fffffff
315 #define TAIL_PRIORITY 0x7ffffffe
316 #define LAUNCH_PRIORITY 0x7f000001
317 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
318 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
320 /* Vector indexed by INSN_UID giving number of insns referring to this
322 static int *insn_ref_count
;
323 #define INSN_REF_COUNT(INSN) (insn_ref_count[INSN_UID (INSN)])
325 /* Vector indexed by INSN_UID giving line-number note in effect for each
326 insn. For line-number notes, this indicates whether the note may be
328 static rtx
*line_note
;
329 #define LINE_NOTE(INSN) (line_note[INSN_UID (INSN)])
331 /* Vector indexed by basic block number giving the starting line-number
332 for each basic block. */
333 static rtx
*line_note_head
;
335 /* List of important notes we must keep around. This is a pointer to the
336 last element in the list. */
337 static rtx note_list
;
341 /* An instruction is ready to be scheduled when all insns preceding it
342 have already been scheduled. It is important to ensure that all
343 insns which use its result will not be executed until its result
344 has been computed. An insn is maintained in one of four structures:
346 (P) the "Pending" set of insns which cannot be scheduled until
347 their dependencies have been satisfied.
348 (Q) the "Queued" set of insns that can be scheduled when sufficient
350 (R) the "Ready" list of unscheduled, uncommitted insns.
351 (S) the "Scheduled" list of insns.
353 Initially, all insns are either "Pending" or "Ready" depending on
354 whether their dependencies are satisfied.
356 Insns move from the "Ready" list to the "Scheduled" list as they
357 are committed to the schedule. As this occurs, the insns in the
358 "Pending" list have their dependencies satisfied and move to either
359 the "Ready" list or the "Queued" set depending on whether
360 sufficient time has passed to make them ready. As time passes,
361 insns move from the "Queued" set to the "Ready" list. Insns may
362 move from the "Ready" list to the "Queued" set if they are blocked
363 due to a function unit conflict.
365 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
366 insns, i.e., those that are ready, queued, and pending.
367 The "Queued" set (Q) is implemented by the variable `insn_queue'.
368 The "Ready" list (R) is implemented by the variables `ready' and
370 The "Scheduled" list (S) is the new insn chain built by this pass.
372 The transition (R->S) is implemented in the scheduling loop in
373 `schedule_block' when the best insn to schedule is chosen.
374 The transition (R->Q) is implemented in `queue_insn' when an
375 insn is found to have a function unit conflict with the already
377 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
378 insns move from the ready list to the scheduled list.
379 The transition (Q->R) is implemented in 'queue_to_insn' as time
380 passes or stalls are introduced. */
382 /* Implement a circular buffer to delay instructions until sufficient
383 time has passed. INSN_QUEUE_SIZE is a power of two larger than
384 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
385 longest time an isnsn may be queued. */
386 static rtx insn_queue
[INSN_QUEUE_SIZE
];
387 static int q_ptr
= 0;
388 static int q_size
= 0;
389 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
390 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
392 /* Vector indexed by INSN_UID giving the minimum clock tick at which
393 the insn becomes ready. This is used to note timing constraints for
394 insns in the pending list. */
395 static int *insn_tick
;
396 #define INSN_TICK(INSN) (insn_tick[INSN_UID (INSN)])
398 /* Forward declarations. */
399 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
401 static void remove_dependence
PROTO ((rtx
, rtx
));
403 static rtx find_insn_list
PROTO ((rtx
, rtx
));
404 static int insn_unit
PROTO ((rtx
));
405 static unsigned int blockage_range
PROTO ((int, rtx
));
406 static void clear_units
PROTO ((void));
407 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
408 static void schedule_unit
PROTO ((int, rtx
, int));
409 static int actual_hazard
PROTO ((int, rtx
, int, int));
410 static int potential_hazard
PROTO ((int, rtx
, int));
411 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
412 static int priority
PROTO ((rtx
));
413 static void free_pending_lists
PROTO ((void));
414 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
415 static void flush_pending_lists
PROTO ((rtx
, int));
416 static void sched_analyze_1
PROTO ((rtx
, rtx
));
417 static void sched_analyze_2
PROTO ((rtx
, rtx
));
418 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
419 static void sched_analyze
PROTO ((rtx
, rtx
));
420 static int rank_for_schedule
PROTO ((const PTR
, const PTR
));
421 static void swap_sort
PROTO ((rtx
*, int));
422 static void queue_insn
PROTO ((rtx
, int));
423 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
424 static void find_insn_reg_weight
PROTO ((int));
425 static int schedule_block
PROTO ((int, int));
426 static char *safe_concat
PROTO ((char *, char *, const char *));
427 static int insn_issue_delay
PROTO ((rtx
));
428 static void adjust_priority
PROTO ((rtx
));
430 /* Some insns (e.g. call) are not allowed to move across blocks. */
431 static char *cant_move
;
432 #define CANT_MOVE(insn) (cant_move[INSN_UID (insn)])
434 /* Control flow graph edges are kept in circular lists. */
443 static haifa_edge
*edge_table
;
445 #define NEXT_IN(edge) (edge_table[edge].next_in)
446 #define NEXT_OUT(edge) (edge_table[edge].next_out)
447 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
448 #define TO_BLOCK(edge) (edge_table[edge].to_block)
450 /* Number of edges in the control flow graph. (In fact, larger than
451 that by 1, since edge 0 is unused.) */
454 /* Circular list of incoming/outgoing edges of a block. */
455 static int *in_edges
;
456 static int *out_edges
;
458 #define IN_EDGES(block) (in_edges[block])
459 #define OUT_EDGES(block) (out_edges[block])
463 static int is_cfg_nonregular
PROTO ((void));
464 static int build_control_flow
PROTO ((int_list_ptr
*, int_list_ptr
*,
466 static void new_edge
PROTO ((int, int));
469 /* A region is the main entity for interblock scheduling: insns
470 are allowed to move between blocks in the same region, along
471 control flow graph edges, in the 'up' direction. */
474 int rgn_nr_blocks
; /* Number of blocks in region. */
475 int rgn_blocks
; /* cblocks in the region (actually index in rgn_bb_table). */
479 /* Number of regions in the procedure. */
480 static int nr_regions
;
482 /* Table of region descriptions. */
483 static region
*rgn_table
;
485 /* Array of lists of regions' blocks. */
486 static int *rgn_bb_table
;
488 /* Topological order of blocks in the region (if b2 is reachable from
489 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
490 always referred to by either block or b, while its topological
491 order name (in the region) is refered to by bb. */
492 static int *block_to_bb
;
494 /* The number of the region containing a block. */
495 static int *containing_rgn
;
497 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
498 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
499 #define BLOCK_TO_BB(block) (block_to_bb[block])
500 #define CONTAINING_RGN(block) (containing_rgn[block])
502 void debug_regions
PROTO ((void));
503 static void find_single_block_region
PROTO ((void));
504 static void find_rgns
PROTO ((int_list_ptr
*, int_list_ptr
*,
505 int *, int *, sbitmap
*));
506 static int too_large
PROTO ((int, int *, int *));
508 extern void debug_live
PROTO ((int, int));
510 /* Blocks of the current region being scheduled. */
511 static int current_nr_blocks
;
512 static int current_blocks
;
514 /* The mapping from bb to block. */
515 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
518 /* Bit vectors and bitset operations are needed for computations on
519 the control flow graph. */
521 typedef unsigned HOST_WIDE_INT
*bitset
;
524 int *first_member
; /* Pointer to the list start in bitlst_table. */
525 int nr_members
; /* The number of members of the bit list. */
529 static int bitlst_table_last
;
530 static int bitlst_table_size
;
531 static int *bitlst_table
;
533 static char bitset_member
PROTO ((bitset
, int, int));
534 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
536 /* Target info declarations.
538 The block currently being scheduled is referred to as the "target" block,
539 while other blocks in the region from which insns can be moved to the
540 target are called "source" blocks. The candidate structure holds info
541 about such sources: are they valid? Speculative? Etc. */
542 typedef bitlst bblst
;
553 static candidate
*candidate_table
;
555 /* A speculative motion requires checking live information on the path
556 from 'source' to 'target'. The split blocks are those to be checked.
557 After a speculative motion, live information should be modified in
560 Lists of split and update blocks for each candidate of the current
561 target are in array bblst_table. */
562 static int *bblst_table
, bblst_size
, bblst_last
;
564 #define IS_VALID(src) ( candidate_table[src].is_valid )
565 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
566 #define SRC_PROB(src) ( candidate_table[src].src_prob )
568 /* The bb being currently scheduled. */
569 static int target_bb
;
572 typedef bitlst edgelst
;
574 /* Target info functions. */
575 static void split_edges
PROTO ((int, int, edgelst
*));
576 static void compute_trg_info
PROTO ((int));
577 void debug_candidate
PROTO ((int));
578 void debug_candidates
PROTO ((int));
581 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
582 typedef bitset bbset
;
584 /* Number of words of the bbset. */
585 static int bbset_size
;
587 /* Dominators array: dom[i] contains the bbset of dominators of
588 bb i in the region. */
591 /* bb 0 is the only region entry. */
592 #define IS_RGN_ENTRY(bb) (!bb)
594 /* Is bb_src dominated by bb_trg. */
595 #define IS_DOMINATED(bb_src, bb_trg) \
596 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
598 /* Probability: Prob[i] is a float in [0, 1] which is the probability
599 of bb i relative to the region entry. */
602 /* The probability of bb_src, relative to bb_trg. Note, that while the
603 'prob[bb]' is a float in [0, 1], this macro returns an integer
605 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
608 /* Bit-set of edges, where bit i stands for edge i. */
609 typedef bitset edgeset
;
611 /* Number of edges in the region. */
612 static int rgn_nr_edges
;
614 /* Array of size rgn_nr_edges. */
615 static int *rgn_edges
;
617 /* Number of words in an edgeset. */
618 static int edgeset_size
;
620 /* Mapping from each edge in the graph to its number in the rgn. */
621 static int *edge_to_bit
;
622 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
624 /* The split edges of a source bb is different for each target
625 bb. In order to compute this efficiently, the 'potential-split edges'
626 are computed for each bb prior to scheduling a region. This is actually
627 the split edges of each bb relative to the region entry.
629 pot_split[bb] is the set of potential split edges of bb. */
630 static edgeset
*pot_split
;
632 /* For every bb, a set of its ancestor edges. */
633 static edgeset
*ancestor_edges
;
635 static void compute_dom_prob_ps
PROTO ((int));
637 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
638 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
639 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
640 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
642 /* Parameters affecting the decision of rank_for_schedule(). */
643 #define MIN_DIFF_PRIORITY 2
644 #define MIN_PROBABILITY 40
645 #define MIN_PROB_DIFF 10
647 /* Speculative scheduling functions. */
648 static int check_live_1
PROTO ((int, rtx
));
649 static void update_live_1
PROTO ((int, rtx
));
650 static int check_live
PROTO ((rtx
, int));
651 static void update_live
PROTO ((rtx
, int));
652 static void set_spec_fed
PROTO ((rtx
));
653 static int is_pfree
PROTO ((rtx
, int, int));
654 static int find_conditional_protection
PROTO ((rtx
, int));
655 static int is_conditionally_protected
PROTO ((rtx
, int, int));
656 static int may_trap_exp
PROTO ((rtx
, int));
657 static int haifa_classify_insn
PROTO ((rtx
));
658 static int is_prisky
PROTO ((rtx
, int, int));
659 static int is_exception_free
PROTO ((rtx
, int, int));
661 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
662 static void compute_block_forward_dependences
PROTO ((int));
663 static void init_rgn_data_dependences
PROTO ((int));
664 static void add_branch_dependences
PROTO ((rtx
, rtx
));
665 static void compute_block_backward_dependences
PROTO ((int));
666 void debug_dependencies
PROTO ((void));
668 /* Notes handling mechanism:
669 =========================
670 Generally, NOTES are saved before scheduling and restored after scheduling.
671 The scheduler distinguishes between three types of notes:
673 (1) LINE_NUMBER notes, generated and used for debugging. Here,
674 before scheduling a region, a pointer to the LINE_NUMBER note is
675 added to the insn following it (in save_line_notes()), and the note
676 is removed (in rm_line_notes() and unlink_line_notes()). After
677 scheduling the region, this pointer is used for regeneration of
678 the LINE_NUMBER note (in restore_line_notes()).
680 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
681 Before scheduling a region, a pointer to the note is added to the insn
682 that follows or precedes it. (This happens as part of the data dependence
683 computation). After scheduling an insn, the pointer contained in it is
684 used for regenerating the corresponding note (in reemit_notes).
686 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
687 these notes are put in a list (in rm_other_notes() and
688 unlink_other_notes ()). After scheduling the block, these notes are
689 inserted at the beginning of the block (in schedule_block()). */
691 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
692 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
693 static void rm_line_notes
PROTO ((int));
694 static void save_line_notes
PROTO ((int));
695 static void restore_line_notes
PROTO ((int));
696 static void rm_redundant_line_notes
PROTO ((void));
697 static void rm_other_notes
PROTO ((rtx
, rtx
));
698 static rtx reemit_notes
PROTO ((rtx
, rtx
));
700 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
701 static void get_bb_head_tail
PROTO ((int, rtx
*, rtx
*));
703 static int queue_to_ready
PROTO ((rtx
[], int));
705 static void debug_ready_list
PROTO ((rtx
[], int));
706 static void init_target_units
PROTO ((void));
707 static void insn_print_units
PROTO ((rtx
));
708 static int get_visual_tbl_length
PROTO ((void));
709 static void init_block_visualization
PROTO ((void));
710 static void print_block_visualization
PROTO ((int, const char *));
711 static void visualize_scheduled_insns
PROTO ((int, int));
712 static void visualize_no_unit
PROTO ((rtx
));
713 static void visualize_stall_cycles
PROTO ((int, int));
714 static void print_exp
PROTO ((char *, rtx
, int));
715 static void print_value
PROTO ((char *, rtx
, int));
716 static void print_pattern
PROTO ((char *, rtx
, int));
717 static void print_insn
PROTO ((char *, rtx
, int));
718 void debug_reg_vector
PROTO ((regset
));
720 static rtx move_insn1
PROTO ((rtx
, rtx
));
721 static rtx move_insn
PROTO ((rtx
, rtx
));
722 static rtx group_leader
PROTO ((rtx
));
723 static int set_priorities
PROTO ((int));
724 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
725 static void schedule_region
PROTO ((int));
727 #endif /* INSN_SCHEDULING */
729 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
731 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
732 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
733 of dependence that this link represents. */
736 add_dependence (insn
, elem
, dep_type
)
739 enum reg_note dep_type
;
743 /* Don't depend an insn on itself. */
747 /* We can get a dependency on deleted insns due to optimizations in
748 the register allocation and reloading or due to splitting. Any
749 such dependency is useless and can be ignored. */
750 if (GET_CODE (elem
) == NOTE
)
753 /* If elem is part of a sequence that must be scheduled together, then
754 make the dependence point to the last insn of the sequence.
755 When HAVE_cc0, it is possible for NOTEs to exist between users and
756 setters of the condition codes, so we must skip past notes here.
757 Otherwise, NOTEs are impossible here. */
759 next
= NEXT_INSN (elem
);
762 while (next
&& GET_CODE (next
) == NOTE
)
763 next
= NEXT_INSN (next
);
766 if (next
&& SCHED_GROUP_P (next
)
767 && GET_CODE (next
) != CODE_LABEL
)
769 /* Notes will never intervene here though, so don't bother checking
771 /* We must reject CODE_LABELs, so that we don't get confused by one
772 that has LABEL_PRESERVE_P set, which is represented by the same
773 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
775 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
776 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
777 next
= NEXT_INSN (next
);
779 /* Again, don't depend an insn on itself. */
783 /* Make the dependence to NEXT, the last insn of the group, instead
784 of the original ELEM. */
788 #ifdef INSN_SCHEDULING
789 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
790 No need for interblock dependences with calls, since
791 calls are not moved between blocks. Note: the edge where
792 elem is a CALL is still required. */
793 if (GET_CODE (insn
) == CALL_INSN
794 && (INSN_BB (elem
) != INSN_BB (insn
)))
798 /* If we already have a true dependency for ELEM, then we do not
799 need to do anything. Avoiding the list walk below can cut
800 compile times dramatically for some code. */
801 if (true_dependency_cache
802 && TEST_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
)))
806 /* Check that we don't already have this dependence. */
807 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
808 if (XEXP (link
, 0) == elem
)
810 /* If this is a more restrictive type of dependence than the existing
811 one, then change the existing dependence to this type. */
812 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
813 PUT_REG_NOTE_KIND (link
, dep_type
);
815 #ifdef INSN_SCHEDULING
816 /* If we are adding a true dependency to INSN's LOG_LINKs, then
817 note that in the bitmap cache of true dependency information. */
818 if ((int)dep_type
== 0 && true_dependency_cache
)
819 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
823 /* Might want to check one level of transitivity to save conses. */
825 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
826 LOG_LINKS (insn
) = link
;
828 /* Insn dependency, not data dependency. */
829 PUT_REG_NOTE_KIND (link
, dep_type
);
833 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
834 of INSN. Abort if not found. */
837 remove_dependence (insn
, elem
)
841 rtx prev
, link
, next
;
844 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
846 next
= XEXP (link
, 1);
847 if (XEXP (link
, 0) == elem
)
850 XEXP (prev
, 1) = next
;
852 LOG_LINKS (insn
) = next
;
854 #ifdef INSN_SCHEDULING
855 /* If we are removing a true dependency from the LOG_LINKS list,
856 make sure to remove it from the cache too. */
857 if (REG_NOTE_KIND (link
) == 0 && true_dependency_cache
)
858 RESET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
862 free_INSN_LIST_node (link
);
874 #endif /* HAVE_cc0 */
876 #ifndef INSN_SCHEDULING
878 schedule_insns (dump_file
)
888 #define HAIFA_INLINE __inline
891 /* Computation of memory dependencies. */
893 /* The *_insns and *_mems are paired lists. Each pending memory operation
894 will have a pointer to the MEM rtx on one list and a pointer to the
895 containing insn on the other list in the same place in the list. */
897 /* We can't use add_dependence like the old code did, because a single insn
898 may have multiple memory accesses, and hence needs to be on the list
899 once for each memory access. Add_dependence won't let you add an insn
900 to a list more than once. */
902 /* An INSN_LIST containing all insns with pending read operations. */
903 static rtx pending_read_insns
;
905 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
906 static rtx pending_read_mems
;
908 /* An INSN_LIST containing all insns with pending write operations. */
909 static rtx pending_write_insns
;
911 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
912 static rtx pending_write_mems
;
914 /* Indicates the combined length of the two pending lists. We must prevent
915 these lists from ever growing too large since the number of dependencies
916 produced is at least O(N*N), and execution time is at least O(4*N*N), as
917 a function of the length of these pending lists. */
919 static int pending_lists_length
;
921 /* The last insn upon which all memory references must depend.
922 This is an insn which flushed the pending lists, creating a dependency
923 between it and all previously pending memory references. This creates
924 a barrier (or a checkpoint) which no memory reference is allowed to cross.
926 This includes all non constant CALL_INSNs. When we do interprocedural
927 alias analysis, this restriction can be relaxed.
928 This may also be an INSN that writes memory if the pending lists grow
931 static rtx last_pending_memory_flush
;
933 /* The last function call we have seen. All hard regs, and, of course,
934 the last function call, must depend on this. */
936 static rtx last_function_call
;
938 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
939 that does not already cross a call. We create dependencies between each
940 of those insn and the next call insn, to ensure that they won't cross a call
941 after scheduling is done. */
943 static rtx sched_before_next_call
;
945 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
946 so that insns independent of the last scheduled insn will be preferred
947 over dependent instructions. */
949 static rtx last_scheduled_insn
;
951 /* Data structures for the computation of data dependences in a regions. We
952 keep one copy of each of the declared above variables for each bb in the
953 region. Before analyzing the data dependences for a bb, its variables
954 are initialized as a function of the variables of its predecessors. When
955 the analysis for a bb completes, we save the contents of each variable X
956 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
957 copied to bb_pending_read_insns[bb]. Another change is that few
958 variables are now a list of insns rather than a single insn:
959 last_pending_memory_flash, last_function_call, reg_last_sets. The
960 manipulation of these variables was changed appropriately. */
962 static rtx
**bb_reg_last_uses
;
963 static rtx
**bb_reg_last_sets
;
964 static rtx
**bb_reg_last_clobbers
;
966 static rtx
*bb_pending_read_insns
;
967 static rtx
*bb_pending_read_mems
;
968 static rtx
*bb_pending_write_insns
;
969 static rtx
*bb_pending_write_mems
;
970 static int *bb_pending_lists_length
;
972 static rtx
*bb_last_pending_memory_flush
;
973 static rtx
*bb_last_function_call
;
974 static rtx
*bb_sched_before_next_call
;
976 /* Functions for construction of the control flow graph. */
978 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
980 We decide not to build the control flow graph if there is possibly more
981 than one entry to the function, if computed branches exist, of if we
982 have nonlocal gotos. */
991 /* If we have a label that could be the target of a nonlocal goto, then
992 the cfg is not well structured. */
993 if (nonlocal_goto_handler_labels
)
996 /* If we have any forced labels, then the cfg is not well structured. */
1000 /* If this function has a computed jump, then we consider the cfg
1001 not well structured. */
1002 if (current_function_has_computed_jump
)
1005 /* If we have exception handlers, then we consider the cfg not well
1006 structured. ?!? We should be able to handle this now that flow.c
1007 computes an accurate cfg for EH. */
1008 if (exception_handler_labels
)
1011 /* If we have non-jumping insns which refer to labels, then we consider
1012 the cfg not well structured. */
1013 /* Check for labels referred to other thn by jumps. */
1014 for (b
= 0; b
< n_basic_blocks
; b
++)
1015 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1017 code
= GET_CODE (insn
);
1018 if (GET_RTX_CLASS (code
) == 'i')
1022 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1023 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1027 if (insn
== BLOCK_END (b
))
1031 /* All the tests passed. Consider the cfg well structured. */
1035 /* Build the control flow graph and set nr_edges.
1037 Instead of trying to build a cfg ourselves, we rely on flow to
1038 do it for us. Stamp out useless code (and bug) duplication.
1040 Return nonzero if an irregularity in the cfg is found which would
1041 prevent cross block scheduling. */
1044 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1045 int_list_ptr
*s_preds
;
1046 int_list_ptr
*s_succs
;
1054 /* Count the number of edges in the cfg. */
1057 for (i
= 0; i
< n_basic_blocks
; i
++)
1059 nr_edges
+= num_succs
[i
];
1061 /* Unreachable loops with more than one basic block are detected
1062 during the DFS traversal in find_rgns.
1064 Unreachable loops with a single block are detected here. This
1065 test is redundant with the one in find_rgns, but it's much
1066 cheaper to go ahead and catch the trivial case here. */
1067 if (num_preds
[i
] == 0
1068 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1072 /* Account for entry/exit edges. */
1075 in_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1076 out_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1077 edge_table
= (haifa_edge
*) xcalloc (nr_edges
, sizeof (haifa_edge
));
1080 for (i
= 0; i
< n_basic_blocks
; i
++)
1081 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1083 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1084 new_edge (i
, INT_LIST_VAL (succ
));
1087 /* Increment by 1, since edge 0 is unused. */
1094 /* Record an edge in the control flow graph from SOURCE to TARGET.
1096 In theory, this is redundant with the s_succs computed above, but
1097 we have not converted all of haifa to use information from the
1101 new_edge (source
, target
)
1105 int curr_edge
, fst_edge
;
1107 /* Check for duplicates. */
1108 fst_edge
= curr_edge
= OUT_EDGES (source
);
1111 if (FROM_BLOCK (curr_edge
) == source
1112 && TO_BLOCK (curr_edge
) == target
)
1117 curr_edge
= NEXT_OUT (curr_edge
);
1119 if (fst_edge
== curr_edge
)
1125 FROM_BLOCK (e
) = source
;
1126 TO_BLOCK (e
) = target
;
1128 if (OUT_EDGES (source
))
1130 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1131 NEXT_OUT (OUT_EDGES (source
)) = e
;
1132 NEXT_OUT (e
) = next_edge
;
1136 OUT_EDGES (source
) = e
;
1140 if (IN_EDGES (target
))
1142 next_edge
= NEXT_IN (IN_EDGES (target
));
1143 NEXT_IN (IN_EDGES (target
)) = e
;
1144 NEXT_IN (e
) = next_edge
;
1148 IN_EDGES (target
) = e
;
1154 /* BITSET macros for operations on the control flow graph. */
1156 /* Compute bitwise union of two bitsets. */
1157 #define BITSET_UNION(set1, set2, len) \
1158 do { register bitset tp = set1, sp = set2; \
1160 for (i = 0; i < len; i++) \
1161 *(tp++) |= *(sp++); } while (0)
1163 /* Compute bitwise intersection of two bitsets. */
1164 #define BITSET_INTER(set1, set2, len) \
1165 do { register bitset tp = set1, sp = set2; \
1167 for (i = 0; i < len; i++) \
1168 *(tp++) &= *(sp++); } while (0)
1170 /* Compute bitwise difference of two bitsets. */
1171 #define BITSET_DIFFER(set1, set2, len) \
1172 do { register bitset tp = set1, sp = set2; \
1174 for (i = 0; i < len; i++) \
1175 *(tp++) &= ~*(sp++); } while (0)
1177 /* Inverts every bit of bitset 'set'. */
1178 #define BITSET_INVERT(set, len) \
1179 do { register bitset tmpset = set; \
1181 for (i = 0; i < len; i++, tmpset++) \
1182 *tmpset = ~*tmpset; } while (0)
1184 /* Turn on the index'th bit in bitset set. */
1185 #define BITSET_ADD(set, index, len) \
1187 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1190 set[index/HOST_BITS_PER_WIDE_INT] |= \
1191 1 << (index % HOST_BITS_PER_WIDE_INT); \
1194 /* Turn off the index'th bit in set. */
1195 #define BITSET_REMOVE(set, index, len) \
1197 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1200 set[index/HOST_BITS_PER_WIDE_INT] &= \
1201 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1205 /* Check if the index'th bit in bitset set is on. */
1208 bitset_member (set
, index
, len
)
1212 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1214 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1215 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1219 /* Translate a bit-set SET to a list BL of the bit-set members. */
1222 extract_bitlst (set
, len
, bl
)
1228 unsigned HOST_WIDE_INT word
;
1230 /* bblst table space is reused in each call to extract_bitlst. */
1231 bitlst_table_last
= 0;
1233 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1236 for (i
= 0; i
< len
; i
++)
1239 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1240 for (j
= 0; word
; j
++)
1244 bitlst_table
[bitlst_table_last
++] = offset
;
1255 /* Functions for the construction of regions. */
1257 /* Print the regions, for debugging purposes. Callable from debugger. */
1264 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1265 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1267 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1268 rgn_table
[rgn
].rgn_nr_blocks
);
1269 fprintf (dump
, ";;\tbb/block: ");
1271 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1273 current_blocks
= RGN_BLOCKS (rgn
);
1275 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1278 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1281 fprintf (dump
, "\n\n");
1286 /* Build a single block region for each basic block in the function.
1287 This allows for using the same code for interblock and basic block
1291 find_single_block_region ()
1295 for (i
= 0; i
< n_basic_blocks
; i
++)
1297 rgn_bb_table
[i
] = i
;
1298 RGN_NR_BLOCKS (i
) = 1;
1300 CONTAINING_RGN (i
) = i
;
1301 BLOCK_TO_BB (i
) = 0;
1303 nr_regions
= n_basic_blocks
;
1307 /* Update number of blocks and the estimate for number of insns
1308 in the region. Return 1 if the region is "too large" for interblock
1309 scheduling (compile time considerations), otherwise return 0. */
1312 too_large (block
, num_bbs
, num_insns
)
1313 int block
, *num_bbs
, *num_insns
;
1316 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1317 INSN_LUID (BLOCK_HEAD (block
)));
1318 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1325 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1326 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1327 loop containing blk. */
1328 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1330 if (max_hdr[blk] == -1) \
1331 max_hdr[blk] = hdr; \
1332 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1333 RESET_BIT (inner, hdr); \
1334 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1336 RESET_BIT (inner,max_hdr[blk]); \
1337 max_hdr[blk] = hdr; \
1342 /* Find regions for interblock scheduling.
1344 A region for scheduling can be:
1346 * A loop-free procedure, or
1348 * A reducible inner loop, or
1350 * A basic block not contained in any other region.
1353 ?!? In theory we could build other regions based on extended basic
1354 blocks or reverse extended basic blocks. Is it worth the trouble?
1356 Loop blocks that form a region are put into the region's block list
1357 in topological order.
1359 This procedure stores its results into the following global (ick) variables
1368 We use dominator relationships to avoid making regions out of non-reducible
1371 This procedure needs to be converted to work on pred/succ lists instead
1372 of edge tables. That would simplify it somewhat. */
1375 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1376 int_list_ptr
*s_preds
;
1377 int_list_ptr
*s_succs
;
1382 int *max_hdr
, *dfs_nr
, *stack
, *queue
, *degree
;
1384 int node
, child
, loop_head
, i
, head
, tail
;
1385 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1386 int num_bbs
, num_insns
, unreachable
;
1387 int too_large_failure
;
1389 /* Note if an edge has been passed. */
1392 /* Note if a block is a natural loop header. */
1395 /* Note if a block is an natural inner loop header. */
1398 /* Note if a block is in the block queue. */
1401 /* Note if a block is in the block queue. */
1404 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1405 and a mapping from block to its loop header (if the block is contained
1406 in a loop, else -1).
1408 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1409 be used as inputs to the second traversal.
1411 STACK, SP and DFS_NR are only used during the first traversal. */
1413 /* Allocate and initialize variables for the first traversal. */
1414 max_hdr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1415 dfs_nr
= (int *) alloca (n_basic_blocks
* sizeof (int));
1416 bzero ((char *) dfs_nr
, n_basic_blocks
* sizeof (int));
1417 stack
= (int *) alloca (nr_edges
* sizeof (int));
1419 inner
= sbitmap_alloc (n_basic_blocks
);
1420 sbitmap_ones (inner
);
1422 header
= sbitmap_alloc (n_basic_blocks
);
1423 sbitmap_zero (header
);
1425 passed
= sbitmap_alloc (nr_edges
);
1426 sbitmap_zero (passed
);
1428 in_queue
= sbitmap_alloc (n_basic_blocks
);
1429 sbitmap_zero (in_queue
);
1431 in_stack
= sbitmap_alloc (n_basic_blocks
);
1432 sbitmap_zero (in_stack
);
1434 for (i
= 0; i
< n_basic_blocks
; i
++)
1437 /* DFS traversal to find inner loops in the cfg. */
1442 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1444 /* We have reached a leaf node or a node that was already
1445 processed. Pop edges off the stack until we find
1446 an edge that has not yet been processed. */
1448 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1450 /* Pop entry off the stack. */
1451 current_edge
= stack
[sp
--];
1452 node
= FROM_BLOCK (current_edge
);
1453 child
= TO_BLOCK (current_edge
);
1454 RESET_BIT (in_stack
, child
);
1455 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1456 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1457 current_edge
= NEXT_OUT (current_edge
);
1460 /* See if have finished the DFS tree traversal. */
1461 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1464 /* Nope, continue the traversal with the popped node. */
1468 /* Process a node. */
1469 node
= FROM_BLOCK (current_edge
);
1470 child
= TO_BLOCK (current_edge
);
1471 SET_BIT (in_stack
, node
);
1472 dfs_nr
[node
] = ++count
;
1474 /* If the successor is in the stack, then we've found a loop.
1475 Mark the loop, if it is not a natural loop, then it will
1476 be rejected during the second traversal. */
1477 if (TEST_BIT (in_stack
, child
))
1480 SET_BIT (header
, child
);
1481 UPDATE_LOOP_RELATIONS (node
, child
);
1482 SET_BIT (passed
, current_edge
);
1483 current_edge
= NEXT_OUT (current_edge
);
1487 /* If the child was already visited, then there is no need to visit
1488 it again. Just update the loop relationships and restart
1492 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1493 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1494 SET_BIT (passed
, current_edge
);
1495 current_edge
= NEXT_OUT (current_edge
);
1499 /* Push an entry on the stack and continue DFS traversal. */
1500 stack
[++sp
] = current_edge
;
1501 SET_BIT (passed
, current_edge
);
1502 current_edge
= OUT_EDGES (child
);
1504 /* This is temporary until haifa is converted to use rth's new
1505 cfg routines which have true entry/exit blocks and the
1506 appropriate edges from/to those blocks.
1508 Generally we update dfs_nr for a node when we process its
1509 out edge. However, if the node has no out edge then we will
1510 not set dfs_nr for that node. This can confuse the scheduler
1511 into thinking that we have unreachable blocks, which in turn
1512 disables cross block scheduling.
1514 So, if we have a node with no out edges, go ahead and mark it
1515 as reachable now. */
1516 if (current_edge
== 0)
1517 dfs_nr
[child
] = ++count
;
1520 /* Another check for unreachable blocks. The earlier test in
1521 is_cfg_nonregular only finds unreachable blocks that do not
1524 The DFS traversal will mark every block that is reachable from
1525 the entry node by placing a nonzero value in dfs_nr. Thus if
1526 dfs_nr is zero for any block, then it must be unreachable. */
1528 for (i
= 0; i
< n_basic_blocks
; i
++)
1535 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1536 to hold degree counts. */
1539 /* Compute the in-degree of every block in the graph. */
1540 for (i
= 0; i
< n_basic_blocks
; i
++)
1541 degree
[i
] = num_preds
[i
];
1543 /* Do not perform region scheduling if there are any unreachable
1548 SET_BIT (header
, 0);
1550 /* Second travsersal:find reducible inner loops and topologically sort
1551 block of each region. */
1553 queue
= (int *) alloca (n_basic_blocks
* sizeof (int));
1555 /* Find blocks which are inner loop headers. We still have non-reducible
1556 loops to consider at this point. */
1557 for (i
= 0; i
< n_basic_blocks
; i
++)
1559 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1564 /* Now check that the loop is reducible. We do this separate
1565 from finding inner loops so that we do not find a reducible
1566 loop which contains an inner non-reducible loop.
1568 A simple way to find reducible/natural loops is to verify
1569 that each block in the loop is dominated by the loop
1572 If there exists a block that is not dominated by the loop
1573 header, then the block is reachable from outside the loop
1574 and thus the loop is not a natural loop. */
1575 for (j
= 0; j
< n_basic_blocks
; j
++)
1577 /* First identify blocks in the loop, except for the loop
1579 if (i
== max_hdr
[j
] && i
!= j
)
1581 /* Now verify that the block is dominated by the loop
1583 if (!TEST_BIT (dom
[j
], i
))
1588 /* If we exited the loop early, then I is the header of
1589 a non-reducible loop and we should quit processing it
1591 if (j
!= n_basic_blocks
)
1594 /* I is a header of an inner loop, or block 0 in a subroutine
1595 with no loops at all. */
1597 too_large_failure
= 0;
1598 loop_head
= max_hdr
[i
];
1600 /* Decrease degree of all I's successors for topological
1602 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1603 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1604 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1605 --degree
[INT_LIST_VAL(ps
)];
1607 /* Estimate # insns, and count # blocks in the region. */
1609 num_insns
= (INSN_LUID (BLOCK_END (i
))
1610 - INSN_LUID (BLOCK_HEAD (i
)));
1613 /* Find all loop latches (blocks with back edges to the loop
1614 header) or all the leaf blocks in the cfg has no loops.
1616 Place those blocks into the queue. */
1619 for (j
= 0; j
< n_basic_blocks
; j
++)
1620 /* Leaf nodes have only a single successor which must
1622 if (num_succs
[j
] == 1
1623 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1626 SET_BIT (in_queue
, j
);
1628 if (too_large (j
, &num_bbs
, &num_insns
))
1630 too_large_failure
= 1;
1639 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1641 node
= INT_LIST_VAL (ps
);
1643 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1646 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1648 /* This is a loop latch. */
1649 queue
[++tail
] = node
;
1650 SET_BIT (in_queue
, node
);
1652 if (too_large (node
, &num_bbs
, &num_insns
))
1654 too_large_failure
= 1;
1662 /* Now add all the blocks in the loop to the queue.
1664 We know the loop is a natural loop; however the algorithm
1665 above will not always mark certain blocks as being in the
1674 The algorithm in the DFS traversal may not mark B & D as part
1675 of the loop (ie they will not have max_hdr set to A).
1677 We know they can not be loop latches (else they would have
1678 had max_hdr set since they'd have a backedge to a dominator
1679 block). So we don't need them on the initial queue.
1681 We know they are part of the loop because they are dominated
1682 by the loop header and can be reached by a backwards walk of
1683 the edges starting with nodes on the initial queue.
1685 It is safe and desirable to include those nodes in the
1686 loop/scheduling region. To do so we would need to decrease
1687 the degree of a node if it is the target of a backedge
1688 within the loop itself as the node is placed in the queue.
1690 We do not do this because I'm not sure that the actual
1691 scheduling code will properly handle this case. ?!? */
1693 while (head
< tail
&& !too_large_failure
)
1696 child
= queue
[++head
];
1698 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1700 node
= INT_LIST_VAL (ps
);
1702 /* See discussion above about nodes not marked as in
1703 this loop during the initial DFS traversal. */
1704 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1705 || max_hdr
[node
] != loop_head
)
1710 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1712 queue
[++tail
] = node
;
1713 SET_BIT (in_queue
, node
);
1715 if (too_large (node
, &num_bbs
, &num_insns
))
1717 too_large_failure
= 1;
1724 if (tail
>= 0 && !too_large_failure
)
1726 /* Place the loop header into list of region blocks. */
1728 rgn_bb_table
[idx
] = i
;
1729 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1730 RGN_BLOCKS (nr_regions
) = idx
++;
1731 CONTAINING_RGN (i
) = nr_regions
;
1732 BLOCK_TO_BB (i
) = count
= 0;
1734 /* Remove blocks from queue[] when their in degree
1735 becomes zero. Repeat until no blocks are left on the
1736 list. This produces a topological list of blocks in
1744 child
= queue
[head
];
1745 if (degree
[child
] == 0)
1748 rgn_bb_table
[idx
++] = child
;
1749 BLOCK_TO_BB (child
) = ++count
;
1750 CONTAINING_RGN (child
) = nr_regions
;
1751 queue
[head
] = queue
[tail
--];
1753 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1754 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1755 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1756 --degree
[INT_LIST_VAL (ps
)];
1767 /* Any block that did not end up in a region is placed into a region
1769 for (i
= 0; i
< n_basic_blocks
; i
++)
1772 rgn_bb_table
[idx
] = i
;
1773 RGN_NR_BLOCKS (nr_regions
) = 1;
1774 RGN_BLOCKS (nr_regions
) = idx
++;
1775 CONTAINING_RGN (i
) = nr_regions
++;
1776 BLOCK_TO_BB (i
) = 0;
1787 /* Functions for regions scheduling information. */
1789 /* Compute dominators, probability, and potential-split-edges of bb.
1790 Assume that these values were already computed for bb's predecessors. */
1793 compute_dom_prob_ps (bb
)
1796 int nxt_in_edge
, fst_in_edge
, pred
;
1797 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1800 if (IS_RGN_ENTRY (bb
))
1802 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1807 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1809 /* Intialize dom[bb] to '111..1'. */
1810 BITSET_INVERT (dom
[bb
], bbset_size
);
1814 pred
= FROM_BLOCK (nxt_in_edge
);
1815 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1817 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1820 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1823 nr_rgn_out_edges
= 0;
1824 fst_out_edge
= OUT_EDGES (pred
);
1825 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1826 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1829 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1831 /* The successor doesn't belong in the region? */
1832 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1833 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1836 while (fst_out_edge
!= nxt_out_edge
)
1839 /* The successor doesn't belong in the region? */
1840 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1841 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1843 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1844 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1848 /* Now nr_rgn_out_edges is the number of region-exit edges from
1849 pred, and nr_out_edges will be the number of pred out edges
1850 not leaving the region. */
1851 nr_out_edges
-= nr_rgn_out_edges
;
1852 if (nr_rgn_out_edges
> 0)
1853 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1855 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1856 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1858 while (fst_in_edge
!= nxt_in_edge
);
1860 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1861 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1863 if (sched_verbose
>= 2)
1864 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1865 } /* compute_dom_prob_ps */
1867 /* Functions for target info. */
1869 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1870 Note that bb_trg dominates bb_src. */
1873 split_edges (bb_src
, bb_trg
, bl
)
1878 int es
= edgeset_size
;
1879 edgeset src
= (edgeset
) alloca (es
* sizeof (HOST_WIDE_INT
));
1882 src
[es
] = (pot_split
[bb_src
])[es
];
1883 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1884 extract_bitlst (src
, edgeset_size
, bl
);
1888 /* Find the valid candidate-source-blocks for the target block TRG, compute
1889 their probability, and check if they are speculative or not.
1890 For speculative sources, compute their update-blocks and split-blocks. */
1893 compute_trg_info (trg
)
1896 register candidate
*sp
;
1898 int check_block
, update_idx
;
1899 int i
, j
, k
, fst_edge
, nxt_edge
;
1901 /* Define some of the fields for the target bb as well. */
1902 sp
= candidate_table
+ trg
;
1904 sp
->is_speculative
= 0;
1907 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1909 sp
= candidate_table
+ i
;
1911 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1914 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1915 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1920 split_edges (i
, trg
, &el
);
1921 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1922 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1928 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1929 sp
->split_bbs
.nr_members
= el
.nr_members
;
1930 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1931 bblst_table
[bblst_last
] =
1932 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1933 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1935 for (j
= 0; j
< el
.nr_members
; j
++)
1937 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1938 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
1941 for (k
= 0; k
< el
.nr_members
; k
++)
1942 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
1945 if (k
>= el
.nr_members
)
1947 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
1951 nxt_edge
= NEXT_OUT (nxt_edge
);
1953 while (fst_edge
!= nxt_edge
);
1955 sp
->update_bbs
.nr_members
= update_idx
;
1960 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1962 sp
->is_speculative
= 0;
1966 } /* compute_trg_info */
1969 /* Print candidates info, for debugging purposes. Callable from debugger. */
1975 if (!candidate_table
[i
].is_valid
)
1978 if (candidate_table
[i
].is_speculative
)
1981 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1983 fprintf (dump
, "split path: ");
1984 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1986 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
1988 fprintf (dump
, " %d ", b
);
1990 fprintf (dump
, "\n");
1992 fprintf (dump
, "update path: ");
1993 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
1995 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
1997 fprintf (dump
, " %d ", b
);
1999 fprintf (dump
, "\n");
2003 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2008 /* Print candidates info, for debugging purposes. Callable from debugger. */
2011 debug_candidates (trg
)
2016 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2017 BB_TO_BLOCK (trg
), trg
);
2018 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2019 debug_candidate (i
);
2023 /* Functions for speculative scheduing. */
2025 /* Return 0 if x is a set of a register alive in the beginning of one
2026 of the split-blocks of src, otherwise return 1. */
2029 check_live_1 (src
, x
)
2035 register rtx reg
= SET_DEST (x
);
2040 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2041 || GET_CODE (reg
) == SIGN_EXTRACT
2042 || GET_CODE (reg
) == STRICT_LOW_PART
)
2043 reg
= XEXP (reg
, 0);
2045 if (GET_CODE (reg
) == PARALLEL
2046 && GET_MODE (reg
) == BLKmode
)
2049 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2050 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2055 if (GET_CODE (reg
) != REG
)
2058 regno
= REGNO (reg
);
2060 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2062 /* Global registers are assumed live. */
2067 if (regno
< FIRST_PSEUDO_REGISTER
)
2069 /* Check for hard registers. */
2070 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2073 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2075 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2077 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
2087 /* Check for psuedo registers. */
2088 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2090 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2092 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, regno
))
2104 /* If x is a set of a register R, mark that R is alive in the beginning
2105 of every update-block of src. */
2108 update_live_1 (src
, x
)
2114 register rtx reg
= SET_DEST (x
);
2119 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2120 || GET_CODE (reg
) == SIGN_EXTRACT
2121 || GET_CODE (reg
) == STRICT_LOW_PART
)
2122 reg
= XEXP (reg
, 0);
2124 if (GET_CODE (reg
) == PARALLEL
2125 && GET_MODE (reg
) == BLKmode
)
2128 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2129 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2133 if (GET_CODE (reg
) != REG
)
2136 /* Global registers are always live, so the code below does not apply
2139 regno
= REGNO (reg
);
2141 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2143 if (regno
< FIRST_PSEUDO_REGISTER
)
2145 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2148 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2150 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2152 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
,
2159 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2161 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2163 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, regno
);
2170 /* Return 1 if insn can be speculatively moved from block src to trg,
2171 otherwise return 0. Called before first insertion of insn to
2172 ready-list or before the scheduling. */
2175 check_live (insn
, src
)
2179 /* Find the registers set by instruction. */
2180 if (GET_CODE (PATTERN (insn
)) == SET
2181 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2182 return check_live_1 (src
, PATTERN (insn
));
2183 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2186 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2187 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2188 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2189 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2199 /* Update the live registers info after insn was moved speculatively from
2200 block src to trg. */
2203 update_live (insn
, src
)
2207 /* Find the registers set by instruction. */
2208 if (GET_CODE (PATTERN (insn
)) == SET
2209 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2210 update_live_1 (src
, PATTERN (insn
));
2211 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2214 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2215 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2216 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2217 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2221 /* Exception Free Loads:
2223 We define five classes of speculative loads: IFREE, IRISKY,
2224 PFREE, PRISKY, and MFREE.
2226 IFREE loads are loads that are proved to be exception-free, just
2227 by examining the load insn. Examples for such loads are loads
2228 from TOC and loads of global data.
2230 IRISKY loads are loads that are proved to be exception-risky,
2231 just by examining the load insn. Examples for such loads are
2232 volatile loads and loads from shared memory.
2234 PFREE loads are loads for which we can prove, by examining other
2235 insns, that they are exception-free. Currently, this class consists
2236 of loads for which we are able to find a "similar load", either in
2237 the target block, or, if only one split-block exists, in that split
2238 block. Load2 is similar to load1 if both have same single base
2239 register. We identify only part of the similar loads, by finding
2240 an insn upon which both load1 and load2 have a DEF-USE dependence.
2242 PRISKY loads are loads for which we can prove, by examining other
2243 insns, that they are exception-risky. Currently we have two proofs for
2244 such loads. The first proof detects loads that are probably guarded by a
2245 test on the memory address. This proof is based on the
2246 backward and forward data dependence information for the region.
2247 Let load-insn be the examined load.
2248 Load-insn is PRISKY iff ALL the following hold:
2250 - insn1 is not in the same block as load-insn
2251 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2252 - test-insn is either a compare or a branch, not in the same block
2254 - load-insn is reachable from test-insn
2255 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2257 This proof might fail when the compare and the load are fed
2258 by an insn not in the region. To solve this, we will add to this
2259 group all loads that have no input DEF-USE dependence.
2261 The second proof detects loads that are directly or indirectly
2262 fed by a speculative load. This proof is affected by the
2263 scheduling process. We will use the flag fed_by_spec_load.
2264 Initially, all insns have this flag reset. After a speculative
2265 motion of an insn, if insn is either a load, or marked as
2266 fed_by_spec_load, we will also mark as fed_by_spec_load every
2267 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2268 load which is fed_by_spec_load is also PRISKY.
2270 MFREE (maybe-free) loads are all the remaining loads. They may be
2271 exception-free, but we cannot prove it.
2273 Now, all loads in IFREE and PFREE classes are considered
2274 exception-free, while all loads in IRISKY and PRISKY classes are
2275 considered exception-risky. As for loads in the MFREE class,
2276 these are considered either exception-free or exception-risky,
2277 depending on whether we are pessimistic or optimistic. We have
2278 to take the pessimistic approach to assure the safety of
2279 speculative scheduling, but we can take the optimistic approach
2280 by invoking the -fsched_spec_load_dangerous option. */
2282 enum INSN_TRAP_CLASS
2284 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2285 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2288 #define WORST_CLASS(class1, class2) \
2289 ((class1 > class2) ? class1 : class2)
2291 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between
2292 some speculatively moved load insn and this one. */
2293 char *fed_by_spec_load
;
2296 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2297 #define IS_REACHABLE(bb_from, bb_to) \
2299 || IS_RGN_ENTRY (bb_from) \
2300 || (bitset_member (ancestor_edges[bb_to], \
2301 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2303 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2304 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2306 /* Non-zero iff the address is comprised from at most 1 register. */
2307 #define CONST_BASED_ADDRESS_P(x) \
2308 (GET_CODE (x) == REG \
2309 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2310 || (GET_CODE (x) == LO_SUM)) \
2311 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2312 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2314 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2317 set_spec_fed (load_insn
)
2322 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2323 if (GET_MODE (link
) == VOIDmode
)
2324 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2325 } /* set_spec_fed */
2327 /* On the path from the insn to load_insn_bb, find a conditional
2328 branch depending on insn, that guards the speculative load. */
2331 find_conditional_protection (insn
, load_insn_bb
)
2337 /* Iterate through DEF-USE forward dependences. */
2338 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2340 rtx next
= XEXP (link
, 0);
2341 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
2342 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2343 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2344 && load_insn_bb
!= INSN_BB (next
)
2345 && GET_MODE (link
) == VOIDmode
2346 && (GET_CODE (next
) == JUMP_INSN
2347 || find_conditional_protection (next
, load_insn_bb
)))
2351 } /* find_conditional_protection */
2353 /* Returns 1 if the same insn1 that participates in the computation
2354 of load_insn's address is feeding a conditional branch that is
2355 guarding on load_insn. This is true if we find a the two DEF-USE
2357 insn1 -> ... -> conditional-branch
2358 insn1 -> ... -> load_insn,
2359 and if a flow path exist:
2360 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2361 and if insn1 is on the path
2362 region-entry -> ... -> bb_trg -> ... load_insn.
2364 Locate insn1 by climbing on LOG_LINKS from load_insn.
2365 Locate the branch by following INSN_DEPEND from insn1. */
2368 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2374 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2376 rtx insn1
= XEXP (link
, 0);
2378 /* Must be a DEF-USE dependence upon non-branch. */
2379 if (GET_MODE (link
) != VOIDmode
2380 || GET_CODE (insn1
) == JUMP_INSN
)
2383 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2384 if (INSN_BB (insn1
) == bb_src
2385 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
2386 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2387 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2388 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2391 /* Now search for the conditional-branch. */
2392 if (find_conditional_protection (insn1
, bb_src
))
2395 /* Recursive step: search another insn1, "above" current insn1. */
2396 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2399 /* The chain does not exist. */
2401 } /* is_conditionally_protected */
2403 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2404 load_insn can move speculatively from bb_src to bb_trg. All the
2405 following must hold:
2407 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2408 (2) load_insn and load1 have a def-use dependence upon
2409 the same insn 'insn1'.
2410 (3) either load2 is in bb_trg, or:
2411 - there's only one split-block, and
2412 - load1 is on the escape path, and
2414 From all these we can conclude that the two loads access memory
2415 addresses that differ at most by a constant, and hence if moving
2416 load_insn would cause an exception, it would have been caused by
2420 is_pfree (load_insn
, bb_src
, bb_trg
)
2425 register candidate
*candp
= candidate_table
+ bb_src
;
2427 if (candp
->split_bbs
.nr_members
!= 1)
2428 /* Must have exactly one escape block. */
2431 for (back_link
= LOG_LINKS (load_insn
);
2432 back_link
; back_link
= XEXP (back_link
, 1))
2434 rtx insn1
= XEXP (back_link
, 0);
2436 if (GET_MODE (back_link
) == VOIDmode
)
2438 /* Found a DEF-USE dependence (insn1, load_insn). */
2441 for (fore_link
= INSN_DEPEND (insn1
);
2442 fore_link
; fore_link
= XEXP (fore_link
, 1))
2444 rtx insn2
= XEXP (fore_link
, 0);
2445 if (GET_MODE (fore_link
) == VOIDmode
)
2447 /* Found a DEF-USE dependence (insn1, insn2). */
2448 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2449 /* insn2 not guaranteed to be a 1 base reg load. */
2452 if (INSN_BB (insn2
) == bb_trg
)
2453 /* insn2 is the similar load, in the target block. */
2456 if (*(candp
->split_bbs
.first_member
) == BLOCK_NUM (insn2
))
2457 /* insn2 is a similar load, in a split-block. */
2464 /* Couldn't find a similar load. */
2468 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2469 as found by analyzing insn's expression. */
2472 may_trap_exp (x
, is_store
)
2480 code
= GET_CODE (x
);
2490 /* The insn uses memory: a volatile load. */
2491 if (MEM_VOLATILE_P (x
))
2493 /* An exception-free load. */
2494 if (!may_trap_p (x
))
2496 /* A load with 1 base register, to be further checked. */
2497 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2498 return PFREE_CANDIDATE
;
2499 /* No info on the load, to be further checked. */
2500 return PRISKY_CANDIDATE
;
2505 int i
, insn_class
= TRAP_FREE
;
2507 /* Neither store nor load, check if it may cause a trap. */
2510 /* Recursive step: walk the insn... */
2511 fmt
= GET_RTX_FORMAT (code
);
2512 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2516 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2517 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2519 else if (fmt
[i
] == 'E')
2522 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2524 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2525 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2526 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2530 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2535 } /* may_trap_exp */
2538 /* Classifies insn for the purpose of verifying that it can be
2539 moved speculatively, by examining it's patterns, returning:
2540 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2541 TRAP_FREE: non-load insn.
2542 IFREE: load from a globaly safe location.
2543 IRISKY: volatile load.
2544 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2545 being either PFREE or PRISKY. */
2548 haifa_classify_insn (insn
)
2551 rtx pat
= PATTERN (insn
);
2552 int tmp_class
= TRAP_FREE
;
2553 int insn_class
= TRAP_FREE
;
2556 if (GET_CODE (pat
) == PARALLEL
)
2558 int i
, len
= XVECLEN (pat
, 0);
2560 for (i
= len
- 1; i
>= 0; i
--)
2562 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2566 /* Test if it is a 'store'. */
2567 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2570 /* Test if it is a store. */
2571 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2572 if (tmp_class
== TRAP_RISKY
)
2574 /* Test if it is a load. */
2576 WORST_CLASS (tmp_class
,
2577 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2580 tmp_class
= TRAP_RISKY
;
2584 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2585 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2591 code
= GET_CODE (pat
);
2595 /* Test if it is a 'store'. */
2596 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2599 /* Test if it is a store. */
2600 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2601 if (tmp_class
== TRAP_RISKY
)
2603 /* Test if it is a load. */
2605 WORST_CLASS (tmp_class
,
2606 may_trap_exp (SET_SRC (pat
), 0));
2609 tmp_class
= TRAP_RISKY
;
2613 insn_class
= tmp_class
;
2618 } /* haifa_classify_insn */
2620 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2621 a load moved speculatively, or if load_insn is protected by
2622 a compare on load_insn's address). */
2625 is_prisky (load_insn
, bb_src
, bb_trg
)
2629 if (FED_BY_SPEC_LOAD (load_insn
))
2632 if (LOG_LINKS (load_insn
) == NULL
)
2633 /* Dependence may 'hide' out of the region. */
2636 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2642 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2643 Return 1 if insn is exception-free (and the motion is valid)
2647 is_exception_free (insn
, bb_src
, bb_trg
)
2651 int insn_class
= haifa_classify_insn (insn
);
2653 /* Handle non-load insns. */
2664 if (!flag_schedule_speculative_load
)
2666 IS_LOAD_INSN (insn
) = 1;
2673 case PFREE_CANDIDATE
:
2674 if (is_pfree (insn
, bb_src
, bb_trg
))
2676 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2677 case PRISKY_CANDIDATE
:
2678 if (!flag_schedule_speculative_load_dangerous
2679 || is_prisky (insn
, bb_src
, bb_trg
))
2685 return flag_schedule_speculative_load_dangerous
;
2686 } /* is_exception_free */
2689 /* Process an insn's memory dependencies. There are four kinds of
2692 (0) read dependence: read follows read
2693 (1) true dependence: read follows write
2694 (2) anti dependence: write follows read
2695 (3) output dependence: write follows write
2697 We are careful to build only dependencies which actually exist, and
2698 use transitivity to avoid building too many links. */
2700 /* Return the INSN_LIST containing INSN in LIST, or NULL
2701 if LIST does not contain INSN. */
2703 HAIFA_INLINE
static rtx
2704 find_insn_list (insn
, list
)
2710 if (XEXP (list
, 0) == insn
)
2712 list
= XEXP (list
, 1);
2718 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2721 HAIFA_INLINE
static char
2722 find_insn_mem_list (insn
, x
, list
, list1
)
2728 if (XEXP (list
, 0) == insn
2729 && XEXP (list1
, 0) == x
)
2731 list
= XEXP (list
, 1);
2732 list1
= XEXP (list1
, 1);
2738 /* Compute the function units used by INSN. This caches the value
2739 returned by function_units_used. A function unit is encoded as the
2740 unit number if the value is non-negative and the compliment of a
2741 mask if the value is negative. A function unit index is the
2742 non-negative encoding. */
2744 HAIFA_INLINE
static int
2748 register int unit
= INSN_UNIT (insn
);
2752 recog_memoized (insn
);
2754 /* A USE insn, or something else we don't need to understand.
2755 We can't pass these directly to function_units_used because it will
2756 trigger a fatal error for unrecognizable insns. */
2757 if (INSN_CODE (insn
) < 0)
2761 unit
= function_units_used (insn
);
2762 /* Increment non-negative values so we can cache zero. */
2766 /* We only cache 16 bits of the result, so if the value is out of
2767 range, don't cache it. */
2768 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2770 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2771 INSN_UNIT (insn
) = unit
;
2773 return (unit
> 0 ? unit
- 1 : unit
);
2776 /* Compute the blockage range for executing INSN on UNIT. This caches
2777 the value returned by the blockage_range_function for the unit.
2778 These values are encoded in an int where the upper half gives the
2779 minimum value and the lower half gives the maximum value. */
2781 HAIFA_INLINE
static unsigned int
2782 blockage_range (unit
, insn
)
2786 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2789 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2791 range
= function_units
[unit
].blockage_range_function (insn
);
2792 /* We only cache the blockage range for one unit and then only if
2794 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2795 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2798 range
= BLOCKAGE_RANGE (blockage
);
2803 /* A vector indexed by function unit instance giving the last insn to use
2804 the unit. The value of the function unit instance index for unit U
2805 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2806 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2808 /* A vector indexed by function unit instance giving the minimum time when
2809 the unit will unblock based on the maximum blockage cost. */
2810 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2812 /* A vector indexed by function unit number giving the number of insns
2813 that remain to use the unit. */
2814 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2816 /* Reset the function unit state to the null state. */
2821 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2822 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2823 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2826 /* Return the issue-delay of an insn. */
2828 HAIFA_INLINE
static int
2829 insn_issue_delay (insn
)
2833 int unit
= insn_unit (insn
);
2835 /* Efficiency note: in fact, we are working 'hard' to compute a
2836 value that was available in md file, and is not available in
2837 function_units[] structure. It would be nice to have this
2838 value there, too. */
2841 if (function_units
[unit
].blockage_range_function
&&
2842 function_units
[unit
].blockage_function
)
2843 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2846 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2847 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2848 && function_units
[i
].blockage_function
)
2849 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2854 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2855 instance INSTANCE at time CLOCK if the previous actual hazard cost
2858 HAIFA_INLINE
static int
2859 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2860 int unit
, instance
, clock
, cost
;
2863 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
2865 if (tick
- clock
> cost
)
2867 /* The scheduler is operating forward, so unit's last insn is the
2868 executing insn and INSN is the candidate insn. We want a
2869 more exact measure of the blockage if we execute INSN at CLOCK
2870 given when we committed the execution of the unit's last insn.
2872 The blockage value is given by either the unit's max blockage
2873 constant, blockage range function, or blockage function. Use
2874 the most exact form for the given unit. */
2876 if (function_units
[unit
].blockage_range_function
)
2878 if (function_units
[unit
].blockage_function
)
2879 tick
+= (function_units
[unit
].blockage_function
2880 (unit_last_insn
[instance
], insn
)
2881 - function_units
[unit
].max_blockage
);
2883 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2884 - function_units
[unit
].max_blockage
);
2886 if (tick
- clock
> cost
)
2887 cost
= tick
- clock
;
2892 /* Record INSN as having begun execution on the units encoded by UNIT at
2895 HAIFA_INLINE
static void
2896 schedule_unit (unit
, insn
, clock
)
2904 int instance
= unit
;
2905 #if MAX_MULTIPLICITY > 1
2906 /* Find the first free instance of the function unit and use that
2907 one. We assume that one is free. */
2908 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2910 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2912 instance
+= FUNCTION_UNITS_SIZE
;
2915 unit_last_insn
[instance
] = insn
;
2916 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2919 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2920 if ((unit
& 1) != 0)
2921 schedule_unit (i
, insn
, clock
);
2924 /* Return the actual hazard cost of executing INSN on the units encoded by
2925 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2927 HAIFA_INLINE
static int
2928 actual_hazard (unit
, insn
, clock
, cost
)
2929 int unit
, clock
, cost
;
2936 /* Find the instance of the function unit with the minimum hazard. */
2937 int instance
= unit
;
2938 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2940 #if MAX_MULTIPLICITY > 1
2943 if (best_cost
> cost
)
2945 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2947 instance
+= FUNCTION_UNITS_SIZE
;
2948 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2950 if (this_cost
< best_cost
)
2952 best_cost
= this_cost
;
2953 if (this_cost
<= cost
)
2959 cost
= MAX (cost
, best_cost
);
2962 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2963 if ((unit
& 1) != 0)
2964 cost
= actual_hazard (i
, insn
, clock
, cost
);
2969 /* Return the potential hazard cost of executing an instruction on the
2970 units encoded by UNIT if the previous potential hazard cost was COST.
2971 An insn with a large blockage time is chosen in preference to one
2972 with a smaller time; an insn that uses a unit that is more likely
2973 to be used is chosen in preference to one with a unit that is less
2974 used. We are trying to minimize a subsequent actual hazard. */
2976 HAIFA_INLINE
static int
2977 potential_hazard (unit
, insn
, cost
)
2982 unsigned int minb
, maxb
;
2986 minb
= maxb
= function_units
[unit
].max_blockage
;
2989 if (function_units
[unit
].blockage_range_function
)
2991 maxb
= minb
= blockage_range (unit
, insn
);
2992 maxb
= MAX_BLOCKAGE_COST (maxb
);
2993 minb
= MIN_BLOCKAGE_COST (minb
);
2998 /* Make the number of instructions left dominate. Make the
2999 minimum delay dominate the maximum delay. If all these
3000 are the same, use the unit number to add an arbitrary
3001 ordering. Other terms can be added. */
3002 ncost
= minb
* 0x40 + maxb
;
3003 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3010 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3011 if ((unit
& 1) != 0)
3012 cost
= potential_hazard (i
, insn
, cost
);
3017 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3018 This is the number of cycles between instruction issue and
3019 instruction results. */
3021 HAIFA_INLINE
static int
3022 insn_cost (insn
, link
, used
)
3023 rtx insn
, link
, used
;
3025 register int cost
= INSN_COST (insn
);
3029 recog_memoized (insn
);
3031 /* A USE insn, or something else we don't need to understand.
3032 We can't pass these directly to result_ready_cost because it will
3033 trigger a fatal error for unrecognizable insns. */
3034 if (INSN_CODE (insn
) < 0)
3036 INSN_COST (insn
) = 1;
3041 cost
= result_ready_cost (insn
);
3046 INSN_COST (insn
) = cost
;
3050 /* In this case estimate cost without caring how insn is used. */
3051 if (link
== 0 && used
== 0)
3054 /* A USE insn should never require the value used to be computed. This
3055 allows the computation of a function's result and parameter values to
3056 overlap the return and call. */
3057 recog_memoized (used
);
3058 if (INSN_CODE (used
) < 0)
3059 LINK_COST_FREE (link
) = 1;
3061 /* If some dependencies vary the cost, compute the adjustment. Most
3062 commonly, the adjustment is complete: either the cost is ignored
3063 (in the case of an output- or anti-dependence), or the cost is
3064 unchanged. These values are cached in the link as LINK_COST_FREE
3065 and LINK_COST_ZERO. */
3067 if (LINK_COST_FREE (link
))
3070 else if (!LINK_COST_ZERO (link
))
3074 ADJUST_COST (used
, link
, insn
, ncost
);
3077 LINK_COST_FREE (link
) = 1;
3081 LINK_COST_ZERO (link
) = 1;
3088 /* Compute the priority number for INSN. */
3097 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3100 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3102 if (INSN_DEPEND (insn
) == 0)
3103 this_priority
= insn_cost (insn
, 0, 0);
3105 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3110 if (RTX_INTEGRATED_P (link
))
3113 next
= XEXP (link
, 0);
3115 /* Critical path is meaningful in block boundaries only. */
3116 if (BLOCK_NUM (next
) != BLOCK_NUM (insn
))
3119 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3120 if (next_priority
> this_priority
)
3121 this_priority
= next_priority
;
3123 INSN_PRIORITY (insn
) = this_priority
;
3125 return this_priority
;
3129 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3130 them to the unused_*_list variables, so that they can be reused. */
3133 free_pending_lists ()
3135 if (current_nr_blocks
<= 1)
3137 free_INSN_LIST_list (&pending_read_insns
);
3138 free_INSN_LIST_list (&pending_write_insns
);
3139 free_EXPR_LIST_list (&pending_read_mems
);
3140 free_EXPR_LIST_list (&pending_write_mems
);
3144 /* Interblock scheduling. */
3147 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3149 free_INSN_LIST_list (&bb_pending_read_insns
[bb
]);
3150 free_INSN_LIST_list (&bb_pending_write_insns
[bb
]);
3151 free_EXPR_LIST_list (&bb_pending_read_mems
[bb
]);
3152 free_EXPR_LIST_list (&bb_pending_write_mems
[bb
]);
3157 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3158 The MEM is a memory reference contained within INSN, which we are saving
3159 so that we can do memory aliasing on it. */
3162 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3163 rtx
*insn_list
, *mem_list
, insn
, mem
;
3167 link
= alloc_INSN_LIST (insn
, *insn_list
);
3170 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3173 pending_lists_length
++;
3177 /* Make a dependency between every memory reference on the pending lists
3178 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3182 flush_pending_lists (insn
, only_write
)
3189 while (pending_read_insns
&& ! only_write
)
3191 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3193 link
= pending_read_insns
;
3194 pending_read_insns
= XEXP (pending_read_insns
, 1);
3195 free_INSN_LIST_node (link
);
3197 link
= pending_read_mems
;
3198 pending_read_mems
= XEXP (pending_read_mems
, 1);
3199 free_EXPR_LIST_node (link
);
3201 while (pending_write_insns
)
3203 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3205 link
= pending_write_insns
;
3206 pending_write_insns
= XEXP (pending_write_insns
, 1);
3207 free_INSN_LIST_node (link
);
3209 link
= pending_write_mems
;
3210 pending_write_mems
= XEXP (pending_write_mems
, 1);
3211 free_EXPR_LIST_node (link
);
3213 pending_lists_length
= 0;
3215 /* last_pending_memory_flush is now a list of insns. */
3216 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3217 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3219 free_INSN_LIST_list (&last_pending_memory_flush
);
3220 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3223 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3224 rtx, X, creating all dependencies generated by the write to the
3225 destination of X, and reads of everything mentioned. */
3228 sched_analyze_1 (x
, insn
)
3233 register rtx dest
= XEXP (x
, 0);
3234 enum rtx_code code
= GET_CODE (x
);
3239 if (GET_CODE (dest
) == PARALLEL
3240 && GET_MODE (dest
) == BLKmode
)
3243 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3244 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3245 if (GET_CODE (x
) == SET
)
3246 sched_analyze_2 (SET_SRC (x
), insn
);
3250 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3251 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3253 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3255 /* The second and third arguments are values read by this insn. */
3256 sched_analyze_2 (XEXP (dest
, 1), insn
);
3257 sched_analyze_2 (XEXP (dest
, 2), insn
);
3259 dest
= XEXP (dest
, 0);
3262 if (GET_CODE (dest
) == REG
)
3266 regno
= REGNO (dest
);
3268 /* A hard reg in a wide mode may really be multiple registers.
3269 If so, mark all of them just like the first. */
3270 if (regno
< FIRST_PSEUDO_REGISTER
)
3272 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3277 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3278 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3280 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3281 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3283 /* Clobbers need not be ordered with respect to one
3284 another, but sets must be ordered with respect to a
3288 free_INSN_LIST_list (®_last_uses
[regno
+ i
]);
3289 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3290 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3291 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3294 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
3296 /* Function calls clobber all call_used regs. */
3297 if (global_regs
[regno
+ i
]
3298 || (code
== SET
&& call_used_regs
[regno
+ i
]))
3299 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3300 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3307 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3308 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3310 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3311 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3315 free_INSN_LIST_list (®_last_uses
[regno
]);
3316 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3317 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3318 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3321 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
3323 /* Pseudos that are REG_EQUIV to something may be replaced
3324 by that during reloading. We need only add dependencies for
3325 the address in the REG_EQUIV note. */
3326 if (!reload_completed
3327 && reg_known_equiv_p
[regno
]
3328 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3329 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3331 /* Don't let it cross a call after scheduling if it doesn't
3332 already cross one. */
3334 if (REG_N_CALLS_CROSSED (regno
) == 0)
3335 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3336 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3339 else if (GET_CODE (dest
) == MEM
)
3341 /* Writing memory. */
3343 if (pending_lists_length
> 32)
3345 /* Flush all pending reads and writes to prevent the pending lists
3346 from getting any larger. Insn scheduling runs too slowly when
3347 these lists get long. The number 32 was chosen because it
3348 seems like a reasonable number. When compiling GCC with itself,
3349 this flush occurs 8 times for sparc, and 10 times for m88k using
3351 flush_pending_lists (insn
, 0);
3356 rtx pending
, pending_mem
;
3358 pending
= pending_read_insns
;
3359 pending_mem
= pending_read_mems
;
3362 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3363 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3365 pending
= XEXP (pending
, 1);
3366 pending_mem
= XEXP (pending_mem
, 1);
3369 pending
= pending_write_insns
;
3370 pending_mem
= pending_write_mems
;
3373 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3374 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3376 pending
= XEXP (pending
, 1);
3377 pending_mem
= XEXP (pending_mem
, 1);
3380 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3381 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3383 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3386 sched_analyze_2 (XEXP (dest
, 0), insn
);
3389 /* Analyze reads. */
3390 if (GET_CODE (x
) == SET
)
3391 sched_analyze_2 (SET_SRC (x
), insn
);
3394 /* Analyze the uses of memory and registers in rtx X in INSN. */
3397 sched_analyze_2 (x
, insn
)
3403 register enum rtx_code code
;
3404 register const char *fmt
;
3409 code
= GET_CODE (x
);
3418 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3419 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3420 this does not mean that this insn is using cc0. */
3428 /* User of CC0 depends on immediately preceding insn. */
3429 SCHED_GROUP_P (insn
) = 1;
3431 /* There may be a note before this insn now, but all notes will
3432 be removed before we actually try to schedule the insns, so
3433 it won't cause a problem later. We must avoid it here though. */
3434 prev
= prev_nonnote_insn (insn
);
3436 /* Make a copy of all dependencies on the immediately previous insn,
3437 and add to this insn. This is so that all the dependencies will
3438 apply to the group. Remove an explicit dependence on this insn
3439 as SCHED_GROUP_P now represents it. */
3441 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3442 remove_dependence (insn
, prev
);
3444 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3445 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3454 int regno
= REGNO (x
);
3455 if (regno
< FIRST_PSEUDO_REGISTER
)
3459 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3462 reg_last_uses
[regno
+ i
]
3463 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3465 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3466 add_dependence (insn
, XEXP (u
, 0), 0);
3468 /* ??? This should never happen. */
3469 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3470 add_dependence (insn
, XEXP (u
, 0), 0);
3472 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3473 /* Function calls clobber all call_used regs. */
3474 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3475 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3480 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
,
3481 reg_last_uses
[regno
]);
3483 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3484 add_dependence (insn
, XEXP (u
, 0), 0);
3486 /* ??? This should never happen. */
3487 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3488 add_dependence (insn
, XEXP (u
, 0), 0);
3490 /* Pseudos that are REG_EQUIV to something may be replaced
3491 by that during reloading. We need only add dependencies for
3492 the address in the REG_EQUIV note. */
3493 if (!reload_completed
3494 && reg_known_equiv_p
[regno
]
3495 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3496 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3498 /* If the register does not already cross any calls, then add this
3499 insn to the sched_before_next_call list so that it will still
3500 not cross calls after scheduling. */
3501 if (REG_N_CALLS_CROSSED (regno
) == 0)
3502 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3509 /* Reading memory. */
3511 rtx pending
, pending_mem
;
3513 pending
= pending_read_insns
;
3514 pending_mem
= pending_read_mems
;
3517 if (read_dependence (XEXP (pending_mem
, 0), x
))
3518 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3520 pending
= XEXP (pending
, 1);
3521 pending_mem
= XEXP (pending_mem
, 1);
3524 pending
= pending_write_insns
;
3525 pending_mem
= pending_write_mems
;
3528 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3530 add_dependence (insn
, XEXP (pending
, 0), 0);
3532 pending
= XEXP (pending
, 1);
3533 pending_mem
= XEXP (pending_mem
, 1);
3536 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3537 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3539 /* Always add these dependencies to pending_reads, since
3540 this insn may be followed by a write. */
3541 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3544 /* Take advantage of tail recursion here. */
3545 sched_analyze_2 (XEXP (x
, 0), insn
);
3549 /* Force pending stores to memory in case a trap handler needs them. */
3551 flush_pending_lists (insn
, 1);
3556 case UNSPEC_VOLATILE
:
3560 /* Traditional and volatile asm instructions must be considered to use
3561 and clobber all hard registers, all pseudo-registers and all of
3562 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3564 Consider for instance a volatile asm that changes the fpu rounding
3565 mode. An insn should not be moved across this even if it only uses
3566 pseudo-regs because it might give an incorrectly rounded result. */
3567 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3569 int max_reg
= max_reg_num ();
3570 for (i
= 0; i
< max_reg
; i
++)
3572 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3573 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3574 free_INSN_LIST_list (®_last_uses
[i
]);
3576 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3577 add_dependence (insn
, XEXP (u
, 0), 0);
3579 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3580 add_dependence (insn
, XEXP (u
, 0), 0);
3582 reg_pending_sets_all
= 1;
3584 flush_pending_lists (insn
, 0);
3587 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3588 We can not just fall through here since then we would be confused
3589 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3590 traditional asms unlike their normal usage. */
3592 if (code
== ASM_OPERANDS
)
3594 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3595 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3605 /* These both read and modify the result. We must handle them as writes
3606 to get proper dependencies for following instructions. We must handle
3607 them as reads to get proper dependencies from this to previous
3608 instructions. Thus we need to pass them to both sched_analyze_1
3609 and sched_analyze_2. We must call sched_analyze_2 first in order
3610 to get the proper antecedent for the read. */
3611 sched_analyze_2 (XEXP (x
, 0), insn
);
3612 sched_analyze_1 (x
, insn
);
3619 /* Other cases: walk the insn. */
3620 fmt
= GET_RTX_FORMAT (code
);
3621 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3624 sched_analyze_2 (XEXP (x
, i
), insn
);
3625 else if (fmt
[i
] == 'E')
3626 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3627 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3631 /* Analyze an INSN with pattern X to find all dependencies. */
3634 sched_analyze_insn (x
, insn
, loop_notes
)
3638 register RTX_CODE code
= GET_CODE (x
);
3640 int maxreg
= max_reg_num ();
3643 if (code
== SET
|| code
== CLOBBER
)
3644 sched_analyze_1 (x
, insn
);
3645 else if (code
== PARALLEL
)
3648 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3650 code
= GET_CODE (XVECEXP (x
, 0, i
));
3651 if (code
== SET
|| code
== CLOBBER
)
3652 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3654 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3658 sched_analyze_2 (x
, insn
);
3660 /* Mark registers CLOBBERED or used by called function. */
3661 if (GET_CODE (insn
) == CALL_INSN
)
3662 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3664 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3665 sched_analyze_1 (XEXP (link
, 0), insn
);
3667 sched_analyze_2 (XEXP (link
, 0), insn
);
3670 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3671 block, then we must be sure that no instructions are scheduled across it.
3672 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3673 become incorrect. */
3677 int max_reg
= max_reg_num ();
3678 int schedule_barrier_found
= 0;
3681 /* Update loop_notes with any notes from this insn. Also determine
3682 if any of the notes on the list correspond to instruction scheduling
3683 barriers (loop, eh & setjmp notes, but not range notes. */
3685 while (XEXP (link
, 1))
3687 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3688 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3689 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3690 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3691 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3692 schedule_barrier_found
= 1;
3694 link
= XEXP (link
, 1);
3696 XEXP (link
, 1) = REG_NOTES (insn
);
3697 REG_NOTES (insn
) = loop_notes
;
3699 /* Add dependencies if a scheduling barrier was found. */
3700 if (schedule_barrier_found
)
3702 for (i
= 0; i
< max_reg
; i
++)
3705 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3706 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3707 free_INSN_LIST_list (®_last_uses
[i
]);
3709 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3710 add_dependence (insn
, XEXP (u
, 0), 0);
3712 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3713 add_dependence (insn
, XEXP (u
, 0), 0);
3715 reg_pending_sets_all
= 1;
3717 flush_pending_lists (insn
, 0);
3722 /* Accumulate clobbers until the next set so that it will be output dependent
3723 on all of them. At the next set we can clear the clobber list, since
3724 subsequent sets will be output dependent on it. */
3725 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3727 free_INSN_LIST_list (®_last_sets
[i
]);
3728 free_INSN_LIST_list (®_last_clobbers
[i
]);
3730 = alloc_INSN_LIST (insn
, NULL_RTX
);
3732 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
3734 reg_last_clobbers
[i
]
3735 = alloc_INSN_LIST (insn
,
3736 reg_last_clobbers
[i
]);
3738 CLEAR_REG_SET (reg_pending_sets
);
3739 CLEAR_REG_SET (reg_pending_clobbers
);
3741 if (reg_pending_sets_all
)
3743 for (i
= 0; i
< maxreg
; i
++)
3745 free_INSN_LIST_list (®_last_sets
[i
]);
3746 free_INSN_LIST_list (®_last_clobbers
[i
]);
3747 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3750 reg_pending_sets_all
= 0;
3753 /* Handle function calls and function returns created by the epilogue
3755 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3760 /* When scheduling instructions, we make sure calls don't lose their
3761 accompanying USE insns by depending them one on another in order.
3763 Also, we must do the same thing for returns created by the epilogue
3764 threading code. Note this code works only in this special case,
3765 because other passes make no guarantee that they will never emit
3766 an instruction between a USE and a RETURN. There is such a guarantee
3767 for USE instructions immediately before a call. */
3769 prev_dep_insn
= insn
;
3770 dep_insn
= PREV_INSN (insn
);
3771 while (GET_CODE (dep_insn
) == INSN
3772 && GET_CODE (PATTERN (dep_insn
)) == USE
3773 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3775 SCHED_GROUP_P (prev_dep_insn
) = 1;
3777 /* Make a copy of all dependencies on dep_insn, and add to insn.
3778 This is so that all of the dependencies will apply to the
3781 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3782 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3784 prev_dep_insn
= dep_insn
;
3785 dep_insn
= PREV_INSN (dep_insn
);
3790 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3791 for every dependency. */
3794 sched_analyze (head
, tail
)
3801 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3803 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3805 /* Clear out the stale LOG_LINKS from flow. */
3806 free_INSN_LIST_list (&LOG_LINKS (insn
));
3808 /* Make each JUMP_INSN a scheduling barrier for memory
3810 if (GET_CODE (insn
) == JUMP_INSN
)
3811 last_pending_memory_flush
3812 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3813 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3816 else if (GET_CODE (insn
) == CALL_INSN
)
3821 CANT_MOVE (insn
) = 1;
3823 /* Clear out the stale LOG_LINKS from flow. */
3824 free_INSN_LIST_list (&LOG_LINKS (insn
));
3826 /* Any instruction using a hard register which may get clobbered
3827 by a call needs to be marked as dependent on this call.
3828 This prevents a use of a hard return reg from being moved
3829 past a void call (i.e. it does not explicitly set the hard
3832 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3833 all registers, not just hard registers, may be clobbered by this
3836 /* Insn, being a CALL_INSN, magically depends on
3837 `last_function_call' already. */
3839 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3840 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3842 int max_reg
= max_reg_num ();
3843 for (i
= 0; i
< max_reg
; i
++)
3845 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3846 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3847 free_INSN_LIST_list (®_last_uses
[i
]);
3849 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3850 add_dependence (insn
, XEXP (u
, 0), 0);
3852 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3853 add_dependence (insn
, XEXP (u
, 0), 0);
3855 reg_pending_sets_all
= 1;
3857 /* Add a pair of REG_SAVE_NOTEs which we will later
3858 convert back into a NOTE_INSN_SETJMP note. See
3859 reemit_notes for why we use a pair of NOTEs. */
3860 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3863 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3864 GEN_INT (NOTE_INSN_SETJMP
),
3869 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3870 if (call_used_regs
[i
] || global_regs
[i
])
3872 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3873 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3875 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3876 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3878 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3882 /* For each insn which shouldn't cross a call, add a dependence
3883 between that insn and this call insn. */
3884 x
= LOG_LINKS (sched_before_next_call
);
3887 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3890 free_INSN_LIST_list (&LOG_LINKS (sched_before_next_call
));
3892 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3895 /* In the absence of interprocedural alias analysis, we must flush
3896 all pending reads and writes, and start new dependencies starting
3897 from here. But only flush writes for constant calls (which may
3898 be passed a pointer to something we haven't written yet). */
3899 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3901 /* Depend this function call (actually, the user of this
3902 function call) on all hard register clobberage. */
3904 /* last_function_call is now a list of insns. */
3905 free_INSN_LIST_list(&last_function_call
);
3906 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3909 /* See comments on reemit_notes as to why we do this.
3910 ??? Actually, the reemit_notes just say what is done, not why. */
3912 else if (GET_CODE (insn
) == NOTE
3913 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3914 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3916 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
, NOTE_RANGE_INFO (insn
),
3918 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3919 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3922 else if (GET_CODE (insn
) == NOTE
3923 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3924 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3925 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3926 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3927 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3928 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3932 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3933 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
3934 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
3936 rtx_region
= GEN_INT (0);
3938 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3941 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3942 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3944 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3953 /* Macros and functions for keeping the priority queue sorted, and
3954 dealing with queueing and dequeueing of instructions. */
3956 #define SCHED_SORT(READY, N_READY) \
3957 do { if ((N_READY) == 2) \
3958 swap_sort (READY, N_READY); \
3959 else if ((N_READY) > 2) \
3960 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3963 /* Returns a positive value if x is preferred; returns a negative value if
3964 y is preferred. Should never return 0, since that will make the sort
3968 rank_for_schedule (x
, y
)
3972 rtx tmp
= *(rtx
*)y
;
3973 rtx tmp2
= *(rtx
*)x
;
3975 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
3976 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
3979 /* Prefer insn with higher priority. */
3980 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
3982 return priority_val
;
3984 /* Prefer an insn with smaller contribution to registers-pressure. */
3985 if (!reload_completed
&&
3986 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
3987 return (weight_val
);
3989 /* Some comparison make sense in interblock scheduling only. */
3990 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
3992 /* Prefer an inblock motion on an interblock motion. */
3993 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
3995 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
3998 /* Prefer a useful motion on a speculative one. */
3999 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4002 /* Prefer a more probable (speculative) insn. */
4003 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4008 /* Compare insns based on their relation to the last-scheduled-insn. */
4009 if (last_scheduled_insn
)
4011 /* Classify the instructions into three classes:
4012 1) Data dependent on last schedule insn.
4013 2) Anti/Output dependent on last scheduled insn.
4014 3) Independent of last scheduled insn, or has latency of one.
4015 Choose the insn from the highest numbered class if different. */
4016 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4017 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4019 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4024 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4025 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4027 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4032 if ((val
= tmp2_class
- tmp_class
))
4036 /* Prefer the insn which has more later insns that depend on it.
4037 This gives the scheduler more freedom when scheduling later
4038 instructions at the expense of added register pressure. */
4040 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4044 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4047 val
= depend_count2
- depend_count1
;
4051 /* If insns are equally good, sort by INSN_LUID (original insn order),
4052 so that we make the sort stable. This minimizes instruction movement,
4053 thus minimizing sched's effect on debugging and cross-jumping. */
4054 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4057 /* Resort the array A in which only element at index N may be out of order. */
4059 HAIFA_INLINE
static void
4064 rtx insn
= a
[n
- 1];
4067 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4075 static int max_priority
;
4077 /* Add INSN to the insn queue so that it can be executed at least
4078 N_CYCLES after the currently executing insn. Preserve insns
4079 chain for debugging purposes. */
4081 HAIFA_INLINE
static void
4082 queue_insn (insn
, n_cycles
)
4086 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4087 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4088 insn_queue
[next_q
] = link
;
4091 if (sched_verbose
>= 2)
4093 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4095 if (INSN_BB (insn
) != target_bb
)
4096 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4098 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4103 /* PREV is an insn that is ready to execute. Adjust its priority if that
4104 will help shorten or lengthen register lifetimes as appropriate. Also
4105 provide a hook for the target to tweek itself. */
4107 HAIFA_INLINE
static void
4108 adjust_priority (prev
)
4109 rtx prev ATTRIBUTE_UNUSED
;
4111 /* ??? There used to be code here to try and estimate how an insn
4112 affected register lifetimes, but it did it by looking at REG_DEAD
4113 notes, which we removed in schedule_region. Nor did it try to
4114 take into account register pressure or anything useful like that.
4116 Revisit when we have a machine model to work with and not before. */
4118 #ifdef ADJUST_PRIORITY
4119 ADJUST_PRIORITY (prev
);
4123 /* Clock at which the previous instruction was issued. */
4124 static int last_clock_var
;
4126 /* INSN is the "currently executing insn". Launch each insn which was
4127 waiting on INSN. READY is a vector of insns which are ready to fire.
4128 N_READY is the number of elements in READY. CLOCK is the current
4132 schedule_insn (insn
, ready
, n_ready
, clock
)
4141 unit
= insn_unit (insn
);
4143 if (sched_verbose
>= 2)
4145 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4147 insn_print_units (insn
);
4148 fprintf (dump
, "\n");
4151 if (sched_verbose
&& unit
== -1)
4152 visualize_no_unit (insn
);
4154 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4155 schedule_unit (unit
, insn
, clock
);
4157 if (INSN_DEPEND (insn
) == 0)
4160 /* This is used by the function adjust_priority above. */
4162 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4164 max_priority
= INSN_PRIORITY (insn
);
4166 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4168 rtx next
= XEXP (link
, 0);
4169 int cost
= insn_cost (insn
, link
, next
);
4171 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4173 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4175 int effective_cost
= INSN_TICK (next
) - clock
;
4177 /* For speculative insns, before inserting to ready/queue,
4178 check live, exception-free, and issue-delay. */
4179 if (INSN_BB (next
) != target_bb
4180 && (!IS_VALID (INSN_BB (next
))
4182 || (IS_SPECULATIVE_INSN (next
)
4183 && (insn_issue_delay (next
) > 3
4184 || !check_live (next
, INSN_BB (next
))
4185 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4188 if (sched_verbose
>= 2)
4190 fprintf (dump
, ";;\t\tdependences resolved: insn %d ",
4193 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4194 fprintf (dump
, "/b%d ", BLOCK_NUM (next
));
4196 if (effective_cost
< 1)
4197 fprintf (dump
, "into ready\n");
4199 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4202 /* Adjust the priority of NEXT and either put it on the ready
4203 list or queue it. */
4204 adjust_priority (next
);
4205 if (effective_cost
< 1)
4206 ready
[n_ready
++] = next
;
4208 queue_insn (next
, effective_cost
);
4212 /* Annotate the instruction with issue information -- TImode
4213 indicates that the instruction is expected not to be able
4214 to issue on the same cycle as the previous insn. A machine
4215 may use this information to decide how the instruction should
4217 if (reload_completed
&& issue_rate
> 1)
4219 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4220 last_clock_var
= clock
;
4226 /* Functions for handling of notes. */
4228 /* Delete notes beginning with INSN and put them in the chain
4229 of notes ended by NOTE_LIST.
4230 Returns the insn following the notes. */
4233 unlink_other_notes (insn
, tail
)
4236 rtx prev
= PREV_INSN (insn
);
4238 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4240 rtx next
= NEXT_INSN (insn
);
4241 /* Delete the note from its current position. */
4243 NEXT_INSN (prev
) = next
;
4245 PREV_INSN (next
) = prev
;
4247 /* See sched_analyze to see how these are handled. */
4248 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4249 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4250 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4251 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4252 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4253 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4254 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4256 /* Insert the note at the end of the notes list. */
4257 PREV_INSN (insn
) = note_list
;
4259 NEXT_INSN (note_list
) = insn
;
4268 /* Delete line notes beginning with INSN. Record line-number notes so
4269 they can be reused. Returns the insn following the notes. */
4272 unlink_line_notes (insn
, tail
)
4275 rtx prev
= PREV_INSN (insn
);
4277 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4279 rtx next
= NEXT_INSN (insn
);
4281 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4283 /* Delete the note from its current position. */
4285 NEXT_INSN (prev
) = next
;
4287 PREV_INSN (next
) = prev
;
4289 /* Record line-number notes so they can be reused. */
4290 LINE_NOTE (insn
) = insn
;
4300 /* Return the head and tail pointers of BB. */
4302 HAIFA_INLINE
static void
4303 get_block_head_tail (b
, headp
, tailp
)
4312 /* HEAD and TAIL delimit the basic block being scheduled. */
4313 head
= BLOCK_HEAD (b
);
4314 tail
= BLOCK_END (b
);
4316 /* Don't include any notes or labels at the beginning of the
4317 basic block, or notes at the ends of basic blocks. */
4318 while (head
!= tail
)
4320 if (GET_CODE (head
) == NOTE
)
4321 head
= NEXT_INSN (head
);
4322 else if (GET_CODE (tail
) == NOTE
)
4323 tail
= PREV_INSN (tail
);
4324 else if (GET_CODE (head
) == CODE_LABEL
)
4325 head
= NEXT_INSN (head
);
4334 HAIFA_INLINE
static void
4335 get_bb_head_tail (bb
, headp
, tailp
)
4340 get_block_head_tail (BB_TO_BLOCK (bb
), headp
, tailp
);
4343 /* Delete line notes from bb. Save them so they can be later restored
4344 (in restore_line_notes ()). */
4355 get_bb_head_tail (bb
, &head
, &tail
);
4358 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4361 next_tail
= NEXT_INSN (tail
);
4362 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4366 /* Farm out notes, and maybe save them in NOTE_LIST.
4367 This is needed to keep the debugger from
4368 getting completely deranged. */
4369 if (GET_CODE (insn
) == NOTE
)
4372 insn
= unlink_line_notes (insn
, next_tail
);
4378 if (insn
== next_tail
)
4384 /* Save line number notes for each insn in bb. */
4387 save_line_notes (bb
)
4393 /* We must use the true line number for the first insn in the block
4394 that was computed and saved at the start of this pass. We can't
4395 use the current line number, because scheduling of the previous
4396 block may have changed the current line number. */
4398 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4401 get_bb_head_tail (bb
, &head
, &tail
);
4402 next_tail
= NEXT_INSN (tail
);
4404 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4406 insn
= NEXT_INSN (insn
))
4407 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4410 LINE_NOTE (insn
) = line
;
4414 /* After bb was scheduled, insert line notes into the insns list. */
4417 restore_line_notes (bb
)
4420 rtx line
, note
, prev
, new;
4421 int added_notes
= 0;
4423 rtx head
, next_tail
, insn
;
4425 b
= BB_TO_BLOCK (bb
);
4427 head
= BLOCK_HEAD (b
);
4428 next_tail
= NEXT_INSN (BLOCK_END (b
));
4430 /* Determine the current line-number. We want to know the current
4431 line number of the first insn of the block here, in case it is
4432 different from the true line number that was saved earlier. If
4433 different, then we need a line number note before the first insn
4434 of this block. If it happens to be the same, then we don't want to
4435 emit another line number note here. */
4436 for (line
= head
; line
; line
= PREV_INSN (line
))
4437 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4440 /* Walk the insns keeping track of the current line-number and inserting
4441 the line-number notes as needed. */
4442 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4443 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4445 /* This used to emit line number notes before every non-deleted note.
4446 However, this confuses a debugger, because line notes not separated
4447 by real instructions all end up at the same address. I can find no
4448 use for line number notes before other notes, so none are emitted. */
4449 else if (GET_CODE (insn
) != NOTE
4450 && (note
= LINE_NOTE (insn
)) != 0
4453 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4454 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4457 prev
= PREV_INSN (insn
);
4458 if (LINE_NOTE (note
))
4460 /* Re-use the original line-number note. */
4461 LINE_NOTE (note
) = 0;
4462 PREV_INSN (note
) = prev
;
4463 NEXT_INSN (prev
) = note
;
4464 PREV_INSN (insn
) = note
;
4465 NEXT_INSN (note
) = insn
;
4470 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4471 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4472 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4475 if (sched_verbose
&& added_notes
)
4476 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4479 /* After scheduling the function, delete redundant line notes from the
4483 rm_redundant_line_notes ()
4486 rtx insn
= get_insns ();
4487 int active_insn
= 0;
4490 /* Walk the insns deleting redundant line-number notes. Many of these
4491 are already present. The remainder tend to occur at basic
4492 block boundaries. */
4493 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4494 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4496 /* If there are no active insns following, INSN is redundant. */
4497 if (active_insn
== 0)
4500 NOTE_SOURCE_FILE (insn
) = 0;
4501 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
4503 /* If the line number is unchanged, LINE is redundant. */
4505 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
4506 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
4509 NOTE_SOURCE_FILE (line
) = 0;
4510 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
4517 else if (!((GET_CODE (insn
) == NOTE
4518 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
4519 || (GET_CODE (insn
) == INSN
4520 && (GET_CODE (PATTERN (insn
)) == USE
4521 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
4524 if (sched_verbose
&& notes
)
4525 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
4528 /* Delete notes between head and tail and put them in the chain
4529 of notes ended by NOTE_LIST. */
4532 rm_other_notes (head
, tail
)
4540 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4543 next_tail
= NEXT_INSN (tail
);
4544 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4548 /* Farm out notes, and maybe save them in NOTE_LIST.
4549 This is needed to keep the debugger from
4550 getting completely deranged. */
4551 if (GET_CODE (insn
) == NOTE
)
4555 insn
= unlink_other_notes (insn
, next_tail
);
4561 if (insn
== next_tail
)
4567 /* Functions for computation of registers live/usage info. */
4569 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4572 find_insn_reg_weight (b
)
4575 rtx insn
, next_tail
, head
, tail
;
4577 get_block_head_tail (b
, &head
, &tail
);
4578 next_tail
= NEXT_INSN (tail
);
4580 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4585 /* Handle register life information. */
4586 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4589 /* Increment weight for each register born here. */
4591 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4592 && register_operand (SET_DEST (x
), VOIDmode
))
4594 else if (GET_CODE (x
) == PARALLEL
)
4597 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
4599 x
= XVECEXP (PATTERN (insn
), 0, j
);
4600 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4601 && register_operand (SET_DEST (x
), VOIDmode
))
4606 /* Decrement weight for each register that dies here. */
4607 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
4609 if (REG_NOTE_KIND (x
) == REG_DEAD
4610 || REG_NOTE_KIND (x
) == REG_UNUSED
)
4614 INSN_REG_WEIGHT (insn
) = reg_weight
;
4618 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4619 static int clock_var
;
4621 /* Move insns that became ready to fire from queue to ready list. */
4624 queue_to_ready (ready
, n_ready
)
4631 q_ptr
= NEXT_Q (q_ptr
);
4633 /* Add all pending insns that can be scheduled without stalls to the
4635 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
4638 insn
= XEXP (link
, 0);
4641 if (sched_verbose
>= 2)
4642 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4644 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4645 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4647 ready
[n_ready
++] = insn
;
4648 if (sched_verbose
>= 2)
4649 fprintf (dump
, "moving to ready without stalls\n");
4651 insn_queue
[q_ptr
] = 0;
4653 /* If there are no ready insns, stall until one is ready and add all
4654 of the pending insns at that point to the ready list. */
4657 register int stalls
;
4659 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
4661 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4663 for (; link
; link
= XEXP (link
, 1))
4665 insn
= XEXP (link
, 0);
4668 if (sched_verbose
>= 2)
4669 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4671 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4672 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4674 ready
[n_ready
++] = insn
;
4675 if (sched_verbose
>= 2)
4676 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
4678 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
4685 if (sched_verbose
&& stalls
)
4686 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
4687 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
4688 clock_var
+= stalls
;
4693 /* Print the ready list for debugging purposes. Callable from debugger. */
4696 debug_ready_list (ready
, n_ready
)
4702 for (i
= 0; i
< n_ready
; i
++)
4704 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
4705 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
4706 fprintf (dump
, "/b%d", BLOCK_NUM (ready
[i
]));
4708 fprintf (dump
, "\n");
4711 /* Print names of units on which insn can/should execute, for debugging. */
4714 insn_print_units (insn
)
4718 int unit
= insn_unit (insn
);
4721 fprintf (dump
, "none");
4723 fprintf (dump
, "%s", function_units
[unit
].name
);
4726 fprintf (dump
, "[");
4727 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
4730 fprintf (dump
, "%s", function_units
[i
].name
);
4732 fprintf (dump
, " ");
4734 fprintf (dump
, "]");
4738 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4739 of a basic block. If more lines are needed, table is splitted to two.
4740 n_visual_lines is the number of lines printed so far for a block.
4741 visual_tbl contains the block visualization info.
4742 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
4743 #define MAX_VISUAL_LINES 100
4748 rtx vis_no_unit
[10];
4750 /* Finds units that are in use in this fuction. Required only
4751 for visualization. */
4754 init_target_units ()
4759 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4761 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4764 unit
= insn_unit (insn
);
4767 target_units
|= ~unit
;
4769 target_units
|= (1 << unit
);
4773 /* Return the length of the visualization table. */
4776 get_visual_tbl_length ()
4782 /* Compute length of one field in line. */
4783 s
= (char *) alloca (INSN_LEN
+ 6);
4784 sprintf (s
, " %33s", "uname");
4787 /* Compute length of one line. */
4790 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
4791 if (function_units
[unit
].bitmask
& target_units
)
4792 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
4795 n
+= strlen ("\n") + 2;
4797 /* Compute length of visualization string. */
4798 return (MAX_VISUAL_LINES
* n
);
4801 /* Init block visualization debugging info. */
4804 init_block_visualization ()
4806 strcpy (visual_tbl
, "");
4814 safe_concat (buf
, cur
, str
)
4819 char *end
= buf
+ BUF_LEN
- 2; /* Leave room for null. */
4828 while (cur
< end
&& (c
= *str
++) != '\0')
4835 /* This recognizes rtx, I classified as expressions. These are always
4836 represent some action on values or results of other expression, that
4837 may be stored in objects representing values. */
4840 print_exp (buf
, x
, verbose
)
4848 const char *fun
= (char *)0;
4853 for (i
= 0; i
< 4; i
++)
4859 switch (GET_CODE (x
))
4862 op
[0] = XEXP (x
, 0);
4863 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
4864 && INTVAL (XEXP (x
, 1)) < 0)
4867 op
[1] = GEN_INT (-INTVAL (XEXP (x
, 1)));
4872 op
[1] = XEXP (x
, 1);
4876 op
[0] = XEXP (x
, 0);
4878 op
[1] = XEXP (x
, 1);
4882 op
[0] = XEXP (x
, 0);
4884 op
[1] = XEXP (x
, 1);
4888 op
[0] = XEXP (x
, 0);
4889 op
[1] = XEXP (x
, 1);
4893 op
[0] = XEXP (x
, 0);
4896 op
[0] = XEXP (x
, 0);
4898 op
[1] = XEXP (x
, 1);
4901 op
[0] = XEXP (x
, 0);
4903 op
[1] = XEXP (x
, 1);
4907 op
[0] = XEXP (x
, 0);
4908 op
[1] = XEXP (x
, 1);
4911 op
[0] = XEXP (x
, 0);
4913 op
[1] = XEXP (x
, 1);
4917 op
[0] = XEXP (x
, 0);
4918 op
[1] = XEXP (x
, 1);
4922 op
[0] = XEXP (x
, 0);
4923 op
[1] = XEXP (x
, 1);
4927 op
[0] = XEXP (x
, 0);
4928 op
[1] = XEXP (x
, 1);
4932 op
[0] = XEXP (x
, 0);
4933 op
[1] = XEXP (x
, 1);
4937 op
[0] = XEXP (x
, 0);
4938 op
[1] = XEXP (x
, 1);
4942 op
[0] = XEXP (x
, 0);
4945 op
[0] = XEXP (x
, 0);
4947 op
[1] = XEXP (x
, 1);
4950 op
[0] = XEXP (x
, 0);
4952 op
[1] = XEXP (x
, 1);
4955 op
[0] = XEXP (x
, 0);
4957 op
[1] = XEXP (x
, 1);
4960 op
[0] = XEXP (x
, 0);
4962 op
[1] = XEXP (x
, 1);
4965 op
[0] = XEXP (x
, 0);
4967 op
[1] = XEXP (x
, 1);
4970 op
[0] = XEXP (x
, 0);
4972 op
[1] = XEXP (x
, 1);
4975 op
[0] = XEXP (x
, 0);
4977 op
[1] = XEXP (x
, 1);
4980 op
[0] = XEXP (x
, 0);
4982 op
[1] = XEXP (x
, 1);
4986 op
[0] = XEXP (x
, 0);
4990 op
[0] = XEXP (x
, 0);
4994 op
[0] = XEXP (x
, 0);
4997 op
[0] = XEXP (x
, 0);
4999 op
[1] = XEXP (x
, 1);
5002 op
[0] = XEXP (x
, 0);
5004 op
[1] = XEXP (x
, 1);
5007 op
[0] = XEXP (x
, 0);
5009 op
[1] = XEXP (x
, 1);
5013 op
[0] = XEXP (x
, 0);
5014 op
[1] = XEXP (x
, 1);
5017 op
[0] = XEXP (x
, 0);
5019 op
[1] = XEXP (x
, 1);
5023 op
[0] = XEXP (x
, 0);
5024 op
[1] = XEXP (x
, 1);
5027 op
[0] = XEXP (x
, 0);
5029 op
[1] = XEXP (x
, 1);
5033 op
[0] = XEXP (x
, 0);
5034 op
[1] = XEXP (x
, 1);
5037 op
[0] = XEXP (x
, 0);
5039 op
[1] = XEXP (x
, 1);
5043 op
[0] = XEXP (x
, 0);
5044 op
[1] = XEXP (x
, 1);
5047 fun
= (verbose
) ? "sign_extract" : "sxt";
5048 op
[0] = XEXP (x
, 0);
5049 op
[1] = XEXP (x
, 1);
5050 op
[2] = XEXP (x
, 2);
5053 fun
= (verbose
) ? "zero_extract" : "zxt";
5054 op
[0] = XEXP (x
, 0);
5055 op
[1] = XEXP (x
, 1);
5056 op
[2] = XEXP (x
, 2);
5059 fun
= (verbose
) ? "sign_extend" : "sxn";
5060 op
[0] = XEXP (x
, 0);
5063 fun
= (verbose
) ? "zero_extend" : "zxn";
5064 op
[0] = XEXP (x
, 0);
5067 fun
= (verbose
) ? "float_extend" : "fxn";
5068 op
[0] = XEXP (x
, 0);
5071 fun
= (verbose
) ? "trunc" : "trn";
5072 op
[0] = XEXP (x
, 0);
5074 case FLOAT_TRUNCATE
:
5075 fun
= (verbose
) ? "float_trunc" : "ftr";
5076 op
[0] = XEXP (x
, 0);
5079 fun
= (verbose
) ? "float" : "flt";
5080 op
[0] = XEXP (x
, 0);
5082 case UNSIGNED_FLOAT
:
5083 fun
= (verbose
) ? "uns_float" : "ufl";
5084 op
[0] = XEXP (x
, 0);
5088 op
[0] = XEXP (x
, 0);
5091 fun
= (verbose
) ? "uns_fix" : "ufx";
5092 op
[0] = XEXP (x
, 0);
5096 op
[0] = XEXP (x
, 0);
5100 op
[0] = XEXP (x
, 0);
5103 op
[0] = XEXP (x
, 0);
5107 op
[0] = XEXP (x
, 0);
5112 op
[0] = XEXP (x
, 0);
5116 op
[1] = XEXP (x
, 1);
5121 op
[0] = XEXP (x
, 0);
5123 op
[1] = XEXP (x
, 1);
5125 op
[2] = XEXP (x
, 2);
5130 op
[0] = TRAP_CONDITION (x
);
5133 case UNSPEC_VOLATILE
:
5135 cur
= safe_concat (buf
, cur
, "unspec");
5136 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
5137 cur
= safe_concat (buf
, cur
, "/v");
5138 cur
= safe_concat (buf
, cur
, "[");
5140 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5142 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
5143 cur
= safe_concat (buf
, cur
, sep
);
5144 cur
= safe_concat (buf
, cur
, tmp
);
5147 cur
= safe_concat (buf
, cur
, "] ");
5148 sprintf (tmp
, "%d", XINT (x
, 1));
5149 cur
= safe_concat (buf
, cur
, tmp
);
5153 /* If (verbose) debug_rtx (x); */
5154 st
[0] = GET_RTX_NAME (GET_CODE (x
));
5158 /* Print this as a function? */
5161 cur
= safe_concat (buf
, cur
, fun
);
5162 cur
= safe_concat (buf
, cur
, "(");
5165 for (i
= 0; i
< 4; i
++)
5168 cur
= safe_concat (buf
, cur
, st
[i
]);
5173 cur
= safe_concat (buf
, cur
, ",");
5175 print_value (tmp
, op
[i
], verbose
);
5176 cur
= safe_concat (buf
, cur
, tmp
);
5181 cur
= safe_concat (buf
, cur
, ")");
5184 /* Prints rtxes, I customly classified as values. They're constants,
5185 registers, labels, symbols and memory accesses. */
5188 print_value (buf
, x
, verbose
)
5196 switch (GET_CODE (x
))
5199 sprintf (t
, HOST_WIDE_INT_PRINT_HEX
, INTVAL (x
));
5200 cur
= safe_concat (buf
, cur
, t
);
5203 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
5204 cur
= safe_concat (buf
, cur
, t
);
5207 cur
= safe_concat (buf
, cur
, "\"");
5208 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5209 cur
= safe_concat (buf
, cur
, "\"");
5212 cur
= safe_concat (buf
, cur
, "`");
5213 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5214 cur
= safe_concat (buf
, cur
, "'");
5217 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
5218 cur
= safe_concat (buf
, cur
, t
);
5221 print_value (t
, XEXP (x
, 0), verbose
);
5222 cur
= safe_concat (buf
, cur
, "const(");
5223 cur
= safe_concat (buf
, cur
, t
);
5224 cur
= safe_concat (buf
, cur
, ")");
5227 print_value (t
, XEXP (x
, 0), verbose
);
5228 cur
= safe_concat (buf
, cur
, "high(");
5229 cur
= safe_concat (buf
, cur
, t
);
5230 cur
= safe_concat (buf
, cur
, ")");
5233 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
5235 int c
= reg_names
[ REGNO (x
) ][0];
5236 if (c
>= '0' && c
<= '9')
5237 cur
= safe_concat (buf
, cur
, "%");
5239 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
5243 sprintf (t
, "r%d", REGNO (x
));
5244 cur
= safe_concat (buf
, cur
, t
);
5248 print_value (t
, SUBREG_REG (x
), verbose
);
5249 cur
= safe_concat (buf
, cur
, t
);
5250 sprintf (t
, "#%d", SUBREG_WORD (x
));
5251 cur
= safe_concat (buf
, cur
, t
);
5254 cur
= safe_concat (buf
, cur
, "scratch");
5257 cur
= safe_concat (buf
, cur
, "cc0");
5260 cur
= safe_concat (buf
, cur
, "pc");
5263 print_value (t
, XEXP (x
, 0), verbose
);
5264 cur
= safe_concat (buf
, cur
, "[");
5265 cur
= safe_concat (buf
, cur
, t
);
5266 cur
= safe_concat (buf
, cur
, "]");
5269 print_exp (t
, x
, verbose
);
5270 cur
= safe_concat (buf
, cur
, t
);
5275 /* The next step in insn detalization, its pattern recognition. */
5278 print_pattern (buf
, x
, verbose
)
5283 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
5285 switch (GET_CODE (x
))
5288 print_value (t1
, SET_DEST (x
), verbose
);
5289 print_value (t2
, SET_SRC (x
), verbose
);
5290 sprintf (buf
, "%s=%s", t1
, t2
);
5293 sprintf (buf
, "return");
5296 print_exp (buf
, x
, verbose
);
5299 print_value (t1
, XEXP (x
, 0), verbose
);
5300 sprintf (buf
, "clobber %s", t1
);
5303 print_value (t1
, XEXP (x
, 0), verbose
);
5304 sprintf (buf
, "use %s", t1
);
5311 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5313 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5314 sprintf (t3
, "%s%s;", t1
, t2
);
5317 sprintf (buf
, "%s}", t1
);
5324 sprintf (t1
, "%%{");
5325 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5327 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
5328 sprintf (t3
, "%s%s;", t1
, t2
);
5331 sprintf (buf
, "%s%%}", t1
);
5335 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
5340 print_value (buf
, XEXP (x
, 0), verbose
);
5343 print_value (t1
, TRAP_CONDITION (x
), verbose
);
5344 sprintf (buf
, "trap_if %s", t1
);
5350 sprintf (t1
, "unspec{");
5351 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5353 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5354 sprintf (t3
, "%s%s;", t1
, t2
);
5357 sprintf (buf
, "%s}", t1
);
5360 case UNSPEC_VOLATILE
:
5364 sprintf (t1
, "unspec/v{");
5365 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5367 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5368 sprintf (t3
, "%s%s;", t1
, t2
);
5371 sprintf (buf
, "%s}", t1
);
5375 print_value (buf
, x
, verbose
);
5377 } /* print_pattern */
5379 /* This is the main function in rtl visualization mechanism. It
5380 accepts an rtx and tries to recognize it as an insn, then prints it
5381 properly in human readable form, resembling assembler mnemonics.
5382 For every insn it prints its UID and BB the insn belongs too.
5383 (Probably the last "option" should be extended somehow, since it
5384 depends now on sched.c inner variables ...) */
5387 print_insn (buf
, x
, verbose
)
5395 switch (GET_CODE (x
))
5398 print_pattern (t
, PATTERN (x
), verbose
);
5400 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
5403 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5406 print_pattern (t
, PATTERN (x
), verbose
);
5408 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
5411 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5415 if (GET_CODE (x
) == PARALLEL
)
5417 x
= XVECEXP (x
, 0, 0);
5418 print_pattern (t
, x
, verbose
);
5421 strcpy (t
, "call <...>");
5423 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
5424 INSN_UID (insn
), t
);
5426 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
5429 sprintf (buf
, "L%d:", INSN_UID (x
));
5432 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
5435 if (NOTE_LINE_NUMBER (x
) > 0)
5436 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
5437 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
5439 sprintf (buf
, "%4d %s", INSN_UID (x
),
5440 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
5445 sprintf (buf
, "Not an INSN at all\n");
5449 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
5453 /* Print visualization debugging info. */
5456 print_block_visualization (b
, s
)
5463 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
5465 /* Print names of units. */
5466 fprintf (dump
, ";; %-8s", "clock");
5467 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5468 if (function_units
[unit
].bitmask
& target_units
)
5469 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5470 fprintf (dump
, " %-33s", function_units
[unit
].name
);
5471 fprintf (dump
, " %-8s\n", "no-unit");
5473 fprintf (dump
, ";; %-8s", "=====");
5474 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5475 if (function_units
[unit
].bitmask
& target_units
)
5476 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5477 fprintf (dump
, " %-33s", "==============================");
5478 fprintf (dump
, " %-8s\n", "=======");
5480 /* Print insns in each cycle. */
5481 fprintf (dump
, "%s\n", visual_tbl
);
5484 /* Print insns in the 'no_unit' column of visualization. */
5487 visualize_no_unit (insn
)
5490 vis_no_unit
[n_vis_no_unit
] = insn
;
5494 /* Print insns scheduled in clock, for visualization. */
5497 visualize_scheduled_insns (b
, clock
)
5502 /* If no more room, split table into two. */
5503 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5505 print_block_visualization (b
, "(incomplete)");
5506 init_block_visualization ();
5511 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
5512 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5513 if (function_units
[unit
].bitmask
& target_units
)
5514 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5516 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
5517 rtx insn
= unit_last_insn
[instance
];
5519 /* Print insns that still keep the unit busy. */
5521 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
5524 print_insn (str
, insn
, 0);
5525 str
[INSN_LEN
] = '\0';
5526 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
5529 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
5532 /* Print insns that are not assigned to any unit. */
5533 for (i
= 0; i
< n_vis_no_unit
; i
++)
5534 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
5535 INSN_UID (vis_no_unit
[i
]));
5538 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5541 /* Print stalled cycles. */
5544 visualize_stall_cycles (b
, stalls
)
5549 /* If no more room, split table into two. */
5550 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5552 print_block_visualization (b
, "(incomplete)");
5553 init_block_visualization ();
5558 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
5559 for (i
= 0; i
< stalls
; i
++)
5560 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
5561 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5564 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5567 move_insn1 (insn
, last
)
5570 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
5571 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
5573 NEXT_INSN (insn
) = NEXT_INSN (last
);
5574 PREV_INSN (NEXT_INSN (last
)) = insn
;
5576 NEXT_INSN (last
) = insn
;
5577 PREV_INSN (insn
) = last
;
5582 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5583 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5584 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5585 saved value for NOTE_BLOCK_NUMBER which is useful for
5586 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5587 output by the instruction scheduler. Return the new value of LAST. */
5590 reemit_notes (insn
, last
)
5597 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
5599 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5601 int note_type
= INTVAL (XEXP (note
, 0));
5602 if (note_type
== NOTE_INSN_SETJMP
)
5604 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
5605 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
5606 remove_note (insn
, note
);
5607 note
= XEXP (note
, 1);
5609 else if (note_type
== NOTE_INSN_RANGE_START
5610 || note_type
== NOTE_INSN_RANGE_END
)
5612 last
= emit_note_before (note_type
, last
);
5613 remove_note (insn
, note
);
5614 note
= XEXP (note
, 1);
5615 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
5619 last
= emit_note_before (note_type
, last
);
5620 remove_note (insn
, note
);
5621 note
= XEXP (note
, 1);
5622 if (note_type
== NOTE_INSN_EH_REGION_BEG
5623 || note_type
== NOTE_INSN_EH_REGION_END
)
5624 NOTE_EH_HANDLER (last
) = INTVAL (XEXP (note
, 0));
5626 remove_note (insn
, note
);
5632 /* Move INSN, and all insns which should be issued before it,
5633 due to SCHED_GROUP_P flag. Reemit notes if needed.
5635 Return the last insn emitted by the scheduler, which is the
5636 return value from the first call to reemit_notes. */
5639 move_insn (insn
, last
)
5644 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5645 insns with SCHED_GROUP_P set first. */
5646 while (SCHED_GROUP_P (insn
))
5648 rtx prev
= PREV_INSN (insn
);
5650 /* Move a SCHED_GROUP_P insn. */
5651 move_insn1 (insn
, last
);
5652 /* If this is the first call to reemit_notes, then record
5653 its return value. */
5654 if (retval
== NULL_RTX
)
5655 retval
= reemit_notes (insn
, insn
);
5657 reemit_notes (insn
, insn
);
5661 /* Now move the first non SCHED_GROUP_P insn. */
5662 move_insn1 (insn
, last
);
5664 /* If this is the first call to reemit_notes, then record
5665 its return value. */
5666 if (retval
== NULL_RTX
)
5667 retval
= reemit_notes (insn
, insn
);
5669 reemit_notes (insn
, insn
);
5674 /* Return an insn which represents a SCHED_GROUP, which is
5675 the last insn in the group. */
5686 insn
= next_nonnote_insn (insn
);
5688 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
5693 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5694 possibly bringing insns from subsequent blocks in the same region.
5695 Return number of insns scheduled. */
5698 schedule_block (bb
, rgn_n_insns
)
5702 /* Local variables. */
5708 /* Flow block of this bb. */
5709 int b
= BB_TO_BLOCK (bb
);
5711 /* target_n_insns == number of insns in b before scheduling starts.
5712 sched_target_n_insns == how many of b's insns were scheduled.
5713 sched_n_insns == how many insns were scheduled in b. */
5714 int target_n_insns
= 0;
5715 int sched_target_n_insns
= 0;
5716 int sched_n_insns
= 0;
5718 #define NEED_NOTHING 0
5723 /* Head/tail info for this block. */
5730 /* We used to have code to avoid getting parameters moved from hard
5731 argument registers into pseudos.
5733 However, it was removed when it proved to be of marginal benefit
5734 and caused problems because schedule_block and compute_forward_dependences
5735 had different notions of what the "head" insn was. */
5736 get_bb_head_tail (bb
, &head
, &tail
);
5738 /* Interblock scheduling could have moved the original head insn from this
5739 block into a proceeding block. This may also cause schedule_block and
5740 compute_forward_dependences to have different notions of what the
5743 If the interblock movement happened to make this block start with
5744 some notes (LOOP, EH or SETJMP) before the first real insn, then
5745 HEAD will have various special notes attached to it which must be
5746 removed so that we don't end up with extra copies of the notes. */
5747 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
5751 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
5752 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5753 remove_note (head
, note
);
5756 next_tail
= NEXT_INSN (tail
);
5757 prev_head
= PREV_INSN (head
);
5759 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5760 to schedule this block. */
5762 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5763 return (sched_n_insns
);
5768 fprintf (dump
, ";; ======================================================\n");
5770 ";; -- basic block %d from %d to %d -- %s reload\n",
5771 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
5772 (reload_completed
? "after" : "before"));
5773 fprintf (dump
, ";; ======================================================\n");
5774 fprintf (dump
, "\n");
5776 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
5777 init_block_visualization ();
5780 /* Remove remaining note insns from the block, save them in
5781 note_list. These notes are restored at the end of
5782 schedule_block (). */
5784 rm_other_notes (head
, tail
);
5788 /* Prepare current target block info. */
5789 if (current_nr_blocks
> 1)
5791 candidate_table
= (candidate
*) alloca (current_nr_blocks
5792 * sizeof (candidate
));
5795 /* ??? It is not clear why bblst_size is computed this way. The original
5796 number was clearly too small as it resulted in compiler failures.
5797 Multiplying by the original number by 2 (to account for update_bbs
5798 members) seems to be a reasonable solution. */
5799 /* ??? Or perhaps there is a bug somewhere else in this file? */
5800 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
5801 bblst_table
= (int *) alloca (bblst_size
* sizeof (int));
5803 bitlst_table_last
= 0;
5804 bitlst_table_size
= rgn_nr_edges
;
5805 bitlst_table
= (int *) alloca (rgn_nr_edges
* sizeof (int));
5807 compute_trg_info (bb
);
5812 /* Allocate the ready list. */
5813 ready
= (rtx
*) alloca ((rgn_n_insns
+ 1) * sizeof (rtx
));
5815 /* Print debugging information. */
5816 if (sched_verbose
>= 5)
5817 debug_dependencies ();
5820 /* Initialize ready list with all 'ready' insns in target block.
5821 Count number of insns in the target block being scheduled. */
5823 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5827 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5829 next
= NEXT_INSN (insn
);
5831 if (INSN_DEP_COUNT (insn
) == 0
5832 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5833 ready
[n_ready
++] = insn
;
5834 if (!(SCHED_GROUP_P (insn
)))
5838 /* Add to ready list all 'ready' insns in valid source blocks.
5839 For speculative insns, check-live, exception-free, and
5841 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
5842 if (IS_VALID (bb_src
))
5848 get_bb_head_tail (bb_src
, &head
, &tail
);
5849 src_next_tail
= NEXT_INSN (tail
);
5853 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5856 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
5858 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5861 if (!CANT_MOVE (insn
)
5862 && (!IS_SPECULATIVE_INSN (insn
)
5863 || (insn_issue_delay (insn
) <= 3
5864 && check_live (insn
, bb_src
)
5865 && is_exception_free (insn
, bb_src
, target_bb
))))
5870 /* Note that we havn't squirrled away the notes for
5871 blocks other than the current. So if this is a
5872 speculative insn, NEXT might otherwise be a note. */
5873 next
= next_nonnote_insn (insn
);
5874 if (INSN_DEP_COUNT (insn
) == 0
5875 && (SCHED_GROUP_P (next
) == 0
5876 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5877 ready
[n_ready
++] = insn
;
5882 #ifdef MD_SCHED_INIT
5883 MD_SCHED_INIT (dump
, sched_verbose
);
5886 /* No insns scheduled in this block yet. */
5887 last_scheduled_insn
= 0;
5889 /* Q_SIZE is the total number of insns in the queue. */
5893 bzero ((char *) insn_queue
, sizeof (insn_queue
));
5895 /* Start just before the beginning of time. */
5898 /* We start inserting insns after PREV_HEAD. */
5901 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
5902 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
5903 ? NEED_HEAD
: NEED_NOTHING
);
5904 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
5905 new_needs
|= NEED_TAIL
;
5907 /* Loop until all the insns in BB are scheduled. */
5908 while (sched_target_n_insns
< target_n_insns
)
5912 /* Add to the ready list all pending insns that can be issued now.
5913 If there are no ready insns, increment clock until one
5914 is ready and add all pending insns at that point to the ready
5916 n_ready
= queue_to_ready (ready
, n_ready
);
5921 if (sched_verbose
>= 2)
5923 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
5924 debug_ready_list (ready
, n_ready
);
5927 /* Sort the ready list based on priority. */
5928 SCHED_SORT (ready
, n_ready
);
5930 /* Allow the target to reorder the list, typically for
5931 better instruction bundling. */
5932 #ifdef MD_SCHED_REORDER
5933 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
, clock_var
,
5936 can_issue_more
= issue_rate
;
5941 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
5942 debug_ready_list (ready
, n_ready
);
5945 /* Issue insns from ready list. */
5946 while (n_ready
!= 0 && can_issue_more
)
5948 /* Select and remove the insn from the ready list. */
5949 rtx insn
= ready
[--n_ready
];
5950 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
5954 queue_insn (insn
, cost
);
5958 /* An interblock motion? */
5959 if (INSN_BB (insn
) != target_bb
)
5964 if (IS_SPECULATIVE_INSN (insn
))
5966 if (!check_live (insn
, INSN_BB (insn
)))
5968 update_live (insn
, INSN_BB (insn
));
5970 /* For speculative load, mark insns fed by it. */
5971 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
5972 set_spec_fed (insn
);
5978 /* Find the beginning of the scheduling group. */
5979 /* ??? Ought to update basic block here, but later bits of
5980 schedule_block assumes the original insn block is
5984 while (SCHED_GROUP_P (insn
))
5985 temp
= PREV_INSN (temp
);
5987 /* Update source block boundaries. */
5988 b1
= BLOCK_FOR_INSN (temp
);
5989 if (temp
== b1
->head
&& insn
== b1
->end
)
5991 /* We moved all the insns in the basic block.
5992 Emit a note after the last insn and update the
5993 begin/end boundaries to point to the note. */
5994 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
5998 else if (insn
== b1
->end
)
6000 /* We took insns from the end of the basic block,
6001 so update the end of block boundary so that it
6002 points to the first insn we did not move. */
6003 b1
->end
= PREV_INSN (temp
);
6005 else if (temp
== b1
->head
)
6007 /* We took insns from the start of the basic block,
6008 so update the start of block boundary so that
6009 it points to the first insn we did not move. */
6010 b1
->head
= NEXT_INSN (insn
);
6015 /* In block motion. */
6016 sched_target_n_insns
++;
6019 last_scheduled_insn
= insn
;
6020 last
= move_insn (insn
, last
);
6023 #ifdef MD_SCHED_VARIABLE_ISSUE
6024 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
,
6030 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6032 /* Close this block after scheduling its jump. */
6033 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6039 visualize_scheduled_insns (b
, clock_var
);
6045 fprintf (dump
, ";;\tReady list (final): ");
6046 debug_ready_list (ready
, n_ready
);
6047 print_block_visualization (b
, "");
6050 /* Sanity check -- queue must be empty now. Meaningless if region has
6052 if (current_nr_blocks
> 1)
6053 if (!flag_schedule_interblock
&& q_size
!= 0)
6056 /* Update head/tail boundaries. */
6057 head
= NEXT_INSN (prev_head
);
6060 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6061 previously found among the insns. Insert them at the beginning
6065 rtx note_head
= note_list
;
6067 while (PREV_INSN (note_head
))
6069 note_head
= PREV_INSN (note_head
);
6072 PREV_INSN (note_head
) = PREV_INSN (head
);
6073 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6074 PREV_INSN (head
) = note_list
;
6075 NEXT_INSN (note_list
) = head
;
6079 /* Update target block boundaries. */
6080 if (new_needs
& NEED_HEAD
)
6081 BLOCK_HEAD (b
) = head
;
6083 if (new_needs
& NEED_TAIL
)
6084 BLOCK_END (b
) = tail
;
6089 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6090 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
6091 fprintf (dump
, ";; new basic block end = %d\n\n",
6092 INSN_UID (BLOCK_END (b
)));
6095 return (sched_n_insns
);
6096 } /* schedule_block () */
6099 /* Print the bit-set of registers, S, callable from debugger. */
6102 debug_reg_vector (s
)
6107 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
6109 fprintf (dump
, " %d", regno
);
6112 fprintf (dump
, "\n");
6115 /* Use the backward dependences from LOG_LINKS to build
6116 forward dependences in INSN_DEPEND. */
6119 compute_block_forward_dependences (bb
)
6125 enum reg_note dep_type
;
6127 get_bb_head_tail (bb
, &head
, &tail
);
6128 next_tail
= NEXT_INSN (tail
);
6129 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6131 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6134 insn
= group_leader (insn
);
6136 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
6138 rtx x
= group_leader (XEXP (link
, 0));
6141 if (x
!= XEXP (link
, 0))
6144 #ifdef ENABLE_CHECKING
6145 /* If add_dependence is working properly there should never
6146 be notes, deleted insns or duplicates in the backward
6147 links. Thus we need not check for them here.
6149 However, if we have enabled checking we might as well go
6150 ahead and verify that add_dependence worked properly. */
6151 if (GET_CODE (x
) == NOTE
6152 || INSN_DELETED_P (x
)
6153 || find_insn_list (insn
, INSN_DEPEND (x
)))
6157 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
6159 dep_type
= REG_NOTE_KIND (link
);
6160 PUT_REG_NOTE_KIND (new_link
, dep_type
);
6162 INSN_DEPEND (x
) = new_link
;
6163 INSN_DEP_COUNT (insn
) += 1;
6168 /* Initialize variables for region data dependence analysis.
6169 n_bbs is the number of region blocks. */
6171 __inline
static void
6172 init_rgn_data_dependences (n_bbs
)
6177 /* Variables for which one copy exists for each block. */
6178 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
6179 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
6180 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
6181 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
6182 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (rtx
));
6183 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
6184 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
6185 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
6187 /* Create an insn here so that we can hang dependencies off of it later. */
6188 for (bb
= 0; bb
< n_bbs
; bb
++)
6190 bb_sched_before_next_call
[bb
] =
6191 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6192 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6193 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
6197 /* Add dependences so that branches are scheduled to run last in their
6201 add_branch_dependences (head
, tail
)
6207 /* For all branches, calls, uses, and cc0 setters, force them to remain
6208 in order at the end of the block by adding dependencies and giving
6209 the last a high priority. There may be notes present, and prev_head
6212 Branches must obviously remain at the end. Calls should remain at the
6213 end since moving them results in worse register allocation. Uses remain
6214 at the end to ensure proper register allocation. cc0 setters remaim
6215 at the end because they can't be moved away from their cc0 user. */
6218 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
6219 || (GET_CODE (insn
) == INSN
6220 && (GET_CODE (PATTERN (insn
)) == USE
6222 || sets_cc0_p (PATTERN (insn
))
6225 || GET_CODE (insn
) == NOTE
)
6227 if (GET_CODE (insn
) != NOTE
)
6230 && !find_insn_list (insn
, LOG_LINKS (last
)))
6232 add_dependence (last
, insn
, REG_DEP_ANTI
);
6233 INSN_REF_COUNT (insn
)++;
6236 CANT_MOVE (insn
) = 1;
6239 /* Skip over insns that are part of a group.
6240 Make each insn explicitly depend on the previous insn.
6241 This ensures that only the group header will ever enter
6242 the ready queue (and, when scheduled, will automatically
6243 schedule the SCHED_GROUP_P block). */
6244 while (SCHED_GROUP_P (insn
))
6246 rtx temp
= prev_nonnote_insn (insn
);
6247 add_dependence (insn
, temp
, REG_DEP_ANTI
);
6252 /* Don't overrun the bounds of the basic block. */
6256 insn
= PREV_INSN (insn
);
6259 /* Make sure these insns are scheduled last in their block. */
6262 while (insn
!= head
)
6264 insn
= prev_nonnote_insn (insn
);
6266 if (INSN_REF_COUNT (insn
) != 0)
6269 add_dependence (last
, insn
, REG_DEP_ANTI
);
6270 INSN_REF_COUNT (insn
) = 1;
6272 /* Skip over insns that are part of a group. */
6273 while (SCHED_GROUP_P (insn
))
6274 insn
= prev_nonnote_insn (insn
);
6278 /* Compute backward dependences inside bb. In a multiple blocks region:
6279 (1) a bb is analyzed after its predecessors, and (2) the lists in
6280 effect at the end of bb (after analyzing for bb) are inherited by
6283 Specifically for reg-reg data dependences, the block insns are
6284 scanned by sched_analyze () top-to-bottom. Two lists are
6285 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6286 and reg_last_uses[] for register USEs.
6288 When analysis is completed for bb, we update for its successors:
6289 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6290 ; - USES[succ] = Union (USES [succ], DEFS [bb])
6292 The mechanism for computing mem-mem data dependence is very
6293 similar, and the result is interblock dependences in the region. */
6296 compute_block_backward_dependences (bb
)
6302 int max_reg
= max_reg_num ();
6304 b
= BB_TO_BLOCK (bb
);
6306 if (current_nr_blocks
== 1)
6308 reg_last_uses
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
6309 reg_last_sets
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
6310 reg_last_clobbers
= (rtx
*) alloca (max_reg
* sizeof (rtx
));
6312 bzero ((char *) reg_last_uses
, max_reg
* sizeof (rtx
));
6313 bzero ((char *) reg_last_sets
, max_reg
* sizeof (rtx
));
6314 bzero ((char *) reg_last_clobbers
, max_reg
* sizeof (rtx
));
6316 pending_read_insns
= 0;
6317 pending_read_mems
= 0;
6318 pending_write_insns
= 0;
6319 pending_write_mems
= 0;
6320 pending_lists_length
= 0;
6321 last_function_call
= 0;
6322 last_pending_memory_flush
= 0;
6323 sched_before_next_call
6324 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6325 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6326 LOG_LINKS (sched_before_next_call
) = 0;
6330 reg_last_uses
= bb_reg_last_uses
[bb
];
6331 reg_last_sets
= bb_reg_last_sets
[bb
];
6332 reg_last_clobbers
= bb_reg_last_clobbers
[bb
];
6334 pending_read_insns
= bb_pending_read_insns
[bb
];
6335 pending_read_mems
= bb_pending_read_mems
[bb
];
6336 pending_write_insns
= bb_pending_write_insns
[bb
];
6337 pending_write_mems
= bb_pending_write_mems
[bb
];
6338 pending_lists_length
= bb_pending_lists_length
[bb
];
6339 last_function_call
= bb_last_function_call
[bb
];
6340 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
6342 sched_before_next_call
= bb_sched_before_next_call
[bb
];
6345 /* Do the analysis for this block. */
6346 get_bb_head_tail (bb
, &head
, &tail
);
6347 sched_analyze (head
, tail
);
6348 add_branch_dependences (head
, tail
);
6350 if (current_nr_blocks
> 1)
6353 int b_succ
, bb_succ
;
6355 rtx link_insn
, link_mem
;
6358 /* These lists should point to the right place, for correct
6360 bb_pending_read_insns
[bb
] = pending_read_insns
;
6361 bb_pending_read_mems
[bb
] = pending_read_mems
;
6362 bb_pending_write_insns
[bb
] = pending_write_insns
;
6363 bb_pending_write_mems
[bb
] = pending_write_mems
;
6365 /* bb's structures are inherited by it's successors. */
6366 first_edge
= e
= OUT_EDGES (b
);
6370 b_succ
= TO_BLOCK (e
);
6371 bb_succ
= BLOCK_TO_BB (b_succ
);
6373 /* Only bbs "below" bb, in the same region, are interesting. */
6374 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
6381 for (reg
= 0; reg
< max_reg
; reg
++)
6384 /* reg-last-uses lists are inherited by bb_succ. */
6385 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
6387 if (find_insn_list (XEXP (u
, 0),
6388 (bb_reg_last_uses
[bb_succ
])[reg
]))
6391 (bb_reg_last_uses
[bb_succ
])[reg
]
6392 = alloc_INSN_LIST (XEXP (u
, 0),
6393 (bb_reg_last_uses
[bb_succ
])[reg
]);
6396 /* reg-last-defs lists are inherited by bb_succ. */
6397 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
6399 if (find_insn_list (XEXP (u
, 0),
6400 (bb_reg_last_sets
[bb_succ
])[reg
]))
6403 (bb_reg_last_sets
[bb_succ
])[reg
]
6404 = alloc_INSN_LIST (XEXP (u
, 0),
6405 (bb_reg_last_sets
[bb_succ
])[reg
]);
6408 for (u
= reg_last_clobbers
[reg
]; u
; u
= XEXP (u
, 1))
6410 if (find_insn_list (XEXP (u
, 0),
6411 (bb_reg_last_clobbers
[bb_succ
])[reg
]))
6414 (bb_reg_last_clobbers
[bb_succ
])[reg
]
6415 = alloc_INSN_LIST (XEXP (u
, 0),
6416 (bb_reg_last_clobbers
[bb_succ
])[reg
]);
6420 /* Mem read/write lists are inherited by bb_succ. */
6421 link_insn
= pending_read_insns
;
6422 link_mem
= pending_read_mems
;
6425 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6427 bb_pending_read_insns
[bb_succ
],
6428 bb_pending_read_mems
[bb_succ
])))
6429 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
6430 &bb_pending_read_mems
[bb_succ
],
6431 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6432 link_insn
= XEXP (link_insn
, 1);
6433 link_mem
= XEXP (link_mem
, 1);
6436 link_insn
= pending_write_insns
;
6437 link_mem
= pending_write_mems
;
6440 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6442 bb_pending_write_insns
[bb_succ
],
6443 bb_pending_write_mems
[bb_succ
])))
6444 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
6445 &bb_pending_write_mems
[bb_succ
],
6446 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6448 link_insn
= XEXP (link_insn
, 1);
6449 link_mem
= XEXP (link_mem
, 1);
6452 /* last_function_call is inherited by bb_succ. */
6453 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
6455 if (find_insn_list (XEXP (u
, 0),
6456 bb_last_function_call
[bb_succ
]))
6459 bb_last_function_call
[bb_succ
]
6460 = alloc_INSN_LIST (XEXP (u
, 0),
6461 bb_last_function_call
[bb_succ
]);
6464 /* last_pending_memory_flush is inherited by bb_succ. */
6465 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
6467 if (find_insn_list (XEXP (u
, 0),
6468 bb_last_pending_memory_flush
[bb_succ
]))
6471 bb_last_pending_memory_flush
[bb_succ
]
6472 = alloc_INSN_LIST (XEXP (u
, 0),
6473 bb_last_pending_memory_flush
[bb_succ
]);
6476 /* sched_before_next_call is inherited by bb_succ. */
6477 x
= LOG_LINKS (sched_before_next_call
);
6478 for (; x
; x
= XEXP (x
, 1))
6479 add_dependence (bb_sched_before_next_call
[bb_succ
],
6480 XEXP (x
, 0), REG_DEP_ANTI
);
6484 while (e
!= first_edge
);
6487 /* Free up the INSN_LISTs.
6489 Note this loop is executed max_reg * nr_regions times. It's first
6490 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6491 The list was empty for the vast majority of those calls. On the PA, not
6492 calling free_INSN_LIST_list in those cases improves -O2 compile times by
6494 for (b
= 0; b
< max_reg
; ++b
)
6496 if (reg_last_clobbers
[b
])
6497 free_INSN_LIST_list (®_last_clobbers
[b
]);
6498 if (reg_last_sets
[b
])
6499 free_INSN_LIST_list (®_last_sets
[b
]);
6500 if (reg_last_uses
[b
])
6501 free_INSN_LIST_list (®_last_uses
[b
]);
6504 /* Assert that we won't need bb_reg_last_* for this block anymore. */
6505 if (current_nr_blocks
> 1)
6507 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
6508 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
6509 bb_reg_last_clobbers
[bb
] = (rtx
*) NULL_RTX
;
6513 /* Print dependences for debugging, callable from debugger. */
6516 debug_dependencies ()
6520 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
6521 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6529 get_bb_head_tail (bb
, &head
, &tail
);
6530 next_tail
= NEXT_INSN (tail
);
6531 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
6532 BB_TO_BLOCK (bb
), bb
);
6534 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6535 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6536 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6537 "----", "----", "--", "---", "----", "----", "--------", "-----");
6538 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6543 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6546 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
6547 if (GET_CODE (insn
) == NOTE
)
6549 n
= NOTE_LINE_NUMBER (insn
);
6551 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
6553 fprintf (dump
, "line %d, file %s\n", n
,
6554 NOTE_SOURCE_FILE (insn
));
6557 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
6561 unit
= insn_unit (insn
);
6563 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
6564 function_units
[unit
].blockage_range_function (insn
);
6566 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
6567 (SCHED_GROUP_P (insn
) ? "+" : " "),
6571 INSN_DEP_COUNT (insn
),
6572 INSN_PRIORITY (insn
),
6573 insn_cost (insn
, 0, 0),
6574 (int) MIN_BLOCKAGE_COST (range
),
6575 (int) MAX_BLOCKAGE_COST (range
));
6576 insn_print_units (insn
);
6577 fprintf (dump
, "\t: ");
6578 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
6579 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
6580 fprintf (dump
, "\n");
6584 fprintf (dump
, "\n");
6587 /* Set_priorities: compute priority of each insn in the block. */
6600 get_bb_head_tail (bb
, &head
, &tail
);
6601 prev_head
= PREV_INSN (head
);
6604 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6608 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
6611 if (GET_CODE (insn
) == NOTE
)
6614 if (!(SCHED_GROUP_P (insn
)))
6616 (void) priority (insn
);
6622 /* Make each element of VECTOR point at an rtx-vector,
6623 taking the space for all those rtx-vectors from SPACE.
6624 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
6625 BYTES_PER_ELT is the number of bytes in one rtx-vector.
6626 (this is the same as init_regset_vector () in flow.c) */
6629 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
6636 register rtx
*p
= space
;
6638 for (i
= 0; i
< nelts
; i
++)
6641 p
+= bytes_per_elt
/ sizeof (*p
);
6645 /* Schedule a region. A region is either an inner loop, a loop-free
6646 subroutine, or a single basic block. Each bb in the region is
6647 scheduled after its flow predecessors. */
6650 schedule_region (rgn
)
6654 int rgn_n_insns
= 0;
6655 int sched_rgn_n_insns
= 0;
6657 /* Set variables for the current region. */
6658 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
6659 current_blocks
= RGN_BLOCKS (rgn
);
6661 reg_pending_sets
= ALLOCA_REG_SET ();
6662 reg_pending_clobbers
= ALLOCA_REG_SET ();
6663 reg_pending_sets_all
= 0;
6665 /* Initializations for region data dependence analyisis. */
6666 if (current_nr_blocks
> 1)
6669 int maxreg
= max_reg_num ();
6671 bb_reg_last_uses
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
6672 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
6673 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
6674 init_rtx_vector (bb_reg_last_uses
, space
, current_nr_blocks
,
6675 maxreg
* sizeof (rtx
*));
6677 bb_reg_last_sets
= (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
6678 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
6679 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
6680 init_rtx_vector (bb_reg_last_sets
, space
, current_nr_blocks
,
6681 maxreg
* sizeof (rtx
*));
6683 bb_reg_last_clobbers
=
6684 (rtx
**) alloca (current_nr_blocks
* sizeof (rtx
*));
6685 space
= (rtx
*) alloca (current_nr_blocks
* maxreg
* sizeof (rtx
));
6686 bzero ((char *) space
, current_nr_blocks
* maxreg
* sizeof (rtx
));
6687 init_rtx_vector (bb_reg_last_clobbers
, space
, current_nr_blocks
,
6688 maxreg
* sizeof (rtx
*));
6690 bb_pending_read_insns
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6691 bb_pending_read_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6692 bb_pending_write_insns
=
6693 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6694 bb_pending_write_mems
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6695 bb_pending_lists_length
=
6696 (int *) alloca (current_nr_blocks
* sizeof (int));
6697 bb_last_pending_memory_flush
=
6698 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6699 bb_last_function_call
= (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6700 bb_sched_before_next_call
=
6701 (rtx
*) alloca (current_nr_blocks
* sizeof (rtx
));
6703 init_rgn_data_dependences (current_nr_blocks
);
6706 /* Compute LOG_LINKS. */
6707 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6708 compute_block_backward_dependences (bb
);
6710 /* Compute INSN_DEPEND. */
6711 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
6712 compute_block_forward_dependences (bb
);
6714 /* Delete line notes and set priorities. */
6715 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6717 if (write_symbols
!= NO_DEBUG
)
6719 save_line_notes (bb
);
6723 rgn_n_insns
+= set_priorities (bb
);
6726 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6727 if (current_nr_blocks
> 1)
6731 prob
= (float *) alloca ((current_nr_blocks
) * sizeof (float));
6733 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
6734 dom
= (bbset
*) alloca (current_nr_blocks
* sizeof (bbset
));
6735 for (i
= 0; i
< current_nr_blocks
; i
++)
6737 dom
[i
] = (bbset
) alloca (bbset_size
* sizeof (HOST_WIDE_INT
));
6738 bzero ((char *) dom
[i
], bbset_size
* sizeof (HOST_WIDE_INT
));
6743 edge_to_bit
= (int *) alloca (nr_edges
* sizeof (int));
6744 for (i
= 1; i
< nr_edges
; i
++)
6745 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
6746 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
6747 rgn_edges
= (int *) alloca (rgn_nr_edges
* sizeof (int));
6750 for (i
= 1; i
< nr_edges
; i
++)
6751 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
6752 rgn_edges
[rgn_nr_edges
++] = i
;
6755 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
6756 pot_split
= (edgeset
*) alloca (current_nr_blocks
* sizeof (edgeset
));
6757 ancestor_edges
= (edgeset
*) alloca (current_nr_blocks
6758 * sizeof (edgeset
));
6759 for (i
= 0; i
< current_nr_blocks
; i
++)
6762 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
6763 bzero ((char *) pot_split
[i
],
6764 edgeset_size
* sizeof (HOST_WIDE_INT
));
6766 (edgeset
) alloca (edgeset_size
* sizeof (HOST_WIDE_INT
));
6767 bzero ((char *) ancestor_edges
[i
],
6768 edgeset_size
* sizeof (HOST_WIDE_INT
));
6771 /* Compute probabilities, dominators, split_edges. */
6772 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6773 compute_dom_prob_ps (bb
);
6776 /* Now we can schedule all blocks. */
6777 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6779 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
6786 /* Sanity check: verify that all region insns were scheduled. */
6787 if (sched_rgn_n_insns
!= rgn_n_insns
)
6790 /* Restore line notes. */
6791 if (write_symbols
!= NO_DEBUG
)
6793 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6794 restore_line_notes (bb
);
6797 /* Done with this region. */
6798 free_pending_lists ();
6800 FREE_REG_SET (reg_pending_sets
);
6801 FREE_REG_SET (reg_pending_clobbers
);
6804 /* The one entry point in this file. DUMP_FILE is the dump file for
6808 schedule_insns (dump_file
)
6811 int *deaths_in_region
;
6812 sbitmap blocks
, large_region_blocks
;
6818 int any_large_regions
;
6820 /* Disable speculative loads in their presence if cc0 defined. */
6822 flag_schedule_speculative_load
= 0;
6825 /* Taking care of this degenerate case makes the rest of
6826 this code simpler. */
6827 if (n_basic_blocks
== 0)
6830 /* Set dump and sched_verbose for the desired debugging output. If no
6831 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
6832 For -fsched-verbose-N, N>=10, print everything to stderr. */
6833 sched_verbose
= sched_verbose_param
;
6834 if (sched_verbose_param
== 0 && dump_file
)
6836 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
6841 /* Initialize issue_rate. */
6842 issue_rate
= ISSUE_RATE
;
6844 split_all_insns (1);
6846 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6847 pseudos which do not cross calls. */
6848 max_uid
= get_max_uid () + 1;
6850 cant_move
= xcalloc (max_uid
, sizeof (char));
6851 fed_by_spec_load
= xcalloc (max_uid
, sizeof (char));
6852 is_load_insn
= xcalloc (max_uid
, sizeof (char));
6854 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
6858 for (b
= 0; b
< n_basic_blocks
; b
++)
6859 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
6861 INSN_LUID (insn
) = luid
;
6863 /* Increment the next luid, unless this is a note. We don't
6864 really need separate IDs for notes and we don't want to
6865 schedule differently depending on whether or not there are
6866 line-number notes, i.e., depending on whether or not we're
6867 generating debugging information. */
6868 if (GET_CODE (insn
) != NOTE
)
6871 if (insn
== BLOCK_END (b
))
6875 /* ?!? We could save some memory by computing a per-region luid mapping
6876 which could reduce both the number of vectors in the cache and the size
6877 of each vector. Instead we just avoid the cache entirely unless the
6878 average number of instructions in a basic block is very high. See
6879 the comment before the declaration of true_dependency_cache for
6880 what we consider "very high". */
6881 if (luid
/ n_basic_blocks
> 100 * 5)
6883 true_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
6884 sbitmap_vector_zero (true_dependency_cache
, luid
);
6888 rgn_table
= (region
*) alloca ((n_basic_blocks
) * sizeof (region
));
6889 rgn_bb_table
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
6890 block_to_bb
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
6891 containing_rgn
= (int *) alloca ((n_basic_blocks
) * sizeof (int));
6893 blocks
= sbitmap_alloc (n_basic_blocks
);
6894 large_region_blocks
= sbitmap_alloc (n_basic_blocks
);
6896 compute_bb_for_insn (max_uid
);
6898 /* Compute regions for scheduling. */
6899 if (reload_completed
6900 || n_basic_blocks
== 1
6901 || !flag_schedule_interblock
)
6903 find_single_block_region ();
6907 /* Verify that a 'good' control flow graph can be built. */
6908 if (is_cfg_nonregular ())
6910 find_single_block_region ();
6914 int_list_ptr
*s_preds
, *s_succs
;
6915 int *num_preds
, *num_succs
;
6916 sbitmap
*dom
, *pdom
;
6918 s_preds
= (int_list_ptr
*) alloca (n_basic_blocks
6919 * sizeof (int_list_ptr
));
6920 s_succs
= (int_list_ptr
*) alloca (n_basic_blocks
6921 * sizeof (int_list_ptr
));
6922 num_preds
= (int *) alloca (n_basic_blocks
* sizeof (int));
6923 num_succs
= (int *) alloca (n_basic_blocks
* sizeof (int));
6924 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6925 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6927 /* The scheduler runs after flow; therefore, we can't blindly call
6928 back into find_basic_blocks since doing so could invalidate the
6929 info in global_live_at_start.
6931 Consider a block consisting entirely of dead stores; after life
6932 analysis it would be a block of NOTE_INSN_DELETED notes. If
6933 we call find_basic_blocks again, then the block would be removed
6934 entirely and invalidate our the register live information.
6936 We could (should?) recompute register live information. Doing
6937 so may even be beneficial. */
6939 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
6941 /* Compute the dominators and post dominators. We don't
6942 currently use post dominators, but we should for
6943 speculative motion analysis. */
6944 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
6946 /* build_control_flow will return nonzero if it detects unreachable
6947 blocks or any other irregularity with the cfg which prevents
6948 cross block scheduling. */
6949 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
6950 find_single_block_region ();
6952 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
6954 if (sched_verbose
>= 3)
6957 /* For now. This will move as more and more of haifa is converted
6958 to using the cfg code in flow.c. */
6965 /* Allocate data for this pass. See comments, above,
6966 for what these vectors do.
6968 We use xmalloc instead of alloca, because max_uid can be very large
6969 when there is a lot of function inlining. If we used alloca, we could
6970 exceed stack limits on some hosts for some inputs. */
6971 insn_priority
= (int *) xcalloc (max_uid
, sizeof (int));
6972 insn_reg_weight
= (int *) xcalloc (max_uid
, sizeof (int));
6973 insn_tick
= (int *) xcalloc (max_uid
, sizeof (int));
6974 insn_costs
= (short *) xcalloc (max_uid
, sizeof (short));
6975 insn_units
= (short *) xcalloc (max_uid
, sizeof (short));
6976 insn_blockage
= (unsigned int *) xcalloc (max_uid
, sizeof (unsigned int));
6977 insn_ref_count
= (int *) xcalloc (max_uid
, sizeof (int));
6979 /* Allocate for forward dependencies. */
6980 insn_dep_count
= (int *) xcalloc (max_uid
, sizeof (int));
6981 insn_depend
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
6983 deaths_in_region
= (int *) alloca (sizeof(int) * nr_regions
);
6985 init_alias_analysis ();
6987 if (write_symbols
!= NO_DEBUG
)
6991 line_note
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
6992 line_note_head
= (rtx
*) alloca (n_basic_blocks
* sizeof (rtx
));
6993 bzero ((char *) line_note_head
, n_basic_blocks
* sizeof (rtx
));
6995 /* Save-line-note-head:
6996 Determine the line-number at the start of each basic block.
6997 This must be computed and saved now, because after a basic block's
6998 predecessor has been scheduled, it is impossible to accurately
6999 determine the correct line number for the first insn of the block. */
7001 for (b
= 0; b
< n_basic_blocks
; b
++)
7002 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
7003 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
7005 line_note_head
[b
] = line
;
7010 /* Find units used in this fuction, for visualization. */
7012 init_target_units ();
7014 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7015 known why this is done. */
7017 insn
= BLOCK_END (n_basic_blocks
- 1);
7018 if (NEXT_INSN (insn
) == 0
7019 || (GET_CODE (insn
) != NOTE
7020 && GET_CODE (insn
) != CODE_LABEL
7021 /* Don't emit a NOTE if it would end up between an unconditional
7022 jump and a BARRIER. */
7023 && !(GET_CODE (insn
) == JUMP_INSN
7024 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
7025 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
7027 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
7028 removing death notes. */
7029 for (b
= n_basic_blocks
- 1; b
>= 0; b
--)
7030 find_insn_reg_weight (b
);
7032 /* Remove all death notes from the subroutine. */
7033 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7035 sbitmap_zero (blocks
);
7036 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
7037 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
7039 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
7042 /* Schedule every region in the subroutine. */
7043 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7045 schedule_region (rgn
);
7052 /* Update life analysis for the subroutine. Do single block regions
7053 first so that we can verify that live_at_start didn't change. Then
7054 do all other blocks. */
7055 /* ??? There is an outside possibility that update_life_info, or more
7056 to the point propagate_block, could get called with non-zero flags
7057 more than once for one basic block. This would be kinda bad if it
7058 were to happen, since REG_INFO would be accumulated twice for the
7059 block, and we'd have twice the REG_DEAD notes.
7061 I'm fairly certain that this _shouldn't_ happen, since I don't think
7062 that live_at_start should change at region heads. Not sure what the
7063 best way to test for this kind of thing... */
7065 allocate_reg_life_data ();
7066 compute_bb_for_insn (max_uid
);
7068 any_large_regions
= 0;
7069 sbitmap_ones (large_region_blocks
);
7071 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7072 if (RGN_NR_BLOCKS (rgn
) > 1)
7073 any_large_regions
= 1;
7076 sbitmap_zero (blocks
);
7077 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7078 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7080 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
7081 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7083 /* In the single block case, the count of registers that died should
7084 not have changed during the schedule. */
7085 if (count_or_remove_death_notes (blocks
, 0) != deaths_in_region
[rgn
])
7089 if (any_large_regions
)
7091 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
7092 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7095 /* Reposition the prologue and epilogue notes in case we moved the
7096 prologue/epilogue insns. */
7097 if (reload_completed
)
7098 reposition_prologue_and_epilogue_notes (get_insns ());
7100 /* Delete redundant line notes. */
7101 if (write_symbols
!= NO_DEBUG
)
7102 rm_redundant_line_notes ();
7106 if (reload_completed
== 0 && flag_schedule_interblock
)
7108 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
7116 fprintf (dump
, "\n\n");
7119 if (true_dependency_cache
)
7121 free (true_dependency_cache
);
7122 true_dependency_cache
= NULL
;
7125 free (fed_by_spec_load
);
7126 free (is_load_insn
);
7129 free (insn_priority
);
7130 free (insn_reg_weight
);
7134 free (insn_blockage
);
7135 free (insn_ref_count
);
7137 free (insn_dep_count
);
7140 if (write_symbols
!= NO_DEBUG
)
7160 sbitmap_free (blocks
);
7161 sbitmap_free (large_region_blocks
);
7163 #endif /* INSN_SCHEDULING */