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
);
831 #ifdef INSN_SCHEDULING
832 /* If we are adding a true dependency to INSN's LOG_LINKs, then
833 note that in the bitmap cache of true dependency information. */
834 if ((int)dep_type
== 0 && true_dependency_cache
)
835 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
840 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
841 of INSN. Abort if not found. */
844 remove_dependence (insn
, elem
)
848 rtx prev
, link
, next
;
851 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
853 next
= XEXP (link
, 1);
854 if (XEXP (link
, 0) == elem
)
857 XEXP (prev
, 1) = next
;
859 LOG_LINKS (insn
) = next
;
861 #ifdef INSN_SCHEDULING
862 /* If we are removing a true dependency from the LOG_LINKS list,
863 make sure to remove it from the cache too. */
864 if (REG_NOTE_KIND (link
) == 0 && true_dependency_cache
)
865 RESET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
869 free_INSN_LIST_node (link
);
881 #endif /* HAVE_cc0 */
883 #ifndef INSN_SCHEDULING
885 schedule_insns (dump_file
)
895 #define HAIFA_INLINE __inline
898 /* Computation of memory dependencies. */
900 /* The *_insns and *_mems are paired lists. Each pending memory operation
901 will have a pointer to the MEM rtx on one list and a pointer to the
902 containing insn on the other list in the same place in the list. */
904 /* We can't use add_dependence like the old code did, because a single insn
905 may have multiple memory accesses, and hence needs to be on the list
906 once for each memory access. Add_dependence won't let you add an insn
907 to a list more than once. */
909 /* An INSN_LIST containing all insns with pending read operations. */
910 static rtx pending_read_insns
;
912 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
913 static rtx pending_read_mems
;
915 /* An INSN_LIST containing all insns with pending write operations. */
916 static rtx pending_write_insns
;
918 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
919 static rtx pending_write_mems
;
921 /* Indicates the combined length of the two pending lists. We must prevent
922 these lists from ever growing too large since the number of dependencies
923 produced is at least O(N*N), and execution time is at least O(4*N*N), as
924 a function of the length of these pending lists. */
926 static int pending_lists_length
;
928 /* The last insn upon which all memory references must depend.
929 This is an insn which flushed the pending lists, creating a dependency
930 between it and all previously pending memory references. This creates
931 a barrier (or a checkpoint) which no memory reference is allowed to cross.
933 This includes all non constant CALL_INSNs. When we do interprocedural
934 alias analysis, this restriction can be relaxed.
935 This may also be an INSN that writes memory if the pending lists grow
938 static rtx last_pending_memory_flush
;
940 /* The last function call we have seen. All hard regs, and, of course,
941 the last function call, must depend on this. */
943 static rtx last_function_call
;
945 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
946 that does not already cross a call. We create dependencies between each
947 of those insn and the next call insn, to ensure that they won't cross a call
948 after scheduling is done. */
950 static rtx sched_before_next_call
;
952 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
953 so that insns independent of the last scheduled insn will be preferred
954 over dependent instructions. */
956 static rtx last_scheduled_insn
;
958 /* Data structures for the computation of data dependences in a regions. We
959 keep one copy of each of the declared above variables for each bb in the
960 region. Before analyzing the data dependences for a bb, its variables
961 are initialized as a function of the variables of its predecessors. When
962 the analysis for a bb completes, we save the contents of each variable X
963 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
964 copied to bb_pending_read_insns[bb]. Another change is that few
965 variables are now a list of insns rather than a single insn:
966 last_pending_memory_flash, last_function_call, reg_last_sets. The
967 manipulation of these variables was changed appropriately. */
969 static rtx
**bb_reg_last_uses
;
970 static rtx
**bb_reg_last_sets
;
971 static rtx
**bb_reg_last_clobbers
;
973 static rtx
*bb_pending_read_insns
;
974 static rtx
*bb_pending_read_mems
;
975 static rtx
*bb_pending_write_insns
;
976 static rtx
*bb_pending_write_mems
;
977 static int *bb_pending_lists_length
;
979 static rtx
*bb_last_pending_memory_flush
;
980 static rtx
*bb_last_function_call
;
981 static rtx
*bb_sched_before_next_call
;
983 /* Functions for construction of the control flow graph. */
985 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
987 We decide not to build the control flow graph if there is possibly more
988 than one entry to the function, if computed branches exist, of if we
989 have nonlocal gotos. */
998 /* If we have a label that could be the target of a nonlocal goto, then
999 the cfg is not well structured. */
1000 if (nonlocal_goto_handler_labels
)
1003 /* If we have any forced labels, then the cfg is not well structured. */
1007 /* If this function has a computed jump, then we consider the cfg
1008 not well structured. */
1009 if (current_function_has_computed_jump
)
1012 /* If we have exception handlers, then we consider the cfg not well
1013 structured. ?!? We should be able to handle this now that flow.c
1014 computes an accurate cfg for EH. */
1015 if (exception_handler_labels
)
1018 /* If we have non-jumping insns which refer to labels, then we consider
1019 the cfg not well structured. */
1020 /* Check for labels referred to other thn by jumps. */
1021 for (b
= 0; b
< n_basic_blocks
; b
++)
1022 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1024 code
= GET_CODE (insn
);
1025 if (GET_RTX_CLASS (code
) == 'i')
1029 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1030 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1034 if (insn
== BLOCK_END (b
))
1038 /* All the tests passed. Consider the cfg well structured. */
1042 /* Build the control flow graph and set nr_edges.
1044 Instead of trying to build a cfg ourselves, we rely on flow to
1045 do it for us. Stamp out useless code (and bug) duplication.
1047 Return nonzero if an irregularity in the cfg is found which would
1048 prevent cross block scheduling. */
1051 build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
)
1052 int_list_ptr
*s_preds
;
1053 int_list_ptr
*s_succs
;
1061 /* Count the number of edges in the cfg. */
1064 for (i
= 0; i
< n_basic_blocks
; i
++)
1066 nr_edges
+= num_succs
[i
];
1068 /* Unreachable loops with more than one basic block are detected
1069 during the DFS traversal in find_rgns.
1071 Unreachable loops with a single block are detected here. This
1072 test is redundant with the one in find_rgns, but it's much
1073 cheaper to go ahead and catch the trivial case here. */
1074 if (num_preds
[i
] == 0
1075 || (num_preds
[i
] == 1 && INT_LIST_VAL (s_preds
[i
]) == i
))
1079 /* Account for entry/exit edges. */
1082 in_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1083 out_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1084 edge_table
= (haifa_edge
*) xcalloc (nr_edges
, sizeof (haifa_edge
));
1087 for (i
= 0; i
< n_basic_blocks
; i
++)
1088 for (succ
= s_succs
[i
]; succ
; succ
= succ
->next
)
1090 if (INT_LIST_VAL (succ
) != EXIT_BLOCK
)
1091 new_edge (i
, INT_LIST_VAL (succ
));
1094 /* Increment by 1, since edge 0 is unused. */
1101 /* Record an edge in the control flow graph from SOURCE to TARGET.
1103 In theory, this is redundant with the s_succs computed above, but
1104 we have not converted all of haifa to use information from the
1108 new_edge (source
, target
)
1112 int curr_edge
, fst_edge
;
1114 /* Check for duplicates. */
1115 fst_edge
= curr_edge
= OUT_EDGES (source
);
1118 if (FROM_BLOCK (curr_edge
) == source
1119 && TO_BLOCK (curr_edge
) == target
)
1124 curr_edge
= NEXT_OUT (curr_edge
);
1126 if (fst_edge
== curr_edge
)
1132 FROM_BLOCK (e
) = source
;
1133 TO_BLOCK (e
) = target
;
1135 if (OUT_EDGES (source
))
1137 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1138 NEXT_OUT (OUT_EDGES (source
)) = e
;
1139 NEXT_OUT (e
) = next_edge
;
1143 OUT_EDGES (source
) = e
;
1147 if (IN_EDGES (target
))
1149 next_edge
= NEXT_IN (IN_EDGES (target
));
1150 NEXT_IN (IN_EDGES (target
)) = e
;
1151 NEXT_IN (e
) = next_edge
;
1155 IN_EDGES (target
) = e
;
1161 /* BITSET macros for operations on the control flow graph. */
1163 /* Compute bitwise union of two bitsets. */
1164 #define BITSET_UNION(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 intersection of two bitsets. */
1171 #define BITSET_INTER(set1, set2, len) \
1172 do { register bitset tp = set1, sp = set2; \
1174 for (i = 0; i < len; i++) \
1175 *(tp++) &= *(sp++); } while (0)
1177 /* Compute bitwise difference of two bitsets. */
1178 #define BITSET_DIFFER(set1, set2, len) \
1179 do { register bitset tp = set1, sp = set2; \
1181 for (i = 0; i < len; i++) \
1182 *(tp++) &= ~*(sp++); } while (0)
1184 /* Inverts every bit of bitset 'set'. */
1185 #define BITSET_INVERT(set, len) \
1186 do { register bitset tmpset = set; \
1188 for (i = 0; i < len; i++, tmpset++) \
1189 *tmpset = ~*tmpset; } while (0)
1191 /* Turn on the index'th bit in bitset set. */
1192 #define BITSET_ADD(set, index, len) \
1194 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1197 set[index/HOST_BITS_PER_WIDE_INT] |= \
1198 1 << (index % HOST_BITS_PER_WIDE_INT); \
1201 /* Turn off the index'th bit in set. */
1202 #define BITSET_REMOVE(set, index, len) \
1204 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1207 set[index/HOST_BITS_PER_WIDE_INT] &= \
1208 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1212 /* Check if the index'th bit in bitset set is on. */
1215 bitset_member (set
, index
, len
)
1219 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1221 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1222 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1226 /* Translate a bit-set SET to a list BL of the bit-set members. */
1229 extract_bitlst (set
, len
, bl
)
1235 unsigned HOST_WIDE_INT word
;
1237 /* bblst table space is reused in each call to extract_bitlst. */
1238 bitlst_table_last
= 0;
1240 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1243 for (i
= 0; i
< len
; i
++)
1246 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1247 for (j
= 0; word
; j
++)
1251 bitlst_table
[bitlst_table_last
++] = offset
;
1262 /* Functions for the construction of regions. */
1264 /* Print the regions, for debugging purposes. Callable from debugger. */
1271 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1272 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1274 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1275 rgn_table
[rgn
].rgn_nr_blocks
);
1276 fprintf (dump
, ";;\tbb/block: ");
1278 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1280 current_blocks
= RGN_BLOCKS (rgn
);
1282 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1285 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1288 fprintf (dump
, "\n\n");
1293 /* Build a single block region for each basic block in the function.
1294 This allows for using the same code for interblock and basic block
1298 find_single_block_region ()
1302 for (i
= 0; i
< n_basic_blocks
; i
++)
1304 rgn_bb_table
[i
] = i
;
1305 RGN_NR_BLOCKS (i
) = 1;
1307 CONTAINING_RGN (i
) = i
;
1308 BLOCK_TO_BB (i
) = 0;
1310 nr_regions
= n_basic_blocks
;
1314 /* Update number of blocks and the estimate for number of insns
1315 in the region. Return 1 if the region is "too large" for interblock
1316 scheduling (compile time considerations), otherwise return 0. */
1319 too_large (block
, num_bbs
, num_insns
)
1320 int block
, *num_bbs
, *num_insns
;
1323 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1324 INSN_LUID (BLOCK_HEAD (block
)));
1325 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1332 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1333 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1334 loop containing blk. */
1335 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1337 if (max_hdr[blk] == -1) \
1338 max_hdr[blk] = hdr; \
1339 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1340 RESET_BIT (inner, hdr); \
1341 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1343 RESET_BIT (inner,max_hdr[blk]); \
1344 max_hdr[blk] = hdr; \
1349 /* Find regions for interblock scheduling.
1351 A region for scheduling can be:
1353 * A loop-free procedure, or
1355 * A reducible inner loop, or
1357 * A basic block not contained in any other region.
1360 ?!? In theory we could build other regions based on extended basic
1361 blocks or reverse extended basic blocks. Is it worth the trouble?
1363 Loop blocks that form a region are put into the region's block list
1364 in topological order.
1366 This procedure stores its results into the following global (ick) variables
1375 We use dominator relationships to avoid making regions out of non-reducible
1378 This procedure needs to be converted to work on pred/succ lists instead
1379 of edge tables. That would simplify it somewhat. */
1382 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
)
1383 int_list_ptr
*s_preds
;
1384 int_list_ptr
*s_succs
;
1389 int *max_hdr
, *dfs_nr
, *stack
, *degree
;
1391 int node
, child
, loop_head
, i
, head
, tail
;
1392 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1393 int num_bbs
, num_insns
, unreachable
;
1394 int too_large_failure
;
1396 /* Note if an edge has been passed. */
1399 /* Note if a block is a natural loop header. */
1402 /* Note if a block is an natural inner loop header. */
1405 /* Note if a block is in the block queue. */
1408 /* Note if a block is in the block queue. */
1411 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1412 and a mapping from block to its loop header (if the block is contained
1413 in a loop, else -1).
1415 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1416 be used as inputs to the second traversal.
1418 STACK, SP and DFS_NR are only used during the first traversal. */
1420 /* Allocate and initialize variables for the first traversal. */
1421 max_hdr
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1422 dfs_nr
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1423 stack
= (int *) xmalloc (nr_edges
* sizeof (int));
1425 inner
= sbitmap_alloc (n_basic_blocks
);
1426 sbitmap_ones (inner
);
1428 header
= sbitmap_alloc (n_basic_blocks
);
1429 sbitmap_zero (header
);
1431 passed
= sbitmap_alloc (nr_edges
);
1432 sbitmap_zero (passed
);
1434 in_queue
= sbitmap_alloc (n_basic_blocks
);
1435 sbitmap_zero (in_queue
);
1437 in_stack
= sbitmap_alloc (n_basic_blocks
);
1438 sbitmap_zero (in_stack
);
1440 for (i
= 0; i
< n_basic_blocks
; i
++)
1443 /* DFS traversal to find inner loops in the cfg. */
1448 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1450 /* We have reached a leaf node or a node that was already
1451 processed. Pop edges off the stack until we find
1452 an edge that has not yet been processed. */
1454 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1456 /* Pop entry off the stack. */
1457 current_edge
= stack
[sp
--];
1458 node
= FROM_BLOCK (current_edge
);
1459 child
= TO_BLOCK (current_edge
);
1460 RESET_BIT (in_stack
, child
);
1461 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1462 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1463 current_edge
= NEXT_OUT (current_edge
);
1466 /* See if have finished the DFS tree traversal. */
1467 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1470 /* Nope, continue the traversal with the popped node. */
1474 /* Process a node. */
1475 node
= FROM_BLOCK (current_edge
);
1476 child
= TO_BLOCK (current_edge
);
1477 SET_BIT (in_stack
, node
);
1478 dfs_nr
[node
] = ++count
;
1480 /* If the successor is in the stack, then we've found a loop.
1481 Mark the loop, if it is not a natural loop, then it will
1482 be rejected during the second traversal. */
1483 if (TEST_BIT (in_stack
, child
))
1486 SET_BIT (header
, child
);
1487 UPDATE_LOOP_RELATIONS (node
, child
);
1488 SET_BIT (passed
, current_edge
);
1489 current_edge
= NEXT_OUT (current_edge
);
1493 /* If the child was already visited, then there is no need to visit
1494 it again. Just update the loop relationships and restart
1498 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1499 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1500 SET_BIT (passed
, current_edge
);
1501 current_edge
= NEXT_OUT (current_edge
);
1505 /* Push an entry on the stack and continue DFS traversal. */
1506 stack
[++sp
] = current_edge
;
1507 SET_BIT (passed
, current_edge
);
1508 current_edge
= OUT_EDGES (child
);
1510 /* This is temporary until haifa is converted to use rth's new
1511 cfg routines which have true entry/exit blocks and the
1512 appropriate edges from/to those blocks.
1514 Generally we update dfs_nr for a node when we process its
1515 out edge. However, if the node has no out edge then we will
1516 not set dfs_nr for that node. This can confuse the scheduler
1517 into thinking that we have unreachable blocks, which in turn
1518 disables cross block scheduling.
1520 So, if we have a node with no out edges, go ahead and mark it
1521 as reachable now. */
1522 if (current_edge
== 0)
1523 dfs_nr
[child
] = ++count
;
1526 /* Another check for unreachable blocks. The earlier test in
1527 is_cfg_nonregular only finds unreachable blocks that do not
1530 The DFS traversal will mark every block that is reachable from
1531 the entry node by placing a nonzero value in dfs_nr. Thus if
1532 dfs_nr is zero for any block, then it must be unreachable. */
1534 for (i
= 0; i
< n_basic_blocks
; i
++)
1541 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1542 to hold degree counts. */
1545 /* Compute the in-degree of every block in the graph. */
1546 for (i
= 0; i
< n_basic_blocks
; i
++)
1547 degree
[i
] = num_preds
[i
];
1549 /* Do not perform region scheduling if there are any unreachable
1556 SET_BIT (header
, 0);
1558 /* Second travsersal:find reducible inner loops and topologically sort
1559 block of each region. */
1561 queue
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1563 /* Find blocks which are inner loop headers. We still have non-reducible
1564 loops to consider at this point. */
1565 for (i
= 0; i
< n_basic_blocks
; i
++)
1567 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1572 /* Now check that the loop is reducible. We do this separate
1573 from finding inner loops so that we do not find a reducible
1574 loop which contains an inner non-reducible loop.
1576 A simple way to find reducible/natural loops is to verify
1577 that each block in the loop is dominated by the loop
1580 If there exists a block that is not dominated by the loop
1581 header, then the block is reachable from outside the loop
1582 and thus the loop is not a natural loop. */
1583 for (j
= 0; j
< n_basic_blocks
; j
++)
1585 /* First identify blocks in the loop, except for the loop
1587 if (i
== max_hdr
[j
] && i
!= j
)
1589 /* Now verify that the block is dominated by the loop
1591 if (!TEST_BIT (dom
[j
], i
))
1596 /* If we exited the loop early, then I is the header of
1597 a non-reducible loop and we should quit processing it
1599 if (j
!= n_basic_blocks
)
1602 /* I is a header of an inner loop, or block 0 in a subroutine
1603 with no loops at all. */
1605 too_large_failure
= 0;
1606 loop_head
= max_hdr
[i
];
1608 /* Decrease degree of all I's successors for topological
1610 for (ps
= s_succs
[i
]; ps
; ps
= ps
->next
)
1611 if (INT_LIST_VAL (ps
) != EXIT_BLOCK
1612 && INT_LIST_VAL (ps
) != ENTRY_BLOCK
)
1613 --degree
[INT_LIST_VAL(ps
)];
1615 /* Estimate # insns, and count # blocks in the region. */
1617 num_insns
= (INSN_LUID (BLOCK_END (i
))
1618 - INSN_LUID (BLOCK_HEAD (i
)));
1621 /* Find all loop latches (blocks with back edges to the loop
1622 header) or all the leaf blocks in the cfg has no loops.
1624 Place those blocks into the queue. */
1627 for (j
= 0; j
< n_basic_blocks
; j
++)
1628 /* Leaf nodes have only a single successor which must
1630 if (num_succs
[j
] == 1
1631 && INT_LIST_VAL (s_succs
[j
]) == EXIT_BLOCK
)
1634 SET_BIT (in_queue
, j
);
1636 if (too_large (j
, &num_bbs
, &num_insns
))
1638 too_large_failure
= 1;
1647 for (ps
= s_preds
[i
]; ps
; ps
= ps
->next
)
1649 node
= INT_LIST_VAL (ps
);
1651 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
)
1654 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1656 /* This is a loop latch. */
1657 queue
[++tail
] = node
;
1658 SET_BIT (in_queue
, node
);
1660 if (too_large (node
, &num_bbs
, &num_insns
))
1662 too_large_failure
= 1;
1670 /* Now add all the blocks in the loop to the queue.
1672 We know the loop is a natural loop; however the algorithm
1673 above will not always mark certain blocks as being in the
1682 The algorithm in the DFS traversal may not mark B & D as part
1683 of the loop (ie they will not have max_hdr set to A).
1685 We know they can not be loop latches (else they would have
1686 had max_hdr set since they'd have a backedge to a dominator
1687 block). So we don't need them on the initial queue.
1689 We know they are part of the loop because they are dominated
1690 by the loop header and can be reached by a backwards walk of
1691 the edges starting with nodes on the initial queue.
1693 It is safe and desirable to include those nodes in the
1694 loop/scheduling region. To do so we would need to decrease
1695 the degree of a node if it is the target of a backedge
1696 within the loop itself as the node is placed in the queue.
1698 We do not do this because I'm not sure that the actual
1699 scheduling code will properly handle this case. ?!? */
1701 while (head
< tail
&& !too_large_failure
)
1704 child
= queue
[++head
];
1706 for (ps
= s_preds
[child
]; ps
; ps
= ps
->next
)
1708 node
= INT_LIST_VAL (ps
);
1710 /* See discussion above about nodes not marked as in
1711 this loop during the initial DFS traversal. */
1712 if (node
== ENTRY_BLOCK
|| node
== EXIT_BLOCK
1713 || max_hdr
[node
] != loop_head
)
1718 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1720 queue
[++tail
] = node
;
1721 SET_BIT (in_queue
, node
);
1723 if (too_large (node
, &num_bbs
, &num_insns
))
1725 too_large_failure
= 1;
1732 if (tail
>= 0 && !too_large_failure
)
1734 /* Place the loop header into list of region blocks. */
1736 rgn_bb_table
[idx
] = i
;
1737 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1738 RGN_BLOCKS (nr_regions
) = idx
++;
1739 CONTAINING_RGN (i
) = nr_regions
;
1740 BLOCK_TO_BB (i
) = count
= 0;
1742 /* Remove blocks from queue[] when their in degree
1743 becomes zero. Repeat until no blocks are left on the
1744 list. This produces a topological list of blocks in
1752 child
= queue
[head
];
1753 if (degree
[child
] == 0)
1756 rgn_bb_table
[idx
++] = child
;
1757 BLOCK_TO_BB (child
) = ++count
;
1758 CONTAINING_RGN (child
) = nr_regions
;
1759 queue
[head
] = queue
[tail
--];
1761 for (ps
= s_succs
[child
]; ps
; ps
= ps
->next
)
1762 if (INT_LIST_VAL (ps
) != ENTRY_BLOCK
1763 && INT_LIST_VAL (ps
) != EXIT_BLOCK
)
1764 --degree
[INT_LIST_VAL (ps
)];
1776 /* Any block that did not end up in a region is placed into a region
1778 for (i
= 0; i
< n_basic_blocks
; i
++)
1781 rgn_bb_table
[idx
] = i
;
1782 RGN_NR_BLOCKS (nr_regions
) = 1;
1783 RGN_BLOCKS (nr_regions
) = idx
++;
1784 CONTAINING_RGN (i
) = nr_regions
++;
1785 BLOCK_TO_BB (i
) = 0;
1799 /* Functions for regions scheduling information. */
1801 /* Compute dominators, probability, and potential-split-edges of bb.
1802 Assume that these values were already computed for bb's predecessors. */
1805 compute_dom_prob_ps (bb
)
1808 int nxt_in_edge
, fst_in_edge
, pred
;
1809 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1812 if (IS_RGN_ENTRY (bb
))
1814 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1819 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1821 /* Intialize dom[bb] to '111..1'. */
1822 BITSET_INVERT (dom
[bb
], bbset_size
);
1826 pred
= FROM_BLOCK (nxt_in_edge
);
1827 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1829 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1832 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1835 nr_rgn_out_edges
= 0;
1836 fst_out_edge
= OUT_EDGES (pred
);
1837 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1838 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1841 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1843 /* The successor doesn't belong in the region? */
1844 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1845 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1848 while (fst_out_edge
!= nxt_out_edge
)
1851 /* The successor doesn't belong in the region? */
1852 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1853 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1855 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1856 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1860 /* Now nr_rgn_out_edges is the number of region-exit edges from
1861 pred, and nr_out_edges will be the number of pred out edges
1862 not leaving the region. */
1863 nr_out_edges
-= nr_rgn_out_edges
;
1864 if (nr_rgn_out_edges
> 0)
1865 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1867 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1868 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1870 while (fst_in_edge
!= nxt_in_edge
);
1872 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1873 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1875 if (sched_verbose
>= 2)
1876 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1877 } /* compute_dom_prob_ps */
1879 /* Functions for target info. */
1881 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1882 Note that bb_trg dominates bb_src. */
1885 split_edges (bb_src
, bb_trg
, bl
)
1890 int es
= edgeset_size
;
1891 edgeset src
= (edgeset
) xmalloc (es
* sizeof (HOST_WIDE_INT
));
1894 src
[es
] = (pot_split
[bb_src
])[es
];
1895 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1896 extract_bitlst (src
, edgeset_size
, bl
);
1901 /* Find the valid candidate-source-blocks for the target block TRG, compute
1902 their probability, and check if they are speculative or not.
1903 For speculative sources, compute their update-blocks and split-blocks. */
1906 compute_trg_info (trg
)
1909 register candidate
*sp
;
1911 int check_block
, update_idx
;
1912 int i
, j
, k
, fst_edge
, nxt_edge
;
1914 /* Define some of the fields for the target bb as well. */
1915 sp
= candidate_table
+ trg
;
1917 sp
->is_speculative
= 0;
1920 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1922 sp
= candidate_table
+ i
;
1924 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1927 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1928 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1933 split_edges (i
, trg
, &el
);
1934 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1935 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1941 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1942 sp
->split_bbs
.nr_members
= el
.nr_members
;
1943 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1944 bblst_table
[bblst_last
] =
1945 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1946 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1948 for (j
= 0; j
< el
.nr_members
; j
++)
1950 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1951 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
1954 for (k
= 0; k
< el
.nr_members
; k
++)
1955 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
1958 if (k
>= el
.nr_members
)
1960 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
1964 nxt_edge
= NEXT_OUT (nxt_edge
);
1966 while (fst_edge
!= nxt_edge
);
1968 sp
->update_bbs
.nr_members
= update_idx
;
1973 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1975 sp
->is_speculative
= 0;
1979 } /* compute_trg_info */
1982 /* Print candidates info, for debugging purposes. Callable from debugger. */
1988 if (!candidate_table
[i
].is_valid
)
1991 if (candidate_table
[i
].is_speculative
)
1994 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
1996 fprintf (dump
, "split path: ");
1997 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
1999 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2001 fprintf (dump
, " %d ", b
);
2003 fprintf (dump
, "\n");
2005 fprintf (dump
, "update path: ");
2006 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2008 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2010 fprintf (dump
, " %d ", b
);
2012 fprintf (dump
, "\n");
2016 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2021 /* Print candidates info, for debugging purposes. Callable from debugger. */
2024 debug_candidates (trg
)
2029 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2030 BB_TO_BLOCK (trg
), trg
);
2031 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2032 debug_candidate (i
);
2036 /* Functions for speculative scheduing. */
2038 /* Return 0 if x is a set of a register alive in the beginning of one
2039 of the split-blocks of src, otherwise return 1. */
2042 check_live_1 (src
, x
)
2048 register rtx reg
= SET_DEST (x
);
2053 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2054 || GET_CODE (reg
) == SIGN_EXTRACT
2055 || GET_CODE (reg
) == STRICT_LOW_PART
)
2056 reg
= XEXP (reg
, 0);
2058 if (GET_CODE (reg
) == PARALLEL
2059 && GET_MODE (reg
) == BLKmode
)
2062 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2063 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2068 if (GET_CODE (reg
) != REG
)
2071 regno
= REGNO (reg
);
2073 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2075 /* Global registers are assumed live. */
2080 if (regno
< FIRST_PSEUDO_REGISTER
)
2082 /* Check for hard registers. */
2083 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2086 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2088 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2090 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
2100 /* Check for psuedo registers. */
2101 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2103 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2105 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, regno
))
2117 /* If x is a set of a register R, mark that R is alive in the beginning
2118 of every update-block of src. */
2121 update_live_1 (src
, x
)
2127 register rtx reg
= SET_DEST (x
);
2132 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2133 || GET_CODE (reg
) == SIGN_EXTRACT
2134 || GET_CODE (reg
) == STRICT_LOW_PART
)
2135 reg
= XEXP (reg
, 0);
2137 if (GET_CODE (reg
) == PARALLEL
2138 && GET_MODE (reg
) == BLKmode
)
2141 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2142 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2146 if (GET_CODE (reg
) != REG
)
2149 /* Global registers are always live, so the code below does not apply
2152 regno
= REGNO (reg
);
2154 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2156 if (regno
< FIRST_PSEUDO_REGISTER
)
2158 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2161 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2163 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2165 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
,
2172 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2174 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2176 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, regno
);
2183 /* Return 1 if insn can be speculatively moved from block src to trg,
2184 otherwise return 0. Called before first insertion of insn to
2185 ready-list or before the scheduling. */
2188 check_live (insn
, src
)
2192 /* Find the registers set by instruction. */
2193 if (GET_CODE (PATTERN (insn
)) == SET
2194 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2195 return check_live_1 (src
, PATTERN (insn
));
2196 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2199 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2200 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2201 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2202 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2212 /* Update the live registers info after insn was moved speculatively from
2213 block src to trg. */
2216 update_live (insn
, src
)
2220 /* Find the registers set by instruction. */
2221 if (GET_CODE (PATTERN (insn
)) == SET
2222 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2223 update_live_1 (src
, PATTERN (insn
));
2224 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2227 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2228 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2229 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2230 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2234 /* Exception Free Loads:
2236 We define five classes of speculative loads: IFREE, IRISKY,
2237 PFREE, PRISKY, and MFREE.
2239 IFREE loads are loads that are proved to be exception-free, just
2240 by examining the load insn. Examples for such loads are loads
2241 from TOC and loads of global data.
2243 IRISKY loads are loads that are proved to be exception-risky,
2244 just by examining the load insn. Examples for such loads are
2245 volatile loads and loads from shared memory.
2247 PFREE loads are loads for which we can prove, by examining other
2248 insns, that they are exception-free. Currently, this class consists
2249 of loads for which we are able to find a "similar load", either in
2250 the target block, or, if only one split-block exists, in that split
2251 block. Load2 is similar to load1 if both have same single base
2252 register. We identify only part of the similar loads, by finding
2253 an insn upon which both load1 and load2 have a DEF-USE dependence.
2255 PRISKY loads are loads for which we can prove, by examining other
2256 insns, that they are exception-risky. Currently we have two proofs for
2257 such loads. The first proof detects loads that are probably guarded by a
2258 test on the memory address. This proof is based on the
2259 backward and forward data dependence information for the region.
2260 Let load-insn be the examined load.
2261 Load-insn is PRISKY iff ALL the following hold:
2263 - insn1 is not in the same block as load-insn
2264 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2265 - test-insn is either a compare or a branch, not in the same block
2267 - load-insn is reachable from test-insn
2268 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2270 This proof might fail when the compare and the load are fed
2271 by an insn not in the region. To solve this, we will add to this
2272 group all loads that have no input DEF-USE dependence.
2274 The second proof detects loads that are directly or indirectly
2275 fed by a speculative load. This proof is affected by the
2276 scheduling process. We will use the flag fed_by_spec_load.
2277 Initially, all insns have this flag reset. After a speculative
2278 motion of an insn, if insn is either a load, or marked as
2279 fed_by_spec_load, we will also mark as fed_by_spec_load every
2280 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2281 load which is fed_by_spec_load is also PRISKY.
2283 MFREE (maybe-free) loads are all the remaining loads. They may be
2284 exception-free, but we cannot prove it.
2286 Now, all loads in IFREE and PFREE classes are considered
2287 exception-free, while all loads in IRISKY and PRISKY classes are
2288 considered exception-risky. As for loads in the MFREE class,
2289 these are considered either exception-free or exception-risky,
2290 depending on whether we are pessimistic or optimistic. We have
2291 to take the pessimistic approach to assure the safety of
2292 speculative scheduling, but we can take the optimistic approach
2293 by invoking the -fsched_spec_load_dangerous option. */
2295 enum INSN_TRAP_CLASS
2297 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2298 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2301 #define WORST_CLASS(class1, class2) \
2302 ((class1 > class2) ? class1 : class2)
2304 /* Indexed by INSN_UID, and set if there's DEF-USE dependence between
2305 some speculatively moved load insn and this one. */
2306 char *fed_by_spec_load
;
2309 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2310 #define IS_REACHABLE(bb_from, bb_to) \
2312 || IS_RGN_ENTRY (bb_from) \
2313 || (bitset_member (ancestor_edges[bb_to], \
2314 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2316 #define FED_BY_SPEC_LOAD(insn) (fed_by_spec_load[INSN_UID (insn)])
2317 #define IS_LOAD_INSN(insn) (is_load_insn[INSN_UID (insn)])
2319 /* Non-zero iff the address is comprised from at most 1 register. */
2320 #define CONST_BASED_ADDRESS_P(x) \
2321 (GET_CODE (x) == REG \
2322 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2323 || (GET_CODE (x) == LO_SUM)) \
2324 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2325 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2327 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2330 set_spec_fed (load_insn
)
2335 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2336 if (GET_MODE (link
) == VOIDmode
)
2337 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2338 } /* set_spec_fed */
2340 /* On the path from the insn to load_insn_bb, find a conditional
2341 branch depending on insn, that guards the speculative load. */
2344 find_conditional_protection (insn
, load_insn_bb
)
2350 /* Iterate through DEF-USE forward dependences. */
2351 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2353 rtx next
= XEXP (link
, 0);
2354 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
2355 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2356 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2357 && load_insn_bb
!= INSN_BB (next
)
2358 && GET_MODE (link
) == VOIDmode
2359 && (GET_CODE (next
) == JUMP_INSN
2360 || find_conditional_protection (next
, load_insn_bb
)))
2364 } /* find_conditional_protection */
2366 /* Returns 1 if the same insn1 that participates in the computation
2367 of load_insn's address is feeding a conditional branch that is
2368 guarding on load_insn. This is true if we find a the two DEF-USE
2370 insn1 -> ... -> conditional-branch
2371 insn1 -> ... -> load_insn,
2372 and if a flow path exist:
2373 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2374 and if insn1 is on the path
2375 region-entry -> ... -> bb_trg -> ... load_insn.
2377 Locate insn1 by climbing on LOG_LINKS from load_insn.
2378 Locate the branch by following INSN_DEPEND from insn1. */
2381 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2387 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2389 rtx insn1
= XEXP (link
, 0);
2391 /* Must be a DEF-USE dependence upon non-branch. */
2392 if (GET_MODE (link
) != VOIDmode
2393 || GET_CODE (insn1
) == JUMP_INSN
)
2396 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2397 if (INSN_BB (insn1
) == bb_src
2398 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
2399 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2400 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2401 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2404 /* Now search for the conditional-branch. */
2405 if (find_conditional_protection (insn1
, bb_src
))
2408 /* Recursive step: search another insn1, "above" current insn1. */
2409 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2412 /* The chain does not exist. */
2414 } /* is_conditionally_protected */
2416 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2417 load_insn can move speculatively from bb_src to bb_trg. All the
2418 following must hold:
2420 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2421 (2) load_insn and load1 have a def-use dependence upon
2422 the same insn 'insn1'.
2423 (3) either load2 is in bb_trg, or:
2424 - there's only one split-block, and
2425 - load1 is on the escape path, and
2427 From all these we can conclude that the two loads access memory
2428 addresses that differ at most by a constant, and hence if moving
2429 load_insn would cause an exception, it would have been caused by
2433 is_pfree (load_insn
, bb_src
, bb_trg
)
2438 register candidate
*candp
= candidate_table
+ bb_src
;
2440 if (candp
->split_bbs
.nr_members
!= 1)
2441 /* Must have exactly one escape block. */
2444 for (back_link
= LOG_LINKS (load_insn
);
2445 back_link
; back_link
= XEXP (back_link
, 1))
2447 rtx insn1
= XEXP (back_link
, 0);
2449 if (GET_MODE (back_link
) == VOIDmode
)
2451 /* Found a DEF-USE dependence (insn1, load_insn). */
2454 for (fore_link
= INSN_DEPEND (insn1
);
2455 fore_link
; fore_link
= XEXP (fore_link
, 1))
2457 rtx insn2
= XEXP (fore_link
, 0);
2458 if (GET_MODE (fore_link
) == VOIDmode
)
2460 /* Found a DEF-USE dependence (insn1, insn2). */
2461 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2462 /* insn2 not guaranteed to be a 1 base reg load. */
2465 if (INSN_BB (insn2
) == bb_trg
)
2466 /* insn2 is the similar load, in the target block. */
2469 if (*(candp
->split_bbs
.first_member
) == BLOCK_NUM (insn2
))
2470 /* insn2 is a similar load, in a split-block. */
2477 /* Couldn't find a similar load. */
2481 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2482 as found by analyzing insn's expression. */
2485 may_trap_exp (x
, is_store
)
2493 code
= GET_CODE (x
);
2503 /* The insn uses memory: a volatile load. */
2504 if (MEM_VOLATILE_P (x
))
2506 /* An exception-free load. */
2507 if (!may_trap_p (x
))
2509 /* A load with 1 base register, to be further checked. */
2510 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2511 return PFREE_CANDIDATE
;
2512 /* No info on the load, to be further checked. */
2513 return PRISKY_CANDIDATE
;
2518 int i
, insn_class
= TRAP_FREE
;
2520 /* Neither store nor load, check if it may cause a trap. */
2523 /* Recursive step: walk the insn... */
2524 fmt
= GET_RTX_FORMAT (code
);
2525 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2529 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2530 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2532 else if (fmt
[i
] == 'E')
2535 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2537 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2538 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2539 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2543 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2548 } /* may_trap_exp */
2551 /* Classifies insn for the purpose of verifying that it can be
2552 moved speculatively, by examining it's patterns, returning:
2553 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2554 TRAP_FREE: non-load insn.
2555 IFREE: load from a globaly safe location.
2556 IRISKY: volatile load.
2557 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2558 being either PFREE or PRISKY. */
2561 haifa_classify_insn (insn
)
2564 rtx pat
= PATTERN (insn
);
2565 int tmp_class
= TRAP_FREE
;
2566 int insn_class
= TRAP_FREE
;
2569 if (GET_CODE (pat
) == PARALLEL
)
2571 int i
, len
= XVECLEN (pat
, 0);
2573 for (i
= len
- 1; i
>= 0; i
--)
2575 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2579 /* Test if it is a 'store'. */
2580 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2583 /* Test if it is a store. */
2584 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2585 if (tmp_class
== TRAP_RISKY
)
2587 /* Test if it is a load. */
2589 WORST_CLASS (tmp_class
,
2590 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2593 tmp_class
= TRAP_RISKY
;
2597 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2598 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2604 code
= GET_CODE (pat
);
2608 /* Test if it is a 'store'. */
2609 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2612 /* Test if it is a store. */
2613 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2614 if (tmp_class
== TRAP_RISKY
)
2616 /* Test if it is a load. */
2618 WORST_CLASS (tmp_class
,
2619 may_trap_exp (SET_SRC (pat
), 0));
2622 tmp_class
= TRAP_RISKY
;
2626 insn_class
= tmp_class
;
2631 } /* haifa_classify_insn */
2633 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2634 a load moved speculatively, or if load_insn is protected by
2635 a compare on load_insn's address). */
2638 is_prisky (load_insn
, bb_src
, bb_trg
)
2642 if (FED_BY_SPEC_LOAD (load_insn
))
2645 if (LOG_LINKS (load_insn
) == NULL
)
2646 /* Dependence may 'hide' out of the region. */
2649 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2655 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2656 Return 1 if insn is exception-free (and the motion is valid)
2660 is_exception_free (insn
, bb_src
, bb_trg
)
2664 int insn_class
= haifa_classify_insn (insn
);
2666 /* Handle non-load insns. */
2677 if (!flag_schedule_speculative_load
)
2679 IS_LOAD_INSN (insn
) = 1;
2686 case PFREE_CANDIDATE
:
2687 if (is_pfree (insn
, bb_src
, bb_trg
))
2689 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2690 case PRISKY_CANDIDATE
:
2691 if (!flag_schedule_speculative_load_dangerous
2692 || is_prisky (insn
, bb_src
, bb_trg
))
2698 return flag_schedule_speculative_load_dangerous
;
2699 } /* is_exception_free */
2702 /* Process an insn's memory dependencies. There are four kinds of
2705 (0) read dependence: read follows read
2706 (1) true dependence: read follows write
2707 (2) anti dependence: write follows read
2708 (3) output dependence: write follows write
2710 We are careful to build only dependencies which actually exist, and
2711 use transitivity to avoid building too many links. */
2713 /* Return the INSN_LIST containing INSN in LIST, or NULL
2714 if LIST does not contain INSN. */
2716 HAIFA_INLINE
static rtx
2717 find_insn_list (insn
, list
)
2723 if (XEXP (list
, 0) == insn
)
2725 list
= XEXP (list
, 1);
2731 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2734 HAIFA_INLINE
static char
2735 find_insn_mem_list (insn
, x
, list
, list1
)
2741 if (XEXP (list
, 0) == insn
2742 && XEXP (list1
, 0) == x
)
2744 list
= XEXP (list
, 1);
2745 list1
= XEXP (list1
, 1);
2751 /* Compute the function units used by INSN. This caches the value
2752 returned by function_units_used. A function unit is encoded as the
2753 unit number if the value is non-negative and the compliment of a
2754 mask if the value is negative. A function unit index is the
2755 non-negative encoding. */
2757 HAIFA_INLINE
static int
2761 register int unit
= INSN_UNIT (insn
);
2765 recog_memoized (insn
);
2767 /* A USE insn, or something else we don't need to understand.
2768 We can't pass these directly to function_units_used because it will
2769 trigger a fatal error for unrecognizable insns. */
2770 if (INSN_CODE (insn
) < 0)
2774 unit
= function_units_used (insn
);
2775 /* Increment non-negative values so we can cache zero. */
2779 /* We only cache 16 bits of the result, so if the value is out of
2780 range, don't cache it. */
2781 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2783 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2784 INSN_UNIT (insn
) = unit
;
2786 return (unit
> 0 ? unit
- 1 : unit
);
2789 /* Compute the blockage range for executing INSN on UNIT. This caches
2790 the value returned by the blockage_range_function for the unit.
2791 These values are encoded in an int where the upper half gives the
2792 minimum value and the lower half gives the maximum value. */
2794 HAIFA_INLINE
static unsigned int
2795 blockage_range (unit
, insn
)
2799 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2802 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2804 range
= function_units
[unit
].blockage_range_function (insn
);
2805 /* We only cache the blockage range for one unit and then only if
2807 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2808 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2811 range
= BLOCKAGE_RANGE (blockage
);
2816 /* A vector indexed by function unit instance giving the last insn to use
2817 the unit. The value of the function unit instance index for unit U
2818 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2819 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2821 /* A vector indexed by function unit instance giving the minimum time when
2822 the unit will unblock based on the maximum blockage cost. */
2823 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2825 /* A vector indexed by function unit number giving the number of insns
2826 that remain to use the unit. */
2827 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2829 /* Reset the function unit state to the null state. */
2834 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2835 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2836 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2839 /* Return the issue-delay of an insn. */
2841 HAIFA_INLINE
static int
2842 insn_issue_delay (insn
)
2846 int unit
= insn_unit (insn
);
2848 /* Efficiency note: in fact, we are working 'hard' to compute a
2849 value that was available in md file, and is not available in
2850 function_units[] structure. It would be nice to have this
2851 value there, too. */
2854 if (function_units
[unit
].blockage_range_function
&&
2855 function_units
[unit
].blockage_function
)
2856 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2859 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2860 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2861 && function_units
[i
].blockage_function
)
2862 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2867 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2868 instance INSTANCE at time CLOCK if the previous actual hazard cost
2871 HAIFA_INLINE
static int
2872 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2873 int unit
, instance
, clock
, cost
;
2876 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
2878 if (tick
- clock
> cost
)
2880 /* The scheduler is operating forward, so unit's last insn is the
2881 executing insn and INSN is the candidate insn. We want a
2882 more exact measure of the blockage if we execute INSN at CLOCK
2883 given when we committed the execution of the unit's last insn.
2885 The blockage value is given by either the unit's max blockage
2886 constant, blockage range function, or blockage function. Use
2887 the most exact form for the given unit. */
2889 if (function_units
[unit
].blockage_range_function
)
2891 if (function_units
[unit
].blockage_function
)
2892 tick
+= (function_units
[unit
].blockage_function
2893 (unit_last_insn
[instance
], insn
)
2894 - function_units
[unit
].max_blockage
);
2896 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2897 - function_units
[unit
].max_blockage
);
2899 if (tick
- clock
> cost
)
2900 cost
= tick
- clock
;
2905 /* Record INSN as having begun execution on the units encoded by UNIT at
2908 HAIFA_INLINE
static void
2909 schedule_unit (unit
, insn
, clock
)
2917 int instance
= unit
;
2918 #if MAX_MULTIPLICITY > 1
2919 /* Find the first free instance of the function unit and use that
2920 one. We assume that one is free. */
2921 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2923 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2925 instance
+= FUNCTION_UNITS_SIZE
;
2928 unit_last_insn
[instance
] = insn
;
2929 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2932 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2933 if ((unit
& 1) != 0)
2934 schedule_unit (i
, insn
, clock
);
2937 /* Return the actual hazard cost of executing INSN on the units encoded by
2938 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2940 HAIFA_INLINE
static int
2941 actual_hazard (unit
, insn
, clock
, cost
)
2942 int unit
, clock
, cost
;
2949 /* Find the instance of the function unit with the minimum hazard. */
2950 int instance
= unit
;
2951 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2953 #if MAX_MULTIPLICITY > 1
2956 if (best_cost
> cost
)
2958 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2960 instance
+= FUNCTION_UNITS_SIZE
;
2961 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2963 if (this_cost
< best_cost
)
2965 best_cost
= this_cost
;
2966 if (this_cost
<= cost
)
2972 cost
= MAX (cost
, best_cost
);
2975 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2976 if ((unit
& 1) != 0)
2977 cost
= actual_hazard (i
, insn
, clock
, cost
);
2982 /* Return the potential hazard cost of executing an instruction on the
2983 units encoded by UNIT if the previous potential hazard cost was COST.
2984 An insn with a large blockage time is chosen in preference to one
2985 with a smaller time; an insn that uses a unit that is more likely
2986 to be used is chosen in preference to one with a unit that is less
2987 used. We are trying to minimize a subsequent actual hazard. */
2989 HAIFA_INLINE
static int
2990 potential_hazard (unit
, insn
, cost
)
2995 unsigned int minb
, maxb
;
2999 minb
= maxb
= function_units
[unit
].max_blockage
;
3002 if (function_units
[unit
].blockage_range_function
)
3004 maxb
= minb
= blockage_range (unit
, insn
);
3005 maxb
= MAX_BLOCKAGE_COST (maxb
);
3006 minb
= MIN_BLOCKAGE_COST (minb
);
3011 /* Make the number of instructions left dominate. Make the
3012 minimum delay dominate the maximum delay. If all these
3013 are the same, use the unit number to add an arbitrary
3014 ordering. Other terms can be added. */
3015 ncost
= minb
* 0x40 + maxb
;
3016 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3023 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3024 if ((unit
& 1) != 0)
3025 cost
= potential_hazard (i
, insn
, cost
);
3030 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3031 This is the number of cycles between instruction issue and
3032 instruction results. */
3034 HAIFA_INLINE
static int
3035 insn_cost (insn
, link
, used
)
3036 rtx insn
, link
, used
;
3038 register int cost
= INSN_COST (insn
);
3042 recog_memoized (insn
);
3044 /* A USE insn, or something else we don't need to understand.
3045 We can't pass these directly to result_ready_cost because it will
3046 trigger a fatal error for unrecognizable insns. */
3047 if (INSN_CODE (insn
) < 0)
3049 INSN_COST (insn
) = 1;
3054 cost
= result_ready_cost (insn
);
3059 INSN_COST (insn
) = cost
;
3063 /* In this case estimate cost without caring how insn is used. */
3064 if (link
== 0 && used
== 0)
3067 /* A USE insn should never require the value used to be computed. This
3068 allows the computation of a function's result and parameter values to
3069 overlap the return and call. */
3070 recog_memoized (used
);
3071 if (INSN_CODE (used
) < 0)
3072 LINK_COST_FREE (link
) = 1;
3074 /* If some dependencies vary the cost, compute the adjustment. Most
3075 commonly, the adjustment is complete: either the cost is ignored
3076 (in the case of an output- or anti-dependence), or the cost is
3077 unchanged. These values are cached in the link as LINK_COST_FREE
3078 and LINK_COST_ZERO. */
3080 if (LINK_COST_FREE (link
))
3083 else if (!LINK_COST_ZERO (link
))
3087 ADJUST_COST (used
, link
, insn
, ncost
);
3090 LINK_COST_FREE (link
) = 1;
3094 LINK_COST_ZERO (link
) = 1;
3101 /* Compute the priority number for INSN. */
3110 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3113 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3115 if (INSN_DEPEND (insn
) == 0)
3116 this_priority
= insn_cost (insn
, 0, 0);
3118 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3123 if (RTX_INTEGRATED_P (link
))
3126 next
= XEXP (link
, 0);
3128 /* Critical path is meaningful in block boundaries only. */
3129 if (BLOCK_NUM (next
) != BLOCK_NUM (insn
))
3132 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3133 if (next_priority
> this_priority
)
3134 this_priority
= next_priority
;
3136 INSN_PRIORITY (insn
) = this_priority
;
3138 return this_priority
;
3142 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3143 them to the unused_*_list variables, so that they can be reused. */
3146 free_pending_lists ()
3148 if (current_nr_blocks
<= 1)
3150 free_INSN_LIST_list (&pending_read_insns
);
3151 free_INSN_LIST_list (&pending_write_insns
);
3152 free_EXPR_LIST_list (&pending_read_mems
);
3153 free_EXPR_LIST_list (&pending_write_mems
);
3157 /* Interblock scheduling. */
3160 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3162 free_INSN_LIST_list (&bb_pending_read_insns
[bb
]);
3163 free_INSN_LIST_list (&bb_pending_write_insns
[bb
]);
3164 free_EXPR_LIST_list (&bb_pending_read_mems
[bb
]);
3165 free_EXPR_LIST_list (&bb_pending_write_mems
[bb
]);
3170 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3171 The MEM is a memory reference contained within INSN, which we are saving
3172 so that we can do memory aliasing on it. */
3175 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3176 rtx
*insn_list
, *mem_list
, insn
, mem
;
3180 link
= alloc_INSN_LIST (insn
, *insn_list
);
3183 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3186 pending_lists_length
++;
3190 /* Make a dependency between every memory reference on the pending lists
3191 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3195 flush_pending_lists (insn
, only_write
)
3202 while (pending_read_insns
&& ! only_write
)
3204 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3206 link
= pending_read_insns
;
3207 pending_read_insns
= XEXP (pending_read_insns
, 1);
3208 free_INSN_LIST_node (link
);
3210 link
= pending_read_mems
;
3211 pending_read_mems
= XEXP (pending_read_mems
, 1);
3212 free_EXPR_LIST_node (link
);
3214 while (pending_write_insns
)
3216 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3218 link
= pending_write_insns
;
3219 pending_write_insns
= XEXP (pending_write_insns
, 1);
3220 free_INSN_LIST_node (link
);
3222 link
= pending_write_mems
;
3223 pending_write_mems
= XEXP (pending_write_mems
, 1);
3224 free_EXPR_LIST_node (link
);
3226 pending_lists_length
= 0;
3228 /* last_pending_memory_flush is now a list of insns. */
3229 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3230 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3232 free_INSN_LIST_list (&last_pending_memory_flush
);
3233 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3236 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3237 rtx, X, creating all dependencies generated by the write to the
3238 destination of X, and reads of everything mentioned. */
3241 sched_analyze_1 (x
, insn
)
3246 register rtx dest
= XEXP (x
, 0);
3247 enum rtx_code code
= GET_CODE (x
);
3252 if (GET_CODE (dest
) == PARALLEL
3253 && GET_MODE (dest
) == BLKmode
)
3256 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3257 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3258 if (GET_CODE (x
) == SET
)
3259 sched_analyze_2 (SET_SRC (x
), insn
);
3263 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3264 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3266 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3268 /* The second and third arguments are values read by this insn. */
3269 sched_analyze_2 (XEXP (dest
, 1), insn
);
3270 sched_analyze_2 (XEXP (dest
, 2), insn
);
3272 dest
= XEXP (dest
, 0);
3275 if (GET_CODE (dest
) == REG
)
3279 regno
= REGNO (dest
);
3281 /* A hard reg in a wide mode may really be multiple registers.
3282 If so, mark all of them just like the first. */
3283 if (regno
< FIRST_PSEUDO_REGISTER
)
3285 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3290 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3291 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3293 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3294 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3296 /* Clobbers need not be ordered with respect to one
3297 another, but sets must be ordered with respect to a
3301 free_INSN_LIST_list (®_last_uses
[regno
+ i
]);
3302 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3303 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3304 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3307 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
3309 /* Function calls clobber all call_used regs. */
3310 if (global_regs
[regno
+ i
]
3311 || (code
== SET
&& call_used_regs
[regno
+ i
]))
3312 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3313 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3320 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3321 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3323 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3324 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3328 free_INSN_LIST_list (®_last_uses
[regno
]);
3329 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3330 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3331 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3334 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
3336 /* Pseudos that are REG_EQUIV to something may be replaced
3337 by that during reloading. We need only add dependencies for
3338 the address in the REG_EQUIV note. */
3339 if (!reload_completed
3340 && reg_known_equiv_p
[regno
]
3341 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3342 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3344 /* Don't let it cross a call after scheduling if it doesn't
3345 already cross one. */
3347 if (REG_N_CALLS_CROSSED (regno
) == 0)
3348 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3349 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3352 else if (GET_CODE (dest
) == MEM
)
3354 /* Writing memory. */
3356 if (pending_lists_length
> 32)
3358 /* Flush all pending reads and writes to prevent the pending lists
3359 from getting any larger. Insn scheduling runs too slowly when
3360 these lists get long. The number 32 was chosen because it
3361 seems like a reasonable number. When compiling GCC with itself,
3362 this flush occurs 8 times for sparc, and 10 times for m88k using
3364 flush_pending_lists (insn
, 0);
3369 rtx pending
, pending_mem
;
3371 pending
= pending_read_insns
;
3372 pending_mem
= pending_read_mems
;
3375 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3376 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3378 pending
= XEXP (pending
, 1);
3379 pending_mem
= XEXP (pending_mem
, 1);
3382 pending
= pending_write_insns
;
3383 pending_mem
= pending_write_mems
;
3386 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3387 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3389 pending
= XEXP (pending
, 1);
3390 pending_mem
= XEXP (pending_mem
, 1);
3393 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3394 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3396 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3399 sched_analyze_2 (XEXP (dest
, 0), insn
);
3402 /* Analyze reads. */
3403 if (GET_CODE (x
) == SET
)
3404 sched_analyze_2 (SET_SRC (x
), insn
);
3407 /* Analyze the uses of memory and registers in rtx X in INSN. */
3410 sched_analyze_2 (x
, insn
)
3416 register enum rtx_code code
;
3417 register const char *fmt
;
3422 code
= GET_CODE (x
);
3431 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3432 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3433 this does not mean that this insn is using cc0. */
3441 /* User of CC0 depends on immediately preceding insn. */
3442 SCHED_GROUP_P (insn
) = 1;
3444 /* There may be a note before this insn now, but all notes will
3445 be removed before we actually try to schedule the insns, so
3446 it won't cause a problem later. We must avoid it here though. */
3447 prev
= prev_nonnote_insn (insn
);
3449 /* Make a copy of all dependencies on the immediately previous insn,
3450 and add to this insn. This is so that all the dependencies will
3451 apply to the group. Remove an explicit dependence on this insn
3452 as SCHED_GROUP_P now represents it. */
3454 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3455 remove_dependence (insn
, prev
);
3457 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3458 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3467 int regno
= REGNO (x
);
3468 if (regno
< FIRST_PSEUDO_REGISTER
)
3472 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3475 reg_last_uses
[regno
+ i
]
3476 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3478 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3479 add_dependence (insn
, XEXP (u
, 0), 0);
3481 /* ??? This should never happen. */
3482 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3483 add_dependence (insn
, XEXP (u
, 0), 0);
3485 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3486 /* Function calls clobber all call_used regs. */
3487 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3488 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3493 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
,
3494 reg_last_uses
[regno
]);
3496 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3497 add_dependence (insn
, XEXP (u
, 0), 0);
3499 /* ??? This should never happen. */
3500 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3501 add_dependence (insn
, XEXP (u
, 0), 0);
3503 /* Pseudos that are REG_EQUIV to something may be replaced
3504 by that during reloading. We need only add dependencies for
3505 the address in the REG_EQUIV note. */
3506 if (!reload_completed
3507 && reg_known_equiv_p
[regno
]
3508 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3509 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3511 /* If the register does not already cross any calls, then add this
3512 insn to the sched_before_next_call list so that it will still
3513 not cross calls after scheduling. */
3514 if (REG_N_CALLS_CROSSED (regno
) == 0)
3515 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3522 /* Reading memory. */
3524 rtx pending
, pending_mem
;
3526 pending
= pending_read_insns
;
3527 pending_mem
= pending_read_mems
;
3530 if (read_dependence (XEXP (pending_mem
, 0), x
))
3531 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3533 pending
= XEXP (pending
, 1);
3534 pending_mem
= XEXP (pending_mem
, 1);
3537 pending
= pending_write_insns
;
3538 pending_mem
= pending_write_mems
;
3541 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3543 add_dependence (insn
, XEXP (pending
, 0), 0);
3545 pending
= XEXP (pending
, 1);
3546 pending_mem
= XEXP (pending_mem
, 1);
3549 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3550 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3552 /* Always add these dependencies to pending_reads, since
3553 this insn may be followed by a write. */
3554 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3557 /* Take advantage of tail recursion here. */
3558 sched_analyze_2 (XEXP (x
, 0), insn
);
3562 /* Force pending stores to memory in case a trap handler needs them. */
3564 flush_pending_lists (insn
, 1);
3569 case UNSPEC_VOLATILE
:
3573 /* Traditional and volatile asm instructions must be considered to use
3574 and clobber all hard registers, all pseudo-registers and all of
3575 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3577 Consider for instance a volatile asm that changes the fpu rounding
3578 mode. An insn should not be moved across this even if it only uses
3579 pseudo-regs because it might give an incorrectly rounded result. */
3580 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3582 int max_reg
= max_reg_num ();
3583 for (i
= 0; i
< max_reg
; i
++)
3585 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3586 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3587 free_INSN_LIST_list (®_last_uses
[i
]);
3589 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3590 add_dependence (insn
, XEXP (u
, 0), 0);
3592 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3593 add_dependence (insn
, XEXP (u
, 0), 0);
3595 reg_pending_sets_all
= 1;
3597 flush_pending_lists (insn
, 0);
3600 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3601 We can not just fall through here since then we would be confused
3602 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3603 traditional asms unlike their normal usage. */
3605 if (code
== ASM_OPERANDS
)
3607 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3608 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3618 /* These both read and modify the result. We must handle them as writes
3619 to get proper dependencies for following instructions. We must handle
3620 them as reads to get proper dependencies from this to previous
3621 instructions. Thus we need to pass them to both sched_analyze_1
3622 and sched_analyze_2. We must call sched_analyze_2 first in order
3623 to get the proper antecedent for the read. */
3624 sched_analyze_2 (XEXP (x
, 0), insn
);
3625 sched_analyze_1 (x
, insn
);
3632 /* Other cases: walk the insn. */
3633 fmt
= GET_RTX_FORMAT (code
);
3634 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3637 sched_analyze_2 (XEXP (x
, i
), insn
);
3638 else if (fmt
[i
] == 'E')
3639 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3640 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3644 /* Analyze an INSN with pattern X to find all dependencies. */
3647 sched_analyze_insn (x
, insn
, loop_notes
)
3651 register RTX_CODE code
= GET_CODE (x
);
3653 int maxreg
= max_reg_num ();
3656 if (code
== SET
|| code
== CLOBBER
)
3657 sched_analyze_1 (x
, insn
);
3658 else if (code
== PARALLEL
)
3661 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3663 code
= GET_CODE (XVECEXP (x
, 0, i
));
3664 if (code
== SET
|| code
== CLOBBER
)
3665 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3667 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3671 sched_analyze_2 (x
, insn
);
3673 /* Mark registers CLOBBERED or used by called function. */
3674 if (GET_CODE (insn
) == CALL_INSN
)
3675 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3677 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3678 sched_analyze_1 (XEXP (link
, 0), insn
);
3680 sched_analyze_2 (XEXP (link
, 0), insn
);
3683 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3684 block, then we must be sure that no instructions are scheduled across it.
3685 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3686 become incorrect. */
3690 int max_reg
= max_reg_num ();
3691 int schedule_barrier_found
= 0;
3694 /* Update loop_notes with any notes from this insn. Also determine
3695 if any of the notes on the list correspond to instruction scheduling
3696 barriers (loop, eh & setjmp notes, but not range notes. */
3698 while (XEXP (link
, 1))
3700 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3701 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3702 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3703 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3704 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3705 schedule_barrier_found
= 1;
3707 link
= XEXP (link
, 1);
3709 XEXP (link
, 1) = REG_NOTES (insn
);
3710 REG_NOTES (insn
) = loop_notes
;
3712 /* Add dependencies if a scheduling barrier was found. */
3713 if (schedule_barrier_found
)
3715 for (i
= 0; i
< max_reg
; i
++)
3718 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3719 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3720 free_INSN_LIST_list (®_last_uses
[i
]);
3722 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3723 add_dependence (insn
, XEXP (u
, 0), 0);
3725 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3726 add_dependence (insn
, XEXP (u
, 0), 0);
3728 reg_pending_sets_all
= 1;
3730 flush_pending_lists (insn
, 0);
3735 /* Accumulate clobbers until the next set so that it will be output dependent
3736 on all of them. At the next set we can clear the clobber list, since
3737 subsequent sets will be output dependent on it. */
3738 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3740 free_INSN_LIST_list (®_last_sets
[i
]);
3741 free_INSN_LIST_list (®_last_clobbers
[i
]);
3743 = alloc_INSN_LIST (insn
, NULL_RTX
);
3745 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
3747 reg_last_clobbers
[i
]
3748 = alloc_INSN_LIST (insn
,
3749 reg_last_clobbers
[i
]);
3751 CLEAR_REG_SET (reg_pending_sets
);
3752 CLEAR_REG_SET (reg_pending_clobbers
);
3754 if (reg_pending_sets_all
)
3756 for (i
= 0; i
< maxreg
; i
++)
3758 free_INSN_LIST_list (®_last_sets
[i
]);
3759 free_INSN_LIST_list (®_last_clobbers
[i
]);
3760 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3763 reg_pending_sets_all
= 0;
3766 /* Handle function calls and function returns created by the epilogue
3768 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3773 /* When scheduling instructions, we make sure calls don't lose their
3774 accompanying USE insns by depending them one on another in order.
3776 Also, we must do the same thing for returns created by the epilogue
3777 threading code. Note this code works only in this special case,
3778 because other passes make no guarantee that they will never emit
3779 an instruction between a USE and a RETURN. There is such a guarantee
3780 for USE instructions immediately before a call. */
3782 prev_dep_insn
= insn
;
3783 dep_insn
= PREV_INSN (insn
);
3784 while (GET_CODE (dep_insn
) == INSN
3785 && GET_CODE (PATTERN (dep_insn
)) == USE
3786 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3788 SCHED_GROUP_P (prev_dep_insn
) = 1;
3790 /* Make a copy of all dependencies on dep_insn, and add to insn.
3791 This is so that all of the dependencies will apply to the
3794 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3795 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3797 prev_dep_insn
= dep_insn
;
3798 dep_insn
= PREV_INSN (dep_insn
);
3803 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3804 for every dependency. */
3807 sched_analyze (head
, tail
)
3814 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3816 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3818 /* Clear out the stale LOG_LINKS from flow. */
3819 free_INSN_LIST_list (&LOG_LINKS (insn
));
3821 /* Make each JUMP_INSN a scheduling barrier for memory
3823 if (GET_CODE (insn
) == JUMP_INSN
)
3824 last_pending_memory_flush
3825 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3826 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3829 else if (GET_CODE (insn
) == CALL_INSN
)
3834 CANT_MOVE (insn
) = 1;
3836 /* Clear out the stale LOG_LINKS from flow. */
3837 free_INSN_LIST_list (&LOG_LINKS (insn
));
3839 /* Any instruction using a hard register which may get clobbered
3840 by a call needs to be marked as dependent on this call.
3841 This prevents a use of a hard return reg from being moved
3842 past a void call (i.e. it does not explicitly set the hard
3845 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3846 all registers, not just hard registers, may be clobbered by this
3849 /* Insn, being a CALL_INSN, magically depends on
3850 `last_function_call' already. */
3852 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3853 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3855 int max_reg
= max_reg_num ();
3856 for (i
= 0; i
< max_reg
; i
++)
3858 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3859 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3860 free_INSN_LIST_list (®_last_uses
[i
]);
3862 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3863 add_dependence (insn
, XEXP (u
, 0), 0);
3865 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3866 add_dependence (insn
, XEXP (u
, 0), 0);
3868 reg_pending_sets_all
= 1;
3870 /* Add a pair of REG_SAVE_NOTEs which we will later
3871 convert back into a NOTE_INSN_SETJMP note. See
3872 reemit_notes for why we use a pair of NOTEs. */
3873 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3876 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3877 GEN_INT (NOTE_INSN_SETJMP
),
3882 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3883 if (call_used_regs
[i
] || global_regs
[i
])
3885 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3886 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3888 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3889 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3891 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3895 /* For each insn which shouldn't cross a call, add a dependence
3896 between that insn and this call insn. */
3897 x
= LOG_LINKS (sched_before_next_call
);
3900 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3903 free_INSN_LIST_list (&LOG_LINKS (sched_before_next_call
));
3905 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3908 /* In the absence of interprocedural alias analysis, we must flush
3909 all pending reads and writes, and start new dependencies starting
3910 from here. But only flush writes for constant calls (which may
3911 be passed a pointer to something we haven't written yet). */
3912 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3914 /* Depend this function call (actually, the user of this
3915 function call) on all hard register clobberage. */
3917 /* last_function_call is now a list of insns. */
3918 free_INSN_LIST_list(&last_function_call
);
3919 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3922 /* See comments on reemit_notes as to why we do this.
3923 ??? Actually, the reemit_notes just say what is done, not why. */
3925 else if (GET_CODE (insn
) == NOTE
3926 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3927 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3929 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
, NOTE_RANGE_INFO (insn
),
3931 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3932 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3935 else if (GET_CODE (insn
) == NOTE
3936 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3937 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3938 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3939 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3940 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3941 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3945 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3946 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
3947 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
3949 rtx_region
= GEN_INT (0);
3951 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3954 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3955 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3957 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3966 /* Macros and functions for keeping the priority queue sorted, and
3967 dealing with queueing and dequeueing of instructions. */
3969 #define SCHED_SORT(READY, N_READY) \
3970 do { if ((N_READY) == 2) \
3971 swap_sort (READY, N_READY); \
3972 else if ((N_READY) > 2) \
3973 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3976 /* Returns a positive value if x is preferred; returns a negative value if
3977 y is preferred. Should never return 0, since that will make the sort
3981 rank_for_schedule (x
, y
)
3985 rtx tmp
= *(rtx
*)y
;
3986 rtx tmp2
= *(rtx
*)x
;
3988 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
3989 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
3992 /* Prefer insn with higher priority. */
3993 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
3995 return priority_val
;
3997 /* Prefer an insn with smaller contribution to registers-pressure. */
3998 if (!reload_completed
&&
3999 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4000 return (weight_val
);
4002 /* Some comparison make sense in interblock scheduling only. */
4003 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4005 /* Prefer an inblock motion on an interblock motion. */
4006 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4008 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4011 /* Prefer a useful motion on a speculative one. */
4012 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4015 /* Prefer a more probable (speculative) insn. */
4016 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4021 /* Compare insns based on their relation to the last-scheduled-insn. */
4022 if (last_scheduled_insn
)
4024 /* Classify the instructions into three classes:
4025 1) Data dependent on last schedule insn.
4026 2) Anti/Output dependent on last scheduled insn.
4027 3) Independent of last scheduled insn, or has latency of one.
4028 Choose the insn from the highest numbered class if different. */
4029 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4030 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4032 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4037 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4038 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4040 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4045 if ((val
= tmp2_class
- tmp_class
))
4049 /* Prefer the insn which has more later insns that depend on it.
4050 This gives the scheduler more freedom when scheduling later
4051 instructions at the expense of added register pressure. */
4053 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4057 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4060 val
= depend_count2
- depend_count1
;
4064 /* If insns are equally good, sort by INSN_LUID (original insn order),
4065 so that we make the sort stable. This minimizes instruction movement,
4066 thus minimizing sched's effect on debugging and cross-jumping. */
4067 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4070 /* Resort the array A in which only element at index N may be out of order. */
4072 HAIFA_INLINE
static void
4077 rtx insn
= a
[n
- 1];
4080 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4088 static int max_priority
;
4090 /* Add INSN to the insn queue so that it can be executed at least
4091 N_CYCLES after the currently executing insn. Preserve insns
4092 chain for debugging purposes. */
4094 HAIFA_INLINE
static void
4095 queue_insn (insn
, n_cycles
)
4099 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4100 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4101 insn_queue
[next_q
] = link
;
4104 if (sched_verbose
>= 2)
4106 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4108 if (INSN_BB (insn
) != target_bb
)
4109 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4111 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4116 /* PREV is an insn that is ready to execute. Adjust its priority if that
4117 will help shorten or lengthen register lifetimes as appropriate. Also
4118 provide a hook for the target to tweek itself. */
4120 HAIFA_INLINE
static void
4121 adjust_priority (prev
)
4122 rtx prev ATTRIBUTE_UNUSED
;
4124 /* ??? There used to be code here to try and estimate how an insn
4125 affected register lifetimes, but it did it by looking at REG_DEAD
4126 notes, which we removed in schedule_region. Nor did it try to
4127 take into account register pressure or anything useful like that.
4129 Revisit when we have a machine model to work with and not before. */
4131 #ifdef ADJUST_PRIORITY
4132 ADJUST_PRIORITY (prev
);
4136 /* Clock at which the previous instruction was issued. */
4137 static int last_clock_var
;
4139 /* INSN is the "currently executing insn". Launch each insn which was
4140 waiting on INSN. READY is a vector of insns which are ready to fire.
4141 N_READY is the number of elements in READY. CLOCK is the current
4145 schedule_insn (insn
, ready
, n_ready
, clock
)
4154 unit
= insn_unit (insn
);
4156 if (sched_verbose
>= 2)
4158 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4160 insn_print_units (insn
);
4161 fprintf (dump
, "\n");
4164 if (sched_verbose
&& unit
== -1)
4165 visualize_no_unit (insn
);
4167 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4168 schedule_unit (unit
, insn
, clock
);
4170 if (INSN_DEPEND (insn
) == 0)
4173 /* This is used by the function adjust_priority above. */
4175 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4177 max_priority
= INSN_PRIORITY (insn
);
4179 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4181 rtx next
= XEXP (link
, 0);
4182 int cost
= insn_cost (insn
, link
, next
);
4184 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4186 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4188 int effective_cost
= INSN_TICK (next
) - clock
;
4190 /* For speculative insns, before inserting to ready/queue,
4191 check live, exception-free, and issue-delay. */
4192 if (INSN_BB (next
) != target_bb
4193 && (!IS_VALID (INSN_BB (next
))
4195 || (IS_SPECULATIVE_INSN (next
)
4196 && (insn_issue_delay (next
) > 3
4197 || !check_live (next
, INSN_BB (next
))
4198 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4201 if (sched_verbose
>= 2)
4203 fprintf (dump
, ";;\t\tdependences resolved: insn %d ",
4206 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4207 fprintf (dump
, "/b%d ", BLOCK_NUM (next
));
4209 if (effective_cost
< 1)
4210 fprintf (dump
, "into ready\n");
4212 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4215 /* Adjust the priority of NEXT and either put it on the ready
4216 list or queue it. */
4217 adjust_priority (next
);
4218 if (effective_cost
< 1)
4219 ready
[n_ready
++] = next
;
4221 queue_insn (next
, effective_cost
);
4225 /* Annotate the instruction with issue information -- TImode
4226 indicates that the instruction is expected not to be able
4227 to issue on the same cycle as the previous insn. A machine
4228 may use this information to decide how the instruction should
4230 if (reload_completed
&& issue_rate
> 1)
4232 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4233 last_clock_var
= clock
;
4239 /* Functions for handling of notes. */
4241 /* Delete notes beginning with INSN and put them in the chain
4242 of notes ended by NOTE_LIST.
4243 Returns the insn following the notes. */
4246 unlink_other_notes (insn
, tail
)
4249 rtx prev
= PREV_INSN (insn
);
4251 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4253 rtx next
= NEXT_INSN (insn
);
4254 /* Delete the note from its current position. */
4256 NEXT_INSN (prev
) = next
;
4258 PREV_INSN (next
) = prev
;
4260 /* See sched_analyze to see how these are handled. */
4261 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4262 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4263 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4264 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4265 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4266 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4267 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4269 /* Insert the note at the end of the notes list. */
4270 PREV_INSN (insn
) = note_list
;
4272 NEXT_INSN (note_list
) = insn
;
4281 /* Delete line notes beginning with INSN. Record line-number notes so
4282 they can be reused. Returns the insn following the notes. */
4285 unlink_line_notes (insn
, tail
)
4288 rtx prev
= PREV_INSN (insn
);
4290 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4292 rtx next
= NEXT_INSN (insn
);
4294 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4296 /* Delete the note from its current position. */
4298 NEXT_INSN (prev
) = next
;
4300 PREV_INSN (next
) = prev
;
4302 /* Record line-number notes so they can be reused. */
4303 LINE_NOTE (insn
) = insn
;
4313 /* Return the head and tail pointers of BB. */
4315 HAIFA_INLINE
static void
4316 get_block_head_tail (b
, headp
, tailp
)
4325 /* HEAD and TAIL delimit the basic block being scheduled. */
4326 head
= BLOCK_HEAD (b
);
4327 tail
= BLOCK_END (b
);
4329 /* Don't include any notes or labels at the beginning of the
4330 basic block, or notes at the ends of basic blocks. */
4331 while (head
!= tail
)
4333 if (GET_CODE (head
) == NOTE
)
4334 head
= NEXT_INSN (head
);
4335 else if (GET_CODE (tail
) == NOTE
)
4336 tail
= PREV_INSN (tail
);
4337 else if (GET_CODE (head
) == CODE_LABEL
)
4338 head
= NEXT_INSN (head
);
4347 HAIFA_INLINE
static void
4348 get_bb_head_tail (bb
, headp
, tailp
)
4353 get_block_head_tail (BB_TO_BLOCK (bb
), headp
, tailp
);
4356 /* Delete line notes from bb. Save them so they can be later restored
4357 (in restore_line_notes ()). */
4368 get_bb_head_tail (bb
, &head
, &tail
);
4371 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4374 next_tail
= NEXT_INSN (tail
);
4375 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4379 /* Farm out notes, and maybe save them in NOTE_LIST.
4380 This is needed to keep the debugger from
4381 getting completely deranged. */
4382 if (GET_CODE (insn
) == NOTE
)
4385 insn
= unlink_line_notes (insn
, next_tail
);
4391 if (insn
== next_tail
)
4397 /* Save line number notes for each insn in bb. */
4400 save_line_notes (bb
)
4406 /* We must use the true line number for the first insn in the block
4407 that was computed and saved at the start of this pass. We can't
4408 use the current line number, because scheduling of the previous
4409 block may have changed the current line number. */
4411 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4414 get_bb_head_tail (bb
, &head
, &tail
);
4415 next_tail
= NEXT_INSN (tail
);
4417 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4419 insn
= NEXT_INSN (insn
))
4420 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4423 LINE_NOTE (insn
) = line
;
4427 /* After bb was scheduled, insert line notes into the insns list. */
4430 restore_line_notes (bb
)
4433 rtx line
, note
, prev
, new;
4434 int added_notes
= 0;
4436 rtx head
, next_tail
, insn
;
4438 b
= BB_TO_BLOCK (bb
);
4440 head
= BLOCK_HEAD (b
);
4441 next_tail
= NEXT_INSN (BLOCK_END (b
));
4443 /* Determine the current line-number. We want to know the current
4444 line number of the first insn of the block here, in case it is
4445 different from the true line number that was saved earlier. If
4446 different, then we need a line number note before the first insn
4447 of this block. If it happens to be the same, then we don't want to
4448 emit another line number note here. */
4449 for (line
= head
; line
; line
= PREV_INSN (line
))
4450 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4453 /* Walk the insns keeping track of the current line-number and inserting
4454 the line-number notes as needed. */
4455 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4456 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4458 /* This used to emit line number notes before every non-deleted note.
4459 However, this confuses a debugger, because line notes not separated
4460 by real instructions all end up at the same address. I can find no
4461 use for line number notes before other notes, so none are emitted. */
4462 else if (GET_CODE (insn
) != NOTE
4463 && (note
= LINE_NOTE (insn
)) != 0
4466 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4467 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4470 prev
= PREV_INSN (insn
);
4471 if (LINE_NOTE (note
))
4473 /* Re-use the original line-number note. */
4474 LINE_NOTE (note
) = 0;
4475 PREV_INSN (note
) = prev
;
4476 NEXT_INSN (prev
) = note
;
4477 PREV_INSN (insn
) = note
;
4478 NEXT_INSN (note
) = insn
;
4483 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4484 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4485 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4488 if (sched_verbose
&& added_notes
)
4489 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4492 /* After scheduling the function, delete redundant line notes from the
4496 rm_redundant_line_notes ()
4499 rtx insn
= get_insns ();
4500 int active_insn
= 0;
4503 /* Walk the insns deleting redundant line-number notes. Many of these
4504 are already present. The remainder tend to occur at basic
4505 block boundaries. */
4506 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4507 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4509 /* If there are no active insns following, INSN is redundant. */
4510 if (active_insn
== 0)
4513 NOTE_SOURCE_FILE (insn
) = 0;
4514 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
4516 /* If the line number is unchanged, LINE is redundant. */
4518 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
4519 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
4522 NOTE_SOURCE_FILE (line
) = 0;
4523 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
4530 else if (!((GET_CODE (insn
) == NOTE
4531 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
4532 || (GET_CODE (insn
) == INSN
4533 && (GET_CODE (PATTERN (insn
)) == USE
4534 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
4537 if (sched_verbose
&& notes
)
4538 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
4541 /* Delete notes between head and tail and put them in the chain
4542 of notes ended by NOTE_LIST. */
4545 rm_other_notes (head
, tail
)
4553 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4556 next_tail
= NEXT_INSN (tail
);
4557 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4561 /* Farm out notes, and maybe save them in NOTE_LIST.
4562 This is needed to keep the debugger from
4563 getting completely deranged. */
4564 if (GET_CODE (insn
) == NOTE
)
4568 insn
= unlink_other_notes (insn
, next_tail
);
4574 if (insn
== next_tail
)
4580 /* Functions for computation of registers live/usage info. */
4582 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4585 find_insn_reg_weight (b
)
4588 rtx insn
, next_tail
, head
, tail
;
4590 get_block_head_tail (b
, &head
, &tail
);
4591 next_tail
= NEXT_INSN (tail
);
4593 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4598 /* Handle register life information. */
4599 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4602 /* Increment weight for each register born here. */
4604 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4605 && register_operand (SET_DEST (x
), VOIDmode
))
4607 else if (GET_CODE (x
) == PARALLEL
)
4610 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
4612 x
= XVECEXP (PATTERN (insn
), 0, j
);
4613 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4614 && register_operand (SET_DEST (x
), VOIDmode
))
4619 /* Decrement weight for each register that dies here. */
4620 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
4622 if (REG_NOTE_KIND (x
) == REG_DEAD
4623 || REG_NOTE_KIND (x
) == REG_UNUSED
)
4627 INSN_REG_WEIGHT (insn
) = reg_weight
;
4631 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4632 static int clock_var
;
4634 /* Move insns that became ready to fire from queue to ready list. */
4637 queue_to_ready (ready
, n_ready
)
4644 q_ptr
= NEXT_Q (q_ptr
);
4646 /* Add all pending insns that can be scheduled without stalls to the
4648 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
4651 insn
= XEXP (link
, 0);
4654 if (sched_verbose
>= 2)
4655 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4657 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4658 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4660 ready
[n_ready
++] = insn
;
4661 if (sched_verbose
>= 2)
4662 fprintf (dump
, "moving to ready without stalls\n");
4664 insn_queue
[q_ptr
] = 0;
4666 /* If there are no ready insns, stall until one is ready and add all
4667 of the pending insns at that point to the ready list. */
4670 register int stalls
;
4672 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
4674 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4676 for (; link
; link
= XEXP (link
, 1))
4678 insn
= XEXP (link
, 0);
4681 if (sched_verbose
>= 2)
4682 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4684 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4685 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4687 ready
[n_ready
++] = insn
;
4688 if (sched_verbose
>= 2)
4689 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
4691 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
4698 if (sched_verbose
&& stalls
)
4699 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
4700 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
4701 clock_var
+= stalls
;
4706 /* Print the ready list for debugging purposes. Callable from debugger. */
4709 debug_ready_list (ready
, n_ready
)
4715 for (i
= 0; i
< n_ready
; i
++)
4717 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
4718 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
4719 fprintf (dump
, "/b%d", BLOCK_NUM (ready
[i
]));
4721 fprintf (dump
, "\n");
4724 /* Print names of units on which insn can/should execute, for debugging. */
4727 insn_print_units (insn
)
4731 int unit
= insn_unit (insn
);
4734 fprintf (dump
, "none");
4736 fprintf (dump
, "%s", function_units
[unit
].name
);
4739 fprintf (dump
, "[");
4740 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
4743 fprintf (dump
, "%s", function_units
[i
].name
);
4745 fprintf (dump
, " ");
4747 fprintf (dump
, "]");
4751 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4752 of a basic block. If more lines are needed, table is splitted to two.
4753 n_visual_lines is the number of lines printed so far for a block.
4754 visual_tbl contains the block visualization info.
4755 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
4756 #define MAX_VISUAL_LINES 100
4761 rtx vis_no_unit
[10];
4763 /* Finds units that are in use in this fuction. Required only
4764 for visualization. */
4767 init_target_units ()
4772 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4774 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4777 unit
= insn_unit (insn
);
4780 target_units
|= ~unit
;
4782 target_units
|= (1 << unit
);
4786 /* Return the length of the visualization table. */
4789 get_visual_tbl_length ()
4795 /* Compute length of one field in line. */
4796 s
= (char *) alloca (INSN_LEN
+ 6);
4797 sprintf (s
, " %33s", "uname");
4800 /* Compute length of one line. */
4803 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
4804 if (function_units
[unit
].bitmask
& target_units
)
4805 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
4808 n
+= strlen ("\n") + 2;
4810 /* Compute length of visualization string. */
4811 return (MAX_VISUAL_LINES
* n
);
4814 /* Init block visualization debugging info. */
4817 init_block_visualization ()
4819 strcpy (visual_tbl
, "");
4827 safe_concat (buf
, cur
, str
)
4832 char *end
= buf
+ BUF_LEN
- 2; /* Leave room for null. */
4841 while (cur
< end
&& (c
= *str
++) != '\0')
4848 /* This recognizes rtx, I classified as expressions. These are always
4849 represent some action on values or results of other expression, that
4850 may be stored in objects representing values. */
4853 print_exp (buf
, x
, verbose
)
4861 const char *fun
= (char *)0;
4866 for (i
= 0; i
< 4; i
++)
4872 switch (GET_CODE (x
))
4875 op
[0] = XEXP (x
, 0);
4876 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
4877 && INTVAL (XEXP (x
, 1)) < 0)
4880 op
[1] = GEN_INT (-INTVAL (XEXP (x
, 1)));
4885 op
[1] = XEXP (x
, 1);
4889 op
[0] = XEXP (x
, 0);
4891 op
[1] = XEXP (x
, 1);
4895 op
[0] = XEXP (x
, 0);
4897 op
[1] = XEXP (x
, 1);
4901 op
[0] = XEXP (x
, 0);
4902 op
[1] = XEXP (x
, 1);
4906 op
[0] = XEXP (x
, 0);
4909 op
[0] = XEXP (x
, 0);
4911 op
[1] = XEXP (x
, 1);
4914 op
[0] = XEXP (x
, 0);
4916 op
[1] = XEXP (x
, 1);
4920 op
[0] = XEXP (x
, 0);
4921 op
[1] = XEXP (x
, 1);
4924 op
[0] = XEXP (x
, 0);
4926 op
[1] = XEXP (x
, 1);
4930 op
[0] = XEXP (x
, 0);
4931 op
[1] = XEXP (x
, 1);
4935 op
[0] = XEXP (x
, 0);
4936 op
[1] = XEXP (x
, 1);
4940 op
[0] = XEXP (x
, 0);
4941 op
[1] = XEXP (x
, 1);
4945 op
[0] = XEXP (x
, 0);
4946 op
[1] = XEXP (x
, 1);
4950 op
[0] = XEXP (x
, 0);
4951 op
[1] = XEXP (x
, 1);
4955 op
[0] = XEXP (x
, 0);
4958 op
[0] = XEXP (x
, 0);
4960 op
[1] = XEXP (x
, 1);
4963 op
[0] = XEXP (x
, 0);
4965 op
[1] = XEXP (x
, 1);
4968 op
[0] = XEXP (x
, 0);
4970 op
[1] = XEXP (x
, 1);
4973 op
[0] = XEXP (x
, 0);
4975 op
[1] = XEXP (x
, 1);
4978 op
[0] = XEXP (x
, 0);
4980 op
[1] = XEXP (x
, 1);
4983 op
[0] = XEXP (x
, 0);
4985 op
[1] = XEXP (x
, 1);
4988 op
[0] = XEXP (x
, 0);
4990 op
[1] = XEXP (x
, 1);
4993 op
[0] = XEXP (x
, 0);
4995 op
[1] = XEXP (x
, 1);
4999 op
[0] = XEXP (x
, 0);
5003 op
[0] = XEXP (x
, 0);
5007 op
[0] = XEXP (x
, 0);
5010 op
[0] = XEXP (x
, 0);
5012 op
[1] = XEXP (x
, 1);
5015 op
[0] = XEXP (x
, 0);
5017 op
[1] = XEXP (x
, 1);
5020 op
[0] = XEXP (x
, 0);
5022 op
[1] = XEXP (x
, 1);
5026 op
[0] = XEXP (x
, 0);
5027 op
[1] = XEXP (x
, 1);
5030 op
[0] = XEXP (x
, 0);
5032 op
[1] = XEXP (x
, 1);
5036 op
[0] = XEXP (x
, 0);
5037 op
[1] = XEXP (x
, 1);
5040 op
[0] = XEXP (x
, 0);
5042 op
[1] = XEXP (x
, 1);
5046 op
[0] = XEXP (x
, 0);
5047 op
[1] = XEXP (x
, 1);
5050 op
[0] = XEXP (x
, 0);
5052 op
[1] = XEXP (x
, 1);
5056 op
[0] = XEXP (x
, 0);
5057 op
[1] = XEXP (x
, 1);
5060 fun
= (verbose
) ? "sign_extract" : "sxt";
5061 op
[0] = XEXP (x
, 0);
5062 op
[1] = XEXP (x
, 1);
5063 op
[2] = XEXP (x
, 2);
5066 fun
= (verbose
) ? "zero_extract" : "zxt";
5067 op
[0] = XEXP (x
, 0);
5068 op
[1] = XEXP (x
, 1);
5069 op
[2] = XEXP (x
, 2);
5072 fun
= (verbose
) ? "sign_extend" : "sxn";
5073 op
[0] = XEXP (x
, 0);
5076 fun
= (verbose
) ? "zero_extend" : "zxn";
5077 op
[0] = XEXP (x
, 0);
5080 fun
= (verbose
) ? "float_extend" : "fxn";
5081 op
[0] = XEXP (x
, 0);
5084 fun
= (verbose
) ? "trunc" : "trn";
5085 op
[0] = XEXP (x
, 0);
5087 case FLOAT_TRUNCATE
:
5088 fun
= (verbose
) ? "float_trunc" : "ftr";
5089 op
[0] = XEXP (x
, 0);
5092 fun
= (verbose
) ? "float" : "flt";
5093 op
[0] = XEXP (x
, 0);
5095 case UNSIGNED_FLOAT
:
5096 fun
= (verbose
) ? "uns_float" : "ufl";
5097 op
[0] = XEXP (x
, 0);
5101 op
[0] = XEXP (x
, 0);
5104 fun
= (verbose
) ? "uns_fix" : "ufx";
5105 op
[0] = XEXP (x
, 0);
5109 op
[0] = XEXP (x
, 0);
5113 op
[0] = XEXP (x
, 0);
5116 op
[0] = XEXP (x
, 0);
5120 op
[0] = XEXP (x
, 0);
5125 op
[0] = XEXP (x
, 0);
5129 op
[1] = XEXP (x
, 1);
5134 op
[0] = XEXP (x
, 0);
5136 op
[1] = XEXP (x
, 1);
5138 op
[2] = XEXP (x
, 2);
5143 op
[0] = TRAP_CONDITION (x
);
5146 case UNSPEC_VOLATILE
:
5148 cur
= safe_concat (buf
, cur
, "unspec");
5149 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
5150 cur
= safe_concat (buf
, cur
, "/v");
5151 cur
= safe_concat (buf
, cur
, "[");
5153 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5155 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
5156 cur
= safe_concat (buf
, cur
, sep
);
5157 cur
= safe_concat (buf
, cur
, tmp
);
5160 cur
= safe_concat (buf
, cur
, "] ");
5161 sprintf (tmp
, "%d", XINT (x
, 1));
5162 cur
= safe_concat (buf
, cur
, tmp
);
5166 /* If (verbose) debug_rtx (x); */
5167 st
[0] = GET_RTX_NAME (GET_CODE (x
));
5171 /* Print this as a function? */
5174 cur
= safe_concat (buf
, cur
, fun
);
5175 cur
= safe_concat (buf
, cur
, "(");
5178 for (i
= 0; i
< 4; i
++)
5181 cur
= safe_concat (buf
, cur
, st
[i
]);
5186 cur
= safe_concat (buf
, cur
, ",");
5188 print_value (tmp
, op
[i
], verbose
);
5189 cur
= safe_concat (buf
, cur
, tmp
);
5194 cur
= safe_concat (buf
, cur
, ")");
5197 /* Prints rtxes, I customly classified as values. They're constants,
5198 registers, labels, symbols and memory accesses. */
5201 print_value (buf
, x
, verbose
)
5209 switch (GET_CODE (x
))
5212 sprintf (t
, HOST_WIDE_INT_PRINT_HEX
, INTVAL (x
));
5213 cur
= safe_concat (buf
, cur
, t
);
5216 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
5217 cur
= safe_concat (buf
, cur
, t
);
5220 cur
= safe_concat (buf
, cur
, "\"");
5221 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5222 cur
= safe_concat (buf
, cur
, "\"");
5225 cur
= safe_concat (buf
, cur
, "`");
5226 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5227 cur
= safe_concat (buf
, cur
, "'");
5230 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
5231 cur
= safe_concat (buf
, cur
, t
);
5234 print_value (t
, XEXP (x
, 0), verbose
);
5235 cur
= safe_concat (buf
, cur
, "const(");
5236 cur
= safe_concat (buf
, cur
, t
);
5237 cur
= safe_concat (buf
, cur
, ")");
5240 print_value (t
, XEXP (x
, 0), verbose
);
5241 cur
= safe_concat (buf
, cur
, "high(");
5242 cur
= safe_concat (buf
, cur
, t
);
5243 cur
= safe_concat (buf
, cur
, ")");
5246 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
5248 int c
= reg_names
[ REGNO (x
) ][0];
5249 if (c
>= '0' && c
<= '9')
5250 cur
= safe_concat (buf
, cur
, "%");
5252 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
5256 sprintf (t
, "r%d", REGNO (x
));
5257 cur
= safe_concat (buf
, cur
, t
);
5261 print_value (t
, SUBREG_REG (x
), verbose
);
5262 cur
= safe_concat (buf
, cur
, t
);
5263 sprintf (t
, "#%d", SUBREG_WORD (x
));
5264 cur
= safe_concat (buf
, cur
, t
);
5267 cur
= safe_concat (buf
, cur
, "scratch");
5270 cur
= safe_concat (buf
, cur
, "cc0");
5273 cur
= safe_concat (buf
, cur
, "pc");
5276 print_value (t
, XEXP (x
, 0), verbose
);
5277 cur
= safe_concat (buf
, cur
, "[");
5278 cur
= safe_concat (buf
, cur
, t
);
5279 cur
= safe_concat (buf
, cur
, "]");
5282 print_exp (t
, x
, verbose
);
5283 cur
= safe_concat (buf
, cur
, t
);
5288 /* The next step in insn detalization, its pattern recognition. */
5291 print_pattern (buf
, x
, verbose
)
5296 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
5298 switch (GET_CODE (x
))
5301 print_value (t1
, SET_DEST (x
), verbose
);
5302 print_value (t2
, SET_SRC (x
), verbose
);
5303 sprintf (buf
, "%s=%s", t1
, t2
);
5306 sprintf (buf
, "return");
5309 print_exp (buf
, x
, verbose
);
5312 print_value (t1
, XEXP (x
, 0), verbose
);
5313 sprintf (buf
, "clobber %s", t1
);
5316 print_value (t1
, XEXP (x
, 0), verbose
);
5317 sprintf (buf
, "use %s", t1
);
5324 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5326 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5327 sprintf (t3
, "%s%s;", t1
, t2
);
5330 sprintf (buf
, "%s}", t1
);
5337 sprintf (t1
, "%%{");
5338 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5340 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
5341 sprintf (t3
, "%s%s;", t1
, t2
);
5344 sprintf (buf
, "%s%%}", t1
);
5348 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
5353 print_value (buf
, XEXP (x
, 0), verbose
);
5356 print_value (t1
, TRAP_CONDITION (x
), verbose
);
5357 sprintf (buf
, "trap_if %s", t1
);
5363 sprintf (t1
, "unspec{");
5364 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5366 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5367 sprintf (t3
, "%s%s;", t1
, t2
);
5370 sprintf (buf
, "%s}", t1
);
5373 case UNSPEC_VOLATILE
:
5377 sprintf (t1
, "unspec/v{");
5378 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5380 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5381 sprintf (t3
, "%s%s;", t1
, t2
);
5384 sprintf (buf
, "%s}", t1
);
5388 print_value (buf
, x
, verbose
);
5390 } /* print_pattern */
5392 /* This is the main function in rtl visualization mechanism. It
5393 accepts an rtx and tries to recognize it as an insn, then prints it
5394 properly in human readable form, resembling assembler mnemonics.
5395 For every insn it prints its UID and BB the insn belongs too.
5396 (Probably the last "option" should be extended somehow, since it
5397 depends now on sched.c inner variables ...) */
5400 print_insn (buf
, x
, verbose
)
5408 switch (GET_CODE (x
))
5411 print_pattern (t
, PATTERN (x
), verbose
);
5413 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
5416 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5419 print_pattern (t
, PATTERN (x
), verbose
);
5421 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
5424 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5428 if (GET_CODE (x
) == PARALLEL
)
5430 x
= XVECEXP (x
, 0, 0);
5431 print_pattern (t
, x
, verbose
);
5434 strcpy (t
, "call <...>");
5436 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
5437 INSN_UID (insn
), t
);
5439 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
5442 sprintf (buf
, "L%d:", INSN_UID (x
));
5445 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
5448 if (NOTE_LINE_NUMBER (x
) > 0)
5449 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
5450 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
5452 sprintf (buf
, "%4d %s", INSN_UID (x
),
5453 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
5458 sprintf (buf
, "Not an INSN at all\n");
5462 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
5466 /* Print visualization debugging info. */
5469 print_block_visualization (b
, s
)
5476 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
5478 /* Print names of units. */
5479 fprintf (dump
, ";; %-8s", "clock");
5480 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5481 if (function_units
[unit
].bitmask
& target_units
)
5482 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5483 fprintf (dump
, " %-33s", function_units
[unit
].name
);
5484 fprintf (dump
, " %-8s\n", "no-unit");
5486 fprintf (dump
, ";; %-8s", "=====");
5487 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5488 if (function_units
[unit
].bitmask
& target_units
)
5489 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5490 fprintf (dump
, " %-33s", "==============================");
5491 fprintf (dump
, " %-8s\n", "=======");
5493 /* Print insns in each cycle. */
5494 fprintf (dump
, "%s\n", visual_tbl
);
5497 /* Print insns in the 'no_unit' column of visualization. */
5500 visualize_no_unit (insn
)
5503 vis_no_unit
[n_vis_no_unit
] = insn
;
5507 /* Print insns scheduled in clock, for visualization. */
5510 visualize_scheduled_insns (b
, clock
)
5515 /* If no more room, split table into two. */
5516 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5518 print_block_visualization (b
, "(incomplete)");
5519 init_block_visualization ();
5524 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
5525 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5526 if (function_units
[unit
].bitmask
& target_units
)
5527 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5529 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
5530 rtx insn
= unit_last_insn
[instance
];
5532 /* Print insns that still keep the unit busy. */
5534 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
5537 print_insn (str
, insn
, 0);
5538 str
[INSN_LEN
] = '\0';
5539 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
5542 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
5545 /* Print insns that are not assigned to any unit. */
5546 for (i
= 0; i
< n_vis_no_unit
; i
++)
5547 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
5548 INSN_UID (vis_no_unit
[i
]));
5551 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5554 /* Print stalled cycles. */
5557 visualize_stall_cycles (b
, stalls
)
5562 /* If no more room, split table into two. */
5563 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5565 print_block_visualization (b
, "(incomplete)");
5566 init_block_visualization ();
5571 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
5572 for (i
= 0; i
< stalls
; i
++)
5573 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
5574 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5577 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5580 move_insn1 (insn
, last
)
5583 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
5584 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
5586 NEXT_INSN (insn
) = NEXT_INSN (last
);
5587 PREV_INSN (NEXT_INSN (last
)) = insn
;
5589 NEXT_INSN (last
) = insn
;
5590 PREV_INSN (insn
) = last
;
5595 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5596 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5597 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5598 saved value for NOTE_BLOCK_NUMBER which is useful for
5599 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5600 output by the instruction scheduler. Return the new value of LAST. */
5603 reemit_notes (insn
, last
)
5610 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
5612 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5614 int note_type
= INTVAL (XEXP (note
, 0));
5615 if (note_type
== NOTE_INSN_SETJMP
)
5617 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
5618 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
5619 remove_note (insn
, note
);
5620 note
= XEXP (note
, 1);
5622 else if (note_type
== NOTE_INSN_RANGE_START
5623 || note_type
== NOTE_INSN_RANGE_END
)
5625 last
= emit_note_before (note_type
, last
);
5626 remove_note (insn
, note
);
5627 note
= XEXP (note
, 1);
5628 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
5632 last
= emit_note_before (note_type
, last
);
5633 remove_note (insn
, note
);
5634 note
= XEXP (note
, 1);
5635 if (note_type
== NOTE_INSN_EH_REGION_BEG
5636 || note_type
== NOTE_INSN_EH_REGION_END
)
5637 NOTE_EH_HANDLER (last
) = INTVAL (XEXP (note
, 0));
5639 remove_note (insn
, note
);
5645 /* Move INSN, and all insns which should be issued before it,
5646 due to SCHED_GROUP_P flag. Reemit notes if needed.
5648 Return the last insn emitted by the scheduler, which is the
5649 return value from the first call to reemit_notes. */
5652 move_insn (insn
, last
)
5657 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5658 insns with SCHED_GROUP_P set first. */
5659 while (SCHED_GROUP_P (insn
))
5661 rtx prev
= PREV_INSN (insn
);
5663 /* Move a SCHED_GROUP_P insn. */
5664 move_insn1 (insn
, last
);
5665 /* If this is the first call to reemit_notes, then record
5666 its return value. */
5667 if (retval
== NULL_RTX
)
5668 retval
= reemit_notes (insn
, insn
);
5670 reemit_notes (insn
, insn
);
5674 /* Now move the first non SCHED_GROUP_P insn. */
5675 move_insn1 (insn
, last
);
5677 /* If this is the first call to reemit_notes, then record
5678 its return value. */
5679 if (retval
== NULL_RTX
)
5680 retval
= reemit_notes (insn
, insn
);
5682 reemit_notes (insn
, insn
);
5687 /* Return an insn which represents a SCHED_GROUP, which is
5688 the last insn in the group. */
5699 insn
= next_nonnote_insn (insn
);
5701 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
5706 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5707 possibly bringing insns from subsequent blocks in the same region.
5708 Return number of insns scheduled. */
5711 schedule_block (bb
, rgn_n_insns
)
5715 /* Local variables. */
5721 /* Flow block of this bb. */
5722 int b
= BB_TO_BLOCK (bb
);
5724 /* target_n_insns == number of insns in b before scheduling starts.
5725 sched_target_n_insns == how many of b's insns were scheduled.
5726 sched_n_insns == how many insns were scheduled in b. */
5727 int target_n_insns
= 0;
5728 int sched_target_n_insns
= 0;
5729 int sched_n_insns
= 0;
5731 #define NEED_NOTHING 0
5736 /* Head/tail info for this block. */
5743 /* We used to have code to avoid getting parameters moved from hard
5744 argument registers into pseudos.
5746 However, it was removed when it proved to be of marginal benefit
5747 and caused problems because schedule_block and compute_forward_dependences
5748 had different notions of what the "head" insn was. */
5749 get_bb_head_tail (bb
, &head
, &tail
);
5751 /* Interblock scheduling could have moved the original head insn from this
5752 block into a proceeding block. This may also cause schedule_block and
5753 compute_forward_dependences to have different notions of what the
5756 If the interblock movement happened to make this block start with
5757 some notes (LOOP, EH or SETJMP) before the first real insn, then
5758 HEAD will have various special notes attached to it which must be
5759 removed so that we don't end up with extra copies of the notes. */
5760 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
5764 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
5765 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5766 remove_note (head
, note
);
5769 next_tail
= NEXT_INSN (tail
);
5770 prev_head
= PREV_INSN (head
);
5772 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5773 to schedule this block. */
5775 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5776 return (sched_n_insns
);
5781 fprintf (dump
, ";; ======================================================\n");
5783 ";; -- basic block %d from %d to %d -- %s reload\n",
5784 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
5785 (reload_completed
? "after" : "before"));
5786 fprintf (dump
, ";; ======================================================\n");
5787 fprintf (dump
, "\n");
5789 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
5790 init_block_visualization ();
5793 /* Remove remaining note insns from the block, save them in
5794 note_list. These notes are restored at the end of
5795 schedule_block (). */
5797 rm_other_notes (head
, tail
);
5801 /* Prepare current target block info. */
5802 if (current_nr_blocks
> 1)
5804 candidate_table
= (candidate
*) xmalloc (current_nr_blocks
5805 * sizeof (candidate
));
5808 /* ??? It is not clear why bblst_size is computed this way. The original
5809 number was clearly too small as it resulted in compiler failures.
5810 Multiplying by the original number by 2 (to account for update_bbs
5811 members) seems to be a reasonable solution. */
5812 /* ??? Or perhaps there is a bug somewhere else in this file? */
5813 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
5814 bblst_table
= (int *) xmalloc (bblst_size
* sizeof (int));
5816 bitlst_table_last
= 0;
5817 bitlst_table_size
= rgn_nr_edges
;
5818 bitlst_table
= (int *) xmalloc (rgn_nr_edges
* sizeof (int));
5820 compute_trg_info (bb
);
5825 /* Allocate the ready list. */
5826 ready
= (rtx
*) xmalloc ((rgn_n_insns
+ 1) * sizeof (rtx
));
5828 /* Print debugging information. */
5829 if (sched_verbose
>= 5)
5830 debug_dependencies ();
5833 /* Initialize ready list with all 'ready' insns in target block.
5834 Count number of insns in the target block being scheduled. */
5836 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5840 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5842 next
= NEXT_INSN (insn
);
5844 if (INSN_DEP_COUNT (insn
) == 0
5845 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5846 ready
[n_ready
++] = insn
;
5847 if (!(SCHED_GROUP_P (insn
)))
5851 /* Add to ready list all 'ready' insns in valid source blocks.
5852 For speculative insns, check-live, exception-free, and
5854 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
5855 if (IS_VALID (bb_src
))
5861 get_bb_head_tail (bb_src
, &head
, &tail
);
5862 src_next_tail
= NEXT_INSN (tail
);
5866 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5869 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
5871 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5874 if (!CANT_MOVE (insn
)
5875 && (!IS_SPECULATIVE_INSN (insn
)
5876 || (insn_issue_delay (insn
) <= 3
5877 && check_live (insn
, bb_src
)
5878 && is_exception_free (insn
, bb_src
, target_bb
))))
5883 /* Note that we havn't squirrled away the notes for
5884 blocks other than the current. So if this is a
5885 speculative insn, NEXT might otherwise be a note. */
5886 next
= next_nonnote_insn (insn
);
5887 if (INSN_DEP_COUNT (insn
) == 0
5888 && (SCHED_GROUP_P (next
) == 0
5889 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5890 ready
[n_ready
++] = insn
;
5895 #ifdef MD_SCHED_INIT
5896 MD_SCHED_INIT (dump
, sched_verbose
);
5899 /* No insns scheduled in this block yet. */
5900 last_scheduled_insn
= 0;
5902 /* Q_SIZE is the total number of insns in the queue. */
5906 bzero ((char *) insn_queue
, sizeof (insn_queue
));
5908 /* Start just before the beginning of time. */
5911 /* We start inserting insns after PREV_HEAD. */
5914 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
5915 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
5916 ? NEED_HEAD
: NEED_NOTHING
);
5917 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
5918 new_needs
|= NEED_TAIL
;
5920 /* Loop until all the insns in BB are scheduled. */
5921 while (sched_target_n_insns
< target_n_insns
)
5925 /* Add to the ready list all pending insns that can be issued now.
5926 If there are no ready insns, increment clock until one
5927 is ready and add all pending insns at that point to the ready
5929 n_ready
= queue_to_ready (ready
, n_ready
);
5934 if (sched_verbose
>= 2)
5936 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
5937 debug_ready_list (ready
, n_ready
);
5940 /* Sort the ready list based on priority. */
5941 SCHED_SORT (ready
, n_ready
);
5943 /* Allow the target to reorder the list, typically for
5944 better instruction bundling. */
5945 #ifdef MD_SCHED_REORDER
5946 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
, clock_var
,
5949 can_issue_more
= issue_rate
;
5954 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
5955 debug_ready_list (ready
, n_ready
);
5958 /* Issue insns from ready list. */
5959 while (n_ready
!= 0 && can_issue_more
)
5961 /* Select and remove the insn from the ready list. */
5962 rtx insn
= ready
[--n_ready
];
5963 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
5967 queue_insn (insn
, cost
);
5971 /* An interblock motion? */
5972 if (INSN_BB (insn
) != target_bb
)
5977 if (IS_SPECULATIVE_INSN (insn
))
5979 if (!check_live (insn
, INSN_BB (insn
)))
5981 update_live (insn
, INSN_BB (insn
));
5983 /* For speculative load, mark insns fed by it. */
5984 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
5985 set_spec_fed (insn
);
5991 /* Find the beginning of the scheduling group. */
5992 /* ??? Ought to update basic block here, but later bits of
5993 schedule_block assumes the original insn block is
5997 while (SCHED_GROUP_P (temp
))
5998 temp
= PREV_INSN (temp
);
6000 /* Update source block boundaries. */
6001 b1
= BLOCK_FOR_INSN (temp
);
6002 if (temp
== b1
->head
&& insn
== b1
->end
)
6004 /* We moved all the insns in the basic block.
6005 Emit a note after the last insn and update the
6006 begin/end boundaries to point to the note. */
6007 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
6011 else if (insn
== b1
->end
)
6013 /* We took insns from the end of the basic block,
6014 so update the end of block boundary so that it
6015 points to the first insn we did not move. */
6016 b1
->end
= PREV_INSN (temp
);
6018 else if (temp
== b1
->head
)
6020 /* We took insns from the start of the basic block,
6021 so update the start of block boundary so that
6022 it points to the first insn we did not move. */
6023 b1
->head
= NEXT_INSN (insn
);
6028 /* In block motion. */
6029 sched_target_n_insns
++;
6032 last_scheduled_insn
= insn
;
6033 last
= move_insn (insn
, last
);
6036 #ifdef MD_SCHED_VARIABLE_ISSUE
6037 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
,
6043 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6045 /* Close this block after scheduling its jump. */
6046 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6052 visualize_scheduled_insns (b
, clock_var
);
6058 fprintf (dump
, ";;\tReady list (final): ");
6059 debug_ready_list (ready
, n_ready
);
6060 print_block_visualization (b
, "");
6063 /* Sanity check -- queue must be empty now. Meaningless if region has
6065 if (current_nr_blocks
> 1)
6066 if (!flag_schedule_interblock
&& q_size
!= 0)
6069 /* Update head/tail boundaries. */
6070 head
= NEXT_INSN (prev_head
);
6073 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6074 previously found among the insns. Insert them at the beginning
6078 rtx note_head
= note_list
;
6080 while (PREV_INSN (note_head
))
6082 note_head
= PREV_INSN (note_head
);
6085 PREV_INSN (note_head
) = PREV_INSN (head
);
6086 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6087 PREV_INSN (head
) = note_list
;
6088 NEXT_INSN (note_list
) = head
;
6092 /* Update target block boundaries. */
6093 if (new_needs
& NEED_HEAD
)
6094 BLOCK_HEAD (b
) = head
;
6096 if (new_needs
& NEED_TAIL
)
6097 BLOCK_END (b
) = tail
;
6102 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6103 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
6104 fprintf (dump
, ";; new basic block end = %d\n\n",
6105 INSN_UID (BLOCK_END (b
)));
6109 if (current_nr_blocks
> 1)
6111 free (candidate_table
);
6113 free (bitlst_table
);
6117 return (sched_n_insns
);
6118 } /* schedule_block () */
6121 /* Print the bit-set of registers, S, callable from debugger. */
6124 debug_reg_vector (s
)
6129 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
6131 fprintf (dump
, " %d", regno
);
6134 fprintf (dump
, "\n");
6137 /* Use the backward dependences from LOG_LINKS to build
6138 forward dependences in INSN_DEPEND. */
6141 compute_block_forward_dependences (bb
)
6147 enum reg_note dep_type
;
6149 get_bb_head_tail (bb
, &head
, &tail
);
6150 next_tail
= NEXT_INSN (tail
);
6151 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6153 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6156 insn
= group_leader (insn
);
6158 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
6160 rtx x
= group_leader (XEXP (link
, 0));
6163 if (x
!= XEXP (link
, 0))
6166 #ifdef ENABLE_CHECKING
6167 /* If add_dependence is working properly there should never
6168 be notes, deleted insns or duplicates in the backward
6169 links. Thus we need not check for them here.
6171 However, if we have enabled checking we might as well go
6172 ahead and verify that add_dependence worked properly. */
6173 if (GET_CODE (x
) == NOTE
6174 || INSN_DELETED_P (x
)
6175 || find_insn_list (insn
, INSN_DEPEND (x
)))
6179 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
6181 dep_type
= REG_NOTE_KIND (link
);
6182 PUT_REG_NOTE_KIND (new_link
, dep_type
);
6184 INSN_DEPEND (x
) = new_link
;
6185 INSN_DEP_COUNT (insn
) += 1;
6190 /* Initialize variables for region data dependence analysis.
6191 n_bbs is the number of region blocks. */
6193 __inline
static void
6194 init_rgn_data_dependences (n_bbs
)
6199 /* Variables for which one copy exists for each block. */
6200 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
6201 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
6202 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
6203 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
6204 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (int));
6205 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
6206 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
6207 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
6209 /* Create an insn here so that we can hang dependencies off of it later. */
6210 for (bb
= 0; bb
< n_bbs
; bb
++)
6212 bb_sched_before_next_call
[bb
] =
6213 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6214 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6215 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
6219 /* Add dependences so that branches are scheduled to run last in their
6223 add_branch_dependences (head
, tail
)
6229 /* For all branches, calls, uses, and cc0 setters, force them to remain
6230 in order at the end of the block by adding dependencies and giving
6231 the last a high priority. There may be notes present, and prev_head
6234 Branches must obviously remain at the end. Calls should remain at the
6235 end since moving them results in worse register allocation. Uses remain
6236 at the end to ensure proper register allocation. cc0 setters remaim
6237 at the end because they can't be moved away from their cc0 user. */
6240 while (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
6241 || (GET_CODE (insn
) == INSN
6242 && (GET_CODE (PATTERN (insn
)) == USE
6244 || sets_cc0_p (PATTERN (insn
))
6247 || GET_CODE (insn
) == NOTE
)
6249 if (GET_CODE (insn
) != NOTE
)
6252 && !find_insn_list (insn
, LOG_LINKS (last
)))
6254 add_dependence (last
, insn
, REG_DEP_ANTI
);
6255 INSN_REF_COUNT (insn
)++;
6258 CANT_MOVE (insn
) = 1;
6261 /* Skip over insns that are part of a group.
6262 Make each insn explicitly depend on the previous insn.
6263 This ensures that only the group header will ever enter
6264 the ready queue (and, when scheduled, will automatically
6265 schedule the SCHED_GROUP_P block). */
6266 while (SCHED_GROUP_P (insn
))
6268 rtx temp
= prev_nonnote_insn (insn
);
6269 add_dependence (insn
, temp
, REG_DEP_ANTI
);
6274 /* Don't overrun the bounds of the basic block. */
6278 insn
= PREV_INSN (insn
);
6281 /* Make sure these insns are scheduled last in their block. */
6284 while (insn
!= head
)
6286 insn
= prev_nonnote_insn (insn
);
6288 if (INSN_REF_COUNT (insn
) != 0)
6291 add_dependence (last
, insn
, REG_DEP_ANTI
);
6292 INSN_REF_COUNT (insn
) = 1;
6294 /* Skip over insns that are part of a group. */
6295 while (SCHED_GROUP_P (insn
))
6296 insn
= prev_nonnote_insn (insn
);
6300 /* Compute backward dependences inside bb. In a multiple blocks region:
6301 (1) a bb is analyzed after its predecessors, and (2) the lists in
6302 effect at the end of bb (after analyzing for bb) are inherited by
6305 Specifically for reg-reg data dependences, the block insns are
6306 scanned by sched_analyze () top-to-bottom. Two lists are
6307 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6308 and reg_last_uses[] for register USEs.
6310 When analysis is completed for bb, we update for its successors:
6311 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6312 ; - USES[succ] = Union (USES [succ], DEFS [bb])
6314 The mechanism for computing mem-mem data dependence is very
6315 similar, and the result is interblock dependences in the region. */
6318 compute_block_backward_dependences (bb
)
6324 int max_reg
= max_reg_num ();
6326 b
= BB_TO_BLOCK (bb
);
6328 if (current_nr_blocks
== 1)
6330 reg_last_uses
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6331 reg_last_sets
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6332 reg_last_clobbers
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6334 pending_read_insns
= 0;
6335 pending_read_mems
= 0;
6336 pending_write_insns
= 0;
6337 pending_write_mems
= 0;
6338 pending_lists_length
= 0;
6339 last_function_call
= 0;
6340 last_pending_memory_flush
= 0;
6341 sched_before_next_call
6342 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6343 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6344 LOG_LINKS (sched_before_next_call
) = 0;
6348 reg_last_uses
= bb_reg_last_uses
[bb
];
6349 reg_last_sets
= bb_reg_last_sets
[bb
];
6350 reg_last_clobbers
= bb_reg_last_clobbers
[bb
];
6352 pending_read_insns
= bb_pending_read_insns
[bb
];
6353 pending_read_mems
= bb_pending_read_mems
[bb
];
6354 pending_write_insns
= bb_pending_write_insns
[bb
];
6355 pending_write_mems
= bb_pending_write_mems
[bb
];
6356 pending_lists_length
= bb_pending_lists_length
[bb
];
6357 last_function_call
= bb_last_function_call
[bb
];
6358 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
6360 sched_before_next_call
= bb_sched_before_next_call
[bb
];
6363 /* Do the analysis for this block. */
6364 get_bb_head_tail (bb
, &head
, &tail
);
6365 sched_analyze (head
, tail
);
6366 add_branch_dependences (head
, tail
);
6368 if (current_nr_blocks
> 1)
6371 int b_succ
, bb_succ
;
6373 rtx link_insn
, link_mem
;
6376 /* These lists should point to the right place, for correct
6378 bb_pending_read_insns
[bb
] = pending_read_insns
;
6379 bb_pending_read_mems
[bb
] = pending_read_mems
;
6380 bb_pending_write_insns
[bb
] = pending_write_insns
;
6381 bb_pending_write_mems
[bb
] = pending_write_mems
;
6383 /* bb's structures are inherited by it's successors. */
6384 first_edge
= e
= OUT_EDGES (b
);
6388 b_succ
= TO_BLOCK (e
);
6389 bb_succ
= BLOCK_TO_BB (b_succ
);
6391 /* Only bbs "below" bb, in the same region, are interesting. */
6392 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
6399 for (reg
= 0; reg
< max_reg
; reg
++)
6402 /* reg-last-uses lists are inherited by bb_succ. */
6403 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
6405 if (find_insn_list (XEXP (u
, 0),
6406 (bb_reg_last_uses
[bb_succ
])[reg
]))
6409 (bb_reg_last_uses
[bb_succ
])[reg
]
6410 = alloc_INSN_LIST (XEXP (u
, 0),
6411 (bb_reg_last_uses
[bb_succ
])[reg
]);
6414 /* reg-last-defs lists are inherited by bb_succ. */
6415 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
6417 if (find_insn_list (XEXP (u
, 0),
6418 (bb_reg_last_sets
[bb_succ
])[reg
]))
6421 (bb_reg_last_sets
[bb_succ
])[reg
]
6422 = alloc_INSN_LIST (XEXP (u
, 0),
6423 (bb_reg_last_sets
[bb_succ
])[reg
]);
6426 for (u
= reg_last_clobbers
[reg
]; u
; u
= XEXP (u
, 1))
6428 if (find_insn_list (XEXP (u
, 0),
6429 (bb_reg_last_clobbers
[bb_succ
])[reg
]))
6432 (bb_reg_last_clobbers
[bb_succ
])[reg
]
6433 = alloc_INSN_LIST (XEXP (u
, 0),
6434 (bb_reg_last_clobbers
[bb_succ
])[reg
]);
6438 /* Mem read/write lists are inherited by bb_succ. */
6439 link_insn
= pending_read_insns
;
6440 link_mem
= pending_read_mems
;
6443 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6445 bb_pending_read_insns
[bb_succ
],
6446 bb_pending_read_mems
[bb_succ
])))
6447 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
6448 &bb_pending_read_mems
[bb_succ
],
6449 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6450 link_insn
= XEXP (link_insn
, 1);
6451 link_mem
= XEXP (link_mem
, 1);
6454 link_insn
= pending_write_insns
;
6455 link_mem
= pending_write_mems
;
6458 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6460 bb_pending_write_insns
[bb_succ
],
6461 bb_pending_write_mems
[bb_succ
])))
6462 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
6463 &bb_pending_write_mems
[bb_succ
],
6464 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6466 link_insn
= XEXP (link_insn
, 1);
6467 link_mem
= XEXP (link_mem
, 1);
6470 /* last_function_call is inherited by bb_succ. */
6471 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
6473 if (find_insn_list (XEXP (u
, 0),
6474 bb_last_function_call
[bb_succ
]))
6477 bb_last_function_call
[bb_succ
]
6478 = alloc_INSN_LIST (XEXP (u
, 0),
6479 bb_last_function_call
[bb_succ
]);
6482 /* last_pending_memory_flush is inherited by bb_succ. */
6483 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
6485 if (find_insn_list (XEXP (u
, 0),
6486 bb_last_pending_memory_flush
[bb_succ
]))
6489 bb_last_pending_memory_flush
[bb_succ
]
6490 = alloc_INSN_LIST (XEXP (u
, 0),
6491 bb_last_pending_memory_flush
[bb_succ
]);
6494 /* sched_before_next_call is inherited by bb_succ. */
6495 x
= LOG_LINKS (sched_before_next_call
);
6496 for (; x
; x
= XEXP (x
, 1))
6497 add_dependence (bb_sched_before_next_call
[bb_succ
],
6498 XEXP (x
, 0), REG_DEP_ANTI
);
6502 while (e
!= first_edge
);
6505 /* Free up the INSN_LISTs.
6507 Note this loop is executed max_reg * nr_regions times. It's first
6508 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6509 The list was empty for the vast majority of those calls. On the PA, not
6510 calling free_INSN_LIST_list in those cases improves -O2 compile times by
6512 for (b
= 0; b
< max_reg
; ++b
)
6514 if (reg_last_clobbers
[b
])
6515 free_INSN_LIST_list (®_last_clobbers
[b
]);
6516 if (reg_last_sets
[b
])
6517 free_INSN_LIST_list (®_last_sets
[b
]);
6518 if (reg_last_uses
[b
])
6519 free_INSN_LIST_list (®_last_uses
[b
]);
6522 /* Assert that we won't need bb_reg_last_* for this block anymore. */
6523 if (current_nr_blocks
> 1)
6525 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
6526 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
6527 bb_reg_last_clobbers
[bb
] = (rtx
*) NULL_RTX
;
6529 else if (current_nr_blocks
== 1)
6531 free (reg_last_uses
);
6532 free (reg_last_sets
);
6533 free (reg_last_clobbers
);
6537 /* Print dependences for debugging, callable from debugger. */
6540 debug_dependencies ()
6544 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
6545 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6553 get_bb_head_tail (bb
, &head
, &tail
);
6554 next_tail
= NEXT_INSN (tail
);
6555 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
6556 BB_TO_BLOCK (bb
), bb
);
6558 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6559 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6560 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6561 "----", "----", "--", "---", "----", "----", "--------", "-----");
6562 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6567 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6570 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
6571 if (GET_CODE (insn
) == NOTE
)
6573 n
= NOTE_LINE_NUMBER (insn
);
6575 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
6577 fprintf (dump
, "line %d, file %s\n", n
,
6578 NOTE_SOURCE_FILE (insn
));
6581 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
6585 unit
= insn_unit (insn
);
6587 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
6588 function_units
[unit
].blockage_range_function (insn
);
6590 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
6591 (SCHED_GROUP_P (insn
) ? "+" : " "),
6595 INSN_DEP_COUNT (insn
),
6596 INSN_PRIORITY (insn
),
6597 insn_cost (insn
, 0, 0),
6598 (int) MIN_BLOCKAGE_COST (range
),
6599 (int) MAX_BLOCKAGE_COST (range
));
6600 insn_print_units (insn
);
6601 fprintf (dump
, "\t: ");
6602 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
6603 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
6604 fprintf (dump
, "\n");
6608 fprintf (dump
, "\n");
6611 /* Set_priorities: compute priority of each insn in the block. */
6624 get_bb_head_tail (bb
, &head
, &tail
);
6625 prev_head
= PREV_INSN (head
);
6628 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6632 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
6635 if (GET_CODE (insn
) == NOTE
)
6638 if (!(SCHED_GROUP_P (insn
)))
6640 (void) priority (insn
);
6646 /* Make each element of VECTOR point at an rtx-vector,
6647 taking the space for all those rtx-vectors from SPACE.
6648 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
6649 BYTES_PER_ELT is the number of bytes in one rtx-vector.
6650 (this is the same as init_regset_vector () in flow.c) */
6653 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
6660 register rtx
*p
= space
;
6662 for (i
= 0; i
< nelts
; i
++)
6665 p
+= bytes_per_elt
/ sizeof (*p
);
6669 /* Schedule a region. A region is either an inner loop, a loop-free
6670 subroutine, or a single basic block. Each bb in the region is
6671 scheduled after its flow predecessors. */
6674 schedule_region (rgn
)
6678 int rgn_n_insns
= 0;
6679 int sched_rgn_n_insns
= 0;
6680 rtx
*bb_reg_last_uses_space
= NULL
;
6681 rtx
*bb_reg_last_sets_space
= NULL
;
6682 rtx
*bb_reg_last_clobbers_space
= NULL
;
6684 /* Set variables for the current region. */
6685 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
6686 current_blocks
= RGN_BLOCKS (rgn
);
6688 reg_pending_sets
= ALLOCA_REG_SET ();
6689 reg_pending_clobbers
= ALLOCA_REG_SET ();
6690 reg_pending_sets_all
= 0;
6692 /* Initializations for region data dependence analyisis. */
6693 if (current_nr_blocks
> 1)
6696 int maxreg
= max_reg_num ();
6698 bb_reg_last_uses
= (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6699 bb_reg_last_uses_space
6700 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6701 init_rtx_vector (bb_reg_last_uses
, bb_reg_last_uses_space
,
6702 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6704 bb_reg_last_sets
= (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6705 bb_reg_last_sets_space
6706 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6707 init_rtx_vector (bb_reg_last_sets
, bb_reg_last_sets_space
,
6708 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6710 bb_reg_last_clobbers
=
6711 (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6712 bb_reg_last_clobbers_space
6713 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6714 init_rtx_vector (bb_reg_last_clobbers
, bb_reg_last_clobbers_space
,
6715 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6717 bb_pending_read_insns
6718 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6719 bb_pending_read_mems
6720 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6721 bb_pending_write_insns
=
6722 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6723 bb_pending_write_mems
6724 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6725 bb_pending_lists_length
=
6726 (int *) xmalloc (current_nr_blocks
* sizeof (int));
6727 bb_last_pending_memory_flush
=
6728 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6729 bb_last_function_call
6730 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6731 bb_sched_before_next_call
=
6732 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6734 init_rgn_data_dependences (current_nr_blocks
);
6737 /* Compute LOG_LINKS. */
6738 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6739 compute_block_backward_dependences (bb
);
6741 /* Compute INSN_DEPEND. */
6742 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
6743 compute_block_forward_dependences (bb
);
6745 /* Delete line notes and set priorities. */
6746 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6748 if (write_symbols
!= NO_DEBUG
)
6750 save_line_notes (bb
);
6754 rgn_n_insns
+= set_priorities (bb
);
6757 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6758 if (current_nr_blocks
> 1)
6762 prob
= (float *) xmalloc ((current_nr_blocks
) * sizeof (float));
6764 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
6765 dom
= (bbset
*) xmalloc (current_nr_blocks
* sizeof (bbset
));
6766 for (i
= 0; i
< current_nr_blocks
; i
++)
6767 dom
[i
] = (bbset
) xcalloc (bbset_size
, sizeof (HOST_WIDE_INT
));
6771 edge_to_bit
= (int *) xmalloc (nr_edges
* sizeof (int));
6772 for (i
= 1; i
< nr_edges
; i
++)
6773 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
6774 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
6775 rgn_edges
= (int *) xmalloc (rgn_nr_edges
* sizeof (int));
6778 for (i
= 1; i
< nr_edges
; i
++)
6779 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
6780 rgn_edges
[rgn_nr_edges
++] = i
;
6783 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
6784 pot_split
= (edgeset
*) xmalloc (current_nr_blocks
* sizeof (edgeset
));
6786 = (edgeset
*) xmalloc (current_nr_blocks
* sizeof (edgeset
));
6787 for (i
= 0; i
< current_nr_blocks
; i
++)
6790 (edgeset
) xcalloc (edgeset_size
, sizeof (HOST_WIDE_INT
));
6792 (edgeset
) xcalloc (edgeset_size
, sizeof (HOST_WIDE_INT
));
6795 /* Compute probabilities, dominators, split_edges. */
6796 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6797 compute_dom_prob_ps (bb
);
6800 /* Now we can schedule all blocks. */
6801 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6802 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
6804 /* Sanity check: verify that all region insns were scheduled. */
6805 if (sched_rgn_n_insns
!= rgn_n_insns
)
6808 /* Restore line notes. */
6809 if (write_symbols
!= NO_DEBUG
)
6811 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6812 restore_line_notes (bb
);
6815 /* Done with this region. */
6816 free_pending_lists ();
6818 FREE_REG_SET (reg_pending_sets
);
6819 FREE_REG_SET (reg_pending_clobbers
);
6821 if (current_nr_blocks
> 1)
6825 free (bb_reg_last_uses_space
);
6826 free (bb_reg_last_uses
);
6827 free (bb_reg_last_sets_space
);
6828 free (bb_reg_last_sets
);
6829 free (bb_reg_last_clobbers_space
);
6830 free (bb_reg_last_clobbers
);
6831 free (bb_pending_read_insns
);
6832 free (bb_pending_read_mems
);
6833 free (bb_pending_write_insns
);
6834 free (bb_pending_write_mems
);
6835 free (bb_pending_lists_length
);
6836 free (bb_last_pending_memory_flush
);
6837 free (bb_last_function_call
);
6838 free (bb_sched_before_next_call
);
6840 for (i
= 0; i
< current_nr_blocks
; ++i
)
6843 free (pot_split
[i
]);
6844 free (ancestor_edges
[i
]);
6850 free (ancestor_edges
);
6854 /* The one entry point in this file. DUMP_FILE is the dump file for
6858 schedule_insns (dump_file
)
6861 int *deaths_in_region
;
6862 sbitmap blocks
, large_region_blocks
;
6868 int any_large_regions
;
6870 /* Disable speculative loads in their presence if cc0 defined. */
6872 flag_schedule_speculative_load
= 0;
6875 /* Taking care of this degenerate case makes the rest of
6876 this code simpler. */
6877 if (n_basic_blocks
== 0)
6880 /* Set dump and sched_verbose for the desired debugging output. If no
6881 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
6882 For -fsched-verbose-N, N>=10, print everything to stderr. */
6883 sched_verbose
= sched_verbose_param
;
6884 if (sched_verbose_param
== 0 && dump_file
)
6886 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
6891 /* Initialize issue_rate. */
6892 issue_rate
= ISSUE_RATE
;
6894 split_all_insns (1);
6896 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6897 pseudos which do not cross calls. */
6898 max_uid
= get_max_uid () + 1;
6900 cant_move
= xcalloc (max_uid
, sizeof (char));
6901 fed_by_spec_load
= xcalloc (max_uid
, sizeof (char));
6902 is_load_insn
= xcalloc (max_uid
, sizeof (char));
6904 insn_luid
= (int *) xmalloc (max_uid
* sizeof (int));
6908 for (b
= 0; b
< n_basic_blocks
; b
++)
6909 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
6911 INSN_LUID (insn
) = luid
;
6913 /* Increment the next luid, unless this is a note. We don't
6914 really need separate IDs for notes and we don't want to
6915 schedule differently depending on whether or not there are
6916 line-number notes, i.e., depending on whether or not we're
6917 generating debugging information. */
6918 if (GET_CODE (insn
) != NOTE
)
6921 if (insn
== BLOCK_END (b
))
6925 /* ?!? We could save some memory by computing a per-region luid mapping
6926 which could reduce both the number of vectors in the cache and the size
6927 of each vector. Instead we just avoid the cache entirely unless the
6928 average number of instructions in a basic block is very high. See
6929 the comment before the declaration of true_dependency_cache for
6930 what we consider "very high". */
6931 if (luid
/ n_basic_blocks
> 100 * 5)
6933 true_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
6934 sbitmap_vector_zero (true_dependency_cache
, luid
);
6938 rgn_table
= (region
*) xmalloc ((n_basic_blocks
) * sizeof (region
));
6939 rgn_bb_table
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6940 block_to_bb
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6941 containing_rgn
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6943 blocks
= sbitmap_alloc (n_basic_blocks
);
6944 large_region_blocks
= sbitmap_alloc (n_basic_blocks
);
6946 compute_bb_for_insn (max_uid
);
6948 /* Compute regions for scheduling. */
6949 if (reload_completed
6950 || n_basic_blocks
== 1
6951 || !flag_schedule_interblock
)
6953 find_single_block_region ();
6957 /* Verify that a 'good' control flow graph can be built. */
6958 if (is_cfg_nonregular ())
6960 find_single_block_region ();
6964 int_list_ptr
*s_preds
, *s_succs
;
6965 int *num_preds
, *num_succs
;
6966 sbitmap
*dom
, *pdom
;
6968 s_preds
= (int_list_ptr
*) xmalloc (n_basic_blocks
6969 * sizeof (int_list_ptr
));
6970 s_succs
= (int_list_ptr
*) xmalloc (n_basic_blocks
6971 * sizeof (int_list_ptr
));
6972 num_preds
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
6973 num_succs
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
6974 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6975 pdom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6977 /* The scheduler runs after flow; therefore, we can't blindly call
6978 back into find_basic_blocks since doing so could invalidate the
6979 info in global_live_at_start.
6981 Consider a block consisting entirely of dead stores; after life
6982 analysis it would be a block of NOTE_INSN_DELETED notes. If
6983 we call find_basic_blocks again, then the block would be removed
6984 entirely and invalidate our the register live information.
6986 We could (should?) recompute register live information. Doing
6987 so may even be beneficial. */
6989 compute_preds_succs (s_preds
, s_succs
, num_preds
, num_succs
);
6991 /* Compute the dominators and post dominators. We don't
6992 currently use post dominators, but we should for
6993 speculative motion analysis. */
6994 compute_dominators (dom
, pdom
, s_preds
, s_succs
);
6996 /* build_control_flow will return nonzero if it detects unreachable
6997 blocks or any other irregularity with the cfg which prevents
6998 cross block scheduling. */
6999 if (build_control_flow (s_preds
, s_succs
, num_preds
, num_succs
) != 0)
7000 find_single_block_region ();
7002 find_rgns (s_preds
, s_succs
, num_preds
, num_succs
, dom
);
7004 if (sched_verbose
>= 3)
7007 /* For now. This will move as more and more of haifa is converted
7008 to using the cfg code in flow.c. */
7019 /* Allocate data for this pass. See comments, above,
7020 for what these vectors do.
7022 We use xmalloc instead of alloca, because max_uid can be very large
7023 when there is a lot of function inlining. If we used alloca, we could
7024 exceed stack limits on some hosts for some inputs. */
7025 insn_priority
= (int *) xcalloc (max_uid
, sizeof (int));
7026 insn_reg_weight
= (int *) xcalloc (max_uid
, sizeof (int));
7027 insn_tick
= (int *) xcalloc (max_uid
, sizeof (int));
7028 insn_costs
= (short *) xcalloc (max_uid
, sizeof (short));
7029 insn_units
= (short *) xcalloc (max_uid
, sizeof (short));
7030 insn_blockage
= (unsigned int *) xcalloc (max_uid
, sizeof (unsigned int));
7031 insn_ref_count
= (int *) xcalloc (max_uid
, sizeof (int));
7033 /* Allocate for forward dependencies. */
7034 insn_dep_count
= (int *) xcalloc (max_uid
, sizeof (int));
7035 insn_depend
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
7037 deaths_in_region
= (int *) xmalloc (sizeof(int) * nr_regions
);
7039 init_alias_analysis ();
7041 if (write_symbols
!= NO_DEBUG
)
7045 line_note
= (rtx
*) xcalloc (max_uid
, sizeof (rtx
));
7046 line_note_head
= (rtx
*) xcalloc (n_basic_blocks
, sizeof (rtx
));
7048 /* Save-line-note-head:
7049 Determine the line-number at the start of each basic block.
7050 This must be computed and saved now, because after a basic block's
7051 predecessor has been scheduled, it is impossible to accurately
7052 determine the correct line number for the first insn of the block. */
7054 for (b
= 0; b
< n_basic_blocks
; b
++)
7055 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
7056 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
7058 line_note_head
[b
] = line
;
7063 /* Find units used in this fuction, for visualization. */
7065 init_target_units ();
7067 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7068 known why this is done. */
7070 insn
= BLOCK_END (n_basic_blocks
- 1);
7071 if (NEXT_INSN (insn
) == 0
7072 || (GET_CODE (insn
) != NOTE
7073 && GET_CODE (insn
) != CODE_LABEL
7074 /* Don't emit a NOTE if it would end up between an unconditional
7075 jump and a BARRIER. */
7076 && !(GET_CODE (insn
) == JUMP_INSN
7077 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
7078 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
7080 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
7081 removing death notes. */
7082 for (b
= n_basic_blocks
- 1; b
>= 0; b
--)
7083 find_insn_reg_weight (b
);
7085 /* Remove all death notes from the subroutine. */
7086 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7088 sbitmap_zero (blocks
);
7089 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
7090 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
7092 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
7095 /* Schedule every region in the subroutine. */
7096 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7097 schedule_region (rgn
);
7099 /* Update life analysis for the subroutine. Do single block regions
7100 first so that we can verify that live_at_start didn't change. Then
7101 do all other blocks. */
7102 /* ??? There is an outside possibility that update_life_info, or more
7103 to the point propagate_block, could get called with non-zero flags
7104 more than once for one basic block. This would be kinda bad if it
7105 were to happen, since REG_INFO would be accumulated twice for the
7106 block, and we'd have twice the REG_DEAD notes.
7108 I'm fairly certain that this _shouldn't_ happen, since I don't think
7109 that live_at_start should change at region heads. Not sure what the
7110 best way to test for this kind of thing... */
7112 allocate_reg_life_data ();
7113 compute_bb_for_insn (max_uid
);
7115 any_large_regions
= 0;
7116 sbitmap_ones (large_region_blocks
);
7118 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7119 if (RGN_NR_BLOCKS (rgn
) > 1)
7120 any_large_regions
= 1;
7123 sbitmap_zero (blocks
);
7124 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7125 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7127 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
7128 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7130 /* In the single block case, the count of registers that died should
7131 not have changed during the schedule. */
7132 if (count_or_remove_death_notes (blocks
, 0) != deaths_in_region
[rgn
])
7136 if (any_large_regions
)
7138 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
7139 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7142 /* Reposition the prologue and epilogue notes in case we moved the
7143 prologue/epilogue insns. */
7144 if (reload_completed
)
7145 reposition_prologue_and_epilogue_notes (get_insns ());
7147 /* Delete redundant line notes. */
7148 if (write_symbols
!= NO_DEBUG
)
7149 rm_redundant_line_notes ();
7153 if (reload_completed
== 0 && flag_schedule_interblock
)
7155 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
7163 fprintf (dump
, "\n\n");
7167 end_alias_analysis ();
7169 if (true_dependency_cache
)
7171 free (true_dependency_cache
);
7172 true_dependency_cache
= NULL
;
7175 free (rgn_bb_table
);
7177 free (containing_rgn
);
7179 free (fed_by_spec_load
);
7180 free (is_load_insn
);
7183 free (insn_priority
);
7184 free (insn_reg_weight
);
7188 free (insn_blockage
);
7189 free (insn_ref_count
);
7191 free (insn_dep_count
);
7194 if (write_symbols
!= NO_DEBUG
)
7197 free (line_note_head
);
7217 sbitmap_free (blocks
);
7218 sbitmap_free (large_region_blocks
);
7220 free (deaths_in_region
);
7223 #endif /* INSN_SCHEDULING */