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 /* To speed up the test for duplicate dependency links we keep a record
247 of true dependencies created by add_dependence when the average number
248 of instructions in a basic block is very large.
250 Studies have shown that there is typically around 5 instructions between
251 branches for typical C code. So we can make a guess that the average
252 basic block is approximately 5 instructions long; we will choose 100X
253 the average size as a very large basic block.
255 Each insn has an associated bitmap for its dependencies. Each bitmap
256 has enough entries to represent a dependency on any other insn in the
258 static sbitmap
*true_dependency_cache
;
260 /* Indexed by INSN_UID, the collection of all data associated with
261 a single instruction. */
263 struct haifa_insn_data
265 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
266 it represents forward dependancies. */
269 /* The line number note in effect for each insn. For line number
270 notes, this indicates whether the note may be reused. */
273 /* Logical uid gives the original ordering of the insns. */
276 /* A priority for each insn. */
279 /* The number of incoming edges in the forward dependency graph.
280 As scheduling proceds, counts are decreased. An insn moves to
281 the ready queue when its counter reaches zero. */
284 /* An encoding of the blockage range function. Both unit and range
286 unsigned int blockage
;
288 /* Number of instructions referring to this insn. */
291 /* The minimum clock tick at which the insn becomes ready. This is
292 used to note timing constraints for the insns in the pending list. */
297 /* An encoding of the function units used. */
300 /* This weight is an estimation of the insn's contribution to
301 register pressure. */
304 /* Some insns (e.g. call) are not allowed to move across blocks. */
305 unsigned int cant_move
: 1;
307 /* Set if there's DEF-USE dependance between some speculatively
308 moved load insn and this one. */
309 unsigned int fed_by_spec_load
: 1;
310 unsigned int is_load_insn
: 1;
313 static struct haifa_insn_data
*h_i_d
;
315 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
316 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
317 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
318 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
319 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
320 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
321 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
323 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
325 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
326 #define ENCODE_BLOCKAGE(U, R) \
327 (((U) << BLOCKAGE_BITS \
328 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
329 | MAX_BLOCKAGE_COST (R))
330 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
331 #define BLOCKAGE_RANGE(B) \
332 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
333 | ((B) & BLOCKAGE_MASK))
335 /* Encodings of the `<name>_unit_blockage_range' function. */
336 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
337 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
339 #define DONE_PRIORITY -1
340 #define MAX_PRIORITY 0x7fffffff
341 #define TAIL_PRIORITY 0x7ffffffe
342 #define LAUNCH_PRIORITY 0x7f000001
343 #define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
344 #define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
346 #define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count)
347 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
348 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
349 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
350 #define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load)
351 #define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn)
353 /* Vector indexed by basic block number giving the starting line-number
354 for each basic block. */
355 static rtx
*line_note_head
;
357 /* List of important notes we must keep around. This is a pointer to the
358 last element in the list. */
359 static rtx note_list
;
363 /* An instruction is ready to be scheduled when all insns preceding it
364 have already been scheduled. It is important to ensure that all
365 insns which use its result will not be executed until its result
366 has been computed. An insn is maintained in one of four structures:
368 (P) the "Pending" set of insns which cannot be scheduled until
369 their dependencies have been satisfied.
370 (Q) the "Queued" set of insns that can be scheduled when sufficient
372 (R) the "Ready" list of unscheduled, uncommitted insns.
373 (S) the "Scheduled" list of insns.
375 Initially, all insns are either "Pending" or "Ready" depending on
376 whether their dependencies are satisfied.
378 Insns move from the "Ready" list to the "Scheduled" list as they
379 are committed to the schedule. As this occurs, the insns in the
380 "Pending" list have their dependencies satisfied and move to either
381 the "Ready" list or the "Queued" set depending on whether
382 sufficient time has passed to make them ready. As time passes,
383 insns move from the "Queued" set to the "Ready" list. Insns may
384 move from the "Ready" list to the "Queued" set if they are blocked
385 due to a function unit conflict.
387 The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
388 insns, i.e., those that are ready, queued, and pending.
389 The "Queued" set (Q) is implemented by the variable `insn_queue'.
390 The "Ready" list (R) is implemented by the variables `ready' and
392 The "Scheduled" list (S) is the new insn chain built by this pass.
394 The transition (R->S) is implemented in the scheduling loop in
395 `schedule_block' when the best insn to schedule is chosen.
396 The transition (R->Q) is implemented in `queue_insn' when an
397 insn is found to have a function unit conflict with the already
399 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
400 insns move from the ready list to the scheduled list.
401 The transition (Q->R) is implemented in 'queue_to_insn' as time
402 passes or stalls are introduced. */
404 /* Implement a circular buffer to delay instructions until sufficient
405 time has passed. INSN_QUEUE_SIZE is a power of two larger than
406 MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
407 longest time an isnsn may be queued. */
408 static rtx insn_queue
[INSN_QUEUE_SIZE
];
409 static int q_ptr
= 0;
410 static int q_size
= 0;
411 #define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
412 #define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
414 /* Forward declarations. */
415 static void add_dependence
PROTO ((rtx
, rtx
, enum reg_note
));
417 static void remove_dependence
PROTO ((rtx
, rtx
));
419 static rtx find_insn_list
PROTO ((rtx
, rtx
));
420 static int insn_unit
PROTO ((rtx
));
421 static unsigned int blockage_range
PROTO ((int, rtx
));
422 static void clear_units
PROTO ((void));
423 static int actual_hazard_this_instance
PROTO ((int, int, rtx
, int, int));
424 static void schedule_unit
PROTO ((int, rtx
, int));
425 static int actual_hazard
PROTO ((int, rtx
, int, int));
426 static int potential_hazard
PROTO ((int, rtx
, int));
427 static int insn_cost
PROTO ((rtx
, rtx
, rtx
));
428 static int priority
PROTO ((rtx
));
429 static void free_pending_lists
PROTO ((void));
430 static void add_insn_mem_dependence
PROTO ((rtx
*, rtx
*, rtx
, rtx
));
431 static void flush_pending_lists
PROTO ((rtx
, int));
432 static void sched_analyze_1
PROTO ((rtx
, rtx
));
433 static void sched_analyze_2
PROTO ((rtx
, rtx
));
434 static void sched_analyze_insn
PROTO ((rtx
, rtx
, rtx
));
435 static void sched_analyze
PROTO ((rtx
, rtx
));
436 static int rank_for_schedule
PROTO ((const PTR
, const PTR
));
437 static void swap_sort
PROTO ((rtx
*, int));
438 static void queue_insn
PROTO ((rtx
, int));
439 static int schedule_insn
PROTO ((rtx
, rtx
*, int, int));
440 static void find_insn_reg_weight
PROTO ((int));
441 static int schedule_block
PROTO ((int, int));
442 static char *safe_concat
PROTO ((char *, char *, const char *));
443 static int insn_issue_delay
PROTO ((rtx
));
444 static void adjust_priority
PROTO ((rtx
));
446 /* Control flow graph edges are kept in circular lists. */
455 static haifa_edge
*edge_table
;
457 #define NEXT_IN(edge) (edge_table[edge].next_in)
458 #define NEXT_OUT(edge) (edge_table[edge].next_out)
459 #define FROM_BLOCK(edge) (edge_table[edge].from_block)
460 #define TO_BLOCK(edge) (edge_table[edge].to_block)
462 /* Number of edges in the control flow graph. (In fact, larger than
463 that by 1, since edge 0 is unused.) */
466 /* Circular list of incoming/outgoing edges of a block. */
467 static int *in_edges
;
468 static int *out_edges
;
470 #define IN_EDGES(block) (in_edges[block])
471 #define OUT_EDGES(block) (out_edges[block])
475 static int is_cfg_nonregular
PROTO ((void));
476 static int build_control_flow
PROTO ((struct edge_list
*));
477 static void new_edge
PROTO ((int, int));
480 /* A region is the main entity for interblock scheduling: insns
481 are allowed to move between blocks in the same region, along
482 control flow graph edges, in the 'up' direction. */
485 int rgn_nr_blocks
; /* Number of blocks in region. */
486 int rgn_blocks
; /* cblocks in the region (actually index in rgn_bb_table). */
490 /* Number of regions in the procedure. */
491 static int nr_regions
;
493 /* Table of region descriptions. */
494 static region
*rgn_table
;
496 /* Array of lists of regions' blocks. */
497 static int *rgn_bb_table
;
499 /* Topological order of blocks in the region (if b2 is reachable from
500 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is
501 always referred to by either block or b, while its topological
502 order name (in the region) is refered to by bb. */
503 static int *block_to_bb
;
505 /* The number of the region containing a block. */
506 static int *containing_rgn
;
508 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
509 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
510 #define BLOCK_TO_BB(block) (block_to_bb[block])
511 #define CONTAINING_RGN(block) (containing_rgn[block])
513 void debug_regions
PROTO ((void));
514 static void find_single_block_region
PROTO ((void));
515 static void find_rgns
PROTO ((struct edge_list
*, sbitmap
*));
516 static int too_large
PROTO ((int, int *, int *));
518 extern void debug_live
PROTO ((int, int));
520 /* Blocks of the current region being scheduled. */
521 static int current_nr_blocks
;
522 static int current_blocks
;
524 /* The mapping from bb to block. */
525 #define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
528 /* Bit vectors and bitset operations are needed for computations on
529 the control flow graph. */
531 typedef unsigned HOST_WIDE_INT
*bitset
;
534 int *first_member
; /* Pointer to the list start in bitlst_table. */
535 int nr_members
; /* The number of members of the bit list. */
539 static int bitlst_table_last
;
540 static int bitlst_table_size
;
541 static int *bitlst_table
;
543 static char bitset_member
PROTO ((bitset
, int, int));
544 static void extract_bitlst
PROTO ((bitset
, int, bitlst
*));
546 /* Target info declarations.
548 The block currently being scheduled is referred to as the "target" block,
549 while other blocks in the region from which insns can be moved to the
550 target are called "source" blocks. The candidate structure holds info
551 about such sources: are they valid? Speculative? Etc. */
552 typedef bitlst bblst
;
563 static candidate
*candidate_table
;
565 /* A speculative motion requires checking live information on the path
566 from 'source' to 'target'. The split blocks are those to be checked.
567 After a speculative motion, live information should be modified in
570 Lists of split and update blocks for each candidate of the current
571 target are in array bblst_table. */
572 static int *bblst_table
, bblst_size
, bblst_last
;
574 #define IS_VALID(src) ( candidate_table[src].is_valid )
575 #define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative )
576 #define SRC_PROB(src) ( candidate_table[src].src_prob )
578 /* The bb being currently scheduled. */
579 static int target_bb
;
582 typedef bitlst edgelst
;
584 /* Target info functions. */
585 static void split_edges
PROTO ((int, int, edgelst
*));
586 static void compute_trg_info
PROTO ((int));
587 void debug_candidate
PROTO ((int));
588 void debug_candidates
PROTO ((int));
591 /* Bit-set of bbs, where bit 'i' stands for bb 'i'. */
592 typedef bitset bbset
;
594 /* Number of words of the bbset. */
595 static int bbset_size
;
597 /* Dominators array: dom[i] contains the bbset of dominators of
598 bb i in the region. */
601 /* bb 0 is the only region entry. */
602 #define IS_RGN_ENTRY(bb) (!bb)
604 /* Is bb_src dominated by bb_trg. */
605 #define IS_DOMINATED(bb_src, bb_trg) \
606 ( bitset_member (dom[bb_src], bb_trg, bbset_size) )
608 /* Probability: Prob[i] is a float in [0, 1] which is the probability
609 of bb i relative to the region entry. */
612 /* The probability of bb_src, relative to bb_trg. Note, that while the
613 'prob[bb]' is a float in [0, 1], this macro returns an integer
615 #define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \
618 /* Bit-set of edges, where bit i stands for edge i. */
619 typedef bitset edgeset
;
621 /* Number of edges in the region. */
622 static int rgn_nr_edges
;
624 /* Array of size rgn_nr_edges. */
625 static int *rgn_edges
;
627 /* Number of words in an edgeset. */
628 static int edgeset_size
;
630 /* Mapping from each edge in the graph to its number in the rgn. */
631 static int *edge_to_bit
;
632 #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
634 /* The split edges of a source bb is different for each target
635 bb. In order to compute this efficiently, the 'potential-split edges'
636 are computed for each bb prior to scheduling a region. This is actually
637 the split edges of each bb relative to the region entry.
639 pot_split[bb] is the set of potential split edges of bb. */
640 static edgeset
*pot_split
;
642 /* For every bb, a set of its ancestor edges. */
643 static edgeset
*ancestor_edges
;
645 static void compute_dom_prob_ps
PROTO ((int));
647 #define ABS_VALUE(x) (((x)<0)?(-(x)):(x))
648 #define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
649 #define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN))))
650 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
652 /* Parameters affecting the decision of rank_for_schedule(). */
653 #define MIN_DIFF_PRIORITY 2
654 #define MIN_PROBABILITY 40
655 #define MIN_PROB_DIFF 10
657 /* Speculative scheduling functions. */
658 static int check_live_1
PROTO ((int, rtx
));
659 static void update_live_1
PROTO ((int, rtx
));
660 static int check_live
PROTO ((rtx
, int));
661 static void update_live
PROTO ((rtx
, int));
662 static void set_spec_fed
PROTO ((rtx
));
663 static int is_pfree
PROTO ((rtx
, int, int));
664 static int find_conditional_protection
PROTO ((rtx
, int));
665 static int is_conditionally_protected
PROTO ((rtx
, int, int));
666 static int may_trap_exp
PROTO ((rtx
, int));
667 static int haifa_classify_insn
PROTO ((rtx
));
668 static int is_prisky
PROTO ((rtx
, int, int));
669 static int is_exception_free
PROTO ((rtx
, int, int));
671 static char find_insn_mem_list
PROTO ((rtx
, rtx
, rtx
, rtx
));
672 static void compute_block_forward_dependences
PROTO ((int));
673 static void init_rgn_data_dependences
PROTO ((int));
674 static void add_branch_dependences
PROTO ((rtx
, rtx
));
675 static void compute_block_backward_dependences
PROTO ((int));
676 void debug_dependencies
PROTO ((void));
678 /* Notes handling mechanism:
679 =========================
680 Generally, NOTES are saved before scheduling and restored after scheduling.
681 The scheduler distinguishes between three types of notes:
683 (1) LINE_NUMBER notes, generated and used for debugging. Here,
684 before scheduling a region, a pointer to the LINE_NUMBER note is
685 added to the insn following it (in save_line_notes()), and the note
686 is removed (in rm_line_notes() and unlink_line_notes()). After
687 scheduling the region, this pointer is used for regeneration of
688 the LINE_NUMBER note (in restore_line_notes()).
690 (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
691 Before scheduling a region, a pointer to the note is added to the insn
692 that follows or precedes it. (This happens as part of the data dependence
693 computation). After scheduling an insn, the pointer contained in it is
694 used for regenerating the corresponding note (in reemit_notes).
696 (3) All other notes (e.g. INSN_DELETED): Before scheduling a block,
697 these notes are put in a list (in rm_other_notes() and
698 unlink_other_notes ()). After scheduling the block, these notes are
699 inserted at the beginning of the block (in schedule_block()). */
701 static rtx unlink_other_notes
PROTO ((rtx
, rtx
));
702 static rtx unlink_line_notes
PROTO ((rtx
, rtx
));
703 static void rm_line_notes
PROTO ((int));
704 static void save_line_notes
PROTO ((int));
705 static void restore_line_notes
PROTO ((int));
706 static void rm_redundant_line_notes
PROTO ((void));
707 static void rm_other_notes
PROTO ((rtx
, rtx
));
708 static rtx reemit_notes
PROTO ((rtx
, rtx
));
710 static void get_block_head_tail
PROTO ((int, rtx
*, rtx
*));
711 static void get_bb_head_tail
PROTO ((int, rtx
*, rtx
*));
713 static int queue_to_ready
PROTO ((rtx
[], int));
715 static void debug_ready_list
PROTO ((rtx
[], int));
716 static void init_target_units
PROTO ((void));
717 static void insn_print_units
PROTO ((rtx
));
718 static int get_visual_tbl_length
PROTO ((void));
719 static void init_block_visualization
PROTO ((void));
720 static void print_block_visualization
PROTO ((int, const char *));
721 static void visualize_scheduled_insns
PROTO ((int, int));
722 static void visualize_no_unit
PROTO ((rtx
));
723 static void visualize_stall_cycles
PROTO ((int, int));
724 static void print_exp
PROTO ((char *, rtx
, int));
725 static void print_value
PROTO ((char *, rtx
, int));
726 static void print_pattern
PROTO ((char *, rtx
, int));
727 static void print_insn
PROTO ((char *, rtx
, int));
728 void debug_reg_vector
PROTO ((regset
));
730 static rtx move_insn1
PROTO ((rtx
, rtx
));
731 static rtx move_insn
PROTO ((rtx
, rtx
));
732 static rtx group_leader
PROTO ((rtx
));
733 static int set_priorities
PROTO ((int));
734 static void init_rtx_vector
PROTO ((rtx
**, rtx
*, int, int));
735 static void schedule_region
PROTO ((int));
737 #endif /* INSN_SCHEDULING */
739 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
741 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
742 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type
743 of dependence that this link represents. */
746 add_dependence (insn
, elem
, dep_type
)
749 enum reg_note dep_type
;
753 /* Don't depend an insn on itself. */
757 /* We can get a dependency on deleted insns due to optimizations in
758 the register allocation and reloading or due to splitting. Any
759 such dependency is useless and can be ignored. */
760 if (GET_CODE (elem
) == NOTE
)
763 /* If elem is part of a sequence that must be scheduled together, then
764 make the dependence point to the last insn of the sequence.
765 When HAVE_cc0, it is possible for NOTEs to exist between users and
766 setters of the condition codes, so we must skip past notes here.
767 Otherwise, NOTEs are impossible here. */
769 next
= NEXT_INSN (elem
);
772 while (next
&& GET_CODE (next
) == NOTE
)
773 next
= NEXT_INSN (next
);
776 if (next
&& SCHED_GROUP_P (next
)
777 && GET_CODE (next
) != CODE_LABEL
)
779 /* Notes will never intervene here though, so don't bother checking
781 /* We must reject CODE_LABELs, so that we don't get confused by one
782 that has LABEL_PRESERVE_P set, which is represented by the same
783 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
785 while (NEXT_INSN (next
) && SCHED_GROUP_P (NEXT_INSN (next
))
786 && GET_CODE (NEXT_INSN (next
)) != CODE_LABEL
)
787 next
= NEXT_INSN (next
);
789 /* Again, don't depend an insn on itself. */
793 /* Make the dependence to NEXT, the last insn of the group, instead
794 of the original ELEM. */
798 #ifdef INSN_SCHEDULING
799 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
800 No need for interblock dependences with calls, since
801 calls are not moved between blocks. Note: the edge where
802 elem is a CALL is still required. */
803 if (GET_CODE (insn
) == CALL_INSN
804 && (INSN_BB (elem
) != INSN_BB (insn
)))
808 /* If we already have a true dependency for ELEM, then we do not
809 need to do anything. Avoiding the list walk below can cut
810 compile times dramatically for some code. */
811 if (true_dependency_cache
812 && TEST_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
)))
816 /* Check that we don't already have this dependence. */
817 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
818 if (XEXP (link
, 0) == elem
)
820 /* If this is a more restrictive type of dependence than the existing
821 one, then change the existing dependence to this type. */
822 if ((int) dep_type
< (int) REG_NOTE_KIND (link
))
823 PUT_REG_NOTE_KIND (link
, dep_type
);
825 #ifdef INSN_SCHEDULING
826 /* If we are adding a true dependency to INSN's LOG_LINKs, then
827 note that in the bitmap cache of true dependency information. */
828 if ((int)dep_type
== 0 && true_dependency_cache
)
829 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
833 /* Might want to check one level of transitivity to save conses. */
835 link
= alloc_INSN_LIST (elem
, LOG_LINKS (insn
));
836 LOG_LINKS (insn
) = link
;
838 /* Insn dependency, not data dependency. */
839 PUT_REG_NOTE_KIND (link
, dep_type
);
841 #ifdef INSN_SCHEDULING
842 /* If we are adding a true dependency to INSN's LOG_LINKs, then
843 note that in the bitmap cache of true dependency information. */
844 if ((int)dep_type
== 0 && true_dependency_cache
)
845 SET_BIT (true_dependency_cache
[INSN_LUID (insn
)], INSN_LUID (elem
));
850 /* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
851 of INSN. Abort if not found. */
854 remove_dependence (insn
, elem
)
858 rtx prev
, link
, next
;
861 for (prev
= 0, link
= LOG_LINKS (insn
); link
; link
= next
)
863 next
= XEXP (link
, 1);
864 if (XEXP (link
, 0) == elem
)
867 XEXP (prev
, 1) = next
;
869 LOG_LINKS (insn
) = next
;
871 #ifdef INSN_SCHEDULING
872 /* If we are removing a true dependency from the LOG_LINKS list,
873 make sure to remove it from the cache too. */
874 if (REG_NOTE_KIND (link
) == 0 && true_dependency_cache
)
875 RESET_BIT (true_dependency_cache
[INSN_LUID (insn
)],
879 free_INSN_LIST_node (link
);
891 #endif /* HAVE_cc0 */
893 #ifndef INSN_SCHEDULING
895 schedule_insns (dump_file
)
905 #define HAIFA_INLINE __inline
908 /* Computation of memory dependencies. */
910 /* The *_insns and *_mems are paired lists. Each pending memory operation
911 will have a pointer to the MEM rtx on one list and a pointer to the
912 containing insn on the other list in the same place in the list. */
914 /* We can't use add_dependence like the old code did, because a single insn
915 may have multiple memory accesses, and hence needs to be on the list
916 once for each memory access. Add_dependence won't let you add an insn
917 to a list more than once. */
919 /* An INSN_LIST containing all insns with pending read operations. */
920 static rtx pending_read_insns
;
922 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
923 static rtx pending_read_mems
;
925 /* An INSN_LIST containing all insns with pending write operations. */
926 static rtx pending_write_insns
;
928 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
929 static rtx pending_write_mems
;
931 /* Indicates the combined length of the two pending lists. We must prevent
932 these lists from ever growing too large since the number of dependencies
933 produced is at least O(N*N), and execution time is at least O(4*N*N), as
934 a function of the length of these pending lists. */
936 static int pending_lists_length
;
938 /* The last insn upon which all memory references must depend.
939 This is an insn which flushed the pending lists, creating a dependency
940 between it and all previously pending memory references. This creates
941 a barrier (or a checkpoint) which no memory reference is allowed to cross.
943 This includes all non constant CALL_INSNs. When we do interprocedural
944 alias analysis, this restriction can be relaxed.
945 This may also be an INSN that writes memory if the pending lists grow
948 static rtx last_pending_memory_flush
;
950 /* The last function call we have seen. All hard regs, and, of course,
951 the last function call, must depend on this. */
953 static rtx last_function_call
;
955 /* The LOG_LINKS field of this is a list of insns which use a pseudo register
956 that does not already cross a call. We create dependencies between each
957 of those insn and the next call insn, to ensure that they won't cross a call
958 after scheduling is done. */
960 static rtx sched_before_next_call
;
962 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
963 so that insns independent of the last scheduled insn will be preferred
964 over dependent instructions. */
966 static rtx last_scheduled_insn
;
968 /* Data structures for the computation of data dependences in a regions. We
969 keep one copy of each of the declared above variables for each bb in the
970 region. Before analyzing the data dependences for a bb, its variables
971 are initialized as a function of the variables of its predecessors. When
972 the analysis for a bb completes, we save the contents of each variable X
973 to a corresponding bb_X[bb] variable. For example, pending_read_insns is
974 copied to bb_pending_read_insns[bb]. Another change is that few
975 variables are now a list of insns rather than a single insn:
976 last_pending_memory_flash, last_function_call, reg_last_sets. The
977 manipulation of these variables was changed appropriately. */
979 static rtx
**bb_reg_last_uses
;
980 static rtx
**bb_reg_last_sets
;
981 static rtx
**bb_reg_last_clobbers
;
983 static rtx
*bb_pending_read_insns
;
984 static rtx
*bb_pending_read_mems
;
985 static rtx
*bb_pending_write_insns
;
986 static rtx
*bb_pending_write_mems
;
987 static int *bb_pending_lists_length
;
989 static rtx
*bb_last_pending_memory_flush
;
990 static rtx
*bb_last_function_call
;
991 static rtx
*bb_sched_before_next_call
;
993 /* Functions for construction of the control flow graph. */
995 /* Return 1 if control flow graph should not be constructed, 0 otherwise.
997 We decide not to build the control flow graph if there is possibly more
998 than one entry to the function, if computed branches exist, of if we
999 have nonlocal gotos. */
1002 is_cfg_nonregular ()
1008 /* If we have a label that could be the target of a nonlocal goto, then
1009 the cfg is not well structured. */
1010 if (nonlocal_goto_handler_labels
)
1013 /* If we have any forced labels, then the cfg is not well structured. */
1017 /* If this function has a computed jump, then we consider the cfg
1018 not well structured. */
1019 if (current_function_has_computed_jump
)
1022 /* If we have exception handlers, then we consider the cfg not well
1023 structured. ?!? We should be able to handle this now that flow.c
1024 computes an accurate cfg for EH. */
1025 if (exception_handler_labels
)
1028 /* If we have non-jumping insns which refer to labels, then we consider
1029 the cfg not well structured. */
1030 /* Check for labels referred to other thn by jumps. */
1031 for (b
= 0; b
< n_basic_blocks
; b
++)
1032 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
1034 code
= GET_CODE (insn
);
1035 if (GET_RTX_CLASS (code
) == 'i')
1039 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1040 if (REG_NOTE_KIND (note
) == REG_LABEL
)
1044 if (insn
== BLOCK_END (b
))
1048 /* All the tests passed. Consider the cfg well structured. */
1052 /* Build the control flow graph and set nr_edges.
1054 Instead of trying to build a cfg ourselves, we rely on flow to
1055 do it for us. Stamp out useless code (and bug) duplication.
1057 Return nonzero if an irregularity in the cfg is found which would
1058 prevent cross block scheduling. */
1061 build_control_flow (edge_list
)
1062 struct edge_list
*edge_list
;
1064 int i
, unreachable
, num_edges
;
1066 /* This already accounts for entry/exit edges. */
1067 num_edges
= NUM_EDGES (edge_list
);
1069 /* Unreachable loops with more than one basic block are detected
1070 during the DFS traversal in find_rgns.
1072 Unreachable loops with a single block are detected here. This
1073 test is redundant with the one in find_rgns, but it's much
1074 cheaper to go ahead and catch the trivial case here. */
1076 for (i
= 0; i
< n_basic_blocks
; i
++)
1078 basic_block b
= BASIC_BLOCK (i
);
1081 || (b
->pred
->dest
== b
1082 && b
->pred
->pred_next
== NULL
))
1086 /* ??? We can kill these soon. */
1087 in_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1088 out_edges
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1089 edge_table
= (haifa_edge
*) xcalloc (num_edges
, sizeof (haifa_edge
));
1092 for (i
= 0; i
< num_edges
; i
++)
1094 edge e
= INDEX_EDGE (edge_list
, i
);
1096 if (e
->dest
!= EXIT_BLOCK_PTR
1097 && e
->src
!= ENTRY_BLOCK_PTR
)
1098 new_edge (e
->src
->index
, e
->dest
->index
);
1101 /* Increment by 1, since edge 0 is unused. */
1108 /* Record an edge in the control flow graph from SOURCE to TARGET.
1110 In theory, this is redundant with the s_succs computed above, but
1111 we have not converted all of haifa to use information from the
1115 new_edge (source
, target
)
1119 int curr_edge
, fst_edge
;
1121 /* Check for duplicates. */
1122 fst_edge
= curr_edge
= OUT_EDGES (source
);
1125 if (FROM_BLOCK (curr_edge
) == source
1126 && TO_BLOCK (curr_edge
) == target
)
1131 curr_edge
= NEXT_OUT (curr_edge
);
1133 if (fst_edge
== curr_edge
)
1139 FROM_BLOCK (e
) = source
;
1140 TO_BLOCK (e
) = target
;
1142 if (OUT_EDGES (source
))
1144 next_edge
= NEXT_OUT (OUT_EDGES (source
));
1145 NEXT_OUT (OUT_EDGES (source
)) = e
;
1146 NEXT_OUT (e
) = next_edge
;
1150 OUT_EDGES (source
) = e
;
1154 if (IN_EDGES (target
))
1156 next_edge
= NEXT_IN (IN_EDGES (target
));
1157 NEXT_IN (IN_EDGES (target
)) = e
;
1158 NEXT_IN (e
) = next_edge
;
1162 IN_EDGES (target
) = e
;
1168 /* BITSET macros for operations on the control flow graph. */
1170 /* Compute bitwise union of two bitsets. */
1171 #define BITSET_UNION(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 intersection of two bitsets. */
1178 #define BITSET_INTER(set1, set2, len) \
1179 do { register bitset tp = set1, sp = set2; \
1181 for (i = 0; i < len; i++) \
1182 *(tp++) &= *(sp++); } while (0)
1184 /* Compute bitwise difference of two bitsets. */
1185 #define BITSET_DIFFER(set1, set2, len) \
1186 do { register bitset tp = set1, sp = set2; \
1188 for (i = 0; i < len; i++) \
1189 *(tp++) &= ~*(sp++); } while (0)
1191 /* Inverts every bit of bitset 'set'. */
1192 #define BITSET_INVERT(set, len) \
1193 do { register bitset tmpset = set; \
1195 for (i = 0; i < len; i++, tmpset++) \
1196 *tmpset = ~*tmpset; } while (0)
1198 /* Turn on the index'th bit in bitset set. */
1199 #define BITSET_ADD(set, index, len) \
1201 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1204 set[index/HOST_BITS_PER_WIDE_INT] |= \
1205 1 << (index % HOST_BITS_PER_WIDE_INT); \
1208 /* Turn off the index'th bit in set. */
1209 #define BITSET_REMOVE(set, index, len) \
1211 if (index >= HOST_BITS_PER_WIDE_INT * len) \
1214 set[index/HOST_BITS_PER_WIDE_INT] &= \
1215 ~(1 << (index%HOST_BITS_PER_WIDE_INT)); \
1219 /* Check if the index'th bit in bitset set is on. */
1222 bitset_member (set
, index
, len
)
1226 if (index
>= HOST_BITS_PER_WIDE_INT
* len
)
1228 return (set
[index
/ HOST_BITS_PER_WIDE_INT
] &
1229 1 << (index
% HOST_BITS_PER_WIDE_INT
)) ? 1 : 0;
1233 /* Translate a bit-set SET to a list BL of the bit-set members. */
1236 extract_bitlst (set
, len
, bl
)
1242 unsigned HOST_WIDE_INT word
;
1244 /* bblst table space is reused in each call to extract_bitlst. */
1245 bitlst_table_last
= 0;
1247 bl
->first_member
= &bitlst_table
[bitlst_table_last
];
1250 for (i
= 0; i
< len
; i
++)
1253 offset
= i
* HOST_BITS_PER_WIDE_INT
;
1254 for (j
= 0; word
; j
++)
1258 bitlst_table
[bitlst_table_last
++] = offset
;
1269 /* Functions for the construction of regions. */
1271 /* Print the regions, for debugging purposes. Callable from debugger. */
1278 fprintf (dump
, "\n;; ------------ REGIONS ----------\n\n");
1279 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
1281 fprintf (dump
, ";;\trgn %d nr_blocks %d:\n", rgn
,
1282 rgn_table
[rgn
].rgn_nr_blocks
);
1283 fprintf (dump
, ";;\tbb/block: ");
1285 for (bb
= 0; bb
< rgn_table
[rgn
].rgn_nr_blocks
; bb
++)
1287 current_blocks
= RGN_BLOCKS (rgn
);
1289 if (bb
!= BLOCK_TO_BB (BB_TO_BLOCK (bb
)))
1292 fprintf (dump
, " %d/%d ", bb
, BB_TO_BLOCK (bb
));
1295 fprintf (dump
, "\n\n");
1300 /* Build a single block region for each basic block in the function.
1301 This allows for using the same code for interblock and basic block
1305 find_single_block_region ()
1309 for (i
= 0; i
< n_basic_blocks
; i
++)
1311 rgn_bb_table
[i
] = i
;
1312 RGN_NR_BLOCKS (i
) = 1;
1314 CONTAINING_RGN (i
) = i
;
1315 BLOCK_TO_BB (i
) = 0;
1317 nr_regions
= n_basic_blocks
;
1321 /* Update number of blocks and the estimate for number of insns
1322 in the region. Return 1 if the region is "too large" for interblock
1323 scheduling (compile time considerations), otherwise return 0. */
1326 too_large (block
, num_bbs
, num_insns
)
1327 int block
, *num_bbs
, *num_insns
;
1330 (*num_insns
) += (INSN_LUID (BLOCK_END (block
)) -
1331 INSN_LUID (BLOCK_HEAD (block
)));
1332 if ((*num_bbs
> MAX_RGN_BLOCKS
) || (*num_insns
> MAX_RGN_INSNS
))
1339 /* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk]
1340 is still an inner loop. Put in max_hdr[blk] the header of the most inner
1341 loop containing blk. */
1342 #define UPDATE_LOOP_RELATIONS(blk, hdr) \
1344 if (max_hdr[blk] == -1) \
1345 max_hdr[blk] = hdr; \
1346 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \
1347 RESET_BIT (inner, hdr); \
1348 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \
1350 RESET_BIT (inner,max_hdr[blk]); \
1351 max_hdr[blk] = hdr; \
1356 /* Find regions for interblock scheduling.
1358 A region for scheduling can be:
1360 * A loop-free procedure, or
1362 * A reducible inner loop, or
1364 * A basic block not contained in any other region.
1367 ?!? In theory we could build other regions based on extended basic
1368 blocks or reverse extended basic blocks. Is it worth the trouble?
1370 Loop blocks that form a region are put into the region's block list
1371 in topological order.
1373 This procedure stores its results into the following global (ick) variables
1382 We use dominator relationships to avoid making regions out of non-reducible
1385 This procedure needs to be converted to work on pred/succ lists instead
1386 of edge tables. That would simplify it somewhat. */
1389 find_rgns (edge_list
, dom
)
1390 struct edge_list
*edge_list
;
1393 int *max_hdr
, *dfs_nr
, *stack
, *degree
;
1395 int node
, child
, loop_head
, i
, head
, tail
;
1396 int count
= 0, sp
, idx
= 0, current_edge
= out_edges
[0];
1397 int num_bbs
, num_insns
, unreachable
;
1398 int too_large_failure
;
1400 /* Note if an edge has been passed. */
1403 /* Note if a block is a natural loop header. */
1406 /* Note if a block is an natural inner loop header. */
1409 /* Note if a block is in the block queue. */
1412 /* Note if a block is in the block queue. */
1415 int num_edges
= NUM_EDGES (edge_list
);
1417 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops
1418 and a mapping from block to its loop header (if the block is contained
1419 in a loop, else -1).
1421 Store results in HEADER, INNER, and MAX_HDR respectively, these will
1422 be used as inputs to the second traversal.
1424 STACK, SP and DFS_NR are only used during the first traversal. */
1426 /* Allocate and initialize variables for the first traversal. */
1427 max_hdr
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1428 dfs_nr
= (int *) xcalloc (n_basic_blocks
, sizeof (int));
1429 stack
= (int *) xmalloc (nr_edges
* sizeof (int));
1431 inner
= sbitmap_alloc (n_basic_blocks
);
1432 sbitmap_ones (inner
);
1434 header
= sbitmap_alloc (n_basic_blocks
);
1435 sbitmap_zero (header
);
1437 passed
= sbitmap_alloc (nr_edges
);
1438 sbitmap_zero (passed
);
1440 in_queue
= sbitmap_alloc (n_basic_blocks
);
1441 sbitmap_zero (in_queue
);
1443 in_stack
= sbitmap_alloc (n_basic_blocks
);
1444 sbitmap_zero (in_stack
);
1446 for (i
= 0; i
< n_basic_blocks
; i
++)
1449 /* DFS traversal to find inner loops in the cfg. */
1454 if (current_edge
== 0 || TEST_BIT (passed
, current_edge
))
1456 /* We have reached a leaf node or a node that was already
1457 processed. Pop edges off the stack until we find
1458 an edge that has not yet been processed. */
1460 && (current_edge
== 0 || TEST_BIT (passed
, current_edge
)))
1462 /* Pop entry off the stack. */
1463 current_edge
= stack
[sp
--];
1464 node
= FROM_BLOCK (current_edge
);
1465 child
= TO_BLOCK (current_edge
);
1466 RESET_BIT (in_stack
, child
);
1467 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1468 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1469 current_edge
= NEXT_OUT (current_edge
);
1472 /* See if have finished the DFS tree traversal. */
1473 if (sp
< 0 && TEST_BIT (passed
, current_edge
))
1476 /* Nope, continue the traversal with the popped node. */
1480 /* Process a node. */
1481 node
= FROM_BLOCK (current_edge
);
1482 child
= TO_BLOCK (current_edge
);
1483 SET_BIT (in_stack
, node
);
1484 dfs_nr
[node
] = ++count
;
1486 /* If the successor is in the stack, then we've found a loop.
1487 Mark the loop, if it is not a natural loop, then it will
1488 be rejected during the second traversal. */
1489 if (TEST_BIT (in_stack
, child
))
1492 SET_BIT (header
, child
);
1493 UPDATE_LOOP_RELATIONS (node
, child
);
1494 SET_BIT (passed
, current_edge
);
1495 current_edge
= NEXT_OUT (current_edge
);
1499 /* If the child was already visited, then there is no need to visit
1500 it again. Just update the loop relationships and restart
1504 if (max_hdr
[child
] >= 0 && TEST_BIT (in_stack
, max_hdr
[child
]))
1505 UPDATE_LOOP_RELATIONS (node
, max_hdr
[child
]);
1506 SET_BIT (passed
, current_edge
);
1507 current_edge
= NEXT_OUT (current_edge
);
1511 /* Push an entry on the stack and continue DFS traversal. */
1512 stack
[++sp
] = current_edge
;
1513 SET_BIT (passed
, current_edge
);
1514 current_edge
= OUT_EDGES (child
);
1516 /* This is temporary until haifa is converted to use rth's new
1517 cfg routines which have true entry/exit blocks and the
1518 appropriate edges from/to those blocks.
1520 Generally we update dfs_nr for a node when we process its
1521 out edge. However, if the node has no out edge then we will
1522 not set dfs_nr for that node. This can confuse the scheduler
1523 into thinking that we have unreachable blocks, which in turn
1524 disables cross block scheduling.
1526 So, if we have a node with no out edges, go ahead and mark it
1527 as reachable now. */
1528 if (current_edge
== 0)
1529 dfs_nr
[child
] = ++count
;
1532 /* Another check for unreachable blocks. The earlier test in
1533 is_cfg_nonregular only finds unreachable blocks that do not
1536 The DFS traversal will mark every block that is reachable from
1537 the entry node by placing a nonzero value in dfs_nr. Thus if
1538 dfs_nr is zero for any block, then it must be unreachable. */
1540 for (i
= 0; i
< n_basic_blocks
; i
++)
1547 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array
1548 to hold degree counts. */
1551 for (i
= 0; i
< num_edges
; i
++)
1553 edge e
= INDEX_EDGE (edge_list
, i
);
1555 if (e
->src
!= ENTRY_BLOCK_PTR
)
1556 degree
[e
->src
->index
]++;
1559 /* Do not perform region scheduling if there are any unreachable
1566 SET_BIT (header
, 0);
1568 /* Second travsersal:find reducible inner loops and topologically sort
1569 block of each region. */
1571 queue
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
1573 /* Find blocks which are inner loop headers. We still have non-reducible
1574 loops to consider at this point. */
1575 for (i
= 0; i
< n_basic_blocks
; i
++)
1577 if (TEST_BIT (header
, i
) && TEST_BIT (inner
, i
))
1582 /* Now check that the loop is reducible. We do this separate
1583 from finding inner loops so that we do not find a reducible
1584 loop which contains an inner non-reducible loop.
1586 A simple way to find reducible/natural loops is to verify
1587 that each block in the loop is dominated by the loop
1590 If there exists a block that is not dominated by the loop
1591 header, then the block is reachable from outside the loop
1592 and thus the loop is not a natural loop. */
1593 for (j
= 0; j
< n_basic_blocks
; j
++)
1595 /* First identify blocks in the loop, except for the loop
1597 if (i
== max_hdr
[j
] && i
!= j
)
1599 /* Now verify that the block is dominated by the loop
1601 if (!TEST_BIT (dom
[j
], i
))
1606 /* If we exited the loop early, then I is the header of
1607 a non-reducible loop and we should quit processing it
1609 if (j
!= n_basic_blocks
)
1612 /* I is a header of an inner loop, or block 0 in a subroutine
1613 with no loops at all. */
1615 too_large_failure
= 0;
1616 loop_head
= max_hdr
[i
];
1618 /* Decrease degree of all I's successors for topological
1620 for (e
= BASIC_BLOCK (i
)->succ
; e
; e
= e
->succ_next
)
1621 if (e
->dest
!= EXIT_BLOCK_PTR
)
1622 --degree
[e
->dest
->index
];
1624 /* Estimate # insns, and count # blocks in the region. */
1626 num_insns
= (INSN_LUID (BLOCK_END (i
))
1627 - INSN_LUID (BLOCK_HEAD (i
)));
1630 /* Find all loop latches (blocks with back edges to the loop
1631 header) or all the leaf blocks in the cfg has no loops.
1633 Place those blocks into the queue. */
1636 for (j
= 0; j
< n_basic_blocks
; j
++)
1637 /* Leaf nodes have only a single successor which must
1639 if (BASIC_BLOCK (j
)->succ
1640 && BASIC_BLOCK (j
)->succ
->dest
== EXIT_BLOCK_PTR
1641 && BASIC_BLOCK (j
)->succ
->succ_next
== NULL
)
1644 SET_BIT (in_queue
, j
);
1646 if (too_large (j
, &num_bbs
, &num_insns
))
1648 too_large_failure
= 1;
1657 for (e
= BASIC_BLOCK (i
)->pred
; e
; e
= e
->pred_next
)
1659 if (e
->src
== ENTRY_BLOCK_PTR
)
1662 node
= e
->src
->index
;
1664 if (max_hdr
[node
] == loop_head
&& node
!= i
)
1666 /* This is a loop latch. */
1667 queue
[++tail
] = node
;
1668 SET_BIT (in_queue
, node
);
1670 if (too_large (node
, &num_bbs
, &num_insns
))
1672 too_large_failure
= 1;
1680 /* Now add all the blocks in the loop to the queue.
1682 We know the loop is a natural loop; however the algorithm
1683 above will not always mark certain blocks as being in the
1692 The algorithm in the DFS traversal may not mark B & D as part
1693 of the loop (ie they will not have max_hdr set to A).
1695 We know they can not be loop latches (else they would have
1696 had max_hdr set since they'd have a backedge to a dominator
1697 block). So we don't need them on the initial queue.
1699 We know they are part of the loop because they are dominated
1700 by the loop header and can be reached by a backwards walk of
1701 the edges starting with nodes on the initial queue.
1703 It is safe and desirable to include those nodes in the
1704 loop/scheduling region. To do so we would need to decrease
1705 the degree of a node if it is the target of a backedge
1706 within the loop itself as the node is placed in the queue.
1708 We do not do this because I'm not sure that the actual
1709 scheduling code will properly handle this case. ?!? */
1711 while (head
< tail
&& !too_large_failure
)
1714 child
= queue
[++head
];
1716 for (e
= BASIC_BLOCK (child
)->pred
; e
; e
= e
->pred_next
)
1718 node
= e
->src
->index
;
1720 /* See discussion above about nodes not marked as in
1721 this loop during the initial DFS traversal. */
1722 if (e
->src
== ENTRY_BLOCK_PTR
1723 || max_hdr
[node
] != loop_head
)
1728 else if (!TEST_BIT (in_queue
, node
) && node
!= i
)
1730 queue
[++tail
] = node
;
1731 SET_BIT (in_queue
, node
);
1733 if (too_large (node
, &num_bbs
, &num_insns
))
1735 too_large_failure
= 1;
1742 if (tail
>= 0 && !too_large_failure
)
1744 /* Place the loop header into list of region blocks. */
1746 rgn_bb_table
[idx
] = i
;
1747 RGN_NR_BLOCKS (nr_regions
) = num_bbs
;
1748 RGN_BLOCKS (nr_regions
) = idx
++;
1749 CONTAINING_RGN (i
) = nr_regions
;
1750 BLOCK_TO_BB (i
) = count
= 0;
1752 /* Remove blocks from queue[] when their in degree
1753 becomes zero. Repeat until no blocks are left on the
1754 list. This produces a topological list of blocks in
1760 child
= queue
[head
];
1761 if (degree
[child
] == 0)
1766 rgn_bb_table
[idx
++] = child
;
1767 BLOCK_TO_BB (child
) = ++count
;
1768 CONTAINING_RGN (child
) = nr_regions
;
1769 queue
[head
] = queue
[tail
--];
1771 for (e
= BASIC_BLOCK (child
)->succ
;
1774 if (e
->dest
!= EXIT_BLOCK_PTR
)
1775 --degree
[e
->dest
->index
];
1787 /* Any block that did not end up in a region is placed into a region
1789 for (i
= 0; i
< n_basic_blocks
; i
++)
1792 rgn_bb_table
[idx
] = i
;
1793 RGN_NR_BLOCKS (nr_regions
) = 1;
1794 RGN_BLOCKS (nr_regions
) = idx
++;
1795 CONTAINING_RGN (i
) = nr_regions
++;
1796 BLOCK_TO_BB (i
) = 0;
1810 /* Functions for regions scheduling information. */
1812 /* Compute dominators, probability, and potential-split-edges of bb.
1813 Assume that these values were already computed for bb's predecessors. */
1816 compute_dom_prob_ps (bb
)
1819 int nxt_in_edge
, fst_in_edge
, pred
;
1820 int fst_out_edge
, nxt_out_edge
, nr_out_edges
, nr_rgn_out_edges
;
1823 if (IS_RGN_ENTRY (bb
))
1825 BITSET_ADD (dom
[bb
], 0, bbset_size
);
1830 fst_in_edge
= nxt_in_edge
= IN_EDGES (BB_TO_BLOCK (bb
));
1832 /* Intialize dom[bb] to '111..1'. */
1833 BITSET_INVERT (dom
[bb
], bbset_size
);
1837 pred
= FROM_BLOCK (nxt_in_edge
);
1838 BITSET_INTER (dom
[bb
], dom
[BLOCK_TO_BB (pred
)], bbset_size
);
1840 BITSET_UNION (ancestor_edges
[bb
], ancestor_edges
[BLOCK_TO_BB (pred
)],
1843 BITSET_ADD (ancestor_edges
[bb
], EDGE_TO_BIT (nxt_in_edge
), edgeset_size
);
1846 nr_rgn_out_edges
= 0;
1847 fst_out_edge
= OUT_EDGES (pred
);
1848 nxt_out_edge
= NEXT_OUT (fst_out_edge
);
1849 BITSET_UNION (pot_split
[bb
], pot_split
[BLOCK_TO_BB (pred
)],
1852 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (fst_out_edge
), edgeset_size
);
1854 /* The successor doesn't belong in the region? */
1855 if (CONTAINING_RGN (TO_BLOCK (fst_out_edge
)) !=
1856 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1859 while (fst_out_edge
!= nxt_out_edge
)
1862 /* The successor doesn't belong in the region? */
1863 if (CONTAINING_RGN (TO_BLOCK (nxt_out_edge
)) !=
1864 CONTAINING_RGN (BB_TO_BLOCK (bb
)))
1866 BITSET_ADD (pot_split
[bb
], EDGE_TO_BIT (nxt_out_edge
), edgeset_size
);
1867 nxt_out_edge
= NEXT_OUT (nxt_out_edge
);
1871 /* Now nr_rgn_out_edges is the number of region-exit edges from
1872 pred, and nr_out_edges will be the number of pred out edges
1873 not leaving the region. */
1874 nr_out_edges
-= nr_rgn_out_edges
;
1875 if (nr_rgn_out_edges
> 0)
1876 prob
[bb
] += 0.9 * prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1878 prob
[bb
] += prob
[BLOCK_TO_BB (pred
)] / nr_out_edges
;
1879 nxt_in_edge
= NEXT_IN (nxt_in_edge
);
1881 while (fst_in_edge
!= nxt_in_edge
);
1883 BITSET_ADD (dom
[bb
], bb
, bbset_size
);
1884 BITSET_DIFFER (pot_split
[bb
], ancestor_edges
[bb
], edgeset_size
);
1886 if (sched_verbose
>= 2)
1887 fprintf (dump
, ";; bb_prob(%d, %d) = %3d\n", bb
, BB_TO_BLOCK (bb
), (int) (100.0 * prob
[bb
]));
1888 } /* compute_dom_prob_ps */
1890 /* Functions for target info. */
1892 /* Compute in BL the list of split-edges of bb_src relatively to bb_trg.
1893 Note that bb_trg dominates bb_src. */
1896 split_edges (bb_src
, bb_trg
, bl
)
1901 int es
= edgeset_size
;
1902 edgeset src
= (edgeset
) xmalloc (es
* sizeof (HOST_WIDE_INT
));
1905 src
[es
] = (pot_split
[bb_src
])[es
];
1906 BITSET_DIFFER (src
, pot_split
[bb_trg
], edgeset_size
);
1907 extract_bitlst (src
, edgeset_size
, bl
);
1912 /* Find the valid candidate-source-blocks for the target block TRG, compute
1913 their probability, and check if they are speculative or not.
1914 For speculative sources, compute their update-blocks and split-blocks. */
1917 compute_trg_info (trg
)
1920 register candidate
*sp
;
1922 int check_block
, update_idx
;
1923 int i
, j
, k
, fst_edge
, nxt_edge
;
1925 /* Define some of the fields for the target bb as well. */
1926 sp
= candidate_table
+ trg
;
1928 sp
->is_speculative
= 0;
1931 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
1933 sp
= candidate_table
+ i
;
1935 sp
->is_valid
= IS_DOMINATED (i
, trg
);
1938 sp
->src_prob
= GET_SRC_PROB (i
, trg
);
1939 sp
->is_valid
= (sp
->src_prob
>= MIN_PROBABILITY
);
1944 split_edges (i
, trg
, &el
);
1945 sp
->is_speculative
= (el
.nr_members
) ? 1 : 0;
1946 if (sp
->is_speculative
&& !flag_schedule_speculative
)
1952 sp
->split_bbs
.first_member
= &bblst_table
[bblst_last
];
1953 sp
->split_bbs
.nr_members
= el
.nr_members
;
1954 for (j
= 0; j
< el
.nr_members
; bblst_last
++, j
++)
1955 bblst_table
[bblst_last
] =
1956 TO_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1957 sp
->update_bbs
.first_member
= &bblst_table
[bblst_last
];
1959 for (j
= 0; j
< el
.nr_members
; j
++)
1961 check_block
= FROM_BLOCK (rgn_edges
[el
.first_member
[j
]]);
1962 fst_edge
= nxt_edge
= OUT_EDGES (check_block
);
1965 for (k
= 0; k
< el
.nr_members
; k
++)
1966 if (EDGE_TO_BIT (nxt_edge
) == el
.first_member
[k
])
1969 if (k
>= el
.nr_members
)
1971 bblst_table
[bblst_last
++] = TO_BLOCK (nxt_edge
);
1975 nxt_edge
= NEXT_OUT (nxt_edge
);
1977 while (fst_edge
!= nxt_edge
);
1979 sp
->update_bbs
.nr_members
= update_idx
;
1984 sp
->split_bbs
.nr_members
= sp
->update_bbs
.nr_members
= 0;
1986 sp
->is_speculative
= 0;
1990 } /* compute_trg_info */
1993 /* Print candidates info, for debugging purposes. Callable from debugger. */
1999 if (!candidate_table
[i
].is_valid
)
2002 if (candidate_table
[i
].is_speculative
)
2005 fprintf (dump
, "src b %d bb %d speculative \n", BB_TO_BLOCK (i
), i
);
2007 fprintf (dump
, "split path: ");
2008 for (j
= 0; j
< candidate_table
[i
].split_bbs
.nr_members
; j
++)
2010 int b
= candidate_table
[i
].split_bbs
.first_member
[j
];
2012 fprintf (dump
, " %d ", b
);
2014 fprintf (dump
, "\n");
2016 fprintf (dump
, "update path: ");
2017 for (j
= 0; j
< candidate_table
[i
].update_bbs
.nr_members
; j
++)
2019 int b
= candidate_table
[i
].update_bbs
.first_member
[j
];
2021 fprintf (dump
, " %d ", b
);
2023 fprintf (dump
, "\n");
2027 fprintf (dump
, " src %d equivalent\n", BB_TO_BLOCK (i
));
2032 /* Print candidates info, for debugging purposes. Callable from debugger. */
2035 debug_candidates (trg
)
2040 fprintf (dump
, "----------- candidate table: target: b=%d bb=%d ---\n",
2041 BB_TO_BLOCK (trg
), trg
);
2042 for (i
= trg
+ 1; i
< current_nr_blocks
; i
++)
2043 debug_candidate (i
);
2047 /* Functions for speculative scheduing. */
2049 /* Return 0 if x is a set of a register alive in the beginning of one
2050 of the split-blocks of src, otherwise return 1. */
2053 check_live_1 (src
, x
)
2059 register rtx reg
= SET_DEST (x
);
2064 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2065 || GET_CODE (reg
) == SIGN_EXTRACT
2066 || GET_CODE (reg
) == STRICT_LOW_PART
)
2067 reg
= XEXP (reg
, 0);
2069 if (GET_CODE (reg
) == PARALLEL
2070 && GET_MODE (reg
) == BLKmode
)
2073 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2074 if (check_live_1 (src
, XVECEXP (reg
, 0, i
)))
2079 if (GET_CODE (reg
) != REG
)
2082 regno
= REGNO (reg
);
2084 if (regno
< FIRST_PSEUDO_REGISTER
&& global_regs
[regno
])
2086 /* Global registers are assumed live. */
2091 if (regno
< FIRST_PSEUDO_REGISTER
)
2093 /* Check for hard registers. */
2094 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
2097 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2099 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2101 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
2111 /* Check for psuedo registers. */
2112 for (i
= 0; i
< candidate_table
[src
].split_bbs
.nr_members
; i
++)
2114 int b
= candidate_table
[src
].split_bbs
.first_member
[i
];
2116 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, regno
))
2128 /* If x is a set of a register R, mark that R is alive in the beginning
2129 of every update-block of src. */
2132 update_live_1 (src
, x
)
2138 register rtx reg
= SET_DEST (x
);
2143 while (GET_CODE (reg
) == SUBREG
|| GET_CODE (reg
) == ZERO_EXTRACT
2144 || GET_CODE (reg
) == SIGN_EXTRACT
2145 || GET_CODE (reg
) == STRICT_LOW_PART
)
2146 reg
= XEXP (reg
, 0);
2148 if (GET_CODE (reg
) == PARALLEL
2149 && GET_MODE (reg
) == BLKmode
)
2152 for (i
= XVECLEN (reg
, 0) - 1; i
>= 0; i
--)
2153 update_live_1 (src
, XVECEXP (reg
, 0, i
));
2157 if (GET_CODE (reg
) != REG
)
2160 /* Global registers are always live, so the code below does not apply
2163 regno
= REGNO (reg
);
2165 if (regno
>= FIRST_PSEUDO_REGISTER
|| !global_regs
[regno
])
2167 if (regno
< FIRST_PSEUDO_REGISTER
)
2169 int j
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
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
,
2183 for (i
= 0; i
< candidate_table
[src
].update_bbs
.nr_members
; i
++)
2185 int b
= candidate_table
[src
].update_bbs
.first_member
[i
];
2187 SET_REGNO_REG_SET (BASIC_BLOCK (b
)->global_live_at_start
, regno
);
2194 /* Return 1 if insn can be speculatively moved from block src to trg,
2195 otherwise return 0. Called before first insertion of insn to
2196 ready-list or before the scheduling. */
2199 check_live (insn
, src
)
2203 /* Find the registers set by instruction. */
2204 if (GET_CODE (PATTERN (insn
)) == SET
2205 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2206 return check_live_1 (src
, PATTERN (insn
));
2207 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2210 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2211 if ((GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2212 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2213 && !check_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
)))
2223 /* Update the live registers info after insn was moved speculatively from
2224 block src to trg. */
2227 update_live (insn
, src
)
2231 /* Find the registers set by instruction. */
2232 if (GET_CODE (PATTERN (insn
)) == SET
2233 || GET_CODE (PATTERN (insn
)) == CLOBBER
)
2234 update_live_1 (src
, PATTERN (insn
));
2235 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2238 for (j
= XVECLEN (PATTERN (insn
), 0) - 1; j
>= 0; j
--)
2239 if (GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == SET
2240 || GET_CODE (XVECEXP (PATTERN (insn
), 0, j
)) == CLOBBER
)
2241 update_live_1 (src
, XVECEXP (PATTERN (insn
), 0, j
));
2245 /* Exception Free Loads:
2247 We define five classes of speculative loads: IFREE, IRISKY,
2248 PFREE, PRISKY, and MFREE.
2250 IFREE loads are loads that are proved to be exception-free, just
2251 by examining the load insn. Examples for such loads are loads
2252 from TOC and loads of global data.
2254 IRISKY loads are loads that are proved to be exception-risky,
2255 just by examining the load insn. Examples for such loads are
2256 volatile loads and loads from shared memory.
2258 PFREE loads are loads for which we can prove, by examining other
2259 insns, that they are exception-free. Currently, this class consists
2260 of loads for which we are able to find a "similar load", either in
2261 the target block, or, if only one split-block exists, in that split
2262 block. Load2 is similar to load1 if both have same single base
2263 register. We identify only part of the similar loads, by finding
2264 an insn upon which both load1 and load2 have a DEF-USE dependence.
2266 PRISKY loads are loads for which we can prove, by examining other
2267 insns, that they are exception-risky. Currently we have two proofs for
2268 such loads. The first proof detects loads that are probably guarded by a
2269 test on the memory address. This proof is based on the
2270 backward and forward data dependence information for the region.
2271 Let load-insn be the examined load.
2272 Load-insn is PRISKY iff ALL the following hold:
2274 - insn1 is not in the same block as load-insn
2275 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
2276 - test-insn is either a compare or a branch, not in the same block
2278 - load-insn is reachable from test-insn
2279 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
2281 This proof might fail when the compare and the load are fed
2282 by an insn not in the region. To solve this, we will add to this
2283 group all loads that have no input DEF-USE dependence.
2285 The second proof detects loads that are directly or indirectly
2286 fed by a speculative load. This proof is affected by the
2287 scheduling process. We will use the flag fed_by_spec_load.
2288 Initially, all insns have this flag reset. After a speculative
2289 motion of an insn, if insn is either a load, or marked as
2290 fed_by_spec_load, we will also mark as fed_by_spec_load every
2291 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
2292 load which is fed_by_spec_load is also PRISKY.
2294 MFREE (maybe-free) loads are all the remaining loads. They may be
2295 exception-free, but we cannot prove it.
2297 Now, all loads in IFREE and PFREE classes are considered
2298 exception-free, while all loads in IRISKY and PRISKY classes are
2299 considered exception-risky. As for loads in the MFREE class,
2300 these are considered either exception-free or exception-risky,
2301 depending on whether we are pessimistic or optimistic. We have
2302 to take the pessimistic approach to assure the safety of
2303 speculative scheduling, but we can take the optimistic approach
2304 by invoking the -fsched_spec_load_dangerous option. */
2306 enum INSN_TRAP_CLASS
2308 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
2309 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
2312 #define WORST_CLASS(class1, class2) \
2313 ((class1 > class2) ? class1 : class2)
2315 /* Non-zero if block bb_to is equal to, or reachable from block bb_from. */
2316 #define IS_REACHABLE(bb_from, bb_to) \
2318 || IS_RGN_ENTRY (bb_from) \
2319 || (bitset_member (ancestor_edges[bb_to], \
2320 EDGE_TO_BIT (IN_EDGES (BB_TO_BLOCK (bb_from))), \
2323 /* Non-zero iff the address is comprised from at most 1 register. */
2324 #define CONST_BASED_ADDRESS_P(x) \
2325 (GET_CODE (x) == REG \
2326 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
2327 || (GET_CODE (x) == LO_SUM)) \
2328 && (GET_CODE (XEXP (x, 0)) == CONST_INT \
2329 || GET_CODE (XEXP (x, 1)) == CONST_INT)))
2331 /* Turns on the fed_by_spec_load flag for insns fed by load_insn. */
2334 set_spec_fed (load_insn
)
2339 for (link
= INSN_DEPEND (load_insn
); link
; link
= XEXP (link
, 1))
2340 if (GET_MODE (link
) == VOIDmode
)
2341 FED_BY_SPEC_LOAD (XEXP (link
, 0)) = 1;
2342 } /* set_spec_fed */
2344 /* On the path from the insn to load_insn_bb, find a conditional
2345 branch depending on insn, that guards the speculative load. */
2348 find_conditional_protection (insn
, load_insn_bb
)
2354 /* Iterate through DEF-USE forward dependences. */
2355 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
2357 rtx next
= XEXP (link
, 0);
2358 if ((CONTAINING_RGN (BLOCK_NUM (next
)) ==
2359 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb
)))
2360 && IS_REACHABLE (INSN_BB (next
), load_insn_bb
)
2361 && load_insn_bb
!= INSN_BB (next
)
2362 && GET_MODE (link
) == VOIDmode
2363 && (GET_CODE (next
) == JUMP_INSN
2364 || find_conditional_protection (next
, load_insn_bb
)))
2368 } /* find_conditional_protection */
2370 /* Returns 1 if the same insn1 that participates in the computation
2371 of load_insn's address is feeding a conditional branch that is
2372 guarding on load_insn. This is true if we find a the two DEF-USE
2374 insn1 -> ... -> conditional-branch
2375 insn1 -> ... -> load_insn,
2376 and if a flow path exist:
2377 insn1 -> ... -> conditional-branch -> ... -> load_insn,
2378 and if insn1 is on the path
2379 region-entry -> ... -> bb_trg -> ... load_insn.
2381 Locate insn1 by climbing on LOG_LINKS from load_insn.
2382 Locate the branch by following INSN_DEPEND from insn1. */
2385 is_conditionally_protected (load_insn
, bb_src
, bb_trg
)
2391 for (link
= LOG_LINKS (load_insn
); link
; link
= XEXP (link
, 1))
2393 rtx insn1
= XEXP (link
, 0);
2395 /* Must be a DEF-USE dependence upon non-branch. */
2396 if (GET_MODE (link
) != VOIDmode
2397 || GET_CODE (insn1
) == JUMP_INSN
)
2400 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */
2401 if (INSN_BB (insn1
) == bb_src
2402 || (CONTAINING_RGN (BLOCK_NUM (insn1
))
2403 != CONTAINING_RGN (BB_TO_BLOCK (bb_src
)))
2404 || (!IS_REACHABLE (bb_trg
, INSN_BB (insn1
))
2405 && !IS_REACHABLE (INSN_BB (insn1
), bb_trg
)))
2408 /* Now search for the conditional-branch. */
2409 if (find_conditional_protection (insn1
, bb_src
))
2412 /* Recursive step: search another insn1, "above" current insn1. */
2413 return is_conditionally_protected (insn1
, bb_src
, bb_trg
);
2416 /* The chain does not exist. */
2418 } /* is_conditionally_protected */
2420 /* Returns 1 if a clue for "similar load" 'insn2' is found, and hence
2421 load_insn can move speculatively from bb_src to bb_trg. All the
2422 following must hold:
2424 (1) both loads have 1 base register (PFREE_CANDIDATEs).
2425 (2) load_insn and load1 have a def-use dependence upon
2426 the same insn 'insn1'.
2427 (3) either load2 is in bb_trg, or:
2428 - there's only one split-block, and
2429 - load1 is on the escape path, and
2431 From all these we can conclude that the two loads access memory
2432 addresses that differ at most by a constant, and hence if moving
2433 load_insn would cause an exception, it would have been caused by
2437 is_pfree (load_insn
, bb_src
, bb_trg
)
2442 register candidate
*candp
= candidate_table
+ bb_src
;
2444 if (candp
->split_bbs
.nr_members
!= 1)
2445 /* Must have exactly one escape block. */
2448 for (back_link
= LOG_LINKS (load_insn
);
2449 back_link
; back_link
= XEXP (back_link
, 1))
2451 rtx insn1
= XEXP (back_link
, 0);
2453 if (GET_MODE (back_link
) == VOIDmode
)
2455 /* Found a DEF-USE dependence (insn1, load_insn). */
2458 for (fore_link
= INSN_DEPEND (insn1
);
2459 fore_link
; fore_link
= XEXP (fore_link
, 1))
2461 rtx insn2
= XEXP (fore_link
, 0);
2462 if (GET_MODE (fore_link
) == VOIDmode
)
2464 /* Found a DEF-USE dependence (insn1, insn2). */
2465 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
2466 /* insn2 not guaranteed to be a 1 base reg load. */
2469 if (INSN_BB (insn2
) == bb_trg
)
2470 /* insn2 is the similar load, in the target block. */
2473 if (*(candp
->split_bbs
.first_member
) == BLOCK_NUM (insn2
))
2474 /* insn2 is a similar load, in a split-block. */
2481 /* Couldn't find a similar load. */
2485 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
2486 as found by analyzing insn's expression. */
2489 may_trap_exp (x
, is_store
)
2497 code
= GET_CODE (x
);
2507 /* The insn uses memory: a volatile load. */
2508 if (MEM_VOLATILE_P (x
))
2510 /* An exception-free load. */
2511 if (!may_trap_p (x
))
2513 /* A load with 1 base register, to be further checked. */
2514 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
2515 return PFREE_CANDIDATE
;
2516 /* No info on the load, to be further checked. */
2517 return PRISKY_CANDIDATE
;
2522 int i
, insn_class
= TRAP_FREE
;
2524 /* Neither store nor load, check if it may cause a trap. */
2527 /* Recursive step: walk the insn... */
2528 fmt
= GET_RTX_FORMAT (code
);
2529 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2533 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
2534 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2536 else if (fmt
[i
] == 'E')
2539 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2541 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
2542 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2543 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2547 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2552 } /* may_trap_exp */
2555 /* Classifies insn for the purpose of verifying that it can be
2556 moved speculatively, by examining it's patterns, returning:
2557 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
2558 TRAP_FREE: non-load insn.
2559 IFREE: load from a globaly safe location.
2560 IRISKY: volatile load.
2561 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
2562 being either PFREE or PRISKY. */
2565 haifa_classify_insn (insn
)
2568 rtx pat
= PATTERN (insn
);
2569 int tmp_class
= TRAP_FREE
;
2570 int insn_class
= TRAP_FREE
;
2573 if (GET_CODE (pat
) == PARALLEL
)
2575 int i
, len
= XVECLEN (pat
, 0);
2577 for (i
= len
- 1; i
>= 0; i
--)
2579 code
= GET_CODE (XVECEXP (pat
, 0, i
));
2583 /* Test if it is a 'store'. */
2584 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
2587 /* Test if it is a store. */
2588 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
2589 if (tmp_class
== TRAP_RISKY
)
2591 /* Test if it is a load. */
2593 WORST_CLASS (tmp_class
,
2594 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)), 0));
2597 tmp_class
= TRAP_RISKY
;
2601 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
2602 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
2608 code
= GET_CODE (pat
);
2612 /* Test if it is a 'store'. */
2613 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
2616 /* Test if it is a store. */
2617 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
2618 if (tmp_class
== TRAP_RISKY
)
2620 /* Test if it is a load. */
2622 WORST_CLASS (tmp_class
,
2623 may_trap_exp (SET_SRC (pat
), 0));
2626 tmp_class
= TRAP_RISKY
;
2630 insn_class
= tmp_class
;
2635 } /* haifa_classify_insn */
2637 /* Return 1 if load_insn is prisky (i.e. if load_insn is fed by
2638 a load moved speculatively, or if load_insn is protected by
2639 a compare on load_insn's address). */
2642 is_prisky (load_insn
, bb_src
, bb_trg
)
2646 if (FED_BY_SPEC_LOAD (load_insn
))
2649 if (LOG_LINKS (load_insn
) == NULL
)
2650 /* Dependence may 'hide' out of the region. */
2653 if (is_conditionally_protected (load_insn
, bb_src
, bb_trg
))
2659 /* Insn is a candidate to be moved speculatively from bb_src to bb_trg.
2660 Return 1 if insn is exception-free (and the motion is valid)
2664 is_exception_free (insn
, bb_src
, bb_trg
)
2668 int insn_class
= haifa_classify_insn (insn
);
2670 /* Handle non-load insns. */
2681 if (!flag_schedule_speculative_load
)
2683 IS_LOAD_INSN (insn
) = 1;
2690 case PFREE_CANDIDATE
:
2691 if (is_pfree (insn
, bb_src
, bb_trg
))
2693 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */
2694 case PRISKY_CANDIDATE
:
2695 if (!flag_schedule_speculative_load_dangerous
2696 || is_prisky (insn
, bb_src
, bb_trg
))
2702 return flag_schedule_speculative_load_dangerous
;
2703 } /* is_exception_free */
2706 /* Process an insn's memory dependencies. There are four kinds of
2709 (0) read dependence: read follows read
2710 (1) true dependence: read follows write
2711 (2) anti dependence: write follows read
2712 (3) output dependence: write follows write
2714 We are careful to build only dependencies which actually exist, and
2715 use transitivity to avoid building too many links. */
2717 /* Return the INSN_LIST containing INSN in LIST, or NULL
2718 if LIST does not contain INSN. */
2720 HAIFA_INLINE
static rtx
2721 find_insn_list (insn
, list
)
2727 if (XEXP (list
, 0) == insn
)
2729 list
= XEXP (list
, 1);
2735 /* Return 1 if the pair (insn, x) is found in (LIST, LIST1), or 0
2738 HAIFA_INLINE
static char
2739 find_insn_mem_list (insn
, x
, list
, list1
)
2745 if (XEXP (list
, 0) == insn
2746 && XEXP (list1
, 0) == x
)
2748 list
= XEXP (list
, 1);
2749 list1
= XEXP (list1
, 1);
2755 /* Compute the function units used by INSN. This caches the value
2756 returned by function_units_used. A function unit is encoded as the
2757 unit number if the value is non-negative and the compliment of a
2758 mask if the value is negative. A function unit index is the
2759 non-negative encoding. */
2761 HAIFA_INLINE
static int
2765 register int unit
= INSN_UNIT (insn
);
2769 recog_memoized (insn
);
2771 /* A USE insn, or something else we don't need to understand.
2772 We can't pass these directly to function_units_used because it will
2773 trigger a fatal error for unrecognizable insns. */
2774 if (INSN_CODE (insn
) < 0)
2778 unit
= function_units_used (insn
);
2779 /* Increment non-negative values so we can cache zero. */
2783 /* We only cache 16 bits of the result, so if the value is out of
2784 range, don't cache it. */
2785 if (FUNCTION_UNITS_SIZE
< HOST_BITS_PER_SHORT
2787 || (unit
& ~((1 << (HOST_BITS_PER_SHORT
- 1)) - 1)) == 0)
2788 INSN_UNIT (insn
) = unit
;
2790 return (unit
> 0 ? unit
- 1 : unit
);
2793 /* Compute the blockage range for executing INSN on UNIT. This caches
2794 the value returned by the blockage_range_function for the unit.
2795 These values are encoded in an int where the upper half gives the
2796 minimum value and the lower half gives the maximum value. */
2798 HAIFA_INLINE
static unsigned int
2799 blockage_range (unit
, insn
)
2803 unsigned int blockage
= INSN_BLOCKAGE (insn
);
2806 if ((int) UNIT_BLOCKED (blockage
) != unit
+ 1)
2808 range
= function_units
[unit
].blockage_range_function (insn
);
2809 /* We only cache the blockage range for one unit and then only if
2811 if (HOST_BITS_PER_INT
>= UNIT_BITS
+ 2 * BLOCKAGE_BITS
)
2812 INSN_BLOCKAGE (insn
) = ENCODE_BLOCKAGE (unit
+ 1, range
);
2815 range
= BLOCKAGE_RANGE (blockage
);
2820 /* A vector indexed by function unit instance giving the last insn to use
2821 the unit. The value of the function unit instance index for unit U
2822 instance I is (U + I * FUNCTION_UNITS_SIZE). */
2823 static rtx unit_last_insn
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2825 /* A vector indexed by function unit instance giving the minimum time when
2826 the unit will unblock based on the maximum blockage cost. */
2827 static int unit_tick
[FUNCTION_UNITS_SIZE
* MAX_MULTIPLICITY
];
2829 /* A vector indexed by function unit number giving the number of insns
2830 that remain to use the unit. */
2831 static int unit_n_insns
[FUNCTION_UNITS_SIZE
];
2833 /* Reset the function unit state to the null state. */
2838 bzero ((char *) unit_last_insn
, sizeof (unit_last_insn
));
2839 bzero ((char *) unit_tick
, sizeof (unit_tick
));
2840 bzero ((char *) unit_n_insns
, sizeof (unit_n_insns
));
2843 /* Return the issue-delay of an insn. */
2845 HAIFA_INLINE
static int
2846 insn_issue_delay (insn
)
2850 int unit
= insn_unit (insn
);
2852 /* Efficiency note: in fact, we are working 'hard' to compute a
2853 value that was available in md file, and is not available in
2854 function_units[] structure. It would be nice to have this
2855 value there, too. */
2858 if (function_units
[unit
].blockage_range_function
&&
2859 function_units
[unit
].blockage_function
)
2860 delay
= function_units
[unit
].blockage_function (insn
, insn
);
2863 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2864 if ((unit
& 1) != 0 && function_units
[i
].blockage_range_function
2865 && function_units
[i
].blockage_function
)
2866 delay
= MAX (delay
, function_units
[i
].blockage_function (insn
, insn
));
2871 /* Return the actual hazard cost of executing INSN on the unit UNIT,
2872 instance INSTANCE at time CLOCK if the previous actual hazard cost
2875 HAIFA_INLINE
static int
2876 actual_hazard_this_instance (unit
, instance
, insn
, clock
, cost
)
2877 int unit
, instance
, clock
, cost
;
2880 int tick
= unit_tick
[instance
]; /* Issue time of the last issued insn. */
2882 if (tick
- clock
> cost
)
2884 /* The scheduler is operating forward, so unit's last insn is the
2885 executing insn and INSN is the candidate insn. We want a
2886 more exact measure of the blockage if we execute INSN at CLOCK
2887 given when we committed the execution of the unit's last insn.
2889 The blockage value is given by either the unit's max blockage
2890 constant, blockage range function, or blockage function. Use
2891 the most exact form for the given unit. */
2893 if (function_units
[unit
].blockage_range_function
)
2895 if (function_units
[unit
].blockage_function
)
2896 tick
+= (function_units
[unit
].blockage_function
2897 (unit_last_insn
[instance
], insn
)
2898 - function_units
[unit
].max_blockage
);
2900 tick
+= ((int) MAX_BLOCKAGE_COST (blockage_range (unit
, insn
))
2901 - function_units
[unit
].max_blockage
);
2903 if (tick
- clock
> cost
)
2904 cost
= tick
- clock
;
2909 /* Record INSN as having begun execution on the units encoded by UNIT at
2912 HAIFA_INLINE
static void
2913 schedule_unit (unit
, insn
, clock
)
2921 int instance
= unit
;
2922 #if MAX_MULTIPLICITY > 1
2923 /* Find the first free instance of the function unit and use that
2924 one. We assume that one is free. */
2925 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2927 if (!actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
2929 instance
+= FUNCTION_UNITS_SIZE
;
2932 unit_last_insn
[instance
] = insn
;
2933 unit_tick
[instance
] = (clock
+ function_units
[unit
].max_blockage
);
2936 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2937 if ((unit
& 1) != 0)
2938 schedule_unit (i
, insn
, clock
);
2941 /* Return the actual hazard cost of executing INSN on the units encoded by
2942 UNIT at time CLOCK if the previous actual hazard cost was COST. */
2944 HAIFA_INLINE
static int
2945 actual_hazard (unit
, insn
, clock
, cost
)
2946 int unit
, clock
, cost
;
2953 /* Find the instance of the function unit with the minimum hazard. */
2954 int instance
= unit
;
2955 int best_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2957 #if MAX_MULTIPLICITY > 1
2960 if (best_cost
> cost
)
2962 for (i
= function_units
[unit
].multiplicity
- 1; i
> 0; i
--)
2964 instance
+= FUNCTION_UNITS_SIZE
;
2965 this_cost
= actual_hazard_this_instance (unit
, instance
, insn
,
2967 if (this_cost
< best_cost
)
2969 best_cost
= this_cost
;
2970 if (this_cost
<= cost
)
2976 cost
= MAX (cost
, best_cost
);
2979 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
2980 if ((unit
& 1) != 0)
2981 cost
= actual_hazard (i
, insn
, clock
, cost
);
2986 /* Return the potential hazard cost of executing an instruction on the
2987 units encoded by UNIT if the previous potential hazard cost was COST.
2988 An insn with a large blockage time is chosen in preference to one
2989 with a smaller time; an insn that uses a unit that is more likely
2990 to be used is chosen in preference to one with a unit that is less
2991 used. We are trying to minimize a subsequent actual hazard. */
2993 HAIFA_INLINE
static int
2994 potential_hazard (unit
, insn
, cost
)
2999 unsigned int minb
, maxb
;
3003 minb
= maxb
= function_units
[unit
].max_blockage
;
3006 if (function_units
[unit
].blockage_range_function
)
3008 maxb
= minb
= blockage_range (unit
, insn
);
3009 maxb
= MAX_BLOCKAGE_COST (maxb
);
3010 minb
= MIN_BLOCKAGE_COST (minb
);
3015 /* Make the number of instructions left dominate. Make the
3016 minimum delay dominate the maximum delay. If all these
3017 are the same, use the unit number to add an arbitrary
3018 ordering. Other terms can be added. */
3019 ncost
= minb
* 0x40 + maxb
;
3020 ncost
*= (unit_n_insns
[unit
] - 1) * 0x1000 + unit
;
3027 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
3028 if ((unit
& 1) != 0)
3029 cost
= potential_hazard (i
, insn
, cost
);
3034 /* Compute cost of executing INSN given the dependence LINK on the insn USED.
3035 This is the number of cycles between instruction issue and
3036 instruction results. */
3038 HAIFA_INLINE
static int
3039 insn_cost (insn
, link
, used
)
3040 rtx insn
, link
, used
;
3042 register int cost
= INSN_COST (insn
);
3046 recog_memoized (insn
);
3048 /* A USE insn, or something else we don't need to understand.
3049 We can't pass these directly to result_ready_cost because it will
3050 trigger a fatal error for unrecognizable insns. */
3051 if (INSN_CODE (insn
) < 0)
3053 INSN_COST (insn
) = 1;
3058 cost
= result_ready_cost (insn
);
3063 INSN_COST (insn
) = cost
;
3067 /* In this case estimate cost without caring how insn is used. */
3068 if (link
== 0 && used
== 0)
3071 /* A USE insn should never require the value used to be computed. This
3072 allows the computation of a function's result and parameter values to
3073 overlap the return and call. */
3074 recog_memoized (used
);
3075 if (INSN_CODE (used
) < 0)
3076 LINK_COST_FREE (link
) = 1;
3078 /* If some dependencies vary the cost, compute the adjustment. Most
3079 commonly, the adjustment is complete: either the cost is ignored
3080 (in the case of an output- or anti-dependence), or the cost is
3081 unchanged. These values are cached in the link as LINK_COST_FREE
3082 and LINK_COST_ZERO. */
3084 if (LINK_COST_FREE (link
))
3087 else if (!LINK_COST_ZERO (link
))
3091 ADJUST_COST (used
, link
, insn
, ncost
);
3094 LINK_COST_FREE (link
) = 1;
3098 LINK_COST_ZERO (link
) = 1;
3105 /* Compute the priority number for INSN. */
3114 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
3117 if ((this_priority
= INSN_PRIORITY (insn
)) == 0)
3119 if (INSN_DEPEND (insn
) == 0)
3120 this_priority
= insn_cost (insn
, 0, 0);
3122 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
3127 if (RTX_INTEGRATED_P (link
))
3130 next
= XEXP (link
, 0);
3132 /* Critical path is meaningful in block boundaries only. */
3133 if (BLOCK_NUM (next
) != BLOCK_NUM (insn
))
3136 next_priority
= insn_cost (insn
, link
, next
) + priority (next
);
3137 if (next_priority
> this_priority
)
3138 this_priority
= next_priority
;
3140 INSN_PRIORITY (insn
) = this_priority
;
3142 return this_priority
;
3146 /* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
3147 them to the unused_*_list variables, so that they can be reused. */
3150 free_pending_lists ()
3152 if (current_nr_blocks
<= 1)
3154 free_INSN_LIST_list (&pending_read_insns
);
3155 free_INSN_LIST_list (&pending_write_insns
);
3156 free_EXPR_LIST_list (&pending_read_mems
);
3157 free_EXPR_LIST_list (&pending_write_mems
);
3161 /* Interblock scheduling. */
3164 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
3166 free_INSN_LIST_list (&bb_pending_read_insns
[bb
]);
3167 free_INSN_LIST_list (&bb_pending_write_insns
[bb
]);
3168 free_EXPR_LIST_list (&bb_pending_read_mems
[bb
]);
3169 free_EXPR_LIST_list (&bb_pending_write_mems
[bb
]);
3174 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
3175 The MEM is a memory reference contained within INSN, which we are saving
3176 so that we can do memory aliasing on it. */
3179 add_insn_mem_dependence (insn_list
, mem_list
, insn
, mem
)
3180 rtx
*insn_list
, *mem_list
, insn
, mem
;
3184 link
= alloc_INSN_LIST (insn
, *insn_list
);
3187 link
= alloc_EXPR_LIST (VOIDmode
, mem
, *mem_list
);
3190 pending_lists_length
++;
3194 /* Make a dependency between every memory reference on the pending lists
3195 and INSN, thus flushing the pending lists. If ONLY_WRITE, don't flush
3199 flush_pending_lists (insn
, only_write
)
3206 while (pending_read_insns
&& ! only_write
)
3208 add_dependence (insn
, XEXP (pending_read_insns
, 0), REG_DEP_ANTI
);
3210 link
= pending_read_insns
;
3211 pending_read_insns
= XEXP (pending_read_insns
, 1);
3212 free_INSN_LIST_node (link
);
3214 link
= pending_read_mems
;
3215 pending_read_mems
= XEXP (pending_read_mems
, 1);
3216 free_EXPR_LIST_node (link
);
3218 while (pending_write_insns
)
3220 add_dependence (insn
, XEXP (pending_write_insns
, 0), REG_DEP_ANTI
);
3222 link
= pending_write_insns
;
3223 pending_write_insns
= XEXP (pending_write_insns
, 1);
3224 free_INSN_LIST_node (link
);
3226 link
= pending_write_mems
;
3227 pending_write_mems
= XEXP (pending_write_mems
, 1);
3228 free_EXPR_LIST_node (link
);
3230 pending_lists_length
= 0;
3232 /* last_pending_memory_flush is now a list of insns. */
3233 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3234 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3236 free_INSN_LIST_list (&last_pending_memory_flush
);
3237 last_pending_memory_flush
= alloc_INSN_LIST (insn
, NULL_RTX
);
3240 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
3241 rtx, X, creating all dependencies generated by the write to the
3242 destination of X, and reads of everything mentioned. */
3245 sched_analyze_1 (x
, insn
)
3250 register rtx dest
= XEXP (x
, 0);
3251 enum rtx_code code
= GET_CODE (x
);
3256 if (GET_CODE (dest
) == PARALLEL
3257 && GET_MODE (dest
) == BLKmode
)
3260 for (i
= XVECLEN (dest
, 0) - 1; i
>= 0; i
--)
3261 sched_analyze_1 (XVECEXP (dest
, 0, i
), insn
);
3262 if (GET_CODE (x
) == SET
)
3263 sched_analyze_2 (SET_SRC (x
), insn
);
3267 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SUBREG
3268 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3270 if (GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SIGN_EXTRACT
)
3272 /* The second and third arguments are values read by this insn. */
3273 sched_analyze_2 (XEXP (dest
, 1), insn
);
3274 sched_analyze_2 (XEXP (dest
, 2), insn
);
3276 dest
= XEXP (dest
, 0);
3279 if (GET_CODE (dest
) == REG
)
3283 regno
= REGNO (dest
);
3285 /* A hard reg in a wide mode may really be multiple registers.
3286 If so, mark all of them just like the first. */
3287 if (regno
< FIRST_PSEUDO_REGISTER
)
3289 i
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
3294 for (u
= reg_last_uses
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3295 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3297 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3298 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3300 /* Clobbers need not be ordered with respect to one
3301 another, but sets must be ordered with respect to a
3305 free_INSN_LIST_list (®_last_uses
[regno
+ i
]);
3306 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3307 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3308 SET_REGNO_REG_SET (reg_pending_sets
, regno
+ i
);
3311 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
+ i
);
3313 /* Function calls clobber all call_used regs. */
3314 if (global_regs
[regno
+ i
]
3315 || (code
== SET
&& call_used_regs
[regno
+ i
]))
3316 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3317 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3324 for (u
= reg_last_uses
[regno
]; u
; u
= XEXP (u
, 1))
3325 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3327 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3328 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3332 free_INSN_LIST_list (®_last_uses
[regno
]);
3333 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3334 add_dependence (insn
, XEXP (u
, 0), REG_DEP_OUTPUT
);
3335 SET_REGNO_REG_SET (reg_pending_sets
, regno
);
3338 SET_REGNO_REG_SET (reg_pending_clobbers
, regno
);
3340 /* Pseudos that are REG_EQUIV to something may be replaced
3341 by that during reloading. We need only add dependencies for
3342 the address in the REG_EQUIV note. */
3343 if (!reload_completed
3344 && reg_known_equiv_p
[regno
]
3345 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3346 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3348 /* Don't let it cross a call after scheduling if it doesn't
3349 already cross one. */
3351 if (REG_N_CALLS_CROSSED (regno
) == 0)
3352 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3353 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3356 else if (GET_CODE (dest
) == MEM
)
3358 /* Writing memory. */
3360 if (pending_lists_length
> 32)
3362 /* Flush all pending reads and writes to prevent the pending lists
3363 from getting any larger. Insn scheduling runs too slowly when
3364 these lists get long. The number 32 was chosen because it
3365 seems like a reasonable number. When compiling GCC with itself,
3366 this flush occurs 8 times for sparc, and 10 times for m88k using
3368 flush_pending_lists (insn
, 0);
3373 rtx pending
, pending_mem
;
3375 pending
= pending_read_insns
;
3376 pending_mem
= pending_read_mems
;
3379 if (anti_dependence (XEXP (pending_mem
, 0), dest
))
3380 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3382 pending
= XEXP (pending
, 1);
3383 pending_mem
= XEXP (pending_mem
, 1);
3386 pending
= pending_write_insns
;
3387 pending_mem
= pending_write_mems
;
3390 if (output_dependence (XEXP (pending_mem
, 0), dest
))
3391 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_OUTPUT
);
3393 pending
= XEXP (pending
, 1);
3394 pending_mem
= XEXP (pending_mem
, 1);
3397 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3398 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3400 add_insn_mem_dependence (&pending_write_insns
, &pending_write_mems
,
3403 sched_analyze_2 (XEXP (dest
, 0), insn
);
3406 /* Analyze reads. */
3407 if (GET_CODE (x
) == SET
)
3408 sched_analyze_2 (SET_SRC (x
), insn
);
3411 /* Analyze the uses of memory and registers in rtx X in INSN. */
3414 sched_analyze_2 (x
, insn
)
3420 register enum rtx_code code
;
3421 register const char *fmt
;
3426 code
= GET_CODE (x
);
3435 /* Ignore constants. Note that we must handle CONST_DOUBLE here
3436 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
3437 this does not mean that this insn is using cc0. */
3445 /* User of CC0 depends on immediately preceding insn. */
3446 SCHED_GROUP_P (insn
) = 1;
3448 /* There may be a note before this insn now, but all notes will
3449 be removed before we actually try to schedule the insns, so
3450 it won't cause a problem later. We must avoid it here though. */
3451 prev
= prev_nonnote_insn (insn
);
3453 /* Make a copy of all dependencies on the immediately previous insn,
3454 and add to this insn. This is so that all the dependencies will
3455 apply to the group. Remove an explicit dependence on this insn
3456 as SCHED_GROUP_P now represents it. */
3458 if (find_insn_list (prev
, LOG_LINKS (insn
)))
3459 remove_dependence (insn
, prev
);
3461 for (link
= LOG_LINKS (prev
); link
; link
= XEXP (link
, 1))
3462 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3471 int regno
= REGNO (x
);
3472 if (regno
< FIRST_PSEUDO_REGISTER
)
3476 i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
3479 reg_last_uses
[regno
+ i
]
3480 = alloc_INSN_LIST (insn
, reg_last_uses
[regno
+ i
]);
3482 for (u
= reg_last_sets
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3483 add_dependence (insn
, XEXP (u
, 0), 0);
3485 /* ??? This should never happen. */
3486 for (u
= reg_last_clobbers
[regno
+ i
]; u
; u
= XEXP (u
, 1))
3487 add_dependence (insn
, XEXP (u
, 0), 0);
3489 if ((call_used_regs
[regno
+ i
] || global_regs
[regno
+ i
]))
3490 /* Function calls clobber all call_used regs. */
3491 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
3492 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3497 reg_last_uses
[regno
] = alloc_INSN_LIST (insn
,
3498 reg_last_uses
[regno
]);
3500 for (u
= reg_last_sets
[regno
]; u
; u
= XEXP (u
, 1))
3501 add_dependence (insn
, XEXP (u
, 0), 0);
3503 /* ??? This should never happen. */
3504 for (u
= reg_last_clobbers
[regno
]; u
; u
= XEXP (u
, 1))
3505 add_dependence (insn
, XEXP (u
, 0), 0);
3507 /* Pseudos that are REG_EQUIV to something may be replaced
3508 by that during reloading. We need only add dependencies for
3509 the address in the REG_EQUIV note. */
3510 if (!reload_completed
3511 && reg_known_equiv_p
[regno
]
3512 && GET_CODE (reg_known_value
[regno
]) == MEM
)
3513 sched_analyze_2 (XEXP (reg_known_value
[regno
], 0), insn
);
3515 /* If the register does not already cross any calls, then add this
3516 insn to the sched_before_next_call list so that it will still
3517 not cross calls after scheduling. */
3518 if (REG_N_CALLS_CROSSED (regno
) == 0)
3519 add_dependence (sched_before_next_call
, insn
, REG_DEP_ANTI
);
3526 /* Reading memory. */
3528 rtx pending
, pending_mem
;
3530 pending
= pending_read_insns
;
3531 pending_mem
= pending_read_mems
;
3534 if (read_dependence (XEXP (pending_mem
, 0), x
))
3535 add_dependence (insn
, XEXP (pending
, 0), REG_DEP_ANTI
);
3537 pending
= XEXP (pending
, 1);
3538 pending_mem
= XEXP (pending_mem
, 1);
3541 pending
= pending_write_insns
;
3542 pending_mem
= pending_write_mems
;
3545 if (true_dependence (XEXP (pending_mem
, 0), VOIDmode
,
3547 add_dependence (insn
, XEXP (pending
, 0), 0);
3549 pending
= XEXP (pending
, 1);
3550 pending_mem
= XEXP (pending_mem
, 1);
3553 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
3554 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3556 /* Always add these dependencies to pending_reads, since
3557 this insn may be followed by a write. */
3558 add_insn_mem_dependence (&pending_read_insns
, &pending_read_mems
,
3561 /* Take advantage of tail recursion here. */
3562 sched_analyze_2 (XEXP (x
, 0), insn
);
3566 /* Force pending stores to memory in case a trap handler needs them. */
3568 flush_pending_lists (insn
, 1);
3573 case UNSPEC_VOLATILE
:
3577 /* Traditional and volatile asm instructions must be considered to use
3578 and clobber all hard registers, all pseudo-registers and all of
3579 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
3581 Consider for instance a volatile asm that changes the fpu rounding
3582 mode. An insn should not be moved across this even if it only uses
3583 pseudo-regs because it might give an incorrectly rounded result. */
3584 if (code
!= ASM_OPERANDS
|| MEM_VOLATILE_P (x
))
3586 int max_reg
= max_reg_num ();
3587 for (i
= 0; i
< max_reg
; i
++)
3589 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3590 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3591 free_INSN_LIST_list (®_last_uses
[i
]);
3593 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3594 add_dependence (insn
, XEXP (u
, 0), 0);
3596 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3597 add_dependence (insn
, XEXP (u
, 0), 0);
3599 reg_pending_sets_all
= 1;
3601 flush_pending_lists (insn
, 0);
3604 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
3605 We can not just fall through here since then we would be confused
3606 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
3607 traditional asms unlike their normal usage. */
3609 if (code
== ASM_OPERANDS
)
3611 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3612 sched_analyze_2 (ASM_OPERANDS_INPUT (x
, j
), insn
);
3622 /* These both read and modify the result. We must handle them as writes
3623 to get proper dependencies for following instructions. We must handle
3624 them as reads to get proper dependencies from this to previous
3625 instructions. Thus we need to pass them to both sched_analyze_1
3626 and sched_analyze_2. We must call sched_analyze_2 first in order
3627 to get the proper antecedent for the read. */
3628 sched_analyze_2 (XEXP (x
, 0), insn
);
3629 sched_analyze_1 (x
, insn
);
3636 /* Other cases: walk the insn. */
3637 fmt
= GET_RTX_FORMAT (code
);
3638 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3641 sched_analyze_2 (XEXP (x
, i
), insn
);
3642 else if (fmt
[i
] == 'E')
3643 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3644 sched_analyze_2 (XVECEXP (x
, i
, j
), insn
);
3648 /* Analyze an INSN with pattern X to find all dependencies. */
3651 sched_analyze_insn (x
, insn
, loop_notes
)
3655 register RTX_CODE code
= GET_CODE (x
);
3657 int maxreg
= max_reg_num ();
3660 if (code
== SET
|| code
== CLOBBER
)
3661 sched_analyze_1 (x
, insn
);
3662 else if (code
== PARALLEL
)
3665 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
3667 code
= GET_CODE (XVECEXP (x
, 0, i
));
3668 if (code
== SET
|| code
== CLOBBER
)
3669 sched_analyze_1 (XVECEXP (x
, 0, i
), insn
);
3671 sched_analyze_2 (XVECEXP (x
, 0, i
), insn
);
3675 sched_analyze_2 (x
, insn
);
3677 /* Mark registers CLOBBERED or used by called function. */
3678 if (GET_CODE (insn
) == CALL_INSN
)
3679 for (link
= CALL_INSN_FUNCTION_USAGE (insn
); link
; link
= XEXP (link
, 1))
3681 if (GET_CODE (XEXP (link
, 0)) == CLOBBER
)
3682 sched_analyze_1 (XEXP (link
, 0), insn
);
3684 sched_analyze_2 (XEXP (link
, 0), insn
);
3687 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
3688 block, then we must be sure that no instructions are scheduled across it.
3689 Otherwise, the reg_n_refs info (which depends on loop_depth) would
3690 become incorrect. */
3694 int max_reg
= max_reg_num ();
3695 int schedule_barrier_found
= 0;
3698 /* Update loop_notes with any notes from this insn. Also determine
3699 if any of the notes on the list correspond to instruction scheduling
3700 barriers (loop, eh & setjmp notes, but not range notes. */
3702 while (XEXP (link
, 1))
3704 if (INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_BEG
3705 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_LOOP_END
3706 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_BEG
3707 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_EH_REGION_END
3708 || INTVAL (XEXP (link
, 0)) == NOTE_INSN_SETJMP
)
3709 schedule_barrier_found
= 1;
3711 link
= XEXP (link
, 1);
3713 XEXP (link
, 1) = REG_NOTES (insn
);
3714 REG_NOTES (insn
) = loop_notes
;
3716 /* Add dependencies if a scheduling barrier was found. */
3717 if (schedule_barrier_found
)
3719 for (i
= 0; i
< max_reg
; i
++)
3722 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3723 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3724 free_INSN_LIST_list (®_last_uses
[i
]);
3726 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3727 add_dependence (insn
, XEXP (u
, 0), 0);
3729 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3730 add_dependence (insn
, XEXP (u
, 0), 0);
3732 reg_pending_sets_all
= 1;
3734 flush_pending_lists (insn
, 0);
3739 /* Accumulate clobbers until the next set so that it will be output dependent
3740 on all of them. At the next set we can clear the clobber list, since
3741 subsequent sets will be output dependent on it. */
3742 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets
, 0, i
,
3744 free_INSN_LIST_list (®_last_sets
[i
]);
3745 free_INSN_LIST_list (®_last_clobbers
[i
]);
3747 = alloc_INSN_LIST (insn
, NULL_RTX
);
3749 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers
, 0, i
,
3751 reg_last_clobbers
[i
]
3752 = alloc_INSN_LIST (insn
,
3753 reg_last_clobbers
[i
]);
3755 CLEAR_REG_SET (reg_pending_sets
);
3756 CLEAR_REG_SET (reg_pending_clobbers
);
3758 if (reg_pending_sets_all
)
3760 for (i
= 0; i
< maxreg
; i
++)
3762 free_INSN_LIST_list (®_last_sets
[i
]);
3763 free_INSN_LIST_list (®_last_clobbers
[i
]);
3764 reg_last_sets
[i
] = alloc_INSN_LIST (insn
, NULL_RTX
);
3767 reg_pending_sets_all
= 0;
3770 /* Handle function calls and function returns created by the epilogue
3772 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3777 /* When scheduling instructions, we make sure calls don't lose their
3778 accompanying USE insns by depending them one on another in order.
3780 Also, we must do the same thing for returns created by the epilogue
3781 threading code. Note this code works only in this special case,
3782 because other passes make no guarantee that they will never emit
3783 an instruction between a USE and a RETURN. There is such a guarantee
3784 for USE instructions immediately before a call. */
3786 prev_dep_insn
= insn
;
3787 dep_insn
= PREV_INSN (insn
);
3788 while (GET_CODE (dep_insn
) == INSN
3789 && GET_CODE (PATTERN (dep_insn
)) == USE
3790 && GET_CODE (XEXP (PATTERN (dep_insn
), 0)) == REG
)
3792 SCHED_GROUP_P (prev_dep_insn
) = 1;
3794 /* Make a copy of all dependencies on dep_insn, and add to insn.
3795 This is so that all of the dependencies will apply to the
3798 for (link
= LOG_LINKS (dep_insn
); link
; link
= XEXP (link
, 1))
3799 add_dependence (insn
, XEXP (link
, 0), REG_NOTE_KIND (link
));
3801 prev_dep_insn
= dep_insn
;
3802 dep_insn
= PREV_INSN (dep_insn
);
3807 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
3808 for every dependency. */
3811 sched_analyze (head
, tail
)
3818 for (insn
= head
;; insn
= NEXT_INSN (insn
))
3820 if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == JUMP_INSN
)
3822 /* Clear out the stale LOG_LINKS from flow. */
3823 free_INSN_LIST_list (&LOG_LINKS (insn
));
3825 /* Make each JUMP_INSN a scheduling barrier for memory
3827 if (GET_CODE (insn
) == JUMP_INSN
)
3828 last_pending_memory_flush
3829 = alloc_INSN_LIST (insn
, last_pending_memory_flush
);
3830 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3833 else if (GET_CODE (insn
) == CALL_INSN
)
3838 CANT_MOVE (insn
) = 1;
3840 /* Clear out the stale LOG_LINKS from flow. */
3841 free_INSN_LIST_list (&LOG_LINKS (insn
));
3843 /* Any instruction using a hard register which may get clobbered
3844 by a call needs to be marked as dependent on this call.
3845 This prevents a use of a hard return reg from being moved
3846 past a void call (i.e. it does not explicitly set the hard
3849 /* If this call is followed by a NOTE_INSN_SETJMP, then assume that
3850 all registers, not just hard registers, may be clobbered by this
3853 /* Insn, being a CALL_INSN, magically depends on
3854 `last_function_call' already. */
3856 if (NEXT_INSN (insn
) && GET_CODE (NEXT_INSN (insn
)) == NOTE
3857 && NOTE_LINE_NUMBER (NEXT_INSN (insn
)) == NOTE_INSN_SETJMP
)
3859 int max_reg
= max_reg_num ();
3860 for (i
= 0; i
< max_reg
; i
++)
3862 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3863 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3864 free_INSN_LIST_list (®_last_uses
[i
]);
3866 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3867 add_dependence (insn
, XEXP (u
, 0), 0);
3869 for (u
= reg_last_clobbers
[i
]; u
; u
= XEXP (u
, 1))
3870 add_dependence (insn
, XEXP (u
, 0), 0);
3872 reg_pending_sets_all
= 1;
3874 /* Add a pair of REG_SAVE_NOTEs which we will later
3875 convert back into a NOTE_INSN_SETJMP note. See
3876 reemit_notes for why we use a pair of NOTEs. */
3877 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3880 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_SAVE_NOTE
,
3881 GEN_INT (NOTE_INSN_SETJMP
),
3886 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3887 if (call_used_regs
[i
] || global_regs
[i
])
3889 for (u
= reg_last_uses
[i
]; u
; u
= XEXP (u
, 1))
3890 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3892 for (u
= reg_last_sets
[i
]; u
; u
= XEXP (u
, 1))
3893 add_dependence (insn
, XEXP (u
, 0), REG_DEP_ANTI
);
3895 SET_REGNO_REG_SET (reg_pending_clobbers
, i
);
3899 /* For each insn which shouldn't cross a call, add a dependence
3900 between that insn and this call insn. */
3901 x
= LOG_LINKS (sched_before_next_call
);
3904 add_dependence (insn
, XEXP (x
, 0), REG_DEP_ANTI
);
3907 free_INSN_LIST_list (&LOG_LINKS (sched_before_next_call
));
3909 sched_analyze_insn (PATTERN (insn
), insn
, loop_notes
);
3912 /* In the absence of interprocedural alias analysis, we must flush
3913 all pending reads and writes, and start new dependencies starting
3914 from here. But only flush writes for constant calls (which may
3915 be passed a pointer to something we haven't written yet). */
3916 flush_pending_lists (insn
, CONST_CALL_P (insn
));
3918 /* Depend this function call (actually, the user of this
3919 function call) on all hard register clobberage. */
3921 /* last_function_call is now a list of insns. */
3922 free_INSN_LIST_list(&last_function_call
);
3923 last_function_call
= alloc_INSN_LIST (insn
, NULL_RTX
);
3926 /* See comments on reemit_notes as to why we do this.
3927 ??? Actually, the reemit_notes just say what is done, not why. */
3929 else if (GET_CODE (insn
) == NOTE
3930 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_START
3931 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_RANGE_END
))
3933 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
, NOTE_RANGE_INFO (insn
),
3935 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3936 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3939 else if (GET_CODE (insn
) == NOTE
3940 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
3941 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
3942 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3943 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
3944 || (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
3945 && GET_CODE (PREV_INSN (insn
)) != CALL_INSN
)))
3949 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_BEG
3950 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EH_REGION_END
)
3951 rtx_region
= GEN_INT (NOTE_EH_HANDLER (insn
));
3953 rtx_region
= GEN_INT (0);
3955 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3958 loop_notes
= alloc_EXPR_LIST (REG_SAVE_NOTE
,
3959 GEN_INT (NOTE_LINE_NUMBER (insn
)),
3961 CONST_CALL_P (loop_notes
) = CONST_CALL_P (insn
);
3970 /* Macros and functions for keeping the priority queue sorted, and
3971 dealing with queueing and dequeueing of instructions. */
3973 #define SCHED_SORT(READY, N_READY) \
3974 do { if ((N_READY) == 2) \
3975 swap_sort (READY, N_READY); \
3976 else if ((N_READY) > 2) \
3977 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
3980 /* Returns a positive value if x is preferred; returns a negative value if
3981 y is preferred. Should never return 0, since that will make the sort
3985 rank_for_schedule (x
, y
)
3989 rtx tmp
= *(rtx
*)y
;
3990 rtx tmp2
= *(rtx
*)x
;
3992 int tmp_class
, tmp2_class
, depend_count1
, depend_count2
;
3993 int val
, priority_val
, spec_val
, prob_val
, weight_val
;
3996 /* Prefer insn with higher priority. */
3997 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
3999 return priority_val
;
4001 /* Prefer an insn with smaller contribution to registers-pressure. */
4002 if (!reload_completed
&&
4003 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
4004 return (weight_val
);
4006 /* Some comparison make sense in interblock scheduling only. */
4007 if (INSN_BB (tmp
) != INSN_BB (tmp2
))
4009 /* Prefer an inblock motion on an interblock motion. */
4010 if ((INSN_BB (tmp2
) == target_bb
) && (INSN_BB (tmp
) != target_bb
))
4012 if ((INSN_BB (tmp
) == target_bb
) && (INSN_BB (tmp2
) != target_bb
))
4015 /* Prefer a useful motion on a speculative one. */
4016 if ((spec_val
= IS_SPECULATIVE_INSN (tmp
) - IS_SPECULATIVE_INSN (tmp2
)))
4019 /* Prefer a more probable (speculative) insn. */
4020 prob_val
= INSN_PROBABILITY (tmp2
) - INSN_PROBABILITY (tmp
);
4025 /* Compare insns based on their relation to the last-scheduled-insn. */
4026 if (last_scheduled_insn
)
4028 /* Classify the instructions into three classes:
4029 1) Data dependent on last schedule insn.
4030 2) Anti/Output dependent on last scheduled insn.
4031 3) Independent of last scheduled insn, or has latency of one.
4032 Choose the insn from the highest numbered class if different. */
4033 link
= find_insn_list (tmp
, INSN_DEPEND (last_scheduled_insn
));
4034 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp
) == 1)
4036 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4041 link
= find_insn_list (tmp2
, INSN_DEPEND (last_scheduled_insn
));
4042 if (link
== 0 || insn_cost (last_scheduled_insn
, link
, tmp2
) == 1)
4044 else if (REG_NOTE_KIND (link
) == 0) /* Data dependence. */
4049 if ((val
= tmp2_class
- tmp_class
))
4053 /* Prefer the insn which has more later insns that depend on it.
4054 This gives the scheduler more freedom when scheduling later
4055 instructions at the expense of added register pressure. */
4057 for (link
= INSN_DEPEND (tmp
); link
; link
= XEXP (link
, 1))
4061 for (link
= INSN_DEPEND (tmp2
); link
; link
= XEXP (link
, 1))
4064 val
= depend_count2
- depend_count1
;
4068 /* If insns are equally good, sort by INSN_LUID (original insn order),
4069 so that we make the sort stable. This minimizes instruction movement,
4070 thus minimizing sched's effect on debugging and cross-jumping. */
4071 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
4074 /* Resort the array A in which only element at index N may be out of order. */
4076 HAIFA_INLINE
static void
4081 rtx insn
= a
[n
- 1];
4084 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
4092 static int max_priority
;
4094 /* Add INSN to the insn queue so that it can be executed at least
4095 N_CYCLES after the currently executing insn. Preserve insns
4096 chain for debugging purposes. */
4098 HAIFA_INLINE
static void
4099 queue_insn (insn
, n_cycles
)
4103 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
4104 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
4105 insn_queue
[next_q
] = link
;
4108 if (sched_verbose
>= 2)
4110 fprintf (dump
, ";;\t\tReady-->Q: insn %d: ", INSN_UID (insn
));
4112 if (INSN_BB (insn
) != target_bb
)
4113 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4115 fprintf (dump
, "queued for %d cycles.\n", n_cycles
);
4120 /* PREV is an insn that is ready to execute. Adjust its priority if that
4121 will help shorten or lengthen register lifetimes as appropriate. Also
4122 provide a hook for the target to tweek itself. */
4124 HAIFA_INLINE
static void
4125 adjust_priority (prev
)
4126 rtx prev ATTRIBUTE_UNUSED
;
4128 /* ??? There used to be code here to try and estimate how an insn
4129 affected register lifetimes, but it did it by looking at REG_DEAD
4130 notes, which we removed in schedule_region. Nor did it try to
4131 take into account register pressure or anything useful like that.
4133 Revisit when we have a machine model to work with and not before. */
4135 #ifdef ADJUST_PRIORITY
4136 ADJUST_PRIORITY (prev
);
4140 /* Clock at which the previous instruction was issued. */
4141 static int last_clock_var
;
4143 /* INSN is the "currently executing insn". Launch each insn which was
4144 waiting on INSN. READY is a vector of insns which are ready to fire.
4145 N_READY is the number of elements in READY. CLOCK is the current
4149 schedule_insn (insn
, ready
, n_ready
, clock
)
4158 unit
= insn_unit (insn
);
4160 if (sched_verbose
>= 2)
4162 fprintf (dump
, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
4164 insn_print_units (insn
);
4165 fprintf (dump
, "\n");
4168 if (sched_verbose
&& unit
== -1)
4169 visualize_no_unit (insn
);
4171 if (MAX_BLOCKAGE
> 1 || issue_rate
> 1 || sched_verbose
)
4172 schedule_unit (unit
, insn
, clock
);
4174 if (INSN_DEPEND (insn
) == 0)
4177 /* This is used by the function adjust_priority above. */
4179 max_priority
= MAX (INSN_PRIORITY (ready
[0]), INSN_PRIORITY (insn
));
4181 max_priority
= INSN_PRIORITY (insn
);
4183 for (link
= INSN_DEPEND (insn
); link
!= 0; link
= XEXP (link
, 1))
4185 rtx next
= XEXP (link
, 0);
4186 int cost
= insn_cost (insn
, link
, next
);
4188 INSN_TICK (next
) = MAX (INSN_TICK (next
), clock
+ cost
);
4190 if ((INSN_DEP_COUNT (next
) -= 1) == 0)
4192 int effective_cost
= INSN_TICK (next
) - clock
;
4194 /* For speculative insns, before inserting to ready/queue,
4195 check live, exception-free, and issue-delay. */
4196 if (INSN_BB (next
) != target_bb
4197 && (!IS_VALID (INSN_BB (next
))
4199 || (IS_SPECULATIVE_INSN (next
)
4200 && (insn_issue_delay (next
) > 3
4201 || !check_live (next
, INSN_BB (next
))
4202 || !is_exception_free (next
, INSN_BB (next
), target_bb
)))))
4205 if (sched_verbose
>= 2)
4207 fprintf (dump
, ";;\t\tdependences resolved: insn %d ",
4210 if (current_nr_blocks
> 1 && INSN_BB (next
) != target_bb
)
4211 fprintf (dump
, "/b%d ", BLOCK_NUM (next
));
4213 if (effective_cost
< 1)
4214 fprintf (dump
, "into ready\n");
4216 fprintf (dump
, "into queue with cost=%d\n", effective_cost
);
4219 /* Adjust the priority of NEXT and either put it on the ready
4220 list or queue it. */
4221 adjust_priority (next
);
4222 if (effective_cost
< 1)
4223 ready
[n_ready
++] = next
;
4225 queue_insn (next
, effective_cost
);
4229 /* Annotate the instruction with issue information -- TImode
4230 indicates that the instruction is expected not to be able
4231 to issue on the same cycle as the previous insn. A machine
4232 may use this information to decide how the instruction should
4234 if (reload_completed
&& issue_rate
> 1)
4236 PUT_MODE (insn
, clock
> last_clock_var
? TImode
: VOIDmode
);
4237 last_clock_var
= clock
;
4243 /* Functions for handling of notes. */
4245 /* Delete notes beginning with INSN and put them in the chain
4246 of notes ended by NOTE_LIST.
4247 Returns the insn following the notes. */
4250 unlink_other_notes (insn
, tail
)
4253 rtx prev
= PREV_INSN (insn
);
4255 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4257 rtx next
= NEXT_INSN (insn
);
4258 /* Delete the note from its current position. */
4260 NEXT_INSN (prev
) = next
;
4262 PREV_INSN (next
) = prev
;
4264 /* See sched_analyze to see how these are handled. */
4265 if (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_SETJMP
4266 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_BEG
4267 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
4268 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_START
4269 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_RANGE_END
4270 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_BEG
4271 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_EH_REGION_END
)
4273 /* Insert the note at the end of the notes list. */
4274 PREV_INSN (insn
) = note_list
;
4276 NEXT_INSN (note_list
) = insn
;
4285 /* Delete line notes beginning with INSN. Record line-number notes so
4286 they can be reused. Returns the insn following the notes. */
4289 unlink_line_notes (insn
, tail
)
4292 rtx prev
= PREV_INSN (insn
);
4294 while (insn
!= tail
&& GET_CODE (insn
) == NOTE
)
4296 rtx next
= NEXT_INSN (insn
);
4298 if (write_symbols
!= NO_DEBUG
&& NOTE_LINE_NUMBER (insn
) > 0)
4300 /* Delete the note from its current position. */
4302 NEXT_INSN (prev
) = next
;
4304 PREV_INSN (next
) = prev
;
4306 /* Record line-number notes so they can be reused. */
4307 LINE_NOTE (insn
) = insn
;
4317 /* Return the head and tail pointers of BB. */
4319 HAIFA_INLINE
static void
4320 get_block_head_tail (b
, headp
, tailp
)
4329 /* HEAD and TAIL delimit the basic block being scheduled. */
4330 head
= BLOCK_HEAD (b
);
4331 tail
= BLOCK_END (b
);
4333 /* Don't include any notes or labels at the beginning of the
4334 basic block, or notes at the ends of basic blocks. */
4335 while (head
!= tail
)
4337 if (GET_CODE (head
) == NOTE
)
4338 head
= NEXT_INSN (head
);
4339 else if (GET_CODE (tail
) == NOTE
)
4340 tail
= PREV_INSN (tail
);
4341 else if (GET_CODE (head
) == CODE_LABEL
)
4342 head
= NEXT_INSN (head
);
4351 HAIFA_INLINE
static void
4352 get_bb_head_tail (bb
, headp
, tailp
)
4357 get_block_head_tail (BB_TO_BLOCK (bb
), headp
, tailp
);
4360 /* Delete line notes from bb. Save them so they can be later restored
4361 (in restore_line_notes ()). */
4372 get_bb_head_tail (bb
, &head
, &tail
);
4375 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4378 next_tail
= NEXT_INSN (tail
);
4379 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4383 /* Farm out notes, and maybe save them in NOTE_LIST.
4384 This is needed to keep the debugger from
4385 getting completely deranged. */
4386 if (GET_CODE (insn
) == NOTE
)
4389 insn
= unlink_line_notes (insn
, next_tail
);
4395 if (insn
== next_tail
)
4401 /* Save line number notes for each insn in bb. */
4404 save_line_notes (bb
)
4410 /* We must use the true line number for the first insn in the block
4411 that was computed and saved at the start of this pass. We can't
4412 use the current line number, because scheduling of the previous
4413 block may have changed the current line number. */
4415 rtx line
= line_note_head
[BB_TO_BLOCK (bb
)];
4418 get_bb_head_tail (bb
, &head
, &tail
);
4419 next_tail
= NEXT_INSN (tail
);
4421 for (insn
= BLOCK_HEAD (BB_TO_BLOCK (bb
));
4423 insn
= NEXT_INSN (insn
))
4424 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4427 LINE_NOTE (insn
) = line
;
4431 /* After bb was scheduled, insert line notes into the insns list. */
4434 restore_line_notes (bb
)
4437 rtx line
, note
, prev
, new;
4438 int added_notes
= 0;
4440 rtx head
, next_tail
, insn
;
4442 b
= BB_TO_BLOCK (bb
);
4444 head
= BLOCK_HEAD (b
);
4445 next_tail
= NEXT_INSN (BLOCK_END (b
));
4447 /* Determine the current line-number. We want to know the current
4448 line number of the first insn of the block here, in case it is
4449 different from the true line number that was saved earlier. If
4450 different, then we need a line number note before the first insn
4451 of this block. If it happens to be the same, then we don't want to
4452 emit another line number note here. */
4453 for (line
= head
; line
; line
= PREV_INSN (line
))
4454 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
4457 /* Walk the insns keeping track of the current line-number and inserting
4458 the line-number notes as needed. */
4459 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4460 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4462 /* This used to emit line number notes before every non-deleted note.
4463 However, this confuses a debugger, because line notes not separated
4464 by real instructions all end up at the same address. I can find no
4465 use for line number notes before other notes, so none are emitted. */
4466 else if (GET_CODE (insn
) != NOTE
4467 && (note
= LINE_NOTE (insn
)) != 0
4470 || NOTE_LINE_NUMBER (note
) != NOTE_LINE_NUMBER (line
)
4471 || NOTE_SOURCE_FILE (note
) != NOTE_SOURCE_FILE (line
)))
4474 prev
= PREV_INSN (insn
);
4475 if (LINE_NOTE (note
))
4477 /* Re-use the original line-number note. */
4478 LINE_NOTE (note
) = 0;
4479 PREV_INSN (note
) = prev
;
4480 NEXT_INSN (prev
) = note
;
4481 PREV_INSN (insn
) = note
;
4482 NEXT_INSN (note
) = insn
;
4487 new = emit_note_after (NOTE_LINE_NUMBER (note
), prev
);
4488 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note
);
4489 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note
);
4492 if (sched_verbose
&& added_notes
)
4493 fprintf (dump
, ";; added %d line-number notes\n", added_notes
);
4496 /* After scheduling the function, delete redundant line notes from the
4500 rm_redundant_line_notes ()
4503 rtx insn
= get_insns ();
4504 int active_insn
= 0;
4507 /* Walk the insns deleting redundant line-number notes. Many of these
4508 are already present. The remainder tend to occur at basic
4509 block boundaries. */
4510 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4511 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
4513 /* If there are no active insns following, INSN is redundant. */
4514 if (active_insn
== 0)
4517 NOTE_SOURCE_FILE (insn
) = 0;
4518 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
4520 /* If the line number is unchanged, LINE is redundant. */
4522 && NOTE_LINE_NUMBER (line
) == NOTE_LINE_NUMBER (insn
)
4523 && NOTE_SOURCE_FILE (line
) == NOTE_SOURCE_FILE (insn
))
4526 NOTE_SOURCE_FILE (line
) = 0;
4527 NOTE_LINE_NUMBER (line
) = NOTE_INSN_DELETED
;
4534 else if (!((GET_CODE (insn
) == NOTE
4535 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
4536 || (GET_CODE (insn
) == INSN
4537 && (GET_CODE (PATTERN (insn
)) == USE
4538 || GET_CODE (PATTERN (insn
)) == CLOBBER
))))
4541 if (sched_verbose
&& notes
)
4542 fprintf (dump
, ";; deleted %d line-number notes\n", notes
);
4545 /* Delete notes between head and tail and put them in the chain
4546 of notes ended by NOTE_LIST. */
4549 rm_other_notes (head
, tail
)
4557 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
4560 next_tail
= NEXT_INSN (tail
);
4561 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4565 /* Farm out notes, and maybe save them in NOTE_LIST.
4566 This is needed to keep the debugger from
4567 getting completely deranged. */
4568 if (GET_CODE (insn
) == NOTE
)
4572 insn
= unlink_other_notes (insn
, next_tail
);
4578 if (insn
== next_tail
)
4584 /* Functions for computation of registers live/usage info. */
4586 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
4589 find_insn_reg_weight (b
)
4592 rtx insn
, next_tail
, head
, tail
;
4594 get_block_head_tail (b
, &head
, &tail
);
4595 next_tail
= NEXT_INSN (tail
);
4597 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
4602 /* Handle register life information. */
4603 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4606 /* Increment weight for each register born here. */
4608 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4609 && register_operand (SET_DEST (x
), VOIDmode
))
4611 else if (GET_CODE (x
) == PARALLEL
)
4614 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
4616 x
= XVECEXP (PATTERN (insn
), 0, j
);
4617 if ((GET_CODE (x
) == SET
|| GET_CODE (x
) == CLOBBER
)
4618 && register_operand (SET_DEST (x
), VOIDmode
))
4623 /* Decrement weight for each register that dies here. */
4624 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
4626 if (REG_NOTE_KIND (x
) == REG_DEAD
4627 || REG_NOTE_KIND (x
) == REG_UNUSED
)
4631 INSN_REG_WEIGHT (insn
) = reg_weight
;
4635 /* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
4636 static int clock_var
;
4638 /* Move insns that became ready to fire from queue to ready list. */
4641 queue_to_ready (ready
, n_ready
)
4648 q_ptr
= NEXT_Q (q_ptr
);
4650 /* Add all pending insns that can be scheduled without stalls to the
4652 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
4655 insn
= XEXP (link
, 0);
4658 if (sched_verbose
>= 2)
4659 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4661 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4662 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4664 ready
[n_ready
++] = insn
;
4665 if (sched_verbose
>= 2)
4666 fprintf (dump
, "moving to ready without stalls\n");
4668 insn_queue
[q_ptr
] = 0;
4670 /* If there are no ready insns, stall until one is ready and add all
4671 of the pending insns at that point to the ready list. */
4674 register int stalls
;
4676 for (stalls
= 1; stalls
< INSN_QUEUE_SIZE
; stalls
++)
4678 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
4680 for (; link
; link
= XEXP (link
, 1))
4682 insn
= XEXP (link
, 0);
4685 if (sched_verbose
>= 2)
4686 fprintf (dump
, ";;\t\tQ-->Ready: insn %d: ", INSN_UID (insn
));
4688 if (sched_verbose
>= 2 && INSN_BB (insn
) != target_bb
)
4689 fprintf (dump
, "(b%d) ", BLOCK_NUM (insn
));
4691 ready
[n_ready
++] = insn
;
4692 if (sched_verbose
>= 2)
4693 fprintf (dump
, "moving to ready with %d stalls\n", stalls
);
4695 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = 0;
4702 if (sched_verbose
&& stalls
)
4703 visualize_stall_cycles (BB_TO_BLOCK (target_bb
), stalls
);
4704 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
4705 clock_var
+= stalls
;
4710 /* Print the ready list for debugging purposes. Callable from debugger. */
4713 debug_ready_list (ready
, n_ready
)
4719 for (i
= 0; i
< n_ready
; i
++)
4721 fprintf (dump
, " %d", INSN_UID (ready
[i
]));
4722 if (current_nr_blocks
> 1 && INSN_BB (ready
[i
]) != target_bb
)
4723 fprintf (dump
, "/b%d", BLOCK_NUM (ready
[i
]));
4725 fprintf (dump
, "\n");
4728 /* Print names of units on which insn can/should execute, for debugging. */
4731 insn_print_units (insn
)
4735 int unit
= insn_unit (insn
);
4738 fprintf (dump
, "none");
4740 fprintf (dump
, "%s", function_units
[unit
].name
);
4743 fprintf (dump
, "[");
4744 for (i
= 0, unit
= ~unit
; unit
; i
++, unit
>>= 1)
4747 fprintf (dump
, "%s", function_units
[i
].name
);
4749 fprintf (dump
, " ");
4751 fprintf (dump
, "]");
4755 /* MAX_VISUAL_LINES is the maximum number of lines in visualization table
4756 of a basic block. If more lines are needed, table is splitted to two.
4757 n_visual_lines is the number of lines printed so far for a block.
4758 visual_tbl contains the block visualization info.
4759 vis_no_unit holds insns in a cycle that are not mapped to any unit. */
4760 #define MAX_VISUAL_LINES 100
4765 rtx vis_no_unit
[10];
4767 /* Finds units that are in use in this fuction. Required only
4768 for visualization. */
4771 init_target_units ()
4776 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
4778 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
4781 unit
= insn_unit (insn
);
4784 target_units
|= ~unit
;
4786 target_units
|= (1 << unit
);
4790 /* Return the length of the visualization table. */
4793 get_visual_tbl_length ()
4799 /* Compute length of one field in line. */
4800 s
= (char *) alloca (INSN_LEN
+ 6);
4801 sprintf (s
, " %33s", "uname");
4804 /* Compute length of one line. */
4807 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
4808 if (function_units
[unit
].bitmask
& target_units
)
4809 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
4812 n
+= strlen ("\n") + 2;
4814 /* Compute length of visualization string. */
4815 return (MAX_VISUAL_LINES
* n
);
4818 /* Init block visualization debugging info. */
4821 init_block_visualization ()
4823 strcpy (visual_tbl
, "");
4831 safe_concat (buf
, cur
, str
)
4836 char *end
= buf
+ BUF_LEN
- 2; /* Leave room for null. */
4845 while (cur
< end
&& (c
= *str
++) != '\0')
4852 /* This recognizes rtx, I classified as expressions. These are always
4853 represent some action on values or results of other expression, that
4854 may be stored in objects representing values. */
4857 print_exp (buf
, x
, verbose
)
4865 const char *fun
= (char *)0;
4870 for (i
= 0; i
< 4; i
++)
4876 switch (GET_CODE (x
))
4879 op
[0] = XEXP (x
, 0);
4880 if (GET_CODE (XEXP (x
, 1)) == CONST_INT
4881 && INTVAL (XEXP (x
, 1)) < 0)
4884 op
[1] = GEN_INT (-INTVAL (XEXP (x
, 1)));
4889 op
[1] = XEXP (x
, 1);
4893 op
[0] = XEXP (x
, 0);
4895 op
[1] = XEXP (x
, 1);
4899 op
[0] = XEXP (x
, 0);
4901 op
[1] = XEXP (x
, 1);
4905 op
[0] = XEXP (x
, 0);
4906 op
[1] = XEXP (x
, 1);
4910 op
[0] = XEXP (x
, 0);
4913 op
[0] = XEXP (x
, 0);
4915 op
[1] = XEXP (x
, 1);
4918 op
[0] = XEXP (x
, 0);
4920 op
[1] = XEXP (x
, 1);
4924 op
[0] = XEXP (x
, 0);
4925 op
[1] = XEXP (x
, 1);
4928 op
[0] = XEXP (x
, 0);
4930 op
[1] = XEXP (x
, 1);
4934 op
[0] = XEXP (x
, 0);
4935 op
[1] = XEXP (x
, 1);
4939 op
[0] = XEXP (x
, 0);
4940 op
[1] = XEXP (x
, 1);
4944 op
[0] = XEXP (x
, 0);
4945 op
[1] = XEXP (x
, 1);
4949 op
[0] = XEXP (x
, 0);
4950 op
[1] = XEXP (x
, 1);
4954 op
[0] = XEXP (x
, 0);
4955 op
[1] = XEXP (x
, 1);
4959 op
[0] = XEXP (x
, 0);
4962 op
[0] = XEXP (x
, 0);
4964 op
[1] = XEXP (x
, 1);
4967 op
[0] = XEXP (x
, 0);
4969 op
[1] = XEXP (x
, 1);
4972 op
[0] = XEXP (x
, 0);
4974 op
[1] = XEXP (x
, 1);
4977 op
[0] = XEXP (x
, 0);
4979 op
[1] = XEXP (x
, 1);
4982 op
[0] = XEXP (x
, 0);
4984 op
[1] = XEXP (x
, 1);
4987 op
[0] = XEXP (x
, 0);
4989 op
[1] = XEXP (x
, 1);
4992 op
[0] = XEXP (x
, 0);
4994 op
[1] = XEXP (x
, 1);
4997 op
[0] = XEXP (x
, 0);
4999 op
[1] = XEXP (x
, 1);
5003 op
[0] = XEXP (x
, 0);
5007 op
[0] = XEXP (x
, 0);
5011 op
[0] = XEXP (x
, 0);
5014 op
[0] = XEXP (x
, 0);
5016 op
[1] = XEXP (x
, 1);
5019 op
[0] = XEXP (x
, 0);
5021 op
[1] = XEXP (x
, 1);
5024 op
[0] = XEXP (x
, 0);
5026 op
[1] = XEXP (x
, 1);
5030 op
[0] = XEXP (x
, 0);
5031 op
[1] = XEXP (x
, 1);
5034 op
[0] = XEXP (x
, 0);
5036 op
[1] = XEXP (x
, 1);
5040 op
[0] = XEXP (x
, 0);
5041 op
[1] = XEXP (x
, 1);
5044 op
[0] = XEXP (x
, 0);
5046 op
[1] = XEXP (x
, 1);
5050 op
[0] = XEXP (x
, 0);
5051 op
[1] = XEXP (x
, 1);
5054 op
[0] = XEXP (x
, 0);
5056 op
[1] = XEXP (x
, 1);
5060 op
[0] = XEXP (x
, 0);
5061 op
[1] = XEXP (x
, 1);
5064 fun
= (verbose
) ? "sign_extract" : "sxt";
5065 op
[0] = XEXP (x
, 0);
5066 op
[1] = XEXP (x
, 1);
5067 op
[2] = XEXP (x
, 2);
5070 fun
= (verbose
) ? "zero_extract" : "zxt";
5071 op
[0] = XEXP (x
, 0);
5072 op
[1] = XEXP (x
, 1);
5073 op
[2] = XEXP (x
, 2);
5076 fun
= (verbose
) ? "sign_extend" : "sxn";
5077 op
[0] = XEXP (x
, 0);
5080 fun
= (verbose
) ? "zero_extend" : "zxn";
5081 op
[0] = XEXP (x
, 0);
5084 fun
= (verbose
) ? "float_extend" : "fxn";
5085 op
[0] = XEXP (x
, 0);
5088 fun
= (verbose
) ? "trunc" : "trn";
5089 op
[0] = XEXP (x
, 0);
5091 case FLOAT_TRUNCATE
:
5092 fun
= (verbose
) ? "float_trunc" : "ftr";
5093 op
[0] = XEXP (x
, 0);
5096 fun
= (verbose
) ? "float" : "flt";
5097 op
[0] = XEXP (x
, 0);
5099 case UNSIGNED_FLOAT
:
5100 fun
= (verbose
) ? "uns_float" : "ufl";
5101 op
[0] = XEXP (x
, 0);
5105 op
[0] = XEXP (x
, 0);
5108 fun
= (verbose
) ? "uns_fix" : "ufx";
5109 op
[0] = XEXP (x
, 0);
5113 op
[0] = XEXP (x
, 0);
5117 op
[0] = XEXP (x
, 0);
5120 op
[0] = XEXP (x
, 0);
5124 op
[0] = XEXP (x
, 0);
5129 op
[0] = XEXP (x
, 0);
5133 op
[1] = XEXP (x
, 1);
5138 op
[0] = XEXP (x
, 0);
5140 op
[1] = XEXP (x
, 1);
5142 op
[2] = XEXP (x
, 2);
5147 op
[0] = TRAP_CONDITION (x
);
5150 case UNSPEC_VOLATILE
:
5152 cur
= safe_concat (buf
, cur
, "unspec");
5153 if (GET_CODE (x
) == UNSPEC_VOLATILE
)
5154 cur
= safe_concat (buf
, cur
, "/v");
5155 cur
= safe_concat (buf
, cur
, "[");
5157 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5159 print_pattern (tmp
, XVECEXP (x
, 0, i
), verbose
);
5160 cur
= safe_concat (buf
, cur
, sep
);
5161 cur
= safe_concat (buf
, cur
, tmp
);
5164 cur
= safe_concat (buf
, cur
, "] ");
5165 sprintf (tmp
, "%d", XINT (x
, 1));
5166 cur
= safe_concat (buf
, cur
, tmp
);
5170 /* If (verbose) debug_rtx (x); */
5171 st
[0] = GET_RTX_NAME (GET_CODE (x
));
5175 /* Print this as a function? */
5178 cur
= safe_concat (buf
, cur
, fun
);
5179 cur
= safe_concat (buf
, cur
, "(");
5182 for (i
= 0; i
< 4; i
++)
5185 cur
= safe_concat (buf
, cur
, st
[i
]);
5190 cur
= safe_concat (buf
, cur
, ",");
5192 print_value (tmp
, op
[i
], verbose
);
5193 cur
= safe_concat (buf
, cur
, tmp
);
5198 cur
= safe_concat (buf
, cur
, ")");
5201 /* Prints rtxes, I customly classified as values. They're constants,
5202 registers, labels, symbols and memory accesses. */
5205 print_value (buf
, x
, verbose
)
5213 switch (GET_CODE (x
))
5216 sprintf (t
, HOST_WIDE_INT_PRINT_HEX
, INTVAL (x
));
5217 cur
= safe_concat (buf
, cur
, t
);
5220 sprintf (t
, "<0x%lx,0x%lx>", (long)XWINT (x
, 2), (long)XWINT (x
, 3));
5221 cur
= safe_concat (buf
, cur
, t
);
5224 cur
= safe_concat (buf
, cur
, "\"");
5225 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5226 cur
= safe_concat (buf
, cur
, "\"");
5229 cur
= safe_concat (buf
, cur
, "`");
5230 cur
= safe_concat (buf
, cur
, XSTR (x
, 0));
5231 cur
= safe_concat (buf
, cur
, "'");
5234 sprintf (t
, "L%d", INSN_UID (XEXP (x
, 0)));
5235 cur
= safe_concat (buf
, cur
, t
);
5238 print_value (t
, XEXP (x
, 0), verbose
);
5239 cur
= safe_concat (buf
, cur
, "const(");
5240 cur
= safe_concat (buf
, cur
, t
);
5241 cur
= safe_concat (buf
, cur
, ")");
5244 print_value (t
, XEXP (x
, 0), verbose
);
5245 cur
= safe_concat (buf
, cur
, "high(");
5246 cur
= safe_concat (buf
, cur
, t
);
5247 cur
= safe_concat (buf
, cur
, ")");
5250 if (REGNO (x
) < FIRST_PSEUDO_REGISTER
)
5252 int c
= reg_names
[ REGNO (x
) ][0];
5253 if (c
>= '0' && c
<= '9')
5254 cur
= safe_concat (buf
, cur
, "%");
5256 cur
= safe_concat (buf
, cur
, reg_names
[ REGNO (x
) ]);
5260 sprintf (t
, "r%d", REGNO (x
));
5261 cur
= safe_concat (buf
, cur
, t
);
5265 print_value (t
, SUBREG_REG (x
), verbose
);
5266 cur
= safe_concat (buf
, cur
, t
);
5267 sprintf (t
, "#%d", SUBREG_WORD (x
));
5268 cur
= safe_concat (buf
, cur
, t
);
5271 cur
= safe_concat (buf
, cur
, "scratch");
5274 cur
= safe_concat (buf
, cur
, "cc0");
5277 cur
= safe_concat (buf
, cur
, "pc");
5280 print_value (t
, XEXP (x
, 0), verbose
);
5281 cur
= safe_concat (buf
, cur
, "[");
5282 cur
= safe_concat (buf
, cur
, t
);
5283 cur
= safe_concat (buf
, cur
, "]");
5286 print_exp (t
, x
, verbose
);
5287 cur
= safe_concat (buf
, cur
, t
);
5292 /* The next step in insn detalization, its pattern recognition. */
5295 print_pattern (buf
, x
, verbose
)
5300 char t1
[BUF_LEN
], t2
[BUF_LEN
], t3
[BUF_LEN
];
5302 switch (GET_CODE (x
))
5305 print_value (t1
, SET_DEST (x
), verbose
);
5306 print_value (t2
, SET_SRC (x
), verbose
);
5307 sprintf (buf
, "%s=%s", t1
, t2
);
5310 sprintf (buf
, "return");
5313 print_exp (buf
, x
, verbose
);
5316 print_value (t1
, XEXP (x
, 0), verbose
);
5317 sprintf (buf
, "clobber %s", t1
);
5320 print_value (t1
, XEXP (x
, 0), verbose
);
5321 sprintf (buf
, "use %s", t1
);
5328 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5330 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5331 sprintf (t3
, "%s%s;", t1
, t2
);
5334 sprintf (buf
, "%s}", t1
);
5341 sprintf (t1
, "%%{");
5342 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5344 print_insn (t2
, XVECEXP (x
, 0, i
), verbose
);
5345 sprintf (t3
, "%s%s;", t1
, t2
);
5348 sprintf (buf
, "%s%%}", t1
);
5352 sprintf (buf
, "asm {%s}", XSTR (x
, 0));
5357 print_value (buf
, XEXP (x
, 0), verbose
);
5360 print_value (t1
, TRAP_CONDITION (x
), verbose
);
5361 sprintf (buf
, "trap_if %s", t1
);
5367 sprintf (t1
, "unspec{");
5368 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5370 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5371 sprintf (t3
, "%s%s;", t1
, t2
);
5374 sprintf (buf
, "%s}", t1
);
5377 case UNSPEC_VOLATILE
:
5381 sprintf (t1
, "unspec/v{");
5382 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
5384 print_pattern (t2
, XVECEXP (x
, 0, i
), verbose
);
5385 sprintf (t3
, "%s%s;", t1
, t2
);
5388 sprintf (buf
, "%s}", t1
);
5392 print_value (buf
, x
, verbose
);
5394 } /* print_pattern */
5396 /* This is the main function in rtl visualization mechanism. It
5397 accepts an rtx and tries to recognize it as an insn, then prints it
5398 properly in human readable form, resembling assembler mnemonics.
5399 For every insn it prints its UID and BB the insn belongs too.
5400 (Probably the last "option" should be extended somehow, since it
5401 depends now on sched.c inner variables ...) */
5404 print_insn (buf
, x
, verbose
)
5412 switch (GET_CODE (x
))
5415 print_pattern (t
, PATTERN (x
), verbose
);
5417 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (x
),
5420 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5423 print_pattern (t
, PATTERN (x
), verbose
);
5425 sprintf (buf
, "b%d: i% 4d: jump %s", INSN_BB (x
),
5428 sprintf (buf
, "%-4d %s", INSN_UID (x
), t
);
5432 if (GET_CODE (x
) == PARALLEL
)
5434 x
= XVECEXP (x
, 0, 0);
5435 print_pattern (t
, x
, verbose
);
5438 strcpy (t
, "call <...>");
5440 sprintf (buf
, "b%d: i% 4d: %s", INSN_BB (insn
),
5441 INSN_UID (insn
), t
);
5443 sprintf (buf
, "%-4d %s", INSN_UID (insn
), t
);
5446 sprintf (buf
, "L%d:", INSN_UID (x
));
5449 sprintf (buf
, "i% 4d: barrier", INSN_UID (x
));
5452 if (NOTE_LINE_NUMBER (x
) > 0)
5453 sprintf (buf
, "%4d note \"%s\" %d", INSN_UID (x
),
5454 NOTE_SOURCE_FILE (x
), NOTE_LINE_NUMBER (x
));
5456 sprintf (buf
, "%4d %s", INSN_UID (x
),
5457 GET_NOTE_INSN_NAME (NOTE_LINE_NUMBER (x
)));
5462 sprintf (buf
, "Not an INSN at all\n");
5466 sprintf (buf
, "i%-4d <What?>", INSN_UID (x
));
5470 /* Print visualization debugging info. */
5473 print_block_visualization (b
, s
)
5480 fprintf (dump
, "\n;; ==================== scheduling visualization for block %d %s \n", b
, s
);
5482 /* Print names of units. */
5483 fprintf (dump
, ";; %-8s", "clock");
5484 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5485 if (function_units
[unit
].bitmask
& target_units
)
5486 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5487 fprintf (dump
, " %-33s", function_units
[unit
].name
);
5488 fprintf (dump
, " %-8s\n", "no-unit");
5490 fprintf (dump
, ";; %-8s", "=====");
5491 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5492 if (function_units
[unit
].bitmask
& target_units
)
5493 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5494 fprintf (dump
, " %-33s", "==============================");
5495 fprintf (dump
, " %-8s\n", "=======");
5497 /* Print insns in each cycle. */
5498 fprintf (dump
, "%s\n", visual_tbl
);
5501 /* Print insns in the 'no_unit' column of visualization. */
5504 visualize_no_unit (insn
)
5507 vis_no_unit
[n_vis_no_unit
] = insn
;
5511 /* Print insns scheduled in clock, for visualization. */
5514 visualize_scheduled_insns (b
, clock
)
5519 /* If no more room, split table into two. */
5520 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5522 print_block_visualization (b
, "(incomplete)");
5523 init_block_visualization ();
5528 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; %-8d", clock
);
5529 for (unit
= 0; unit
< FUNCTION_UNITS_SIZE
; unit
++)
5530 if (function_units
[unit
].bitmask
& target_units
)
5531 for (i
= 0; i
< function_units
[unit
].multiplicity
; i
++)
5533 int instance
= unit
+ i
* FUNCTION_UNITS_SIZE
;
5534 rtx insn
= unit_last_insn
[instance
];
5536 /* Print insns that still keep the unit busy. */
5538 actual_hazard_this_instance (unit
, instance
, insn
, clock
, 0))
5541 print_insn (str
, insn
, 0);
5542 str
[INSN_LEN
] = '\0';
5543 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", str
);
5546 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-33s", "------------------------------");
5549 /* Print insns that are not assigned to any unit. */
5550 for (i
= 0; i
< n_vis_no_unit
; i
++)
5551 sprintf (visual_tbl
+ strlen (visual_tbl
), " %-8d",
5552 INSN_UID (vis_no_unit
[i
]));
5555 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5558 /* Print stalled cycles. */
5561 visualize_stall_cycles (b
, stalls
)
5566 /* If no more room, split table into two. */
5567 if (n_visual_lines
>= MAX_VISUAL_LINES
)
5569 print_block_visualization (b
, "(incomplete)");
5570 init_block_visualization ();
5575 sprintf (visual_tbl
+ strlen (visual_tbl
), ";; ");
5576 for (i
= 0; i
< stalls
; i
++)
5577 sprintf (visual_tbl
+ strlen (visual_tbl
), ".");
5578 sprintf (visual_tbl
+ strlen (visual_tbl
), "\n");
5581 /* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
5584 move_insn1 (insn
, last
)
5587 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
5588 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
5590 NEXT_INSN (insn
) = NEXT_INSN (last
);
5591 PREV_INSN (NEXT_INSN (last
)) = insn
;
5593 NEXT_INSN (last
) = insn
;
5594 PREV_INSN (insn
) = last
;
5599 /* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
5600 NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
5601 NOTEs. The REG_SAVE_NOTE note following first one is contains the
5602 saved value for NOTE_BLOCK_NUMBER which is useful for
5603 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
5604 output by the instruction scheduler. Return the new value of LAST. */
5607 reemit_notes (insn
, last
)
5614 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
5616 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5618 int note_type
= INTVAL (XEXP (note
, 0));
5619 if (note_type
== NOTE_INSN_SETJMP
)
5621 retval
= emit_note_after (NOTE_INSN_SETJMP
, insn
);
5622 CONST_CALL_P (retval
) = CONST_CALL_P (note
);
5623 remove_note (insn
, note
);
5624 note
= XEXP (note
, 1);
5626 else if (note_type
== NOTE_INSN_RANGE_START
5627 || note_type
== NOTE_INSN_RANGE_END
)
5629 last
= emit_note_before (note_type
, last
);
5630 remove_note (insn
, note
);
5631 note
= XEXP (note
, 1);
5632 NOTE_RANGE_INFO (last
) = XEXP (note
, 0);
5636 last
= emit_note_before (note_type
, last
);
5637 remove_note (insn
, note
);
5638 note
= XEXP (note
, 1);
5639 if (note_type
== NOTE_INSN_EH_REGION_BEG
5640 || note_type
== NOTE_INSN_EH_REGION_END
)
5641 NOTE_EH_HANDLER (last
) = INTVAL (XEXP (note
, 0));
5643 remove_note (insn
, note
);
5649 /* Move INSN, and all insns which should be issued before it,
5650 due to SCHED_GROUP_P flag. Reemit notes if needed.
5652 Return the last insn emitted by the scheduler, which is the
5653 return value from the first call to reemit_notes. */
5656 move_insn (insn
, last
)
5661 /* If INSN has SCHED_GROUP_P set, then issue it and any other
5662 insns with SCHED_GROUP_P set first. */
5663 while (SCHED_GROUP_P (insn
))
5665 rtx prev
= PREV_INSN (insn
);
5667 /* Move a SCHED_GROUP_P insn. */
5668 move_insn1 (insn
, last
);
5669 /* If this is the first call to reemit_notes, then record
5670 its return value. */
5671 if (retval
== NULL_RTX
)
5672 retval
= reemit_notes (insn
, insn
);
5674 reemit_notes (insn
, insn
);
5678 /* Now move the first non SCHED_GROUP_P insn. */
5679 move_insn1 (insn
, last
);
5681 /* If this is the first call to reemit_notes, then record
5682 its return value. */
5683 if (retval
== NULL_RTX
)
5684 retval
= reemit_notes (insn
, insn
);
5686 reemit_notes (insn
, insn
);
5691 /* Return an insn which represents a SCHED_GROUP, which is
5692 the last insn in the group. */
5703 insn
= next_nonnote_insn (insn
);
5705 while (insn
&& SCHED_GROUP_P (insn
) && (GET_CODE (insn
) != CODE_LABEL
));
5710 /* Use forward list scheduling to rearrange insns of block BB in region RGN,
5711 possibly bringing insns from subsequent blocks in the same region.
5712 Return number of insns scheduled. */
5715 schedule_block (bb
, rgn_n_insns
)
5719 /* Local variables. */
5725 /* Flow block of this bb. */
5726 int b
= BB_TO_BLOCK (bb
);
5728 /* target_n_insns == number of insns in b before scheduling starts.
5729 sched_target_n_insns == how many of b's insns were scheduled.
5730 sched_n_insns == how many insns were scheduled in b. */
5731 int target_n_insns
= 0;
5732 int sched_target_n_insns
= 0;
5733 int sched_n_insns
= 0;
5735 #define NEED_NOTHING 0
5740 /* Head/tail info for this block. */
5747 /* We used to have code to avoid getting parameters moved from hard
5748 argument registers into pseudos.
5750 However, it was removed when it proved to be of marginal benefit
5751 and caused problems because schedule_block and compute_forward_dependences
5752 had different notions of what the "head" insn was. */
5753 get_bb_head_tail (bb
, &head
, &tail
);
5755 /* Interblock scheduling could have moved the original head insn from this
5756 block into a proceeding block. This may also cause schedule_block and
5757 compute_forward_dependences to have different notions of what the
5760 If the interblock movement happened to make this block start with
5761 some notes (LOOP, EH or SETJMP) before the first real insn, then
5762 HEAD will have various special notes attached to it which must be
5763 removed so that we don't end up with extra copies of the notes. */
5764 if (GET_RTX_CLASS (GET_CODE (head
)) == 'i')
5768 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
5769 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
5770 remove_note (head
, note
);
5773 next_tail
= NEXT_INSN (tail
);
5774 prev_head
= PREV_INSN (head
);
5776 /* If the only insn left is a NOTE or a CODE_LABEL, then there is no need
5777 to schedule this block. */
5779 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5780 return (sched_n_insns
);
5785 fprintf (dump
, ";; ======================================================\n");
5787 ";; -- basic block %d from %d to %d -- %s reload\n",
5788 b
, INSN_UID (BLOCK_HEAD (b
)), INSN_UID (BLOCK_END (b
)),
5789 (reload_completed
? "after" : "before"));
5790 fprintf (dump
, ";; ======================================================\n");
5791 fprintf (dump
, "\n");
5793 visual_tbl
= (char *) alloca (get_visual_tbl_length ());
5794 init_block_visualization ();
5797 /* Remove remaining note insns from the block, save them in
5798 note_list. These notes are restored at the end of
5799 schedule_block (). */
5801 rm_other_notes (head
, tail
);
5805 /* Prepare current target block info. */
5806 if (current_nr_blocks
> 1)
5808 candidate_table
= (candidate
*) xmalloc (current_nr_blocks
5809 * sizeof (candidate
));
5812 /* ??? It is not clear why bblst_size is computed this way. The original
5813 number was clearly too small as it resulted in compiler failures.
5814 Multiplying by the original number by 2 (to account for update_bbs
5815 members) seems to be a reasonable solution. */
5816 /* ??? Or perhaps there is a bug somewhere else in this file? */
5817 bblst_size
= (current_nr_blocks
- bb
) * rgn_nr_edges
* 2;
5818 bblst_table
= (int *) xmalloc (bblst_size
* sizeof (int));
5820 bitlst_table_last
= 0;
5821 bitlst_table_size
= rgn_nr_edges
;
5822 bitlst_table
= (int *) xmalloc (rgn_nr_edges
* sizeof (int));
5824 compute_trg_info (bb
);
5829 /* Allocate the ready list. */
5830 ready
= (rtx
*) xmalloc ((rgn_n_insns
+ 1) * sizeof (rtx
));
5832 /* Print debugging information. */
5833 if (sched_verbose
>= 5)
5834 debug_dependencies ();
5837 /* Initialize ready list with all 'ready' insns in target block.
5838 Count number of insns in the target block being scheduled. */
5840 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
5844 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5846 next
= NEXT_INSN (insn
);
5848 if (INSN_DEP_COUNT (insn
) == 0
5849 && (SCHED_GROUP_P (next
) == 0 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5850 ready
[n_ready
++] = insn
;
5851 if (!(SCHED_GROUP_P (insn
)))
5855 /* Add to ready list all 'ready' insns in valid source blocks.
5856 For speculative insns, check-live, exception-free, and
5858 for (bb_src
= bb
+ 1; bb_src
< current_nr_blocks
; bb_src
++)
5859 if (IS_VALID (bb_src
))
5865 get_bb_head_tail (bb_src
, &head
, &tail
);
5866 src_next_tail
= NEXT_INSN (tail
);
5870 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
5873 for (insn
= src_head
; insn
!= src_next_tail
; insn
= NEXT_INSN (insn
))
5875 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
5878 if (!CANT_MOVE (insn
)
5879 && (!IS_SPECULATIVE_INSN (insn
)
5880 || (insn_issue_delay (insn
) <= 3
5881 && check_live (insn
, bb_src
)
5882 && is_exception_free (insn
, bb_src
, target_bb
))))
5886 /* Note that we havn't squirrled away the notes for
5887 blocks other than the current. So if this is a
5888 speculative insn, NEXT might otherwise be a note. */
5889 next
= next_nonnote_insn (insn
);
5890 if (INSN_DEP_COUNT (insn
) == 0
5892 || SCHED_GROUP_P (next
) == 0
5893 || GET_RTX_CLASS (GET_CODE (next
)) != 'i'))
5894 ready
[n_ready
++] = insn
;
5899 #ifdef MD_SCHED_INIT
5900 MD_SCHED_INIT (dump
, sched_verbose
);
5903 /* No insns scheduled in this block yet. */
5904 last_scheduled_insn
= 0;
5906 /* Q_SIZE is the total number of insns in the queue. */
5910 bzero ((char *) insn_queue
, sizeof (insn_queue
));
5912 /* Start just before the beginning of time. */
5915 /* We start inserting insns after PREV_HEAD. */
5918 /* Initialize INSN_QUEUE, LIST and NEW_NEEDS. */
5919 new_needs
= (NEXT_INSN (prev_head
) == BLOCK_HEAD (b
)
5920 ? NEED_HEAD
: NEED_NOTHING
);
5921 if (PREV_INSN (next_tail
) == BLOCK_END (b
))
5922 new_needs
|= NEED_TAIL
;
5924 /* Loop until all the insns in BB are scheduled. */
5925 while (sched_target_n_insns
< target_n_insns
)
5929 /* Add to the ready list all pending insns that can be issued now.
5930 If there are no ready insns, increment clock until one
5931 is ready and add all pending insns at that point to the ready
5933 n_ready
= queue_to_ready (ready
, n_ready
);
5938 if (sched_verbose
>= 2)
5940 fprintf (dump
, ";;\t\tReady list after queue_to_ready: ");
5941 debug_ready_list (ready
, n_ready
);
5944 /* Sort the ready list based on priority. */
5945 SCHED_SORT (ready
, n_ready
);
5947 /* Allow the target to reorder the list, typically for
5948 better instruction bundling. */
5949 #ifdef MD_SCHED_REORDER
5950 MD_SCHED_REORDER (dump
, sched_verbose
, ready
, n_ready
, clock_var
,
5953 can_issue_more
= issue_rate
;
5958 fprintf (dump
, "\n;;\tReady list (t =%3d): ", clock_var
);
5959 debug_ready_list (ready
, n_ready
);
5962 /* Issue insns from ready list. */
5963 while (n_ready
!= 0 && can_issue_more
)
5965 /* Select and remove the insn from the ready list. */
5966 rtx insn
= ready
[--n_ready
];
5967 int cost
= actual_hazard (insn_unit (insn
), insn
, clock_var
, 0);
5971 queue_insn (insn
, cost
);
5975 /* An interblock motion? */
5976 if (INSN_BB (insn
) != target_bb
)
5981 if (IS_SPECULATIVE_INSN (insn
))
5983 if (!check_live (insn
, INSN_BB (insn
)))
5985 update_live (insn
, INSN_BB (insn
));
5987 /* For speculative load, mark insns fed by it. */
5988 if (IS_LOAD_INSN (insn
) || FED_BY_SPEC_LOAD (insn
))
5989 set_spec_fed (insn
);
5995 /* Find the beginning of the scheduling group. */
5996 /* ??? Ought to update basic block here, but later bits of
5997 schedule_block assumes the original insn block is
6001 while (SCHED_GROUP_P (temp
))
6002 temp
= PREV_INSN (temp
);
6004 /* Update source block boundaries. */
6005 b1
= BLOCK_FOR_INSN (temp
);
6006 if (temp
== b1
->head
&& insn
== b1
->end
)
6008 /* We moved all the insns in the basic block.
6009 Emit a note after the last insn and update the
6010 begin/end boundaries to point to the note. */
6011 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
6015 else if (insn
== b1
->end
)
6017 /* We took insns from the end of the basic block,
6018 so update the end of block boundary so that it
6019 points to the first insn we did not move. */
6020 b1
->end
= PREV_INSN (temp
);
6022 else if (temp
== b1
->head
)
6024 /* We took insns from the start of the basic block,
6025 so update the start of block boundary so that
6026 it points to the first insn we did not move. */
6027 b1
->head
= NEXT_INSN (insn
);
6032 /* In block motion. */
6033 sched_target_n_insns
++;
6036 last_scheduled_insn
= insn
;
6037 last
= move_insn (insn
, last
);
6040 #ifdef MD_SCHED_VARIABLE_ISSUE
6041 MD_SCHED_VARIABLE_ISSUE (dump
, sched_verbose
, insn
,
6047 n_ready
= schedule_insn (insn
, ready
, n_ready
, clock_var
);
6049 /* Close this block after scheduling its jump. */
6050 if (GET_CODE (last_scheduled_insn
) == JUMP_INSN
)
6056 visualize_scheduled_insns (b
, clock_var
);
6062 fprintf (dump
, ";;\tReady list (final): ");
6063 debug_ready_list (ready
, n_ready
);
6064 print_block_visualization (b
, "");
6067 /* Sanity check -- queue must be empty now. Meaningless if region has
6069 if (current_nr_blocks
> 1)
6070 if (!flag_schedule_interblock
&& q_size
!= 0)
6073 /* Update head/tail boundaries. */
6074 head
= NEXT_INSN (prev_head
);
6077 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
6078 previously found among the insns. Insert them at the beginning
6082 rtx note_head
= note_list
;
6084 while (PREV_INSN (note_head
))
6086 note_head
= PREV_INSN (note_head
);
6089 PREV_INSN (note_head
) = PREV_INSN (head
);
6090 NEXT_INSN (PREV_INSN (head
)) = note_head
;
6091 PREV_INSN (head
) = note_list
;
6092 NEXT_INSN (note_list
) = head
;
6096 /* Update target block boundaries. */
6097 if (new_needs
& NEED_HEAD
)
6098 BLOCK_HEAD (b
) = head
;
6100 if (new_needs
& NEED_TAIL
)
6101 BLOCK_END (b
) = tail
;
6106 fprintf (dump
, ";; total time = %d\n;; new basic block head = %d\n",
6107 clock_var
, INSN_UID (BLOCK_HEAD (b
)));
6108 fprintf (dump
, ";; new basic block end = %d\n\n",
6109 INSN_UID (BLOCK_END (b
)));
6113 if (current_nr_blocks
> 1)
6115 free (candidate_table
);
6117 free (bitlst_table
);
6121 return (sched_n_insns
);
6122 } /* schedule_block () */
6125 /* Print the bit-set of registers, S, callable from debugger. */
6128 debug_reg_vector (s
)
6133 EXECUTE_IF_SET_IN_REG_SET (s
, 0, regno
,
6135 fprintf (dump
, " %d", regno
);
6138 fprintf (dump
, "\n");
6141 /* Use the backward dependences from LOG_LINKS to build
6142 forward dependences in INSN_DEPEND. */
6145 compute_block_forward_dependences (bb
)
6151 enum reg_note dep_type
;
6153 get_bb_head_tail (bb
, &head
, &tail
);
6154 next_tail
= NEXT_INSN (tail
);
6155 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6157 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6160 insn
= group_leader (insn
);
6162 for (link
= LOG_LINKS (insn
); link
; link
= XEXP (link
, 1))
6164 rtx x
= group_leader (XEXP (link
, 0));
6167 if (x
!= XEXP (link
, 0))
6170 #ifdef ENABLE_CHECKING
6171 /* If add_dependence is working properly there should never
6172 be notes, deleted insns or duplicates in the backward
6173 links. Thus we need not check for them here.
6175 However, if we have enabled checking we might as well go
6176 ahead and verify that add_dependence worked properly. */
6177 if (GET_CODE (x
) == NOTE
6178 || INSN_DELETED_P (x
)
6179 || find_insn_list (insn
, INSN_DEPEND (x
)))
6183 new_link
= alloc_INSN_LIST (insn
, INSN_DEPEND (x
));
6185 dep_type
= REG_NOTE_KIND (link
);
6186 PUT_REG_NOTE_KIND (new_link
, dep_type
);
6188 INSN_DEPEND (x
) = new_link
;
6189 INSN_DEP_COUNT (insn
) += 1;
6194 /* Initialize variables for region data dependence analysis.
6195 n_bbs is the number of region blocks. */
6197 __inline
static void
6198 init_rgn_data_dependences (n_bbs
)
6203 /* Variables for which one copy exists for each block. */
6204 bzero ((char *) bb_pending_read_insns
, n_bbs
* sizeof (rtx
));
6205 bzero ((char *) bb_pending_read_mems
, n_bbs
* sizeof (rtx
));
6206 bzero ((char *) bb_pending_write_insns
, n_bbs
* sizeof (rtx
));
6207 bzero ((char *) bb_pending_write_mems
, n_bbs
* sizeof (rtx
));
6208 bzero ((char *) bb_pending_lists_length
, n_bbs
* sizeof (int));
6209 bzero ((char *) bb_last_pending_memory_flush
, n_bbs
* sizeof (rtx
));
6210 bzero ((char *) bb_last_function_call
, n_bbs
* sizeof (rtx
));
6211 bzero ((char *) bb_sched_before_next_call
, n_bbs
* sizeof (rtx
));
6213 /* Create an insn here so that we can hang dependencies off of it later. */
6214 for (bb
= 0; bb
< n_bbs
; bb
++)
6216 bb_sched_before_next_call
[bb
] =
6217 gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6218 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6219 LOG_LINKS (bb_sched_before_next_call
[bb
]) = 0;
6223 /* Add dependences so that branches are scheduled to run last in their
6227 add_branch_dependences (head
, tail
)
6233 /* For all branches, calls, uses, clobbers, and cc0 setters, force them
6234 to remain in order at the end of the block by adding dependencies and
6235 giving the last a high priority. There may be notes present, and
6236 prev_head may also be a note.
6238 Branches must obviously remain at the end. Calls should remain at the
6239 end since moving them results in worse register allocation. Uses remain
6240 at the end to ensure proper register allocation. cc0 setters remaim
6241 at the end because they can't be moved away from their cc0 user. */
6244 while (GET_CODE (insn
) == CALL_INSN
6245 || GET_CODE (insn
) == JUMP_INSN
6246 || (GET_CODE (insn
) == INSN
6247 && (GET_CODE (PATTERN (insn
)) == USE
6248 || GET_CODE (PATTERN (insn
)) == CLOBBER
6250 || sets_cc0_p (PATTERN (insn
))
6253 || GET_CODE (insn
) == NOTE
)
6255 if (GET_CODE (insn
) != NOTE
)
6258 && !find_insn_list (insn
, LOG_LINKS (last
)))
6260 add_dependence (last
, insn
, REG_DEP_ANTI
);
6261 INSN_REF_COUNT (insn
)++;
6264 CANT_MOVE (insn
) = 1;
6267 /* Skip over insns that are part of a group.
6268 Make each insn explicitly depend on the previous insn.
6269 This ensures that only the group header will ever enter
6270 the ready queue (and, when scheduled, will automatically
6271 schedule the SCHED_GROUP_P block). */
6272 while (SCHED_GROUP_P (insn
))
6274 rtx temp
= prev_nonnote_insn (insn
);
6275 add_dependence (insn
, temp
, REG_DEP_ANTI
);
6280 /* Don't overrun the bounds of the basic block. */
6284 insn
= PREV_INSN (insn
);
6287 /* Make sure these insns are scheduled last in their block. */
6290 while (insn
!= head
)
6292 insn
= prev_nonnote_insn (insn
);
6294 if (INSN_REF_COUNT (insn
) != 0)
6297 add_dependence (last
, insn
, REG_DEP_ANTI
);
6298 INSN_REF_COUNT (insn
) = 1;
6300 /* Skip over insns that are part of a group. */
6301 while (SCHED_GROUP_P (insn
))
6302 insn
= prev_nonnote_insn (insn
);
6306 /* Compute backward dependences inside bb. In a multiple blocks region:
6307 (1) a bb is analyzed after its predecessors, and (2) the lists in
6308 effect at the end of bb (after analyzing for bb) are inherited by
6311 Specifically for reg-reg data dependences, the block insns are
6312 scanned by sched_analyze () top-to-bottom. Two lists are
6313 maintained by sched_analyze (): reg_last_sets[] for register DEFs,
6314 and reg_last_uses[] for register USEs.
6316 When analysis is completed for bb, we update for its successors:
6317 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
6318 ; - USES[succ] = Union (USES [succ], DEFS [bb])
6320 The mechanism for computing mem-mem data dependence is very
6321 similar, and the result is interblock dependences in the region. */
6324 compute_block_backward_dependences (bb
)
6330 int max_reg
= max_reg_num ();
6332 b
= BB_TO_BLOCK (bb
);
6334 if (current_nr_blocks
== 1)
6336 reg_last_uses
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6337 reg_last_sets
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6338 reg_last_clobbers
= (rtx
*) xcalloc (max_reg
, sizeof (rtx
));
6340 pending_read_insns
= 0;
6341 pending_read_mems
= 0;
6342 pending_write_insns
= 0;
6343 pending_write_mems
= 0;
6344 pending_lists_length
= 0;
6345 last_function_call
= 0;
6346 last_pending_memory_flush
= 0;
6347 sched_before_next_call
6348 = gen_rtx_INSN (VOIDmode
, 0, NULL_RTX
, NULL_RTX
,
6349 NULL_RTX
, 0, NULL_RTX
, NULL_RTX
);
6350 LOG_LINKS (sched_before_next_call
) = 0;
6354 reg_last_uses
= bb_reg_last_uses
[bb
];
6355 reg_last_sets
= bb_reg_last_sets
[bb
];
6356 reg_last_clobbers
= bb_reg_last_clobbers
[bb
];
6358 pending_read_insns
= bb_pending_read_insns
[bb
];
6359 pending_read_mems
= bb_pending_read_mems
[bb
];
6360 pending_write_insns
= bb_pending_write_insns
[bb
];
6361 pending_write_mems
= bb_pending_write_mems
[bb
];
6362 pending_lists_length
= bb_pending_lists_length
[bb
];
6363 last_function_call
= bb_last_function_call
[bb
];
6364 last_pending_memory_flush
= bb_last_pending_memory_flush
[bb
];
6366 sched_before_next_call
= bb_sched_before_next_call
[bb
];
6369 /* Do the analysis for this block. */
6370 get_bb_head_tail (bb
, &head
, &tail
);
6371 sched_analyze (head
, tail
);
6372 add_branch_dependences (head
, tail
);
6374 if (current_nr_blocks
> 1)
6377 int b_succ
, bb_succ
;
6379 rtx link_insn
, link_mem
;
6382 /* These lists should point to the right place, for correct
6384 bb_pending_read_insns
[bb
] = pending_read_insns
;
6385 bb_pending_read_mems
[bb
] = pending_read_mems
;
6386 bb_pending_write_insns
[bb
] = pending_write_insns
;
6387 bb_pending_write_mems
[bb
] = pending_write_mems
;
6389 /* bb's structures are inherited by it's successors. */
6390 first_edge
= e
= OUT_EDGES (b
);
6394 b_succ
= TO_BLOCK (e
);
6395 bb_succ
= BLOCK_TO_BB (b_succ
);
6397 /* Only bbs "below" bb, in the same region, are interesting. */
6398 if (CONTAINING_RGN (b
) != CONTAINING_RGN (b_succ
)
6405 for (reg
= 0; reg
< max_reg
; reg
++)
6408 /* reg-last-uses lists are inherited by bb_succ. */
6409 for (u
= reg_last_uses
[reg
]; u
; u
= XEXP (u
, 1))
6411 if (find_insn_list (XEXP (u
, 0),
6412 (bb_reg_last_uses
[bb_succ
])[reg
]))
6415 (bb_reg_last_uses
[bb_succ
])[reg
]
6416 = alloc_INSN_LIST (XEXP (u
, 0),
6417 (bb_reg_last_uses
[bb_succ
])[reg
]);
6420 /* reg-last-defs lists are inherited by bb_succ. */
6421 for (u
= reg_last_sets
[reg
]; u
; u
= XEXP (u
, 1))
6423 if (find_insn_list (XEXP (u
, 0),
6424 (bb_reg_last_sets
[bb_succ
])[reg
]))
6427 (bb_reg_last_sets
[bb_succ
])[reg
]
6428 = alloc_INSN_LIST (XEXP (u
, 0),
6429 (bb_reg_last_sets
[bb_succ
])[reg
]);
6432 for (u
= reg_last_clobbers
[reg
]; u
; u
= XEXP (u
, 1))
6434 if (find_insn_list (XEXP (u
, 0),
6435 (bb_reg_last_clobbers
[bb_succ
])[reg
]))
6438 (bb_reg_last_clobbers
[bb_succ
])[reg
]
6439 = alloc_INSN_LIST (XEXP (u
, 0),
6440 (bb_reg_last_clobbers
[bb_succ
])[reg
]);
6444 /* Mem read/write lists are inherited by bb_succ. */
6445 link_insn
= pending_read_insns
;
6446 link_mem
= pending_read_mems
;
6449 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6451 bb_pending_read_insns
[bb_succ
],
6452 bb_pending_read_mems
[bb_succ
])))
6453 add_insn_mem_dependence (&bb_pending_read_insns
[bb_succ
],
6454 &bb_pending_read_mems
[bb_succ
],
6455 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6456 link_insn
= XEXP (link_insn
, 1);
6457 link_mem
= XEXP (link_mem
, 1);
6460 link_insn
= pending_write_insns
;
6461 link_mem
= pending_write_mems
;
6464 if (!(find_insn_mem_list (XEXP (link_insn
, 0),
6466 bb_pending_write_insns
[bb_succ
],
6467 bb_pending_write_mems
[bb_succ
])))
6468 add_insn_mem_dependence (&bb_pending_write_insns
[bb_succ
],
6469 &bb_pending_write_mems
[bb_succ
],
6470 XEXP (link_insn
, 0), XEXP (link_mem
, 0));
6472 link_insn
= XEXP (link_insn
, 1);
6473 link_mem
= XEXP (link_mem
, 1);
6476 /* last_function_call is inherited by bb_succ. */
6477 for (u
= last_function_call
; u
; u
= XEXP (u
, 1))
6479 if (find_insn_list (XEXP (u
, 0),
6480 bb_last_function_call
[bb_succ
]))
6483 bb_last_function_call
[bb_succ
]
6484 = alloc_INSN_LIST (XEXP (u
, 0),
6485 bb_last_function_call
[bb_succ
]);
6488 /* last_pending_memory_flush is inherited by bb_succ. */
6489 for (u
= last_pending_memory_flush
; u
; u
= XEXP (u
, 1))
6491 if (find_insn_list (XEXP (u
, 0),
6492 bb_last_pending_memory_flush
[bb_succ
]))
6495 bb_last_pending_memory_flush
[bb_succ
]
6496 = alloc_INSN_LIST (XEXP (u
, 0),
6497 bb_last_pending_memory_flush
[bb_succ
]);
6500 /* sched_before_next_call is inherited by bb_succ. */
6501 x
= LOG_LINKS (sched_before_next_call
);
6502 for (; x
; x
= XEXP (x
, 1))
6503 add_dependence (bb_sched_before_next_call
[bb_succ
],
6504 XEXP (x
, 0), REG_DEP_ANTI
);
6508 while (e
!= first_edge
);
6511 /* Free up the INSN_LISTs.
6513 Note this loop is executed max_reg * nr_regions times. It's first
6514 implementation accounted for over 90% of the calls to free_INSN_LIST_list.
6515 The list was empty for the vast majority of those calls. On the PA, not
6516 calling free_INSN_LIST_list in those cases improves -O2 compile times by
6518 for (b
= 0; b
< max_reg
; ++b
)
6520 if (reg_last_clobbers
[b
])
6521 free_INSN_LIST_list (®_last_clobbers
[b
]);
6522 if (reg_last_sets
[b
])
6523 free_INSN_LIST_list (®_last_sets
[b
]);
6524 if (reg_last_uses
[b
])
6525 free_INSN_LIST_list (®_last_uses
[b
]);
6528 /* Assert that we won't need bb_reg_last_* for this block anymore. */
6529 if (current_nr_blocks
> 1)
6531 bb_reg_last_uses
[bb
] = (rtx
*) NULL_RTX
;
6532 bb_reg_last_sets
[bb
] = (rtx
*) NULL_RTX
;
6533 bb_reg_last_clobbers
[bb
] = (rtx
*) NULL_RTX
;
6535 else if (current_nr_blocks
== 1)
6537 free (reg_last_uses
);
6538 free (reg_last_sets
);
6539 free (reg_last_clobbers
);
6543 /* Print dependences for debugging, callable from debugger. */
6546 debug_dependencies ()
6550 fprintf (dump
, ";; --------------- forward dependences: ------------ \n");
6551 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6559 get_bb_head_tail (bb
, &head
, &tail
);
6560 next_tail
= NEXT_INSN (tail
);
6561 fprintf (dump
, "\n;; --- Region Dependences --- b %d bb %d \n",
6562 BB_TO_BLOCK (bb
), bb
);
6564 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6565 "insn", "code", "bb", "dep", "prio", "cost", "blockage", "units");
6566 fprintf (dump
, ";; %7s%6s%6s%6s%6s%6s%11s%6s\n",
6567 "----", "----", "--", "---", "----", "----", "--------", "-----");
6568 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
6573 if (GET_RTX_CLASS (GET_CODE (insn
)) != 'i')
6576 fprintf (dump
, ";; %6d ", INSN_UID (insn
));
6577 if (GET_CODE (insn
) == NOTE
)
6579 n
= NOTE_LINE_NUMBER (insn
);
6581 fprintf (dump
, "%s\n", GET_NOTE_INSN_NAME (n
));
6583 fprintf (dump
, "line %d, file %s\n", n
,
6584 NOTE_SOURCE_FILE (insn
));
6587 fprintf (dump
, " {%s}\n", GET_RTX_NAME (GET_CODE (insn
)));
6591 unit
= insn_unit (insn
);
6593 || function_units
[unit
].blockage_range_function
== 0) ? 0 :
6594 function_units
[unit
].blockage_range_function (insn
);
6596 ";; %s%5d%6d%6d%6d%6d%6d %3d -%3d ",
6597 (SCHED_GROUP_P (insn
) ? "+" : " "),
6601 INSN_DEP_COUNT (insn
),
6602 INSN_PRIORITY (insn
),
6603 insn_cost (insn
, 0, 0),
6604 (int) MIN_BLOCKAGE_COST (range
),
6605 (int) MAX_BLOCKAGE_COST (range
));
6606 insn_print_units (insn
);
6607 fprintf (dump
, "\t: ");
6608 for (link
= INSN_DEPEND (insn
); link
; link
= XEXP (link
, 1))
6609 fprintf (dump
, "%d ", INSN_UID (XEXP (link
, 0)));
6610 fprintf (dump
, "\n");
6614 fprintf (dump
, "\n");
6617 /* Set_priorities: compute priority of each insn in the block. */
6630 get_bb_head_tail (bb
, &head
, &tail
);
6631 prev_head
= PREV_INSN (head
);
6634 && (GET_RTX_CLASS (GET_CODE (head
)) != 'i'))
6638 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
6641 if (GET_CODE (insn
) == NOTE
)
6644 if (!(SCHED_GROUP_P (insn
)))
6646 (void) priority (insn
);
6652 /* Make each element of VECTOR point at an rtx-vector,
6653 taking the space for all those rtx-vectors from SPACE.
6654 SPACE is of type (rtx *), but it is really as long as NELTS rtx-vectors.
6655 BYTES_PER_ELT is the number of bytes in one rtx-vector.
6656 (this is the same as init_regset_vector () in flow.c) */
6659 init_rtx_vector (vector
, space
, nelts
, bytes_per_elt
)
6666 register rtx
*p
= space
;
6668 for (i
= 0; i
< nelts
; i
++)
6671 p
+= bytes_per_elt
/ sizeof (*p
);
6675 /* Schedule a region. A region is either an inner loop, a loop-free
6676 subroutine, or a single basic block. Each bb in the region is
6677 scheduled after its flow predecessors. */
6680 schedule_region (rgn
)
6684 int rgn_n_insns
= 0;
6685 int sched_rgn_n_insns
= 0;
6686 rtx
*bb_reg_last_uses_space
= NULL
;
6687 rtx
*bb_reg_last_sets_space
= NULL
;
6688 rtx
*bb_reg_last_clobbers_space
= NULL
;
6690 /* Set variables for the current region. */
6691 current_nr_blocks
= RGN_NR_BLOCKS (rgn
);
6692 current_blocks
= RGN_BLOCKS (rgn
);
6694 reg_pending_sets
= ALLOCA_REG_SET ();
6695 reg_pending_clobbers
= ALLOCA_REG_SET ();
6696 reg_pending_sets_all
= 0;
6698 /* Initializations for region data dependence analyisis. */
6699 if (current_nr_blocks
> 1)
6701 int maxreg
= max_reg_num ();
6703 bb_reg_last_uses
= (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6704 bb_reg_last_uses_space
6705 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6706 init_rtx_vector (bb_reg_last_uses
, bb_reg_last_uses_space
,
6707 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6709 bb_reg_last_sets
= (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6710 bb_reg_last_sets_space
6711 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6712 init_rtx_vector (bb_reg_last_sets
, bb_reg_last_sets_space
,
6713 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6715 bb_reg_last_clobbers
=
6716 (rtx
**) xmalloc (current_nr_blocks
* sizeof (rtx
*));
6717 bb_reg_last_clobbers_space
6718 = (rtx
*) xcalloc (current_nr_blocks
* maxreg
, sizeof (rtx
));
6719 init_rtx_vector (bb_reg_last_clobbers
, bb_reg_last_clobbers_space
,
6720 current_nr_blocks
, maxreg
* sizeof (rtx
*));
6722 bb_pending_read_insns
6723 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6724 bb_pending_read_mems
6725 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6726 bb_pending_write_insns
=
6727 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6728 bb_pending_write_mems
6729 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6730 bb_pending_lists_length
=
6731 (int *) xmalloc (current_nr_blocks
* sizeof (int));
6732 bb_last_pending_memory_flush
=
6733 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6734 bb_last_function_call
6735 = (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6736 bb_sched_before_next_call
=
6737 (rtx
*) xmalloc (current_nr_blocks
* sizeof (rtx
));
6739 init_rgn_data_dependences (current_nr_blocks
);
6742 /* Compute LOG_LINKS. */
6743 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6744 compute_block_backward_dependences (bb
);
6746 /* Compute INSN_DEPEND. */
6747 for (bb
= current_nr_blocks
- 1; bb
>= 0; bb
--)
6748 compute_block_forward_dependences (bb
);
6750 /* Delete line notes and set priorities. */
6751 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6753 if (write_symbols
!= NO_DEBUG
)
6755 save_line_notes (bb
);
6759 rgn_n_insns
+= set_priorities (bb
);
6762 /* Compute interblock info: probabilities, split-edges, dominators, etc. */
6763 if (current_nr_blocks
> 1)
6767 prob
= (float *) xmalloc ((current_nr_blocks
) * sizeof (float));
6769 bbset_size
= current_nr_blocks
/ HOST_BITS_PER_WIDE_INT
+ 1;
6770 dom
= (bbset
*) xmalloc (current_nr_blocks
* sizeof (bbset
));
6771 for (i
= 0; i
< current_nr_blocks
; i
++)
6772 dom
[i
] = (bbset
) xcalloc (bbset_size
, sizeof (HOST_WIDE_INT
));
6776 edge_to_bit
= (int *) xmalloc (nr_edges
* sizeof (int));
6777 for (i
= 1; i
< nr_edges
; i
++)
6778 if (CONTAINING_RGN (FROM_BLOCK (i
)) == rgn
)
6779 EDGE_TO_BIT (i
) = rgn_nr_edges
++;
6780 rgn_edges
= (int *) xmalloc (rgn_nr_edges
* sizeof (int));
6783 for (i
= 1; i
< nr_edges
; i
++)
6784 if (CONTAINING_RGN (FROM_BLOCK (i
)) == (rgn
))
6785 rgn_edges
[rgn_nr_edges
++] = i
;
6788 edgeset_size
= rgn_nr_edges
/ HOST_BITS_PER_WIDE_INT
+ 1;
6789 pot_split
= (edgeset
*) xmalloc (current_nr_blocks
* sizeof (edgeset
));
6791 = (edgeset
*) xmalloc (current_nr_blocks
* sizeof (edgeset
));
6792 for (i
= 0; i
< current_nr_blocks
; i
++)
6795 (edgeset
) xcalloc (edgeset_size
, sizeof (HOST_WIDE_INT
));
6797 (edgeset
) xcalloc (edgeset_size
, sizeof (HOST_WIDE_INT
));
6800 /* Compute probabilities, dominators, split_edges. */
6801 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6802 compute_dom_prob_ps (bb
);
6805 /* Now we can schedule all blocks. */
6806 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6807 sched_rgn_n_insns
+= schedule_block (bb
, rgn_n_insns
);
6809 /* Sanity check: verify that all region insns were scheduled. */
6810 if (sched_rgn_n_insns
!= rgn_n_insns
)
6813 /* Restore line notes. */
6814 if (write_symbols
!= NO_DEBUG
)
6816 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
6817 restore_line_notes (bb
);
6820 /* Done with this region. */
6821 free_pending_lists ();
6823 FREE_REG_SET (reg_pending_sets
);
6824 FREE_REG_SET (reg_pending_clobbers
);
6826 if (current_nr_blocks
> 1)
6830 free (bb_reg_last_uses_space
);
6831 free (bb_reg_last_uses
);
6832 free (bb_reg_last_sets_space
);
6833 free (bb_reg_last_sets
);
6834 free (bb_reg_last_clobbers_space
);
6835 free (bb_reg_last_clobbers
);
6836 free (bb_pending_read_insns
);
6837 free (bb_pending_read_mems
);
6838 free (bb_pending_write_insns
);
6839 free (bb_pending_write_mems
);
6840 free (bb_pending_lists_length
);
6841 free (bb_last_pending_memory_flush
);
6842 free (bb_last_function_call
);
6843 free (bb_sched_before_next_call
);
6845 for (i
= 0; i
< current_nr_blocks
; ++i
)
6848 free (pot_split
[i
]);
6849 free (ancestor_edges
[i
]);
6855 free (ancestor_edges
);
6859 /* The one entry point in this file. DUMP_FILE is the dump file for
6863 schedule_insns (dump_file
)
6866 int *deaths_in_region
;
6867 sbitmap blocks
, large_region_blocks
;
6873 int any_large_regions
;
6875 /* Disable speculative loads in their presence if cc0 defined. */
6877 flag_schedule_speculative_load
= 0;
6880 /* Taking care of this degenerate case makes the rest of
6881 this code simpler. */
6882 if (n_basic_blocks
== 0)
6885 /* Set dump and sched_verbose for the desired debugging output. If no
6886 dump-file was specified, but -fsched-verbose-N (any N), print to stderr.
6887 For -fsched-verbose-N, N>=10, print everything to stderr. */
6888 sched_verbose
= sched_verbose_param
;
6889 if (sched_verbose_param
== 0 && dump_file
)
6891 dump
= ((sched_verbose_param
>= 10 || !dump_file
) ? stderr
: dump_file
);
6896 /* Initialize issue_rate. */
6897 issue_rate
= ISSUE_RATE
;
6899 split_all_insns (1);
6901 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
6902 pseudos which do not cross calls. */
6903 max_uid
= get_max_uid () + 1;
6905 h_i_d
= (struct haifa_insn_data
*) xcalloc (max_uid
, sizeof (*h_i_d
));
6909 for (b
= 0; b
< n_basic_blocks
; b
++)
6910 for (insn
= BLOCK_HEAD (b
);; insn
= NEXT_INSN (insn
))
6912 INSN_LUID (insn
) = luid
;
6914 /* Increment the next luid, unless this is a note. We don't
6915 really need separate IDs for notes and we don't want to
6916 schedule differently depending on whether or not there are
6917 line-number notes, i.e., depending on whether or not we're
6918 generating debugging information. */
6919 if (GET_CODE (insn
) != NOTE
)
6922 if (insn
== BLOCK_END (b
))
6926 /* ?!? We could save some memory by computing a per-region luid mapping
6927 which could reduce both the number of vectors in the cache and the size
6928 of each vector. Instead we just avoid the cache entirely unless the
6929 average number of instructions in a basic block is very high. See
6930 the comment before the declaration of true_dependency_cache for
6931 what we consider "very high". */
6932 if (luid
/ n_basic_blocks
> 100 * 5)
6934 true_dependency_cache
= sbitmap_vector_alloc (luid
, luid
);
6935 sbitmap_vector_zero (true_dependency_cache
, luid
);
6939 rgn_table
= (region
*) xmalloc ((n_basic_blocks
) * sizeof (region
));
6940 rgn_bb_table
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6941 block_to_bb
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6942 containing_rgn
= (int *) xmalloc ((n_basic_blocks
) * sizeof (int));
6944 blocks
= sbitmap_alloc (n_basic_blocks
);
6945 large_region_blocks
= sbitmap_alloc (n_basic_blocks
);
6947 compute_bb_for_insn (max_uid
);
6949 /* Compute regions for scheduling. */
6950 if (reload_completed
6951 || n_basic_blocks
== 1
6952 || !flag_schedule_interblock
)
6954 find_single_block_region ();
6958 /* Verify that a 'good' control flow graph can be built. */
6959 if (is_cfg_nonregular ())
6961 find_single_block_region ();
6966 struct edge_list
*edge_list
;
6968 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
6970 /* The scheduler runs after flow; therefore, we can't blindly call
6971 back into find_basic_blocks since doing so could invalidate the
6972 info in global_live_at_start.
6974 Consider a block consisting entirely of dead stores; after life
6975 analysis it would be a block of NOTE_INSN_DELETED notes. If
6976 we call find_basic_blocks again, then the block would be removed
6977 entirely and invalidate our the register live information.
6979 We could (should?) recompute register live information. Doing
6980 so may even be beneficial. */
6981 edge_list
= create_edge_list ();
6983 /* Compute the dominators and post dominators. We don't
6984 currently use post dominators, but we should for
6985 speculative motion analysis. */
6986 compute_flow_dominators (dom
, NULL
);
6988 /* build_control_flow will return nonzero if it detects unreachable
6989 blocks or any other irregularity with the cfg which prevents
6990 cross block scheduling. */
6991 if (build_control_flow (edge_list
) != 0)
6992 find_single_block_region ();
6994 find_rgns (edge_list
, dom
);
6996 if (sched_verbose
>= 3)
6999 /* For now. This will move as more and more of haifa is converted
7000 to using the cfg code in flow.c. */
7005 deaths_in_region
= (int *) xmalloc (sizeof(int) * nr_regions
);
7007 init_alias_analysis ();
7009 if (write_symbols
!= NO_DEBUG
)
7013 line_note_head
= (rtx
*) xcalloc (n_basic_blocks
, sizeof (rtx
));
7015 /* Save-line-note-head:
7016 Determine the line-number at the start of each basic block.
7017 This must be computed and saved now, because after a basic block's
7018 predecessor has been scheduled, it is impossible to accurately
7019 determine the correct line number for the first insn of the block. */
7021 for (b
= 0; b
< n_basic_blocks
; b
++)
7022 for (line
= BLOCK_HEAD (b
); line
; line
= PREV_INSN (line
))
7023 if (GET_CODE (line
) == NOTE
&& NOTE_LINE_NUMBER (line
) > 0)
7025 line_note_head
[b
] = line
;
7030 /* Find units used in this fuction, for visualization. */
7032 init_target_units ();
7034 /* ??? Add a NOTE after the last insn of the last basic block. It is not
7035 known why this is done. */
7037 insn
= BLOCK_END (n_basic_blocks
- 1);
7038 if (NEXT_INSN (insn
) == 0
7039 || (GET_CODE (insn
) != NOTE
7040 && GET_CODE (insn
) != CODE_LABEL
7041 /* Don't emit a NOTE if it would end up between an unconditional
7042 jump and a BARRIER. */
7043 && !(GET_CODE (insn
) == JUMP_INSN
7044 && GET_CODE (NEXT_INSN (insn
)) == BARRIER
)))
7045 emit_note_after (NOTE_INSN_DELETED
, BLOCK_END (n_basic_blocks
- 1));
7047 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
7048 removing death notes. */
7049 for (b
= n_basic_blocks
- 1; b
>= 0; b
--)
7050 find_insn_reg_weight (b
);
7052 /* Remove all death notes from the subroutine. */
7053 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7055 sbitmap_zero (blocks
);
7056 for (b
= RGN_NR_BLOCKS (rgn
) - 1; b
>= 0; --b
)
7057 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
) + b
]);
7059 deaths_in_region
[rgn
] = count_or_remove_death_notes (blocks
, 1);
7062 /* Schedule every region in the subroutine. */
7063 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7064 schedule_region (rgn
);
7066 /* Update life analysis for the subroutine. Do single block regions
7067 first so that we can verify that live_at_start didn't change. Then
7068 do all other blocks. */
7069 /* ??? There is an outside possibility that update_life_info, or more
7070 to the point propagate_block, could get called with non-zero flags
7071 more than once for one basic block. This would be kinda bad if it
7072 were to happen, since REG_INFO would be accumulated twice for the
7073 block, and we'd have twice the REG_DEAD notes.
7075 I'm fairly certain that this _shouldn't_ happen, since I don't think
7076 that live_at_start should change at region heads. Not sure what the
7077 best way to test for this kind of thing... */
7079 allocate_reg_life_data ();
7080 compute_bb_for_insn (max_uid
);
7082 any_large_regions
= 0;
7083 sbitmap_ones (large_region_blocks
);
7085 for (rgn
= 0; rgn
< nr_regions
; rgn
++)
7086 if (RGN_NR_BLOCKS (rgn
) > 1)
7087 any_large_regions
= 1;
7090 sbitmap_zero (blocks
);
7091 SET_BIT (blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7092 RESET_BIT (large_region_blocks
, rgn_bb_table
[RGN_BLOCKS (rgn
)]);
7094 update_life_info (blocks
, UPDATE_LIFE_LOCAL
,
7095 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7097 /* In the single block case, the count of registers that died should
7098 not have changed during the schedule. */
7099 if (count_or_remove_death_notes (blocks
, 0) != deaths_in_region
[rgn
])
7103 if (any_large_regions
)
7105 update_life_info (large_region_blocks
, UPDATE_LIFE_GLOBAL
,
7106 PROP_DEATH_NOTES
| PROP_REG_INFO
);
7109 /* Reposition the prologue and epilogue notes in case we moved the
7110 prologue/epilogue insns. */
7111 if (reload_completed
)
7112 reposition_prologue_and_epilogue_notes (get_insns ());
7114 /* Delete redundant line notes. */
7115 if (write_symbols
!= NO_DEBUG
)
7116 rm_redundant_line_notes ();
7120 if (reload_completed
== 0 && flag_schedule_interblock
)
7122 fprintf (dump
, "\n;; Procedure interblock/speculative motions == %d/%d \n",
7130 fprintf (dump
, "\n\n");
7134 end_alias_analysis ();
7136 if (true_dependency_cache
)
7138 free (true_dependency_cache
);
7139 true_dependency_cache
= NULL
;
7142 free (rgn_bb_table
);
7144 free (containing_rgn
);
7148 if (write_symbols
!= NO_DEBUG
)
7149 free (line_note_head
);
7168 sbitmap_free (blocks
);
7169 sbitmap_free (large_region_blocks
);
7171 free (deaths_in_region
);
7174 #endif /* INSN_SCHEDULING */