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