/* Instruction scheduling pass. This file contains definitions used
internally in the scheduler.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
This file is part of GCC.
/* Forward declaration. */
struct ready_list;
-/* Type to represent status of a dependence. A convinient short alias. */
-typedef HOST_WIDE_INT ds_t;
+/* Type to represent status of a dependence. */
+typedef int ds_t;
/* Type to represent weakness of speculative dependence. */
typedef int dw_t;
{
/* Add all insns that are initially ready to the ready list. Called once
before scheduling a set of insns. */
- void (*init_ready_list) (struct ready_list *);
+ void (*init_ready_list) (void);
/* Called after taking an insn from the ready list. Returns nonzero if
this insn can be scheduled, nonzero if we should silently discard it. */
int (*can_schedule_ready_p) (rtx);
/* Return nonzero if there are more insns that should be scheduled. */
int (*schedule_more_p) (void);
- /* Called after an insn has all its dependencies resolved. Return nonzero
- if it should be moved to the ready list or the queue, or zero if we
- should silently discard it. */
- int (*new_ready) (rtx);
+ /* Called after an insn has all its hard dependencies resolved.
+ Adjusts status of instruction (which is passed through second parameter)
+ to indicate if instruction should be moved to the ready list or the
+ queue, or if it should silently discard it (until next resolved
+ dependence). */
+ ds_t (*new_ready) (rtx, ds_t);
/* Compare priority of two insns. Return a positive number if the second
insn is to be preferred for scheduling, and a negative one if the first
is to be preferred. Zero if they are equally good. */
/* Maximum priority that has been assigned to an insn. */
int sched_max_insns_priority;
+ /* Hooks to support speculative scheduling. */
+
+ /* Called to notify frontend that instruction is being added (second
+ parameter == 0) or removed (second parameter == 1). */
+ void (*add_remove_insn) (rtx, int);
+
+ /* Called to notify frontend that instruction is being scheduled.
+ The first parameter - instruction to scheduled, the second parameter -
+ last scheduled instruction. */
+ void (*begin_schedule_ready) (rtx, rtx);
+
+ /* Called to notify frontend, that new basic block is being added.
+ The first parameter - new basic block.
+ The second parameter - block, after which new basic block is being added,
+ or EXIT_BLOCK_PTR, if recovery block is being added,
+ or NULL, if standalone block is being added. */
+ void (*add_block) (basic_block, basic_block);
+
+ /* If the second parameter is not NULL, return nonnull value, if the
+ basic block should be advanced.
+ If the second parameter is NULL, return the next basic block in EBB.
+ The first parameter is the current basic block in EBB. */
+ basic_block (*advance_target_bb) (basic_block, rtx);
+
+ /* Called after blocks were rearranged due to movement of jump instruction.
+ The first parameter - index of basic block, in which jump currently is.
+ The second parameter - index of basic block, in which jump used
+ to be.
+ The third parameter - index of basic block, that follows the second
+ parameter. */
+ void (*fix_recovery_cfg) (int, int, int);
+
+#ifdef ENABLE_CHECKING
+ /* If the second parameter is zero, return nonzero, if block is head of the
+ region.
+ If the second parameter is nonzero, return nonzero, if block is leaf of
+ the region.
+ global_live_at_start should not change in region heads and
+ global_live_at_end should not change in region leafs due to scheduling. */
+ int (*region_head_or_leaf_p) (basic_block, int);
+#endif
+
/* ??? FIXME: should use straight bitfields inside sched_info instead of
this flag field. */
unsigned int flags;
};
+/* This structure holds description of the properties for speculative
+ scheduling. */
+struct spec_info_def
+{
+ /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
+ BE_IN_{DATA_CONTROL}. */
+ int mask;
+
+ /* A dump file for additional information on speculative scheduling. */
+ FILE *dump;
+
+ /* Minimal cumulative weakness of speculative instruction's
+ dependencies, so that insn will be scheduled. */
+ dw_t weakness_cutoff;
+
+ /* Flags from the enum SPEC_SCHED_FLAGS. */
+ int flags;
+};
+typedef struct spec_info_def *spec_info_t;
+
extern struct sched_info *current_sched_info;
/* Indexed by INSN_UID, the collection of all data associated with
it represents forward dependencies. */
rtx depend;
+ /* A list of scheduled producers of the instruction. Links are being moved
+ from LOG_LINKS to RESOLVED_DEPS during scheduling. */
+ rtx resolved_deps;
+
/* The line number note in effect for each insn. For line number
notes, this indicates whether the note may be reused. */
rtx line_note;
used to note timing constraints for the insns in the pending list. */
int tick;
+ /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
+ subsequent blocks in a region. */
+ int inter_tick;
+
+ /* See comment on QUEUE_INDEX macro in haifa-sched.c. */
+ int queue_index;
+
short cost;
/* This weight is an estimation of the insn's contribution to
/* Nonzero if instruction has internal dependence
(e.g. add_dependence was invoked with (insn == elem)). */
unsigned int has_internal_dep : 1;
+
+ /* What speculations are necessary to apply to schedule the instruction. */
+ ds_t todo_spec;
+ /* What speculations were already applied. */
+ ds_t done_spec;
+ /* What speculations are checked by this instruction. */
+ ds_t check_spec;
+
+ /* Recovery block for speculation checks. */
+ basic_block recovery_block;
+
+ /* Original pattern of the instruction. */
+ rtx orig_pat;
};
extern struct haifa_insn_data *h_i_d;
+/* Used only if (current_sched_info->flags & USE_GLAT) != 0.
+ These regsets store global_live_at_{start, end} information
+ for each basic block. */
+extern regset *glat_start, *glat_end;
/* Accessor macros for h_i_d. There are more in haifa-sched.c and
sched-rgn.c. */
#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend)
+#define RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps)
#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid)
#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move)
#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep)
+#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec)
+#define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec)
+#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
+#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
+#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
-/* DEP_STATUS of the link incapsulates information, that is needed for
+/* DEP_STATUS of the link encapsulates information, that is needed for
speculative scheduling. Namely, it is 4 integers in the range
[0, MAX_DEP_WEAK] and 3 bits.
The integers correspond to the probability of the dependence to *not*
to know just the major type of all the dependence between two instructions,
as only true dependence can be overcome.
There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
- for using to describe instruction's status. It is set whenever instuction
+ for using to describe instruction's status. It is set whenever instruction
has at least one dependence, that cannot be overcome.
See also: check_dep_status () in sched-deps.c . */
-#define DEP_STATUS(LINK) XWINT (LINK, 2)
+#define DEP_STATUS(LINK) XINT (LINK, 2)
/* We exclude sign bit. */
-#define BITS_PER_DEP_STATUS (HOST_BITS_PER_WIDE_INT - 1)
+#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
/* First '4' stands for 3 dep type bits and HARD_DEP bit.
Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
/* The following defines provide numerous constants used to distinguish between
different types of speculative dependencies. */
-/* Dependence can be overcomed with generation of new data speculative
+/* Dependence can be overcome with generation of new data speculative
instruction. */
#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
/* This dependence is to the instruction in the recovery block, that was
formed to recover after data-speculation failure.
- Thus, this dependence can overcomed with generating of the copy of
+ Thus, this dependence can overcome with generating of the copy of
this instruction in the recovery block. */
#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
-/* Dependence can be overcomed with generation of new control speculative
+/* Dependence can be overcome with generation of new control speculative
instruction. */
#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
/* This dependence is to the instruction in the recovery block, that was
formed to recover after control-speculation failure.
- Thus, this dependence can overcomed with generating of the copy of
+ Thus, this dependence can be overcome with generating of the copy of
this instruction in the recovery block. */
#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
-/* Few convinient combinations. */
+/* A few convenient combinations. */
#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
/* Perform data or control (or both) speculation.
Results in generation of data and control speculative dependencies.
Requires USE_DEPS_LIST set. */
- DO_SPECULATION = USE_DEPS_LIST << 1
+ DO_SPECULATION = USE_DEPS_LIST << 1,
+ SCHED_RGN = DO_SPECULATION << 1,
+ SCHED_EBB = SCHED_RGN << 1,
+ /* Detach register live information from basic block headers.
+ This is necessary to invoke functions, that change CFG (e.g. split_edge).
+ Requires USE_GLAT. */
+ DETACH_LIFE_INFO = SCHED_EBB << 1,
+ /* Save register live information from basic block headers to
+ glat_{start, end} arrays. */
+ USE_GLAT = DETACH_LIFE_INFO << 1
+};
+
+enum SPEC_SCHED_FLAGS {
+ COUNT_SPEC_IN_CRITICAL_PATH = 1,
+ PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
+ PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
};
+#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE) \
+ != NOTE_INSN_BASIC_BLOCK))
+
extern FILE *sched_dump;
extern int sched_verbose;
extern rtx find_insn_list (rtx, rtx);
extern void init_dependency_caches (int);
extern void free_dependency_caches (void);
+extern void extend_dependency_caches (int, bool);
extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
enum reg_note, ds_t);
extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
extern void delete_back_forw_dep (rtx, rtx);
+extern dw_t get_dep_weak (ds_t, ds_t);
extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
+extern ds_t ds_merge (ds_t, ds_t);
/* Functions in haifa-sched.c. */
extern int haifa_classify_insn (rtx);
-extern void get_block_head_tail (int, rtx *, rtx *);
+extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
extern int no_real_insns_p (rtx, rtx);
extern void rm_line_notes (rtx, rtx);
extern int insn_cost (rtx, rtx, rtx);
extern int set_priorities (rtx, rtx);
-extern void schedule_block (int, int);
+extern void schedule_block (basic_block *, int);
extern void sched_init (void);
extern void sched_finish (void);
-extern void ready_add (struct ready_list *, rtx);
+extern int try_ready (rtx);
+extern void * xrecalloc (void *, size_t, size_t, size_t);
+extern void unlink_bb_notes (basic_block, basic_block);
+extern void add_block (basic_block, basic_block);
+extern void attach_life_info (void);
+extern rtx bb_note (basic_block);
+
+#ifdef ENABLE_CHECKING
+extern void check_reg_live (bool);
+#endif
#endif /* GCC_SCHED_INT_H */