1 |
12 |
jlechner |
/* 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, 51 Franklin Street, Fifth Floor, Boston, MA
|
22 |
|
|
02110-1301, 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 */
|