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