]>
Commit | Line | Data |
---|---|---|
10c4b247 JL |
1 | /* Form lists of pseudo register references for autoinc optimization |
2 | for GNU compiler. This is part of flow optimization. | |
7890e8f3 | 3 | Copyright (C) 1999, 2000, 2001, 2003 Free Software Foundation, Inc. |
10c4b247 JL |
4 | Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz) |
5 | ||
1322177d | 6 | This file is part of GCC. |
10c4b247 | 7 | |
1322177d LB |
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. | |
10c4b247 | 12 | |
1322177d LB |
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. | |
10c4b247 JL |
17 | |
18 | You should have received a copy of the GNU General Public License | |
1322177d LB |
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. */ | |
10c4b247 | 22 | |
10c4b247 JL |
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 | |
7890e8f3 | 32 | #define DF_HARD_REGS 1024 /* Mark hard registers. */ |
73991d6a | 33 | #define DF_EQUIV_NOTES 2048 /* Mark uses present in EQUIV/EQUAL notes. */ |
50aac998 | 34 | #define DF_FOR_REGALLOC 4096 /* If called for the register allocator. */ |
10c4b247 JL |
35 | |
36 | enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD, | |
37 | DF_REF_REG_MEM_STORE}; | |
38 | ||
39 | #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"} | |
40 | ||
10c4b247 JL |
41 | /* Link on a def-use or use-def chain. */ |
42 | struct df_link | |
43 | { | |
44 | struct df_link *next; | |
45 | struct ref *ref; | |
46 | }; | |
47 | ||
7fcd7218 JH |
48 | enum df_ref_flags |
49 | { | |
7890e8f3 MH |
50 | /* Read-modify-write refs generate both a use and a def and |
51 | these are marked with this flag to show that they are not | |
52 | independent. */ | |
ed8d2920 | 53 | DF_REF_READ_WRITE = 1, |
7890e8f3 MH |
54 | |
55 | /* This flag is set on register references inside a subreg on | |
50aac998 | 56 | machines which have CANNOT_CHANGE_MODE_CLASS. |
7890e8f3 MH |
57 | Note, that this flag can also be set on df_refs representing |
58 | the REG itself (i.e., one might not see the subreg anyore). | |
59 | Also note, that this flag is set also for hardreg refs, i.e., | |
60 | you must check yourself if it's a pseudo. */ | |
50aac998 MM |
61 | DF_REF_MODE_CHANGE = 2, |
62 | ||
63 | /* This flag is set, if we stripped the subreg from the reference. | |
64 | In this case we must make conservative guesses, at what the | |
65 | outer mode was. */ | |
b3411d7e DB |
66 | DF_REF_STRIPPED = 4, |
67 | ||
68 | /* This flag is set during register allocation if it's okay for | |
69 | the reference's INSN to have one of its operands replaced with a | |
70 | memory reference. */ | |
71 | DF_REF_MEM_OK = 8 | |
7fcd7218 | 72 | }; |
10c4b247 | 73 | |
7890e8f3 MH |
74 | |
75 | /* Define a register reference structure. One of these is allocated | |
76 | for every register reference (use or def). Note some register | |
77 | references (e.g., post_inc, subreg) generate both a def and a use. */ | |
10c4b247 JL |
78 | struct ref |
79 | { | |
80 | rtx reg; /* The register referenced. */ | |
10c4b247 | 81 | rtx insn; /* Insn containing ref. */ |
7890e8f3 | 82 | rtx *loc; /* The location of the reg. */ |
10c4b247 | 83 | struct df_link *chain; /* Head of def-use or use-def chain. */ |
ed8d2920 | 84 | unsigned int id; /* Ref index. */ |
7890e8f3 | 85 | enum df_ref_type type; /* Type of ref. */ |
7fcd7218 | 86 | enum df_ref_flags flags; /* Various flags. */ |
10c4b247 JL |
87 | }; |
88 | ||
89 | ||
90 | /* One of these structures is allocated for every insn. */ | |
91 | struct insn_info | |
92 | { | |
93 | struct df_link *defs; /* Head of insn-def chain. */ | |
94 | struct df_link *uses; /* Head of insn-use chain. */ | |
7890e8f3 | 95 | /* ???? The following luid field should be considerd private so that |
f63d1bf7 | 96 | we can change it on the fly to accommodate new insns? */ |
10c4b247 | 97 | int luid; /* Logical UID. */ |
10c4b247 JL |
98 | }; |
99 | ||
100 | ||
101 | /* One of these structures is allocated for every reg. */ | |
102 | struct reg_info | |
103 | { | |
104 | struct df_link *defs; /* Head of reg-def chain. */ | |
105 | struct df_link *uses; /* Head of reg-use chain. */ | |
106 | int lifetime; | |
107 | int n_defs; | |
108 | int n_uses; | |
109 | }; | |
110 | ||
111 | ||
112 | /* One of these structures is allocated for every basic block. */ | |
113 | struct bb_info | |
114 | { | |
115 | /* Reaching def bitmaps have def_id elements. */ | |
116 | bitmap rd_kill; | |
117 | bitmap rd_gen; | |
118 | bitmap rd_in; | |
119 | bitmap rd_out; | |
120 | /* Reaching use bitmaps have use_id elements. */ | |
121 | bitmap ru_kill; | |
122 | bitmap ru_gen; | |
123 | bitmap ru_in; | |
124 | bitmap ru_out; | |
125 | /* Live variable bitmaps have n_regs elements. */ | |
126 | bitmap lr_def; | |
127 | bitmap lr_use; | |
128 | bitmap lr_in; | |
129 | bitmap lr_out; | |
130 | int rd_valid; | |
131 | int ru_valid; | |
132 | int lr_valid; | |
133 | }; | |
134 | ||
135 | ||
136 | struct df | |
137 | { | |
138 | int flags; /* Indicates what's recorded. */ | |
139 | struct bb_info *bbs; /* Basic block table. */ | |
140 | struct ref **defs; /* Def table, indexed by def_id. */ | |
141 | struct ref **uses; /* Use table, indexed by use_id. */ | |
142 | struct ref **reg_def_last; /* Indexed by regno. */ | |
143 | struct reg_info *regs; /* Regs table, index by regno. */ | |
144 | unsigned int reg_size; /* Size of regs table. */ | |
145 | struct insn_info *insns; /* Insn table, indexed by insn UID. */ | |
146 | unsigned int insn_size; /* Size of insn table. */ | |
147 | unsigned int def_id; /* Next def ID. */ | |
148 | unsigned int def_size; /* Size of def table. */ | |
149 | unsigned int n_defs; /* Size of def bitmaps. */ | |
150 | unsigned int use_id; /* Next use ID. */ | |
151 | unsigned int use_size; /* Size of use table. */ | |
152 | unsigned int n_uses; /* Size of use bitmaps. */ | |
153 | unsigned int n_bbs; /* Number of basic blocks. */ | |
154 | unsigned int n_regs; /* Number of regs. */ | |
155 | unsigned int def_id_save; /* Saved next def ID. */ | |
156 | unsigned int use_id_save; /* Saved next use ID. */ | |
157 | bitmap insns_modified; /* Insns that (may) have changed. */ | |
158 | bitmap bbs_modified; /* Blocks that (may) have changed. */ | |
159 | bitmap all_blocks; /* All blocks in CFG. */ | |
2a6f0eca | 160 | /* The sbitmap vector of dominators or NULL if not computed. |
10c4b247 | 161 | Ideally, this should be a pointer to a CFG object. */ |
2a6f0eca | 162 | sbitmap *dom; |
7890e8f3 MH |
163 | int *dfs_order; /* DFS order -> block number. */ |
164 | int *rc_order; /* Reverse completion order -> block number. */ | |
165 | int *rts_order; /* Reverse top sort order -> block number. */ | |
166 | int *inverse_rc_map; /* Block number -> reverse completion order. */ | |
167 | int *inverse_dfs_map; /* Block number -> DFS order. */ | |
168 | int *inverse_rts_map; /* Block number -> reverse top-sort order. */ | |
10c4b247 JL |
169 | }; |
170 | ||
171 | ||
172 | struct df_map | |
173 | { | |
174 | rtx old; | |
175 | rtx new; | |
176 | }; | |
177 | ||
178 | ||
0b17ab2f | 179 | #define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index]) |
10c4b247 JL |
180 | |
181 | ||
182 | /* Macros to access the elements within the ref structure. */ | |
7890e8f3 | 183 | |
10c4b247 JL |
184 | #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \ |
185 | ? SUBREG_REG ((REF)->reg) : ((REF)->reg)) | |
186 | #define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF)) | |
187 | #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \ | |
188 | ? &SUBREG_REG ((REF)->reg) : ((REF)->loc)) | |
10c4b247 JL |
189 | #define DF_REF_REG(REF) ((REF)->reg) |
190 | #define DF_REF_LOC(REF) ((REF)->loc) | |
5a133afd | 191 | #define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn)) |
0b17ab2f | 192 | #define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index) |
10c4b247 JL |
193 | #define DF_REF_INSN(REF) ((REF)->insn) |
194 | #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn)) | |
195 | #define DF_REF_TYPE(REF) ((REF)->type) | |
196 | #define DF_REF_CHAIN(REF) ((REF)->chain) | |
197 | #define DF_REF_ID(REF) ((REF)->id) | |
7fcd7218 | 198 | #define DF_REF_FLAGS(REF) ((REF)->flags) |
10c4b247 JL |
199 | |
200 | /* Macros to determine the reference type. */ | |
201 | ||
202 | #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF) | |
203 | #define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF)) | |
204 | #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE) | |
205 | #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD) | |
206 | #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \ | |
7890e8f3 | 207 | || DF_REF_REG_MEM_LOAD_P (REF)) |
10c4b247 JL |
208 | |
209 | ||
210 | /* Macros to access the elements within the reg_info structure table. */ | |
211 | ||
212 | #define DF_REGNO_FIRST_DEF(DF, REGNUM) \ | |
213 | ((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0) | |
214 | #define DF_REGNO_LAST_USE(DF, REGNUM) \ | |
215 | ((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0) | |
216 | ||
217 | #define DF_REGNO_FIRST_BB(DF, REGNUM) \ | |
218 | (DF_REGNO_FIRST_DEF (DF, REGNUM) \ | |
219 | ? DF_REF_BB (DF_REGNO_FIRST_DEF (DF, REGNUM)) : 0) | |
220 | #define DF_REGNO_LAST_BB(DF, REGNUM) \ | |
221 | (DF_REGNO_LAST_USE (DF, REGNUM) \ | |
222 | ? DF_REF_BB (DF_REGNO_LAST_USE (DF, REGNUM)) : 0) | |
223 | ||
224 | ||
225 | /* Macros to access the elements within the insn_info structure table. */ | |
226 | ||
227 | #define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid) | |
228 | #define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs) | |
229 | #define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses) | |
230 | ||
231 | ||
232 | /* Functions to build and analyse dataflow information. */ | |
233 | ||
234 | extern struct df *df_init PARAMS ((void)); | |
235 | ||
236 | extern int df_analyse PARAMS ((struct df *, bitmap, int)); | |
237 | ||
238 | extern void df_finish PARAMS ((struct df *)); | |
239 | ||
240 | extern void df_dump PARAMS ((struct df *, int, FILE *)); | |
241 | ||
7890e8f3 | 242 | |
10c4b247 JL |
243 | /* Functions to modify insns. */ |
244 | ||
245 | extern void df_insn_modify PARAMS ((struct df *, basic_block, rtx)); | |
246 | ||
247 | extern rtx df_insn_delete PARAMS ((struct df *, basic_block, rtx)); | |
248 | ||
249 | extern rtx df_pattern_emit_before PARAMS ((struct df *, rtx, | |
250 | basic_block, rtx)); | |
251 | ||
252 | extern rtx df_jump_pattern_emit_after PARAMS ((struct df *, rtx, | |
253 | basic_block, rtx)); | |
254 | ||
255 | extern rtx df_pattern_emit_after PARAMS ((struct df *, rtx, | |
7890e8f3 | 256 | basic_block, rtx)); |
10c4b247 JL |
257 | |
258 | extern rtx df_insn_move_before PARAMS ((struct df *, basic_block, rtx, | |
259 | basic_block, rtx)); | |
260 | ||
261 | extern int df_reg_replace PARAMS ((struct df *, bitmap, rtx, rtx)); | |
262 | ||
263 | extern int df_ref_reg_replace PARAMS ((struct df *, struct ref *, rtx, rtx)); | |
264 | ||
265 | extern int df_ref_remove PARAMS ((struct df *, struct ref *)); | |
266 | ||
267 | extern int df_insn_reg_replace PARAMS ((struct df *, basic_block, | |
268 | rtx, rtx, rtx)); | |
269 | ||
270 | extern int df_insn_mem_replace PARAMS ((struct df *, basic_block, | |
271 | rtx, rtx, rtx)); | |
272 | ||
273 | extern struct ref *df_bb_def_use_swap PARAMS ((struct df *, basic_block, | |
274 | rtx, rtx, unsigned int)); | |
275 | ||
276 | ||
277 | /* Functions to query dataflow information. */ | |
278 | ||
279 | extern basic_block df_regno_bb PARAMS((struct df *, unsigned int)); | |
280 | ||
281 | extern int df_reg_lifetime PARAMS ((struct df *, rtx)); | |
282 | ||
283 | extern int df_reg_global_p PARAMS ((struct df *, rtx)); | |
284 | ||
285 | extern int df_insn_regno_def_p PARAMS ((struct df *, | |
286 | basic_block, rtx, unsigned int)); | |
287 | ||
288 | extern int df_insn_dominates_all_uses_p PARAMS ((struct df *, | |
289 | basic_block, rtx)); | |
290 | ||
291 | extern int df_insn_dominates_uses_p PARAMS ((struct df *, basic_block, | |
292 | rtx, bitmap)); | |
293 | ||
294 | extern int df_bb_reg_live_start_p PARAMS ((struct df *, basic_block, rtx)); | |
295 | ||
296 | extern int df_bb_reg_live_end_p PARAMS ((struct df *, basic_block, rtx)); | |
297 | ||
298 | extern int df_bb_regs_lives_compare PARAMS ((struct df *, basic_block, | |
299 | rtx, rtx)); | |
300 | ||
301 | extern rtx df_bb_single_def_use_insn_find PARAMS((struct df *, basic_block, | |
302 | rtx, rtx)); | |
303 | ||
304 | ||
305 | /* Functions for debugging from GDB. */ | |
306 | ||
307 | extern void debug_df_insn PARAMS ((rtx)); | |
308 | ||
309 | extern void debug_df_regno PARAMS ((unsigned int)); | |
310 | ||
311 | extern void debug_df_reg PARAMS ((rtx)); | |
312 | ||
313 | extern void debug_df_defno PARAMS ((unsigned int)); | |
314 | ||
315 | extern void debug_df_useno PARAMS ((unsigned int)); | |
316 | ||
317 | extern void debug_df_ref PARAMS ((struct ref *)); | |
318 | ||
319 | extern void debug_df_chain PARAMS ((struct df_link *)); | |
7890e8f3 | 320 | |
10c4b247 | 321 | extern void df_insn_debug PARAMS ((struct df *, rtx, FILE *)); |
7890e8f3 | 322 | |
10c4b247 | 323 | extern void df_insn_debug_regno PARAMS ((struct df *, rtx, FILE *)); |
7890e8f3 MH |
324 | |
325 | ||
326 | /* Meet over any path (UNION) or meet over all paths (INTERSECTION). */ | |
2a6f0eca DB |
327 | enum df_confluence_op |
328 | { | |
7890e8f3 MH |
329 | DF_UNION, |
330 | DF_INTERSECTION | |
2a6f0eca | 331 | }; |
7890e8f3 MH |
332 | |
333 | ||
334 | /* Dataflow direction. */ | |
2a6f0eca DB |
335 | enum df_flow_dir |
336 | { | |
7890e8f3 MH |
337 | DF_FORWARD, |
338 | DF_BACKWARD | |
2a6f0eca DB |
339 | }; |
340 | ||
7890e8f3 | 341 | |
afb14002 | 342 | typedef void (*transfer_function_sbitmap) PARAMS ((int, int *, sbitmap, sbitmap, |
7890e8f3 MH |
343 | sbitmap, sbitmap, void *)); |
344 | ||
afb14002 | 345 | typedef void (*transfer_function_bitmap) PARAMS ((int, int *, bitmap, bitmap, |
7890e8f3 | 346 | bitmap, bitmap, void *)); |
2a6f0eca DB |
347 | |
348 | extern void iterative_dataflow_sbitmap PARAMS ((sbitmap *, sbitmap *, | |
349 | sbitmap *, sbitmap *, | |
350 | bitmap, enum df_flow_dir, | |
351 | enum df_confluence_op, | |
352 | transfer_function_sbitmap, | |
353 | int *, void *)); | |
7890e8f3 | 354 | |
2a6f0eca DB |
355 | extern void iterative_dataflow_bitmap PARAMS ((bitmap *, bitmap *, bitmap *, |
356 | bitmap *, bitmap, | |
357 | enum df_flow_dir, | |
358 | enum df_confluence_op, | |
359 | transfer_function_bitmap, | |
360 | int *, void *)); | |
37bd08f8 | 361 | extern bool read_modify_subreg_p PARAMS ((rtx)); |