stl_bvector.h (swap(_Bit_reference,_Bit_reference)): Move/rename...
[official-gcc.git] / gcc / sched-int.h
blob56c200e86fb9c8671f7bf80002ab5194cfe988fc
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
11 version.
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
16 for more details.
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
21 02111-1307, USA. */
23 /* Pointer to data describing the current DFA state. */
24 extern state_t curr_state;
26 /* Forward declaration. */
27 struct ready_list;
29 /* Describe state of dependencies used during sched_analyze phase. */
30 struct deps
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
71 too large. */
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
86 the call. */
87 bool in_post_call_group_p;
89 /* The maximum register number for the following arrays. Before reload
90 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
91 int max_reg;
93 /* Element N is the next insn that sets (hard or pseudo) register
94 N within the current basic block; or zero, if there is no
95 such insn. Needed for new registers which may be introduced
96 by splitting insns. */
97 struct deps_reg
99 rtx uses;
100 rtx sets;
101 rtx clobbers;
102 int uses_length;
103 int clobbers_length;
104 } *reg_last;
106 /* Element N is set for each register that has any non-zero element
107 in reg_last[N].{uses,sets,clobbers}. */
108 regset_head reg_last_in_use;
111 /* This structure holds some state of the current scheduling pass, and
112 contains some function pointers that abstract out some of the non-generic
113 functionality from functions such as schedule_block or schedule_insn.
114 There is one global variable, current_sched_info, which points to the
115 sched_info structure currently in use. */
116 struct sched_info
118 /* Add all insns that are initially ready to the ready list. Called once
119 before scheduling a set of insns. */
120 void (*init_ready_list) PARAMS ((struct ready_list *));
121 /* Called after taking an insn from the ready list. Returns nonzero if
122 this insn can be scheduled, nonzero if we should silently discard it. */
123 int (*can_schedule_ready_p) PARAMS ((rtx));
124 /* Return nonzero if there are more insns that should be scheduled. */
125 int (*schedule_more_p) PARAMS ((void));
126 /* Called after an insn has all its dependencies resolved. Return nonzero
127 if it should be moved to the ready list or the queue, or zero if we
128 should silently discard it. */
129 int (*new_ready) PARAMS ((rtx));
130 /* Compare priority of two insns. Return a positive number if the second
131 insn is to be preferred for scheduling, and a negative one if the first
132 is to be preferred. Zero if they are equally good. */
133 int (*rank) PARAMS ((rtx, rtx));
134 /* Return a string that contains the insn uid and optionally anything else
135 necessary to identify this insn in an output. It's valid to use a
136 static buffer for this. The ALIGNED parameter should cause the string
137 to be formatted so that multiple output lines will line up nicely. */
138 const char *(*print_insn) PARAMS ((rtx, int));
139 /* Return nonzero if an insn should be included in priority
140 calculations. */
141 int (*contributes_to_priority) PARAMS ((rtx, rtx));
142 /* Called when computing dependencies for a JUMP_INSN. This function
143 should store the set of registers that must be considered as set by
144 the jump in the regset. */
145 void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset));
147 /* The boundaries of the set of insns to be scheduled. */
148 rtx prev_head, next_tail;
150 /* Filled in after the schedule is finished; the first and last scheduled
151 insns. */
152 rtx head, tail;
154 /* If nonzero, enables an additional sanity check in schedule_block. */
155 unsigned int queue_must_finish_empty:1;
156 /* Nonzero if we should use cselib for better alias analysis. This
157 must be 0 if the dependency information is used after sched_analyze
158 has completed, e.g. if we're using it to initialize state for successor
159 blocks in region scheduling. */
160 unsigned int use_cselib:1;
163 extern struct sched_info *current_sched_info;
165 /* Indexed by INSN_UID, the collection of all data associated with
166 a single instruction. */
168 struct haifa_insn_data
170 /* A list of insns which depend on the instruction. Unlike LOG_LINKS,
171 it represents forward dependencies. */
172 rtx depend;
174 /* The line number note in effect for each insn. For line number
175 notes, this indicates whether the note may be reused. */
176 rtx line_note;
178 /* Logical uid gives the original ordering of the insns. */
179 int luid;
181 /* A priority for each insn. */
182 int priority;
184 /* The number of incoming edges in the forward dependency graph.
185 As scheduling proceds, counts are decreased. An insn moves to
186 the ready queue when its counter reaches zero. */
187 int dep_count;
189 /* An encoding of the blockage range function. Both unit and range
190 are coded. This member is used only for old pipeline interface. */
191 unsigned int blockage;
193 /* Number of instructions referring to this insn. */
194 int ref_count;
196 /* The minimum clock tick at which the insn becomes ready. This is
197 used to note timing constraints for the insns in the pending list. */
198 int tick;
200 short cost;
202 /* An encoding of the function units used. This member is used only
203 for old pipeline interface. */
204 short units;
206 /* This weight is an estimation of the insn's contribution to
207 register pressure. */
208 short reg_weight;
210 /* Some insns (e.g. call) are not allowed to move across blocks. */
211 unsigned int cant_move : 1;
213 /* Set if there's DEF-USE dependence between some speculatively
214 moved load insn and this one. */
215 unsigned int fed_by_spec_load : 1;
216 unsigned int is_load_insn : 1;
218 /* Nonzero if priority has been computed already. */
219 unsigned int priority_known : 1;
222 extern struct haifa_insn_data *h_i_d;
224 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
225 sched-rgn.c. */
226 #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
227 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
228 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
229 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
230 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
231 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
232 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
233 #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units)
234 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
236 #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage)
237 #define UNIT_BITS 5
238 #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1)
239 #define ENCODE_BLOCKAGE(U, R) \
240 (((U) << BLOCKAGE_BITS \
241 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \
242 | MAX_BLOCKAGE_COST (R))
243 #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
244 #define BLOCKAGE_RANGE(B) \
245 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
246 | ((B) & BLOCKAGE_MASK))
248 /* Encodings of the `<name>_unit_blockage_range' function. */
249 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
250 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
252 extern FILE *sched_dump;
253 extern int sched_verbose;
255 #ifndef __GNUC__
256 #define __inline
257 #endif
259 #ifndef HAIFA_INLINE
260 #define HAIFA_INLINE __inline
261 #endif
263 /* Functions in sched-vis.c. */
264 extern void init_target_units PARAMS ((void));
265 extern void insn_print_units PARAMS ((rtx));
266 extern void init_block_visualization PARAMS ((void));
267 extern void print_block_visualization PARAMS ((const char *));
268 extern void visualize_scheduled_insns PARAMS ((int));
269 extern void visualize_no_unit PARAMS ((rtx));
270 extern void visualize_stall_cycles PARAMS ((int));
271 extern void visualize_alloc PARAMS ((void));
272 extern void visualize_free PARAMS ((void));
274 /* Functions in sched-deps.c. */
275 extern void add_dependence PARAMS ((rtx, rtx, enum reg_note));
276 extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
277 rtx));
278 extern void sched_analyze PARAMS ((struct deps *, rtx, rtx));
279 extern void init_deps PARAMS ((struct deps *));
280 extern void free_deps PARAMS ((struct deps *));
281 extern void init_deps_global PARAMS ((void));
282 extern void finish_deps_global PARAMS ((void));
283 extern void compute_forward_dependences PARAMS ((rtx, rtx));
284 extern rtx find_insn_list PARAMS ((rtx, rtx));
285 extern void init_dependency_caches PARAMS ((int));
286 extern void free_dependency_caches PARAMS ((void));
288 /* Functions in haifa-sched.c. */
289 extern void get_block_head_tail PARAMS ((int, rtx *, rtx *));
290 extern int no_real_insns_p PARAMS ((rtx, rtx));
292 extern void rm_line_notes PARAMS ((rtx, rtx));
293 extern void save_line_notes PARAMS ((int, rtx, rtx));
294 extern void restore_line_notes PARAMS ((rtx, rtx));
295 extern void rm_redundant_line_notes PARAMS ((void));
296 extern void rm_other_notes PARAMS ((rtx, rtx));
298 extern int insn_issue_delay PARAMS ((rtx));
299 extern int set_priorities PARAMS ((rtx, rtx));
301 extern rtx sched_emit_insn PARAMS ((rtx));
302 extern void schedule_block PARAMS ((int, int));
303 extern void sched_init PARAMS ((FILE *));
304 extern void sched_finish PARAMS ((void));
306 extern void ready_add PARAMS ((struct ready_list *, rtx));
308 /* The following are exported for the benefit of debugging functions. It
309 would be nicer to keep them private to haifa-sched.c. */
310 extern int insn_unit PARAMS ((rtx));
311 extern int insn_cost PARAMS ((rtx, rtx, rtx));
312 extern rtx get_unit_last_insn PARAMS ((int));
313 extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
314 extern void print_insn PARAMS ((char *, rtx, int));