]>
Commit | Line | Data |
---|---|---|
1708fd40 BS |
1 | /* Instruction scheduling pass. This file contains definitions used |
2 | internally in the scheduler. | |
3 | Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
14052b68 | 4 | 1999, 2000, 2001 Free Software Foundation, Inc. |
1708fd40 | 5 | |
1322177d | 6 | This file is part of GCC. |
1708fd40 | 7 | |
1322177d LB |
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. | |
1708fd40 | 12 | |
1322177d LB |
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 | |
1708fd40 BS |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
f2d40127 NC |
19 | along with GCC; see the file COPYING. If not, write to the Free |
20 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
1708fd40 BS |
21 | 02111-1307, USA. */ |
22 | ||
23 | /* Forward declaration. */ | |
24 | struct ready_list; | |
25 | ||
16f6ece6 BS |
26 | /* Describe state of dependencies used during sched_analyze phase. */ |
27 | struct deps | |
28 | { | |
29 | /* The *_insns and *_mems are paired lists. Each pending memory operation | |
30 | will have a pointer to the MEM rtx on one list and a pointer to the | |
31 | containing insn on the other list in the same place in the list. */ | |
32 | ||
33 | /* We can't use add_dependence like the old code did, because a single insn | |
34 | may have multiple memory accesses, and hence needs to be on the list | |
35 | once for each memory access. Add_dependence won't let you add an insn | |
36 | to a list more than once. */ | |
37 | ||
38 | /* An INSN_LIST containing all insns with pending read operations. */ | |
39 | rtx pending_read_insns; | |
40 | ||
41 | /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ | |
42 | rtx pending_read_mems; | |
43 | ||
44 | /* An INSN_LIST containing all insns with pending write operations. */ | |
45 | rtx pending_write_insns; | |
46 | ||
47 | /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ | |
48 | rtx pending_write_mems; | |
49 | ||
50 | /* Indicates the combined length of the two pending lists. We must prevent | |
51 | these lists from ever growing too large since the number of dependencies | |
52 | produced is at least O(N*N), and execution time is at least O(4*N*N), as | |
53 | a function of the length of these pending lists. */ | |
54 | int pending_lists_length; | |
55 | ||
4a121cc3 AM |
56 | /* Length of the pending memory flush list. Large functions with no |
57 | calls may build up extremely large lists. */ | |
58 | int pending_flush_length; | |
59 | ||
16f6ece6 BS |
60 | /* The last insn upon which all memory references must depend. |
61 | This is an insn which flushed the pending lists, creating a dependency | |
62 | between it and all previously pending memory references. This creates | |
63 | a barrier (or a checkpoint) which no memory reference is allowed to cross. | |
64 | ||
65 | This includes all non constant CALL_INSNs. When we do interprocedural | |
66 | alias analysis, this restriction can be relaxed. | |
67 | This may also be an INSN that writes memory if the pending lists grow | |
68 | too large. */ | |
69 | rtx last_pending_memory_flush; | |
70 | ||
71 | /* The last function call we have seen. All hard regs, and, of course, | |
72 | the last function call, must depend on this. */ | |
73 | rtx last_function_call; | |
74 | ||
75 | /* Used to keep post-call psuedo/hard reg movements together with | |
76 | the call. */ | |
77 | int in_post_call_group_p; | |
78 | ||
79 | /* The LOG_LINKS field of this is a list of insns which use a pseudo | |
80 | register that does not already cross a call. We create | |
81 | dependencies between each of those insn and the next call insn, | |
82 | to ensure that they won't cross a call after scheduling is done. */ | |
83 | rtx sched_before_next_call; | |
84 | ||
4ba478b8 RH |
85 | /* The maximum register number for the following arrays. Before reload |
86 | this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ | |
87 | int max_reg; | |
88 | ||
16f6ece6 BS |
89 | /* Element N is the next insn that sets (hard or pseudo) register |
90 | N within the current basic block; or zero, if there is no | |
91 | such insn. Needed for new registers which may be introduced | |
92 | by splitting insns. */ | |
4ba478b8 RH |
93 | struct deps_reg |
94 | { | |
95 | rtx uses; | |
96 | rtx sets; | |
97 | rtx clobbers; | |
98 | } *reg_last; | |
99 | ||
100 | /* Element N is set for each register that has any non-zero element | |
101 | in reg_last[N].{uses,sets,clobbers}. */ | |
102 | regset_head reg_last_in_use; | |
16f6ece6 BS |
103 | }; |
104 | ||
1708fd40 BS |
105 | /* This structure holds some state of the current scheduling pass, and |
106 | contains some function pointers that abstract out some of the non-generic | |
107 | functionality from functions such as schedule_block or schedule_insn. | |
108 | There is one global variable, current_sched_info, which points to the | |
109 | sched_info structure currently in use. */ | |
110 | struct sched_info | |
111 | { | |
112 | /* Add all insns that are initially ready to the ready list. Called once | |
113 | before scheduling a set of insns. */ | |
114 | void (*init_ready_list) PARAMS ((struct ready_list *)); | |
115 | /* Called after taking an insn from the ready list. Returns nonzero if | |
116 | this insn can be scheduled, nonzero if we should silently discard it. */ | |
117 | int (*can_schedule_ready_p) PARAMS ((rtx)); | |
118 | /* Return nonzero if there are more insns that should be scheduled. */ | |
119 | int (*schedule_more_p) PARAMS ((void)); | |
120 | /* Called after an insn has all its dependencies resolved. Return nonzero | |
121 | if it should be moved to the ready list or the queue, or zero if we | |
122 | should silently discard it. */ | |
123 | int (*new_ready) PARAMS ((rtx)); | |
124 | /* Compare priority of two insns. Return a positive number if the second | |
125 | insn is to be preferred for scheduling, and a negative one if the first | |
126 | is to be preferred. Zero if they are equally good. */ | |
127 | int (*rank) PARAMS ((rtx, rtx)); | |
128 | /* Return a string that contains the insn uid and optionally anything else | |
129 | necessary to identify this insn in an output. It's valid to use a | |
130 | static buffer for this. The ALIGNED parameter should cause the string | |
131 | to be formatted so that multiple output lines will line up nicely. */ | |
132 | const char *(*print_insn) PARAMS ((rtx, int)); | |
18e720b3 BS |
133 | /* Return nonzero if an insn should be included in priority |
134 | calculations. */ | |
135 | int (*contributes_to_priority) PARAMS ((rtx, rtx)); | |
136 | /* Called when computing dependencies for a JUMP_INSN. This function | |
137 | should store the set of registers that must be considered as set by | |
138 | the jump in the regset. */ | |
139 | void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset)); | |
1708fd40 BS |
140 | |
141 | /* The boundaries of the set of insns to be scheduled. */ | |
142 | rtx prev_head, next_tail; | |
143 | ||
144 | /* Filled in after the schedule is finished; the first and last scheduled | |
145 | insns. */ | |
146 | rtx head, tail; | |
147 | ||
148 | /* If nonzero, enables an additional sanity check in schedule_block. */ | |
4b6c5340 BS |
149 | unsigned int queue_must_finish_empty:1; |
150 | /* Nonzero if we should use cselib for better alias analysis. This | |
151 | must be 0 if the dependency information is used after sched_analyze | |
152 | has completed, e.g. if we're using it to initialize state for successor | |
153 | blocks in region scheduling. */ | |
154 | unsigned int use_cselib:1; | |
1708fd40 BS |
155 | }; |
156 | ||
16f6ece6 BS |
157 | extern struct sched_info *current_sched_info; |
158 | ||
159 | /* Indexed by INSN_UID, the collection of all data associated with | |
160 | a single instruction. */ | |
161 | ||
162 | struct haifa_insn_data | |
163 | { | |
164 | /* A list of insns which depend on the instruction. Unlike LOG_LINKS, | |
ff7cc307 | 165 | it represents forward dependencies. */ |
16f6ece6 BS |
166 | rtx depend; |
167 | ||
168 | /* The line number note in effect for each insn. For line number | |
169 | notes, this indicates whether the note may be reused. */ | |
170 | rtx line_note; | |
171 | ||
172 | /* Logical uid gives the original ordering of the insns. */ | |
173 | int luid; | |
174 | ||
175 | /* A priority for each insn. */ | |
176 | int priority; | |
177 | ||
178 | /* The number of incoming edges in the forward dependency graph. | |
179 | As scheduling proceds, counts are decreased. An insn moves to | |
180 | the ready queue when its counter reaches zero. */ | |
181 | int dep_count; | |
182 | ||
183 | /* An encoding of the blockage range function. Both unit and range | |
b8ec5764 | 184 | are coded. */ |
16f6ece6 BS |
185 | unsigned int blockage; |
186 | ||
187 | /* Number of instructions referring to this insn. */ | |
188 | int ref_count; | |
189 | ||
190 | /* The minimum clock tick at which the insn becomes ready. This is | |
191 | used to note timing constraints for the insns in the pending list. */ | |
192 | int tick; | |
193 | ||
194 | short cost; | |
195 | ||
b8ec5764 | 196 | /* An encoding of the function units used. */ |
16f6ece6 BS |
197 | short units; |
198 | ||
199 | /* This weight is an estimation of the insn's contribution to | |
200 | register pressure. */ | |
201 | short reg_weight; | |
202 | ||
203 | /* Some insns (e.g. call) are not allowed to move across blocks. */ | |
204 | unsigned int cant_move : 1; | |
205 | ||
f5143c46 | 206 | /* Set if there's DEF-USE dependence between some speculatively |
16f6ece6 BS |
207 | moved load insn and this one. */ |
208 | unsigned int fed_by_spec_load : 1; | |
209 | unsigned int is_load_insn : 1; | |
21e4c9a8 BS |
210 | |
211 | /* Nonzero if priority has been computed already. */ | |
212 | unsigned int priority_known : 1; | |
16f6ece6 BS |
213 | }; |
214 | ||
215 | extern struct haifa_insn_data *h_i_d; | |
216 | ||
b4ead7d4 BS |
217 | /* Accessor macros for h_i_d. There are more in haifa-sched.c and |
218 | sched-rgn.c. */ | |
16f6ece6 BS |
219 | #define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) |
220 | #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) | |
221 | #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) | |
222 | #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) | |
b4ead7d4 | 223 | #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) |
21e4c9a8 | 224 | #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) |
b4ead7d4 BS |
225 | #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) |
226 | #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) | |
227 | #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) | |
228 | ||
229 | #define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) | |
230 | #define UNIT_BITS 5 | |
231 | #define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) | |
232 | #define ENCODE_BLOCKAGE(U, R) \ | |
233 | (((U) << BLOCKAGE_BITS \ | |
234 | | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ | |
235 | | MAX_BLOCKAGE_COST (R)) | |
236 | #define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) | |
237 | #define BLOCKAGE_RANGE(B) \ | |
238 | (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ | |
239 | | ((B) & BLOCKAGE_MASK)) | |
240 | ||
241 | /* Encodings of the `<name>_unit_blockage_range' function. */ | |
242 | #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) | |
243 | #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) | |
16f6ece6 BS |
244 | |
245 | extern FILE *sched_dump; | |
b4ead7d4 | 246 | extern int sched_verbose; |
16f6ece6 | 247 | |
1708fd40 BS |
248 | #ifndef __GNUC__ |
249 | #define __inline | |
250 | #endif | |
251 | ||
252 | #ifndef HAIFA_INLINE | |
253 | #define HAIFA_INLINE __inline | |
254 | #endif | |
16f6ece6 BS |
255 | |
256 | /* Functions in sched-vis.c. */ | |
257 | extern void init_target_units PARAMS ((void)); | |
258 | extern void insn_print_units PARAMS ((rtx)); | |
259 | extern void init_block_visualization PARAMS ((void)); | |
260 | extern void print_block_visualization PARAMS ((const char *)); | |
261 | extern void visualize_scheduled_insns PARAMS ((int)); | |
262 | extern void visualize_no_unit PARAMS ((rtx)); | |
263 | extern void visualize_stall_cycles PARAMS ((int)); | |
264 | extern void visualize_alloc PARAMS ((void)); | |
265 | extern void visualize_free PARAMS ((void)); | |
266 | ||
267 | /* Functions in sched-deps.c. */ | |
268 | extern void add_dependence PARAMS ((rtx, rtx, enum reg_note)); | |
269 | extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, | |
270 | rtx)); | |
271 | extern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); | |
272 | extern void init_deps PARAMS ((struct deps *)); | |
273 | extern void free_deps PARAMS ((struct deps *)); | |
274 | extern void init_deps_global PARAMS ((void)); | |
275 | extern void finish_deps_global PARAMS ((void)); | |
276 | extern void compute_forward_dependences PARAMS ((rtx, rtx)); | |
277 | extern int find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx)); | |
278 | extern rtx find_insn_list PARAMS ((rtx, rtx)); | |
279 | extern void init_dependency_caches PARAMS ((int)); | |
280 | extern void free_dependency_caches PARAMS ((void)); | |
281 | ||
282 | /* Functions in haifa-sched.c. */ | |
b4ead7d4 BS |
283 | extern void get_block_head_tail PARAMS ((int, rtx *, rtx *)); |
284 | extern int no_real_insns_p PARAMS ((rtx, rtx)); | |
285 | ||
79c2ffde BS |
286 | extern void rm_line_notes PARAMS ((rtx, rtx)); |
287 | extern void save_line_notes PARAMS ((int, rtx, rtx)); | |
14052b68 | 288 | extern void restore_line_notes PARAMS ((rtx, rtx)); |
b4ead7d4 BS |
289 | extern void rm_redundant_line_notes PARAMS ((void)); |
290 | extern void rm_other_notes PARAMS ((rtx, rtx)); | |
291 | ||
292 | extern int insn_issue_delay PARAMS ((rtx)); | |
79c2ffde | 293 | extern int set_priorities PARAMS ((rtx, rtx)); |
b4ead7d4 BS |
294 | |
295 | extern void schedule_block PARAMS ((int, int)); | |
296 | extern void sched_init PARAMS ((FILE *)); | |
297 | extern void sched_finish PARAMS ((void)); | |
298 | ||
299 | extern void ready_add PARAMS ((struct ready_list *, rtx)); | |
300 | ||
301 | /* The following are exported for the benefit of debugging functions. It | |
302 | would be nicer to keep them private to haifa-sched.c. */ | |
16f6ece6 | 303 | extern int insn_unit PARAMS ((rtx)); |
b4ead7d4 | 304 | extern int insn_cost PARAMS ((rtx, rtx, rtx)); |
16f6ece6 BS |
305 | extern rtx get_unit_last_insn PARAMS ((int)); |
306 | extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); | |
307 |