2005-04-25 Paul Brook <paul@codesourcery.com>
[official-gcc.git] / gcc / df.h
blob60f6030fae15ec305f8b55f9fa8b06f8953b0234
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, 2003, 2004, 2005
4 Free Software Foundation, Inc.
5 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 02111-1307, USA. */
24 #ifndef GCC_DF_H
25 #define GCC_DF_H
27 #include "bitmap.h"
28 #include "basic-block.h"
30 #define DF_RD 1 /* Reaching definitions. */
31 #define DF_RU 2 /* Reaching uses. */
32 #define DF_LR 4 /* Live registers. */
33 #define DF_DU_CHAIN 8 /* Def-use chain. */
34 #define DF_UD_CHAIN 16 /* Use-def chain. */
35 #define DF_REG_INFO 32 /* Register info. */
36 #define DF_RD_CHAIN 64 /* Reg-def chain. */
37 #define DF_RU_CHAIN 128 /* Reg-use chain. */
38 #define DF_ALL 255
39 #define DF_HARD_REGS 1024 /* Mark hard registers. */
40 #define DF_EQUIV_NOTES 2048 /* Mark uses present in EQUIV/EQUAL notes. */
42 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
43 DF_REF_REG_MEM_STORE};
45 #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
47 /* Link on a def-use or use-def chain. */
48 struct df_link
50 struct df_link *next;
51 struct ref *ref;
54 enum df_ref_flags
56 /* Read-modify-write refs generate both a use and a def and
57 these are marked with this flag to show that they are not
58 independent. */
59 DF_REF_READ_WRITE = 1,
61 /* This flag is set, if we stripped the subreg from the reference.
62 In this case we must make conservative guesses, at what the
63 outer mode was. */
64 DF_REF_STRIPPED = 2
68 /* Define a register reference structure. One of these is allocated
69 for every register reference (use or def). Note some register
70 references (e.g., post_inc, subreg) generate both a def and a use. */
71 struct ref
73 rtx reg; /* The register referenced. */
74 rtx insn; /* Insn containing ref. */
75 rtx *loc; /* The location of the reg. */
76 struct df_link *chain; /* Head of def-use or use-def chain. */
77 unsigned int id; /* Ref index. */
78 enum df_ref_type type; /* Type of ref. */
79 enum df_ref_flags flags; /* Various flags. */
80 void *data; /* The data assigned to it by user. */
84 /* One of these structures is allocated for every insn. */
85 struct insn_info
87 struct df_link *defs; /* Head of insn-def chain. */
88 struct df_link *uses; /* Head of insn-use chain. */
89 /* ???? The following luid field should be considered private so that
90 we can change it on the fly to accommodate new insns? */
91 int luid; /* Logical UID. */
95 /* One of these structures is allocated for every reg. */
96 struct reg_info
98 struct df_link *defs; /* Head of reg-def chain. */
99 struct df_link *uses; /* Head of reg-use chain. */
100 int lifetime;
101 int n_defs;
102 int n_uses;
106 /* One of these structures is allocated for every basic block. */
107 struct bb_info
109 /* Reaching def bitmaps have def_id elements. */
110 bitmap rd_kill;
111 bitmap rd_gen;
112 bitmap rd_in;
113 bitmap rd_out;
114 /* Reaching use bitmaps have use_id elements. */
115 bitmap ru_kill;
116 bitmap ru_gen;
117 bitmap ru_in;
118 bitmap ru_out;
119 /* Live variable bitmaps have n_regs elements. */
120 bitmap lr_def;
121 bitmap lr_use;
122 bitmap lr_in;
123 bitmap lr_out;
124 int rd_valid;
125 int ru_valid;
126 int lr_valid;
130 struct df
132 int flags; /* Indicates what's recorded. */
133 struct bb_info *bbs; /* Basic block table. */
134 struct ref **defs; /* Def table, indexed by def_id. */
135 struct ref **uses; /* Use table, indexed by use_id. */
136 struct ref **reg_def_last; /* Indexed by regno. */
137 struct reg_info *regs; /* Regs table, index by regno. */
138 unsigned int reg_size; /* Size of regs table. */
139 struct insn_info *insns; /* Insn table, indexed by insn UID. */
140 unsigned int insn_size; /* Size of insn table. */
141 unsigned int def_id; /* Next def ID. */
142 unsigned int def_size; /* Size of def table. */
143 unsigned int n_defs; /* Size of def bitmaps. */
144 unsigned int use_id; /* Next use ID. */
145 unsigned int use_size; /* Size of use table. */
146 unsigned int n_uses; /* Size of use bitmaps. */
147 unsigned int n_bbs; /* Number of basic blocks. */
148 unsigned int n_regs; /* Number of regs. */
149 unsigned int def_id_save; /* Saved next def ID. */
150 unsigned int use_id_save; /* Saved next use ID. */
151 bitmap insns_modified; /* Insns that (may) have changed. */
152 bitmap bbs_modified; /* Blocks that (may) have changed. */
153 bitmap all_blocks; /* All blocks in CFG. */
154 int *dfs_order; /* DFS order -> block number. */
155 int *rc_order; /* Reverse completion order -> block number. */
156 int *rts_order; /* Reverse top sort order -> block number. */
157 int *inverse_rc_map; /* Block number -> reverse completion order. */
158 int *inverse_dfs_map; /* Block number -> DFS order. */
159 int *inverse_rts_map; /* Block number -> reverse top-sort order. */
163 struct df_map
165 rtx old;
166 rtx new;
170 #define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index])
173 /* Macros to access the elements within the ref structure. */
175 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
176 ? SUBREG_REG ((REF)->reg) : ((REF)->reg))
177 #define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF))
178 #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \
179 ? &SUBREG_REG ((REF)->reg) : ((REF)->loc))
180 #define DF_REF_REG(REF) ((REF)->reg)
181 #define DF_REF_LOC(REF) ((REF)->loc)
182 #define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn))
183 #define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index)
184 #define DF_REF_INSN(REF) ((REF)->insn)
185 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
186 #define DF_REF_TYPE(REF) ((REF)->type)
187 #define DF_REF_CHAIN(REF) ((REF)->chain)
188 #define DF_REF_ID(REF) ((REF)->id)
189 #define DF_REF_FLAGS(REF) ((REF)->flags)
190 #define DF_REF_DATA(REF) ((REF)->data)
192 /* Macros to determine the reference type. */
194 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
195 #define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF))
196 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
197 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
198 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
199 || DF_REF_REG_MEM_LOAD_P (REF))
202 /* Macros to access the elements within the reg_info structure table. */
204 #define DF_REGNO_FIRST_DEF(DF, REGNUM) \
205 ((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0)
206 #define DF_REGNO_LAST_USE(DF, REGNUM) \
207 ((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0)
209 #define DF_REGNO_FIRST_BB(DF, REGNUM) \
210 (DF_REGNO_FIRST_DEF (DF, REGNUM) \
211 ? DF_REF_BB (DF_REGNO_FIRST_DEF (DF, REGNUM)) : 0)
212 #define DF_REGNO_LAST_BB(DF, REGNUM) \
213 (DF_REGNO_LAST_USE (DF, REGNUM) \
214 ? DF_REF_BB (DF_REGNO_LAST_USE (DF, REGNUM)) : 0)
217 /* Macros to access the elements within the insn_info structure table. */
219 #define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid)
220 #define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs)
221 #define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses)
224 /* Functions to build and analyze dataflow information. */
226 extern struct df *df_init (void);
228 extern int df_analyze (struct df *, bitmap, int);
229 extern void df_analyze_subcfg (struct df *, bitmap, int);
231 extern void df_finish (struct df *);
233 extern void df_dump (struct df *, int, FILE *);
236 /* Functions to modify insns. */
238 extern void df_insn_modify (struct df *, basic_block, rtx);
240 extern rtx df_insn_delete (struct df *, basic_block, rtx);
242 extern rtx df_pattern_emit_before (struct df *, rtx, basic_block, rtx);
244 extern rtx df_jump_pattern_emit_after (struct df *, rtx, basic_block, rtx);
246 extern rtx df_pattern_emit_after (struct df *, rtx, basic_block, rtx);
248 extern rtx df_insn_move_before (struct df *, basic_block, rtx, basic_block,
249 rtx);
251 extern int df_reg_replace (struct df *, bitmap, rtx, rtx);
253 extern int df_ref_reg_replace (struct df *, struct ref *, rtx, rtx);
255 extern int df_ref_remove (struct df *, struct ref *);
257 extern int df_insn_mem_replace (struct df *, basic_block, rtx, rtx, rtx);
259 extern struct ref *df_bb_def_use_swap (struct df *, basic_block, rtx, rtx,
260 unsigned int);
263 /* Functions to query dataflow information. */
265 extern basic_block df_regno_bb (struct df *, unsigned int);
267 extern int df_reg_lifetime (struct df *, rtx);
269 extern int df_reg_global_p (struct df *, rtx);
271 extern int df_insn_regno_def_p (struct df *, basic_block, rtx, unsigned int);
273 extern int df_insn_dominates_all_uses_p (struct df *, basic_block, rtx);
275 extern int df_insn_dominates_uses_p (struct df *, basic_block, rtx, bitmap);
277 extern int df_bb_reg_live_start_p (struct df *, basic_block, rtx);
279 extern int df_bb_reg_live_end_p (struct df *, basic_block, rtx);
281 extern int df_bb_regs_lives_compare (struct df *, basic_block, rtx, rtx);
283 extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx,
284 rtx);
285 extern struct ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int);
287 extern struct ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int);
289 extern struct ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
291 extern struct ref *df_find_def (struct df *, rtx, rtx);
293 extern int df_reg_used (struct df *, rtx, rtx);
295 /* Functions for debugging from GDB. */
297 extern void debug_df_insn (rtx);
299 extern void debug_df_regno (unsigned int);
301 extern void debug_df_reg (rtx);
303 extern void debug_df_defno (unsigned int);
305 extern void debug_df_useno (unsigned int);
307 extern void debug_df_ref (struct ref *);
309 extern void debug_df_chain (struct df_link *);
311 extern void df_insn_debug (struct df *, rtx, FILE *);
313 extern void df_insn_debug_regno (struct df *, rtx, FILE *);
316 /* Meet over any path (UNION) or meet over all paths (INTERSECTION). */
317 enum df_confluence_op
319 DF_UNION,
320 DF_INTERSECTION
324 /* Dataflow direction. */
325 enum df_flow_dir
327 DF_FORWARD,
328 DF_BACKWARD
332 typedef void (*transfer_function) (int, int *, void *, void *,
333 void *, void *, void *);
335 /* The description of a dataflow problem to solve. */
337 enum set_representation
339 SR_SBITMAP, /* Represent sets by bitmaps. */
340 SR_BITMAP /* Represent sets by sbitmaps. */
343 struct dataflow
345 enum set_representation repr; /* The way the sets are represented. */
347 /* The following arrays are indexed by block indices, so they must always
348 be large enough even if we restrict ourselves just to a subset of cfg. */
349 void **gen, **kill; /* Gen and kill sets. */
350 void **in, **out; /* Results. */
352 enum df_flow_dir dir; /* Dataflow direction. */
353 enum df_confluence_op conf_op; /* Confluence operator. */
354 unsigned n_blocks; /* Number of basic blocks in the
355 order. */
356 int *order; /* The list of basic blocks to work
357 with, in the order they should
358 be processed in. */
359 transfer_function transfun; /* The transfer function. */
360 void *data; /* Data used by the transfer
361 function. */
364 extern void iterative_dataflow (struct dataflow *);
365 extern bool read_modify_subreg_p (rtx);
367 #endif /* GCC_DF_H */