1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992-2020 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #ifndef GCC_SCHED_INT_H
22 #define GCC_SCHED_INT_H
23
24 #ifdef INSN_SCHEDULING
25
26 /* Identificator of a scheduler pass. */
27 enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,
28 SCHED_SMS_PASS, SCHED_SEL_PASS };
29
30 /* The algorithm used to implement -fsched-pressure. */
31 enum sched_pressure_algorithm
32 {
33 SCHED_PRESSURE_NONE,
34 SCHED_PRESSURE_WEIGHTED,
35 SCHED_PRESSURE_MODEL
36 };
37
38 typedef vec<basic_block> bb_vec_t;
39 typedef vec<rtx_insn *> insn_vec_t;
40 typedef vec<rtx_insn *> rtx_vec_t;
41
42 extern void sched_init_bbs (void);
43
44 extern void sched_extend_luids (void);
45 extern void sched_init_insn_luid (rtx_insn *);
46 extern void sched_init_luids (bb_vec_t);
47 extern void sched_finish_luids (void);
48
49 extern void sched_extend_target (void);
50
51 extern void haifa_init_h_i_d (bb_vec_t);
52 extern void haifa_finish_h_i_d (void);
53
54 /* Hooks that are common to all the schedulers. */
55 struct common_sched_info_def
56 {
57 /* Called after blocks were rearranged due to movement of jump instruction.
58 The first parameter - index of basic block, in which jump currently is.
59 The second parameter - index of basic block, in which jump used
60 to be.
61 The third parameter - index of basic block, that follows the second
62 parameter. */
63 void (*fix_recovery_cfg) (int, int, int);
64
65 /* Called to notify frontend, that new basic block is being added.
66 The first parameter - new basic block.
67 The second parameter - block, after which new basic block is being added,
68 or the exit block, if recovery block is being added,
69 or NULL, if standalone block is being added. */
70 void (*add_block) (basic_block, basic_block);
71
72 /* Estimate number of insns in the basic block. */
73 int (*estimate_number_of_insns) (basic_block);
74
75 /* Given a non-insn (!INSN_P (x)) return
76 -1 - if this rtx don't need a luid.
77 0 - if it should have the same luid as the previous insn.
78 1 - if it needs a separate luid. */
79 int (*luid_for_non_insn) (rtx);
80
81 /* Scheduler pass identifier. It is preferably used in assertions. */
82 enum sched_pass_id_t sched_pass_id;
83 };
84
85 extern struct common_sched_info_def *common_sched_info;
86
87 extern const struct common_sched_info_def haifa_common_sched_info;
88
89 /* Return true if selective scheduling pass is working. */
90 static inline bool
sel_sched_p(void)91 sel_sched_p (void)
92 {
93 return common_sched_info->sched_pass_id == SCHED_SEL_PASS;
94 }
95
96 /* Returns maximum priority that an insn was assigned to. */
97 extern int get_rgn_sched_max_insns_priority (void);
98
99 /* Increases effective priority for INSN by AMOUNT. */
100 extern void sel_add_to_insn_priority (rtx, int);
101
102 /* True if during selective scheduling we need to emulate some of haifa
103 scheduler behavior. */
104 extern int sched_emulate_haifa_p;
105
106 /* Mapping from INSN_UID to INSN_LUID. In the end all other per insn data
107 structures should be indexed by luid. */
108 extern vec<int> sched_luids;
109 #define INSN_LUID(INSN) (sched_luids[INSN_UID (INSN)])
110 #define LUID_BY_UID(UID) (sched_luids[UID])
111
112 #define SET_INSN_LUID(INSN, LUID) \
113 (sched_luids[INSN_UID (INSN)] = (LUID))
114
115 /* The highest INSN_LUID. */
116 extern int sched_max_luid;
117
118 extern int insn_luid (rtx);
119
120 /* This list holds ripped off notes from the current block. These notes will
121 be attached to the beginning of the block when its scheduling is
122 finished. */
123 extern rtx_insn *note_list;
124
125 extern void remove_notes (rtx_insn *, rtx_insn *);
126 extern rtx_insn *restore_other_notes (rtx_insn *, basic_block);
127 extern void sched_insns_init (rtx);
128 extern void sched_insns_finish (void);
129
130 extern void *xrecalloc (void *, size_t, size_t, size_t);
131
132 extern void reemit_notes (rtx_insn *);
133
134 /* Functions in haifa-sched.c. */
135 extern int haifa_classify_insn (const_rtx);
136
137 /* Functions in sel-sched-ir.c. */
138 extern void sel_find_rgns (void);
139 extern void sel_mark_hard_insn (rtx);
140
141 extern size_t dfa_state_size;
142
143 extern void advance_state (state_t);
144
145 extern void setup_sched_dump (void);
146 extern void sched_init (void);
147 extern void sched_finish (void);
148
149 extern bool sel_insn_is_speculation_check (rtx);
150
151 /* Describe the ready list of the scheduler.
152 VEC holds space enough for all insns in the current region. VECLEN
153 says how many exactly.
154 FIRST is the index of the element with the highest priority; i.e. the
155 last one in the ready list, since elements are ordered by ascending
156 priority.
157 N_READY determines how many insns are on the ready list.
158 N_DEBUG determines how many debug insns are on the ready list. */
159 struct ready_list
160 {
161 rtx_insn **vec;
162 int veclen;
163 int first;
164 int n_ready;
165 int n_debug;
166 };
167
168 extern signed char *ready_try;
169 extern struct ready_list ready;
170
171 extern int max_issue (struct ready_list *, int, state_t, bool, int *);
172
173 extern void ebb_compute_jump_reg_dependencies (rtx, regset);
174
175 extern edge find_fallthru_edge_from (basic_block);
176
177 extern void (* sched_init_only_bb) (basic_block, basic_block);
178 extern basic_block (* sched_split_block) (basic_block, rtx);
179 extern basic_block sched_split_block_1 (basic_block, rtx);
180 extern basic_block (* sched_create_empty_bb) (basic_block);
181 extern basic_block sched_create_empty_bb_1 (basic_block);
182
183 extern basic_block sched_create_recovery_block (basic_block *);
184 extern void sched_create_recovery_edges (basic_block, basic_block,
185 basic_block);
186
187 /* Pointer to data describing the current DFA state. */
188 extern state_t curr_state;
189
190 /* Type to represent status of a dependence. */
191 typedef unsigned int ds_t;
192 #define BITS_PER_DEP_STATUS HOST_BITS_PER_INT
193
194 /* Type to represent weakness of speculative dependence. */
195 typedef unsigned int dw_t;
196
197 extern enum reg_note ds_to_dk (ds_t);
198 extern ds_t dk_to_ds (enum reg_note);
199
200 /* Describe a dependency that can be broken by making a replacement
201 in one of the patterns. LOC is the location, ORIG and NEWVAL the
202 two alternative contents, and INSN the instruction that must be
203 changed. */
204 struct dep_replacement
205 {
206 rtx *loc;
207 rtx orig;
208 rtx newval;
209 rtx_insn *insn;
210 };
211
212 /* Information about the dependency. */
213 struct _dep
214 {
215 /* Producer. */
216 rtx_insn *pro;
217
218 /* Consumer. */
219 rtx_insn *con;
220
221 /* If nonnull, holds a pointer to information about how to break the
222 dependency by making a replacement in one of the insns. There is
223 only one such dependency for each insn that must be modified in
224 order to break such a dependency. */
225 struct dep_replacement *replace;
226
227 /* Dependency status. This field holds all dependency types and additional
228 information for speculative dependencies. */
229 ds_t status;
230
231 /* Dependency major type. This field is superseded by STATUS above.
232 Though, it is still in place because some targets use it. */
233 ENUM_BITFIELD(reg_note) type:6;
234
235 unsigned nonreg:1;
236 unsigned multiple:1;
237
238 /* Cached cost of the dependency. Make sure to update UNKNOWN_DEP_COST
239 when changing the size of this field. */
240 int cost:20;
241
242 unsigned unused:4;
243 };
244
245 #define UNKNOWN_DEP_COST ((int) ((unsigned int) -1 << 19))
246
247 typedef struct _dep dep_def;
248 typedef dep_def *dep_t;
249
250 #define DEP_PRO(D) ((D)->pro)
251 #define DEP_CON(D) ((D)->con)
252 #define DEP_TYPE(D) ((D)->type)
253 #define DEP_STATUS(D) ((D)->status)
254 #define DEP_COST(D) ((D)->cost)
255 #define DEP_NONREG(D) ((D)->nonreg)
256 #define DEP_MULTIPLE(D) ((D)->multiple)
257 #define DEP_REPLACE(D) ((D)->replace)
258
259 /* Functions to work with dep. */
260
261 extern void init_dep_1 (dep_t, rtx_insn *, rtx_insn *, enum reg_note, ds_t);
262 extern void init_dep (dep_t, rtx_insn *, rtx_insn *, enum reg_note);
263
264 extern void sd_debug_dep (dep_t);
265
266 /* Definition of this struct resides below. */
267 struct _dep_node;
268 typedef struct _dep_node *dep_node_t;
269
270 /* A link in the dependency list. This is essentially an equivalent of a
271 single {INSN, DEPS}_LIST rtx. */
272 struct _dep_link
273 {
274 /* Dep node with all the data. */
275 dep_node_t node;
276
277 /* Next link in the list. For the last one it is NULL. */
278 struct _dep_link *next;
279
280 /* Pointer to the next field of the previous link in the list.
281 For the first link this points to the deps_list->first.
282
283 With help of this field it is easy to remove and insert links to the
284 list. */
285 struct _dep_link **prev_nextp;
286 };
287 typedef struct _dep_link *dep_link_t;
288
289 #define DEP_LINK_NODE(N) ((N)->node)
290 #define DEP_LINK_NEXT(N) ((N)->next)
291 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
292
293 /* Macros to work dep_link. For most usecases only part of the dependency
294 information is need. These macros conveniently provide that piece of
295 information. */
296
297 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
298 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
299 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
300 #define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
301 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
302
303 /* A list of dep_links. */
304 struct _deps_list
305 {
306 /* First element. */
307 dep_link_t first;
308
309 /* Total number of elements in the list. */
310 int n_links;
311 };
312 typedef struct _deps_list *deps_list_t;
313
314 #define DEPS_LIST_FIRST(L) ((L)->first)
315 #define DEPS_LIST_N_LINKS(L) ((L)->n_links)
316
317 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
318 additional dependents con0 and con2, and con1 is dependent on additional
319 insns pro0 and pro1:
320
321 .con0 pro0
322 . ^ |
323 . | |
324 . | |
325 . X A
326 . | |
327 . | |
328 . | V
329 .pro1--Y-->con1
330 . | ^
331 . | |
332 . | |
333 . Z B
334 . | |
335 . | |
336 . V |
337 .con2 pro2
338
339 This is represented using a "dep_node" for each dependence arc, which are
340 connected as follows (diagram is centered around Y which is fully shown;
341 other dep_nodes shown partially):
342
343 . +------------+ +--------------+ +------------+
344 . : dep_node X : | dep_node Y | : dep_node Z :
345 . : : | | : :
346 . : : | | : :
347 . : forw : | forw | : forw :
348 . : +--------+ : | +--------+ | : +--------+ :
349 forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
350 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
351 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
352 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
353 . ^ ^ : | ^ | : | | ^ | | : | | :
354 . | | : | | | : | | | | | : | | :
355 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
356 . | : | | | : | | | | | : | | | :
357 . | : | +----+ | : | | +----+ | | : | +----+ | :
358 . | : | |prev| | : | | |prev| | | : | |prev| | :
359 . | : | |next| | : | | |next| | | : | |next| | :
360 . | : | +----+ | : | | +----+ | | : | +----+ | :
361 . | : | | :<-+ | | | |<-+ : | | :<-+
362 . | : | +----+ | : | | | +----+ | | | : | +----+ | : |
363 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
364 . | : | +----+ | : | | +----+ | | : | +----+ | :
365 . | : | | : | | | | : | | :
366 . | : +--------+ : | +--------+ | : +--------+ :
367 . | : : | | : :
368 . | : SAME pro1 : | +--------+ | : SAME pro1 :
369 . | : DIFF con0 : | |dep | | : DIFF con2 :
370 . | : : | | | | : :
371 . | | | +----+ | |
372 .RTX<------------------------+--+-|pro1| | |
373 .pro1 | | +----+ | |
374 . | | | |
375 . | | +----+ | |
376 .RTX<------------------------+--+-|con1| | |
377 .con1 | | +----+ | |
378 . | | | | |
379 . | | | +----+ | |
380 . | | | |kind| | |
381 . | | | +----+ | |
382 . | : : | | |stat| | | : :
383 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 :
384 . | : SAME con1 : | | | | : SAME con1 :
385 . | : : | +--------+ | : :
386 . | : : | | : :
387 . | : back : | back | : back :
388 . v : +--------+ : | +--------+ | : +--------+ :
389 back_deps : |dep_link| : | |dep_link| | : |dep_link| :
390 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
391 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
392 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
393 . ^ : | ^ | : | | ^ | | : | | :
394 . | : | | | : | | | | | : | | :
395 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
396 . : | | | : | | | | | : | | | :
397 . : | +----+ | : | | +----+ | | : | +----+ | :
398 . : | |prev| | : | | |prev| | | : | |prev| | :
399 . : | |next| | : | | |next| | | : | |next| | :
400 . : | +----+ | : | | +----+ | | : | +----+ | :
401 . : | | :<-+ | | | |<-+ : | | :<-+
402 . : | +----+ | : | | | +----+ | | | : | +----+ | : |
403 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
404 . : | +----+ | : | | +----+ | | : | +----+ | :
405 . : | | : | | | | : | | :
406 . : +--------+ : | +--------+ | : +--------+ :
407 . : : | | : :
408 . : dep_node A : | dep_node Y | : dep_node B :
409 . +------------+ +--------------+ +------------+
410 */
411
412 struct _dep_node
413 {
414 /* Backward link. */
415 struct _dep_link back;
416
417 /* The dep. */
418 struct _dep dep;
419
420 /* Forward link. */
421 struct _dep_link forw;
422 };
423
424 #define DEP_NODE_BACK(N) (&(N)->back)
425 #define DEP_NODE_DEP(N) (&(N)->dep)
426 #define DEP_NODE_FORW(N) (&(N)->forw)
427
428 /* The following enumeration values tell us what dependencies we
429 should use to implement the barrier. We use true-dependencies for
430 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
431 enum reg_pending_barrier_mode
432 {
433 NOT_A_BARRIER = 0,
434 MOVE_BARRIER,
435 TRUE_BARRIER
436 };
437
438 /* Whether a register movement is associated with a call. */
439 enum post_call_group
440 {
441 not_post_call,
442 post_call,
443 post_call_initial
444 };
445
446 /* Insns which affect pseudo-registers. */
447 struct deps_reg
448 {
449 rtx_insn_list *uses;
450 rtx_insn_list *sets;
451 rtx_insn_list *implicit_sets;
452 rtx_insn_list *control_uses;
453 rtx_insn_list *clobbers;
454 int uses_length;
455 int clobbers_length;
456 };
457
458 /* Describe state of dependencies used during sched_analyze phase. */
459 class deps_desc
460 {
461 public:
462 /* The *_insns and *_mems are paired lists. Each pending memory operation
463 will have a pointer to the MEM rtx on one list and a pointer to the
464 containing insn on the other list in the same place in the list. */
465
466 /* We can't use add_dependence like the old code did, because a single insn
467 may have multiple memory accesses, and hence needs to be on the list
468 once for each memory access. Add_dependence won't let you add an insn
469 to a list more than once. */
470
471 /* An INSN_LIST containing all insns with pending read operations. */
472 rtx_insn_list *pending_read_insns;
473
474 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
475 rtx_expr_list *pending_read_mems;
476
477 /* An INSN_LIST containing all insns with pending write operations. */
478 rtx_insn_list *pending_write_insns;
479
480 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
481 rtx_expr_list *pending_write_mems;
482
483 /* An INSN_LIST containing all jump insns. */
484 rtx_insn_list *pending_jump_insns;
485
486 /* We must prevent the above lists from ever growing too large since
487 the number of dependencies produced is at least O(N*N),
488 and execution time is at least O(4*N*N), as a function of the
489 length of these pending lists. */
490
491 /* Indicates the length of the pending_read list. */
492 int pending_read_list_length;
493
494 /* Indicates the length of the pending_write list. */
495 int pending_write_list_length;
496
497 /* Length of the pending memory flush list plus the length of the pending
498 jump insn list. Large functions with no calls may build up extremely
499 large lists. */
500 int pending_flush_length;
501
502 /* The last insn upon which all memory references must depend.
503 This is an insn which flushed the pending lists, creating a dependency
504 between it and all previously pending memory references. This creates
505 a barrier (or a checkpoint) which no memory reference is allowed to cross.
506
507 This includes all non constant CALL_INSNs. When we do interprocedural
508 alias analysis, this restriction can be relaxed.
509 This may also be an INSN that writes memory if the pending lists grow
510 too large. */
511 rtx_insn_list *last_pending_memory_flush;
512
513 /* A list of the last function calls we have seen. We use a list to
514 represent last function calls from multiple predecessor blocks.
515 Used to prevent register lifetimes from expanding unnecessarily. */
516 rtx_insn_list *last_function_call;
517
518 /* A list of the last function calls that may not return normally
519 we have seen. We use a list to represent last function calls from
520 multiple predecessor blocks. Used to prevent moving trapping insns
521 across such calls. */
522 rtx_insn_list *last_function_call_may_noreturn;
523
524 /* A list of insns which use a pseudo register that does not already
525 cross a call. We create dependencies between each of those insn
526 and the next call insn, to ensure that they won't cross a call after
527 scheduling is done. */
528 rtx_insn_list *sched_before_next_call;
529
530 /* Similarly, a list of insns which should not cross a branch. */
531 rtx_insn_list *sched_before_next_jump;
532
533 /* Used to keep post-call pseudo/hard reg movements together with
534 the call. */
535 enum post_call_group in_post_call_group_p;
536
537 /* The last debug insn we've seen. */
538 rtx_insn *last_debug_insn;
539
540 /* The last insn bearing REG_ARGS_SIZE that we've seen. */
541 rtx_insn *last_args_size;
542
543 /* A list of all prologue insns we have seen without intervening epilogue
544 insns, and one of all epilogue insns we have seen without intervening
545 prologue insns. This is used to prevent mixing prologue and epilogue
546 insns. See PR78029. */
547 rtx_insn_list *last_prologue;
548 rtx_insn_list *last_epilogue;
549
550 /* Whether the last *logue insn was an epilogue insn or a prologue insn
551 instead. */
552 bool last_logue_was_epilogue;
553
554 /* The maximum register number for the following arrays. Before reload
555 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
556 int max_reg;
557
558 /* Element N is the next insn that sets (hard or pseudo) register
559 N within the current basic block; or zero, if there is no
560 such insn. Needed for new registers which may be introduced
561 by splitting insns. */
562 struct deps_reg *reg_last;
563
564 /* Element N is set for each register that has any nonzero element
565 in reg_last[N].{uses,sets,clobbers}. */
566 regset_head reg_last_in_use;
567
568 /* Shows the last value of reg_pending_barrier associated with the insn. */
569 enum reg_pending_barrier_mode last_reg_pending_barrier;
570
571 /* True when this context should be treated as a readonly by
572 the analysis. */
573 BOOL_BITFIELD readonly : 1;
574 };
575
576 typedef class deps_desc *deps_t;
577
578 /* This structure holds some state of the current scheduling pass, and
579 contains some function pointers that abstract out some of the non-generic
580 functionality from functions such as schedule_block or schedule_insn.
581 There is one global variable, current_sched_info, which points to the
582 sched_info structure currently in use. */
583 struct haifa_sched_info
584 {
585 /* Add all insns that are initially ready to the ready list. Called once
586 before scheduling a set of insns. */
587 void (*init_ready_list) (void);
588 /* Called after taking an insn from the ready list. Returns nonzero if
589 this insn can be scheduled, nonzero if we should silently discard it. */
590 int (*can_schedule_ready_p) (rtx_insn *);
591 /* Return nonzero if there are more insns that should be scheduled. */
592 int (*schedule_more_p) (void);
593 /* Called after an insn has all its hard dependencies resolved.
594 Adjusts status of instruction (which is passed through second parameter)
595 to indicate if instruction should be moved to the ready list or the
596 queue, or if it should silently discard it (until next resolved
597 dependence). */
598 ds_t (*new_ready) (rtx_insn *, ds_t);
599 /* Compare priority of two insns. Return a positive number if the second
600 insn is to be preferred for scheduling, and a negative one if the first
601 is to be preferred. Zero if they are equally good. */
602 int (*rank) (rtx_insn *, rtx_insn *);
603 /* Return a string that contains the insn uid and optionally anything else
604 necessary to identify this insn in an output. It's valid to use a
605 static buffer for this. The ALIGNED parameter should cause the string
606 to be formatted so that multiple output lines will line up nicely. */
607 const char *(*print_insn) (const rtx_insn *, int);
608 /* Return nonzero if an insn should be included in priority
609 calculations. */
610 int (*contributes_to_priority) (rtx_insn *, rtx_insn *);
611
612 /* Return true if scheduling insn (passed as the parameter) will trigger
613 finish of scheduling current block. */
614 bool (*insn_finishes_block_p) (rtx_insn *);
615
616 /* The boundaries of the set of insns to be scheduled. */
617 rtx_insn *prev_head, *next_tail;
618
619 /* Filled in after the schedule is finished; the first and last scheduled
620 insns. */
621 rtx_insn *head, *tail;
622
623 /* If nonzero, enables an additional sanity check in schedule_block. */
624 unsigned int queue_must_finish_empty:1;
625
626 /* Maximum priority that has been assigned to an insn. */
627 int sched_max_insns_priority;
628
629 /* Hooks to support speculative scheduling. */
630
631 /* Called to notify frontend that instruction is being added (second
632 parameter == 0) or removed (second parameter == 1). */
633 void (*add_remove_insn) (rtx_insn *, int);
634
635 /* Called to notify the frontend that instruction INSN is being
636 scheduled. */
637 void (*begin_schedule_ready) (rtx_insn *insn);
638
639 /* Called to notify the frontend that an instruction INSN is about to be
640 moved to its correct place in the final schedule. This is done for all
641 insns in order of the schedule. LAST indicates the last scheduled
642 instruction. */
643 void (*begin_move_insn) (rtx_insn *insn, rtx_insn *last);
644
645 /* If the second parameter is not NULL, return nonnull value, if the
646 basic block should be advanced.
647 If the second parameter is NULL, return the next basic block in EBB.
648 The first parameter is the current basic block in EBB. */
649 basic_block (*advance_target_bb) (basic_block, rtx_insn *);
650
651 /* Allocate memory, store the frontend scheduler state in it, and
652 return it. */
653 void *(*save_state) (void);
654 /* Restore frontend scheduler state from the argument, and free the
655 memory. */
656 void (*restore_state) (void *);
657
658 /* ??? FIXME: should use straight bitfields inside sched_info instead of
659 this flag field. */
660 unsigned int flags;
661 };
662
663 /* This structure holds description of the properties for speculative
664 scheduling. */
665 struct spec_info_def
666 {
667 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
668 BE_IN_{DATA_CONTROL}. */
669 int mask;
670
671 /* A dump file for additional information on speculative scheduling. */
672 FILE *dump;
673
674 /* Minimal cumulative weakness of speculative instruction's
675 dependencies, so that insn will be scheduled. */
676 dw_t data_weakness_cutoff;
677
678 /* Minimal usefulness of speculative instruction to be considered for
679 scheduling. */
680 int control_weakness_cutoff;
681
682 /* Flags from the enum SPEC_SCHED_FLAGS. */
683 int flags;
684 };
685 typedef struct spec_info_def *spec_info_t;
686
687 extern spec_info_t spec_info;
688
689 extern struct haifa_sched_info *current_sched_info;
690
691 /* Do register pressure sensitive insn scheduling if the flag is set
692 up. */
693 extern enum sched_pressure_algorithm sched_pressure;
694
695 /* Map regno -> its pressure class. The map defined only when
696 SCHED_PRESSURE_P is true. */
697 extern enum reg_class *sched_regno_pressure_class;
698
699 /* Indexed by INSN_UID, the collection of all data associated with
700 a single instruction. */
701
702 struct _haifa_deps_insn_data
703 {
704 /* The number of incoming edges in the forward dependency graph.
705 As scheduling proceeds, counts are decreased. An insn moves to
706 the ready queue when its counter reaches zero. */
707 int dep_count;
708
709 /* Nonzero if instruction has internal dependence
710 (e.g. add_dependence was invoked with (insn == elem)). */
711 unsigned int has_internal_dep;
712
713 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
714 h_i_d because when h_i_d extends, addresses of the deps_list->first
715 change without updating deps_list->first->next->prev_nextp. Thus
716 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
717 list is allocated on the obstack. */
718
719 /* A list of hard backward dependencies. The insn is a consumer of all the
720 deps mentioned here. */
721 deps_list_t hard_back_deps;
722
723 /* A list of speculative (weak) dependencies. The insn is a consumer of all
724 the deps mentioned here. */
725 deps_list_t spec_back_deps;
726
727 /* A list of insns which depend on the instruction. Unlike 'back_deps',
728 it represents forward dependencies. */
729 deps_list_t forw_deps;
730
731 /* A list of scheduled producers of the instruction. Links are being moved
732 from 'back_deps' to 'resolved_back_deps' while scheduling. */
733 deps_list_t resolved_back_deps;
734
735 /* A list of scheduled consumers of the instruction. Links are being moved
736 from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
737 search in 'forw_deps'. */
738 deps_list_t resolved_forw_deps;
739
740 /* If the insn is conditional (either through COND_EXEC, or because
741 it is a conditional branch), this records the condition. NULL
742 for insns that haven't been seen yet or don't have a condition;
743 const_true_rtx to mark an insn without a condition, or with a
744 condition that has been clobbered by a subsequent insn. */
745 rtx cond;
746
747 /* For a conditional insn, a list of insns that could set the condition
748 register. Used when generating control dependencies. */
749 rtx_insn_list *cond_deps;
750
751 /* True if the condition in 'cond' should be reversed to get the actual
752 condition. */
753 unsigned int reverse_cond : 1;
754
755 /* Some insns (e.g. call) are not allowed to move across blocks. */
756 unsigned int cant_move : 1;
757 };
758
759
760 /* Bits used for storing values of the fields in the following
761 structure. */
762 #define INCREASE_BITS 8
763
764 /* The structure describes how the corresponding insn increases the
765 register pressure for each pressure class. */
766 struct reg_pressure_data
767 {
768 /* Pressure increase for given class because of clobber. */
769 unsigned int clobber_increase : INCREASE_BITS;
770 /* Increase in register pressure for given class because of register
771 sets. */
772 unsigned int set_increase : INCREASE_BITS;
773 /* Pressure increase for given class because of unused register
774 set. */
775 unsigned int unused_set_increase : INCREASE_BITS;
776 /* Pressure change: #sets - #deaths. */
777 int change : INCREASE_BITS;
778 };
779
780 /* The following structure describes usage of registers by insns. */
781 struct reg_use_data
782 {
783 /* Regno used in the insn. */
784 int regno;
785 /* Insn using the regno. */
786 rtx_insn *insn;
787 /* Cyclic list of elements with the same regno. */
788 struct reg_use_data *next_regno_use;
789 /* List of elements with the same insn. */
790 struct reg_use_data *next_insn_use;
791 };
792
793 /* The following structure describes used sets of registers by insns.
794 Registers are pseudos whose pressure class is not NO_REGS or hard
795 registers available for allocations. */
796 struct reg_set_data
797 {
798 /* Regno used in the insn. */
799 int regno;
800 /* Insn setting the regno. */
801 rtx insn;
802 /* List of elements with the same insn. */
803 struct reg_set_data *next_insn_set;
804 };
805
806 enum autopref_multipass_data_status {
807 /* Entry is irrelevant for auto-prefetcher. */
808 AUTOPREF_MULTIPASS_DATA_IRRELEVANT = -2,
809 /* Entry is uninitialized. */
810 AUTOPREF_MULTIPASS_DATA_UNINITIALIZED = -1,
811 /* Entry is relevant for auto-prefetcher and insn can be delayed
812 to allow another insn through. */
813 AUTOPREF_MULTIPASS_DATA_NORMAL = 0,
814 /* Entry is relevant for auto-prefetcher, but insn should not be
815 delayed as that will break scheduling. */
816 AUTOPREF_MULTIPASS_DATA_DONT_DELAY = 1
817 };
818
819 /* Data for modeling cache auto-prefetcher. */
820 struct autopref_multipass_data_
821 {
822 /* Base part of memory address. */
823 rtx base;
824
825 /* Memory offsets from the base. */
826 int offset;
827
828 /* Entry status. */
829 enum autopref_multipass_data_status status;
830 };
831 typedef struct autopref_multipass_data_ autopref_multipass_data_def;
832 typedef autopref_multipass_data_def *autopref_multipass_data_t;
833
834 struct _haifa_insn_data
835 {
836 /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
837 because when h_i_d extends, addresses of the deps_list->first
838 change without updating deps_list->first->next->prev_nextp. */
839
840 /* Logical uid gives the original ordering of the insns. */
841 int luid;
842
843 /* A priority for each insn. */
844 int priority;
845
846 /* The fusion priority for each insn. */
847 int fusion_priority;
848
849 /* The minimum clock tick at which the insn becomes ready. This is
850 used to note timing constraints for the insns in the pending list. */
851 int tick;
852
853 /* For insns that are scheduled at a fixed difference from another,
854 this records the tick in which they must be ready. */
855 int exact_tick;
856
857 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
858 subsequent blocks in a region. */
859 int inter_tick;
860
861 /* Used temporarily to estimate an INSN_TICK value for an insn given
862 current knowledge. */
863 int tick_estimate;
864
865 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
866 int queue_index;
867
868 short cost;
869
870 /* '> 0' if priority is valid,
871 '== 0' if priority was not yet computed,
872 '< 0' if priority in invalid and should be recomputed. */
873 signed char priority_status;
874
875 /* Set if there's DEF-USE dependence between some speculatively
876 moved load insn and this one. */
877 unsigned int fed_by_spec_load : 1;
878 unsigned int is_load_insn : 1;
879 /* Nonzero if this insn has negative-cost forward dependencies against
880 an already scheduled insn. */
881 unsigned int feeds_backtrack_insn : 1;
882
883 /* Nonzero if this insn is a shadow of another, scheduled after a fixed
884 delay. We only emit shadows at the end of a cycle, with no other
885 real insns following them. */
886 unsigned int shadow_p : 1;
887
888 /* Used internally in unschedule_insns_until to mark insns that must have
889 their TODO_SPEC recomputed. */
890 unsigned int must_recompute_spec : 1;
891
892 /* What speculations are necessary to apply to schedule the instruction. */
893 ds_t todo_spec;
894
895 /* What speculations were already applied. */
896 ds_t done_spec;
897
898 /* What speculations are checked by this instruction. */
899 ds_t check_spec;
900
901 /* Recovery block for speculation checks. */
902 basic_block recovery_block;
903
904 /* Original pattern of the instruction. */
905 rtx orig_pat;
906
907 /* For insns with DEP_CONTROL dependencies, the predicated pattern if it
908 was ever successfully constructed. */
909 rtx predicated_pat;
910
911 /* The following array contains info how the insn increases register
912 pressure. There is an element for each cover class of pseudos
913 referenced in insns. */
914 struct reg_pressure_data *reg_pressure;
915 /* The following array contains maximal reg pressure between last
916 scheduled insn and given insn. There is an element for each
917 pressure class of pseudos referenced in insns. This info updated
918 after scheduling each insn for each insn between the two
919 mentioned insns. */
920 int *max_reg_pressure;
921 /* The following list contains info about used pseudos and hard
922 registers available for allocation. */
923 struct reg_use_data *reg_use_list;
924 /* The following list contains info about set pseudos and hard
925 registers available for allocation. */
926 struct reg_set_data *reg_set_list;
927 /* Info about how scheduling the insn changes cost of register
928 pressure excess (between source and target). */
929 int reg_pressure_excess_cost_change;
930 int model_index;
931
932 /* Original order of insns in the ready list. */
933 int rfs_debug_orig_order;
934
935 /* The deciding reason for INSN's place in the ready list. */
936 int last_rfs_win;
937
938 /* Two entries for cache auto-prefetcher model: one for mem reads,
939 and one for mem writes. */
940 autopref_multipass_data_def autopref_multipass_data[2];
941 };
942
943 typedef struct _haifa_insn_data haifa_insn_data_def;
944 typedef haifa_insn_data_def *haifa_insn_data_t;
945
946
947 extern vec<haifa_insn_data_def> h_i_d;
948
949 #define HID(INSN) (&h_i_d[INSN_UID (INSN)])
950
951 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
952 sched-rgn.c. */
953 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
954 #define INSN_FUSION_PRIORITY(INSN) (HID (INSN)->fusion_priority)
955 #define INSN_REG_PRESSURE(INSN) (HID (INSN)->reg_pressure)
956 #define INSN_MAX_REG_PRESSURE(INSN) (HID (INSN)->max_reg_pressure)
957 #define INSN_REG_USE_LIST(INSN) (HID (INSN)->reg_use_list)
958 #define INSN_REG_SET_LIST(INSN) (HID (INSN)->reg_set_list)
959 #define INSN_REG_PRESSURE_EXCESS_COST_CHANGE(INSN) \
960 (HID (INSN)->reg_pressure_excess_cost_change)
961 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
962 #define INSN_MODEL_INDEX(INSN) (HID (INSN)->model_index)
963 #define INSN_AUTOPREF_MULTIPASS_DATA(INSN) \
964 (HID (INSN)->autopref_multipass_data)
965
966 typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def;
967 typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t;
968
969
970 extern vec<haifa_deps_insn_data_def> h_d_i_d;
971
972 #define HDID(INSN) (&h_d_i_d[INSN_LUID (INSN)])
973 #define INSN_DEP_COUNT(INSN) (HDID (INSN)->dep_count)
974 #define HAS_INTERNAL_DEP(INSN) (HDID (INSN)->has_internal_dep)
975 #define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
976 #define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
977 #define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
978 #define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
979 #define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
980 #define INSN_CACHED_COND(INSN) (HDID (INSN)->cond)
981 #define INSN_REVERSE_COND(INSN) (HDID (INSN)->reverse_cond)
982 #define INSN_COND_DEPS(INSN) (HDID (INSN)->cond_deps)
983 #define CANT_MOVE(INSN) (HDID (INSN)->cant_move)
984 #define CANT_MOVE_BY_LUID(LUID) (h_d_i_d[LUID].cant_move)
985
986
987 #define INSN_PRIORITY(INSN) (HID (INSN)->priority)
988 #define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
989 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
990 #define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
991 #define DONE_SPEC(INSN) (HID (INSN)->done_spec)
992 #define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
993 #define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
994 #define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
995 #define PREDICATED_PAT(INSN) (HID (INSN)->predicated_pat)
996
997 /* INSN is either a simple or a branchy speculation check. */
998 #define IS_SPECULATION_CHECK_P(INSN) \
999 (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
1000
1001 /* INSN is a speculation check that will simply reexecute the speculatively
1002 scheduled instruction if the speculation fails. */
1003 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
1004 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR_FOR_FN (cfun))
1005
1006 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
1007 speculation fails. Insns in that block will reexecute the speculatively
1008 scheduled code and then will return immediately after INSN thus preserving
1009 semantics of the program. */
1010 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
1011 (RECOVERY_BLOCK (INSN) != NULL \
1012 && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR_FOR_FN (cfun))
1013
1014
1015 /* Dep status (aka ds_t) of the link encapsulates all information for a given
1016 dependency, including everything that is needed for speculative scheduling.
1017
1018 The lay-out of a ds_t is as follows:
1019
1020 1. Integers corresponding to the probability of the dependence to *not*
1021 exist. This is the probability that overcoming this dependence will
1022 not be followed by execution of the recovery code. Note that however
1023 high this probability is, the recovery code should still always be
1024 generated to preserve semantics of the program.
1025
1026 The probability values can be set or retrieved using the functions
1027 the set_dep_weak() and get_dep_weak() in sched-deps.c. The values
1028 are always in the range [0, MAX_DEP_WEAK].
1029
1030 BEGIN_DATA : BITS_PER_DEP_WEAK
1031 BE_IN_DATA : BITS_PER_DEP_WEAK
1032 BEGIN_CONTROL : BITS_PER_DEP_WEAK
1033 BE_IN_CONTROL : BITS_PER_DEP_WEAK
1034
1035 The basic type of DS_T is a host int. For a 32-bits int, the values
1036 will each take 6 bits.
1037
1038 2. The type of dependence. This supercedes the old-style REG_NOTE_KIND
1039 values. TODO: Use this field instead of DEP_TYPE, or make DEP_TYPE
1040 extract the dependence type from here.
1041
1042 dep_type : 4 => DEP_{TRUE|OUTPUT|ANTI|CONTROL}
1043
1044 3. Various flags:
1045
1046 HARD_DEP : 1 => Set if an instruction has a non-speculative
1047 dependence. This is an instruction property
1048 so this bit can only appear in the TODO_SPEC
1049 field of an instruction.
1050 DEP_POSTPONED : 1 => Like HARD_DEP, but the hard dependence may
1051 still be broken by adjusting the instruction.
1052 DEP_CANCELLED : 1 => Set if a dependency has been broken using
1053 some form of speculation.
1054 RESERVED : 1 => Reserved for use in the delay slot scheduler.
1055
1056 See also: check_dep_status () in sched-deps.c . */
1057
1058 /* The number of bits per weakness probability. There are 4 weakness types
1059 and we need 8 bits for other data in a DS_T. */
1060 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 8) / 4)
1061
1062 /* Mask of speculative weakness in dep_status. */
1063 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
1064
1065 /* This constant means that dependence is fake with 99.999...% probability.
1066 This is the maximum value, that can appear in dep_status.
1067 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
1068 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when
1069 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */
1070 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
1071
1072 /* This constant means that dependence is 99.999...% real and it is a really
1073 bad idea to overcome it (though this can be done, preserving program
1074 semantics). */
1075 #define MIN_DEP_WEAK 1
1076
1077 /* This constant represents 100% probability.
1078 E.g. it is used to represent weakness of dependence, that doesn't exist.
1079 This value never appears in a ds_t, it is only used for computing the
1080 weakness of a dependence. */
1081 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
1082
1083 /* Default weakness of speculative dependence. Used when we can't say
1084 neither bad nor good about the dependence. */
1085 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
1086
1087 /* Offset for speculative weaknesses in dep_status. */
1088 enum SPEC_TYPES_OFFSETS {
1089 BEGIN_DATA_BITS_OFFSET = 0,
1090 BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
1091 BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
1092 BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
1093 };
1094
1095 /* The following defines provide numerous constants used to distinguish
1096 between different types of speculative dependencies. They are also
1097 used as masks to clear/preserve the bits corresponding to the type
1098 of dependency weakness. */
1099
1100 /* Dependence can be overcome with generation of new data speculative
1101 instruction. */
1102 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
1103
1104 /* This dependence is to the instruction in the recovery block, that was
1105 formed to recover after data-speculation failure.
1106 Thus, this dependence can overcome with generating of the copy of
1107 this instruction in the recovery block. */
1108 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
1109
1110 /* Dependence can be overcome with generation of new control speculative
1111 instruction. */
1112 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
1113
1114 /* This dependence is to the instruction in the recovery block, that was
1115 formed to recover after control-speculation failure.
1116 Thus, this dependence can be overcome with generating of the copy of
1117 this instruction in the recovery block. */
1118 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
1119
1120 /* A few convenient combinations. */
1121 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
1122 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
1123 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
1124 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
1125 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
1126
1127 /* Constants, that are helpful in iterating through dep_status. */
1128 #define FIRST_SPEC_TYPE BEGIN_DATA
1129 #define LAST_SPEC_TYPE BE_IN_CONTROL
1130 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
1131
1132 /* Dependence on instruction can be of multiple types
1133 (e.g. true and output). This fields enhance REG_NOTE_KIND information
1134 of the dependence. */
1135 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
1136 #define DEP_OUTPUT (DEP_TRUE << 1)
1137 #define DEP_ANTI (DEP_OUTPUT << 1)
1138 #define DEP_CONTROL (DEP_ANTI << 1)
1139
1140 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI | DEP_CONTROL)
1141
1142 /* Instruction has non-speculative dependence. This bit represents the
1143 property of an instruction - not the one of a dependence.
1144 Therefore, it can appear only in the TODO_SPEC field of an instruction. */
1145 #define HARD_DEP (DEP_CONTROL << 1)
1146
1147 /* Like HARD_DEP, but dependencies can perhaps be broken by modifying
1148 the instructions. This is used for example to change:
1149
1150 rn++ => rm=[rn + 4]
1151 rm=[rn] rn++
1152
1153 For instructions that have this bit set, one of the dependencies of
1154 the instructions will have a non-NULL REPLACE field in its DEP_T.
1155 Just like HARD_DEP, this bit is only ever set in TODO_SPEC. */
1156 #define DEP_POSTPONED (HARD_DEP << 1)
1157
1158 /* Set if a dependency is cancelled via speculation. */
1159 #define DEP_CANCELLED (DEP_POSTPONED << 1)
1160
1161
1162 /* This represents the results of calling sched-deps.c functions,
1163 which modify dependencies. */
1164 enum DEPS_ADJUST_RESULT {
1165 /* No dependence needed (e.g. producer == consumer). */
1166 DEP_NODEP,
1167 /* Dependence is already present and wasn't modified. */
1168 DEP_PRESENT,
1169 /* Existing dependence was modified to include additional information. */
1170 DEP_CHANGED,
1171 /* New dependence has been created. */
1172 DEP_CREATED
1173 };
1174
1175 /* Represents the bits that can be set in the flags field of the
1176 sched_info structure. */
1177 enum SCHED_FLAGS {
1178 /* If set, generate links between instruction as DEPS_LIST.
1179 Otherwise, generate usual INSN_LIST links. */
1180 USE_DEPS_LIST = 1,
1181 /* Perform data or control (or both) speculation.
1182 Results in generation of data and control speculative dependencies.
1183 Requires USE_DEPS_LIST set. */
1184 DO_SPECULATION = USE_DEPS_LIST << 1,
1185 DO_BACKTRACKING = DO_SPECULATION << 1,
1186 DO_PREDICATION = DO_BACKTRACKING << 1,
1187 DONT_BREAK_DEPENDENCIES = DO_PREDICATION << 1,
1188 SCHED_RGN = DONT_BREAK_DEPENDENCIES << 1,
1189 SCHED_EBB = SCHED_RGN << 1,
1190 /* Scheduler can possibly create new basic blocks. Used for assertions. */
1191 NEW_BBS = SCHED_EBB << 1,
1192 SEL_SCHED = NEW_BBS << 1
1193 };
1194
1195 enum SPEC_SCHED_FLAGS {
1196 COUNT_SPEC_IN_CRITICAL_PATH = 1,
1197 SEL_SCHED_SPEC_DONT_CHECK_CONTROL = COUNT_SPEC_IN_CRITICAL_PATH << 1
1198 };
1199
1200 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
1201 != NOTE_INSN_BASIC_BLOCK))
1202
1203 extern FILE *sched_dump;
1204 extern int sched_verbose;
1205
1206 extern spec_info_t spec_info;
1207 extern bool haifa_recovery_bb_ever_added_p;
1208
1209 /* Exception Free Loads:
1210
1211 We define five classes of speculative loads: IFREE, IRISKY,
1212 PFREE, PRISKY, and MFREE.
1213
1214 IFREE loads are loads that are proved to be exception-free, just
1215 by examining the load insn. Examples for such loads are loads
1216 from TOC and loads of global data.
1217
1218 IRISKY loads are loads that are proved to be exception-risky,
1219 just by examining the load insn. Examples for such loads are
1220 volatile loads and loads from shared memory.
1221
1222 PFREE loads are loads for which we can prove, by examining other
1223 insns, that they are exception-free. Currently, this class consists
1224 of loads for which we are able to find a "similar load", either in
1225 the target block, or, if only one split-block exists, in that split
1226 block. Load2 is similar to load1 if both have same single base
1227 register. We identify only part of the similar loads, by finding
1228 an insn upon which both load1 and load2 have a DEF-USE dependence.
1229
1230 PRISKY loads are loads for which we can prove, by examining other
1231 insns, that they are exception-risky. Currently we have two proofs for
1232 such loads. The first proof detects loads that are probably guarded by a
1233 test on the memory address. This proof is based on the
1234 backward and forward data dependence information for the region.
1235 Let load-insn be the examined load.
1236 Load-insn is PRISKY iff ALL the following hold:
1237
1238 - insn1 is not in the same block as load-insn
1239 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1240 - test-insn is either a compare or a branch, not in the same block
1241 as load-insn
1242 - load-insn is reachable from test-insn
1243 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1244
1245 This proof might fail when the compare and the load are fed
1246 by an insn not in the region. To solve this, we will add to this
1247 group all loads that have no input DEF-USE dependence.
1248
1249 The second proof detects loads that are directly or indirectly
1250 fed by a speculative load. This proof is affected by the
1251 scheduling process. We will use the flag fed_by_spec_load.
1252 Initially, all insns have this flag reset. After a speculative
1253 motion of an insn, if insn is either a load, or marked as
1254 fed_by_spec_load, we will also mark as fed_by_spec_load every
1255 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
1256 load which is fed_by_spec_load is also PRISKY.
1257
1258 MFREE (maybe-free) loads are all the remaining loads. They may be
1259 exception-free, but we cannot prove it.
1260
1261 Now, all loads in IFREE and PFREE classes are considered
1262 exception-free, while all loads in IRISKY and PRISKY classes are
1263 considered exception-risky. As for loads in the MFREE class,
1264 these are considered either exception-free or exception-risky,
1265 depending on whether we are pessimistic or optimistic. We have
1266 to take the pessimistic approach to assure the safety of
1267 speculative scheduling, but we can take the optimistic approach
1268 by invoking the -fsched_spec_load_dangerous option. */
1269
1270 enum INSN_TRAP_CLASS
1271 {
1272 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1273 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1274 };
1275
1276 #define WORST_CLASS(class1, class2) \
1277 ((class1 > class2) ? class1 : class2)
1278
1279 #ifndef __GNUC__
1280 #define __inline
1281 #endif
1282
1283 #ifndef HAIFA_INLINE
1284 #define HAIFA_INLINE __inline
1285 #endif
1286
1287 struct sched_deps_info_def
1288 {
1289 /* Called when computing dependencies for a JUMP_INSN. This function
1290 should store the set of registers that must be considered as set by
1291 the jump in the regset. */
1292 void (*compute_jump_reg_dependencies) (rtx, regset);
1293
1294 /* Start analyzing insn. */
1295 void (*start_insn) (rtx_insn *);
1296
1297 /* Finish analyzing insn. */
1298 void (*finish_insn) (void);
1299
1300 /* Start analyzing insn LHS (Left Hand Side). */
1301 void (*start_lhs) (rtx);
1302
1303 /* Finish analyzing insn LHS. */
1304 void (*finish_lhs) (void);
1305
1306 /* Start analyzing insn RHS (Right Hand Side). */
1307 void (*start_rhs) (rtx);
1308
1309 /* Finish analyzing insn RHS. */
1310 void (*finish_rhs) (void);
1311
1312 /* Note set of the register. */
1313 void (*note_reg_set) (int);
1314
1315 /* Note clobber of the register. */
1316 void (*note_reg_clobber) (int);
1317
1318 /* Note use of the register. */
1319 void (*note_reg_use) (int);
1320
1321 /* Note memory dependence of type DS between MEM1 and MEM2 (which is
1322 in the INSN2). */
1323 void (*note_mem_dep) (rtx mem1, rtx mem2, rtx_insn *insn2, ds_t ds);
1324
1325 /* Note a dependence of type DS from the INSN. */
1326 void (*note_dep) (rtx_insn *, ds_t ds);
1327
1328 /* Nonzero if we should use cselib for better alias analysis. This
1329 must be 0 if the dependency information is used after sched_analyze
1330 has completed, e.g. if we're using it to initialize state for successor
1331 blocks in region scheduling. */
1332 unsigned int use_cselib : 1;
1333
1334 /* If set, generate links between instruction as DEPS_LIST.
1335 Otherwise, generate usual INSN_LIST links. */
1336 unsigned int use_deps_list : 1;
1337
1338 /* Generate data and control speculative dependencies.
1339 Requires USE_DEPS_LIST set. */
1340 unsigned int generate_spec_deps : 1;
1341 };
1342
1343 extern struct sched_deps_info_def *sched_deps_info;
1344
1345
1346 /* Functions in sched-deps.c. */
1347 extern rtx sched_get_reverse_condition_uncached (const rtx_insn *);
1348 extern bool sched_insns_conditions_mutex_p (const rtx_insn *,
1349 const rtx_insn *);
1350 extern bool sched_insn_is_legitimate_for_speculation_p (const rtx_insn *, ds_t);
1351 extern void add_dependence (rtx_insn *, rtx_insn *, enum reg_note);
1352 extern void sched_analyze (class deps_desc *, rtx_insn *, rtx_insn *);
1353 extern void init_deps (class deps_desc *, bool);
1354 extern void init_deps_reg_last (class deps_desc *);
1355 extern void free_deps (class deps_desc *);
1356 extern void init_deps_global (void);
1357 extern void finish_deps_global (void);
1358 extern void deps_analyze_insn (class deps_desc *, rtx_insn *);
1359 extern void remove_from_deps (class deps_desc *, rtx_insn *);
1360 extern void init_insn_reg_pressure_info (rtx_insn *);
1361 extern void get_implicit_reg_pending_clobbers (HARD_REG_SET *, rtx_insn *);
1362
1363 extern dw_t get_dep_weak (ds_t, ds_t);
1364 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
1365 extern dw_t estimate_dep_weak (rtx, rtx);
1366 extern ds_t ds_merge (ds_t, ds_t);
1367 extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx);
1368 extern ds_t ds_max_merge (ds_t, ds_t);
1369 extern dw_t ds_weak (ds_t);
1370 extern ds_t ds_get_speculation_types (ds_t);
1371 extern ds_t ds_get_max_dep_weak (ds_t);
1372
1373 extern void sched_deps_init (bool);
1374 extern void sched_deps_finish (void);
1375
1376 extern void haifa_note_reg_set (int);
1377 extern void haifa_note_reg_clobber (int);
1378 extern void haifa_note_reg_use (int);
1379
1380 extern void maybe_extend_reg_info_p (void);
1381
1382 extern void deps_start_bb (class deps_desc *, rtx_insn *);
1383 extern enum reg_note ds_to_dt (ds_t);
1384
1385 extern bool deps_pools_are_empty_p (void);
1386 extern void sched_free_deps (rtx_insn *, rtx_insn *, bool);
1387 extern void extend_dependency_caches (int, bool);
1388
1389 extern void debug_ds (ds_t);
1390
1391
1392 /* Functions in haifa-sched.c. */
1393 extern void initialize_live_range_shrinkage (void);
1394 extern void finish_live_range_shrinkage (void);
1395 extern void sched_init_region_reg_pressure_info (void);
1396 extern void free_global_sched_pressure_data (void);
1397 extern int haifa_classify_insn (const_rtx);
1398 extern void get_ebb_head_tail (basic_block, basic_block,
1399 rtx_insn **, rtx_insn **);
1400 extern int no_real_insns_p (const rtx_insn *, const rtx_insn *);
1401
1402 extern int insn_sched_cost (rtx_insn *);
1403 extern int dep_cost_1 (dep_t, dw_t);
1404 extern int dep_cost (dep_t);
1405 extern int set_priorities (rtx_insn *, rtx_insn *);
1406
1407 extern void sched_setup_bb_reg_pressure_info (basic_block, rtx_insn *);
1408 extern bool schedule_block (basic_block *, state_t);
1409
1410 extern int cycle_issued_insns;
1411 extern int issue_rate;
1412 extern int dfa_lookahead;
1413
1414 extern int autopref_multipass_dfa_lookahead_guard (rtx_insn *, int);
1415
1416 extern rtx_insn *ready_element (struct ready_list *, int);
1417 extern rtx_insn **ready_lastpos (struct ready_list *);
1418
1419 extern int try_ready (rtx_insn *);
1420 extern void sched_extend_ready_list (int);
1421 extern void sched_finish_ready_list (void);
1422 extern void sched_change_pattern (rtx, rtx);
1423 extern int sched_speculate_insn (rtx_insn *, ds_t, rtx *);
1424 extern void unlink_bb_notes (basic_block, basic_block);
1425 extern void add_block (basic_block, basic_block);
1426 extern rtx_note *bb_note (basic_block);
1427 extern void concat_note_lists (rtx_insn *, rtx_insn **);
1428 extern rtx_insn *sched_emit_insn (rtx);
1429 extern rtx_insn *get_ready_element (int);
1430 extern int number_in_ready (void);
1431
1432 /* Types and functions in sched-ebb.c. */
1433
1434 extern basic_block schedule_ebb (rtx_insn *, rtx_insn *, bool);
1435 extern void schedule_ebbs_init (void);
1436 extern void schedule_ebbs_finish (void);
1437
1438 /* Types and functions in sched-rgn.c. */
1439
1440 /* A region is the main entity for interblock scheduling: insns
1441 are allowed to move between blocks in the same region, along
1442 control flow graph edges, in the 'up' direction. */
1443 struct region
1444 {
1445 /* Number of extended basic blocks in region. */
1446 int rgn_nr_blocks;
1447 /* cblocks in the region (actually index in rgn_bb_table). */
1448 int rgn_blocks;
1449 /* Dependencies for this region are already computed. Basically, indicates,
1450 that this is a recovery block. */
1451 unsigned int dont_calc_deps : 1;
1452 /* This region has at least one non-trivial ebb. */
1453 unsigned int has_real_ebb : 1;
1454 };
1455
1456 extern int nr_regions;
1457 extern region *rgn_table;
1458 extern int *rgn_bb_table;
1459 extern int *block_to_bb;
1460 extern int *containing_rgn;
1461
1462 /* Often used short-hand in the scheduler. The rest of the compiler uses
1463 BLOCK_FOR_INSN(INSN) and an indirect reference to get the basic block
1464 number ("index"). For historical reasons, the scheduler does not. */
1465 #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
1466
1467 #define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
1468 #define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
1469 #define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
1470 #define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
1471 #define BLOCK_TO_BB(block) (block_to_bb[block])
1472 #define CONTAINING_RGN(block) (containing_rgn[block])
1473
1474 /* The mapping from ebb to block. */
1475 extern int *ebb_head;
1476 #define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
1477 #define EBB_FIRST_BB(ebb) BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (ebb))
1478 #define EBB_LAST_BB(ebb) \
1479 BASIC_BLOCK_FOR_FN (cfun, rgn_bb_table[ebb_head[ebb + 1] - 1])
1480 #define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
1481
1482 extern int current_nr_blocks;
1483 extern int current_blocks;
1484 extern int target_bb;
1485 extern bool sched_no_dce;
1486
1487 extern void set_modulo_params (int, int, int, int);
1488 extern void record_delay_slot_pair (rtx_insn *, rtx_insn *, int, int);
1489 extern rtx_insn *real_insn_for_shadow (rtx_insn *);
1490 extern void discard_delay_pairs_above (int);
1491 extern void free_delay_pairs (void);
1492 extern void add_delay_dependencies (rtx_insn *);
1493 extern bool sched_is_disabled_for_current_region_p (void);
1494 extern void sched_rgn_init (bool);
1495 extern void sched_rgn_finish (void);
1496 extern void rgn_setup_region (int);
1497 extern void sched_rgn_compute_dependencies (int);
1498 extern void sched_rgn_local_init (int);
1499 extern void sched_rgn_local_finish (void);
1500 extern void sched_rgn_local_free (void);
1501 extern void extend_regions (void);
1502 extern void rgn_make_new_region_out_of_new_block (basic_block);
1503
1504 extern void compute_priorities (void);
1505 extern void increase_insn_priority (rtx_insn *, int);
1506 extern void debug_rgn_dependencies (int);
1507 extern void debug_dependencies (rtx_insn *, rtx_insn *);
1508 extern void dump_rgn_dependencies_dot (FILE *);
1509 extern void dump_rgn_dependencies_dot (const char *);
1510
1511 extern void free_rgn_deps (void);
1512 extern int contributes_to_priority (rtx_insn *, rtx_insn *);
1513 extern void extend_rgns (int *, int *, sbitmap, int *);
1514 extern void deps_join (class deps_desc *, class deps_desc *);
1515
1516 extern void rgn_setup_common_sched_info (void);
1517 extern void rgn_setup_sched_infos (void);
1518
1519 extern void debug_regions (void);
1520 extern void debug_region (int);
1521 extern void dump_region_dot (FILE *, int);
1522 extern void dump_region_dot_file (const char *, int);
1523
1524 extern void haifa_sched_init (void);
1525 extern void haifa_sched_finish (void);
1526
1527 extern void find_modifiable_mems (rtx_insn *, rtx_insn *);
1528
1529 /* sched-deps.c interface to walk, add, search, update, resolve, delete
1530 and debug instruction dependencies. */
1531
1532 /* Constants defining dependences lists. */
1533
1534 /* No list. */
1535 #define SD_LIST_NONE (0)
1536
1537 /* hard_back_deps. */
1538 #define SD_LIST_HARD_BACK (1)
1539
1540 /* spec_back_deps. */
1541 #define SD_LIST_SPEC_BACK (2)
1542
1543 /* forw_deps. */
1544 #define SD_LIST_FORW (4)
1545
1546 /* resolved_back_deps. */
1547 #define SD_LIST_RES_BACK (8)
1548
1549 /* resolved_forw_deps. */
1550 #define SD_LIST_RES_FORW (16)
1551
1552 #define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
1553
1554 /* A type to hold above flags. */
1555 typedef int sd_list_types_def;
1556
1557 extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *);
1558
1559 /* Iterator to walk through, resolve and delete dependencies. */
1560 struct _sd_iterator
1561 {
1562 /* What lists to walk. Can be any combination of SD_LIST_* flags. */
1563 sd_list_types_def types;
1564
1565 /* Instruction dependencies lists of which will be walked. */
1566 rtx insn;
1567
1568 /* Pointer to the next field of the previous element. This is not
1569 simply a pointer to the next element to allow easy deletion from the
1570 list. When a dep is being removed from the list the iterator
1571 will automatically advance because the value in *linkp will start
1572 referring to the next element. */
1573 dep_link_t *linkp;
1574
1575 /* True if the current list is a resolved one. */
1576 bool resolved_p;
1577 };
1578
1579 typedef struct _sd_iterator sd_iterator_def;
1580
1581 /* ??? We can move some definitions that are used in below inline functions
1582 out of sched-int.h to sched-deps.c provided that the below functions will
1583 become global externals.
1584 These definitions include:
1585 * struct _deps_list: opaque pointer is needed at global scope.
1586 * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
1587 * struct _dep_node: opaque pointer is needed at scope of
1588 struct _deps_link. */
1589
1590 /* Return initialized iterator. */
1591 static inline sd_iterator_def
sd_iterator_start(rtx insn,sd_list_types_def types)1592 sd_iterator_start (rtx insn, sd_list_types_def types)
1593 {
1594 /* Some dep_link a pointer to which will return NULL. */
1595 static dep_link_t null_link = NULL;
1596
1597 sd_iterator_def i;
1598
1599 i.types = types;
1600 i.insn = insn;
1601 i.linkp = &null_link;
1602
1603 /* Avoid 'uninitialized warning'. */
1604 i.resolved_p = false;
1605
1606 return i;
1607 }
1608
1609 /* Return the current element. */
1610 static inline bool
sd_iterator_cond(sd_iterator_def * it_ptr,dep_t * dep_ptr)1611 sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr)
1612 {
1613 while (true)
1614 {
1615 dep_link_t link = *it_ptr->linkp;
1616
1617 if (link != NULL)
1618 {
1619 *dep_ptr = DEP_LINK_DEP (link);
1620 return true;
1621 }
1622 else
1623 {
1624 sd_list_types_def types = it_ptr->types;
1625
1626 if (types != SD_LIST_NONE)
1627 /* Switch to next list. */
1628 {
1629 deps_list_t list;
1630
1631 sd_next_list (it_ptr->insn,
1632 &it_ptr->types, &list, &it_ptr->resolved_p);
1633
1634 if (list)
1635 {
1636 it_ptr->linkp = &DEPS_LIST_FIRST (list);
1637 continue;
1638 }
1639 }
1640
1641 *dep_ptr = NULL;
1642 return false;
1643 }
1644 }
1645 }
1646
1647 /* Advance iterator. */
1648 static inline void
sd_iterator_next(sd_iterator_def * it_ptr)1649 sd_iterator_next (sd_iterator_def *it_ptr)
1650 {
1651 it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp);
1652 }
1653
1654 /* A cycle wrapper. */
1655 #define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP) \
1656 for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES)); \
1657 sd_iterator_cond (&(ITER), &(DEP)); \
1658 sd_iterator_next (&(ITER)))
1659
1660 #define IS_DISPATCH_ON 1
1661 #define IS_CMP 2
1662 #define DISPATCH_VIOLATION 3
1663 #define FITS_DISPATCH_WINDOW 4
1664 #define DISPATCH_INIT 5
1665 #define ADD_TO_DISPATCH_WINDOW 6
1666
1667 extern int sd_lists_size (const_rtx, sd_list_types_def);
1668 extern bool sd_lists_empty_p (const_rtx, sd_list_types_def);
1669 extern void sd_init_insn (rtx_insn *);
1670 extern void sd_finish_insn (rtx_insn *);
1671 extern dep_t sd_find_dep_between (rtx, rtx, bool);
1672 extern void sd_add_dep (dep_t, bool);
1673 extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
1674 extern void sd_resolve_dep (sd_iterator_def);
1675 extern void sd_unresolve_dep (sd_iterator_def);
1676 extern void sd_copy_back_deps (rtx_insn *, rtx_insn *, bool);
1677 extern void sd_delete_dep (sd_iterator_def);
1678 extern void sd_debug_lists (rtx, sd_list_types_def);
1679
1680 /* Macros and declarations for scheduling fusion. */
1681 #define FUSION_MAX_PRIORITY (INT_MAX)
1682 extern bool sched_fusion;
1683
1684 #endif /* INSN_SCHEDULING */
1685
1686 #endif /* GCC_SCHED_INT_H */
1687
1688