OSDN Git Service

2005-05-26 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / df.h
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)
6
7 This file is part of GCC.
8
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.
13
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.
18
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.  */
23
24 #ifndef GCC_DF_H
25 #define GCC_DF_H
26
27 #include "bitmap.h"
28 #include "basic-block.h"
29
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.  */
41 #define DF_SUBREGS      4096    /* Return subregs rather than the inner reg.  */
42
43 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
44                   DF_REF_REG_MEM_STORE};
45
46 #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
47
48 /* Link on a def-use or use-def chain.  */
49 struct df_link
50 {
51   struct df_link *next;
52   struct ref *ref;
53 };
54
55 enum df_ref_flags
56   {
57     /* Read-modify-write refs generate both a use and a def and
58        these are marked with this flag to show that they are not
59        independent.  */
60     DF_REF_READ_WRITE = 1,
61
62     /* This flag is set, if we stripped the subreg from the reference.
63        In this case we must make conservative guesses, at what the
64        outer mode was.  */
65     DF_REF_STRIPPED = 2
66   };
67
68
69 /* Define a register reference structure.  One of these is allocated
70    for every register reference (use or def).  Note some register
71    references (e.g., post_inc, subreg) generate both a def and a use.  */
72 struct ref
73 {
74   rtx reg;                      /* The register referenced.  */
75   rtx insn;                     /* Insn containing ref.  */
76   rtx *loc;                     /* The location of the reg.  */
77   struct df_link *chain;        /* Head of def-use or use-def chain.  */
78   unsigned int id;              /* Ref index.  */
79   enum df_ref_type type;        /* Type of ref.  */
80   enum df_ref_flags flags;      /* Various flags.  */
81   void *data;                   /* The data assigned to it by user.  */
82 };
83
84
85 /* One of these structures is allocated for every insn.  */
86 struct insn_info
87 {
88   struct df_link *defs;         /* Head of insn-def chain.  */
89   struct df_link *uses;         /* Head of insn-use chain.  */
90   /* ???? The following luid field should be considered private so that
91      we can change it on the fly to accommodate new insns?  */
92   int luid;                     /* Logical UID.  */
93 };
94
95
96 /* One of these structures is allocated for every reg.  */
97 struct reg_info
98 {
99   struct df_link *defs;         /* Head of reg-def chain.  */
100   struct df_link *uses;         /* Head of reg-use chain.  */
101   int lifetime;
102   int n_defs;
103   int n_uses;
104 };
105
106
107 /* One of these structures is allocated for every basic block.  */
108 struct bb_info
109 {
110   /* Reaching def bitmaps have def_id elements.  */
111   bitmap rd_kill;
112   bitmap rd_gen;
113   bitmap rd_in;
114   bitmap rd_out;
115   /* Reaching use bitmaps have use_id elements.  */
116   bitmap ru_kill;
117   bitmap ru_gen;
118   bitmap ru_in;
119   bitmap ru_out;
120   /* Live variable bitmaps have n_regs elements.  */
121   bitmap lr_def;
122   bitmap lr_use;
123   bitmap lr_in;
124   bitmap lr_out;
125   int rd_valid;
126   int ru_valid;
127   int lr_valid;
128 };
129
130
131 struct df
132 {
133   int flags;                    /* Indicates what's recorded.  */
134   struct bb_info *bbs;          /* Basic block table.  */
135   struct ref **defs;            /* Def table, indexed by def_id.  */
136   struct ref **uses;            /* Use table, indexed by use_id.  */
137   struct ref **reg_def_last;    /* Indexed by regno.  */
138   struct reg_info *regs;        /* Regs table, index by regno.  */
139   unsigned int reg_size;        /* Size of regs table.  */
140   struct insn_info *insns;      /* Insn table, indexed by insn UID.  */
141   unsigned int insn_size;       /* Size of insn table.  */
142   unsigned int def_id;          /* Next def ID.  */
143   unsigned int def_size;        /* Size of def table.  */
144   unsigned int n_defs;          /* Size of def bitmaps.  */
145   unsigned int use_id;          /* Next use ID.  */
146   unsigned int use_size;        /* Size of use table.  */
147   unsigned int n_uses;          /* Size of use bitmaps.  */
148   unsigned int n_bbs;           /* Number of basic blocks.  */
149   unsigned int n_regs;          /* Number of regs.  */
150   unsigned int def_id_save;     /* Saved next def ID.  */
151   unsigned int use_id_save;     /* Saved next use ID.  */
152   bitmap insns_modified;        /* Insns that (may) have changed.  */
153   bitmap bbs_modified;          /* Blocks that (may) have changed.  */
154   bitmap all_blocks;            /* All blocks in CFG.  */
155   int *dfs_order;               /* DFS order -> block number.  */
156   int *rc_order;                /* Reverse completion order -> block number.  */
157   int *rts_order;               /* Reverse top sort order -> block number.  */
158   int *inverse_rc_map;          /* Block number -> reverse completion order.  */
159   int *inverse_dfs_map;         /* Block number -> DFS order.  */
160   int *inverse_rts_map;         /* Block number -> reverse top-sort order.  */
161 };
162
163
164 struct df_map
165 {
166   rtx old;
167   rtx new;
168 };
169
170
171 #define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index])
172
173
174 /* Macros to access the elements within the ref structure.  */
175
176 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
177                                 ? SUBREG_REG ((REF)->reg) : ((REF)->reg))
178 #define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF))
179 #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \
180                                 ? &SUBREG_REG ((REF)->reg) : ((REF)->loc))
181 #define DF_REF_REG(REF) ((REF)->reg)
182 #define DF_REF_LOC(REF) ((REF)->loc)
183 #define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn))
184 #define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index)
185 #define DF_REF_INSN(REF) ((REF)->insn)
186 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
187 #define DF_REF_TYPE(REF) ((REF)->type)
188 #define DF_REF_CHAIN(REF) ((REF)->chain)
189 #define DF_REF_ID(REF) ((REF)->id)
190 #define DF_REF_FLAGS(REF) ((REF)->flags)
191 #define DF_REF_DATA(REF) ((REF)->data)
192
193 /* Macros to determine the reference type.  */
194
195 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
196 #define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF))
197 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
198 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
199 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
200                                || DF_REF_REG_MEM_LOAD_P (REF))
201
202
203 /* Macros to access the elements within the reg_info structure table.  */
204
205 #define DF_REGNO_FIRST_DEF(DF, REGNUM) \
206 ((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0)
207 #define DF_REGNO_LAST_USE(DF, REGNUM) \
208 ((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0)
209
210 #define DF_REGNO_FIRST_BB(DF, REGNUM) \
211 ((DF)->regs[REGNUM].defs ? DF_REF_BB ((DF)->regs[REGNUM].defs->ref) : 0)
212 #define DF_REGNO_LAST_BB(DF, REGNUM) \
213 ((DF)->regs[REGNUM].uses ? DF_REF_BB ((DF)->regs[REGNUM].uses->ref) : 0)
214
215
216 /* Macros to access the elements within the insn_info structure table.  */
217
218 #define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid)
219 #define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs)
220 #define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses)
221
222
223 /* Functions to build and analyze dataflow information.  */
224
225 extern struct df *df_init (void);
226
227 extern int df_analyze (struct df *, bitmap, int);
228 extern void df_analyze_subcfg (struct df *, bitmap, int);
229
230 extern void df_finish (struct df *);
231
232 extern void df_dump (struct df *, int, FILE *);
233
234
235 /* Functions to modify insns.  */
236
237 extern bool df_insn_modified_p (struct df *, rtx);
238
239 extern void df_insn_modify (struct df *, basic_block, rtx);
240
241 extern rtx df_insn_delete (struct df *, basic_block, rtx);
242
243 extern rtx df_pattern_emit_before (struct df *, rtx, basic_block, rtx);
244
245 extern rtx df_jump_pattern_emit_after (struct df *, rtx, basic_block, rtx);
246
247 extern rtx df_pattern_emit_after (struct df *, rtx, basic_block, rtx);
248
249 extern rtx df_insn_move_before (struct df *, basic_block, rtx, basic_block,
250                                 rtx);
251
252 extern int df_reg_replace (struct df *, bitmap, rtx, rtx);
253
254 extern int df_ref_reg_replace (struct df *, struct ref *, rtx, rtx);
255
256 extern int df_ref_remove (struct df *, struct ref *);
257
258 extern int df_insn_mem_replace (struct df *, basic_block, rtx, rtx, rtx);
259
260 extern struct ref *df_bb_def_use_swap (struct df *, basic_block, rtx, rtx,
261                                        unsigned int);
262
263
264 /* Functions to query dataflow information.  */
265
266 extern basic_block df_regno_bb (struct df *, unsigned int);
267
268 extern int df_reg_lifetime (struct df *, rtx);
269
270 extern int df_reg_global_p (struct df *, rtx);
271
272 extern int df_insn_regno_def_p (struct df *, basic_block, rtx, unsigned int);
273
274 extern int df_insn_dominates_all_uses_p (struct df *, basic_block, rtx);
275
276 extern int df_insn_dominates_uses_p (struct df *, basic_block, rtx, bitmap);
277
278 extern int df_bb_reg_live_start_p (struct df *, basic_block, rtx);
279
280 extern int df_bb_reg_live_end_p (struct df *, basic_block, rtx);
281
282 extern int df_bb_regs_lives_compare (struct df *, basic_block, rtx, rtx);
283
284 extern bool df_local_def_available_p (struct df *, struct ref *, struct ref *);
285
286 extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx,
287                                            rtx);
288 extern struct ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int);
289
290 extern struct ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int);
291
292 extern struct ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
293
294 extern struct ref *df_find_def (struct df *, rtx, rtx);
295
296 extern int df_reg_used (struct df *, rtx, rtx);
297
298 /* Functions for debugging from GDB.  */
299
300 extern void debug_df_insn (rtx);
301
302 extern void debug_df_regno (unsigned int);
303
304 extern void debug_df_reg (rtx);
305
306 extern void debug_df_defno (unsigned int);
307
308 extern void debug_df_useno (unsigned int);
309
310 extern void debug_df_ref (struct ref *);
311
312 extern void debug_df_chain (struct df_link *);
313
314 extern void df_insn_debug (struct df *, rtx, FILE *);
315
316 extern void df_insn_debug_regno (struct df *, rtx, FILE *);
317
318
319 /* Meet over any path (UNION) or meet over all paths (INTERSECTION).  */
320 enum df_confluence_op
321   {
322     DF_UNION,
323     DF_INTERSECTION
324   };
325
326
327 /* Dataflow direction.  */
328 enum df_flow_dir
329   {
330     DF_FORWARD,
331     DF_BACKWARD
332   };
333
334
335 typedef void (*transfer_function) (int, int *, void *, void *,
336                                    void *, void *, void *);
337
338 /* The description of a dataflow problem to solve.  */
339
340 enum set_representation
341 {
342   SR_SBITMAP,           /* Represent sets by bitmaps.  */
343   SR_BITMAP             /* Represent sets by sbitmaps.  */
344 };
345
346 struct dataflow
347 {
348   enum set_representation repr;         /* The way the sets are represented.  */
349
350   /* The following arrays are indexed by block indices, so they must always
351      be large enough even if we restrict ourselves just to a subset of cfg.  */
352   void **gen, **kill;                   /* Gen and kill sets.  */
353   void **in, **out;                     /* Results.  */
354
355   enum df_flow_dir dir;                 /* Dataflow direction.  */
356   enum df_confluence_op conf_op;        /* Confluence operator.  */ 
357   unsigned n_blocks;                    /* Number of basic blocks in the
358                                            order.  */
359   int *order;                           /* The list of basic blocks to work
360                                            with, in the order they should
361                                            be processed in.  */
362   transfer_function transfun;           /* The transfer function.  */
363   void *data;                           /* Data used by the transfer
364                                            function.  */
365 };
366
367 extern void iterative_dataflow (struct dataflow *);
368 extern bool read_modify_subreg_p (rtx);
369
370 #endif /* GCC_DF_H */