1 /* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2003, 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #ifndef GCC_SCHED_INT_H
24 #define GCC_SCHED_INT_H
27 #include "insn-attr.h"
28 /* For regset_head. */
29 #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. Lists of this type are now used instead of rtx
116 LOG_LINKS and alike lists. */
121 typedef struct _deps_list
*deps_list_t
;
123 #define DEPS_LIST_FIRST(L) ((L)->first)
125 /* Macro to walk through deps_list. */
126 #define FOR_EACH_DEP_LINK(LINK, LIST) \
127 for ((LINK) = DEPS_LIST_FIRST (LIST); \
129 (LINK) = DEP_LINK_NEXT (LINK))
131 /* Functions to work with deps_list. */
133 deps_list_t
create_deps_list (bool);
134 void free_deps_list (deps_list_t
);
135 void delete_deps_list (deps_list_t
);
136 bool deps_list_empty_p (deps_list_t
);
137 void debug_deps_list (deps_list_t
);
138 void add_back_dep_to_deps_list (deps_list_t
, dep_t
);
139 dep_link_t
find_link_by_pro_in_deps_list (deps_list_t
, rtx
);
140 dep_link_t
find_link_by_con_in_deps_list (deps_list_t
, rtx
);
141 void copy_deps_list_change_con (deps_list_t
, deps_list_t
, rtx
);
143 void move_dep_link (dep_link_t
, deps_list_t
);
145 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
146 additional dependents con0 and con2, and con1 is dependent on additional
167 This is represented using a "dep_node" for each dependence arc, which are
168 connected as follows (diagram is centered around Y which is fully shown;
169 other dep_nodes shown partially):
171 . +------------+ +--------------+ +------------+
172 . : dep_node X : | dep_node Y | : dep_node Z :
175 . : forw : | forw | : forw :
176 . : +--------+ : | +--------+ | : +--------+ :
177 forw_deps : |dep_link| : | |dep_link| | : |dep_link| :
178 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
179 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
180 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
181 . ^ ^ : | ^ | : | | ^ | | : | | :
182 . | | : | | | : | | | | | : | | :
183 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
184 . | : | | | : | | | | | : | | | :
185 . | : | +----+ | : | | +----+ | | : | +----+ | :
186 . | : | |prev| | : | | |prev| | | : | |prev| | :
187 . | : | |next| | : | | |next| | | : | |next| | :
188 . | : | +----+ | : | | +----+ | | : | +----+ | :
189 . | : | | :<-+ | | | |<-+ : | | :<-+
190 . | : | +----+ | : | | | +----+ | | | : | +----+ | : |
191 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
192 . | : | +----+ | : | | +----+ | | : | +----+ | :
193 . | : | | : | | | | : | | :
194 . | : +--------+ : | +--------+ | : +--------+ :
196 . | : SAME pro1 : | +--------+ | : SAME pro1 :
197 . | : DIFF con0 : | |dep | | : DIFF con2 :
200 .RTX<------------------------+--+-|pro1| | |
204 .RTX<------------------------+--+-|con1| | |
210 . | : : | | |stat| | | : :
211 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 :
212 . | : SAME con1 : | | | | : SAME con1 :
213 . | : : | +--------+ | : :
215 . | : back : | back | : back :
216 . v : +--------+ : | +--------+ | : +--------+ :
217 back_deps : |dep_link| : | |dep_link| | : |dep_link| :
218 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
219 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
220 +-----+ : | +----+ | : | | +----+ | | : | +----+ | :
221 . ^ : | ^ | : | | ^ | | : | | :
222 . | : | | | : | | | | | : | | :
223 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | :
224 . : | | | : | | | | | : | | | :
225 . : | +----+ | : | | +----+ | | : | +----+ | :
226 . : | |prev| | : | | |prev| | | : | |prev| | :
227 . : | |next| | : | | |next| | | : | |next| | :
228 . : | +----+ | : | | +----+ | | : | +----+ | :
229 . : | | :<-+ | | | |<-+ : | | :<-+
230 . : | +----+ | : | | | +----+ | | | : | +----+ | : |
231 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+
232 . : | +----+ | : | | +----+ | | : | +----+ | :
233 . : | | : | | | | : | | :
234 . : +--------+ : | +--------+ | : +--------+ :
236 . : dep_node A : | dep_node Y | : dep_node B :
237 . +------------+ +--------------+ +------------+
243 struct _dep_link back
;
249 struct _dep_link forw
;
251 typedef struct _dep_node
*dep_node_t
;
253 #define DEP_NODE_BACK(N) (&(N)->back)
254 #define DEP_NODE_DEP(N) (&(N)->dep)
255 #define DEP_NODE_FORW(N) (&(N)->forw)
257 /* Describe state of dependencies used during sched_analyze phase. */
260 /* The *_insns and *_mems are paired lists. Each pending memory operation
261 will have a pointer to the MEM rtx on one list and a pointer to the
262 containing insn on the other list in the same place in the list. */
264 /* We can't use add_dependence like the old code did, because a single insn
265 may have multiple memory accesses, and hence needs to be on the list
266 once for each memory access. Add_dependence won't let you add an insn
267 to a list more than once. */
269 /* An INSN_LIST containing all insns with pending read operations. */
270 rtx pending_read_insns
;
272 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */
273 rtx pending_read_mems
;
275 /* An INSN_LIST containing all insns with pending write operations. */
276 rtx pending_write_insns
;
278 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */
279 rtx pending_write_mems
;
281 /* We must prevent the above lists from ever growing too large since
282 the number of dependencies produced is at least O(N*N),
283 and execution time is at least O(4*N*N), as a function of the
284 length of these pending lists. */
286 /* Indicates the length of the pending_read list. */
287 int pending_read_list_length
;
289 /* Indicates the length of the pending_write list. */
290 int pending_write_list_length
;
292 /* Length of the pending memory flush list. Large functions with no
293 calls may build up extremely large lists. */
294 int pending_flush_length
;
296 /* The last insn upon which all memory references must depend.
297 This is an insn which flushed the pending lists, creating a dependency
298 between it and all previously pending memory references. This creates
299 a barrier (or a checkpoint) which no memory reference is allowed to cross.
301 This includes all non constant CALL_INSNs. When we do interprocedural
302 alias analysis, this restriction can be relaxed.
303 This may also be an INSN that writes memory if the pending lists grow
305 rtx last_pending_memory_flush
;
307 /* A list of the last function calls we have seen. We use a list to
308 represent last function calls from multiple predecessor blocks.
309 Used to prevent register lifetimes from expanding unnecessarily. */
310 rtx last_function_call
;
312 /* A list of insns which use a pseudo register that does not already
313 cross a call. We create dependencies between each of those insn
314 and the next call insn, to ensure that they won't cross a call after
315 scheduling is done. */
316 rtx sched_before_next_call
;
318 /* Used to keep post-call pseudo/hard reg movements together with
320 enum { not_post_call
, post_call
, post_call_initial
} in_post_call_group_p
;
322 /* Set to the tail insn of the outermost libcall block.
324 When nonzero, we will mark each insn processed by sched_analyze_insn
325 with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */
326 rtx libcall_block_tail_insn
;
328 /* The maximum register number for the following arrays. Before reload
329 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */
332 /* Element N is the next insn that sets (hard or pseudo) register
333 N within the current basic block; or zero, if there is no
334 such insn. Needed for new registers which may be introduced
335 by splitting insns. */
345 /* Element N is set for each register that has any nonzero element
346 in reg_last[N].{uses,sets,clobbers}. */
347 regset_head reg_last_in_use
;
349 /* Element N is set for each register that is conditionally set. */
350 regset_head reg_conditional_sets
;
353 /* This structure holds some state of the current scheduling pass, and
354 contains some function pointers that abstract out some of the non-generic
355 functionality from functions such as schedule_block or schedule_insn.
356 There is one global variable, current_sched_info, which points to the
357 sched_info structure currently in use. */
360 /* Add all insns that are initially ready to the ready list. Called once
361 before scheduling a set of insns. */
362 void (*init_ready_list
) (void);
363 /* Called after taking an insn from the ready list. Returns nonzero if
364 this insn can be scheduled, nonzero if we should silently discard it. */
365 int (*can_schedule_ready_p
) (rtx
);
366 /* Return nonzero if there are more insns that should be scheduled. */
367 int (*schedule_more_p
) (void);
368 /* Called after an insn has all its hard dependencies resolved.
369 Adjusts status of instruction (which is passed through second parameter)
370 to indicate if instruction should be moved to the ready list or the
371 queue, or if it should silently discard it (until next resolved
373 ds_t (*new_ready
) (rtx
, ds_t
);
374 /* Compare priority of two insns. Return a positive number if the second
375 insn is to be preferred for scheduling, and a negative one if the first
376 is to be preferred. Zero if they are equally good. */
377 int (*rank
) (rtx
, rtx
);
378 /* Return a string that contains the insn uid and optionally anything else
379 necessary to identify this insn in an output. It's valid to use a
380 static buffer for this. The ALIGNED parameter should cause the string
381 to be formatted so that multiple output lines will line up nicely. */
382 const char *(*print_insn
) (rtx
, int);
383 /* Return nonzero if an insn should be included in priority
385 int (*contributes_to_priority
) (rtx
, rtx
);
386 /* Called when computing dependencies for a JUMP_INSN. This function
387 should store the set of registers that must be considered as set by
388 the jump in the regset. */
389 void (*compute_jump_reg_dependencies
) (rtx
, regset
, regset
, regset
);
391 /* The boundaries of the set of insns to be scheduled. */
392 rtx prev_head
, next_tail
;
394 /* Filled in after the schedule is finished; the first and last scheduled
398 /* If nonzero, enables an additional sanity check in schedule_block. */
399 unsigned int queue_must_finish_empty
:1;
400 /* Nonzero if we should use cselib for better alias analysis. This
401 must be 0 if the dependency information is used after sched_analyze
402 has completed, e.g. if we're using it to initialize state for successor
403 blocks in region scheduling. */
404 unsigned int use_cselib
:1;
406 /* Maximum priority that has been assigned to an insn. */
407 int sched_max_insns_priority
;
409 /* Hooks to support speculative scheduling. */
411 /* Called to notify frontend that instruction is being added (second
412 parameter == 0) or removed (second parameter == 1). */
413 void (*add_remove_insn
) (rtx
, int);
415 /* Called to notify frontend that instruction is being scheduled.
416 The first parameter - instruction to scheduled, the second parameter -
417 last scheduled instruction. */
418 void (*begin_schedule_ready
) (rtx
, rtx
);
420 /* Called to notify frontend, that new basic block is being added.
421 The first parameter - new basic block.
422 The second parameter - block, after which new basic block is being added,
423 or EXIT_BLOCK_PTR, if recovery block is being added,
424 or NULL, if standalone block is being added. */
425 void (*add_block
) (basic_block
, basic_block
);
427 /* If the second parameter is not NULL, return nonnull value, if the
428 basic block should be advanced.
429 If the second parameter is NULL, return the next basic block in EBB.
430 The first parameter is the current basic block in EBB. */
431 basic_block (*advance_target_bb
) (basic_block
, rtx
);
433 /* Called after blocks were rearranged due to movement of jump instruction.
434 The first parameter - index of basic block, in which jump currently is.
435 The second parameter - index of basic block, in which jump used
437 The third parameter - index of basic block, that follows the second
439 void (*fix_recovery_cfg
) (int, int, int);
441 #ifdef ENABLE_CHECKING
442 /* If the second parameter is zero, return nonzero, if block is head of the
444 If the second parameter is nonzero, return nonzero, if block is leaf of
446 global_live_at_start should not change in region heads and
447 global_live_at_end should not change in region leafs due to scheduling. */
448 int (*region_head_or_leaf_p
) (basic_block
, int);
451 /* ??? FIXME: should use straight bitfields inside sched_info instead of
456 /* This structure holds description of the properties for speculative
460 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
461 BE_IN_{DATA_CONTROL}. */
464 /* A dump file for additional information on speculative scheduling. */
467 /* Minimal cumulative weakness of speculative instruction's
468 dependencies, so that insn will be scheduled. */
469 dw_t weakness_cutoff
;
471 /* Flags from the enum SPEC_SCHED_FLAGS. */
474 typedef struct spec_info_def
*spec_info_t
;
476 extern struct sched_info
*current_sched_info
;
478 /* Indexed by INSN_UID, the collection of all data associated with
479 a single instruction. */
481 struct haifa_insn_data
483 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
484 h_i_d because when h_i_d extends, addresses of the deps_list->first
485 change without updating deps_list->first->next->prev_nextp. Thus
486 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
487 list is allocated on the obstack. */
489 /* A list of backward dependencies. The insn is a consumer of all the
490 deps mentioned here. */
491 deps_list_t back_deps
;
493 /* A list of insns which depend on the instruction. Unlike 'back_deps',
494 it represents forward dependencies. */
495 deps_list_t forw_deps
;
497 /* A list of scheduled producers of the instruction. Links are being moved
498 from 'back_deps' to 'resolved_back_deps' while scheduling. */
499 deps_list_t resolved_back_deps
;
501 /* Logical uid gives the original ordering of the insns. */
504 /* A priority for each insn. */
507 /* The number of incoming edges in the forward dependency graph.
508 As scheduling proceeds, counts are decreased. An insn moves to
509 the ready queue when its counter reaches zero. */
512 /* Number of instructions referring to this insn. */
515 /* The minimum clock tick at which the insn becomes ready. This is
516 used to note timing constraints for the insns in the pending list. */
519 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
520 subsequent blocks in a region. */
523 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
528 /* This weight is an estimation of the insn's contribution to
529 register pressure. */
532 /* Some insns (e.g. call) are not allowed to move across blocks. */
533 unsigned int cant_move
: 1;
535 /* Set if there's DEF-USE dependence between some speculatively
536 moved load insn and this one. */
537 unsigned int fed_by_spec_load
: 1;
538 unsigned int is_load_insn
: 1;
540 /* Nonzero if priority has been computed already. */
541 unsigned int priority_known
: 1;
543 /* Nonzero if instruction has internal dependence
544 (e.g. add_dependence was invoked with (insn == elem)). */
545 unsigned int has_internal_dep
: 1;
547 /* What speculations are necessary to apply to schedule the instruction. */
549 /* What speculations were already applied. */
551 /* What speculations are checked by this instruction. */
554 /* Recovery block for speculation checks. */
555 basic_block recovery_block
;
557 /* Original pattern of the instruction. */
561 extern struct haifa_insn_data
*h_i_d
;
562 /* Used only if (current_sched_info->flags & USE_GLAT) != 0.
563 These regsets store global_live_at_{start, end} information
564 for each basic block. */
565 extern regset
*glat_start
, *glat_end
;
567 /* Accessor macros for h_i_d. There are more in haifa-sched.c and
569 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
570 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
571 #define INSN_RESOLVED_BACK_DEPS(INSN) \
572 (h_i_d[INSN_UID (INSN)].resolved_back_deps)
573 #define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
574 #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
575 #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
576 #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
577 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
578 #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
579 #define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep)
580 #define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec)
581 #define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec)
582 #define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
583 #define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
584 #define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
586 /* INSN is either a simple or a branchy speculation check. */
587 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
589 /* INSN is a speculation check that will simply reexecute the speculatively
590 scheduled instruction if the speculation fails. */
591 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
592 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
594 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
595 speculation fails. Insns in that block will reexecute the speculatively
596 scheduled code and then will return immediately after INSN thus preserving
597 semantics of the program. */
598 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
599 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
601 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
602 for speculative scheduling. Namely, it is 4 integers in the range
603 [0, MAX_DEP_WEAK] and 3 bits.
604 The integers correspond to the probability of the dependence to *not*
605 exist, it is the probability, that overcoming of this dependence will
606 not be followed by execution of the recovery code. Nevertheless,
607 whatever high the probability of success is, recovery code should still
608 be generated to preserve semantics of the program. To find a way to
609 get/set these integers, please refer to the {get, set}_dep_weak ()
610 functions in sched-deps.c .
611 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
612 output- and anti- dependence. It is not enough for speculative scheduling
613 to know just the major type of all the dependence between two instructions,
614 as only true dependence can be overcome.
615 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
616 for using to describe instruction's status. It is set whenever instruction
617 has at least one dependence, that cannot be overcame.
618 See also: check_dep_status () in sched-deps.c . */
620 /* We exclude sign bit. */
621 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
623 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
624 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
626 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
628 /* Mask of speculative weakness in dep_status. */
629 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
631 /* This constant means that dependence is fake with 99.999...% probability.
632 This is the maximum value, that can appear in dep_status.
633 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
634 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when
635 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */
636 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
638 /* This constant means that dependence is 99.999...% real and it is a really
639 bad idea to overcome it (though this can be done, preserving program
641 #define MIN_DEP_WEAK 1
643 /* This constant represents 100% probability.
644 E.g. it is used to represent weakness of dependence, that doesn't exist. */
645 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
647 /* Default weakness of speculative dependence. Used when we can't say
648 neither bad nor good about the dependence. */
649 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
651 /* Offset for speculative weaknesses in dep_status. */
652 enum SPEC_TYPES_OFFSETS
{
653 BEGIN_DATA_BITS_OFFSET
= 0,
654 BE_IN_DATA_BITS_OFFSET
= BEGIN_DATA_BITS_OFFSET
+ BITS_PER_DEP_WEAK
,
655 BEGIN_CONTROL_BITS_OFFSET
= BE_IN_DATA_BITS_OFFSET
+ BITS_PER_DEP_WEAK
,
656 BE_IN_CONTROL_BITS_OFFSET
= BEGIN_CONTROL_BITS_OFFSET
+ BITS_PER_DEP_WEAK
659 /* The following defines provide numerous constants used to distinguish between
660 different types of speculative dependencies. */
662 /* Dependence can be overcome with generation of new data speculative
664 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
666 /* This dependence is to the instruction in the recovery block, that was
667 formed to recover after data-speculation failure.
668 Thus, this dependence can overcome with generating of the copy of
669 this instruction in the recovery block. */
670 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
672 /* Dependence can be overcome with generation of new control speculative
674 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
676 /* This dependence is to the instruction in the recovery block, that was
677 formed to recover after control-speculation failure.
678 Thus, this dependence can be overcome with generating of the copy of
679 this instruction in the recovery block. */
680 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
682 /* A few convenient combinations. */
683 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
684 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
685 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
686 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
687 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
689 /* Constants, that are helpful in iterating through dep_status. */
690 #define FIRST_SPEC_TYPE BEGIN_DATA
691 #define LAST_SPEC_TYPE BE_IN_CONTROL
692 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
694 /* Dependence on instruction can be of multiple types
695 (e.g. true and output). This fields enhance REG_NOTE_KIND information
696 of the dependence. */
697 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
698 #define DEP_OUTPUT (DEP_TRUE << 1)
699 #define DEP_ANTI (DEP_OUTPUT << 1)
701 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
703 /* Instruction has non-speculative dependence. This bit represents the
704 property of an instruction - not the one of a dependence.
705 Therefore, it can appear only in TODO_SPEC field of an instruction. */
706 #define HARD_DEP (DEP_ANTI << 1)
708 /* This represents the results of calling sched-deps.c functions,
709 which modify dependencies. Possible choices are: a dependence
710 is already present and nothing has been changed; a dependence type
711 has been changed; brand new dependence has been created. */
712 enum DEPS_ADJUST_RESULT
{
718 /* Represents the bits that can be set in the flags field of the
719 sched_info structure. */
721 /* If set, generate links between instruction as DEPS_LIST.
722 Otherwise, generate usual INSN_LIST links. */
724 /* Perform data or control (or both) speculation.
725 Results in generation of data and control speculative dependencies.
726 Requires USE_DEPS_LIST set. */
727 DO_SPECULATION
= USE_DEPS_LIST
<< 1,
728 SCHED_RGN
= DO_SPECULATION
<< 1,
729 SCHED_EBB
= SCHED_RGN
<< 1,
730 /* Detach register live information from basic block headers.
731 This is necessary to invoke functions, that change CFG (e.g. split_edge).
732 Requires USE_GLAT. */
733 DETACH_LIFE_INFO
= SCHED_EBB
<< 1,
734 /* Save register live information from basic block headers to
735 glat_{start, end} arrays. */
736 USE_GLAT
= DETACH_LIFE_INFO
<< 1
739 enum SPEC_SCHED_FLAGS
{
740 COUNT_SPEC_IN_CRITICAL_PATH
= 1,
741 PREFER_NON_DATA_SPEC
= COUNT_SPEC_IN_CRITICAL_PATH
<< 1,
742 PREFER_NON_CONTROL_SPEC
= PREFER_NON_DATA_SPEC
<< 1
745 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE) \
746 != NOTE_INSN_BASIC_BLOCK))
748 extern FILE *sched_dump
;
749 extern int sched_verbose
;
751 /* Exception Free Loads:
753 We define five classes of speculative loads: IFREE, IRISKY,
754 PFREE, PRISKY, and MFREE.
756 IFREE loads are loads that are proved to be exception-free, just
757 by examining the load insn. Examples for such loads are loads
758 from TOC and loads of global data.
760 IRISKY loads are loads that are proved to be exception-risky,
761 just by examining the load insn. Examples for such loads are
762 volatile loads and loads from shared memory.
764 PFREE loads are loads for which we can prove, by examining other
765 insns, that they are exception-free. Currently, this class consists
766 of loads for which we are able to find a "similar load", either in
767 the target block, or, if only one split-block exists, in that split
768 block. Load2 is similar to load1 if both have same single base
769 register. We identify only part of the similar loads, by finding
770 an insn upon which both load1 and load2 have a DEF-USE dependence.
772 PRISKY loads are loads for which we can prove, by examining other
773 insns, that they are exception-risky. Currently we have two proofs for
774 such loads. The first proof detects loads that are probably guarded by a
775 test on the memory address. This proof is based on the
776 backward and forward data dependence information for the region.
777 Let load-insn be the examined load.
778 Load-insn is PRISKY iff ALL the following hold:
780 - insn1 is not in the same block as load-insn
781 - there is a DEF-USE dependence chain (insn1, ..., load-insn)
782 - test-insn is either a compare or a branch, not in the same block
784 - load-insn is reachable from test-insn
785 - there is a DEF-USE dependence chain (insn1, ..., test-insn)
787 This proof might fail when the compare and the load are fed
788 by an insn not in the region. To solve this, we will add to this
789 group all loads that have no input DEF-USE dependence.
791 The second proof detects loads that are directly or indirectly
792 fed by a speculative load. This proof is affected by the
793 scheduling process. We will use the flag fed_by_spec_load.
794 Initially, all insns have this flag reset. After a speculative
795 motion of an insn, if insn is either a load, or marked as
796 fed_by_spec_load, we will also mark as fed_by_spec_load every
797 insn1 for which a DEF-USE dependence (insn, insn1) exists. A
798 load which is fed_by_spec_load is also PRISKY.
800 MFREE (maybe-free) loads are all the remaining loads. They may be
801 exception-free, but we cannot prove it.
803 Now, all loads in IFREE and PFREE classes are considered
804 exception-free, while all loads in IRISKY and PRISKY classes are
805 considered exception-risky. As for loads in the MFREE class,
806 these are considered either exception-free or exception-risky,
807 depending on whether we are pessimistic or optimistic. We have
808 to take the pessimistic approach to assure the safety of
809 speculative scheduling, but we can take the optimistic approach
810 by invoking the -fsched_spec_load_dangerous option. */
814 TRAP_FREE
= 0, IFREE
= 1, PFREE_CANDIDATE
= 2,
815 PRISKY_CANDIDATE
= 3, IRISKY
= 4, TRAP_RISKY
= 5
818 #define WORST_CLASS(class1, class2) \
819 ((class1 > class2) ? class1 : class2)
826 #define HAIFA_INLINE __inline
829 /* Functions in sched-vis.c. */
830 extern void print_insn (char *, rtx
, int);
832 /* Functions in sched-deps.c. */
833 extern bool sched_insns_conditions_mutex_p (rtx
, rtx
);
834 extern void add_dependence (rtx
, rtx
, enum reg_note
);
835 extern void sched_analyze (struct deps
*, rtx
, rtx
);
836 extern void init_deps (struct deps
*);
837 extern void free_deps (struct deps
*);
838 extern void init_deps_global (void);
839 extern void finish_deps_global (void);
840 extern void add_forw_dep (dep_link_t
);
841 extern void compute_forward_dependences (rtx
, rtx
);
842 extern void init_dependency_caches (int);
843 extern void free_dependency_caches (void);
844 extern void extend_dependency_caches (int, bool);
845 extern enum DEPS_ADJUST_RESULT
add_or_update_back_dep (rtx
, rtx
,
846 enum reg_note
, ds_t
);
847 extern void add_or_update_back_forw_dep (rtx
, rtx
, enum reg_note
, ds_t
);
848 extern void add_back_forw_dep (rtx
, rtx
, enum reg_note
, ds_t
);
849 extern void delete_back_forw_dep (dep_link_t
);
850 extern dw_t
get_dep_weak (ds_t
, ds_t
);
851 extern ds_t
set_dep_weak (ds_t
, ds_t
, dw_t
);
852 extern ds_t
ds_merge (ds_t
, ds_t
);
854 /* Functions in haifa-sched.c. */
855 extern int haifa_classify_insn (rtx
);
856 extern void get_ebb_head_tail (basic_block
, basic_block
, rtx
*, rtx
*);
857 extern int no_real_insns_p (rtx
, rtx
);
859 extern void rm_other_notes (rtx
, rtx
);
861 extern int insn_cost (rtx
);
862 extern int dep_cost (dep_t
);
863 extern int set_priorities (rtx
, rtx
);
865 extern void schedule_block (basic_block
*, int);
866 extern void sched_init (void);
867 extern void sched_finish (void);
869 extern int try_ready (rtx
);
870 extern void * xrecalloc (void *, size_t, size_t, size_t);
871 extern void unlink_bb_notes (basic_block
, basic_block
);
872 extern void add_block (basic_block
, basic_block
);
873 extern void attach_life_info (void);
874 extern rtx
bb_note (basic_block
);
876 #ifdef ENABLE_CHECKING
877 extern void check_reg_live (bool);
880 #endif /* GCC_SCHED_INT_H */