1 /* Form lists of pseudo register references for autoinc optimization
2 for GNU compiler. This is part of flow optimization.
3 Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
5 Originally contributed by Michael P. Hayes
6 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
7 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
8 and Kenneth Zadeck (zadeck@naturalbridge.com).
10 This file is part of GCC.
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 3, or (at your option) any later
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING3. If not see
24 <http://www.gnu.org/licenses/>. */
30 #include "basic-block.h"
31 #include "alloc-pool.h"
38 /* Data flow problems. All problems must have a unique id here. */
39 /* Scanning is not really a dataflow problem, but it is useful to have
40 the basic block functions in the vector so that things get done in
41 a uniform manner. The first four problems are always defined. The
42 last 5 are optional and can be added or deleted at any time. */
44 #define DF_LR 1 /* Live Registers backward. */
45 #define DF_LIVE 2 /* Live Registers & Uninitialized Registers */
47 #define DF_RD 3 /* Reaching Defs. */
48 #define DF_UREC 4 /* Uninitialized Registers with Early Clobber. */
49 #define DF_CHAIN 5 /* Def-Use and/or Use-Def Chains. */
50 #define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */
52 #define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1)
54 /* Dataflow direction. */
63 /* The first of these is a set of a register. The remaining three are
64 all uses of a register (the mem_load and mem_store relate to how
65 the register as an addressing operand). */
66 enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
67 DF_REF_REG_MEM_STORE};
69 #define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
73 /* Read-modify-write refs generate both a use and a def and
74 these are marked with this flag to show that they are not
76 DF_REF_READ_WRITE = 1 << 0,
78 /* If this flag is set for an artificial use or def, that ref
79 logically happens at the top of the block. If it is not set
80 for an artificial use or def, that ref logically happens at the
81 bottom of the block. This is never set for regular refs. */
82 DF_REF_AT_TOP = 1 << 1,
84 /* This flag is set if the use is inside a REG_EQUAL or REG_EQUIV
86 DF_REF_IN_NOTE = 1 << 2,
88 /* This flag is set if this ref, generally a def, may clobber the
89 referenced register. This is generally only set for hard
90 registers that cross a call site. With better information
91 about calls, some of these could be changed in the future to
92 DF_REF_MUST_CLOBBER. */
93 DF_REF_MAY_CLOBBER = 1 << 3,
97 /* This flag is set if this ref, generally a def, is a real
98 clobber. This is not currently set for registers live across a
99 call because that clobbering may or may not happen.
101 Most of the uses of this are with sets that have a
102 GET_CODE(..)==CLOBBER. Note that this is set even if the
103 clobber is to a subreg. So in order to tell if the clobber
104 wipes out the entire register, it is necessary to also check
105 the DF_REF_PARTIAL flag. */
106 DF_REF_MUST_CLOBBER = 1 << 4,
108 /* This bit is true if this ref is part of a multiword hardreg. */
109 DF_REF_MW_HARDREG = 1 << 5,
111 /* This flag is set if this ref is a partial use or def of the
112 associated register. */
113 DF_REF_PARTIAL = 1 << 6,
115 /* This flag is set if this ref occurs inside of a conditional
116 execution instruction. */
117 DF_REF_CONDITIONAL = 1 << 7,
121 /* This flag is set if this ref is inside a pre/post modify. */
122 DF_REF_PRE_POST_MODIFY = 1 << 8,
124 /* This flag is set if this ref is a usage of the stack pointer by
126 DF_REF_CALL_STACK_USAGE = 1 << 9,
128 /* This flag is used for verification of existing refs. */
129 DF_REF_REG_MARKER = 1 << 10,
131 /* This bit is true if this ref can make regs_ever_live true for
133 DF_HARD_REG_LIVE = 1 << 11
136 /* The possible ordering of refs within the df_ref_info. */
139 /* There is not table. */
140 DF_REF_ORDER_NO_TABLE,
142 /* There is a table of refs but it is not (or no longer) organized
143 by one of the following methods. */
144 DF_REF_ORDER_UNORDERED,
145 DF_REF_ORDER_UNORDERED_WITH_NOTES,
147 /* Organize the table by reg order, all of the refs with regno 0
148 followed by all of the refs with regno 1 ... . Within all of
149 the regs for a particular regno, the refs are unordered. */
152 /* For uses, the refs within eq notes may be added for
153 DF_REF_ORDER_BY_REG. */
154 DF_REF_ORDER_BY_REG_WITH_NOTES,
156 /* Organize the refs in insn order. The insns are ordered within a
157 block, and the blocks are ordered by FOR_ALL_BB. */
158 DF_REF_ORDER_BY_INSN,
160 /* For uses, the refs within eq notes may be added for
161 DF_REF_ORDER_BY_INSN. */
162 DF_REF_ORDER_BY_INSN_WITH_NOTES
165 /* Function prototypes added to df_problem instance. */
167 /* Allocate the problem specific data. */
168 typedef void (*df_alloc_function) (bitmap);
170 /* This function is called if the problem has global data that needs
171 to be cleared when ever the set of blocks changes. The bitmap
172 contains the set of blocks that may require special attention.
173 This call is only made if some of the blocks are going to change.
174 If everything is to be deleted, the wholesale deletion mechanisms
176 typedef void (*df_reset_function) (bitmap);
178 /* Free the basic block info. Called from the block reordering code
179 to get rid of the blocks that have been squished down. */
180 typedef void (*df_free_bb_function) (basic_block, void *);
182 /* Local compute function. */
183 typedef void (*df_local_compute_function) (bitmap);
185 /* Init the solution specific data. */
186 typedef void (*df_init_function) (bitmap);
188 /* Iterative dataflow function. */
189 typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int);
191 /* Confluence operator for blocks with 0 out (or in) edges. */
192 typedef void (*df_confluence_function_0) (basic_block);
194 /* Confluence operator for blocks with 1 or more out (or in) edges. */
195 typedef void (*df_confluence_function_n) (edge);
197 /* Transfer function for blocks. */
198 typedef bool (*df_transfer_function) (int);
200 /* Function to massage the information after the problem solving. */
201 typedef void (*df_finalizer_function) (bitmap);
203 /* Function to free all of the problem specific datastructures. */
204 typedef void (*df_free_function) (void);
206 /* Function to remove this problem from the stack of dataflow problems
207 without effecting the other problems in the stack except for those
208 that depend on this problem. */
209 typedef void (*df_remove_problem_function) (void);
211 /* Function to dump basic block independent results to FILE. */
212 typedef void (*df_dump_problem_function) (FILE *);
214 /* Function to dump top or bottom of basic block results to FILE. */
215 typedef void (*df_dump_bb_problem_function) (basic_block, FILE *);
217 /* Function to dump top or bottom of basic block results to FILE. */
218 typedef void (*df_verify_solution_start) (void);
220 /* Function to dump top or bottom of basic block results to FILE. */
221 typedef void (*df_verify_solution_end) (void);
223 /* The static description of a dataflow problem to solve. See above
224 typedefs for doc for the function fields. */
227 /* The unique id of the problem. This is used it index into
228 df->defined_problems to make accessing the problem data easy. */
230 enum df_flow_dir dir; /* Dataflow direction. */
231 df_alloc_function alloc_fun;
232 df_reset_function reset_fun;
233 df_free_bb_function free_bb_fun;
234 df_local_compute_function local_compute_fun;
235 df_init_function init_fun;
236 df_dataflow_function dataflow_fun;
237 df_confluence_function_0 con_fun_0;
238 df_confluence_function_n con_fun_n;
239 df_transfer_function trans_fun;
240 df_finalizer_function finalize_fun;
241 df_free_function free_fun;
242 df_remove_problem_function remove_problem_fun;
243 df_dump_problem_function dump_start_fun;
244 df_dump_bb_problem_function dump_top_fun;
245 df_dump_bb_problem_function dump_bottom_fun;
246 df_verify_solution_start verify_start_fun;
247 df_verify_solution_end verify_end_fun;
248 struct df_problem *dependent_problem;
250 /* The timevar id associated with this pass. */
253 /* True if the df_set_blocks should null out the basic block info if
254 this block drops out of df->blocks_to_analyze. */
255 bool free_blocks_on_set_blocks;
259 /* The specific instance of the problem to solve. */
262 struct df_problem *problem; /* The problem to be solved. */
264 /* Array indexed by bb->index, that contains basic block problem and
265 solution specific information. */
267 unsigned int block_info_size;
269 /* The pool to allocate the block_info from. */
270 alloc_pool block_pool;
272 /* The lr and live problems have their transfer functions recomputed
273 only if necessary. This is possible for them because, the
274 problems are kept active for the entire backend and their
275 transfer functions are indexed by the REGNO. These are not
276 defined for any other problem. */
277 bitmap out_of_date_transfer_functions;
279 /* Other problem specific data that is not on a per basic block
280 basis. The structure is generally defined privately for the
281 problem. The exception being the scanning problem where it is
285 /* Local flags for some of the problems. */
286 unsigned int local_flags;
288 /* True if this problem of this instance has been initialized. This
289 is used by the dumpers to keep garbage out of the dumps if, for
290 debugging a dump is produced before the first call to
291 df_analyze after a new problem is added. */
294 /* True if the something has changed which invalidates the dataflow
295 solutions. Note that this bit is always true for all problems except
297 bool solutions_dirty;
299 /* If true, this pass is deleted by df_finish_pass. This is never
300 true for DF_SCAN and DF_LR. It is true for DF_LIVE if optimize >
301 1. It is always true for the other problems. */
306 /* The set of multiword hardregs used as operands to this
307 instruction. These are factored into individual uses and defs but
308 the aggregate is still needed to service the REG_DEAD and
312 rtx mw_reg; /* The multiword hardreg. */
313 /* These two bitfields are intentionally oversized, in the hope that
314 accesses to 16-bit fields will usually be quicker. */
315 ENUM_BITFIELD(df_ref_type) type : 16;
316 /* Used to see if the ref is read or write. */
317 ENUM_BITFIELD(df_ref_flags) flags : 16;
319 unsigned int start_regno; /* First word of the multi word subreg. */
320 unsigned int end_regno; /* Last word of the multi word subreg. */
321 unsigned int mw_order; /* Same as df_ref.ref_order. */
325 /* One of these structures is allocated for every insn. */
328 rtx insn; /* The insn this info comes from. */
329 struct df_ref **defs; /* Head of insn-def chain. */
330 struct df_ref **uses; /* Head of insn-use chain. */
331 /* Head of insn-use chain for uses in REG_EQUAL/EQUIV notes. */
332 struct df_ref **eq_uses;
333 struct df_mw_hardreg **mw_hardregs;
334 /* The logical uid of the insn in the basic block. This is valid
335 after any call to df_analyze but may rot after insns are added,
341 /* Define a register reference structure. One of these is allocated
342 for every register reference (use or def). Note some register
343 references (e.g., post_inc, subreg) generate both a def and a use. */
346 rtx reg; /* The register referenced. */
347 basic_block bb; /* Basic block containing the instruction. */
349 /* Insn containing ref. This will be null if this is an artificial
352 rtx *loc; /* The location of the reg. */
353 struct df_link *chain; /* Head of def-use, use-def. */
354 /* Location in the ref table. This is only valid after a call to
355 df_maybe_reorganize_[use,def]_refs which is an expensive operation. */
357 /* The index at which the operand was scanned in the insn. This is
358 used to totally order the refs in an insn. */
359 unsigned int ref_order;
361 unsigned int regno; /* The register number referenced. */
362 /* These two bitfields are intentionally oversized, in the hope that
363 accesses to 16-bit fields will usually be quicker. */
364 ENUM_BITFIELD(df_ref_type) type : 16;
366 ENUM_BITFIELD(df_ref_flags) flags : 16;
369 /* For each regno, there are three chains of refs, one for the uses,
370 the eq_uses and the defs. These chains go thru the refs
371 themselves rather than using an external structure. */
372 struct df_ref *next_reg; /* Next ref with same regno and type. */
373 struct df_ref *prev_reg; /* Prev ref with same regno and type. */
376 /* These links are used for two purposes:
377 1) def-use or use-def chains.
378 2) Multiword hard registers that underly a single hardware register. */
382 struct df_link *next;
388 /* Flags that control the building of chains. */
389 DF_DU_CHAIN = 1, /* Build DU chains. */
390 DF_UD_CHAIN = 2 /* Build UD chains. */
393 enum df_changeable_flags
395 /* Scanning flags. */
396 /* Flag to control the running of dce as a side effect of building LR. */
397 DF_LR_RUN_DCE = 1, /* Run DCE. */
398 DF_NO_HARD_REGS = 2, /* Skip hard registers in RD and CHAIN Building. */
399 DF_EQ_NOTES = 4, /* Build chains with uses present in EQUIV/EQUAL notes. */
400 DF_NO_REGS_EVER_LIVE = 8, /* Do not compute the regs_ever_live. */
402 /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
403 return immediately. This is used by passes that know how to update
404 the scanning them selves. */
405 DF_NO_INSN_RESCAN = 16,
407 /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
408 return after marking the insn for later processing. This allows all
409 rescans to be batched. */
410 DF_DEFER_INSN_RESCAN = 32,
412 DF_VERIFY_SCHEDULED = 64
415 /* Two of these structures are inline in df, one for the uses and one
416 for the defs. This structure is only contains the refs within the
417 boundary of the df_set_blocks if that has been defined. */
420 struct df_ref **refs; /* Ref table, indexed by id. */
421 unsigned int *begin; /* First ref_index for this pseudo. */
422 unsigned int *count; /* Count of refs for this pseudo. */
423 unsigned int refs_size; /* Size of currently allocated refs table. */
425 /* Table_size is the number of elements in the refs table. This
426 will also be the width of the bitvectors in the rd and ru
427 problems. Total_size is the number of refs. These will be the
428 same if the focus has not been reduced by df_set_blocks. If the
429 focus has been reduced, table_size will be smaller since it only
430 contains the refs in the set blocks. */
431 unsigned int table_size;
432 unsigned int total_size;
434 enum df_ref_order ref_order;
437 /* Three of these structures are allocated for every pseudo reg. One
438 for the uses, one for the eq_uses and one for the defs. */
441 /* Head of chain for refs of that type and regno. */
442 struct df_ref *reg_chain;
443 /* Number of refs in the chain. */
448 /*----------------------------------------------------------------------------
449 Problem data for the scanning dataflow problem. Unlike the other
450 dataflow problems, the problem data for scanning is fully exposed and
451 used by owners of the problem.
452 ----------------------------------------------------------------------------*/
457 /* The set of problems to be solved is stored in two arrays. In
458 PROBLEMS_IN_ORDER, the problems are stored in the order that they
459 are solved. This is an internally dense array that may have
460 nulls at the end of it. In PROBLEMS_BY_INDEX, the problem is
461 stored by the value in df_problem.id. These are used to access
462 the problem local data without having to search the first
465 struct dataflow *problems_in_order[DF_LAST_PROBLEM_PLUS1];
466 struct dataflow *problems_by_index[DF_LAST_PROBLEM_PLUS1];
467 int num_problems_defined;
469 /* If not NULL, this subset of blocks of the program to be
470 considered for analysis. At certain times, this will contain all
471 the blocks in the function so it cannot be used as an indicator
472 of if we are analyzing a subset. See analyze_subset. */
473 bitmap blocks_to_analyze;
475 /* If this is true, then only a subset of the blocks of the program
476 is considered to compute the solutions of dataflow problems. */
479 /* True if someone added or deleted something from regs_ever_live so
480 that the entry and exit blocks need be reprocessed. */
481 bool redo_entry_and_exit;
483 /* The following information is really the problem data for the
484 scanning instance but it is used too often by the other problems
485 to keep getting it from there. */
486 struct df_ref_info def_info; /* Def info. */
487 struct df_ref_info use_info; /* Use info. */
489 /* The following three arrays are allocated in parallel. They contain
490 the sets of refs of each type for each reg. */
491 struct df_reg_info **def_regs; /* Def reg info. */
492 struct df_reg_info **use_regs; /* Eq_use reg info. */
493 struct df_reg_info **eq_use_regs; /* Eq_use info. */
494 unsigned int regs_size; /* Size of currently allocated regs table. */
495 unsigned int regs_inited; /* Number of regs with reg_infos allocated. */
498 struct df_insn_info **insns; /* Insn table, indexed by insn UID. */
499 unsigned int insns_size; /* Size of insn table. */
500 bitmap hardware_regs_used; /* The set of hardware registers used. */
501 /* The set of hard regs that are in the artificial uses at the end
502 of a regular basic block. */
503 bitmap regular_block_artificial_uses;
504 /* The set of hard regs that are in the artificial uses at the end
505 of a basic block that has an EH pred. */
506 bitmap eh_block_artificial_uses;
507 /* The set of hardware registers live on entry to the function. */
508 bitmap entry_block_defs;
509 bitmap exit_block_uses; /* The set of hardware registers used in exit block. */
511 /* Insns to delete, rescan or reprocess the notes at next
512 df_rescan_all or df_process_deferred_rescans. */
513 bitmap insns_to_delete;
514 bitmap insns_to_rescan;
515 bitmap insns_to_notes_rescan;
516 int *postorder; /* The current set of basic blocks
517 in reverse postorder. */
518 int *postorder_inverted; /* The current set of basic blocks
519 in reverse postorder of inverted CFG. */
520 int n_blocks; /* The number of blocks in reverse postorder. */
521 int n_blocks_inverted; /* The number of blocks
522 in reverse postorder of inverted CFG. */
524 /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number
525 of refs that qualify as being real hard regs uses. Artificial
526 uses and defs as well as refs in eq notes are ignored. If the
527 ref is a def, it cannot be a MAY_CLOBBER def. If the ref is a
528 use, it cannot be the emim_reg_set or be the frame or arg pointer
531 IT IS NOT ACCEPTABLE TO MANUALLY CHANGE THIS ARRAY. This array
532 always reflects the actual number of refs in the insn stream that
533 satisfy the above criteria. */
534 unsigned int *hard_regs_live_count;
536 /* This counter provides a way to totally order refs without using
537 addresses. It is incremented whenever a ref is created. */
538 unsigned int ref_order;
540 /* Problem specific control information. */
541 enum df_changeable_flags changeable_flags;
544 #define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info((BB)->index))
545 #define DF_RD_BB_INFO(BB) (df_rd_get_bb_info((BB)->index))
546 #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index))
547 #define DF_UREC_BB_INFO(BB) (df_urec_get_bb_info((BB)->index))
548 #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index))
550 /* Most transformations that wish to use live register analysis will
551 use these macros. This info is the and of the lr and live sets. */
552 #define DF_LIVE_IN(BB) (DF_LIVE_BB_INFO(BB)->in)
553 #define DF_LIVE_OUT(BB) (DF_LIVE_BB_INFO(BB)->out)
556 /* Live in for register allocation also takes into account several other factors. */
557 #define DF_RA_LIVE_IN(BB) (DF_UREC_BB_INFO(BB)->in)
558 #define DF_RA_LIVE_TOP(BB) (DF_UREC_BB_INFO(BB)->top)
559 #define DF_RA_LIVE_OUT(BB) (DF_UREC_BB_INFO(BB)->out)
561 /* These macros are currently used by only reg-stack since it is not
562 tolerant of uninitialized variables. This intolerance should be
563 fixed because it causes other problems. */
564 #define DF_LR_IN(BB) (DF_LR_BB_INFO(BB)->in)
565 #define DF_LR_TOP(BB) (DF_LR_BB_INFO(BB)->top)
566 #define DF_LR_OUT(BB) (DF_LR_BB_INFO(BB)->out)
568 /* Macros to access the elements within the ref structure. */
571 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
572 ? SUBREG_REG ((REF)->reg) : ((REF)->reg))
573 #define DF_REF_REGNO(REF) ((REF)->regno)
574 #define DF_REF_REAL_LOC(REF) (GET_CODE (*((REF)->loc)) == SUBREG \
575 ? &SUBREG_REG (*((REF)->loc)) : ((REF)->loc))
576 #define DF_REF_REG(REF) ((REF)->reg)
577 #define DF_REF_LOC(REF) ((REF)->loc)
578 #define DF_REF_BB(REF) ((REF)->bb)
579 #define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index)
580 #define DF_REF_INSN(REF) ((REF)->insn)
581 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
582 #define DF_REF_TYPE(REF) ((REF)->type)
583 #define DF_REF_CHAIN(REF) ((REF)->chain)
584 #define DF_REF_ID(REF) ((REF)->id)
585 #define DF_REF_FLAGS(REF) ((REF)->flags)
586 #define DF_REF_FLAGS_IS_SET(REF, v) ((DF_REF_FLAGS (REF) & (v)) != 0)
587 #define DF_REF_FLAGS_SET(REF, v) (DF_REF_FLAGS (REF) |= (v))
588 #define DF_REF_FLAGS_CLEAR(REF, v) (DF_REF_FLAGS (REF) &= ~(v))
589 #define DF_REF_ORDER(REF) ((REF)->ref_order)
590 /* If DF_REF_IS_ARTIFICIAL () is true, this is not a real definition/use,
591 but an artificial one created to model
592 always live registers, eh uses, etc.
593 ARTIFICIAL refs has NULL insn. */
594 #define DF_REF_IS_ARTIFICIAL(REF) ((REF)->insn == NULL)
595 #define DF_REF_REG_MARK(REF) (DF_REF_FLAGS_SET ((REF),DF_REF_REG_MARKER))
596 #define DF_REF_REG_UNMARK(REF) (DF_REF_FLAGS_CLEAR ((REF),DF_REF_REG_MARKER))
597 #define DF_REF_IS_REG_MARKED(REF) (DF_REF_FLAGS_IS_SET ((REF),DF_REF_REG_MARKER))
598 #define DF_REF_NEXT_REG(REF) ((REF)->next_reg)
599 #define DF_REF_PREV_REG(REF) ((REF)->prev_reg)
601 /* Macros to determine the reference type. */
603 #define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF)
604 #define DF_REF_REG_USE_P(REF) ((REF) && !DF_REF_REG_DEF_P (REF))
605 #define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE)
606 #define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD)
607 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
608 || DF_REF_REG_MEM_LOAD_P (REF))
610 /* Macros to get the refs out of def_info or use_info refs table. If
611 the focus of the dataflow has been set to some subset of blocks
612 with df_set_blocks, these macros will only find the uses and defs
613 in that subset of blocks.
615 These macros should be used with care. The def macros are only
616 usable after a call to df_maybe_reorganize_def_refs and the use
617 macros are only usable after a call to
618 df_maybe_reorganize_use_refs. HOWEVER, BUILDING AND USING THESE
619 ARRAYS ARE A CACHE LOCALITY KILLER. */
621 #define DF_DEFS_TABLE_SIZE() (df->def_info.table_size)
622 #define DF_DEFS_GET(ID) (df->def_info.refs[(ID)])
623 #define DF_DEFS_SET(ID,VAL) (df->def_info.refs[(ID)]=(VAL))
624 #define DF_DEFS_COUNT(ID) (df->def_info.count[(ID)])
625 #define DF_DEFS_BEGIN(ID) (df->def_info.begin[(ID)])
626 #define DF_USES_TABLE_SIZE() (df->use_info.table_size)
627 #define DF_USES_GET(ID) (df->use_info.refs[(ID)])
628 #define DF_USES_SET(ID,VAL) (df->use_info.refs[(ID)]=(VAL))
629 #define DF_USES_COUNT(ID) (df->use_info.count[(ID)])
630 #define DF_USES_BEGIN(ID) (df->use_info.begin[(ID)])
632 /* Macros to access the register information from scan dataflow record. */
634 #define DF_REG_SIZE(DF) (df->regs_inited)
635 #define DF_REG_DEF_GET(REG) (df->def_regs[(REG)])
636 #define DF_REG_DEF_CHAIN(REG) (df->def_regs[(REG)]->reg_chain)
637 #define DF_REG_DEF_COUNT(REG) (df->def_regs[(REG)]->n_refs)
638 #define DF_REG_USE_GET(REG) (df->use_regs[(REG)])
639 #define DF_REG_USE_CHAIN(REG) (df->use_regs[(REG)]->reg_chain)
640 #define DF_REG_USE_COUNT(REG) (df->use_regs[(REG)]->n_refs)
641 #define DF_REG_EQ_USE_GET(REG) (df->eq_use_regs[(REG)])
642 #define DF_REG_EQ_USE_CHAIN(REG) (df->eq_use_regs[(REG)]->reg_chain)
643 #define DF_REG_EQ_USE_COUNT(REG) (df->eq_use_regs[(REG)]->n_refs)
645 /* Macros to access the elements within the reg_info structure table. */
647 #define DF_REGNO_FIRST_DEF(REGNUM) \
648 (DF_REG_DEF_GET(REGNUM) ? DF_REG_DEF_GET(REGNUM) : 0)
649 #define DF_REGNO_LAST_USE(REGNUM) \
650 (DF_REG_USE_GET(REGNUM) ? DF_REG_USE_GET(REGNUM) : 0)
652 /* Macros to access the elements within the insn_info structure table. */
654 #define DF_INSN_SIZE() ((df)->insns_size)
655 #define DF_INSN_GET(INSN) (df->insns[(INSN_UID(INSN))])
656 #define DF_INSN_SET(INSN,VAL) (df->insns[(INSN_UID (INSN))]=(VAL))
657 #define DF_INSN_LUID(INSN) (DF_INSN_GET(INSN)->luid)
658 #define DF_INSN_DEFS(INSN) (DF_INSN_GET(INSN)->defs)
659 #define DF_INSN_USES(INSN) (DF_INSN_GET(INSN)->uses)
660 #define DF_INSN_EQ_USES(INSN) (DF_INSN_GET(INSN)->eq_uses)
662 #define DF_INSN_UID_GET(UID) (df->insns[(UID)])
663 #define DF_INSN_UID_SET(UID,VAL) (df->insns[(UID)]=(VAL))
664 #define DF_INSN_UID_SAFE_GET(UID) (((unsigned)(UID) < DF_INSN_SIZE()) \
665 ? DF_INSN_UID_GET (UID) \
667 #define DF_INSN_UID_LUID(INSN) (DF_INSN_UID_GET(INSN)->luid)
668 #define DF_INSN_UID_DEFS(INSN) (DF_INSN_UID_GET(INSN)->defs)
669 #define DF_INSN_UID_USES(INSN) (DF_INSN_UID_GET(INSN)->uses)
670 #define DF_INSN_UID_EQ_USES(INSN) (DF_INSN_UID_GET(INSN)->eq_uses)
671 #define DF_INSN_UID_MWS(INSN) (DF_INSN_UID_GET(INSN)->mw_hardregs)
673 /* An obstack for bitmap not related to specific dataflow problems.
674 This obstack should e.g. be used for bitmaps with a short life time
675 such as temporary bitmaps. This obstack is declared in df-core.c. */
677 extern bitmap_obstack df_bitmap_obstack;
679 /* This is a bitmap copy of regs_invalidated_by_call so that we can
680 easily add it into bitmaps, etc. */
682 extern bitmap df_invalidated_by_call;
685 /* One of these structures is allocated for every basic block. */
686 struct df_scan_bb_info
688 /* Defs at the start of a basic block that is the target of an
690 struct df_ref **artificial_defs;
692 /* Uses of hard registers that are live at every block. */
693 struct df_ref **artificial_uses;
697 /* Reaching definitions. All bitmaps are indexed by the id field of
698 the ref except sparse_kill (see above). */
701 /* Local sets to describe the basic blocks. See the note in the RU
702 datastructures for kill and sparse_kill. */
705 bitmap gen; /* The set of defs generated in this block. */
707 /* The results of the dataflow problem. */
708 bitmap in; /* At the top of the block. */
709 bitmap out; /* At the bottom of the block. */
713 /* Live registers. All bitmaps are referenced by the register number.
715 df_lr_bb_info:IN is the "in" set of the traditional dataflow sense
716 which is the confluence of out sets of all predecessor blocks.
717 The difference between IN and TOP is
718 due to the artificial defs and uses at the top (DF_REF_TOP)
719 (e.g. exception handling dispatch block, which can have
720 a few registers defined by the runtime) - which is NOT included
721 in the "in" set before this function but is included after.
722 For the initial live set of forward scanning, TOP should be used
723 instead of IN - otherwise, artificial defs won't be in IN set
724 causing the bad transformation. TOP set can not simply be
725 the union of IN set and artificial defs at the top,
726 because artificial defs might not be used at all,
727 in which case those defs are not live at any point
728 (except as a dangling def) - hence TOP has to be calculated
729 during the LR problem computation and stored in df_lr_bb_info. */
733 /* Local sets to describe the basic blocks. */
734 bitmap def; /* The set of registers set in this block
735 - except artificial defs at the top. */
736 bitmap use; /* The set of registers used in this block. */
737 bitmap adef; /* The artificial defs at top. */
738 bitmap ause; /* The artificial uses at top. */
740 /* The results of the dataflow problem. */
741 bitmap in; /* Just before the block itself. */
742 bitmap top; /* Just before the first insn in the block. */
743 bitmap out; /* At the bottom of the block. */
747 /* Uninitialized registers. All bitmaps are referenced by the
748 register number. Anded results of the forwards and backward live
749 info. Note that the forwards live information is not available
751 struct df_live_bb_info
753 /* Local sets to describe the basic blocks. */
754 bitmap kill; /* The set of registers unset in this block. Calls,
755 for instance, unset registers. */
756 bitmap gen; /* The set of registers set in this block. */
758 /* The results of the dataflow problem. */
759 bitmap in; /* At the top of the block. */
760 bitmap out; /* At the bottom of the block. */
764 /* Uninitialized registers. All bitmaps are referenced by the register number. */
765 struct df_urec_bb_info
767 /* Local sets to describe the basic blocks. */
768 bitmap earlyclobber; /* The set of registers that are referenced
769 with an early clobber mode. */
770 /* Kill and gen are defined as in the UR problem. */
774 /* The results of the dataflow problem. */
775 bitmap in; /* Just before the block. */
776 bitmap top; /* Just before the first insn in the block. */
777 bitmap out; /* At the bottom of the block. */
781 /* This is used for debugging and for the dumpers to find the latest
782 instance so that the df info can be added to the dumps. This
783 should not be used by regular code. */
784 extern struct df *df;
785 #define df_scan (df->problems_by_index[DF_SCAN])
786 #define df_rd (df->problems_by_index[DF_RD])
787 #define df_lr (df->problems_by_index[DF_LR])
788 #define df_live (df->problems_by_index[DF_LIVE])
789 #define df_urec (df->problems_by_index[DF_UREC])
790 #define df_chain (df->problems_by_index[DF_CHAIN])
791 #define df_note (df->problems_by_index[DF_NOTE])
793 /* This symbol turns on checking that each modification of the cfg has
794 been identified to the appropriate df routines. It is not part of
795 verification per se because the check that the final solution has
796 not changed covers this. However, if the solution is not being
797 properly recomputed because the cfg is being modified, adding in
798 calls to df_check_cfg_clean can be used to find the source of that
805 /* Functions defined in df-core.c. */
807 extern void df_add_problem (struct df_problem *);
808 extern enum df_changeable_flags df_set_flags (enum df_changeable_flags);
809 extern enum df_changeable_flags df_clear_flags (enum df_changeable_flags);
810 extern void df_set_blocks (bitmap);
811 extern void df_remove_problem (struct dataflow *);
812 extern void df_finish_pass (bool);
813 extern void df_analyze_problem (struct dataflow *, bitmap, int *, int);
814 extern void df_analyze (void);
815 extern int df_get_n_blocks (enum df_flow_dir);
816 extern int *df_get_postorder (enum df_flow_dir);
817 extern void df_simple_dataflow (enum df_flow_dir, df_init_function,
818 df_confluence_function_0, df_confluence_function_n,
819 df_transfer_function, bitmap, int *, int);
820 extern void df_mark_solutions_dirty (void);
821 extern bool df_get_bb_dirty (basic_block);
822 extern void df_set_bb_dirty (basic_block);
823 extern void df_compact_blocks (void);
824 extern void df_bb_replace (int, basic_block);
825 extern void df_bb_delete (int);
826 extern void df_verify (void);
828 extern void df_check_cfg_clean (void);
830 extern struct df_ref *df_bb_regno_first_def_find (basic_block, unsigned int);
831 extern struct df_ref *df_bb_regno_last_def_find (basic_block, unsigned int);
832 extern struct df_ref *df_find_def (rtx, rtx);
833 extern bool df_reg_defined (rtx, rtx);
834 extern struct df_ref *df_find_use (rtx, rtx);
835 extern bool df_reg_used (rtx, rtx);
836 extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int);
837 extern void df_print_regset (FILE *file, bitmap r);
838 extern void df_dump (FILE *);
839 extern void df_dump_region (FILE *);
840 extern void df_dump_start (FILE *);
841 extern void df_dump_top (basic_block, FILE *);
842 extern void df_dump_bottom (basic_block, FILE *);
843 extern void df_refs_chain_dump (struct df_ref **, bool, FILE *);
844 extern void df_regs_chain_dump (struct df_ref *, FILE *);
845 extern void df_insn_debug (rtx, bool, FILE *);
846 extern void df_insn_debug_regno (rtx, FILE *);
847 extern void df_regno_debug (unsigned int, FILE *);
848 extern void df_ref_debug (struct df_ref *, FILE *);
849 extern void debug_df_insn (rtx);
850 extern void debug_df_regno (unsigned int);
851 extern void debug_df_reg (rtx);
852 extern void debug_df_defno (unsigned int);
853 extern void debug_df_useno (unsigned int);
854 extern void debug_df_ref (struct df_ref *);
855 extern void debug_df_chain (struct df_link *);
857 /* Functions defined in df-problems.c. */
859 extern struct df_link *df_chain_create (struct df_ref *, struct df_ref *);
860 extern void df_chain_unlink (struct df_ref *);
861 extern void df_chain_copy (struct df_ref *, struct df_link *);
862 extern bitmap df_get_live_in (basic_block);
863 extern bitmap df_get_live_out (basic_block);
864 extern bitmap df_get_live_top (basic_block);
865 extern void df_grow_bb_info (struct dataflow *);
866 extern void df_chain_dump (struct df_link *, FILE *);
867 extern void df_print_bb_index (basic_block bb, FILE *file);
868 extern void df_rd_add_problem (void);
869 extern void df_lr_add_problem (void);
870 extern void df_lr_verify_transfer_functions (void);
871 extern void df_live_verify_transfer_functions (void);
872 extern void df_live_add_problem (void);
873 extern void df_live_set_all_dirty (void);
874 extern void df_urec_add_problem (void);
875 extern void df_chain_add_problem (enum df_chain_flags);
876 extern void df_note_add_problem (void);
877 extern void df_simulate_find_defs (rtx, bitmap);
878 extern void df_simulate_defs (rtx, bitmap);
879 extern void df_simulate_uses (rtx, bitmap);
880 extern void df_simulate_artificial_refs_at_top (basic_block, bitmap);
881 extern void df_simulate_one_insn_forwards (basic_block, rtx, bitmap);
882 extern void df_simulate_artificial_refs_at_end (basic_block, bitmap);
883 extern void df_simulate_one_insn_backwards (basic_block, rtx, bitmap);
885 /* Functions defined in df-scan.c. */
887 extern void df_scan_alloc (bitmap);
888 extern void df_scan_add_problem (void);
889 extern void df_grow_reg_info (void);
890 extern void df_grow_insn_info (void);
891 extern void df_scan_blocks (void);
892 extern struct df_ref *df_ref_create (rtx, rtx *, rtx,basic_block,
893 enum df_ref_type, enum df_ref_flags);
894 extern void df_ref_remove (struct df_ref *);
895 extern struct df_insn_info * df_insn_create_insn_record (rtx);
896 extern void df_insn_delete (basic_block, unsigned int);
897 extern void df_bb_refs_record (int, bool);
898 extern bool df_insn_rescan (rtx);
899 extern void df_insn_rescan_all (void);
900 extern void df_process_deferred_rescans (void);
901 extern bool df_has_eh_preds (basic_block);
902 extern void df_recompute_luids (basic_block);
903 extern void df_insn_change_bb (rtx);
904 extern void df_maybe_reorganize_use_refs (enum df_ref_order);
905 extern void df_maybe_reorganize_def_refs (enum df_ref_order);
906 extern void df_ref_change_reg_with_loc (int, int, rtx);
907 extern void df_notes_rescan (rtx);
908 extern void df_hard_reg_init (void);
909 extern void df_update_entry_block_defs (void);
910 extern void df_update_exit_block_uses (void);
911 extern void df_update_entry_exit_and_calls (void);
912 extern bool df_hard_reg_used_p (unsigned int);
913 extern unsigned int df_hard_reg_used_count (unsigned int);
914 extern bool df_regs_ever_live_p (unsigned int);
915 extern void df_set_regs_ever_live (unsigned int, bool);
916 extern void df_compute_regs_ever_live (bool);
917 extern bool df_read_modify_subreg_p (rtx);
918 extern void df_scan_verify (void);
921 /* Get basic block info. */
923 static inline struct df_scan_bb_info *
924 df_scan_get_bb_info (unsigned int index)
926 if (index < df_scan->block_info_size)
927 return (struct df_scan_bb_info *) df_scan->block_info[index];
932 static inline struct df_rd_bb_info *
933 df_rd_get_bb_info (unsigned int index)
935 if (index < df_rd->block_info_size)
936 return (struct df_rd_bb_info *) df_rd->block_info[index];
941 static inline struct df_lr_bb_info *
942 df_lr_get_bb_info (unsigned int index)
944 if (index < df_lr->block_info_size)
945 return (struct df_lr_bb_info *) df_lr->block_info[index];
950 static inline struct df_live_bb_info *
951 df_live_get_bb_info (unsigned int index)
953 if (index < df_live->block_info_size)
954 return (struct df_live_bb_info *) df_live->block_info[index];
959 static inline struct df_urec_bb_info *
960 df_urec_get_bb_info (unsigned int index)
962 if (index < df_urec->block_info_size)
963 return (struct df_urec_bb_info *) df_urec->block_info[index];
969 /* Get the artificial defs for a basic block. */
971 static inline struct df_ref **
972 df_get_artificial_defs (unsigned int bb_index)
974 return df_scan_get_bb_info (bb_index)->artificial_defs;
978 /* Get the artificial uses for a basic block. */
980 static inline struct df_ref **
981 df_get_artificial_uses (unsigned int bb_index)
983 return df_scan_get_bb_info (bb_index)->artificial_uses;
989 /* This entry is allocated for each reference in the insn stream. */
992 /* Pointer to the parent in the union/find tree. */
993 struct web_entry *pred;
994 /* Newly assigned register to the entry. Set only for roots. */
999 extern struct web_entry *unionfind_root (struct web_entry *);
1000 extern bool unionfind_union (struct web_entry *, struct web_entry *);
1001 extern void union_defs (struct df_ref *,
1002 struct web_entry *, struct web_entry *,
1003 bool (*fun) (struct web_entry *, struct web_entry *));
1005 #endif /* GCC_DF_H */
OSDN Git Service
