2002-02-19 Philip Blundell <philb@gnu.org>
[official-gcc.git] / gcc / df.h
blob7f4e4be71efc3c910290575fff9ece829900b4da
1 /* Form lists of pseudo register references for autoinc optimization
2 for GNU compiler. This is part of flow optimization.
3 Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
4 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
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
11 version.
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
16 for more details.
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, 59 Temple Place - Suite 330, Boston, MA
21 02111-1307, USA. */
23 #define DF_RD 1 /* Reaching definitions. */
24 #define DF_RU 2 /* Reaching uses. */
25 #define DF_LR 4 /* Live registers. */
26 #define DF_DU_CHAIN 8 /* Def-use chain. */
27 #define DF_UD_CHAIN 16 /* Use-def chain. */
28 #define DF_REG_INFO 32 /* Register info. */
29 #define DF_RD_CHAIN 64 /* Reg-def chain. */
30 #define DF_RU_CHAIN 128 /* Reg-use chain. */
31 #define DF_ALL 255
32 #define DF_HARD_REGS 1024
33 #define DF_EQUIV_NOTES 2048 /* Mark uses present in EQUIV/EQUAL notes. */
35 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
36 DF_REF_REG_MEM_STORE};
38 #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
40 /* ???> Perhaps all these data structures should be made private
41 to enforce the interface. */
44 /* Link on a def-use or use-def chain. */
45 struct df_link
47 struct df_link *next;
48 struct ref *ref;
51 enum df_ref_flags
53 DF_REF_READ_WRITE = 1
56 /* Define a register reference structure. */
57 struct ref
59 rtx reg; /* The register referenced. */
60 rtx insn; /* Insn containing ref. */
61 rtx *loc; /* Loc is the location of the reg. */
62 struct df_link *chain; /* Head of def-use or use-def chain. */
63 enum df_ref_type type; /* Type of ref. */
64 int id; /* Ref index. */
65 enum df_ref_flags flags; /* Various flags. */
69 /* One of these structures is allocated for every insn. */
70 struct insn_info
72 struct df_link *defs; /* Head of insn-def chain. */
73 struct df_link *uses; /* Head of insn-use chain. */
74 /* ???? The following luid field should be considerd private so that
75 we can change it on the fly to accommodate new insns? */
76 int luid; /* Logical UID. */
77 #if 0
78 rtx insn; /* Backpointer to the insn. */
79 #endif
83 /* One of these structures is allocated for every reg. */
84 struct reg_info
86 struct df_link *defs; /* Head of reg-def chain. */
87 struct df_link *uses; /* Head of reg-use chain. */
88 int lifetime;
89 int n_defs;
90 int n_uses;
94 /* One of these structures is allocated for every basic block. */
95 struct bb_info
97 /* Reaching def bitmaps have def_id elements. */
98 bitmap rd_kill;
99 bitmap rd_gen;
100 bitmap rd_in;
101 bitmap rd_out;
102 /* Reaching use bitmaps have use_id elements. */
103 bitmap ru_kill;
104 bitmap ru_gen;
105 bitmap ru_in;
106 bitmap ru_out;
107 /* Live variable bitmaps have n_regs elements. */
108 bitmap lr_def;
109 bitmap lr_use;
110 bitmap lr_in;
111 bitmap lr_out;
112 int rd_valid;
113 int ru_valid;
114 int lr_valid;
118 struct df
120 int flags; /* Indicates what's recorded. */
121 struct bb_info *bbs; /* Basic block table. */
122 struct ref **defs; /* Def table, indexed by def_id. */
123 struct ref **uses; /* Use table, indexed by use_id. */
124 struct ref **reg_def_last; /* Indexed by regno. */
125 struct reg_info *regs; /* Regs table, index by regno. */
126 unsigned int reg_size; /* Size of regs table. */
127 struct insn_info *insns; /* Insn table, indexed by insn UID. */
128 unsigned int insn_size; /* Size of insn table. */
129 unsigned int def_id; /* Next def ID. */
130 unsigned int def_size; /* Size of def table. */
131 unsigned int n_defs; /* Size of def bitmaps. */
132 unsigned int use_id; /* Next use ID. */
133 unsigned int use_size; /* Size of use table. */
134 unsigned int n_uses; /* Size of use bitmaps. */
135 unsigned int n_bbs; /* Number of basic blocks. */
136 unsigned int n_regs; /* Number of regs. */
137 unsigned int def_id_save; /* Saved next def ID. */
138 unsigned int use_id_save; /* Saved next use ID. */
139 bitmap insns_modified; /* Insns that (may) have changed. */
140 bitmap bbs_modified; /* Blocks that (may) have changed. */
141 bitmap all_blocks; /* All blocks in CFG. */
142 /* The sbitmap vector of dominators or NULL if not computed.
143 Ideally, this should be a pointer to a CFG object. */
144 sbitmap *dom;
145 int * dfs_order; /* DFS order -> block number */
146 int * rc_order; /* reverse completion order -> block number */
147 int * rts_order; /* reverse top sort order -> block number */
148 int * inverse_rc_map; /* block number -> reverse completion order */
149 int * inverse_dfs_map; /* block number -> DFS order */
150 int * inverse_rts_map; /* block number -> reverse top-sort order */
154 struct df_map
156 rtx old;
157 rtx new;
161 #define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index])
164 /* Macros to access the elements within the ref structure. */
165 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
166 ? SUBREG_REG ((REF)->reg) : ((REF)->reg))
167 #define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF))
168 #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \
169 ? &SUBREG_REG ((REF)->reg) : ((REF)->loc))
170 #ifdef OLD_DF_INTERFACE
171 #define DF_REF_REG(REF) DF_REF_REAL_REG(REF)
172 #define DF_REF_LOC(REF) DF_REF_REAL_LOC(REF)
173 #else
174 #define DF_REF_REG(REF) ((REF)->reg)
175 #define DF_REF_LOC(REF) ((REF)->loc)
176 #endif
177 #define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn))
178 #define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index)
179 #define DF_REF_INSN(REF) ((REF)->insn)
180 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
181 #define DF_REF_TYPE(REF) ((REF)->type)
182 #define DF_REF_CHAIN(REF) ((REF)->chain)
183 #define DF_REF_ID(REF) ((REF)->id)
184 #define DF_REF_FLAGS(REF) ((REF)->flags)
186 /* Macros to determine the reference type. */
188 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
189 #define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF))
190 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
191 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
192 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
193 || DF_REF_REG_MEM_LOAD_P (REF))
196 /* Macros to access the elements within the reg_info structure table. */
198 #define DF_REGNO_FIRST_DEF(DF, REGNUM) \
199 ((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0)
200 #define DF_REGNO_LAST_USE(DF, REGNUM) \
201 ((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0)
203 #define DF_REGNO_FIRST_BB(DF, REGNUM) \
204 (DF_REGNO_FIRST_DEF (DF, REGNUM) \
205 ? DF_REF_BB (DF_REGNO_FIRST_DEF (DF, REGNUM)) : 0)
206 #define DF_REGNO_LAST_BB(DF, REGNUM) \
207 (DF_REGNO_LAST_USE (DF, REGNUM) \
208 ? DF_REF_BB (DF_REGNO_LAST_USE (DF, REGNUM)) : 0)
211 /* Macros to access the elements within the insn_info structure table. */
213 #define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid)
214 #define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs)
215 #define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses)
218 /* Functions to build and analyse dataflow information. */
220 extern struct df *df_init PARAMS ((void));
222 extern int df_analyse PARAMS ((struct df *, bitmap, int));
224 extern void df_finish PARAMS ((struct df *));
226 extern void df_dump PARAMS ((struct df *, int, FILE *));
228 /* Functions to modify insns. */
230 extern void df_insn_modify PARAMS ((struct df *, basic_block, rtx));
232 extern rtx df_insn_delete PARAMS ((struct df *, basic_block, rtx));
234 extern rtx df_pattern_emit_before PARAMS ((struct df *, rtx,
235 basic_block, rtx));
237 extern rtx df_jump_pattern_emit_after PARAMS ((struct df *, rtx,
238 basic_block, rtx));
240 extern rtx df_pattern_emit_after PARAMS ((struct df *, rtx,
241 basic_block, rtx));
243 extern rtx df_insn_move_before PARAMS ((struct df *, basic_block, rtx,
244 basic_block, rtx));
246 extern int df_reg_replace PARAMS ((struct df *, bitmap, rtx, rtx));
248 extern int df_ref_reg_replace PARAMS ((struct df *, struct ref *, rtx, rtx));
250 extern int df_ref_remove PARAMS ((struct df *, struct ref *));
252 extern int df_insn_reg_replace PARAMS ((struct df *, basic_block,
253 rtx, rtx, rtx));
255 extern int df_insn_mem_replace PARAMS ((struct df *, basic_block,
256 rtx, rtx, rtx));
258 extern struct ref *df_bb_def_use_swap PARAMS ((struct df *, basic_block,
259 rtx, rtx, unsigned int));
262 /* Functions to query dataflow information. */
264 extern basic_block df_regno_bb PARAMS((struct df *, unsigned int));
266 extern int df_reg_lifetime PARAMS ((struct df *, rtx));
268 extern int df_reg_global_p PARAMS ((struct df *, rtx));
270 extern int df_insn_regno_def_p PARAMS ((struct df *,
271 basic_block, rtx, unsigned int));
273 extern int df_insn_dominates_all_uses_p PARAMS ((struct df *,
274 basic_block, rtx));
276 extern int df_insn_dominates_uses_p PARAMS ((struct df *, basic_block,
277 rtx, bitmap));
279 extern int df_bb_reg_live_start_p PARAMS ((struct df *, basic_block, rtx));
281 extern int df_bb_reg_live_end_p PARAMS ((struct df *, basic_block, rtx));
283 extern int df_bb_regs_lives_compare PARAMS ((struct df *, basic_block,
284 rtx, rtx));
286 extern rtx df_bb_single_def_use_insn_find PARAMS((struct df *, basic_block,
287 rtx, rtx));
290 /* Functions for debugging from GDB. */
292 extern void debug_df_insn PARAMS ((rtx));
294 extern void debug_df_regno PARAMS ((unsigned int));
296 extern void debug_df_reg PARAMS ((rtx));
298 extern void debug_df_defno PARAMS ((unsigned int));
300 extern void debug_df_useno PARAMS ((unsigned int));
302 extern void debug_df_ref PARAMS ((struct ref *));
304 extern void debug_df_chain PARAMS ((struct df_link *));
305 extern void df_insn_debug PARAMS ((struct df *, rtx, FILE *));
306 extern void df_insn_debug_regno PARAMS ((struct df *, rtx, FILE *));
307 /* Meet over any path (UNION) or meet over all paths (INTERSECTION) */
308 enum df_confluence_op
310 UNION,
311 INTERSECTION
313 /* Dataflow direction */
314 enum df_flow_dir
316 FORWARD,
317 BACKWARD
320 typedef void (*transfer_function_sbitmap) PARAMS ((int, int *, sbitmap, sbitmap,
321 sbitmap, sbitmap, void *));
322 typedef void (*transfer_function_bitmap) PARAMS ((int, int *, bitmap, bitmap,
323 bitmap, bitmap, void *));
325 extern void iterative_dataflow_sbitmap PARAMS ((sbitmap *, sbitmap *,
326 sbitmap *, sbitmap *,
327 bitmap, enum df_flow_dir,
328 enum df_confluence_op,
329 transfer_function_sbitmap,
330 int *, void *));
331 extern void iterative_dataflow_bitmap PARAMS ((bitmap *, bitmap *, bitmap *,
332 bitmap *, bitmap,
333 enum df_flow_dir,
334 enum df_confluence_op,
335 transfer_function_bitmap,
336 int *, void *));