0
|
1 /* Instruction scheduling pass. This file contains definitions used
|
|
2 internally in the scheduler.
|
|
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
|
|
4 2001, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
|
|
5
|
|
6 This file is part of GCC.
|
|
7
|
|
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 3, or (at your option) any later
|
|
11 version.
|
|
12
|
|
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.
|
|
17
|
|
18 You should have received a copy of the GNU General Public License
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
21
|
|
22 #ifndef GCC_SCHED_INT_H
|
|
23 #define GCC_SCHED_INT_H
|
|
24
|
|
25 #ifdef INSN_SCHEDULING
|
|
26
|
|
27 /* For state_t. */
|
|
28 #include "insn-attr.h"
|
|
29 #include "df.h"
|
|
30 #include "basic-block.h"
|
|
31
|
|
32 /* For VEC (int, heap). */
|
|
33 #include "vecprim.h"
|
|
34
|
|
35 /* Identificator of a scheduler pass. */
|
|
36 enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,
|
|
37 SCHED_SMS_PASS, SCHED_SEL_PASS };
|
|
38
|
|
39 typedef VEC (basic_block, heap) *bb_vec_t;
|
|
40 typedef VEC (rtx, heap) *insn_vec_t;
|
|
41 typedef VEC(rtx, heap) *rtx_vec_t;
|
|
42
|
|
43 struct sched_scan_info_def
|
|
44 {
|
|
45 /* This hook notifies scheduler frontend to extend its internal per basic
|
|
46 block data structures. This hook should be called once before a series of
|
|
47 calls to bb_init (). */
|
|
48 void (*extend_bb) (void);
|
|
49
|
|
50 /* This hook makes scheduler frontend to initialize its internal data
|
|
51 structures for the passed basic block. */
|
|
52 void (*init_bb) (basic_block);
|
|
53
|
|
54 /* This hook notifies scheduler frontend to extend its internal per insn data
|
|
55 structures. This hook should be called once before a series of calls to
|
|
56 insn_init (). */
|
|
57 void (*extend_insn) (void);
|
|
58
|
|
59 /* This hook makes scheduler frontend to initialize its internal data
|
|
60 structures for the passed insn. */
|
|
61 void (*init_insn) (rtx);
|
|
62 };
|
|
63
|
|
64 extern const struct sched_scan_info_def *sched_scan_info;
|
|
65
|
|
66 extern void sched_scan (const struct sched_scan_info_def *,
|
|
67 bb_vec_t, basic_block, insn_vec_t, rtx);
|
|
68
|
|
69 extern void sched_init_bbs (void);
|
|
70
|
|
71 extern void sched_init_luids (bb_vec_t, basic_block, insn_vec_t, rtx);
|
|
72 extern void sched_finish_luids (void);
|
|
73
|
|
74 extern void sched_extend_target (void);
|
|
75
|
|
76 extern void haifa_init_h_i_d (bb_vec_t, basic_block, insn_vec_t, rtx);
|
|
77 extern void haifa_finish_h_i_d (void);
|
|
78
|
|
79 /* Hooks that are common to all the schedulers. */
|
|
80 struct common_sched_info_def
|
|
81 {
|
|
82 /* Called after blocks were rearranged due to movement of jump instruction.
|
|
83 The first parameter - index of basic block, in which jump currently is.
|
|
84 The second parameter - index of basic block, in which jump used
|
|
85 to be.
|
|
86 The third parameter - index of basic block, that follows the second
|
|
87 parameter. */
|
|
88 void (*fix_recovery_cfg) (int, int, int);
|
|
89
|
|
90 /* Called to notify frontend, that new basic block is being added.
|
|
91 The first parameter - new basic block.
|
|
92 The second parameter - block, after which new basic block is being added,
|
|
93 or EXIT_BLOCK_PTR, if recovery block is being added,
|
|
94 or NULL, if standalone block is being added. */
|
|
95 void (*add_block) (basic_block, basic_block);
|
|
96
|
|
97 /* Estimate number of insns in the basic block. */
|
|
98 int (*estimate_number_of_insns) (basic_block);
|
|
99
|
|
100 /* Given a non-insn (!INSN_P (x)) return
|
|
101 -1 - if this rtx don't need a luid.
|
|
102 0 - if it should have the same luid as the previous insn.
|
|
103 1 - if it needs a separate luid. */
|
|
104 int (*luid_for_non_insn) (rtx);
|
|
105
|
|
106 /* Scheduler pass identifier. It is preferably used in assertions. */
|
|
107 enum sched_pass_id_t sched_pass_id;
|
|
108 };
|
|
109
|
|
110 extern struct common_sched_info_def *common_sched_info;
|
|
111
|
|
112 extern const struct common_sched_info_def haifa_common_sched_info;
|
|
113
|
|
114 /* Return true if selective scheduling pass is working. */
|
|
115 static inline bool
|
|
116 sel_sched_p (void)
|
|
117 {
|
|
118 return common_sched_info->sched_pass_id == SCHED_SEL_PASS;
|
|
119 }
|
|
120
|
|
121 /* Returns maximum priority that an insn was assigned to. */
|
|
122 extern int get_rgn_sched_max_insns_priority (void);
|
|
123
|
|
124 /* Increases effective priority for INSN by AMOUNT. */
|
|
125 extern void sel_add_to_insn_priority (rtx, int);
|
|
126
|
|
127 /* True if during selective scheduling we need to emulate some of haifa
|
|
128 scheduler behaviour. */
|
|
129 extern int sched_emulate_haifa_p;
|
|
130
|
|
131 /* Mapping from INSN_UID to INSN_LUID. In the end all other per insn data
|
|
132 structures should be indexed by luid. */
|
|
133 extern VEC (int, heap) *sched_luids;
|
|
134 #define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
|
|
135 #define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
|
|
136
|
|
137 #define SET_INSN_LUID(INSN, LUID) \
|
|
138 (VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
|
|
139
|
|
140 /* The highest INSN_LUID. */
|
|
141 extern int sched_max_luid;
|
|
142
|
|
143 extern int insn_luid (rtx);
|
|
144
|
|
145 /* This list holds ripped off notes from the current block. These notes will
|
|
146 be attached to the beginning of the block when its scheduling is
|
|
147 finished. */
|
|
148 extern rtx note_list;
|
|
149
|
|
150 extern void remove_notes (rtx, rtx);
|
|
151 extern rtx restore_other_notes (rtx, basic_block);
|
|
152 extern void sched_insns_init (rtx);
|
|
153 extern void sched_insns_finish (void);
|
|
154
|
|
155 extern void *xrecalloc (void *, size_t, size_t, size_t);
|
|
156 extern rtx bb_note (basic_block);
|
|
157
|
|
158 extern void reemit_notes (rtx);
|
|
159
|
|
160 /* Functions in haifa-sched.c. */
|
|
161 extern int haifa_classify_insn (const_rtx);
|
|
162
|
|
163 /* Functions in sel-sched-ir.c. */
|
|
164 extern void sel_find_rgns (void);
|
|
165 extern void sel_mark_hard_insn (rtx);
|
|
166
|
|
167 extern size_t dfa_state_size;
|
|
168
|
|
169 extern void advance_state (state_t);
|
|
170
|
|
171 extern void setup_sched_dump (void);
|
|
172 extern void sched_init (void);
|
|
173 extern void sched_finish (void);
|
|
174
|
|
175 extern bool sel_insn_is_speculation_check (rtx);
|
|
176
|
|
177 /* Describe the ready list of the scheduler.
|
|
178 VEC holds space enough for all insns in the current region. VECLEN
|
|
179 says how many exactly.
|
|
180 FIRST is the index of the element with the highest priority; i.e. the
|
|
181 last one in the ready list, since elements are ordered by ascending
|
|
182 priority.
|
|
183 N_READY determines how many insns are on the ready list. */
|
|
184 struct ready_list
|
|
185 {
|
|
186 rtx *vec;
|
|
187 int veclen;
|
|
188 int first;
|
|
189 int n_ready;
|
|
190 };
|
|
191
|
|
192 extern char *ready_try;
|
|
193 extern struct ready_list ready;
|
|
194
|
|
195 extern int max_issue (struct ready_list *, int, state_t, int *);
|
|
196
|
|
197 extern void ebb_compute_jump_reg_dependencies (rtx, regset, regset, regset);
|
|
198
|
|
199 extern edge find_fallthru_edge (basic_block);
|
|
200
|
|
201 extern void (* sched_init_only_bb) (basic_block, basic_block);
|
|
202 extern basic_block (* sched_split_block) (basic_block, rtx);
|
|
203 extern basic_block sched_split_block_1 (basic_block, rtx);
|
|
204 extern basic_block (* sched_create_empty_bb) (basic_block);
|
|
205 extern basic_block sched_create_empty_bb_1 (basic_block);
|
|
206
|
|
207 extern basic_block sched_create_recovery_block (basic_block *);
|
|
208 extern void sched_create_recovery_edges (basic_block, basic_block,
|
|
209 basic_block);
|
|
210
|
|
211 /* Pointer to data describing the current DFA state. */
|
|
212 extern state_t curr_state;
|
|
213
|
|
214 /* Type to represent status of a dependence. */
|
|
215 typedef int ds_t;
|
|
216
|
|
217 /* Type to represent weakness of speculative dependence. */
|
|
218 typedef int dw_t;
|
|
219
|
|
220 extern enum reg_note ds_to_dk (ds_t);
|
|
221 extern ds_t dk_to_ds (enum reg_note);
|
|
222
|
|
223 /* Information about the dependency. */
|
|
224 struct _dep
|
|
225 {
|
|
226 /* Producer. */
|
|
227 rtx pro;
|
|
228
|
|
229 /* Consumer. */
|
|
230 rtx con;
|
|
231
|
|
232 /* Dependency major type. This field is superseded by STATUS below.
|
|
233 Though, it is still in place because some targets use it. */
|
|
234 enum reg_note type;
|
|
235
|
|
236 /* Dependency status. This field holds all dependency types and additional
|
|
237 information for speculative dependencies. */
|
|
238 ds_t status;
|
|
239 };
|
|
240
|
|
241 typedef struct _dep dep_def;
|
|
242 typedef dep_def *dep_t;
|
|
243
|
|
244 #define DEP_PRO(D) ((D)->pro)
|
|
245 #define DEP_CON(D) ((D)->con)
|
|
246 #define DEP_TYPE(D) ((D)->type)
|
|
247 #define DEP_STATUS(D) ((D)->status)
|
|
248
|
|
249 /* Functions to work with dep. */
|
|
250
|
|
251 extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t);
|
|
252 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
|
|
253
|
|
254 extern void sd_debug_dep (dep_t);
|
|
255
|
|
256 /* Definition of this struct resides below. */
|
|
257 struct _dep_node;
|
|
258 typedef struct _dep_node *dep_node_t;
|
|
259
|
|
260 /* A link in the dependency list. This is essentially an equivalent of a
|
|
261 single {INSN, DEPS}_LIST rtx. */
|
|
262 struct _dep_link
|
|
263 {
|
|
264 /* Dep node with all the data. */
|
|
265 dep_node_t node;
|
|
266
|
|
267 /* Next link in the list. For the last one it is NULL. */
|
|
268 struct _dep_link *next;
|
|
269
|
|
270 /* Pointer to the next field of the previous link in the list.
|
|
271 For the first link this points to the deps_list->first.
|
|
272
|
|
273 With help of this field it is easy to remove and insert links to the
|
|
274 list. */
|
|
275 struct _dep_link **prev_nextp;
|
|
276 };
|
|
277 typedef struct _dep_link *dep_link_t;
|
|
278
|
|
279 #define DEP_LINK_NODE(N) ((N)->node)
|
|
280 #define DEP_LINK_NEXT(N) ((N)->next)
|
|
281 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
|
|
282
|
|
283 /* Macros to work dep_link. For most usecases only part of the dependency
|
|
284 information is need. These macros conveniently provide that piece of
|
|
285 information. */
|
|
286
|
|
287 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
|
|
288 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
|
|
289 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
|
|
290 #define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
|
|
291 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
|
|
292
|
|
293 /* A list of dep_links. */
|
|
294 struct _deps_list
|
|
295 {
|
|
296 /* First element. */
|
|
297 dep_link_t first;
|
|
298
|
|
299 /* Total number of elements in the list. */
|
|
300 int n_links;
|
|
301 };
|
|
302 typedef struct _deps_list *deps_list_t;
|
|
303
|
|
304 #define DEPS_LIST_FIRST(L) ((L)->first)
|
|
305 #define DEPS_LIST_N_LINKS(L) ((L)->n_links)
|
|
306
|
|
307 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
|
|
308 additional dependents con0 and con2, and con1 is dependent on additional
|
|
309 insns pro0 and pro1:
|
|
310
|
|
311 .con0 pro0
|
|
312 . ^ |
|
|
313 . | |
|
|
314 . | |
|
|
315 . X A
|
|
316 . | |
|
|
317 . | |
|
|
318 . | V
|
|
319 .pro1--Y-->con1
|
|
320 . | ^
|
|
321 . | |
|
|
322 . | |
|
|
323 . Z B
|
|
324 . | |
|
|
325 . | |
|
|
326 . V |
|
|
327 .con2 pro2
|
|
328
|
|
329 This is represented using a "dep_node" for each dependence arc, which are
|
|
330 connected as follows (diagram is centered around Y which is fully shown;
|
|
331 other dep_nodes shown partially):
|
|
332
|
|
333 . +------------+ +--------------+ +------------+
|
|
334 . : dep_node X : | dep_node Y | : dep_node Z :
|
|
335 . : : | | : :
|
|
336 . : : | | : :
|
|
337 . : forw : | forw | : forw :
|
|
338 . : +--------+ : | +--------+ | : +--------+ :
|
|
339 forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
|
|
340 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|
|
341 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
|
|
342 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|
|
343 . ^ ^ : | ^ | : | | ^ | | : | | :
|
|
344 . | | : | | | : | | | | | : | | :
|
|
345 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
|
|
346 . | : | | | : | | | | | : | | | :
|
|
347 . | : | +----+ | : | | +----+ | | : | +----+ | :
|
|
348 . | : | |prev| | : | | |prev| | | : | |prev| | :
|
|
349 . | : | |next| | : | | |next| | | : | |next| | :
|
|
350 . | : | +----+ | : | | +----+ | | : | +----+ | :
|
|
351 . | : | | :<-+ | | | |<-+ : | | :<-+
|
|
352 . | : | +----+ | : | | | +----+ | | | : | +----+ | : |
|
|
353 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
|
|
354 . | : | +----+ | : | | +----+ | | : | +----+ | :
|
|
355 . | : | | : | | | | : | | :
|
|
356 . | : +--------+ : | +--------+ | : +--------+ :
|
|
357 . | : : | | : :
|
|
358 . | : SAME pro1 : | +--------+ | : SAME pro1 :
|
|
359 . | : DIFF con0 : | |dep | | : DIFF con2 :
|
|
360 . | : : | | | | : :
|
|
361 . | | | +----+ | |
|
|
362 .RTX<------------------------+--+-|pro1| | |
|
|
363 .pro1 | | +----+ | |
|
|
364 . | | | |
|
|
365 . | | +----+ | |
|
|
366 .RTX<------------------------+--+-|con1| | |
|
|
367 .con1 | | +----+ | |
|
|
368 . | | | | |
|
|
369 . | | | +----+ | |
|
|
370 . | | | |kind| | |
|
|
371 . | | | +----+ | |
|
|
372 . | : : | | |stat| | | : :
|
|
373 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 :
|
|
374 . | : SAME con1 : | | | | : SAME con1 :
|
|
375 . | : : | +--------+ | : :
|
|
376 . | : : | | : :
|
|
377 . | : back : | back | : back :
|
|
378 . v : +--------+ : | +--------+ | : +--------+ :
|
|
379 back_deps : |dep_link| : | |dep_link| | : |dep_link| :
|
|
380 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|
|
381 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
|
|
382 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
|
|
383 . ^ : | ^ | : | | ^ | | : | | :
|
|
384 . | : | | | : | | | | | : | | :
|
|
385 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
|
|
386 . : | | | : | | | | | : | | | :
|
|
387 . : | +----+ | : | | +----+ | | : | +----+ | :
|
|
388 . : | |prev| | : | | |prev| | | : | |prev| | :
|
|
389 . : | |next| | : | | |next| | | : | |next| | :
|
|
390 . : | +----+ | : | | +----+ | | : | +----+ | :
|
|
391 . : | | :<-+ | | | |<-+ : | | :<-+
|
|
392 . : | +----+ | : | | | +----+ | | | : | +----+ | : |
|
|
393 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
|
|
394 . : | +----+ | : | | +----+ | | : | +----+ | :
|
|
395 . : | | : | | | | : | | :
|
|
396 . : +--------+ : | +--------+ | : +--------+ :
|
|
397 . : : | | : :
|
|
398 . : dep_node A : | dep_node Y | : dep_node B :
|
|
399 . +------------+ +--------------+ +------------+
|
|
400 */
|
|
401
|
|
402 struct _dep_node
|
|
403 {
|
|
404 /* Backward link. */
|
|
405 struct _dep_link back;
|
|
406
|
|
407 /* The dep. */
|
|
408 struct _dep dep;
|
|
409
|
|
410 /* Forward link. */
|
|
411 struct _dep_link forw;
|
|
412 };
|
|
413
|
|
414 #define DEP_NODE_BACK(N) (&(N)->back)
|
|
415 #define DEP_NODE_DEP(N) (&(N)->dep)
|
|
416 #define DEP_NODE_FORW(N) (&(N)->forw)
|
|
417
|
|
418 /* The following enumeration values tell us what dependencies we
|
|
419 should use to implement the barrier. We use true-dependencies for
|
|
420 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
|
|
421 enum reg_pending_barrier_mode
|
|
422 {
|
|
423 NOT_A_BARRIER = 0,
|
|
424 MOVE_BARRIER,
|
|
425 TRUE_BARRIER
|
|
426 };
|
|
427
|
|
428 /* Describe state of dependencies used during sched_analyze phase. */
|
|
429 struct deps
|
|
430 {
|
|
431 /* The *_insns and *_mems are paired lists. Each pending memory operation
|
|
432 will have a pointer to the MEM rtx on one list and a pointer to the
|
|
433 containing insn on the other list in the same place in the list. */
|
|
434
|
|
435 /* We can't use add_dependence like the old code did, because a single insn
|
|
436 may have multiple memory accesses, and hence needs to be on the list
|
|
437 once for each memory access. Add_dependence won't let you add an insn
|
|
438 to a list more than once. */
|
|
439
|
|
440 /* An INSN_LIST containing all insns with pending read operations. */
|
|
441 rtx pending_read_insns;
|
|
442
|
|
443 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
|
|
444 rtx pending_read_mems;
|
|
445
|
|
446 /* An INSN_LIST containing all insns with pending write operations. */
|
|
447 rtx pending_write_insns;
|
|
448
|
|
449 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
|
|
450 rtx pending_write_mems;
|
|
451
|
|
452 /* We must prevent the above lists from ever growing too large since
|
|
453 the number of dependencies produced is at least O(N*N),
|
|
454 and execution time is at least O(4*N*N), as a function of the
|
|
455 length of these pending lists. */
|
|
456
|
|
457 /* Indicates the length of the pending_read list. */
|
|
458 int pending_read_list_length;
|
|
459
|
|
460 /* Indicates the length of the pending_write list. */
|
|
461 int pending_write_list_length;
|
|
462
|
|
463 /* Length of the pending memory flush list. Large functions with no
|
|
464 calls may build up extremely large lists. */
|
|
465 int pending_flush_length;
|
|
466
|
|
467 /* The last insn upon which all memory references must depend.
|
|
468 This is an insn which flushed the pending lists, creating a dependency
|
|
469 between it and all previously pending memory references. This creates
|
|
470 a barrier (or a checkpoint) which no memory reference is allowed to cross.
|
|
471
|
|
472 This includes all non constant CALL_INSNs. When we do interprocedural
|
|
473 alias analysis, this restriction can be relaxed.
|
|
474 This may also be an INSN that writes memory if the pending lists grow
|
|
475 too large. */
|
|
476 rtx last_pending_memory_flush;
|
|
477
|
|
478 /* A list of the last function calls we have seen. We use a list to
|
|
479 represent last function calls from multiple predecessor blocks.
|
|
480 Used to prevent register lifetimes from expanding unnecessarily. */
|
|
481 rtx last_function_call;
|
|
482
|
|
483 /* A list of insns which use a pseudo register that does not already
|
|
484 cross a call. We create dependencies between each of those insn
|
|
485 and the next call insn, to ensure that they won't cross a call after
|
|
486 scheduling is done. */
|
|
487 rtx sched_before_next_call;
|
|
488
|
|
489 /* Used to keep post-call pseudo/hard reg movements together with
|
|
490 the call. */
|
|
491 enum { not_post_call, post_call, post_call_initial } in_post_call_group_p;
|
|
492
|
|
493 /* The maximum register number for the following arrays. Before reload
|
|
494 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
|
|
495 int max_reg;
|
|
496
|
|
497 /* Element N is the next insn that sets (hard or pseudo) register
|
|
498 N within the current basic block; or zero, if there is no
|
|
499 such insn. Needed for new registers which may be introduced
|
|
500 by splitting insns. */
|
|
501 struct deps_reg
|
|
502 {
|
|
503 rtx uses;
|
|
504 rtx sets;
|
|
505 rtx clobbers;
|
|
506 int uses_length;
|
|
507 int clobbers_length;
|
|
508 } *reg_last;
|
|
509
|
|
510 /* Element N is set for each register that has any nonzero element
|
|
511 in reg_last[N].{uses,sets,clobbers}. */
|
|
512 regset_head reg_last_in_use;
|
|
513
|
|
514 /* Element N is set for each register that is conditionally set. */
|
|
515 regset_head reg_conditional_sets;
|
|
516
|
|
517 /* Shows the last value of reg_pending_barrier associated with the insn. */
|
|
518 enum reg_pending_barrier_mode last_reg_pending_barrier;
|
|
519
|
|
520 /* True when this context should be treated as a readonly by
|
|
521 the analysis. */
|
|
522 BOOL_BITFIELD readonly : 1;
|
|
523 };
|
|
524
|
|
525 typedef struct deps *deps_t;
|
|
526
|
|
527 /* This structure holds some state of the current scheduling pass, and
|
|
528 contains some function pointers that abstract out some of the non-generic
|
|
529 functionality from functions such as schedule_block or schedule_insn.
|
|
530 There is one global variable, current_sched_info, which points to the
|
|
531 sched_info structure currently in use. */
|
|
532 struct haifa_sched_info
|
|
533 {
|
|
534 /* Add all insns that are initially ready to the ready list. Called once
|
|
535 before scheduling a set of insns. */
|
|
536 void (*init_ready_list) (void);
|
|
537 /* Called after taking an insn from the ready list. Returns nonzero if
|
|
538 this insn can be scheduled, nonzero if we should silently discard it. */
|
|
539 int (*can_schedule_ready_p) (rtx);
|
|
540 /* Return nonzero if there are more insns that should be scheduled. */
|
|
541 int (*schedule_more_p) (void);
|
|
542 /* Called after an insn has all its hard dependencies resolved.
|
|
543 Adjusts status of instruction (which is passed through second parameter)
|
|
544 to indicate if instruction should be moved to the ready list or the
|
|
545 queue, or if it should silently discard it (until next resolved
|
|
546 dependence). */
|
|
547 ds_t (*new_ready) (rtx, ds_t);
|
|
548 /* Compare priority of two insns. Return a positive number if the second
|
|
549 insn is to be preferred for scheduling, and a negative one if the first
|
|
550 is to be preferred. Zero if they are equally good. */
|
|
551 int (*rank) (rtx, rtx);
|
|
552 /* Return a string that contains the insn uid and optionally anything else
|
|
553 necessary to identify this insn in an output. It's valid to use a
|
|
554 static buffer for this. The ALIGNED parameter should cause the string
|
|
555 to be formatted so that multiple output lines will line up nicely. */
|
|
556 const char *(*print_insn) (const_rtx, int);
|
|
557 /* Return nonzero if an insn should be included in priority
|
|
558 calculations. */
|
|
559 int (*contributes_to_priority) (rtx, rtx);
|
|
560
|
|
561 /* The boundaries of the set of insns to be scheduled. */
|
|
562 rtx prev_head, next_tail;
|
|
563
|
|
564 /* Filled in after the schedule is finished; the first and last scheduled
|
|
565 insns. */
|
|
566 rtx head, tail;
|
|
567
|
|
568 /* If nonzero, enables an additional sanity check in schedule_block. */
|
|
569 unsigned int queue_must_finish_empty:1;
|
|
570
|
|
571 /* Maximum priority that has been assigned to an insn. */
|
|
572 int sched_max_insns_priority;
|
|
573
|
|
574 /* Hooks to support speculative scheduling. */
|
|
575
|
|
576 /* Called to notify frontend that instruction is being added (second
|
|
577 parameter == 0) or removed (second parameter == 1). */
|
|
578 void (*add_remove_insn) (rtx, int);
|
|
579
|
|
580 /* Called to notify frontend that instruction is being scheduled.
|
|
581 The first parameter - instruction to scheduled, the second parameter -
|
|
582 last scheduled instruction. */
|
|
583 void (*begin_schedule_ready) (rtx, rtx);
|
|
584
|
|
585 /* If the second parameter is not NULL, return nonnull value, if the
|
|
586 basic block should be advanced.
|
|
587 If the second parameter is NULL, return the next basic block in EBB.
|
|
588 The first parameter is the current basic block in EBB. */
|
|
589 basic_block (*advance_target_bb) (basic_block, rtx);
|
|
590
|
|
591 /* ??? FIXME: should use straight bitfields inside sched_info instead of
|
|
592 this flag field. */
|
|
593 unsigned int flags;
|
|
594 };
|
|
595
|
|
596 /* This structure holds description of the properties for speculative
|
|
597 scheduling. */
|
|
598 struct spec_info_def
|
|
599 {
|
|
600 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
|
|
601 BE_IN_{DATA_CONTROL}. */
|
|
602 int mask;
|
|
603
|
|
604 /* A dump file for additional information on speculative scheduling. */
|
|
605 FILE *dump;
|
|
606
|
|
607 /* Minimal cumulative weakness of speculative instruction's
|
|
608 dependencies, so that insn will be scheduled. */
|
|
609 dw_t data_weakness_cutoff;
|
|
610
|
|
611 /* Minimal usefulness of speculative instruction to be considered for
|
|
612 scheduling. */
|
|
613 int control_weakness_cutoff;
|
|
614
|
|
615 /* Flags from the enum SPEC_SCHED_FLAGS. */
|
|
616 int flags;
|
|
617 };
|
|
618 typedef struct spec_info_def *spec_info_t;
|
|
619
|
|
620 extern spec_info_t spec_info;
|
|
621
|
|
622 extern struct haifa_sched_info *current_sched_info;
|
|
623
|
|
624 /* Indexed by INSN_UID, the collection of all data associated with
|
|
625 a single instruction. */
|
|
626
|
|
627 struct _haifa_deps_insn_data
|
|
628 {
|
|
629 /* The number of incoming edges in the forward dependency graph.
|
|
630 As scheduling proceeds, counts are decreased. An insn moves to
|
|
631 the ready queue when its counter reaches zero. */
|
|
632 int dep_count;
|
|
633
|
|
634 /* Nonzero if instruction has internal dependence
|
|
635 (e.g. add_dependence was invoked with (insn == elem)). */
|
|
636 unsigned int has_internal_dep;
|
|
637
|
|
638 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
|
|
639 h_i_d because when h_i_d extends, addresses of the deps_list->first
|
|
640 change without updating deps_list->first->next->prev_nextp. Thus
|
|
641 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
|
|
642 list is allocated on the obstack. */
|
|
643
|
|
644 /* A list of hard backward dependencies. The insn is a consumer of all the
|
|
645 deps mentioned here. */
|
|
646 deps_list_t hard_back_deps;
|
|
647
|
|
648 /* A list of speculative (weak) dependencies. The insn is a consumer of all
|
|
649 the deps mentioned here. */
|
|
650 deps_list_t spec_back_deps;
|
|
651
|
|
652 /* A list of insns which depend on the instruction. Unlike 'back_deps',
|
|
653 it represents forward dependencies. */
|
|
654 deps_list_t forw_deps;
|
|
655
|
|
656 /* A list of scheduled producers of the instruction. Links are being moved
|
|
657 from 'back_deps' to 'resolved_back_deps' while scheduling. */
|
|
658 deps_list_t resolved_back_deps;
|
|
659
|
|
660 /* A list of scheduled consumers of the instruction. Links are being moved
|
|
661 from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
|
|
662 search in 'forw_deps'. */
|
|
663 deps_list_t resolved_forw_deps;
|
|
664
|
|
665 /* Some insns (e.g. call) are not allowed to move across blocks. */
|
|
666 unsigned int cant_move : 1;
|
|
667 };
|
|
668
|
|
669 struct _haifa_insn_data
|
|
670 {
|
|
671 /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
|
|
672 because when h_i_d extends, addresses of the deps_list->first
|
|
673 change without updating deps_list->first->next->prev_nextp. */
|
|
674
|
|
675 /* Logical uid gives the original ordering of the insns. */
|
|
676 int luid;
|
|
677
|
|
678 /* A priority for each insn. */
|
|
679 int priority;
|
|
680
|
|
681 /* The minimum clock tick at which the insn becomes ready. This is
|
|
682 used to note timing constraints for the insns in the pending list. */
|
|
683 int tick;
|
|
684
|
|
685 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
|
|
686 subsequent blocks in a region. */
|
|
687 int inter_tick;
|
|
688
|
|
689 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
|
|
690 int queue_index;
|
|
691
|
|
692 short cost;
|
|
693
|
|
694 /* This weight is an estimation of the insn's contribution to
|
|
695 register pressure. */
|
|
696 short reg_weight;
|
|
697
|
|
698 /* Set if there's DEF-USE dependence between some speculatively
|
|
699 moved load insn and this one. */
|
|
700 unsigned int fed_by_spec_load : 1;
|
|
701 unsigned int is_load_insn : 1;
|
|
702
|
|
703 /* '> 0' if priority is valid,
|
|
704 '== 0' if priority was not yet computed,
|
|
705 '< 0' if priority in invalid and should be recomputed. */
|
|
706 signed char priority_status;
|
|
707
|
|
708 /* What speculations are necessary to apply to schedule the instruction. */
|
|
709 ds_t todo_spec;
|
|
710
|
|
711 /* What speculations were already applied. */
|
|
712 ds_t done_spec;
|
|
713
|
|
714 /* What speculations are checked by this instruction. */
|
|
715 ds_t check_spec;
|
|
716
|
|
717 /* Recovery block for speculation checks. */
|
|
718 basic_block recovery_block;
|
|
719
|
|
720 /* Original pattern of the instruction. */
|
|
721 rtx orig_pat;
|
|
722 };
|
|
723
|
|
724 typedef struct _haifa_insn_data haifa_insn_data_def;
|
|
725 typedef haifa_insn_data_def *haifa_insn_data_t;
|
|
726
|
|
727 DEF_VEC_O (haifa_insn_data_def);
|
|
728 DEF_VEC_ALLOC_O (haifa_insn_data_def, heap);
|
|
729
|
|
730 extern VEC(haifa_insn_data_def, heap) *h_i_d;
|
|
731
|
|
732 #define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN)))
|
|
733
|
|
734 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
|
|
735 sched-rgn.c. */
|
|
736 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
|
|
737 #define INSN_REG_WEIGHT(INSN) (HID (INSN)->reg_weight)
|
|
738 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
|
|
739
|
|
740 typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def;
|
|
741 typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t;
|
|
742
|
|
743 DEF_VEC_O (haifa_deps_insn_data_def);
|
|
744 DEF_VEC_ALLOC_O (haifa_deps_insn_data_def, heap);
|
|
745
|
|
746 extern VEC(haifa_deps_insn_data_def, heap) *h_d_i_d;
|
|
747
|
|
748 #define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
|
|
749 INSN_LUID (INSN)))
|
|
750 #define INSN_DEP_COUNT(INSN) (HDID (INSN)->dep_count)
|
|
751 #define HAS_INTERNAL_DEP(INSN) (HDID (INSN)->has_internal_dep)
|
|
752 #define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
|
|
753 #define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
|
|
754 #define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
|
|
755 #define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
|
|
756 #define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
|
|
757 #define CANT_MOVE(INSN) (HDID (INSN)->cant_move)
|
|
758 #define CANT_MOVE_BY_LUID(LUID) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
|
|
759 LUID)->cant_move)
|
|
760
|
|
761
|
|
762 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
|
|
763 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
|
|
764 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
|
|
765 #define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
|
|
766 #define DONE_SPEC(INSN) (HID (INSN)->done_spec)
|
|
767 #define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
|
|
768 #define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
|
|
769 #define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
|
|
770
|
|
771 /* INSN is either a simple or a branchy speculation check. */
|
|
772 #define IS_SPECULATION_CHECK_P(INSN) \
|
|
773 (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
|
|
774
|
|
775 /* INSN is a speculation check that will simply reexecute the speculatively
|
|
776 scheduled instruction if the speculation fails. */
|
|
777 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
|
|
778 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
|
|
779
|
|
780 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
|
|
781 speculation fails. Insns in that block will reexecute the speculatively
|
|
782 scheduled code and then will return immediately after INSN thus preserving
|
|
783 semantics of the program. */
|
|
784 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
|
|
785 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
|
|
786
|
|
787 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
|
|
788 for speculative scheduling. Namely, it is 4 integers in the range
|
|
789 [0, MAX_DEP_WEAK] and 3 bits.
|
|
790 The integers correspond to the probability of the dependence to *not*
|
|
791 exist, it is the probability, that overcoming of this dependence will
|
|
792 not be followed by execution of the recovery code. Nevertheless,
|
|
793 whatever high the probability of success is, recovery code should still
|
|
794 be generated to preserve semantics of the program. To find a way to
|
|
795 get/set these integers, please refer to the {get, set}_dep_weak ()
|
|
796 functions in sched-deps.c .
|
|
797 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
|
|
798 output- and anti- dependence. It is not enough for speculative scheduling
|
|
799 to know just the major type of all the dependence between two instructions,
|
|
800 as only true dependence can be overcome.
|
|
801 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
|
|
802 for using to describe instruction's status. It is set whenever instruction
|
|
803 has at least one dependence, that cannot be overcame.
|
|
804 See also: check_dep_status () in sched-deps.c . */
|
|
805
|
|
806 /* We exclude sign bit. */
|
|
807 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
|
|
808
|
|
809 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
|
|
810 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
|
|
811 dep weakness. */
|
|
812 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
|
|
813
|
|
814 /* Mask of speculative weakness in dep_status. */
|
|
815 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
|
|
816
|
|
817 /* This constant means that dependence is fake with 99.999...% probability.
|
|
818 This is the maximum value, that can appear in dep_status.
|
|
819 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
|
|
820 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when
|
|
821 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */
|
|
822 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
|
|
823
|
|
824 /* This constant means that dependence is 99.999...% real and it is a really
|
|
825 bad idea to overcome it (though this can be done, preserving program
|
|
826 semantics). */
|
|
827 #define MIN_DEP_WEAK 1
|
|
828
|
|
829 /* This constant represents 100% probability.
|
|
830 E.g. it is used to represent weakness of dependence, that doesn't exist. */
|
|
831 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
|
|
832
|
|
833 /* Default weakness of speculative dependence. Used when we can't say
|
|
834 neither bad nor good about the dependence. */
|
|
835 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
|
|
836
|
|
837 /* Offset for speculative weaknesses in dep_status. */
|
|
838 enum SPEC_TYPES_OFFSETS {
|
|
839 BEGIN_DATA_BITS_OFFSET = 0,
|
|
840 BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
|
|
841 BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
|
|
842 BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
|
|
843 };
|
|
844
|
|
845 /* The following defines provide numerous constants used to distinguish between
|
|
846 different types of speculative dependencies. */
|
|
847
|
|
848 /* Dependence can be overcome with generation of new data speculative
|
|
849 instruction. */
|
|
850 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
|
|
851
|
|
852 /* This dependence is to the instruction in the recovery block, that was
|
|
853 formed to recover after data-speculation failure.
|
|
854 Thus, this dependence can overcome with generating of the copy of
|
|
855 this instruction in the recovery block. */
|
|
856 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
|
|
857
|
|
858 /* Dependence can be overcome with generation of new control speculative
|
|
859 instruction. */
|
|
860 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
|
|
861
|
|
862 /* This dependence is to the instruction in the recovery block, that was
|
|
863 formed to recover after control-speculation failure.
|
|
864 Thus, this dependence can be overcome with generating of the copy of
|
|
865 this instruction in the recovery block. */
|
|
866 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
|
|
867
|
|
868 /* A few convenient combinations. */
|
|
869 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
|
|
870 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
|
|
871 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
|
|
872 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
|
|
873 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
|
|
874
|
|
875 /* Constants, that are helpful in iterating through dep_status. */
|
|
876 #define FIRST_SPEC_TYPE BEGIN_DATA
|
|
877 #define LAST_SPEC_TYPE BE_IN_CONTROL
|
|
878 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
|
|
879
|
|
880 /* Dependence on instruction can be of multiple types
|
|
881 (e.g. true and output). This fields enhance REG_NOTE_KIND information
|
|
882 of the dependence. */
|
|
883 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
|
|
884 #define DEP_OUTPUT (DEP_TRUE << 1)
|
|
885 #define DEP_ANTI (DEP_OUTPUT << 1)
|
|
886
|
|
887 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
|
|
888
|
|
889 /* Instruction has non-speculative dependence. This bit represents the
|
|
890 property of an instruction - not the one of a dependence.
|
|
891 Therefore, it can appear only in TODO_SPEC field of an instruction. */
|
|
892 #define HARD_DEP (DEP_ANTI << 1)
|
|
893
|
|
894 /* This represents the results of calling sched-deps.c functions,
|
|
895 which modify dependencies. */
|
|
896 enum DEPS_ADJUST_RESULT {
|
|
897 /* No dependence needed (e.g. producer == consumer). */
|
|
898 DEP_NODEP,
|
|
899 /* Dependence is already present and wasn't modified. */
|
|
900 DEP_PRESENT,
|
|
901 /* Existing dependence was modified to include additional information. */
|
|
902 DEP_CHANGED,
|
|
903 /* New dependence has been created. */
|
|
904 DEP_CREATED
|
|
905 };
|
|
906
|
|
907 /* Represents the bits that can be set in the flags field of the
|
|
908 sched_info structure. */
|
|
909 enum SCHED_FLAGS {
|
|
910 /* If set, generate links between instruction as DEPS_LIST.
|
|
911 Otherwise, generate usual INSN_LIST links. */
|
|
912 USE_DEPS_LIST = 1,
|
|
913 /* Perform data or control (or both) speculation.
|
|
914 Results in generation of data and control speculative dependencies.
|
|
915 Requires USE_DEPS_LIST set. */
|
|
916 DO_SPECULATION = USE_DEPS_LIST << 1,
|
|
917 SCHED_RGN = DO_SPECULATION << 1,
|
|
918 SCHED_EBB = SCHED_RGN << 1,
|
|
919 /* Scheduler can possibly create new basic blocks. Used for assertions. */
|
|
920 NEW_BBS = SCHED_EBB << 1,
|
|
921 SEL_SCHED = NEW_BBS << 1
|
|
922 };
|
|
923
|
|
924 enum SPEC_SCHED_FLAGS {
|
|
925 COUNT_SPEC_IN_CRITICAL_PATH = 1,
|
|
926 PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
|
|
927 PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1,
|
|
928 SEL_SCHED_SPEC_DONT_CHECK_CONTROL = PREFER_NON_CONTROL_SPEC << 1
|
|
929 };
|
|
930
|
|
931 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
|
|
932 != NOTE_INSN_BASIC_BLOCK))
|
|
933
|
|
934 extern FILE *sched_dump;
|
|
935 extern int sched_verbose;
|
|
936
|
|
937 extern spec_info_t spec_info;
|
|
938 extern bool haifa_recovery_bb_ever_added_p;
|
|
939
|
|
940 /* Exception Free Loads:
|
|
941
|
|
942 We define five classes of speculative loads: IFREE, IRISKY,
|
|
943 PFREE, PRISKY, and MFREE.
|
|
944
|
|
945 IFREE loads are loads that are proved to be exception-free, just
|
|
946 by examining the load insn. Examples for such loads are loads
|
|
947 from TOC and loads of global data.
|
|
948
|
|
949 IRISKY loads are loads that are proved to be exception-risky,
|
|
950 just by examining the load insn. Examples for such loads are
|
|
951 volatile loads and loads from shared memory.
|
|
952
|
|
953 PFREE loads are loads for which we can prove, by examining other
|
|
954 insns, that they are exception-free. Currently, this class consists
|
|
955 of loads for which we are able to find a "similar load", either in
|
|
956 the target block, or, if only one split-block exists, in that split
|
|
957 block. Load2 is similar to load1 if both have same single base
|
|
958 register. We identify only part of the similar loads, by finding
|
|
959 an insn upon which both load1 and load2 have a DEF-USE dependence.
|
|
960
|
|
961 PRISKY loads are loads for which we can prove, by examining other
|
|
962 insns, that they are exception-risky. Currently we have two proofs for
|
|
963 such loads. The first proof detects loads that are probably guarded by a
|
|
964 test on the memory address. This proof is based on the
|
|
965 backward and forward data dependence information for the region.
|
|
966 Let load-insn be the examined load.
|
|
967 Load-insn is PRISKY iff ALL the following hold:
|
|
968
|
|
969 - insn1 is not in the same block as load-insn
|
|
970 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
|
|
971 - test-insn is either a compare or a branch, not in the same block
|
|
972 as load-insn
|
|
973 - load-insn is reachable from test-insn
|
|
974 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
|
|
975
|
|
976 This proof might fail when the compare and the load are fed
|
|
977 by an insn not in the region. To solve this, we will add to this
|
|
978 group all loads that have no input DEF-USE dependence.
|
|
979
|
|
980 The second proof detects loads that are directly or indirectly
|
|
981 fed by a speculative load. This proof is affected by the
|
|
982 scheduling process. We will use the flag fed_by_spec_load.
|
|
983 Initially, all insns have this flag reset. After a speculative
|
|
984 motion of an insn, if insn is either a load, or marked as
|
|
985 fed_by_spec_load, we will also mark as fed_by_spec_load every
|
|
986 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
|
|
987 load which is fed_by_spec_load is also PRISKY.
|
|
988
|
|
989 MFREE (maybe-free) loads are all the remaining loads. They may be
|
|
990 exception-free, but we cannot prove it.
|
|
991
|
|
992 Now, all loads in IFREE and PFREE classes are considered
|
|
993 exception-free, while all loads in IRISKY and PRISKY classes are
|
|
994 considered exception-risky. As for loads in the MFREE class,
|
|
995 these are considered either exception-free or exception-risky,
|
|
996 depending on whether we are pessimistic or optimistic. We have
|
|
997 to take the pessimistic approach to assure the safety of
|
|
998 speculative scheduling, but we can take the optimistic approach
|
|
999 by invoking the -fsched_spec_load_dangerous option. */
|
|
1000
|
|
1001 enum INSN_TRAP_CLASS
|
|
1002 {
|
|
1003 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
|
|
1004 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
|
|
1005 };
|
|
1006
|
|
1007 #define WORST_CLASS(class1, class2) \
|
|
1008 ((class1 > class2) ? class1 : class2)
|
|
1009
|
|
1010 #ifndef __GNUC__
|
|
1011 #define __inline
|
|
1012 #endif
|
|
1013
|
|
1014 #ifndef HAIFA_INLINE
|
|
1015 #define HAIFA_INLINE __inline
|
|
1016 #endif
|
|
1017
|
|
1018 struct sched_deps_info_def
|
|
1019 {
|
|
1020 /* Called when computing dependencies for a JUMP_INSN. This function
|
|
1021 should store the set of registers that must be considered as set by
|
|
1022 the jump in the regset. */
|
|
1023 void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
|
|
1024
|
|
1025 /* Start analyzing insn. */
|
|
1026 void (*start_insn) (rtx);
|
|
1027
|
|
1028 /* Finish analyzing insn. */
|
|
1029 void (*finish_insn) (void);
|
|
1030
|
|
1031 /* Start analyzing insn LHS (Left Hand Side). */
|
|
1032 void (*start_lhs) (rtx);
|
|
1033
|
|
1034 /* Finish analyzing insn LHS. */
|
|
1035 void (*finish_lhs) (void);
|
|
1036
|
|
1037 /* Start analyzing insn RHS (Right Hand Side). */
|
|
1038 void (*start_rhs) (rtx);
|
|
1039
|
|
1040 /* Finish analyzing insn RHS. */
|
|
1041 void (*finish_rhs) (void);
|
|
1042
|
|
1043 /* Note set of the register. */
|
|
1044 void (*note_reg_set) (int);
|
|
1045
|
|
1046 /* Note clobber of the register. */
|
|
1047 void (*note_reg_clobber) (int);
|
|
1048
|
|
1049 /* Note use of the register. */
|
|
1050 void (*note_reg_use) (int);
|
|
1051
|
|
1052 /* Note memory dependence of type DS between MEM1 and MEM2 (which is
|
|
1053 in the INSN2). */
|
|
1054 void (*note_mem_dep) (rtx mem1, rtx mem2, rtx insn2, ds_t ds);
|
|
1055
|
|
1056 /* Note a dependence of type DS from the INSN. */
|
|
1057 void (*note_dep) (rtx insn, ds_t ds);
|
|
1058
|
|
1059 /* Nonzero if we should use cselib for better alias analysis. This
|
|
1060 must be 0 if the dependency information is used after sched_analyze
|
|
1061 has completed, e.g. if we're using it to initialize state for successor
|
|
1062 blocks in region scheduling. */
|
|
1063 unsigned int use_cselib : 1;
|
|
1064
|
|
1065 /* If set, generate links between instruction as DEPS_LIST.
|
|
1066 Otherwise, generate usual INSN_LIST links. */
|
|
1067 unsigned int use_deps_list : 1;
|
|
1068
|
|
1069 /* Generate data and control speculative dependencies.
|
|
1070 Requires USE_DEPS_LIST set. */
|
|
1071 unsigned int generate_spec_deps : 1;
|
|
1072 };
|
|
1073
|
|
1074 extern struct sched_deps_info_def *sched_deps_info;
|
|
1075
|
|
1076
|
|
1077 /* Functions in sched-deps.c. */
|
|
1078 extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
|
|
1079 extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t);
|
|
1080 extern void add_dependence (rtx, rtx, enum reg_note);
|
|
1081 extern void sched_analyze (struct deps *, rtx, rtx);
|
|
1082 extern void init_deps (struct deps *);
|
|
1083 extern void free_deps (struct deps *);
|
|
1084 extern void init_deps_global (void);
|
|
1085 extern void finish_deps_global (void);
|
|
1086 extern void deps_analyze_insn (struct deps *, rtx);
|
|
1087 extern void remove_from_deps (struct deps *, rtx);
|
|
1088
|
|
1089 extern dw_t get_dep_weak_1 (ds_t, ds_t);
|
|
1090 extern dw_t get_dep_weak (ds_t, ds_t);
|
|
1091 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
|
|
1092 extern dw_t estimate_dep_weak (rtx, rtx);
|
|
1093 extern ds_t ds_merge (ds_t, ds_t);
|
|
1094 extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx);
|
|
1095 extern ds_t ds_max_merge (ds_t, ds_t);
|
|
1096 extern dw_t ds_weak (ds_t);
|
|
1097 extern ds_t ds_get_speculation_types (ds_t);
|
|
1098 extern ds_t ds_get_max_dep_weak (ds_t);
|
|
1099
|
|
1100 extern void sched_deps_init (bool);
|
|
1101 extern void sched_deps_finish (void);
|
|
1102
|
|
1103 extern void haifa_note_reg_set (int);
|
|
1104 extern void haifa_note_reg_clobber (int);
|
|
1105 extern void haifa_note_reg_use (int);
|
|
1106
|
|
1107 extern void maybe_extend_reg_info_p (void);
|
|
1108
|
|
1109 extern void deps_start_bb (struct deps *, rtx);
|
|
1110 extern enum reg_note ds_to_dt (ds_t);
|
|
1111
|
|
1112 extern bool deps_pools_are_empty_p (void);
|
|
1113 extern void sched_free_deps (rtx, rtx, bool);
|
|
1114 extern void extend_dependency_caches (int, bool);
|
|
1115
|
|
1116 extern void debug_ds (ds_t);
|
|
1117
|
|
1118 /* Functions in haifa-sched.c. */
|
|
1119 extern int haifa_classify_insn (const_rtx);
|
|
1120 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
|
|
1121 extern int no_real_insns_p (const_rtx, const_rtx);
|
|
1122
|
|
1123 extern int insn_cost (rtx);
|
|
1124 extern int dep_cost_1 (dep_t, dw_t);
|
|
1125 extern int dep_cost (dep_t);
|
|
1126 extern int set_priorities (rtx, rtx);
|
|
1127
|
|
1128 extern void schedule_block (basic_block *);
|
|
1129
|
|
1130 extern int cycle_issued_insns;
|
|
1131 extern int issue_rate;
|
|
1132 extern int dfa_lookahead;
|
|
1133
|
|
1134 extern void ready_sort (struct ready_list *);
|
|
1135 extern rtx ready_element (struct ready_list *, int);
|
|
1136 extern rtx *ready_lastpos (struct ready_list *);
|
|
1137
|
|
1138 extern int try_ready (rtx);
|
|
1139 extern void sched_extend_ready_list (int);
|
|
1140 extern void sched_finish_ready_list (void);
|
|
1141 extern void sched_change_pattern (rtx, rtx);
|
|
1142 extern int sched_speculate_insn (rtx, ds_t, rtx *);
|
|
1143 extern void unlink_bb_notes (basic_block, basic_block);
|
|
1144 extern void add_block (basic_block, basic_block);
|
|
1145 extern rtx bb_note (basic_block);
|
|
1146 extern void concat_note_lists (rtx, rtx *);
|
|
1147 extern rtx sched_emit_insn (rtx);
|
|
1148
|
|
1149
|
|
1150 /* Types and functions in sched-rgn.c. */
|
|
1151
|
|
1152 /* A region is the main entity for interblock scheduling: insns
|
|
1153 are allowed to move between blocks in the same region, along
|
|
1154 control flow graph edges, in the 'up' direction. */
|
|
1155 typedef struct
|
|
1156 {
|
|
1157 /* Number of extended basic blocks in region. */
|
|
1158 int rgn_nr_blocks;
|
|
1159 /* cblocks in the region (actually index in rgn_bb_table). */
|
|
1160 int rgn_blocks;
|
|
1161 /* Dependencies for this region are already computed. Basically, indicates,
|
|
1162 that this is a recovery block. */
|
|
1163 unsigned int dont_calc_deps : 1;
|
|
1164 /* This region has at least one non-trivial ebb. */
|
|
1165 unsigned int has_real_ebb : 1;
|
|
1166 }
|
|
1167 region;
|
|
1168
|
|
1169 extern int nr_regions;
|
|
1170 extern region *rgn_table;
|
|
1171 extern int *rgn_bb_table;
|
|
1172 extern int *block_to_bb;
|
|
1173 extern int *containing_rgn;
|
|
1174
|
|
1175 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
|
|
1176 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
|
|
1177 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
|
|
1178 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
|
|
1179 #define BLOCK_TO_BB(block) (block_to_bb[block])
|
|
1180 #define CONTAINING_RGN(block) (containing_rgn[block])
|
|
1181
|
|
1182 /* The mapping from ebb to block. */
|
|
1183 extern int *ebb_head;
|
|
1184 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
|
|
1185 #define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
|
|
1186 #define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
|
|
1187 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
|
|
1188
|
|
1189 extern int current_nr_blocks;
|
|
1190 extern int current_blocks;
|
|
1191 extern int target_bb;
|
|
1192
|
|
1193 extern bool sched_is_disabled_for_current_region_p (void);
|
|
1194 extern void sched_rgn_init (bool);
|
|
1195 extern void sched_rgn_finish (void);
|
|
1196 extern void rgn_setup_region (int);
|
|
1197 extern void sched_rgn_compute_dependencies (int);
|
|
1198 extern void sched_rgn_local_init (int);
|
|
1199 extern void sched_rgn_local_finish (void);
|
|
1200 extern void sched_rgn_local_free (void);
|
|
1201 extern void extend_regions (void);
|
|
1202 extern void rgn_make_new_region_out_of_new_block (basic_block);
|
|
1203
|
|
1204 extern void compute_priorities (void);
|
|
1205 extern void increase_insn_priority (rtx, int);
|
|
1206 extern void debug_rgn_dependencies (int);
|
|
1207 extern void debug_dependencies (rtx, rtx);
|
|
1208 extern void free_rgn_deps (void);
|
|
1209 extern int contributes_to_priority (rtx, rtx);
|
|
1210 extern void extend_rgns (int *, int *, sbitmap, int *);
|
|
1211 extern void deps_join (struct deps *, struct deps *);
|
|
1212
|
|
1213 extern void rgn_setup_common_sched_info (void);
|
|
1214 extern void rgn_setup_sched_infos (void);
|
|
1215
|
|
1216 extern void debug_regions (void);
|
|
1217 extern void debug_region (int);
|
|
1218 extern void dump_region_dot (FILE *, int);
|
|
1219 extern void dump_region_dot_file (const char *, int);
|
|
1220
|
|
1221 extern void haifa_sched_init (void);
|
|
1222 extern void haifa_sched_finish (void);
|
|
1223
|
|
1224 /* sched-deps.c interface to walk, add, search, update, resolve, delete
|
|
1225 and debug instruction dependencies. */
|
|
1226
|
|
1227 /* Constants defining dependences lists. */
|
|
1228
|
|
1229 /* No list. */
|
|
1230 #define SD_LIST_NONE (0)
|
|
1231
|
|
1232 /* hard_back_deps. */
|
|
1233 #define SD_LIST_HARD_BACK (1)
|
|
1234
|
|
1235 /* spec_back_deps. */
|
|
1236 #define SD_LIST_SPEC_BACK (2)
|
|
1237
|
|
1238 /* forw_deps. */
|
|
1239 #define SD_LIST_FORW (4)
|
|
1240
|
|
1241 /* resolved_back_deps. */
|
|
1242 #define SD_LIST_RES_BACK (8)
|
|
1243
|
|
1244 /* resolved_forw_deps. */
|
|
1245 #define SD_LIST_RES_FORW (16)
|
|
1246
|
|
1247 #define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
|
|
1248
|
|
1249 /* A type to hold above flags. */
|
|
1250 typedef int sd_list_types_def;
|
|
1251
|
|
1252 extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *);
|
|
1253
|
|
1254 /* Iterator to walk through, resolve and delete dependencies. */
|
|
1255 struct _sd_iterator
|
|
1256 {
|
|
1257 /* What lists to walk. Can be any combination of SD_LIST_* flags. */
|
|
1258 sd_list_types_def types;
|
|
1259
|
|
1260 /* Instruction dependencies lists of which will be walked. */
|
|
1261 rtx insn;
|
|
1262
|
|
1263 /* Pointer to the next field of the previous element. This is not
|
|
1264 simply a pointer to the next element to allow easy deletion from the
|
|
1265 list. When a dep is being removed from the list the iterator
|
|
1266 will automatically advance because the value in *linkp will start
|
|
1267 referring to the next element. */
|
|
1268 dep_link_t *linkp;
|
|
1269
|
|
1270 /* True if the current list is a resolved one. */
|
|
1271 bool resolved_p;
|
|
1272 };
|
|
1273
|
|
1274 typedef struct _sd_iterator sd_iterator_def;
|
|
1275
|
|
1276 /* ??? We can move some definitions that are used in below inline functions
|
|
1277 out of sched-int.h to sched-deps.c provided that the below functions will
|
|
1278 become global externals.
|
|
1279 These definitions include:
|
|
1280 * struct _deps_list: opaque pointer is needed at global scope.
|
|
1281 * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
|
|
1282 * struct _dep_node: opaque pointer is needed at scope of
|
|
1283 struct _deps_link. */
|
|
1284
|
|
1285 /* Return initialized iterator. */
|
|
1286 static inline sd_iterator_def
|
|
1287 sd_iterator_start (rtx insn, sd_list_types_def types)
|
|
1288 {
|
|
1289 /* Some dep_link a pointer to which will return NULL. */
|
|
1290 static dep_link_t null_link = NULL;
|
|
1291
|
|
1292 sd_iterator_def i;
|
|
1293
|
|
1294 i.types = types;
|
|
1295 i.insn = insn;
|
|
1296 i.linkp = &null_link;
|
|
1297
|
|
1298 /* Avoid 'uninitialized warning'. */
|
|
1299 i.resolved_p = false;
|
|
1300
|
|
1301 return i;
|
|
1302 }
|
|
1303
|
|
1304 /* Return the current element. */
|
|
1305 static inline bool
|
|
1306 sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr)
|
|
1307 {
|
|
1308 dep_link_t link = *it_ptr->linkp;
|
|
1309
|
|
1310 if (link != NULL)
|
|
1311 {
|
|
1312 *dep_ptr = DEP_LINK_DEP (link);
|
|
1313 return true;
|
|
1314 }
|
|
1315 else
|
|
1316 {
|
|
1317 sd_list_types_def types = it_ptr->types;
|
|
1318
|
|
1319 if (types != SD_LIST_NONE)
|
|
1320 /* Switch to next list. */
|
|
1321 {
|
|
1322 deps_list_t list;
|
|
1323
|
|
1324 sd_next_list (it_ptr->insn,
|
|
1325 &it_ptr->types, &list, &it_ptr->resolved_p);
|
|
1326
|
|
1327 it_ptr->linkp = &DEPS_LIST_FIRST (list);
|
|
1328
|
|
1329 return sd_iterator_cond (it_ptr, dep_ptr);
|
|
1330 }
|
|
1331
|
|
1332 *dep_ptr = NULL;
|
|
1333 return false;
|
|
1334 }
|
|
1335 }
|
|
1336
|
|
1337 /* Advance iterator. */
|
|
1338 static inline void
|
|
1339 sd_iterator_next (sd_iterator_def *it_ptr)
|
|
1340 {
|
|
1341 it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp);
|
|
1342 }
|
|
1343
|
|
1344 /* A cycle wrapper. */
|
|
1345 #define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP) \
|
|
1346 for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES)); \
|
|
1347 sd_iterator_cond (&(ITER), &(DEP)); \
|
|
1348 sd_iterator_next (&(ITER)))
|
|
1349
|
|
1350 extern int sd_lists_size (const_rtx, sd_list_types_def);
|
|
1351 extern bool sd_lists_empty_p (const_rtx, sd_list_types_def);
|
|
1352 extern void sd_init_insn (rtx);
|
|
1353 extern void sd_finish_insn (rtx);
|
|
1354 extern dep_t sd_find_dep_between (rtx, rtx, bool);
|
|
1355 extern void sd_add_dep (dep_t, bool);
|
|
1356 extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
|
|
1357 extern void sd_resolve_dep (sd_iterator_def);
|
|
1358 extern void sd_copy_back_deps (rtx, rtx, bool);
|
|
1359 extern void sd_delete_dep (sd_iterator_def);
|
|
1360 extern void sd_debug_lists (rtx, sd_list_types_def);
|
|
1361
|
|
1362 #endif /* INSN_SCHEDULING */
|
|
1363
|
|
1364 /* Functions in sched-vis.c. These must be outside INSN_SCHEDULING as
|
|
1365 sched-vis.c is compiled always. */
|
|
1366 extern void print_insn (char *, const_rtx, int);
|
|
1367 extern void print_pattern (char *, const_rtx, int);
|
|
1368 extern void print_value (char *, const_rtx, int);
|
|
1369
|
|
1370 #endif /* GCC_SCHED_INT_H */
|