1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
4 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #ifndef GCC_SCHED_INT_H
23 #define GCC_SCHED_INT_H
26 #include "insn-attr.h"
27 /* For regset_head. */
28 #include "basic-block.h"
33 /* Pointer to data describing the current DFA state. */
34 extern state_t curr_state;
36 /* Forward declaration. */
39 /* Type to represent status of a dependence. */
42 /* Type to represent weakness of speculative dependence. */
45 extern enum reg_note ds_to_dk (ds_t);
46 extern ds_t dk_to_ds (enum reg_note);
48 /* Information about the dependency. */
57 /* Dependency kind (aka dependency major type). This field is superseded
58 by STATUS below. Though, it is still in place because all the backends
62 /* Dependency status. This field holds all dependency types and additional
63 information for speculative dependencies. */
66 typedef struct _dep *dep_t;
68 #define DEP_PRO(D) ((D)->pro)
69 #define DEP_CON(D) ((D)->con)
70 #define DEP_KIND(D) ((D)->kind)
71 #define DEP_STATUS(D) ((D)->status)
73 /* Functions to work with dep. */
75 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
77 /* Definition of this struct resides below. */
80 /* A link in the dependency list. This is essentially an equivalent of a
81 single {INSN, DEPS}_LIST rtx. */
84 /* Dep node with all the data. */
85 struct _dep_node *node;
87 /* Next link in the list. For the last one it is NULL. */
88 struct _dep_link *next;
90 /* Pointer to the next field of the previous link in the list.
91 For the first link this points to the deps_list->first.
93 With help of this field it is easy to remove and insert links to the
95 struct _dep_link **prev_nextp;
97 typedef struct _dep_link *dep_link_t;
99 #define DEP_LINK_NODE(N) ((N)->node)
100 #define DEP_LINK_NEXT(N) ((N)->next)
101 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
103 /* Macros to work dep_link. For most usecases only part of the dependency
104 information is need. These macros conveniently provide that piece of
107 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
108 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
109 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
110 #define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N)))
111 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
113 void debug_dep_links (dep_link_t);
115 /* A list of dep_links. */
120 typedef struct _deps_list *deps_list_t;
122 #define DEPS_LIST_FIRST(L) ((L)->first)
124 /* Macro to walk through deps_list. */
125 #define FOR_EACH_DEP_LINK(LINK, LIST) \
126 for ((LINK) = DEPS_LIST_FIRST (LIST); \
128 (LINK) = DEP_LINK_NEXT (LINK))
130 /* Functions to work with deps_list. */
132 deps_list_t create_deps_list (bool);
133 void free_deps_list (deps_list_t);
134 void delete_deps_list (deps_list_t);
135 bool deps_list_empty_p (deps_list_t);
136 void debug_deps_list (deps_list_t);
137 void add_back_dep_to_deps_list (deps_list_t, dep_t);
138 dep_link_t find_link_by_pro_in_deps_list (deps_list_t, rtx);
139 dep_link_t find_link_by_con_in_deps_list (deps_list_t, rtx);
140 void copy_deps_list_change_con (deps_list_t, deps_list_t, rtx);
142 void move_dep_link (dep_link_t, deps_list_t);
144 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
145 additional dependents con0 and con2, and con1 is dependent on additional
166 This is represented using a "dep_node" for each dependence arc, which are
167 connected as follows (diagram is centered around Y which is fully shown;
168 other dep_nodes shown partially):
170 . +------------+ +--------------+ +------------+
171 . : dep_node X : | dep_node Y | : dep_node Z :
174 . : forw : | forw | : forw :
175 . : +--------+ : | +--------+ | : +--------+ :
176 forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
177 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
178 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
179 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
180 . ^ ^ : | ^ | : | | ^ | | : | | :
181 . | | : | | | : | | | | | : | | :
182 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
183 . | : | | | : | | | | | : | | | :
184 . | : | +----+ | : | | +----+ | | : | +----+ | :
185 . | : | |prev| | : | | |prev| | | : | |prev| | :
186 . | : | |next| | : | | |next| | | : | |next| | :
187 . | : | +----+ | : | | +----+ | | : | +----+ | :
188 . | : | | :<-+ | | | |<-+ : | | :<-+
189 . | : | +----+ | : | | | +----+ | | | : | +----+ | : |
190 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
191 . | : | +----+ | : | | +----+ | | : | +----+ | :
192 . | : | | : | | | | : | | :
193 . | : +--------+ : | +--------+ | : +--------+ :
195 . | : SAME pro1 : | +--------+ | : SAME pro1 :
196 . | : DIFF con0 : | |dep | | : DIFF con2 :
199 .RTX<------------------------+--+-|pro1| | |
203 .RTX<------------------------+--+-|con1| | |
209 . | : : | | |stat| | | : :
210 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 :
211 . | : SAME con1 : | | | | : SAME con1 :
212 . | : : | +--------+ | : :
214 . | : back : | back | : back :
215 . v : +--------+ : | +--------+ | : +--------+ :
216 back_deps : |dep_link| : | |dep_link| | : |dep_link| :
217 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
218 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
219 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
220 . ^ : | ^ | : | | ^ | | : | | :
221 . | : | | | : | | | | | : | | :
222 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
223 . : | | | : | | | | | : | | | :
224 . : | +----+ | : | | +----+ | | : | +----+ | :
225 . : | |prev| | : | | |prev| | | : | |prev| | :
226 . : | |next| | : | | |next| | | : | |next| | :
227 . : | +----+ | : | | +----+ | | : | +----+ | :
228 . : | | :<-+ | | | |<-+ : | | :<-+
229 . : | +----+ | : | | | +----+ | | | : | +----+ | : |
230 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
231 . : | +----+ | : | | +----+ | | : | +----+ | :
232 . : | | : | | | | : | | :
233 . : +--------+ : | +--------+ | : +--------+ :
235 . : dep_node A : | dep_node Y | : dep_node B :
236 . +------------+ +--------------+ +------------+
242 struct _dep_link back;
248 struct _dep_link forw;
250 typedef struct _dep_node *dep_node_t;
252 #define DEP_NODE_BACK(N) (&(N)->back)
253 #define DEP_NODE_DEP(N) (&(N)->dep)
254 #define DEP_NODE_FORW(N) (&(N)->forw)
256 /* Describe state of dependencies used during sched_analyze phase. */
259 /* The *_insns and *_mems are paired lists. Each pending memory operation
260 will have a pointer to the MEM rtx on one list and a pointer to the
261 containing insn on the other list in the same place in the list. */
263 /* We can't use add_dependence like the old code did, because a single insn
264 may have multiple memory accesses, and hence needs to be on the list
265 once for each memory access. Add_dependence won't let you add an insn
266 to a list more than once. */
268 /* An INSN_LIST containing all insns with pending read operations. */
269 rtx pending_read_insns;
271 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
272 rtx pending_read_mems;
274 /* An INSN_LIST containing all insns with pending write operations. */
275 rtx pending_write_insns;
277 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
278 rtx pending_write_mems;
280 /* We must prevent the above lists from ever growing too large since
281 the number of dependencies produced is at least O(N*N),
282 and execution time is at least O(4*N*N), as a function of the
283 length of these pending lists. */
285 /* Indicates the length of the pending_read list. */
286 int pending_read_list_length;
288 /* Indicates the length of the pending_write list. */
289 int pending_write_list_length;
291 /* Length of the pending memory flush list. Large functions with no
292 calls may build up extremely large lists. */
293 int pending_flush_length;
295 /* The last insn upon which all memory references must depend.
296 This is an insn which flushed the pending lists, creating a dependency
297 between it and all previously pending memory references. This creates
298 a barrier (or a checkpoint) which no memory reference is allowed to cross.
300 This includes all non constant CALL_INSNs. When we do interprocedural
301 alias analysis, this restriction can be relaxed.
302 This may also be an INSN that writes memory if the pending lists grow
304 rtx last_pending_memory_flush;
306 /* A list of the last function calls we have seen. We use a list to
307 represent last function calls from multiple predecessor blocks.
308 Used to prevent register lifetimes from expanding unnecessarily. */
309 rtx last_function_call;
311 /* A list of insns which use a pseudo register that does not already
312 cross a call. We create dependencies between each of those insn
313 and the next call insn, to ensure that they won't cross a call after
314 scheduling is done. */
315 rtx sched_before_next_call;
317 /* Used to keep post-call pseudo/hard reg movements together with
319 enum { not_post_call, post_call, post_call_initial } in_post_call_group_p;
321 /* Set to the tail insn of the outermost libcall block.
323 When nonzero, we will mark each insn processed by sched_analyze_insn
324 with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */
325 rtx libcall_block_tail_insn;
327 /* The maximum register number for the following arrays. Before reload
328 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
331 /* Element N is the next insn that sets (hard or pseudo) register
332 N within the current basic block; or zero, if there is no
333 such insn. Needed for new registers which may be introduced
334 by splitting insns. */
344 /* Element N is set for each register that has any nonzero element
345 in reg_last[N].{uses,sets,clobbers}. */
346 regset_head reg_last_in_use;
348 /* Element N is set for each register that is conditionally set. */
349 regset_head reg_conditional_sets;
352 /* This structure holds some state of the current scheduling pass, and
353 contains some function pointers that abstract out some of the non-generic
354 functionality from functions such as schedule_block or schedule_insn.
355 There is one global variable, current_sched_info, which points to the
356 sched_info structure currently in use. */
359 /* Add all insns that are initially ready to the ready list. Called once
360 before scheduling a set of insns. */
361 void (*init_ready_list) (void);
362 /* Called after taking an insn from the ready list. Returns nonzero if
363 this insn can be scheduled, nonzero if we should silently discard it. */
364 int (*can_schedule_ready_p) (rtx);
365 /* Return nonzero if there are more insns that should be scheduled. */
366 int (*schedule_more_p) (void);
367 /* Called after an insn has all its hard dependencies resolved.
368 Adjusts status of instruction (which is passed through second parameter)
369 to indicate if instruction should be moved to the ready list or the
370 queue, or if it should silently discard it (until next resolved
372 ds_t (*new_ready) (rtx, ds_t);
373 /* Compare priority of two insns. Return a positive number if the second
374 insn is to be preferred for scheduling, and a negative one if the first
375 is to be preferred. Zero if they are equally good. */
376 int (*rank) (rtx, rtx);
377 /* Return a string that contains the insn uid and optionally anything else
378 necessary to identify this insn in an output. It's valid to use a
379 static buffer for this. The ALIGNED parameter should cause the string
380 to be formatted so that multiple output lines will line up nicely. */
381 const char *(*print_insn) (rtx, int);
382 /* Return nonzero if an insn should be included in priority
384 int (*contributes_to_priority) (rtx, rtx);
385 /* Called when computing dependencies for a JUMP_INSN. This function
386 should store the set of registers that must be considered as set by
387 the jump in the regset. */
388 void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
390 /* The boundaries of the set of insns to be scheduled. */
391 rtx prev_head, next_tail;
393 /* Filled in after the schedule is finished; the first and last scheduled
397 /* If nonzero, enables an additional sanity check in schedule_block. */
398 unsigned int queue_must_finish_empty:1;
399 /* Nonzero if we should use cselib for better alias analysis. This
400 must be 0 if the dependency information is used after sched_analyze
401 has completed, e.g. if we're using it to initialize state for successor
402 blocks in region scheduling. */
403 unsigned int use_cselib:1;
405 /* Maximum priority that has been assigned to an insn. */
406 int sched_max_insns_priority;
408 /* Hooks to support speculative scheduling. */
410 /* Called to notify frontend that instruction is being added (second
411 parameter == 0) or removed (second parameter == 1). */
412 void (*add_remove_insn) (rtx, int);
414 /* Called to notify frontend that instruction is being scheduled.
415 The first parameter - instruction to scheduled, the second parameter -
416 last scheduled instruction. */
417 void (*begin_schedule_ready) (rtx, rtx);
419 /* Called to notify frontend, that new basic block is being added.
420 The first parameter - new basic block.
421 The second parameter - block, after which new basic block is being added,
422 or EXIT_BLOCK_PTR, if recovery block is being added,
423 or NULL, if standalone block is being added. */
424 void (*add_block) (basic_block, basic_block);
426 /* If the second parameter is not NULL, return nonnull value, if the
427 basic block should be advanced.
428 If the second parameter is NULL, return the next basic block in EBB.
429 The first parameter is the current basic block in EBB. */
430 basic_block (*advance_target_bb) (basic_block, rtx);
432 /* Called after blocks were rearranged due to movement of jump instruction.
433 The first parameter - index of basic block, in which jump currently is.
434 The second parameter - index of basic block, in which jump used
436 The third parameter - index of basic block, that follows the second
438 void (*fix_recovery_cfg) (int, int, int);
440 /* ??? FIXME: should use straight bitfields inside sched_info instead of
445 /* This structure holds description of the properties for speculative
449 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
450 BE_IN_{DATA_CONTROL}. */
453 /* A dump file for additional information on speculative scheduling. */
456 /* Minimal cumulative weakness of speculative instruction's
457 dependencies, so that insn will be scheduled. */
458 dw_t weakness_cutoff;
460 /* Flags from the enum SPEC_SCHED_FLAGS. */
463 typedef struct spec_info_def *spec_info_t;
465 extern struct sched_info *current_sched_info;
467 /* Indexed by INSN_UID, the collection of all data associated with
468 a single instruction. */
470 struct haifa_insn_data
472 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
473 h_i_d because when h_i_d extends, addresses of the deps_list->first
474 change without updating deps_list->first->next->prev_nextp. Thus
475 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
476 list is allocated on the obstack. */
478 /* A list of backward dependencies. The insn is a consumer of all the
479 deps mentioned here. */
480 deps_list_t back_deps;
482 /* A list of insns which depend on the instruction. Unlike 'back_deps',
483 it represents forward dependencies. */
484 deps_list_t forw_deps;
486 /* A list of scheduled producers of the instruction. Links are being moved
487 from 'back_deps' to 'resolved_back_deps' while scheduling. */
488 deps_list_t resolved_back_deps;
490 /* Logical uid gives the original ordering of the insns. */
493 /* A priority for each insn. */
496 /* The number of incoming edges in the forward dependency graph.
497 As scheduling proceeds, counts are decreased. An insn moves to
498 the ready queue when its counter reaches zero. */
501 /* Number of instructions referring to this insn. */
504 /* The minimum clock tick at which the insn becomes ready. This is
505 used to note timing constraints for the insns in the pending list. */
508 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
509 subsequent blocks in a region. */
512 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
517 /* This weight is an estimation of the insn's contribution to
518 register pressure. */
521 /* Some insns (e.g. call) are not allowed to move across blocks. */
522 unsigned int cant_move : 1;
524 /* Set if there's DEF-USE dependence between some speculatively
525 moved load insn and this one. */
526 unsigned int fed_by_spec_load : 1;
527 unsigned int is_load_insn : 1;
529 /* '> 0' if priority is valid,
530 '== 0' if priority was not yet computed,
531 '< 0' if priority in invalid and should be recomputed. */
532 signed char priority_status;
534 /* Nonzero if instruction has internal dependence
535 (e.g. add_dependence was invoked with (insn == elem)). */
536 unsigned int has_internal_dep : 1;
538 /* What speculations are necessary to apply to schedule the instruction. */
540 /* What speculations were already applied. */
542 /* What speculations are checked by this instruction. */
545 /* Recovery block for speculation checks. */
546 basic_block recovery_block;
548 /* Original pattern of the instruction. */
552 extern struct haifa_insn_data *h_i_d;
554 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
556 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
557 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
558 #define INSN_RESOLVED_BACK_DEPS(INSN) \
559 (h_i_d[INSN_UID (INSN)].resolved_back_deps)
560 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
561 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
562 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
563 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
564 #define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status)
565 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
566 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
567 #define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep)
568 #define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec)
569 #define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec)
570 #define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
571 #define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
572 #define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
574 /* INSN is either a simple or a branchy speculation check. */
575 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
577 /* INSN is a speculation check that will simply reexecute the speculatively
578 scheduled instruction if the speculation fails. */
579 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
580 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
582 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
583 speculation fails. Insns in that block will reexecute the speculatively
584 scheduled code and then will return immediately after INSN thus preserving
585 semantics of the program. */
586 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
587 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
589 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
590 for speculative scheduling. Namely, it is 4 integers in the range
591 [0, MAX_DEP_WEAK] and 3 bits.
592 The integers correspond to the probability of the dependence to *not*
593 exist, it is the probability, that overcoming of this dependence will
594 not be followed by execution of the recovery code. Nevertheless,
595 whatever high the probability of success is, recovery code should still
596 be generated to preserve semantics of the program. To find a way to
597 get/set these integers, please refer to the {get, set}_dep_weak ()
598 functions in sched-deps.c .
599 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
600 output- and anti- dependence. It is not enough for speculative scheduling
601 to know just the major type of all the dependence between two instructions,
602 as only true dependence can be overcome.
603 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
604 for using to describe instruction's status. It is set whenever instruction
605 has at least one dependence, that cannot be overcame.
606 See also: check_dep_status () in sched-deps.c . */
608 /* We exclude sign bit. */
609 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
611 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
612 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
614 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
616 /* Mask of speculative weakness in dep_status. */
617 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
619 /* This constant means that dependence is fake with 99.999...% probability.
620 This is the maximum value, that can appear in dep_status.
621 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
622 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when
623 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */
624 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
626 /* This constant means that dependence is 99.999...% real and it is a really
627 bad idea to overcome it (though this can be done, preserving program
629 #define MIN_DEP_WEAK 1
631 /* This constant represents 100% probability.
632 E.g. it is used to represent weakness of dependence, that doesn't exist. */
633 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
635 /* Default weakness of speculative dependence. Used when we can't say
636 neither bad nor good about the dependence. */
637 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
639 /* Offset for speculative weaknesses in dep_status. */
640 enum SPEC_TYPES_OFFSETS {
641 BEGIN_DATA_BITS_OFFSET = 0,
642 BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
643 BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
644 BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
647 /* The following defines provide numerous constants used to distinguish between
648 different types of speculative dependencies. */
650 /* Dependence can be overcome with generation of new data speculative
652 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
654 /* This dependence is to the instruction in the recovery block, that was
655 formed to recover after data-speculation failure.
656 Thus, this dependence can overcome with generating of the copy of
657 this instruction in the recovery block. */
658 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
660 /* Dependence can be overcome with generation of new control speculative
662 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
664 /* This dependence is to the instruction in the recovery block, that was
665 formed to recover after control-speculation failure.
666 Thus, this dependence can be overcome with generating of the copy of
667 this instruction in the recovery block. */
668 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
670 /* A few convenient combinations. */
671 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
672 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
673 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
674 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
675 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
677 /* Constants, that are helpful in iterating through dep_status. */
678 #define FIRST_SPEC_TYPE BEGIN_DATA
679 #define LAST_SPEC_TYPE BE_IN_CONTROL
680 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
682 /* Dependence on instruction can be of multiple types
683 (e.g. true and output). This fields enhance REG_NOTE_KIND information
684 of the dependence. */
685 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
686 #define DEP_OUTPUT (DEP_TRUE << 1)
687 #define DEP_ANTI (DEP_OUTPUT << 1)
689 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
691 /* Instruction has non-speculative dependence. This bit represents the
692 property of an instruction - not the one of a dependence.
693 Therefore, it can appear only in TODO_SPEC field of an instruction. */
694 #define HARD_DEP (DEP_ANTI << 1)
696 /* This represents the results of calling sched-deps.c functions,
697 which modify dependencies. Possible choices are: a dependence
698 is already present and nothing has been changed; a dependence type
699 has been changed; brand new dependence has been created. */
700 enum DEPS_ADJUST_RESULT {
706 /* Represents the bits that can be set in the flags field of the
707 sched_info structure. */
709 /* If set, generate links between instruction as DEPS_LIST.
710 Otherwise, generate usual INSN_LIST links. */
712 /* Perform data or control (or both) speculation.
713 Results in generation of data and control speculative dependencies.
714 Requires USE_DEPS_LIST set. */
715 DO_SPECULATION = USE_DEPS_LIST << 1,
716 SCHED_RGN = DO_SPECULATION << 1,
717 SCHED_EBB = SCHED_RGN << 1,
718 /* Scheduler can possible create new basic blocks. Used for assertions. */
719 NEW_BBS = SCHED_EBB << 1
722 enum SPEC_SCHED_FLAGS {
723 COUNT_SPEC_IN_CRITICAL_PATH = 1,
724 PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
725 PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
728 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
729 != NOTE_INSN_BASIC_BLOCK))
731 extern FILE *sched_dump;
732 extern int sched_verbose;
734 /* Exception Free Loads:
736 We define five classes of speculative loads: IFREE, IRISKY,
737 PFREE, PRISKY, and MFREE.
739 IFREE loads are loads that are proved to be exception-free, just
740 by examining the load insn. Examples for such loads are loads
741 from TOC and loads of global data.
743 IRISKY loads are loads that are proved to be exception-risky,
744 just by examining the load insn. Examples for such loads are
745 volatile loads and loads from shared memory.
747 PFREE loads are loads for which we can prove, by examining other
748 insns, that they are exception-free. Currently, this class consists
749 of loads for which we are able to find a "similar load", either in
750 the target block, or, if only one split-block exists, in that split
751 block. Load2 is similar to load1 if both have same single base
752 register. We identify only part of the similar loads, by finding
753 an insn upon which both load1 and load2 have a DEF-USE dependence.
755 PRISKY loads are loads for which we can prove, by examining other
756 insns, that they are exception-risky. Currently we have two proofs for
757 such loads. The first proof detects loads that are probably guarded by a
758 test on the memory address. This proof is based on the
759 backward and forward data dependence information for the region.
760 Let load-insn be the examined load.
761 Load-insn is PRISKY iff ALL the following hold:
763 - insn1 is not in the same block as load-insn
764 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
765 - test-insn is either a compare or a branch, not in the same block
767 - load-insn is reachable from test-insn
768 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
770 This proof might fail when the compare and the load are fed
771 by an insn not in the region. To solve this, we will add to this
772 group all loads that have no input DEF-USE dependence.
774 The second proof detects loads that are directly or indirectly
775 fed by a speculative load. This proof is affected by the
776 scheduling process. We will use the flag fed_by_spec_load.
777 Initially, all insns have this flag reset. After a speculative
778 motion of an insn, if insn is either a load, or marked as
779 fed_by_spec_load, we will also mark as fed_by_spec_load every
780 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
781 load which is fed_by_spec_load is also PRISKY.
783 MFREE (maybe-free) loads are all the remaining loads. They may be
784 exception-free, but we cannot prove it.
786 Now, all loads in IFREE and PFREE classes are considered
787 exception-free, while all loads in IRISKY and PRISKY classes are
788 considered exception-risky. As for loads in the MFREE class,
789 these are considered either exception-free or exception-risky,
790 depending on whether we are pessimistic or optimistic. We have
791 to take the pessimistic approach to assure the safety of
792 speculative scheduling, but we can take the optimistic approach
793 by invoking the -fsched_spec_load_dangerous option. */
797 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
798 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
801 #define WORST_CLASS(class1, class2) \
802 ((class1 > class2) ? class1 : class2)
809 #define HAIFA_INLINE __inline
812 /* Functions in sched-vis.c. */
813 extern void print_insn (char *, rtx, int);
815 /* Functions in sched-deps.c. */
816 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
817 extern void add_dependence (rtx, rtx, enum reg_note);
818 extern void sched_analyze (struct deps *, rtx, rtx);
819 extern void init_deps (struct deps *);
820 extern void free_deps (struct deps *);
821 extern void init_deps_global (void);
822 extern void finish_deps_global (void);
823 extern void add_forw_dep (dep_link_t);
824 extern void compute_forward_dependences (rtx, rtx);
825 extern void init_dependency_caches (int);
826 extern void free_dependency_caches (void);
827 extern void extend_dependency_caches (int, bool);
828 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
829 enum reg_note, ds_t);
830 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
831 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
832 extern void delete_back_forw_dep (dep_link_t);
833 extern dw_t get_dep_weak (ds_t, ds_t);
834 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
835 extern ds_t ds_merge (ds_t, ds_t);
837 /* Functions in haifa-sched.c. */
838 extern int haifa_classify_insn (rtx);
839 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
840 extern int no_real_insns_p (rtx, rtx);
842 extern void rm_other_notes (rtx, rtx);
844 extern int insn_cost (rtx);
845 extern int dep_cost (dep_t);
846 extern int set_priorities (rtx, rtx);
848 extern void schedule_block (basic_block *, int);
849 extern void sched_init (void);
850 extern void sched_finish (void);
852 extern int try_ready (rtx);
853 extern void * xrecalloc (void *, size_t, size_t, size_t);
854 extern void unlink_bb_notes (basic_block, basic_block);
855 extern void add_block (basic_block, basic_block);
856 extern rtx bb_note (basic_block);
858 /* Functions in sched-rgn.c. */
859 extern void debug_dependencies (rtx, rtx);
861 #endif /* GCC_SCHED_INT_H */