struct dataflow;
struct df;
struct df_problem;
+struct df_link;
/* Data flow problems. All problems must have a unique here. */
/* Scanning is not really a dataflow problem, but it is useful to have
#define DF_RI 7 /* Register Info. */
#define DF_LAST_PROBLEM_PLUS1 (DF_RI + 1)
-/* Flags that control the building of chains. */
-#define DF_DU_CHAIN 1 /* Build DU chains. */
-#define DF_UD_CHAIN 2 /* Build UD chains. */
-
/* Dataflow direction. */
enum df_flow_dir
DF_BACKWARD
};
+
+/* The first of these is a set of a register. The remaining three are
+ all uses of a register (the mem_load and mem_store relate to how
+ the register as an addressing operand). */
+enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
+ DF_REF_REG_MEM_STORE};
+
+#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
+
+enum df_ref_flags
+ {
+ /* Read-modify-write refs generate both a use and a def and
+ these are marked with this flag to show that they are not
+ independent. */
+ DF_REF_READ_WRITE = 1,
+
+ /* This flag is set, if we stripped the subreg from the reference.
+ In this case we must make conservative guesses, at what the
+ outer mode was. */
+ DF_REF_STRIPPED = 2,
+
+ /* If this flag is set, this is not a real definition/use, but an
+ artificial one created to model always live registers, eh uses, etc. */
+ DF_REF_ARTIFICIAL = 4,
+
+
+ /* If this flag is set for an artificial use or def, that ref
+ logically happens at the top of the block. If it is not set
+ for an artificial use or def, that ref logically happens at the
+ bottom of the block. This is never set for regular refs. */
+ DF_REF_AT_TOP = 8,
+
+ /* This flag is set if the use is inside a REG_EQUAL note. */
+ DF_REF_IN_NOTE = 16,
+
+ /* This flag is set if this ref, generally a def, may clobber the
+ referenced register. This is generally only set for hard
+ registers that cross a call site. With better information
+ about calls, some of these could be changed in the future to
+ DF_REF_MUST_CLOBBER. */
+ DF_REF_MAY_CLOBBER = 32,
+
+ /* This flag is set if this ref, generally a def, is a real
+ clobber. This is not currently set for registers live across a
+ call because that clobbering may or may not happen.
+
+ Most of the uses of this are with sets that have a
+ GET_CODE(..)==CLOBBER. Note that this is set even if the
+ clobber is to a subreg. So in order to tell if the clobber
+ wipes out the entire register, it is necessary to also check
+ the DF_REF_PARTIAL flag. */
+ DF_REF_MUST_CLOBBER = 64,
+
+ /* This bit is true if this ref is part of a multiword hardreg. */
+ DF_REF_MW_HARDREG = 128,
+
+ /* This flag is set if this ref is a partial use or def of the
+ associated register. */
+ DF_REF_PARTIAL = 256
+ };
+
+
/* Function prototypes added to df_problem instance. */
/* Allocate the problem specific data. */
-typedef void (*df_alloc_function) (struct dataflow *, bitmap);
+typedef void (*df_alloc_function) (struct dataflow *, bitmap, bitmap);
/* This function is called if the problem has global data that needs
to be cleared when ever the set of blocks changes. The bitmap
/* Function to dump results to FILE. */
typedef void (*df_dump_problem_function) (struct dataflow *, FILE *);
+/* Function to add problem a dataflow problem that must be solved
+ before this problem can be solved. */
+typedef struct dataflow * (*df_dependent_problem_function) (struct df *, int);
+
/* The static description of a dataflow problem to solve. See above
typedefs for doc for the function fields. */
df_finalizer_function finalize_fun;
df_free_function free_fun;
df_dump_problem_function dump_fun;
+ df_dependent_problem_function dependent_problem_fun;
- /* A dataflow problem that must be solved before this problem can be
- solved. */
- struct df_problem *dependent_problem;
+ /* Flags can be changed after analysis starts. */
+ int changeable_flags;
};
/* The pool to allocate the block_info from. */
alloc_pool block_pool;
+ /* Problem specific control information. */
+
+ /* Scanning flags. */
+#define DF_HARD_REGS 1 /* Mark hard registers. */
+#define DF_EQUIV_NOTES 2 /* Mark uses present in EQUIV/EQUAL notes. */
+#define DF_SUBREGS 4 /* Return subregs rather than the inner reg. */
+ /* Flags that control the building of chains. */
+#define DF_DU_CHAIN 1 /* Build DU chains. */
+#define DF_UD_CHAIN 2 /* Build UD chains. */
+ /* Flag to control the building of register info. */
+#define DF_RI_LIFE 1 /* Build register info. */
+
+ int flags;
+
/* Other problem specific data that is not on a per basic block
basis. The structure is generally defined privately for the
problem. The exception being the scanning problem where it is
void *problem_data;
};
+
+/* The set of multiword hardregs used as operands to this
+ instruction. These are factored into individual uses and defs but
+ the aggregate is still needed to service the REG_DEAD and
+ REG_UNUSED notes. */
+struct df_mw_hardreg
+{
+ rtx mw_reg; /* The multiword hardreg. */
+ enum df_ref_type type; /* Used to see if the ref is read or write. */
+ enum df_ref_flags flags; /* Various flags. */
+ struct df_link *regs; /* The individual regs that make up
+ this hardreg. */
+ struct df_mw_hardreg *next; /* The next mw_hardreg in this insn. */
+};
+
+
/* One of these structures is allocated for every insn. */
struct df_insn_info
{
struct df_ref *defs; /* Head of insn-def chain. */
struct df_ref *uses; /* Head of insn-use chain. */
+ struct df_mw_hardreg *mw_hardregs;
/* ???? The following luid field should be considered private so that
we can change it on the fly to accommodate new insns? */
int luid; /* Logical UID. */
bool contains_asm; /* Contains an asm instruction. */
};
+
/* Two of these structures are allocated for every pseudo reg, one for
the uses and one for the defs. */
struct df_reg_info
unsigned int n_refs; /* Number of refs or defs for this pseudo. */
};
-
-enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
- DF_REF_REG_MEM_STORE};
-
-#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
-
-enum df_ref_flags
- {
- /* Read-modify-write refs generate both a use and a def and
- these are marked with this flag to show that they are not
- independent. */
- DF_REF_READ_WRITE = 1,
-
- /* This flag is set, if we stripped the subreg from the reference.
- In this case we must make conservative guesses, at what the
- outer mode was. */
- DF_REF_STRIPPED = 2,
-
- /* If this flag is set, this is not a real definition/use, but an
- artificial one created to model always live registers, eh uses, etc. */
- DF_REF_ARTIFICIAL = 4,
-
-
- /* If this flag is set for an artificial use or def, that ref
- logically happens at the top of the block. If it is not set
- for an artificial use or def, that ref logically happens at the
- bottom of the block. This is never set for regular refs. */
- DF_REF_AT_TOP = 8,
-
- /* This flag is set if the use is inside a REG_EQUAL note. */
- DF_REF_IN_NOTE = 16,
-
- /* This flag is set if this ref is really a clobber, and not a def. */
- DF_REF_CLOBBER = 32,
-
- /* True if ref is dead (i.e. the next ref is a def or clobber or
- the end of the function.) This is only valid the RI problem
- has been set in this df instance. */
- DF_REF_DIES_AFTER_THIS_USE = 64
- };
-
-
/* Define a register reference structure. One of these is allocated
for every register reference (use or def). Note some register
references (e.g., post_inc, subreg) generate both a def and a use. */
void *data; /* The data assigned to it by user. */
};
-/* There are two kinds of links: */
-
-/* This is used for def-use or use-def chains. */
+/* These links are used for two purposes:
+ 1) def-use or use-def chains.
+ 2) Multiword hard registers that underly a single hardware register. */
struct df_link
{
struct df_ref *ref;
unsigned int bitmap_size; /* Number of refs seen. */
/* True if refs table is organized so that every reference for a
- pseudo is contigious. */
+ pseudo is contiguous. */
bool refs_organized;
/* True if the next refs should be added immediately or false to
defer to later to reorganize the table. */
struct df
{
-#define DF_HARD_REGS 1 /* Mark hard registers. */
-#define DF_EQUIV_NOTES 2 /* Mark uses present in EQUIV/EQUAL notes. */
-#define DF_SUBREGS 4 /* Return subregs rather than the inner reg. */
-
- int flags; /* Indicates what's recorded. */
-
/* The set of problems to be solved is stored in two arrays. In
PROBLEMS_IN_ORDER, the problems are stored in the order that they
are solved. This is an internally dense array that may have
/* Macros to determine the reference type. */
#define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
-#define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF))
+#define DF_REF_REG_USE_P(REF) ((REF) && !DF_REF_REG_DEF_P (REF))
#define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
#define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
#define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
/* Macros to access the register information from scan dataflow record. */
-#define DF_REG_SIZE(DF) ((DF)->def_info.regs_size)
+#define DF_REG_SIZE(DF) ((DF)->def_info.regs_inited)
#define DF_REG_DEF_GET(DF, REG) ((DF)->def_info.regs[(REG)])
#define DF_REG_DEF_SET(DF, REG, VAL) ((DF)->def_info.regs[(REG)]=(VAL))
+#define DF_REG_DEF_COUNT(DF, REG) ((DF)->def_info.regs[(REG)]->n_refs)
#define DF_REG_USE_GET(DF, REG) ((DF)->use_info.regs[(REG)])
#define DF_REG_USE_SET(DF, REG, VAL) ((DF)->use_info.regs[(REG)]=(VAL))
+#define DF_REG_USE_COUNT(DF, REG) ((DF)->use_info.regs[(REG)]->n_refs)
/* Macros to access the elements within the reg_info structure table. */
#define DF_INSN_UID_LUID(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->luid)
#define DF_INSN_UID_DEFS(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->defs)
#define DF_INSN_UID_USES(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->uses)
+#define DF_INSN_UID_MWS(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->mw_hardregs)
/* This is a bitmap copy of regs_invalidated_by_call so that we can
easily add it into bitmaps, etc. */
extern bitmap df_invalidated_by_call;
-/* Initialize ur_in and ur_out as if all hard registers were partially
-available. */
-
-/* The way that registers are processed, especially hard registers,
- changes as the compilation proceeds. These states are passed to
- df_set_state to control this processing. */
-
-#define DF_SCAN_INITIAL 1 /* Processing from beginning of rtl to
- global-alloc. */
-#define DF_SCAN_GLOBAL 2 /* Processing before global
- allocation. */
-#define DF_SCAN_POST_ALLOC 4 /* Processing after register
- allocation. */
-extern int df_state; /* Indicates where we are in the compilation. */
-
/* One of these structures is allocated for every basic block. */
struct df_scan_bb_info
};
-/* Reaching uses. */
+/* Reaching uses. All bitmaps are indexed by the id field of the ref
+ except sparse_kill (see below). */
struct df_ru_bb_info
{
+ /* Local sets to describe the basic blocks. */
+ /* The kill set is the set of uses that are killed in this block.
+ However, if the number of uses for this register is greater than
+ DF_SPARSE_THRESHOLD, the sparse_kill is used instead. In
+ sparse_kill, each register gets a slot and a 1 in this bitvector
+ means that all of the uses of that register are killed. This is
+ a very useful efficiency hack in that it keeps from having push
+ around big groups of 1s. This is implemented by the
+ bitmap_clear_range call. */
+
bitmap kill;
bitmap sparse_kill;
- bitmap gen;
- bitmap in;
- bitmap out;
+ bitmap gen; /* The set of uses generated in this block. */
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* At the top of the block. */
+ bitmap out; /* At the bottom of the block. */
};
-/* Reaching definitions. */
+/* Reaching definitions. All bitmaps are indexed by the id field of
+ the ref except sparse_kill (see above). */
struct df_rd_bb_info
{
- bitmap kill;
+ /* Local sets to describe the basic blocks. See the note in the RU
+ datastructures for kill and sparse_kill. */
+ bitmap kill;
bitmap sparse_kill;
- bitmap gen;
- bitmap in;
- bitmap out;
+ bitmap gen; /* The set of defs generated in this block. */
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* At the top of the block. */
+ bitmap out; /* At the bottom of the block. */
};
-/* Live registers. */
+/* Live registers. All bitmaps are referenced by the register number. */
struct df_lr_bb_info
{
- bitmap def;
- bitmap use;
- bitmap in;
- bitmap out;
+ /* Local sets to describe the basic blocks. */
+ bitmap def; /* The set of registers set in this block. */
+ bitmap use; /* The set of registers used in this block. */
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* At the top of the block. */
+ bitmap out; /* At the bottom of the block. */
};
-/* Uninitialized registers. */
+/* Uninitialized registers. All bitmaps are referenced by the register number. */
struct df_ur_bb_info
{
- bitmap kill;
- bitmap gen;
- bitmap in;
- bitmap out;
+ /* Local sets to describe the basic blocks. */
+ bitmap kill; /* The set of registers unset in this block. Calls,
+ for instance, unset registers. */
+ bitmap gen; /* The set of registers set in this block. */
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* At the top of the block. */
+ bitmap out; /* At the bottom of the block. */
};
-/* Uninitialized registers. */
+/* Uninitialized registers. All bitmaps are referenced by the register number. */
struct df_urec_bb_info
{
- bitmap earlyclobber;
+ /* Local sets to describe the basic blocks. */
+ bitmap earlyclobber; /* The set of registers that are referenced
+ with an early clobber mode. */
+ /* Kill and gen are defined as in the UR problem. */
bitmap kill;
bitmap gen;
- bitmap in;
- bitmap out;
+
+ /* The results of the dataflow problem. */
+ bitmap in; /* At the top of the block. */
+ bitmap out; /* At the bottom of the block. */
};
/* Functions defined in df-core.c. */
extern struct df *df_init (int);
-extern struct dataflow *df_add_problem (struct df *, struct df_problem *);
+extern struct dataflow *df_add_problem (struct df *, struct df_problem *, int);
+extern int df_set_flags (struct dataflow *, int);
+extern int df_clear_flags (struct dataflow *, int);
extern void df_set_blocks (struct df*, bitmap);
+extern void df_delete_basic_block (struct df *, int);
extern void df_finish1 (struct df *);
+extern void df_analyze_problem (struct dataflow *, bitmap, bitmap, bitmap, int *, int, bool);
extern void df_analyze (struct df *);
extern void df_compact_blocks (struct df *);
extern void df_bb_replace (struct df *, int, basic_block);
extern bool df_reg_used (struct df *, rtx, rtx);
extern void df_iterative_dataflow (struct dataflow *, bitmap, bitmap, int *, int, bool);
extern void df_dump (struct df *, FILE *);
-extern void df_chain_dump (struct df *, struct df_link *, FILE *);
-extern void df_refs_chain_dump (struct df *, struct df_ref *, bool, FILE *);
+extern void df_refs_chain_dump (struct df_ref *, bool, FILE *);
extern void df_regs_chain_dump (struct df *, struct df_ref *, FILE *);
extern void df_insn_debug (struct df *, rtx, bool, FILE *);
extern void df_insn_debug_regno (struct df *, rtx, FILE *);
extern void df_regno_debug (struct df *, unsigned int, FILE *);
-extern void df_ref_debug (struct df *, struct df_ref *, FILE *);
+extern void df_ref_debug (struct df_ref *, FILE *);
extern void debug_df_insn (rtx);
extern void debug_df_regno (unsigned int);
extern void debug_df_reg (rtx);
/* Functions defined in df-problems.c. */
-extern struct dataflow *df_get_dependent_problem (struct dataflow *);
extern struct df_link *df_chain_create (struct dataflow *, struct df_ref *, struct df_ref *);
extern void df_chain_unlink (struct dataflow *, struct df_ref *, struct df_link *);
extern void df_chain_copy (struct dataflow *, struct df_ref *, struct df_link *);
extern bitmap df_get_live_in (struct df *, basic_block);
extern bitmap df_get_live_out (struct df *, basic_block);
extern void df_grow_bb_info (struct dataflow *);
-extern void df_chain_dump (struct df *, struct df_link *, FILE *);
+extern void df_chain_dump (struct df_link *, FILE *);
extern void df_print_bb_index (basic_block bb, FILE *file);
-extern struct dataflow *df_ru_add_problem (struct df *);
+extern struct dataflow *df_ru_add_problem (struct df *, int);
extern struct df_ru_bb_info *df_ru_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_rd_add_problem (struct df *);
+extern struct dataflow *df_rd_add_problem (struct df *, int);
extern struct df_rd_bb_info *df_rd_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_lr_add_problem (struct df *);
+extern struct dataflow *df_lr_add_problem (struct df *, int);
extern struct df_lr_bb_info *df_lr_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_ur_add_problem (struct df *);
+extern struct dataflow *df_ur_add_problem (struct df *, int);
extern struct df_ur_bb_info *df_ur_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_urec_add_problem (struct df *);
+extern struct dataflow *df_urec_add_problem (struct df *, int);
extern struct df_urec_bb_info *df_urec_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_chain_add_problem (struct df *, int flags);
-extern struct dataflow *df_ri_add_problem (struct df *);
-extern int df_reg_lifetime (struct df *, rtx reg);
+extern struct dataflow *df_chain_add_problem (struct df *, int);
+extern struct dataflow *df_ri_add_problem (struct df *, int);
/* Functions defined in df-scan.c. */
extern struct df_scan_bb_info *df_scan_get_bb_info (struct dataflow *, unsigned int);
-extern struct dataflow *df_scan_add_problem (struct df *);
+extern struct dataflow *df_scan_add_problem (struct df *, int);
extern void df_rescan_blocks (struct df *, bitmap);
extern struct df_ref *df_ref_create (struct df *, rtx, rtx *, rtx,basic_block,enum df_ref_type, enum df_ref_flags);
extern struct df_ref *df_get_artificial_defs (struct df *, unsigned int);
extern void df_bb_refs_delete (struct dataflow *, int);
extern void df_refs_delete (struct dataflow *, bitmap);
extern void df_reorganize_refs (struct df_ref_info *);
-extern void df_set_state (int);
extern void df_hard_reg_init (void);
extern bool df_read_modify_subreg_p (rtx);
+/* web */
+
+/* This entry is allocated for each reference in the insn stream. */
+struct web_entry
+{
+ /* Pointer to the parent in the union/find tree. */
+ struct web_entry *pred;
+ /* Newly assigned register to the entry. Set only for roots. */
+ rtx reg;
+ void* extra_info;
+};
+
+extern struct web_entry *unionfind_root (struct web_entry *);
+extern bool unionfind_union (struct web_entry *, struct web_entry *);
+extern void union_defs (struct df *, struct df_ref *,
+ struct web_entry *, struct web_entry *,
+ bool (*fun) (struct web_entry *, struct web_entry *));
+
+
#endif /* GCC_DF_H */
OSDN Git Service
