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