/* 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, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
+ 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#ifndef GCC_SCHED_INT_H
#define GCC_SCHED_INT_H
+#ifdef INSN_SCHEDULING
+
/* For state_t. */
#include "insn-attr.h"
/* For regset_head. */
#include "basic-block.h"
/* For reg_note. */
#include "rtl.h"
+#include "df.h"
/* Pointer to data describing the current DFA state. */
extern state_t curr_state;
/* Consumer. */
rtx con;
- /* Dependency kind (aka dependency major type). This field is superseded
- by STATUS below. Though, it is still in place because all the backends
- use it. */
- enum reg_note kind;
+ /* Dependency major type. This field is superseded by STATUS below.
+ Though, it is still in place because some targets use it. */
+ enum reg_note type;
/* Dependency status. This field holds all dependency types and additional
information for speculative dependencies. */
ds_t status;
};
-typedef struct _dep *dep_t;
+
+typedef struct _dep dep_def;
+typedef dep_def *dep_t;
#define DEP_PRO(D) ((D)->pro)
#define DEP_CON(D) ((D)->con)
-#define DEP_KIND(D) ((D)->kind)
+#define DEP_TYPE(D) ((D)->type)
#define DEP_STATUS(D) ((D)->status)
/* Functions to work with dep. */
+extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t);
extern void init_dep (dep_t, rtx, rtx, enum reg_note);
+extern void sd_debug_dep (dep_t);
+
/* Definition of this struct resides below. */
struct _dep_node;
+typedef struct _dep_node *dep_node_t;
/* A link in the dependency list. This is essentially an equivalent of a
single {INSN, DEPS}_LIST rtx. */
struct _dep_link
{
/* Dep node with all the data. */
- struct _dep_node *node;
+ dep_node_t node;
/* Next link in the list. For the last one it is NULL. */
struct _dep_link *next;
#define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
#define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
#define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
-#define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N)))
+#define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
#define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
-void debug_dep_links (dep_link_t);
-
-/* A list of dep_links. Lists of this type are now used instead of rtx
- LOG_LINKS and alike lists. */
+/* A list of dep_links. */
struct _deps_list
{
+ /* First element. */
dep_link_t first;
+
+ /* Total number of elements in the list. */
+ int n_links;
};
typedef struct _deps_list *deps_list_t;
#define DEPS_LIST_FIRST(L) ((L)->first)
-
-/* Macro to walk through deps_list. */
-#define FOR_EACH_DEP_LINK(LINK, LIST) \
- for ((LINK) = DEPS_LIST_FIRST (LIST); \
- (LINK) != NULL; \
- (LINK) = DEP_LINK_NEXT (LINK))
-
-/* Functions to work with deps_list. */
-
-deps_list_t create_deps_list (bool);
-void free_deps_list (deps_list_t);
-void delete_deps_list (deps_list_t);
-bool deps_list_empty_p (deps_list_t);
-void debug_deps_list (deps_list_t);
-void add_back_dep_to_deps_list (deps_list_t, dep_t);
-dep_link_t find_link_by_pro_in_deps_list (deps_list_t, rtx);
-dep_link_t find_link_by_con_in_deps_list (deps_list_t, rtx);
-void copy_deps_list_change_con (deps_list_t, deps_list_t, rtx);
-
-void move_dep_link (dep_link_t, deps_list_t);
+#define DEPS_LIST_N_LINKS(L) ((L)->n_links)
/* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
additional dependents con0 and con2, and con1 is dependent on additional
/* Forward link. */
struct _dep_link forw;
};
-typedef struct _dep_node *dep_node_t;
#define DEP_NODE_BACK(N) (&(N)->back)
#define DEP_NODE_DEP(N) (&(N)->dep)
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;
struct haifa_insn_data
{
- /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
- h_i_d because when h_i_d extends, addresses of the deps_list->first
- change without updating deps_list->first->next->prev_nextp. Thus
- BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
- list is allocated on the obstack. */
+ /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
+ because when h_i_d extends, addresses of the deps_list->first
+ change without updating deps_list->first->next->prev_nextp. */
- /* A list of backward dependencies. The insn is a consumer of all the
+ /* A list of hard backward dependencies. The insn is a consumer of all the
deps mentioned here. */
- deps_list_t back_deps;
+ deps_list_t hard_back_deps;
+
+ /* A list of speculative (weak) dependencies. The insn is a consumer of all
+ the deps mentioned here. */
+ deps_list_t spec_back_deps;
/* A list of insns which depend on the instruction. Unlike 'back_deps',
it represents forward dependencies. */
/* A list of scheduled producers of the instruction. Links are being moved
from 'back_deps' to 'resolved_back_deps' while scheduling. */
deps_list_t resolved_back_deps;
+
+ /* A list of scheduled consumers of the instruction. Links are being moved
+ from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
+ search in 'forw_deps'. */
+ deps_list_t resolved_forw_deps;
/* Logical uid gives the original ordering of the insns. */
int luid;
/* A priority for each insn. */
int priority;
- /* The number of incoming edges in the forward dependency graph.
- As scheduling proceeds, counts are decreased. An insn moves to
- the ready queue when its counter reaches zero. */
- int dep_count;
-
/* Number of instructions referring to this insn. */
int ref_count;
};
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_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
+
+#define INSN_HARD_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].hard_back_deps)
+#define INSN_SPEC_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].spec_back_deps)
#define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
#define INSN_RESOLVED_BACK_DEPS(INSN) \
(h_i_d[INSN_UID (INSN)].resolved_back_deps)
+#define INSN_RESOLVED_FORW_DEPS(INSN) \
+ (h_i_d[INSN_UID (INSN)].resolved_forw_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_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
#define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status)
#define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
#define HARD_DEP (DEP_ANTI << 1)
/* This represents the results of calling sched-deps.c functions,
- which modify dependencies. Possible choices are: a dependence
- is already present and nothing has been changed; a dependence type
- has been changed; brand new dependence has been created. */
+ which modify dependencies. */
enum DEPS_ADJUST_RESULT {
- DEP_PRESENT = 1,
- DEP_CHANGED = 2,
- DEP_CREATED = 3
+ /* No dependence needed (e.g. producer == consumer). */
+ DEP_NODEP,
+ /* Dependence is already present and wasn't modified. */
+ DEP_PRESENT,
+ /* Existing dependence was modified to include additional information. */
+ DEP_CHANGED,
+ /* New dependence has been created. */
+ DEP_CREATED
};
/* Represents the bits that can be set in the flags field of the
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
+ /* Scheduler can possible create new basic blocks. Used for assertions. */
+ NEW_BBS = SCHED_EBB << 1
};
enum SPEC_SCHED_FLAGS {
PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
};
-#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE) \
+#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
!= NOTE_INSN_BASIC_BLOCK))
extern FILE *sched_dump;
extern int sched_verbose;
+extern spec_info_t spec_info;
+extern bool haifa_recovery_bb_ever_added_p;
+
/* Exception Free Loads:
We define five classes of speculative loads: IFREE, IRISKY,
#define HAIFA_INLINE __inline
#endif
-/* Functions in sched-vis.c. */
-extern void print_insn (char *, rtx, int);
-
/* Functions in sched-deps.c. */
-extern bool sched_insns_conditions_mutex_p (rtx, rtx);
+extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
extern void add_dependence (rtx, rtx, enum reg_note);
extern void sched_analyze (struct deps *, rtx, rtx);
+extern bool deps_pools_are_empty_p (void);
+extern void sched_free_deps (rtx, rtx, bool);
extern void init_deps (struct deps *);
extern void free_deps (struct deps *);
extern void init_deps_global (void);
extern void finish_deps_global (void);
-extern void add_forw_dep (dep_link_t);
-extern void compute_forward_dependences (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 (dep_link_t);
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);
+extern void debug_ds (ds_t);
/* Functions in haifa-sched.c. */
-extern int haifa_classify_insn (rtx);
+extern int haifa_classify_insn (const_rtx);
extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
-extern int no_real_insns_p (rtx, rtx);
+extern int no_real_insns_p (const_rtx, const_rtx);
extern void rm_other_notes (rtx, rtx);
extern int try_ready (rtx);
extern void * xrecalloc (void *, size_t, size_t, size_t);
+extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_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
-
/* Functions in sched-rgn.c. */
+
extern void debug_dependencies (rtx, rtx);
+/* sched-deps.c interface to walk, add, search, update, resolve, delete
+ and debug instruction dependencies. */
+
+/* Constants defining dependences lists. */
+
+/* No list. */
+#define SD_LIST_NONE (0)
+
+/* hard_back_deps. */
+#define SD_LIST_HARD_BACK (1)
+
+/* spec_back_deps. */
+#define SD_LIST_SPEC_BACK (2)
+
+/* forw_deps. */
+#define SD_LIST_FORW (4)
+
+/* resolved_back_deps. */
+#define SD_LIST_RES_BACK (8)
+
+/* resolved_forw_deps. */
+#define SD_LIST_RES_FORW (16)
+
+#define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
+
+/* A type to hold above flags. */
+typedef int sd_list_types_def;
+
+extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *);
+
+/* Iterator to walk through, resolve and delete dependencies. */
+struct _sd_iterator
+{
+ /* What lists to walk. Can be any combination of SD_LIST_* flags. */
+ sd_list_types_def types;
+
+ /* Instruction dependencies lists of which will be walked. */
+ rtx insn;
+
+ /* Pointer to the next field of the previous element. This is not
+ simply a pointer to the next element to allow easy deletion from the
+ list. When a dep is being removed from the list the iterator
+ will automatically advance because the value in *linkp will start
+ referring to the next element. */
+ dep_link_t *linkp;
+
+ /* True if the current list is a resolved one. */
+ bool resolved_p;
+};
+
+typedef struct _sd_iterator sd_iterator_def;
+
+/* ??? We can move some definitions that are used in below inline functions
+ out of sched-int.h to sched-deps.c provided that the below functions will
+ become global externals.
+ These definitions include:
+ * struct _deps_list: opaque pointer is needed at global scope.
+ * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
+ * struct _dep_node: opaque pointer is needed at scope of
+ struct _deps_link. */
+
+/* Return initialized iterator. */
+static inline sd_iterator_def
+sd_iterator_start (rtx insn, sd_list_types_def types)
+{
+ /* Some dep_link a pointer to which will return NULL. */
+ static dep_link_t null_link = NULL;
+
+ sd_iterator_def i;
+
+ i.types = types;
+ i.insn = insn;
+ i.linkp = &null_link;
+
+ /* Avoid 'uninitialized warning'. */
+ i.resolved_p = false;
+
+ return i;
+}
+
+/* Return the current element. */
+static inline bool
+sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr)
+{
+ dep_link_t link = *it_ptr->linkp;
+
+ if (link != NULL)
+ {
+ *dep_ptr = DEP_LINK_DEP (link);
+ return true;
+ }
+ else
+ {
+ sd_list_types_def types = it_ptr->types;
+
+ if (types != SD_LIST_NONE)
+ /* Switch to next list. */
+ {
+ deps_list_t list;
+
+ sd_next_list (it_ptr->insn,
+ &it_ptr->types, &list, &it_ptr->resolved_p);
+
+ it_ptr->linkp = &DEPS_LIST_FIRST (list);
+
+ return sd_iterator_cond (it_ptr, dep_ptr);
+ }
+
+ *dep_ptr = NULL;
+ return false;
+ }
+}
+
+/* Advance iterator. */
+static inline void
+sd_iterator_next (sd_iterator_def *it_ptr)
+{
+ it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp);
+}
+
+/* A cycle wrapper. */
+#define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP) \
+ for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES)); \
+ sd_iterator_cond (&(ITER), &(DEP)); \
+ sd_iterator_next (&(ITER)))
+
+extern int sd_lists_size (const_rtx, sd_list_types_def);
+extern bool sd_lists_empty_p (const_rtx, sd_list_types_def);
+extern void sd_init_insn (rtx);
+extern void sd_finish_insn (rtx);
+extern dep_t sd_find_dep_between (rtx, rtx, bool);
+extern void sd_add_dep (dep_t, bool);
+extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
+extern void sd_resolve_dep (sd_iterator_def);
+extern void sd_copy_back_deps (rtx, rtx, bool);
+extern void sd_delete_dep (sd_iterator_def);
+extern void sd_debug_lists (rtx, sd_list_types_def);
+
+#endif /* INSN_SCHEDULING */
+
#endif /* GCC_SCHED_INT_H */
OSDN Git Service
