Branch data Line data Source code
1 : : /* Form lists of pseudo register references for autoinc optimization
2 : : for GNU compiler. This is part of flow optimization.
3 : : Copyright (C) 1999-2024 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 : : DF_REF_SIGN_EXTRACT = 1 << 8,
133 : :
134 : : /* This flag is set if the ref contains a ZERO_EXTRACT. */
135 : : DF_REF_ZERO_EXTRACT = 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 DF_REF_EXTRACT_WIDTH(REF) ((REF)->extract_ref.width)
687 : : #define DF_REF_EXTRACT_OFFSET(REF) ((REF)->extract_ref.offset)
688 : : #define DF_REF_EXTRACT_MODE(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 : 1821158018 : df_scan_get_bb_info (unsigned int index)
1102 : : {
1103 : 316797684 : if (index < df_scan->block_info_size)
1104 : 1821158018 : 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 : 565368644 : df_rd_get_bb_info (unsigned int index)
1111 : : {
1112 : 565368644 : if (index < df_rd->block_info_size)
1113 : 565368644 : 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 : 3865073714 : df_lr_get_bb_info (unsigned int index)
1120 : : {
1121 : 3793214039 : if (index < df_lr->block_info_size)
1122 : 3865078300 : 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 : 0 : df_md_get_bb_info (unsigned int index)
1129 : : {
1130 : 0 : if (index < df_md->block_info_size)
1131 : 0 : 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 : 1703223805 : df_live_get_bb_info (unsigned int index)
1138 : : {
1139 : 1564614814 : if (index < df_live->block_info_size)
1140 : 1703223613 : 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 : 33160649 : df_word_lr_get_bb_info (unsigned int index)
1147 : : {
1148 : 33160649 : if (index < df_word_lr->block_info_size)
1149 : 33160649 : 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 : 84351815 : df_mir_get_bb_info (unsigned int index)
1156 : : {
1157 : 84351815 : if (index < df_mir->block_info_size)
1158 : 84351815 : 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 : 548196771 : df_get_live_out (basic_block bb)
1170 : : {
1171 : 548196771 : gcc_checking_assert (df_lr);
1172 : :
1173 : 548196771 : if (df_live)
1174 : 346891768 : return DF_LIVE_OUT (bb);
1175 : : else
1176 : 749501774 : 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 : 464120190 : df_get_live_in (basic_block bb)
1186 : : {
1187 : 464120190 : gcc_checking_assert (df_lr);
1188 : :
1189 : 464120190 : if (df_live)
1190 : 59009632 : return DF_LIVE_IN (bb);
1191 : : else
1192 : 869230748 : 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 : 1075602146 : df_get_artificial_defs (unsigned int bb_index)
1200 : : {
1201 : 2151204292 : return df_scan_get_bb_info (bb_index)->artificial_defs;
1202 : : }
1203 : :
1204 : :
1205 : : /* Get the artificial uses for a basic block. */
1206 : :
1207 : : inline df_ref
1208 : 667208847 : df_get_artificial_uses (unsigned int bb_index)
1209 : : {
1210 : 1256349891 : return df_scan_get_bb_info (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 : 108983872 : df_single_def (const df_insn_info *info)
1218 : : {
1219 : 108983872 : df_ref defs = DF_INSN_INFO_DEFS (info);
1220 : 108983872 : 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 : 54491936 : df_single_use (const df_insn_info *info)
1228 : : {
1229 : 54491936 : df_ref uses = DF_INSN_INFO_USES (info);
1230 : 54491936 : 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 : 47932262 : web_entry_base *pred () { return pred_pvt; }
1244 : 13965388 : 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 */
|
