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