1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* Pointer to data describing the current DFA state. */
24 extern state_t curr_state
;
26 /* Forward declaration. */
29 /* Describe state of dependencies used during sched_analyze phase. */
32 /* The *_insns and *_mems are paired lists. Each pending memory operation
33 will have a pointer to the MEM rtx on one list and a pointer to the
34 containing insn on the other list in the same place in the list. */
36 /* We can't use add_dependence like the old code did, because a single insn
37 may have multiple memory accesses, and hence needs to be on the list
38 once for each memory access. Add_dependence won't let you add an insn
39 to a list more than once. */
41 /* An INSN_LIST containing all insns with pending read operations. */
42 rtx pending_read_insns
;
44 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
45 rtx pending_read_mems
;
47 /* An INSN_LIST containing all insns with pending write operations. */
48 rtx pending_write_insns
;
50 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
51 rtx pending_write_mems
;
53 /* Indicates the combined length of the two pending lists. We must prevent
54 these lists from ever growing too large since the number of dependencies
55 produced is at least O(N*N), and execution time is at least O(4*N*N), as
56 a function of the length of these pending lists. */
57 int pending_lists_length
;
59 /* Length of the pending memory flush list. Large functions with no
60 calls may build up extremely large lists. */
61 int pending_flush_length
;
63 /* The last insn upon which all memory references must depend.
64 This is an insn which flushed the pending lists, creating a dependency
65 between it and all previously pending memory references. This creates
66 a barrier (or a checkpoint) which no memory reference is allowed to cross.
68 This includes all non constant CALL_INSNs. When we do interprocedural
69 alias analysis, this restriction can be relaxed.
70 This may also be an INSN that writes memory if the pending lists grow
72 rtx last_pending_memory_flush
;
74 /* A list of the last function calls we have seen. We use a list to
75 represent last function calls from multiple predecessor blocks.
76 Used to prevent register lifetimes from expanding unnecessarily. */
77 rtx last_function_call
;
79 /* A list of insns which use a pseudo register that does not already
80 cross a call. We create dependencies between each of those insn
81 and the next call insn, to ensure that they won't cross a call after
82 scheduling is done. */
83 rtx sched_before_next_call
;
85 /* Used to keep post-call psuedo/hard reg movements together with
87 bool in_post_call_group_p
;
89 /* Set to the tail insn of the outermost libcall block.
91 When nonzero, we will mark each insn processed by sched_analyze_insn
92 with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */
93 rtx libcall_block_tail_insn
;
95 /* The maximum register number for the following arrays. Before reload
96 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
99 /* Element N is the next insn that sets (hard or pseudo) register
100 N within the current basic block; or zero, if there is no
101 such insn. Needed for new registers which may be introduced
102 by splitting insns. */
112 /* Element N is set for each register that has any nonzero element
113 in reg_last[N].{uses,sets,clobbers}. */
114 regset_head reg_last_in_use
;
117 /* This structure holds some state of the current scheduling pass, and
118 contains some function pointers that abstract out some of the non-generic
119 functionality from functions such as schedule_block or schedule_insn.
120 There is one global variable, current_sched_info, which points to the
121 sched_info structure currently in use. */
124 /* Add all insns that are initially ready to the ready list. Called once
125 before scheduling a set of insns. */
126 void (*init_ready_list
) PARAMS ((struct ready_list
*));
127 /* Called after taking an insn from the ready list. Returns nonzero if
128 this insn can be scheduled, nonzero if we should silently discard it. */
129 int (*can_schedule_ready_p
) PARAMS ((rtx
));
130 /* Return nonzero if there are more insns that should be scheduled. */
131 int (*schedule_more_p
) PARAMS ((void));
132 /* Called after an insn has all its dependencies resolved. Return nonzero
133 if it should be moved to the ready list or the queue, or zero if we
134 should silently discard it. */
135 int (*new_ready
) PARAMS ((rtx
));
136 /* Compare priority of two insns. Return a positive number if the second
137 insn is to be preferred for scheduling, and a negative one if the first
138 is to be preferred. Zero if they are equally good. */
139 int (*rank
) PARAMS ((rtx
, rtx
));
140 /* Return a string that contains the insn uid and optionally anything else
141 necessary to identify this insn in an output. It's valid to use a
142 static buffer for this. The ALIGNED parameter should cause the string
143 to be formatted so that multiple output lines will line up nicely. */
144 const char *(*print_insn
) PARAMS ((rtx
, int));
145 /* Return nonzero if an insn should be included in priority
147 int (*contributes_to_priority
) PARAMS ((rtx
, rtx
));
148 /* Called when computing dependencies for a JUMP_INSN. This function
149 should store the set of registers that must be considered as set by
150 the jump in the regset. */
151 void (*compute_jump_reg_dependencies
) PARAMS ((rtx
, regset
));
153 /* The boundaries of the set of insns to be scheduled. */
154 rtx prev_head
, next_tail
;
156 /* Filled in after the schedule is finished; the first and last scheduled
160 /* If nonzero, enables an additional sanity check in schedule_block. */
161 unsigned int queue_must_finish_empty
:1;
162 /* Nonzero if we should use cselib for better alias analysis. This
163 must be 0 if the dependency information is used after sched_analyze
164 has completed, e.g. if we're using it to initialize state for successor
165 blocks in region scheduling. */
166 unsigned int use_cselib
:1;
169 extern struct sched_info
*current_sched_info
;
171 /* Indexed by INSN_UID, the collection of all data associated with
172 a single instruction. */
174 struct haifa_insn_data
176 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
177 it represents forward dependencies. */
180 /* The line number note in effect for each insn. For line number
181 notes, this indicates whether the note may be reused. */
184 /* Logical uid gives the original ordering of the insns. */
187 /* A priority for each insn. */
190 /* The number of incoming edges in the forward dependency graph.
191 As scheduling proceds, counts are decreased. An insn moves to
192 the ready queue when its counter reaches zero. */
195 /* An encoding of the blockage range function. Both unit and range
196 are coded. This member is used only for old pipeline interface. */
197 unsigned int blockage
;
199 /* Number of instructions referring to this insn. */
202 /* The minimum clock tick at which the insn becomes ready. This is
203 used to note timing constraints for the insns in the pending list. */
208 /* An encoding of the function units used. This member is used only
209 for old pipeline interface. */
212 /* This weight is an estimation of the insn's contribution to
213 register pressure. */
216 /* Some insns (e.g. call) are not allowed to move across blocks. */
217 unsigned int cant_move
: 1;
219 /* Set if there's DEF-USE dependence between some speculatively
220 moved load insn and this one. */
221 unsigned int fed_by_spec_load
: 1;
222 unsigned int is_load_insn
: 1;
224 /* Nonzero if priority has been computed already. */
225 unsigned int priority_known
: 1;
228 extern struct haifa_insn_data
*h_i_d
;
230 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
232 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
233 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
234 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
235 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
236 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
237 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
238 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
239 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
240 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
242 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
244 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
245 #define ENCODE_BLOCKAGE(U, R) \
246 (((U) << BLOCKAGE_BITS \
247 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
248 | MAX_BLOCKAGE_COST (R))
249 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
250 #define BLOCKAGE_RANGE(B) \
251 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
252 | ((B) & BLOCKAGE_MASK))
254 /* Encodings of the `<name>_unit_blockage_range' function. */
255 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
256 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
258 extern FILE *sched_dump
;
259 extern int sched_verbose
;
261 /* Exception Free Loads:
263 We define five classes of speculative loads: IFREE, IRISKY,
264 PFREE, PRISKY, and MFREE.
266 IFREE loads are loads that are proved to be exception-free, just
267 by examining the load insn. Examples for such loads are loads
268 from TOC and loads of global data.
270 IRISKY loads are loads that are proved to be exception-risky,
271 just by examining the load insn. Examples for such loads are
272 volatile loads and loads from shared memory.
274 PFREE loads are loads for which we can prove, by examining other
275 insns, that they are exception-free. Currently, this class consists
276 of loads for which we are able to find a "similar load", either in
277 the target block, or, if only one split-block exists, in that split
278 block. Load2 is similar to load1 if both have same single base
279 register. We identify only part of the similar loads, by finding
280 an insn upon which both load1 and load2 have a DEF-USE dependence.
282 PRISKY loads are loads for which we can prove, by examining other
283 insns, that they are exception-risky. Currently we have two proofs for
284 such loads. The first proof detects loads that are probably guarded by a
285 test on the memory address. This proof is based on the
286 backward and forward data dependence information for the region.
287 Let load-insn be the examined load.
288 Load-insn is PRISKY iff ALL the following hold:
290 - insn1 is not in the same block as load-insn
291 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
292 - test-insn is either a compare or a branch, not in the same block
294 - load-insn is reachable from test-insn
295 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
297 This proof might fail when the compare and the load are fed
298 by an insn not in the region. To solve this, we will add to this
299 group all loads that have no input DEF-USE dependence.
301 The second proof detects loads that are directly or indirectly
302 fed by a speculative load. This proof is affected by the
303 scheduling process. We will use the flag fed_by_spec_load.
304 Initially, all insns have this flag reset. After a speculative
305 motion of an insn, if insn is either a load, or marked as
306 fed_by_spec_load, we will also mark as fed_by_spec_load every
307 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
308 load which is fed_by_spec_load is also PRISKY.
310 MFREE (maybe-free) loads are all the remaining loads. They may be
311 exception-free, but we cannot prove it.
313 Now, all loads in IFREE and PFREE classes are considered
314 exception-free, while all loads in IRISKY and PRISKY classes are
315 considered exception-risky. As for loads in the MFREE class,
316 these are considered either exception-free or exception-risky,
317 depending on whether we are pessimistic or optimistic. We have
318 to take the pessimistic approach to assure the safety of
319 speculative scheduling, but we can take the optimistic approach
320 by invoking the -fsched_spec_load_dangerous option. */
324 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
325 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
328 #define WORST_CLASS(class1, class2) \
329 ((class1 > class2) ? class1 : class2)
336 #define HAIFA_INLINE __inline
339 /* Functions in sched-vis.c. */
340 extern void init_target_units
PARAMS ((void));
341 extern void insn_print_units
PARAMS ((rtx
));
342 extern void init_block_visualization
PARAMS ((void));
343 extern void print_block_visualization
PARAMS ((const char *));
344 extern void visualize_scheduled_insns
PARAMS ((int));
345 extern void visualize_no_unit
PARAMS ((rtx
));
346 extern void visualize_stall_cycles
PARAMS ((int));
347 extern void visualize_alloc
PARAMS ((void));
348 extern void visualize_free
PARAMS ((void));
350 /* Functions in sched-deps.c. */
351 extern int add_dependence
PARAMS ((rtx
, rtx
, enum reg_note
));
352 extern void add_insn_mem_dependence
PARAMS ((struct deps
*, rtx
*, rtx
*, rtx
,
354 extern void sched_analyze
PARAMS ((struct deps
*, rtx
, rtx
));
355 extern void init_deps
PARAMS ((struct deps
*));
356 extern void free_deps
PARAMS ((struct deps
*));
357 extern void init_deps_global
PARAMS ((void));
358 extern void finish_deps_global
PARAMS ((void));
359 extern void add_forward_dependence
PARAMS ((rtx
, rtx
, enum reg_note
));
360 extern void compute_forward_dependences
PARAMS ((rtx
, rtx
));
361 extern rtx find_insn_list
PARAMS ((rtx
, rtx
));
362 extern void init_dependency_caches
PARAMS ((int));
363 extern void free_dependency_caches
PARAMS ((void));
365 /* Functions in haifa-sched.c. */
366 extern int haifa_classify_insn
PARAMS ((rtx
));
367 extern void get_block_head_tail
PARAMS ((int, rtx
*, rtx
*));
368 extern int no_real_insns_p
PARAMS ((rtx
, rtx
));
370 extern void rm_line_notes
PARAMS ((rtx
, rtx
));
371 extern void save_line_notes
PARAMS ((int, rtx
, rtx
));
372 extern void restore_line_notes
PARAMS ((rtx
, rtx
));
373 extern void rm_redundant_line_notes
PARAMS ((void));
374 extern void rm_other_notes
PARAMS ((rtx
, rtx
));
376 extern int insn_issue_delay
PARAMS ((rtx
));
377 extern int set_priorities
PARAMS ((rtx
, rtx
));
379 extern rtx sched_emit_insn
PARAMS ((rtx
));
380 extern void schedule_block
PARAMS ((int, int));
381 extern void sched_init
PARAMS ((FILE *));
382 extern void sched_finish
PARAMS ((void));
384 extern void ready_add
PARAMS ((struct ready_list
*, rtx
));
386 /* The following are exported for the benefit of debugging functions. It
387 would be nicer to keep them private to haifa-sched.c. */
388 extern int insn_unit
PARAMS ((rtx
));
389 extern int insn_cost
PARAMS ((rtx
, rtx
, rtx
));
390 extern rtx get_unit_last_insn
PARAMS ((int));
391 extern int actual_hazard_this_instance
PARAMS ((int, int, rtx
, int, int));
392 extern void print_insn
PARAMS ((char *, rtx
, int));