]>
Commit | Line | Data |
---|---|---|
10c4b247 | 1 | /* Form lists of pseudo register references for autoinc optimization |
7080f735 | 2 | for GNU compiler. This is part of flow optimization. |
7c028163 AO |
3 | Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, |
4 | 2009, 2010 Free Software Foundation, Inc. | |
b8698a0f | 5 | Originally contributed by Michael P. Hayes |
4d779342 DB |
6 | (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) |
7 | Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) | |
8 | and Kenneth Zadeck (zadeck@naturalbridge.com). | |
10c4b247 | 9 | |
1322177d | 10 | This file is part of GCC. |
10c4b247 | 11 | |
1322177d LB |
12 | GCC is free software; you can redistribute it and/or modify it under |
13 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 14 | Software Foundation; either version 3, or (at your option) any later |
1322177d | 15 | version. |
10c4b247 | 16 | |
1322177d LB |
17 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
18 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
19 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
20 | for more details. | |
10c4b247 JL |
21 | |
22 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
23 | along with GCC; see the file COPYING3. If not see |
24 | <http://www.gnu.org/licenses/>. */ | |
10c4b247 | 25 | |
59587b18 JQ |
26 | #ifndef GCC_DF_H |
27 | #define GCC_DF_H | |
28 | ||
29 | #include "bitmap.h" | |
7a8cba34 SB |
30 | #include "regset.h" |
31 | #include "sbitmap.h" | |
59587b18 | 32 | #include "basic-block.h" |
4d779342 | 33 | #include "alloc-pool.h" |
7072a650 | 34 | #include "timevar.h" |
4d779342 DB |
35 | |
36 | struct dataflow; | |
37 | struct df; | |
38 | struct df_problem; | |
23249ac4 | 39 | struct df_link; |
57512f53 KZ |
40 | struct df_insn_info; |
41 | union df_ref_d; | |
4d779342 | 42 | |
b8698a0f | 43 | /* Data flow problems. All problems must have a unique id here. */ |
05c219bb | 44 | |
4d779342 DB |
45 | /* Scanning is not really a dataflow problem, but it is useful to have |
46 | the basic block functions in the vector so that things get done in | |
05c219bb PB |
47 | a uniform manner. The last four problems can be added or deleted |
48 | at any time are always defined (though LIVE is always there at -O2 | |
49 | or higher); the others are always there. */ | |
b8698a0f | 50 | #define DF_SCAN 0 |
cc806ac1 RS |
51 | #define DF_LR 1 /* Live Registers backward. */ |
52 | #define DF_LIVE 2 /* Live Registers & Uninitialized Registers */ | |
53 | #define DF_RD 3 /* Reaching Defs. */ | |
54 | #define DF_CHAIN 4 /* Def-Use and/or Use-Def Chains. */ | |
55 | #define DF_BYTE_LR 5 /* Subreg tracking lr. */ | |
56 | #define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */ | |
c6741572 | 57 | #define DF_MD 7 /* Multiple Definitions. */ |
4d779342 | 58 | |
c6741572 | 59 | #define DF_LAST_PROBLEM_PLUS1 (DF_MD + 1) |
10c4b247 | 60 | |
4d779342 DB |
61 | /* Dataflow direction. */ |
62 | enum df_flow_dir | |
63 | { | |
64 | DF_NONE, | |
65 | DF_FORWARD, | |
66 | DF_BACKWARD | |
67 | }; | |
10c4b247 | 68 | |
cc806ac1 RS |
69 | /* Used in the byte scanning to determine if may or must info is to be |
70 | returned. */ | |
71 | enum df_mm | |
72 | { | |
73 | DF_MM_MAY, | |
74 | DF_MM_MUST | |
75 | }; | |
23249ac4 | 76 | |
57512f53 KZ |
77 | /* Descriminator for the various df_ref types. */ |
78 | enum df_ref_class {DF_REF_BASE, DF_REF_ARTIFICIAL, DF_REF_REGULAR, DF_REF_EXTRACT}; | |
23249ac4 | 79 | |
57512f53 KZ |
80 | /* The first of these us a set of a registers. The remaining three |
81 | are all uses of a register (the mem_load and mem_store relate to | |
82 | how the register as an addressing operand). */ | |
83 | enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, | |
84 | DF_REF_REG_MEM_LOAD, DF_REF_REG_MEM_STORE}; | |
23249ac4 DB |
85 | |
86 | enum df_ref_flags | |
87 | { | |
ba49cb7b KZ |
88 | /* This flag is set if this ref occurs inside of a conditional |
89 | execution instruction. */ | |
90 | DF_REF_CONDITIONAL = 1 << 0, | |
23249ac4 DB |
91 | |
92 | /* If this flag is set for an artificial use or def, that ref | |
93 | logically happens at the top of the block. If it is not set | |
94 | for an artificial use or def, that ref logically happens at the | |
95 | bottom of the block. This is never set for regular refs. */ | |
6fb5fa3c | 96 | DF_REF_AT_TOP = 1 << 1, |
23249ac4 | 97 | |
6fb5fa3c DB |
98 | /* This flag is set if the use is inside a REG_EQUAL or REG_EQUIV |
99 | note. */ | |
100 | DF_REF_IN_NOTE = 1 << 2, | |
23249ac4 | 101 | |
ba49cb7b KZ |
102 | /* This bit is true if this ref can make regs_ever_live true for |
103 | this regno. */ | |
104 | DF_HARD_REG_LIVE = 1 << 3, | |
105 | ||
106 | ||
107 | /* This flag is set if this ref is a partial use or def of the | |
108 | associated register. */ | |
109 | DF_REF_PARTIAL = 1 << 4, | |
b8698a0f | 110 | |
ba49cb7b KZ |
111 | /* Read-modify-write refs generate both a use and a def and |
112 | these are marked with this flag to show that they are not | |
113 | independent. */ | |
114 | DF_REF_READ_WRITE = 1 << 5, | |
115 | ||
23249ac4 DB |
116 | /* This flag is set if this ref, generally a def, may clobber the |
117 | referenced register. This is generally only set for hard | |
118 | registers that cross a call site. With better information | |
119 | about calls, some of these could be changed in the future to | |
120 | DF_REF_MUST_CLOBBER. */ | |
ba49cb7b | 121 | DF_REF_MAY_CLOBBER = 1 << 6, |
23249ac4 DB |
122 | |
123 | /* This flag is set if this ref, generally a def, is a real | |
124 | clobber. This is not currently set for registers live across a | |
b8698a0f | 125 | call because that clobbering may or may not happen. |
23249ac4 DB |
126 | |
127 | Most of the uses of this are with sets that have a | |
128 | GET_CODE(..)==CLOBBER. Note that this is set even if the | |
129 | clobber is to a subreg. So in order to tell if the clobber | |
130 | wipes out the entire register, it is necessary to also check | |
131 | the DF_REF_PARTIAL flag. */ | |
ba49cb7b | 132 | DF_REF_MUST_CLOBBER = 1 << 7, |
23249ac4 | 133 | |
23249ac4 | 134 | |
ca9052ce KZ |
135 | /* If the ref has one of the following two flags set, then the |
136 | struct df_ref can be cast to struct df_ref_extract to access | |
137 | the width and offset fields. */ | |
b8698a0f | 138 | |
ca9052ce KZ |
139 | /* This flag is set if the ref contains a SIGN_EXTRACT. */ |
140 | DF_REF_SIGN_EXTRACT = 1 << 8, | |
6fb5fa3c | 141 | |
ca9052ce KZ |
142 | /* This flag is set if the ref contains a ZERO_EXTRACT. */ |
143 | DF_REF_ZERO_EXTRACT = 1 << 9, | |
6fb5fa3c | 144 | |
ca9052ce KZ |
145 | /* This flag is set if the ref contains a STRICT_LOW_PART. */ |
146 | DF_REF_STRICT_LOW_PART = 1 << 10, | |
6fb5fa3c | 147 | |
ba49cb7b KZ |
148 | /* This flag is set if the ref contains a SUBREG. */ |
149 | DF_REF_SUBREG = 1 << 11, | |
150 | ||
151 | ||
152 | /* This bit is true if this ref is part of a multiword hardreg. */ | |
153 | DF_REF_MW_HARDREG = 1 << 12, | |
6fb5fa3c DB |
154 | |
155 | /* This flag is set if this ref is a usage of the stack pointer by | |
156 | a function call. */ | |
ba49cb7b | 157 | DF_REF_CALL_STACK_USAGE = 1 << 13, |
6fb5fa3c DB |
158 | |
159 | /* This flag is used for verification of existing refs. */ | |
ca9052ce KZ |
160 | DF_REF_REG_MARKER = 1 << 14, |
161 | ||
162 | /* This flag is set if this ref is inside a pre/post modify. */ | |
163 | DF_REF_PRE_POST_MODIFY = 1 << 15 | |
164 | ||
23249ac4 DB |
165 | }; |
166 | ||
6fb5fa3c DB |
167 | /* The possible ordering of refs within the df_ref_info. */ |
168 | enum df_ref_order | |
169 | { | |
b8698a0f | 170 | /* There is not table. */ |
6fb5fa3c DB |
171 | DF_REF_ORDER_NO_TABLE, |
172 | ||
173 | /* There is a table of refs but it is not (or no longer) organized | |
174 | by one of the following methods. */ | |
175 | DF_REF_ORDER_UNORDERED, | |
176 | DF_REF_ORDER_UNORDERED_WITH_NOTES, | |
b8698a0f | 177 | |
6fb5fa3c DB |
178 | /* Organize the table by reg order, all of the refs with regno 0 |
179 | followed by all of the refs with regno 1 ... . Within all of | |
180 | the regs for a particular regno, the refs are unordered. */ | |
181 | DF_REF_ORDER_BY_REG, | |
182 | ||
183 | /* For uses, the refs within eq notes may be added for | |
184 | DF_REF_ORDER_BY_REG. */ | |
185 | DF_REF_ORDER_BY_REG_WITH_NOTES, | |
186 | ||
187 | /* Organize the refs in insn order. The insns are ordered within a | |
b8698a0f | 188 | block, and the blocks are ordered by FOR_ALL_BB. */ |
6fb5fa3c DB |
189 | DF_REF_ORDER_BY_INSN, |
190 | ||
191 | /* For uses, the refs within eq notes may be added for | |
192 | DF_REF_ORDER_BY_INSN. */ | |
193 | DF_REF_ORDER_BY_INSN_WITH_NOTES | |
194 | }; | |
23249ac4 | 195 | |
4d779342 | 196 | /* Function prototypes added to df_problem instance. */ |
10c4b247 | 197 | |
4d779342 | 198 | /* Allocate the problem specific data. */ |
6fb5fa3c | 199 | typedef void (*df_alloc_function) (bitmap); |
4d779342 | 200 | |
30cb87a0 KZ |
201 | /* This function is called if the problem has global data that needs |
202 | to be cleared when ever the set of blocks changes. The bitmap | |
203 | contains the set of blocks that may require special attention. | |
204 | This call is only made if some of the blocks are going to change. | |
205 | If everything is to be deleted, the wholesale deletion mechanisms | |
206 | apply. */ | |
6fb5fa3c | 207 | typedef void (*df_reset_function) (bitmap); |
30cb87a0 | 208 | |
4d779342 DB |
209 | /* Free the basic block info. Called from the block reordering code |
210 | to get rid of the blocks that have been squished down. */ | |
6fb5fa3c | 211 | typedef void (*df_free_bb_function) (basic_block, void *); |
4d779342 DB |
212 | |
213 | /* Local compute function. */ | |
6fb5fa3c | 214 | typedef void (*df_local_compute_function) (bitmap); |
4d779342 DB |
215 | |
216 | /* Init the solution specific data. */ | |
6fb5fa3c | 217 | typedef void (*df_init_function) (bitmap); |
4d779342 DB |
218 | |
219 | /* Iterative dataflow function. */ | |
6fb5fa3c | 220 | typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int); |
4d779342 DB |
221 | |
222 | /* Confluence operator for blocks with 0 out (or in) edges. */ | |
6fb5fa3c | 223 | typedef void (*df_confluence_function_0) (basic_block); |
4d779342 DB |
224 | |
225 | /* Confluence operator for blocks with 1 or more out (or in) edges. */ | |
6fb5fa3c | 226 | typedef void (*df_confluence_function_n) (edge); |
4d779342 DB |
227 | |
228 | /* Transfer function for blocks. */ | |
6fb5fa3c | 229 | typedef bool (*df_transfer_function) (int); |
4d779342 DB |
230 | |
231 | /* Function to massage the information after the problem solving. */ | |
6fb5fa3c | 232 | typedef void (*df_finalizer_function) (bitmap); |
4d779342 DB |
233 | |
234 | /* Function to free all of the problem specific datastructures. */ | |
6fb5fa3c DB |
235 | typedef void (*df_free_function) (void); |
236 | ||
237 | /* Function to remove this problem from the stack of dataflow problems | |
238 | without effecting the other problems in the stack except for those | |
239 | that depend on this problem. */ | |
240 | typedef void (*df_remove_problem_function) (void); | |
241 | ||
242 | /* Function to dump basic block independent results to FILE. */ | |
243 | typedef void (*df_dump_problem_function) (FILE *); | |
4d779342 | 244 | |
6fb5fa3c DB |
245 | /* Function to dump top or bottom of basic block results to FILE. */ |
246 | typedef void (*df_dump_bb_problem_function) (basic_block, FILE *); | |
4d779342 | 247 | |
6fb5fa3c DB |
248 | /* Function to dump top or bottom of basic block results to FILE. */ |
249 | typedef void (*df_verify_solution_start) (void); | |
250 | ||
251 | /* Function to dump top or bottom of basic block results to FILE. */ | |
252 | typedef void (*df_verify_solution_end) (void); | |
23249ac4 | 253 | |
4d779342 DB |
254 | /* The static description of a dataflow problem to solve. See above |
255 | typedefs for doc for the function fields. */ | |
256 | ||
257 | struct df_problem { | |
258 | /* The unique id of the problem. This is used it index into | |
259 | df->defined_problems to make accessing the problem data easy. */ | |
b8698a0f | 260 | unsigned int id; |
4d779342 DB |
261 | enum df_flow_dir dir; /* Dataflow direction. */ |
262 | df_alloc_function alloc_fun; | |
30cb87a0 | 263 | df_reset_function reset_fun; |
4d779342 DB |
264 | df_free_bb_function free_bb_fun; |
265 | df_local_compute_function local_compute_fun; | |
266 | df_init_function init_fun; | |
267 | df_dataflow_function dataflow_fun; | |
268 | df_confluence_function_0 con_fun_0; | |
269 | df_confluence_function_n con_fun_n; | |
270 | df_transfer_function trans_fun; | |
271 | df_finalizer_function finalize_fun; | |
272 | df_free_function free_fun; | |
6fb5fa3c DB |
273 | df_remove_problem_function remove_problem_fun; |
274 | df_dump_problem_function dump_start_fun; | |
275 | df_dump_bb_problem_function dump_top_fun; | |
276 | df_dump_bb_problem_function dump_bottom_fun; | |
277 | df_verify_solution_start verify_start_fun; | |
278 | df_verify_solution_end verify_end_fun; | |
279 | struct df_problem *dependent_problem; | |
89a95777 | 280 | |
6fb5fa3c | 281 | /* The timevar id associated with this pass. */ |
7072a650 | 282 | timevar_id_t tv_id; |
89a95777 KZ |
283 | |
284 | /* True if the df_set_blocks should null out the basic block info if | |
285 | this block drops out of df->blocks_to_analyze. */ | |
286 | bool free_blocks_on_set_blocks; | |
4d779342 DB |
287 | }; |
288 | ||
289 | ||
290 | /* The specific instance of the problem to solve. */ | |
291 | struct dataflow | |
10c4b247 | 292 | { |
4d779342 DB |
293 | struct df_problem *problem; /* The problem to be solved. */ |
294 | ||
4d779342 DB |
295 | /* Array indexed by bb->index, that contains basic block problem and |
296 | solution specific information. */ | |
297 | void **block_info; | |
298 | unsigned int block_info_size; | |
299 | ||
300 | /* The pool to allocate the block_info from. */ | |
b8698a0f | 301 | alloc_pool block_pool; |
4d779342 | 302 | |
6fb5fa3c DB |
303 | /* The lr and live problems have their transfer functions recomputed |
304 | only if necessary. This is possible for them because, the | |
305 | problems are kept active for the entire backend and their | |
306 | transfer functions are indexed by the REGNO. These are not | |
307 | defined for any other problem. */ | |
308 | bitmap out_of_date_transfer_functions; | |
23249ac4 | 309 | |
4d779342 DB |
310 | /* Other problem specific data that is not on a per basic block |
311 | basis. The structure is generally defined privately for the | |
312 | problem. The exception being the scanning problem where it is | |
313 | fully public. */ | |
6fb5fa3c DB |
314 | void *problem_data; |
315 | ||
316 | /* Local flags for some of the problems. */ | |
317 | unsigned int local_flags; | |
b8698a0f | 318 | |
6fb5fa3c DB |
319 | /* True if this problem of this instance has been initialized. This |
320 | is used by the dumpers to keep garbage out of the dumps if, for | |
321 | debugging a dump is produced before the first call to | |
322 | df_analyze after a new problem is added. */ | |
323 | bool computed; | |
324 | ||
325 | /* True if the something has changed which invalidates the dataflow | |
b8698a0f | 326 | solutions. Note that this bit is always true for all problems except |
6fb5fa3c DB |
327 | lr and live. */ |
328 | bool solutions_dirty; | |
89a95777 KZ |
329 | |
330 | /* If true, this pass is deleted by df_finish_pass. This is never | |
331 | true for DF_SCAN and DF_LR. It is true for DF_LIVE if optimize > | |
332 | 1. It is always true for the other problems. */ | |
333 | bool optional_p; | |
10c4b247 JL |
334 | }; |
335 | ||
23249ac4 DB |
336 | |
337 | /* The set of multiword hardregs used as operands to this | |
338 | instruction. These are factored into individual uses and defs but | |
339 | the aggregate is still needed to service the REG_DEAD and | |
340 | REG_UNUSED notes. */ | |
341 | struct df_mw_hardreg | |
342 | { | |
b8698a0f | 343 | rtx mw_reg; /* The multiword hardreg. */ |
cea618ac | 344 | /* These two bitfields are intentionally oversized, in the hope that |
ab34041d RS |
345 | accesses to 16-bit fields will usually be quicker. */ |
346 | ENUM_BITFIELD(df_ref_type) type : 16; | |
347 | /* Used to see if the ref is read or write. */ | |
32e8bb8e | 348 | int flags : 16; /* Various df_ref_flags. */ |
6fb5fa3c DB |
349 | unsigned int start_regno; /* First word of the multi word subreg. */ |
350 | unsigned int end_regno; /* Last word of the multi word subreg. */ | |
351 | unsigned int mw_order; /* Same as df_ref.ref_order. */ | |
23249ac4 | 352 | }; |
b8698a0f | 353 | |
23249ac4 | 354 | |
7890e8f3 | 355 | /* Define a register reference structure. One of these is allocated |
57512f53 KZ |
356 | for every register reference (use or def). Note some register |
357 | references (e.g., post_inc, subreg) generate both a def and a use. */ | |
358 | struct df_base_ref | |
10c4b247 | 359 | { |
57512f53 KZ |
360 | /* These three bitfields are intentionally oversized, in the hope that |
361 | accesses to 8 and 16-bit fields will usually be quicker. */ | |
362 | ENUM_BITFIELD(df_ref_class) cl : 8; | |
50e94c7e | 363 | |
57512f53 KZ |
364 | ENUM_BITFIELD(df_ref_type) type : 8; |
365 | /* Type of ref. */ | |
32e8bb8e | 366 | int flags : 16; /* Various df_ref_flags. */ |
57512f53 | 367 | rtx reg; /* The register referenced. */ |
30cb87a0 | 368 | struct df_link *chain; /* Head of def-use, use-def. */ |
b8698a0f | 369 | /* Pointer to the insn info of the containing instruction. FIXME! |
57512f53 | 370 | Currently this is NULL for artificial refs but this will be used |
b8698a0f | 371 | when FUDs are added. */ |
57512f53 KZ |
372 | struct df_insn_info *insn_info; |
373 | /* For each regno, there are three chains of refs, one for the uses, | |
374 | the eq_uses and the defs. These chains go thru the refs | |
375 | themselves rather than using an external structure. */ | |
376 | union df_ref_d *next_reg; /* Next ref with same regno and type. */ | |
377 | union df_ref_d *prev_reg; /* Prev ref with same regno and type. */ | |
378 | unsigned int regno; /* The register number referenced. */ | |
b8698a0f | 379 | /* Location in the ref table. This is only valid after a call to |
6fb5fa3c DB |
380 | df_maybe_reorganize_[use,def]_refs which is an expensive operation. */ |
381 | int id; | |
382 | /* The index at which the operand was scanned in the insn. This is | |
383 | used to totally order the refs in an insn. */ | |
384 | unsigned int ref_order; | |
57512f53 | 385 | }; |
6fb5fa3c | 386 | |
10c4b247 | 387 | |
57512f53 | 388 | /* The three types of df_refs. Note that the df_ref_extract is an |
b8698a0f | 389 | extension of the df_regular_ref, not the df_base_ref. */ |
57512f53 KZ |
390 | struct df_artificial_ref |
391 | { | |
392 | struct df_base_ref base; | |
393 | ||
394 | /* Artificial refs do not have an insn, so to get the basic block, | |
395 | it must be explicitly here. */ | |
396 | basic_block bb; | |
397 | }; | |
398 | ||
399 | ||
400 | struct df_regular_ref | |
401 | { | |
402 | struct df_base_ref base; | |
403 | /* The loc is the address in the insn of the reg. This is not | |
404 | defined for special registers, such as clobbers and stack | |
405 | pointers that are also associated with call insns and so those | |
406 | just use the base. */ | |
407 | rtx *loc; | |
10c4b247 JL |
408 | }; |
409 | ||
57512f53 | 410 | |
ca9052ce KZ |
411 | /* A df_ref_extract is just a df_ref with a width and offset field at |
412 | the end of it. It is used to hold this information if the ref was | |
413 | wrapped by a SIGN_EXTRACT or a ZERO_EXTRACT and to pass this info | |
414 | to passes that wish to process partial regs precisely. */ | |
57512f53 | 415 | struct df_extract_ref |
ca9052ce | 416 | { |
57512f53 | 417 | struct df_regular_ref base; |
ca9052ce KZ |
418 | int width; |
419 | int offset; | |
cc806ac1 | 420 | enum machine_mode mode; |
ca9052ce KZ |
421 | }; |
422 | ||
57512f53 KZ |
423 | /* Union of the different kinds of defs/uses placeholders. */ |
424 | union df_ref_d | |
425 | { | |
426 | struct df_base_ref base; | |
427 | struct df_regular_ref regular_ref; | |
428 | struct df_artificial_ref artificial_ref; | |
429 | struct df_extract_ref extract_ref; | |
430 | }; | |
431 | typedef union df_ref_d *df_ref; | |
432 | ||
433 | ||
434 | /* One of these structures is allocated for every insn. */ | |
435 | struct df_insn_info | |
436 | { | |
437 | rtx insn; /* The insn this info comes from. */ | |
438 | df_ref *defs; /* Head of insn-def chain. */ | |
439 | df_ref *uses; /* Head of insn-use chain. */ | |
440 | /* Head of insn-use chain for uses in REG_EQUAL/EQUIV notes. */ | |
b8698a0f | 441 | df_ref *eq_uses; |
57512f53 KZ |
442 | struct df_mw_hardreg **mw_hardregs; |
443 | /* The logical uid of the insn in the basic block. This is valid | |
444 | after any call to df_analyze but may rot after insns are added, | |
445 | deleted or moved. */ | |
b8698a0f | 446 | int luid; |
57512f53 | 447 | }; |
b8698a0f | 448 | |
fed6152d SB |
449 | /* These links are used for ref-ref chains. Currently only DEF-USE and |
450 | USE-DEF chains can be built by DF. */ | |
4d779342 | 451 | struct df_link |
10c4b247 | 452 | { |
57512f53 | 453 | df_ref ref; |
4d779342 | 454 | struct df_link *next; |
10c4b247 JL |
455 | }; |
456 | ||
6fb5fa3c DB |
457 | \f |
458 | enum df_chain_flags | |
459 | { | |
460 | /* Flags that control the building of chains. */ | |
b8698a0f | 461 | DF_DU_CHAIN = 1, /* Build DU chains. */ |
6fb5fa3c DB |
462 | DF_UD_CHAIN = 2 /* Build UD chains. */ |
463 | }; | |
464 | ||
b8698a0f | 465 | enum df_changeable_flags |
6fb5fa3c DB |
466 | { |
467 | /* Scanning flags. */ | |
468 | /* Flag to control the running of dce as a side effect of building LR. */ | |
2b49e1a0 KZ |
469 | DF_LR_RUN_DCE = 1 << 0, /* Run DCE. */ |
470 | DF_NO_HARD_REGS = 1 << 1, /* Skip hard registers in RD and CHAIN Building. */ | |
471 | ||
963acd6f KZ |
472 | DF_EQ_NOTES = 1 << 2, /* Build chains with uses present in EQUIV/EQUAL notes. */ |
473 | DF_NO_REGS_EVER_LIVE = 1 << 3, /* Do not compute the regs_ever_live. */ | |
6fb5fa3c DB |
474 | |
475 | /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to | |
476 | return immediately. This is used by passes that know how to update | |
477 | the scanning them selves. */ | |
963acd6f | 478 | DF_NO_INSN_RESCAN = 1 << 4, |
6fb5fa3c DB |
479 | |
480 | /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to | |
481 | return after marking the insn for later processing. This allows all | |
482 | rescans to be batched. */ | |
963acd6f | 483 | DF_DEFER_INSN_RESCAN = 1 << 5, |
0d475361 | 484 | |
963acd6f | 485 | DF_VERIFY_SCHEDULED = 1 << 6 |
6fb5fa3c DB |
486 | }; |
487 | ||
488 | /* Two of these structures are inline in df, one for the uses and one | |
489 | for the defs. This structure is only contains the refs within the | |
490 | boundary of the df_set_blocks if that has been defined. */ | |
4d779342 | 491 | struct df_ref_info |
10c4b247 | 492 | { |
57512f53 | 493 | df_ref *refs; /* Ref table, indexed by id. */ |
6fb5fa3c DB |
494 | unsigned int *begin; /* First ref_index for this pseudo. */ |
495 | unsigned int *count; /* Count of refs for this pseudo. */ | |
4d779342 | 496 | unsigned int refs_size; /* Size of currently allocated refs table. */ |
6fb5fa3c DB |
497 | |
498 | /* Table_size is the number of elements in the refs table. This | |
499 | will also be the width of the bitvectors in the rd and ru | |
500 | problems. Total_size is the number of refs. These will be the | |
501 | same if the focus has not been reduced by df_set_blocks. If the | |
502 | focus has been reduced, table_size will be smaller since it only | |
503 | contains the refs in the set blocks. */ | |
504 | unsigned int table_size; | |
505 | unsigned int total_size; | |
506 | ||
507 | enum df_ref_order ref_order; | |
10c4b247 JL |
508 | }; |
509 | ||
6fb5fa3c DB |
510 | /* Three of these structures are allocated for every pseudo reg. One |
511 | for the uses, one for the eq_uses and one for the defs. */ | |
512 | struct df_reg_info | |
513 | { | |
514 | /* Head of chain for refs of that type and regno. */ | |
57512f53 | 515 | df_ref reg_chain; |
6fb5fa3c DB |
516 | /* Number of refs in the chain. */ |
517 | unsigned int n_refs; | |
518 | }; | |
519 | ||
520 | ||
4d779342 DB |
521 | /*---------------------------------------------------------------------------- |
522 | Problem data for the scanning dataflow problem. Unlike the other | |
523 | dataflow problems, the problem data for scanning is fully exposed and | |
524 | used by owners of the problem. | |
525 | ----------------------------------------------------------------------------*/ | |
10c4b247 JL |
526 | |
527 | struct df | |
528 | { | |
4d779342 | 529 | |
4d779342 DB |
530 | /* The set of problems to be solved is stored in two arrays. In |
531 | PROBLEMS_IN_ORDER, the problems are stored in the order that they | |
532 | are solved. This is an internally dense array that may have | |
533 | nulls at the end of it. In PROBLEMS_BY_INDEX, the problem is | |
534 | stored by the value in df_problem.id. These are used to access | |
535 | the problem local data without having to search the first | |
536 | array. */ | |
537 | ||
b8698a0f L |
538 | struct dataflow *problems_in_order[DF_LAST_PROBLEM_PLUS1]; |
539 | struct dataflow *problems_by_index[DF_LAST_PROBLEM_PLUS1]; | |
4d779342 | 540 | |
6fb5fa3c DB |
541 | /* If not NULL, this subset of blocks of the program to be |
542 | considered for analysis. At certain times, this will contain all | |
543 | the blocks in the function so it cannot be used as an indicator | |
b8698a0f | 544 | of if we are analyzing a subset. See analyze_subset. */ |
4d779342 DB |
545 | bitmap blocks_to_analyze; |
546 | ||
547 | /* The following information is really the problem data for the | |
548 | scanning instance but it is used too often by the other problems | |
549 | to keep getting it from there. */ | |
550 | struct df_ref_info def_info; /* Def info. */ | |
551 | struct df_ref_info use_info; /* Use info. */ | |
6fb5fa3c DB |
552 | |
553 | /* The following three arrays are allocated in parallel. They contain | |
554 | the sets of refs of each type for each reg. */ | |
555 | struct df_reg_info **def_regs; /* Def reg info. */ | |
556 | struct df_reg_info **use_regs; /* Eq_use reg info. */ | |
557 | struct df_reg_info **eq_use_regs; /* Eq_use info. */ | |
558 | unsigned int regs_size; /* Size of currently allocated regs table. */ | |
559 | unsigned int regs_inited; /* Number of regs with reg_infos allocated. */ | |
560 | ||
561 | ||
4d779342 DB |
562 | struct df_insn_info **insns; /* Insn table, indexed by insn UID. */ |
563 | unsigned int insns_size; /* Size of insn table. */ | |
8f5929e1 JJ |
564 | |
565 | int num_problems_defined; | |
566 | ||
4d779342 | 567 | bitmap hardware_regs_used; /* The set of hardware registers used. */ |
6fb5fa3c DB |
568 | /* The set of hard regs that are in the artificial uses at the end |
569 | of a regular basic block. */ | |
570 | bitmap regular_block_artificial_uses; | |
571 | /* The set of hard regs that are in the artificial uses at the end | |
572 | of a basic block that has an EH pred. */ | |
573 | bitmap eh_block_artificial_uses; | |
574 | /* The set of hardware registers live on entry to the function. */ | |
575 | bitmap entry_block_defs; | |
4d779342 | 576 | bitmap exit_block_uses; /* The set of hardware registers used in exit block. */ |
6fb5fa3c DB |
577 | |
578 | /* Insns to delete, rescan or reprocess the notes at next | |
579 | df_rescan_all or df_process_deferred_rescans. */ | |
580 | bitmap insns_to_delete; | |
581 | bitmap insns_to_rescan; | |
582 | bitmap insns_to_notes_rescan; | |
b8698a0f | 583 | int *postorder; /* The current set of basic blocks |
6fb5fa3c | 584 | in reverse postorder. */ |
b8698a0f | 585 | int *postorder_inverted; /* The current set of basic blocks |
6fb5fa3c DB |
586 | in reverse postorder of inverted CFG. */ |
587 | int n_blocks; /* The number of blocks in reverse postorder. */ | |
b8698a0f | 588 | int n_blocks_inverted; /* The number of blocks |
6fb5fa3c DB |
589 | in reverse postorder of inverted CFG. */ |
590 | ||
591 | /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number | |
592 | of refs that qualify as being real hard regs uses. Artificial | |
593 | uses and defs as well as refs in eq notes are ignored. If the | |
594 | ref is a def, it cannot be a MAY_CLOBBER def. If the ref is a | |
595 | use, it cannot be the emim_reg_set or be the frame or arg pointer | |
596 | register. | |
597 | ||
598 | IT IS NOT ACCEPTABLE TO MANUALLY CHANGE THIS ARRAY. This array | |
599 | always reflects the actual number of refs in the insn stream that | |
600 | satisfy the above criteria. */ | |
601 | unsigned int *hard_regs_live_count; | |
602 | ||
603 | /* This counter provides a way to totally order refs without using | |
604 | addresses. It is incremented whenever a ref is created. */ | |
605 | unsigned int ref_order; | |
606 | ||
32e8bb8e ILT |
607 | /* Problem specific control information. This is a combination of |
608 | enum df_changeable_flags values. */ | |
609 | int changeable_flags : 8; | |
8f5929e1 JJ |
610 | |
611 | /* If this is true, then only a subset of the blocks of the program | |
612 | is considered to compute the solutions of dataflow problems. */ | |
613 | bool analyze_subset; | |
614 | ||
615 | /* True if someone added or deleted something from regs_ever_live so | |
616 | that the entry and exit blocks need be reprocessed. */ | |
617 | bool redo_entry_and_exit; | |
10c4b247 JL |
618 | }; |
619 | ||
6fb5fa3c | 620 | #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info((BB)->index)) |
6fb5fa3c DB |
621 | #define DF_RD_BB_INFO(BB) (df_rd_get_bb_info((BB)->index)) |
622 | #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index)) | |
6fb5fa3c | 623 | #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index)) |
cc806ac1 | 624 | #define DF_BYTE_LR_BB_INFO(BB) (df_byte_lr_get_bb_info((BB)->index)) |
c6741572 | 625 | #define DF_MD_BB_INFO(BB) (df_md_get_bb_info((BB)->index)) |
10c4b247 | 626 | |
4d779342 | 627 | /* Most transformations that wish to use live register analysis will |
6fb5fa3c | 628 | use these macros. This info is the and of the lr and live sets. */ |
b8698a0f L |
629 | #define DF_LIVE_IN(BB) (DF_LIVE_BB_INFO(BB)->in) |
630 | #define DF_LIVE_OUT(BB) (DF_LIVE_BB_INFO(BB)->out) | |
10c4b247 | 631 | |
30c6f45d RS |
632 | /* These macros are used by passes that are not tolerant of |
633 | uninitialized variables. This intolerance should eventually | |
634 | be fixed. */ | |
b8698a0f L |
635 | #define DF_LR_IN(BB) (DF_LR_BB_INFO(BB)->in) |
636 | #define DF_LR_OUT(BB) (DF_LR_BB_INFO(BB)->out) | |
10c4b247 | 637 | |
cc806ac1 RS |
638 | /* These macros are used by passes that are not tolerant of |
639 | uninitialized variables. This intolerance should eventually | |
640 | be fixed. */ | |
b8698a0f L |
641 | #define DF_BYTE_LR_IN(BB) (DF_BYTE_LR_BB_INFO(BB)->in) |
642 | #define DF_BYTE_LR_OUT(BB) (DF_BYTE_LR_BB_INFO(BB)->out) | |
cc806ac1 | 643 | |
10c4b247 | 644 | /* Macros to access the elements within the ref structure. */ |
7890e8f3 | 645 | |
4d779342 | 646 | |
57512f53 KZ |
647 | #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->base.reg) == SUBREG \ |
648 | ? SUBREG_REG ((REF)->base.reg) : ((REF)->base.reg)) | |
649 | #define DF_REF_REGNO(REF) ((REF)->base.regno) | |
650 | #define DF_REF_REAL_LOC(REF) (GET_CODE (*((REF)->regular_ref.loc)) == SUBREG \ | |
651 | ? &SUBREG_REG (*((REF)->regular_ref.loc)) : ((REF)->regular_ref.loc)) | |
652 | #define DF_REF_REG(REF) ((REF)->base.reg) | |
653 | #define DF_REF_LOC(REF) ((DF_REF_CLASS(REF) == DF_REF_REGULAR || DF_REF_CLASS(REF) == DF_REF_EXTRACT) ? \ | |
654 | (REF)->regular_ref.loc : NULL) | |
655 | #define DF_REF_BB(REF) (DF_REF_IS_ARTIFICIAL(REF) ? \ | |
656 | (REF)->artificial_ref.bb : BLOCK_FOR_INSN (DF_REF_INSN(REF))) | |
4d779342 | 657 | #define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index) |
57512f53 KZ |
658 | #define DF_REF_INSN_INFO(REF) ((REF)->base.insn_info) |
659 | #define DF_REF_INSN(REF) ((REF)->base.insn_info->insn) | |
50e94c7e | 660 | #define DF_REF_INSN_UID(REF) (INSN_UID (DF_REF_INSN(REF))) |
57512f53 KZ |
661 | #define DF_REF_CLASS(REF) ((REF)->base.cl) |
662 | #define DF_REF_TYPE(REF) ((REF)->base.type) | |
663 | #define DF_REF_CHAIN(REF) ((REF)->base.chain) | |
664 | #define DF_REF_ID(REF) ((REF)->base.id) | |
665 | #define DF_REF_FLAGS(REF) ((REF)->base.flags) | |
6fb5fa3c DB |
666 | #define DF_REF_FLAGS_IS_SET(REF, v) ((DF_REF_FLAGS (REF) & (v)) != 0) |
667 | #define DF_REF_FLAGS_SET(REF, v) (DF_REF_FLAGS (REF) |= (v)) | |
668 | #define DF_REF_FLAGS_CLEAR(REF, v) (DF_REF_FLAGS (REF) &= ~(v)) | |
57512f53 KZ |
669 | #define DF_REF_ORDER(REF) ((REF)->base.ref_order) |
670 | /* If DF_REF_IS_ARTIFICIAL () is true, this is not a real | |
671 | definition/use, but an artificial one created to model always live | |
672 | registers, eh uses, etc. */ | |
673 | #define DF_REF_IS_ARTIFICIAL(REF) (DF_REF_CLASS(REF) == DF_REF_ARTIFICIAL) | |
6fb5fa3c DB |
674 | #define DF_REF_REG_MARK(REF) (DF_REF_FLAGS_SET ((REF),DF_REF_REG_MARKER)) |
675 | #define DF_REF_REG_UNMARK(REF) (DF_REF_FLAGS_CLEAR ((REF),DF_REF_REG_MARKER)) | |
676 | #define DF_REF_IS_REG_MARKED(REF) (DF_REF_FLAGS_IS_SET ((REF),DF_REF_REG_MARKER)) | |
57512f53 KZ |
677 | #define DF_REF_NEXT_REG(REF) ((REF)->base.next_reg) |
678 | #define DF_REF_PREV_REG(REF) ((REF)->base.prev_reg) | |
b8698a0f L |
679 | /* The following two macros may only be applied if one of |
680 | DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT is true. */ | |
57512f53 KZ |
681 | #define DF_REF_EXTRACT_WIDTH(REF) ((REF)->extract_ref.width) |
682 | #define DF_REF_EXTRACT_OFFSET(REF) ((REF)->extract_ref.offset) | |
683 | #define DF_REF_EXTRACT_MODE(REF) ((REF)->extract_ref.mode) | |
10c4b247 | 684 | |
57512f53 | 685 | /* Macros to determine the reference type. */ |
10c4b247 | 686 | #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF) |
23249ac4 | 687 | #define DF_REF_REG_USE_P(REF) ((REF) && !DF_REF_REG_DEF_P (REF)) |
10c4b247 JL |
688 | #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE) |
689 | #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD) | |
690 | #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \ | |
7890e8f3 | 691 | || DF_REF_REG_MEM_LOAD_P (REF)) |
10c4b247 | 692 | |
57512f53 KZ |
693 | #define DF_MWS_REG_DEF_P(MREF) (DF_MWS_TYPE (MREF) == DF_REF_REG_DEF) |
694 | #define DF_MWS_REG_USE_P(MREF) ((MREF) && !DF_MWS_REG_DEF_P (MREF)) | |
695 | #define DF_MWS_TYPE(MREF) ((MREF)->type) | |
696 | ||
6fb5fa3c DB |
697 | /* Macros to get the refs out of def_info or use_info refs table. If |
698 | the focus of the dataflow has been set to some subset of blocks | |
699 | with df_set_blocks, these macros will only find the uses and defs | |
b8698a0f | 700 | in that subset of blocks. |
6fb5fa3c DB |
701 | |
702 | These macros should be used with care. The def macros are only | |
703 | usable after a call to df_maybe_reorganize_def_refs and the use | |
704 | macros are only usable after a call to | |
705 | df_maybe_reorganize_use_refs. HOWEVER, BUILDING AND USING THESE | |
706 | ARRAYS ARE A CACHE LOCALITY KILLER. */ | |
707 | ||
708 | #define DF_DEFS_TABLE_SIZE() (df->def_info.table_size) | |
709 | #define DF_DEFS_GET(ID) (df->def_info.refs[(ID)]) | |
710 | #define DF_DEFS_SET(ID,VAL) (df->def_info.refs[(ID)]=(VAL)) | |
711 | #define DF_DEFS_COUNT(ID) (df->def_info.count[(ID)]) | |
712 | #define DF_DEFS_BEGIN(ID) (df->def_info.begin[(ID)]) | |
713 | #define DF_USES_TABLE_SIZE() (df->use_info.table_size) | |
714 | #define DF_USES_GET(ID) (df->use_info.refs[(ID)]) | |
715 | #define DF_USES_SET(ID,VAL) (df->use_info.refs[(ID)]=(VAL)) | |
716 | #define DF_USES_COUNT(ID) (df->use_info.count[(ID)]) | |
717 | #define DF_USES_BEGIN(ID) (df->use_info.begin[(ID)]) | |
4d779342 DB |
718 | |
719 | /* Macros to access the register information from scan dataflow record. */ | |
720 | ||
6fb5fa3c DB |
721 | #define DF_REG_SIZE(DF) (df->regs_inited) |
722 | #define DF_REG_DEF_GET(REG) (df->def_regs[(REG)]) | |
723 | #define DF_REG_DEF_CHAIN(REG) (df->def_regs[(REG)]->reg_chain) | |
724 | #define DF_REG_DEF_COUNT(REG) (df->def_regs[(REG)]->n_refs) | |
725 | #define DF_REG_USE_GET(REG) (df->use_regs[(REG)]) | |
726 | #define DF_REG_USE_CHAIN(REG) (df->use_regs[(REG)]->reg_chain) | |
727 | #define DF_REG_USE_COUNT(REG) (df->use_regs[(REG)]->n_refs) | |
728 | #define DF_REG_EQ_USE_GET(REG) (df->eq_use_regs[(REG)]) | |
729 | #define DF_REG_EQ_USE_CHAIN(REG) (df->eq_use_regs[(REG)]->reg_chain) | |
730 | #define DF_REG_EQ_USE_COUNT(REG) (df->eq_use_regs[(REG)]->n_refs) | |
10c4b247 JL |
731 | |
732 | /* Macros to access the elements within the reg_info structure table. */ | |
733 | ||
6fb5fa3c DB |
734 | #define DF_REGNO_FIRST_DEF(REGNUM) \ |
735 | (DF_REG_DEF_GET(REGNUM) ? DF_REG_DEF_GET(REGNUM) : 0) | |
736 | #define DF_REGNO_LAST_USE(REGNUM) \ | |
737 | (DF_REG_USE_GET(REGNUM) ? DF_REG_USE_GET(REGNUM) : 0) | |
10c4b247 JL |
738 | |
739 | /* Macros to access the elements within the insn_info structure table. */ | |
740 | ||
6fb5fa3c | 741 | #define DF_INSN_SIZE() ((df)->insns_size) |
50e94c7e SB |
742 | #define DF_INSN_INFO_GET(INSN) (df->insns[(INSN_UID(INSN))]) |
743 | #define DF_INSN_INFO_SET(INSN,VAL) (df->insns[(INSN_UID (INSN))]=(VAL)) | |
744 | #define DF_INSN_INFO_LUID(II) ((II)->luid) | |
745 | #define DF_INSN_INFO_DEFS(II) ((II)->defs) | |
746 | #define DF_INSN_INFO_USES(II) ((II)->uses) | |
747 | #define DF_INSN_INFO_EQ_USES(II) ((II)->eq_uses) | |
748 | ||
749 | #define DF_INSN_LUID(INSN) (DF_INSN_INFO_LUID (DF_INSN_INFO_GET(INSN))) | |
750 | #define DF_INSN_DEFS(INSN) (DF_INSN_INFO_DEFS (DF_INSN_INFO_GET(INSN))) | |
751 | #define DF_INSN_USES(INSN) (DF_INSN_INFO_USES (DF_INSN_INFO_GET(INSN))) | |
752 | #define DF_INSN_EQ_USES(INSN) (DF_INSN_INFO_EQ_USES (DF_INSN_INFO_GET(INSN))) | |
6fb5fa3c DB |
753 | |
754 | #define DF_INSN_UID_GET(UID) (df->insns[(UID)]) | |
755 | #define DF_INSN_UID_SET(UID,VAL) (df->insns[(UID)]=(VAL)) | |
756 | #define DF_INSN_UID_SAFE_GET(UID) (((unsigned)(UID) < DF_INSN_SIZE()) \ | |
757 | ? DF_INSN_UID_GET (UID) \ | |
758 | : NULL) | |
759 | #define DF_INSN_UID_LUID(INSN) (DF_INSN_UID_GET(INSN)->luid) | |
760 | #define DF_INSN_UID_DEFS(INSN) (DF_INSN_UID_GET(INSN)->defs) | |
761 | #define DF_INSN_UID_USES(INSN) (DF_INSN_UID_GET(INSN)->uses) | |
762 | #define DF_INSN_UID_EQ_USES(INSN) (DF_INSN_UID_GET(INSN)->eq_uses) | |
763 | #define DF_INSN_UID_MWS(INSN) (DF_INSN_UID_GET(INSN)->mw_hardregs) | |
764 | ||
765 | /* An obstack for bitmap not related to specific dataflow problems. | |
766 | This obstack should e.g. be used for bitmaps with a short life time | |
767 | such as temporary bitmaps. This obstack is declared in df-core.c. */ | |
768 | ||
769 | extern bitmap_obstack df_bitmap_obstack; | |
10c4b247 | 770 | |
10c4b247 | 771 | |
4d779342 DB |
772 | /* One of these structures is allocated for every basic block. */ |
773 | struct df_scan_bb_info | |
774 | { | |
ba49cb7b KZ |
775 | /* The entry block has many artificial defs and these are at the |
776 | bottom of the block. | |
777 | ||
778 | Blocks that are targets of exception edges may have some | |
779 | artificial defs. These are logically located at the top of the | |
780 | block. | |
781 | ||
782 | Blocks that are the targets of non-local goto's have the hard | |
783 | frame pointer defined at the top of the block. */ | |
57512f53 | 784 | df_ref *artificial_defs; |
10c4b247 | 785 | |
ba49cb7b KZ |
786 | /* Blocks that are targets of exception edges may have some |
787 | artificial uses. These are logically at the top of the block. | |
788 | ||
789 | Most blocks have artificial uses at the bottom of the block. */ | |
57512f53 | 790 | df_ref *artificial_uses; |
4d779342 | 791 | }; |
10c4b247 | 792 | |
10c4b247 | 793 | |
b11550aa | 794 | /* Reaching definitions. All bitmaps are indexed by the id field of |
2b49e1a0 | 795 | the ref except sparse_kill which is indexed by regno. */ |
b8698a0f | 796 | struct df_rd_bb_info |
4d779342 | 797 | { |
2b49e1a0 | 798 | /* Local sets to describe the basic blocks. */ |
b8698a0f | 799 | bitmap kill; |
4d779342 | 800 | bitmap sparse_kill; |
963acd6f | 801 | bitmap gen; /* The set of defs generated in this block. */ |
b11550aa | 802 | |
963acd6f | 803 | /* The results of the dataflow problem. */ |
b11550aa KZ |
804 | bitmap in; /* At the top of the block. */ |
805 | bitmap out; /* At the bottom of the block. */ | |
4d779342 | 806 | }; |
e5626198 | 807 | |
e5626198 | 808 | |
c6741572 PB |
809 | /* Multiple reaching definitions. All bitmaps are referenced by the |
810 | register number. */ | |
811 | ||
b8698a0f | 812 | struct df_md_bb_info |
c6741572 PB |
813 | { |
814 | /* Local sets to describe the basic blocks. */ | |
815 | bitmap gen; /* Partial/conditional definitions live at BB out. */ | |
816 | bitmap kill; /* Other definitions that are live at BB out. */ | |
817 | bitmap init; /* Definitions coming from dominance frontier edges. */ | |
818 | ||
819 | /* The results of the dataflow problem. */ | |
820 | bitmap in; /* Just before the block itself. */ | |
821 | bitmap out; /* At the bottom of the block. */ | |
822 | }; | |
823 | ||
824 | ||
ba49cb7b KZ |
825 | /* Live registers, a backwards dataflow problem. All bitmaps are |
826 | referenced by the register number. */ | |
6fb5fa3c | 827 | |
b8698a0f | 828 | struct df_lr_bb_info |
4d779342 | 829 | { |
b11550aa | 830 | /* Local sets to describe the basic blocks. */ |
b8698a0f | 831 | bitmap def; /* The set of registers set in this block |
6fb5fa3c | 832 | - except artificial defs at the top. */ |
b11550aa KZ |
833 | bitmap use; /* The set of registers used in this block. */ |
834 | ||
835 | /* The results of the dataflow problem. */ | |
6fb5fa3c | 836 | bitmap in; /* Just before the block itself. */ |
b11550aa | 837 | bitmap out; /* At the bottom of the block. */ |
4d779342 | 838 | }; |
e5626198 | 839 | |
e5626198 | 840 | |
6fb5fa3c DB |
841 | /* Uninitialized registers. All bitmaps are referenced by the |
842 | register number. Anded results of the forwards and backward live | |
843 | info. Note that the forwards live information is not available | |
844 | separately. */ | |
b8698a0f | 845 | struct df_live_bb_info |
4d779342 | 846 | { |
b11550aa KZ |
847 | /* Local sets to describe the basic blocks. */ |
848 | bitmap kill; /* The set of registers unset in this block. Calls, | |
849 | for instance, unset registers. */ | |
850 | bitmap gen; /* The set of registers set in this block. */ | |
851 | ||
852 | /* The results of the dataflow problem. */ | |
853 | bitmap in; /* At the top of the block. */ | |
854 | bitmap out; /* At the bottom of the block. */ | |
4d779342 | 855 | }; |
1052bd54 | 856 | |
6fb5fa3c | 857 | |
cc806ac1 RS |
858 | /* Live registers, a backwards dataflow problem. These bitmaps are |
859 | indexed by the df_byte_lr_offset array which is indexed by pseudo. */ | |
860 | ||
b8698a0f | 861 | struct df_byte_lr_bb_info |
cc806ac1 RS |
862 | { |
863 | /* Local sets to describe the basic blocks. */ | |
b8698a0f | 864 | bitmap def; /* The set of registers set in this block |
cc806ac1 RS |
865 | - except artificial defs at the top. */ |
866 | bitmap use; /* The set of registers used in this block. */ | |
867 | ||
868 | /* The results of the dataflow problem. */ | |
869 | bitmap in; /* Just before the block itself. */ | |
870 | bitmap out; /* At the bottom of the block. */ | |
871 | }; | |
872 | ||
873 | ||
6fb5fa3c DB |
874 | /* This is used for debugging and for the dumpers to find the latest |
875 | instance so that the df info can be added to the dumps. This | |
b8698a0f | 876 | should not be used by regular code. */ |
6fb5fa3c | 877 | extern struct df *df; |
cc806ac1 RS |
878 | #define df_scan (df->problems_by_index[DF_SCAN]) |
879 | #define df_rd (df->problems_by_index[DF_RD]) | |
880 | #define df_lr (df->problems_by_index[DF_LR]) | |
881 | #define df_live (df->problems_by_index[DF_LIVE]) | |
882 | #define df_chain (df->problems_by_index[DF_CHAIN]) | |
883 | #define df_byte_lr (df->problems_by_index[DF_BYTE_LR]) | |
884 | #define df_note (df->problems_by_index[DF_NOTE]) | |
c6741572 | 885 | #define df_md (df->problems_by_index[DF_MD]) |
6fb5fa3c | 886 | |
0d52bcc1 | 887 | /* This symbol turns on checking that each modification of the cfg has |
6fb5fa3c DB |
888 | been identified to the appropriate df routines. It is not part of |
889 | verification per se because the check that the final solution has | |
890 | not changed covers this. However, if the solution is not being | |
891 | properly recomputed because the cfg is being modified, adding in | |
892 | calls to df_check_cfg_clean can be used to find the source of that | |
893 | kind of problem. */ | |
894 | #if 0 | |
895 | #define DF_DEBUG_CFG | |
896 | #endif | |
897 | ||
4d779342 DB |
898 | |
899 | /* Functions defined in df-core.c. */ | |
900 | ||
6fb5fa3c | 901 | extern void df_add_problem (struct df_problem *); |
81f40b79 ILT |
902 | extern int df_set_flags (int); |
903 | extern int df_clear_flags (int); | |
6fb5fa3c DB |
904 | extern void df_set_blocks (bitmap); |
905 | extern void df_remove_problem (struct dataflow *); | |
0d475361 | 906 | extern void df_finish_pass (bool); |
6fb5fa3c DB |
907 | extern void df_analyze_problem (struct dataflow *, bitmap, int *, int); |
908 | extern void df_analyze (void); | |
909 | extern int df_get_n_blocks (enum df_flow_dir); | |
910 | extern int *df_get_postorder (enum df_flow_dir); | |
911 | extern void df_simple_dataflow (enum df_flow_dir, df_init_function, | |
912 | df_confluence_function_0, df_confluence_function_n, | |
913 | df_transfer_function, bitmap, int *, int); | |
914 | extern void df_mark_solutions_dirty (void); | |
915 | extern bool df_get_bb_dirty (basic_block); | |
916 | extern void df_set_bb_dirty (basic_block); | |
c23cd1d6 | 917 | extern void df_set_bb_dirty_nonlr (basic_block); |
6fb5fa3c DB |
918 | extern void df_compact_blocks (void); |
919 | extern void df_bb_replace (int, basic_block); | |
920 | extern void df_bb_delete (int); | |
921 | extern void df_verify (void); | |
922 | #ifdef DF_DEBUG_CFG | |
923 | extern void df_check_cfg_clean (void); | |
924 | #endif | |
57512f53 KZ |
925 | extern df_ref df_bb_regno_first_def_find (basic_block, unsigned int); |
926 | extern df_ref df_bb_regno_last_def_find (basic_block, unsigned int); | |
927 | extern df_ref df_find_def (rtx, rtx); | |
6fb5fa3c | 928 | extern bool df_reg_defined (rtx, rtx); |
57512f53 | 929 | extern df_ref df_find_use (rtx, rtx); |
6fb5fa3c DB |
930 | extern bool df_reg_used (rtx, rtx); |
931 | extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int); | |
932 | extern void df_print_regset (FILE *file, bitmap r); | |
cc806ac1 | 933 | extern void df_print_byte_regset (FILE *file, bitmap r); |
6fb5fa3c | 934 | extern void df_dump (FILE *); |
ffd640ed | 935 | extern void df_dump_region (FILE *); |
6fb5fa3c DB |
936 | extern void df_dump_start (FILE *); |
937 | extern void df_dump_top (basic_block, FILE *); | |
938 | extern void df_dump_bottom (basic_block, FILE *); | |
57512f53 KZ |
939 | extern void df_refs_chain_dump (df_ref *, bool, FILE *); |
940 | extern void df_regs_chain_dump (df_ref, FILE *); | |
6fb5fa3c DB |
941 | extern void df_insn_debug (rtx, bool, FILE *); |
942 | extern void df_insn_debug_regno (rtx, FILE *); | |
943 | extern void df_regno_debug (unsigned int, FILE *); | |
57512f53 | 944 | extern void df_ref_debug (df_ref, FILE *); |
7080f735 | 945 | extern void debug_df_insn (rtx); |
7080f735 | 946 | extern void debug_df_regno (unsigned int); |
7080f735 | 947 | extern void debug_df_reg (rtx); |
7080f735 | 948 | extern void debug_df_defno (unsigned int); |
7080f735 | 949 | extern void debug_df_useno (unsigned int); |
57512f53 | 950 | extern void debug_df_ref (df_ref); |
7080f735 | 951 | extern void debug_df_chain (struct df_link *); |
4d779342 DB |
952 | |
953 | /* Functions defined in df-problems.c. */ | |
954 | ||
57512f53 KZ |
955 | extern struct df_link *df_chain_create (df_ref, df_ref); |
956 | extern void df_chain_unlink (df_ref); | |
957 | extern void df_chain_copy (df_ref, struct df_link *); | |
6fb5fa3c DB |
958 | extern bitmap df_get_live_in (basic_block); |
959 | extern bitmap df_get_live_out (basic_block); | |
4d779342 | 960 | extern void df_grow_bb_info (struct dataflow *); |
23249ac4 | 961 | extern void df_chain_dump (struct df_link *, FILE *); |
4d779342 | 962 | extern void df_print_bb_index (basic_block bb, FILE *file); |
6fb5fa3c | 963 | extern void df_rd_add_problem (void); |
00952e97 PB |
964 | extern void df_rd_simulate_artificial_defs_at_top (basic_block, bitmap); |
965 | extern void df_rd_simulate_one_insn (basic_block, rtx, bitmap); | |
6fb5fa3c DB |
966 | extern void df_lr_add_problem (void); |
967 | extern void df_lr_verify_transfer_functions (void); | |
968 | extern void df_live_verify_transfer_functions (void); | |
969 | extern void df_live_add_problem (void); | |
89a95777 | 970 | extern void df_live_set_all_dirty (void); |
bbbbb16a | 971 | extern void df_chain_add_problem (unsigned int); |
cc806ac1 RS |
972 | extern void df_byte_lr_add_problem (void); |
973 | extern int df_byte_lr_get_regno_start (unsigned int); | |
974 | extern int df_byte_lr_get_regno_len (unsigned int); | |
975 | extern void df_byte_lr_simulate_defs (rtx, bitmap); | |
976 | extern void df_byte_lr_simulate_uses (rtx, bitmap); | |
977 | extern void df_byte_lr_simulate_artificial_refs_at_top (basic_block, bitmap); | |
978 | extern void df_byte_lr_simulate_artificial_refs_at_end (basic_block, bitmap); | |
6fb5fa3c | 979 | extern void df_note_add_problem (void); |
c6741572 PB |
980 | extern void df_md_add_problem (void); |
981 | extern void df_md_simulate_artificial_defs_at_top (basic_block, bitmap); | |
982 | extern void df_md_simulate_one_insn (basic_block, rtx, bitmap); | |
907deb1a | 983 | extern void df_simulate_find_noclobber_defs (rtx, bitmap); |
6fb5fa3c DB |
984 | extern void df_simulate_find_defs (rtx, bitmap); |
985 | extern void df_simulate_defs (rtx, bitmap); | |
986 | extern void df_simulate_uses (rtx, bitmap); | |
02b47899 KZ |
987 | extern void df_simulate_initialize_backwards (basic_block, bitmap); |
988 | extern void df_simulate_one_insn_backwards (basic_block, rtx, bitmap); | |
989 | extern void df_simulate_finalize_backwards (basic_block, bitmap); | |
990 | extern void df_simulate_initialize_forwards (basic_block, bitmap); | |
991 | extern void df_simulate_one_insn_forwards (basic_block, rtx, bitmap); | |
4d779342 DB |
992 | |
993 | /* Functions defined in df-scan.c. */ | |
994 | ||
6fb5fa3c DB |
995 | extern void df_scan_alloc (bitmap); |
996 | extern void df_scan_add_problem (void); | |
997 | extern void df_grow_reg_info (void); | |
998 | extern void df_grow_insn_info (void); | |
999 | extern void df_scan_blocks (void); | |
b8698a0f | 1000 | extern df_ref df_ref_create (rtx, rtx *, rtx,basic_block, |
bbbbb16a | 1001 | enum df_ref_type, int ref_flags, |
cc806ac1 | 1002 | int, int, enum machine_mode); |
57512f53 | 1003 | extern void df_ref_remove (df_ref); |
6fb5fa3c DB |
1004 | extern struct df_insn_info * df_insn_create_insn_record (rtx); |
1005 | extern void df_insn_delete (basic_block, unsigned int); | |
1006 | extern void df_bb_refs_record (int, bool); | |
1007 | extern bool df_insn_rescan (rtx); | |
b5b8b0ac | 1008 | extern bool df_insn_rescan_debug_internal (rtx); |
6fb5fa3c DB |
1009 | extern void df_insn_rescan_all (void); |
1010 | extern void df_process_deferred_rescans (void); | |
6fb5fa3c | 1011 | extern void df_recompute_luids (basic_block); |
63642d5a | 1012 | extern void df_insn_change_bb (rtx, basic_block); |
6fb5fa3c DB |
1013 | extern void df_maybe_reorganize_use_refs (enum df_ref_order); |
1014 | extern void df_maybe_reorganize_def_refs (enum df_ref_order); | |
1015 | extern void df_ref_change_reg_with_loc (int, int, rtx); | |
1016 | extern void df_notes_rescan (rtx); | |
4d779342 | 1017 | extern void df_hard_reg_init (void); |
6fb5fa3c DB |
1018 | extern void df_update_entry_block_defs (void); |
1019 | extern void df_update_exit_block_uses (void); | |
1020 | extern void df_update_entry_exit_and_calls (void); | |
1021 | extern bool df_hard_reg_used_p (unsigned int); | |
1022 | extern unsigned int df_hard_reg_used_count (unsigned int); | |
1023 | extern bool df_regs_ever_live_p (unsigned int); | |
1024 | extern void df_set_regs_ever_live (unsigned int, bool); | |
1025 | extern void df_compute_regs_ever_live (bool); | |
4d779342 | 1026 | extern bool df_read_modify_subreg_p (rtx); |
6fb5fa3c DB |
1027 | extern void df_scan_verify (void); |
1028 | ||
cc806ac1 | 1029 | /* Functions defined in df-byte-scan.c. */ |
b8698a0f | 1030 | extern bool df_compute_accessed_bytes (df_ref, enum df_mm, |
cc806ac1 RS |
1031 | unsigned int *, unsigned int *); |
1032 | ||
6fb5fa3c DB |
1033 | |
1034 | /* Get basic block info. */ | |
1035 | ||
1036 | static inline struct df_scan_bb_info * | |
1037 | df_scan_get_bb_info (unsigned int index) | |
1038 | { | |
1039 | if (index < df_scan->block_info_size) | |
1040 | return (struct df_scan_bb_info *) df_scan->block_info[index]; | |
1041 | else | |
1042 | return NULL; | |
1043 | } | |
1044 | ||
6fb5fa3c DB |
1045 | static inline struct df_rd_bb_info * |
1046 | df_rd_get_bb_info (unsigned int index) | |
1047 | { | |
1048 | if (index < df_rd->block_info_size) | |
1049 | return (struct df_rd_bb_info *) df_rd->block_info[index]; | |
1050 | else | |
1051 | return NULL; | |
1052 | } | |
1053 | ||
1054 | static inline struct df_lr_bb_info * | |
1055 | df_lr_get_bb_info (unsigned int index) | |
1056 | { | |
1057 | if (index < df_lr->block_info_size) | |
1058 | return (struct df_lr_bb_info *) df_lr->block_info[index]; | |
1059 | else | |
1060 | return NULL; | |
1061 | } | |
1062 | ||
c6741572 PB |
1063 | static inline struct df_md_bb_info * |
1064 | df_md_get_bb_info (unsigned int index) | |
1065 | { | |
1066 | if (index < df_md->block_info_size) | |
1067 | return (struct df_md_bb_info *) df_md->block_info[index]; | |
1068 | else | |
1069 | return NULL; | |
1070 | } | |
1071 | ||
6fb5fa3c DB |
1072 | static inline struct df_live_bb_info * |
1073 | df_live_get_bb_info (unsigned int index) | |
1074 | { | |
1075 | if (index < df_live->block_info_size) | |
1076 | return (struct df_live_bb_info *) df_live->block_info[index]; | |
cc806ac1 RS |
1077 | else |
1078 | return NULL; | |
1079 | } | |
1080 | ||
1081 | static inline struct df_byte_lr_bb_info * | |
1082 | df_byte_lr_get_bb_info (unsigned int index) | |
1083 | { | |
1084 | if (index < df_byte_lr->block_info_size) | |
1085 | return (struct df_byte_lr_bb_info *) df_byte_lr->block_info[index]; | |
6fb5fa3c DB |
1086 | else |
1087 | return NULL; | |
1088 | } | |
1089 | ||
6fb5fa3c DB |
1090 | /* Get the artificial defs for a basic block. */ |
1091 | ||
57512f53 | 1092 | static inline df_ref * |
6fb5fa3c DB |
1093 | df_get_artificial_defs (unsigned int bb_index) |
1094 | { | |
1095 | return df_scan_get_bb_info (bb_index)->artificial_defs; | |
1096 | } | |
1097 | ||
1098 | ||
1099 | /* Get the artificial uses for a basic block. */ | |
1100 | ||
57512f53 | 1101 | static inline df_ref * |
6fb5fa3c DB |
1102 | df_get_artificial_uses (unsigned int bb_index) |
1103 | { | |
1104 | return df_scan_get_bb_info (bb_index)->artificial_uses; | |
1105 | } | |
7890e8f3 | 1106 | |
59587b18 | 1107 | |
8cd37d0b RL |
1108 | /* web */ |
1109 | ||
1110 | /* This entry is allocated for each reference in the insn stream. */ | |
1111 | struct web_entry | |
1112 | { | |
1113 | /* Pointer to the parent in the union/find tree. */ | |
1114 | struct web_entry *pred; | |
1115 | /* Newly assigned register to the entry. Set only for roots. */ | |
1116 | rtx reg; | |
1117 | void* extra_info; | |
1118 | }; | |
1119 | ||
1120 | extern struct web_entry *unionfind_root (struct web_entry *); | |
1121 | extern bool unionfind_union (struct web_entry *, struct web_entry *); | |
994ae26c AO |
1122 | extern void union_defs (df_ref, struct web_entry *, |
1123 | unsigned int *used, struct web_entry *, | |
8cd37d0b RL |
1124 | bool (*fun) (struct web_entry *, struct web_entry *)); |
1125 | ||
59587b18 | 1126 | #endif /* GCC_DF_H */ |