190075Sobrien/* Form lists of pseudo register references for autoinc optimization 2132718Skan for GNU compiler. This is part of flow optimization. 3169689Skan Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005, 2006 4169689Skan Free Software Foundation, Inc. 5169689Skan Originally contributed by Michael P. Hayes 6169689Skan (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) 7169689Skan Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) 8169689Skan and Kenneth Zadeck (zadeck@naturalbridge.com). 990075Sobrien 1090075SobrienThis file is part of GCC. 1190075Sobrien 1290075SobrienGCC is free software; you can redistribute it and/or modify it under 1390075Sobrienthe terms of the GNU General Public License as published by the Free 1490075SobrienSoftware Foundation; either version 2, or (at your option) any later 1590075Sobrienversion. 1690075Sobrien 1790075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1890075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1990075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 2090075Sobrienfor more details. 2190075Sobrien 2290075SobrienYou should have received a copy of the GNU General Public License 2390075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 24169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 25169689Skan02110-1301, USA. */ 2690075Sobrien 27169689Skan#ifndef GCC_DF_H 28169689Skan#define GCC_DF_H 2990075Sobrien 30169689Skan#include "bitmap.h" 31169689Skan#include "basic-block.h" 32169689Skan#include "alloc-pool.h" 33169689Skan 34169689Skanstruct dataflow; 35169689Skanstruct df; 36169689Skanstruct df_problem; 37169689Skanstruct df_link; 38169689Skan 39169689Skan/* Data flow problems. All problems must have a unique here. */ 40169689Skan/* Scanning is not really a dataflow problem, but it is useful to have 41169689Skan the basic block functions in the vector so that things get done in 42169689Skan a uniform manner. */ 43169689Skan#define DF_SCAN 0 44169689Skan#define DF_RU 1 /* Reaching Uses. */ 45169689Skan#define DF_RD 2 /* Reaching Defs. */ 46169689Skan#define DF_LR 3 /* Live Registers. */ 47169689Skan#define DF_UR 4 /* Uninitialized Registers. */ 48169689Skan#define DF_UREC 5 /* Uninitialized Registers with Early Clobber. */ 49169689Skan#define DF_CHAIN 6 /* Def-Use and/or Use-Def Chains. */ 50169689Skan#define DF_RI 7 /* Register Info. */ 51169689Skan#define DF_LAST_PROBLEM_PLUS1 (DF_RI + 1) 52169689Skan 53169689Skan 54169689Skan/* Dataflow direction. */ 55169689Skanenum df_flow_dir 56169689Skan { 57169689Skan DF_NONE, 58169689Skan DF_FORWARD, 59169689Skan DF_BACKWARD 60169689Skan }; 61169689Skan 62169689Skan 63169689Skan/* The first of these is a set of a register. The remaining three are 64169689Skan all uses of a register (the mem_load and mem_store relate to how 65169689Skan the register as an addressing operand). */ 6690075Sobrienenum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD, 6790075Sobrien DF_REF_REG_MEM_STORE}; 6890075Sobrien 6990075Sobrien#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"} 7090075Sobrien 7190075Sobrienenum df_ref_flags 7290075Sobrien { 73132718Skan /* Read-modify-write refs generate both a use and a def and 74132718Skan these are marked with this flag to show that they are not 75132718Skan independent. */ 76117395Skan DF_REF_READ_WRITE = 1, 77117395Skan 78132718Skan /* This flag is set, if we stripped the subreg from the reference. 79132718Skan In this case we must make conservative guesses, at what the 80132718Skan outer mode was. */ 81169689Skan DF_REF_STRIPPED = 2, 82169689Skan 83169689Skan /* If this flag is set, this is not a real definition/use, but an 84169689Skan artificial one created to model always live registers, eh uses, etc. */ 85169689Skan DF_REF_ARTIFICIAL = 4, 86132718Skan 87169689Skan 88169689Skan /* If this flag is set for an artificial use or def, that ref 89169689Skan logically happens at the top of the block. If it is not set 90169689Skan for an artificial use or def, that ref logically happens at the 91169689Skan bottom of the block. This is never set for regular refs. */ 92169689Skan DF_REF_AT_TOP = 8, 93169689Skan 94169689Skan /* This flag is set if the use is inside a REG_EQUAL note. */ 95169689Skan DF_REF_IN_NOTE = 16, 96169689Skan 97169689Skan /* This flag is set if this ref, generally a def, may clobber the 98169689Skan referenced register. This is generally only set for hard 99169689Skan registers that cross a call site. With better information 100169689Skan about calls, some of these could be changed in the future to 101169689Skan DF_REF_MUST_CLOBBER. */ 102169689Skan DF_REF_MAY_CLOBBER = 32, 103169689Skan 104169689Skan /* This flag is set if this ref, generally a def, is a real 105169689Skan clobber. This is not currently set for registers live across a 106169689Skan call because that clobbering may or may not happen. 107169689Skan 108169689Skan Most of the uses of this are with sets that have a 109169689Skan GET_CODE(..)==CLOBBER. Note that this is set even if the 110169689Skan clobber is to a subreg. So in order to tell if the clobber 111169689Skan wipes out the entire register, it is necessary to also check 112169689Skan the DF_REF_PARTIAL flag. */ 113169689Skan DF_REF_MUST_CLOBBER = 64, 114169689Skan 115169689Skan /* This bit is true if this ref is part of a multiword hardreg. */ 116169689Skan DF_REF_MW_HARDREG = 128, 117169689Skan 118169689Skan /* This flag is set if this ref is a partial use or def of the 119169689Skan associated register. */ 120169689Skan DF_REF_PARTIAL = 256 12190075Sobrien }; 12290075Sobrien 123132718Skan 124169689Skan/* Function prototypes added to df_problem instance. */ 125169689Skan 126169689Skan/* Allocate the problem specific data. */ 127169689Skantypedef void (*df_alloc_function) (struct dataflow *, bitmap, bitmap); 128169689Skan 129169689Skan/* This function is called if the problem has global data that needs 130169689Skan to be cleared when ever the set of blocks changes. The bitmap 131169689Skan contains the set of blocks that may require special attention. 132169689Skan This call is only made if some of the blocks are going to change. 133169689Skan If everything is to be deleted, the wholesale deletion mechanisms 134169689Skan apply. */ 135169689Skantypedef void (*df_reset_function) (struct dataflow *, bitmap); 136169689Skan 137169689Skan/* Free the basic block info. Called from the block reordering code 138169689Skan to get rid of the blocks that have been squished down. */ 139169689Skantypedef void (*df_free_bb_function) (struct dataflow *, basic_block, void *); 140169689Skan 141169689Skan/* Local compute function. */ 142169689Skantypedef void (*df_local_compute_function) (struct dataflow *, bitmap, bitmap); 143169689Skan 144169689Skan/* Init the solution specific data. */ 145169689Skantypedef void (*df_init_function) (struct dataflow *, bitmap); 146169689Skan 147169689Skan/* Iterative dataflow function. */ 148169689Skantypedef void (*df_dataflow_function) (struct dataflow *, bitmap, bitmap, 149169689Skan int *, int, bool); 150169689Skan 151169689Skan/* Confluence operator for blocks with 0 out (or in) edges. */ 152169689Skantypedef void (*df_confluence_function_0) (struct dataflow *, basic_block); 153169689Skan 154169689Skan/* Confluence operator for blocks with 1 or more out (or in) edges. */ 155169689Skantypedef void (*df_confluence_function_n) (struct dataflow *, edge); 156169689Skan 157169689Skan/* Transfer function for blocks. */ 158169689Skantypedef bool (*df_transfer_function) (struct dataflow *, int); 159169689Skan 160169689Skan/* Function to massage the information after the problem solving. */ 161169689Skantypedef void (*df_finalizer_function) (struct dataflow*, bitmap); 162169689Skan 163169689Skan/* Function to free all of the problem specific datastructures. */ 164169689Skantypedef void (*df_free_function) (struct dataflow *); 165169689Skan 166169689Skan/* Function to dump results to FILE. */ 167169689Skantypedef void (*df_dump_problem_function) (struct dataflow *, FILE *); 168169689Skan 169169689Skan/* Function to add problem a dataflow problem that must be solved 170169689Skan before this problem can be solved. */ 171169689Skantypedef struct dataflow * (*df_dependent_problem_function) (struct df *, int); 172169689Skan 173169689Skan/* The static description of a dataflow problem to solve. See above 174169689Skan typedefs for doc for the function fields. */ 175169689Skan 176169689Skanstruct df_problem { 177169689Skan /* The unique id of the problem. This is used it index into 178169689Skan df->defined_problems to make accessing the problem data easy. */ 179169689Skan unsigned int id; 180169689Skan enum df_flow_dir dir; /* Dataflow direction. */ 181169689Skan df_alloc_function alloc_fun; 182169689Skan df_reset_function reset_fun; 183169689Skan df_free_bb_function free_bb_fun; 184169689Skan df_local_compute_function local_compute_fun; 185169689Skan df_init_function init_fun; 186169689Skan df_dataflow_function dataflow_fun; 187169689Skan df_confluence_function_0 con_fun_0; 188169689Skan df_confluence_function_n con_fun_n; 189169689Skan df_transfer_function trans_fun; 190169689Skan df_finalizer_function finalize_fun; 191169689Skan df_free_function free_fun; 192169689Skan df_dump_problem_function dump_fun; 193169689Skan df_dependent_problem_function dependent_problem_fun; 194169689Skan 195169689Skan /* Flags can be changed after analysis starts. */ 196169689Skan int changeable_flags; 197169689Skan}; 198169689Skan 199169689Skan 200169689Skan/* The specific instance of the problem to solve. */ 201169689Skanstruct dataflow 20290075Sobrien{ 203169689Skan struct df *df; /* Instance of df we are working in. */ 204169689Skan struct df_problem *problem; /* The problem to be solved. */ 205169689Skan 206169689Skan /* Communication between iterative_dataflow and hybrid_search. */ 207169689Skan sbitmap visited, pending, considered; 208169689Skan 209169689Skan /* Array indexed by bb->index, that contains basic block problem and 210169689Skan solution specific information. */ 211169689Skan void **block_info; 212169689Skan unsigned int block_info_size; 213169689Skan 214169689Skan /* The pool to allocate the block_info from. */ 215169689Skan alloc_pool block_pool; 216169689Skan 217169689Skan /* Problem specific control information. */ 218169689Skan 219169689Skan /* Scanning flags. */ 220169689Skan#define DF_HARD_REGS 1 /* Mark hard registers. */ 221169689Skan#define DF_EQUIV_NOTES 2 /* Mark uses present in EQUIV/EQUAL notes. */ 222169689Skan#define DF_SUBREGS 4 /* Return subregs rather than the inner reg. */ 223169689Skan /* Flags that control the building of chains. */ 224169689Skan#define DF_DU_CHAIN 1 /* Build DU chains. */ 225169689Skan#define DF_UD_CHAIN 2 /* Build UD chains. */ 226169689Skan /* Flag to control the building of register info. */ 227169689Skan#define DF_RI_LIFE 1 /* Build register info. */ 228169689Skan 229169689Skan int flags; 230169689Skan 231169689Skan /* Other problem specific data that is not on a per basic block 232169689Skan basis. The structure is generally defined privately for the 233169689Skan problem. The exception being the scanning problem where it is 234169689Skan fully public. */ 235169689Skan void *problem_data; 236169689Skan}; 237169689Skan 238169689Skan 239169689Skan/* The set of multiword hardregs used as operands to this 240169689Skan instruction. These are factored into individual uses and defs but 241169689Skan the aggregate is still needed to service the REG_DEAD and 242169689Skan REG_UNUSED notes. */ 243169689Skanstruct df_mw_hardreg 244169689Skan{ 245169689Skan rtx mw_reg; /* The multiword hardreg. */ 246169689Skan enum df_ref_type type; /* Used to see if the ref is read or write. */ 24790075Sobrien enum df_ref_flags flags; /* Various flags. */ 248169689Skan struct df_link *regs; /* The individual regs that make up 249169689Skan this hardreg. */ 250169689Skan struct df_mw_hardreg *next; /* The next mw_hardreg in this insn. */ 25190075Sobrien}; 252169689Skan 25390075Sobrien 25490075Sobrien/* One of these structures is allocated for every insn. */ 255169689Skanstruct df_insn_info 25690075Sobrien{ 257169689Skan struct df_ref *defs; /* Head of insn-def chain. */ 258169689Skan struct df_ref *uses; /* Head of insn-use chain. */ 259169689Skan struct df_mw_hardreg *mw_hardregs; 260132718Skan /* ???? The following luid field should be considered private so that 26190075Sobrien we can change it on the fly to accommodate new insns? */ 26290075Sobrien int luid; /* Logical UID. */ 263169689Skan bool contains_asm; /* Contains an asm instruction. */ 26490075Sobrien}; 26590075Sobrien 26690075Sobrien 267169689Skan/* Two of these structures are allocated for every pseudo reg, one for 268169689Skan the uses and one for the defs. */ 269169689Skanstruct df_reg_info 27090075Sobrien{ 271169689Skan struct df_ref *reg_chain; /* Head of reg-use or def chain. */ 272169689Skan unsigned int begin; /* First def_index for this pseudo. */ 273169689Skan unsigned int n_refs; /* Number of refs or defs for this pseudo. */ 27490075Sobrien}; 27590075Sobrien 276169689Skan/* Define a register reference structure. One of these is allocated 277169689Skan for every register reference (use or def). Note some register 278169689Skan references (e.g., post_inc, subreg) generate both a def and a use. */ 279169689Skanstruct df_ref 280169689Skan{ 281169689Skan rtx reg; /* The register referenced. */ 282169689Skan unsigned int regno; /* The register number referenced. */ 283169689Skan basic_block bb; /* Basic block containing the instruction. */ 28490075Sobrien 285169689Skan /* Insn containing ref. This will be null if this is an artificial 286169689Skan reference. */ 287169689Skan rtx insn; 288169689Skan rtx *loc; /* The location of the reg. */ 289169689Skan struct df_link *chain; /* Head of def-use, use-def. */ 290169689Skan unsigned int id; /* Location in table. */ 291169689Skan enum df_ref_type type; /* Type of ref. */ 292169689Skan enum df_ref_flags flags; /* Various flags. */ 293169689Skan 294169689Skan /* For each regno, there are two chains of refs, one for the uses 295169689Skan and one for the defs. These chains go thru the refs themselves 296169689Skan rather than using an external structure. */ 297169689Skan struct df_ref *next_reg; /* Next ref with same regno and type. */ 298169689Skan struct df_ref *prev_reg; /* Prev ref with same regno and type. */ 299169689Skan 300169689Skan /* Each insn has two lists, one for the uses and one for the 301169689Skan defs. This is the next field in either of these chains. */ 302169689Skan struct df_ref *next_ref; 303169689Skan void *data; /* The data assigned to it by user. */ 304169689Skan}; 305169689Skan 306169689Skan/* These links are used for two purposes: 307169689Skan 1) def-use or use-def chains. 308169689Skan 2) Multiword hard registers that underly a single hardware register. */ 309169689Skanstruct df_link 31090075Sobrien{ 311169689Skan struct df_ref *ref; 312169689Skan struct df_link *next; 31390075Sobrien}; 31490075Sobrien 315169689Skan/* Two of these structures are allocated, one for the uses and one for 316169689Skan the defs. */ 317169689Skanstruct df_ref_info 318169689Skan{ 319169689Skan struct df_reg_info **regs; /* Array indexed by pseudo regno. */ 320169689Skan unsigned int regs_size; /* Size of currently allocated regs table. */ 321169689Skan unsigned int regs_inited; /* Number of regs with reg_infos allocated. */ 322169689Skan struct df_ref **refs; /* Ref table, indexed by id. */ 323169689Skan unsigned int refs_size; /* Size of currently allocated refs table. */ 324169689Skan unsigned int bitmap_size; /* Number of refs seen. */ 32590075Sobrien 326169689Skan /* True if refs table is organized so that every reference for a 327169689Skan pseudo is contiguous. */ 328169689Skan bool refs_organized; 329169689Skan /* True if the next refs should be added immediately or false to 330169689Skan defer to later to reorganize the table. */ 331169689Skan bool add_refs_inline; 332169689Skan}; 333169689Skan 334169689Skan 335169689Skan/*---------------------------------------------------------------------------- 336169689Skan Problem data for the scanning dataflow problem. Unlike the other 337169689Skan dataflow problems, the problem data for scanning is fully exposed and 338169689Skan used by owners of the problem. 339169689Skan----------------------------------------------------------------------------*/ 340169689Skan 34190075Sobrienstruct df 34290075Sobrien{ 34390075Sobrien 344169689Skan /* The set of problems to be solved is stored in two arrays. In 345169689Skan PROBLEMS_IN_ORDER, the problems are stored in the order that they 346169689Skan are solved. This is an internally dense array that may have 347169689Skan nulls at the end of it. In PROBLEMS_BY_INDEX, the problem is 348169689Skan stored by the value in df_problem.id. These are used to access 349169689Skan the problem local data without having to search the first 350169689Skan array. */ 35190075Sobrien 352169689Skan struct dataflow *problems_in_order [DF_LAST_PROBLEM_PLUS1]; 353169689Skan struct dataflow *problems_by_index [DF_LAST_PROBLEM_PLUS1]; 354169689Skan int num_problems_defined; 355169689Skan 356169689Skan /* Set after calls to df_scan_blocks, this contains all of the 357169689Skan blocks that higher level problems must rescan before solving the 358169689Skan dataflow equations. If this is NULL, the blocks_to_analyze is 359169689Skan used. */ 360169689Skan bitmap blocks_to_scan; 361169689Skan 362169689Skan /* If not NULL, the subset of blocks of the program to be considered 363169689Skan for analysis. */ 364169689Skan bitmap blocks_to_analyze; 365169689Skan 366169689Skan /* The following information is really the problem data for the 367169689Skan scanning instance but it is used too often by the other problems 368169689Skan to keep getting it from there. */ 369169689Skan struct df_ref_info def_info; /* Def info. */ 370169689Skan struct df_ref_info use_info; /* Use info. */ 371169689Skan struct df_insn_info **insns; /* Insn table, indexed by insn UID. */ 372169689Skan unsigned int insns_size; /* Size of insn table. */ 373169689Skan bitmap hardware_regs_used; /* The set of hardware registers used. */ 374169689Skan bitmap entry_block_defs; /* The set of hardware registers live on entry to the function. */ 375169689Skan bitmap exit_block_uses; /* The set of hardware registers used in exit block. */ 37690075Sobrien}; 37790075Sobrien 378169689Skan#define DF_SCAN_BB_INFO(DF, BB) (df_scan_get_bb_info((DF)->problems_by_index[DF_SCAN],(BB)->index)) 379169689Skan#define DF_RU_BB_INFO(DF, BB) (df_ru_get_bb_info((DF)->problems_by_index[DF_RU],(BB)->index)) 380169689Skan#define DF_RD_BB_INFO(DF, BB) (df_rd_get_bb_info((DF)->problems_by_index[DF_RD],(BB)->index)) 381169689Skan#define DF_LR_BB_INFO(DF, BB) (df_lr_get_bb_info((DF)->problems_by_index[DF_LR],(BB)->index)) 382169689Skan#define DF_UR_BB_INFO(DF, BB) (df_ur_get_bb_info((DF)->problems_by_index[DF_UR],(BB)->index)) 383169689Skan#define DF_UREC_BB_INFO(DF, BB) (df_urec_get_bb_info((DF)->problems_by_index[DF_UREC],(BB)->index)) 38490075Sobrien 385169689Skan/* Most transformations that wish to use live register analysis will 386169689Skan use these macros. The DF_UPWARD_LIVE* macros are only half of the 387169689Skan solution. */ 388169689Skan#define DF_LIVE_IN(DF, BB) (DF_UR_BB_INFO(DF, BB)->in) 389169689Skan#define DF_LIVE_OUT(DF, BB) (DF_UR_BB_INFO(DF, BB)->out) 39090075Sobrien 39190075Sobrien 392169689Skan/* Live in for register allocation also takes into account several other factors. */ 393169689Skan#define DF_RA_LIVE_IN(DF, BB) (DF_UREC_BB_INFO(DF, BB)->in) 394169689Skan#define DF_RA_LIVE_OUT(DF, BB) (DF_UREC_BB_INFO(DF, BB)->out) 395169689Skan 396169689Skan/* These macros are currently used by only reg-stack since it is not 397169689Skan tolerant of uninitialized variables. This intolerance should be 398169689Skan fixed because it causes other problems. */ 399169689Skan#define DF_UPWARD_LIVE_IN(DF, BB) (DF_LR_BB_INFO(DF, BB)->in) 400169689Skan#define DF_UPWARD_LIVE_OUT(DF, BB) (DF_LR_BB_INFO(DF, BB)->out) 401169689Skan 402169689Skan 40390075Sobrien/* Macros to access the elements within the ref structure. */ 404132718Skan 405169689Skan 40690075Sobrien#define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \ 40790075Sobrien ? SUBREG_REG ((REF)->reg) : ((REF)->reg)) 408169689Skan#define DF_REF_REGNO(REF) ((REF)->regno) 40990075Sobrien#define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \ 41090075Sobrien ? &SUBREG_REG ((REF)->reg) : ((REF)->loc)) 41190075Sobrien#define DF_REF_REG(REF) ((REF)->reg) 41290075Sobrien#define DF_REF_LOC(REF) ((REF)->loc) 413169689Skan#define DF_REF_BB(REF) ((REF)->bb) 414169689Skan#define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index) 41590075Sobrien#define DF_REF_INSN(REF) ((REF)->insn) 41690075Sobrien#define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn)) 41790075Sobrien#define DF_REF_TYPE(REF) ((REF)->type) 41890075Sobrien#define DF_REF_CHAIN(REF) ((REF)->chain) 41990075Sobrien#define DF_REF_ID(REF) ((REF)->id) 42090075Sobrien#define DF_REF_FLAGS(REF) ((REF)->flags) 421169689Skan#define DF_REF_NEXT_REG(REF) ((REF)->next_reg) 422169689Skan#define DF_REF_PREV_REG(REF) ((REF)->prev_reg) 423169689Skan#define DF_REF_NEXT_REF(REF) ((REF)->next_ref) 424169689Skan#define DF_REF_DATA(REF) ((REF)->data) 42590075Sobrien 42690075Sobrien/* Macros to determine the reference type. */ 42790075Sobrien 42890075Sobrien#define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF) 429169689Skan#define DF_REF_REG_USE_P(REF) ((REF) && !DF_REF_REG_DEF_P (REF)) 43090075Sobrien#define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE) 43190075Sobrien#define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD) 43290075Sobrien#define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \ 433132718Skan || DF_REF_REG_MEM_LOAD_P (REF)) 43490075Sobrien 435169689Skan/* Macros to get the refs out of def_info or use_info refs table. */ 436169689Skan#define DF_DEFS_SIZE(DF) ((DF)->def_info.bitmap_size) 437169689Skan#define DF_DEFS_GET(DF,ID) ((DF)->def_info.refs[(ID)]) 438169689Skan#define DF_DEFS_SET(DF,ID,VAL) ((DF)->def_info.refs[(ID)]=(VAL)) 439169689Skan#define DF_USES_SIZE(DF) ((DF)->use_info.bitmap_size) 440169689Skan#define DF_USES_GET(DF,ID) ((DF)->use_info.refs[(ID)]) 441169689Skan#define DF_USES_SET(DF,ID,VAL) ((DF)->use_info.refs[(ID)]=(VAL)) 44290075Sobrien 443169689Skan/* Macros to access the register information from scan dataflow record. */ 444169689Skan 445169689Skan#define DF_REG_SIZE(DF) ((DF)->def_info.regs_inited) 446169689Skan#define DF_REG_DEF_GET(DF, REG) ((DF)->def_info.regs[(REG)]) 447169689Skan#define DF_REG_DEF_SET(DF, REG, VAL) ((DF)->def_info.regs[(REG)]=(VAL)) 448169689Skan#define DF_REG_DEF_COUNT(DF, REG) ((DF)->def_info.regs[(REG)]->n_refs) 449169689Skan#define DF_REG_USE_GET(DF, REG) ((DF)->use_info.regs[(REG)]) 450169689Skan#define DF_REG_USE_SET(DF, REG, VAL) ((DF)->use_info.regs[(REG)]=(VAL)) 451169689Skan#define DF_REG_USE_COUNT(DF, REG) ((DF)->use_info.regs[(REG)]->n_refs) 452169689Skan 45390075Sobrien/* Macros to access the elements within the reg_info structure table. */ 45490075Sobrien 45590075Sobrien#define DF_REGNO_FIRST_DEF(DF, REGNUM) \ 456169689Skan(DF_REG_DEF_GET(DF, REGNUM) ? DF_REG_DEF_GET(DF, REGNUM) : 0) 45790075Sobrien#define DF_REGNO_LAST_USE(DF, REGNUM) \ 458169689Skan(DF_REG_USE_GET(DF, REGNUM) ? DF_REG_USE_GET(DF, REGNUM) : 0) 45990075Sobrien 46090075Sobrien/* Macros to access the elements within the insn_info structure table. */ 46190075Sobrien 462169689Skan#define DF_INSN_SIZE(DF) ((DF)->insns_size) 463169689Skan#define DF_INSN_GET(DF,INSN) ((DF)->insns[(INSN_UID(INSN))]) 464169689Skan#define DF_INSN_SET(DF,INSN,VAL) ((DF)->insns[(INSN_UID (INSN))]=(VAL)) 465169689Skan#define DF_INSN_CONTAINS_ASM(DF, INSN) (DF_INSN_GET(DF,INSN)->contains_asm) 466169689Skan#define DF_INSN_LUID(DF, INSN) (DF_INSN_GET(DF,INSN)->luid) 467169689Skan#define DF_INSN_DEFS(DF, INSN) (DF_INSN_GET(DF,INSN)->defs) 468169689Skan#define DF_INSN_USES(DF, INSN) (DF_INSN_GET(DF,INSN)->uses) 46990075Sobrien 470169689Skan#define DF_INSN_UID_GET(DF,UID) ((DF)->insns[(UID)]) 471169689Skan#define DF_INSN_UID_LUID(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->luid) 472169689Skan#define DF_INSN_UID_DEFS(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->defs) 473169689Skan#define DF_INSN_UID_USES(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->uses) 474169689Skan#define DF_INSN_UID_MWS(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->mw_hardregs) 47590075Sobrien 476169689Skan/* This is a bitmap copy of regs_invalidated_by_call so that we can 477169689Skan easily add it into bitmaps, etc. */ 47890075Sobrien 479169689Skanextern bitmap df_invalidated_by_call; 48090075Sobrien 48190075Sobrien 482169689Skan/* One of these structures is allocated for every basic block. */ 483169689Skanstruct df_scan_bb_info 484169689Skan{ 485169689Skan /* Defs at the start of a basic block that is the target of an 486169689Skan exception edge. */ 487169689Skan struct df_ref *artificial_defs; 48890075Sobrien 489169689Skan /* Uses of hard registers that are live at every block. */ 490169689Skan struct df_ref *artificial_uses; 491169689Skan}; 49290075Sobrien 493132718Skan 494169689Skan/* Reaching uses. All bitmaps are indexed by the id field of the ref 495169689Skan except sparse_kill (see below). */ 496169689Skanstruct df_ru_bb_info 497169689Skan{ 498169689Skan /* Local sets to describe the basic blocks. */ 499169689Skan /* The kill set is the set of uses that are killed in this block. 500169689Skan However, if the number of uses for this register is greater than 501169689Skan DF_SPARSE_THRESHOLD, the sparse_kill is used instead. In 502169689Skan sparse_kill, each register gets a slot and a 1 in this bitvector 503169689Skan means that all of the uses of that register are killed. This is 504169689Skan a very useful efficiency hack in that it keeps from having push 505169689Skan around big groups of 1s. This is implemented by the 506169689Skan bitmap_clear_range call. */ 50790075Sobrien 508169689Skan bitmap kill; 509169689Skan bitmap sparse_kill; 510169689Skan bitmap gen; /* The set of uses generated in this block. */ 51190075Sobrien 512169689Skan /* The results of the dataflow problem. */ 513169689Skan bitmap in; /* At the top of the block. */ 514169689Skan bitmap out; /* At the bottom of the block. */ 515169689Skan}; 51690075Sobrien 51790075Sobrien 518169689Skan/* Reaching definitions. All bitmaps are indexed by the id field of 519169689Skan the ref except sparse_kill (see above). */ 520169689Skanstruct df_rd_bb_info 521169689Skan{ 522169689Skan /* Local sets to describe the basic blocks. See the note in the RU 523169689Skan datastructures for kill and sparse_kill. */ 524169689Skan bitmap kill; 525169689Skan bitmap sparse_kill; 526169689Skan bitmap gen; /* The set of defs generated in this block. */ 52790075Sobrien 528169689Skan /* The results of the dataflow problem. */ 529169689Skan bitmap in; /* At the top of the block. */ 530169689Skan bitmap out; /* At the bottom of the block. */ 531169689Skan}; 53290075Sobrien 53390075Sobrien 534169689Skan/* Live registers. All bitmaps are referenced by the register number. */ 535169689Skanstruct df_lr_bb_info 536169689Skan{ 537169689Skan /* Local sets to describe the basic blocks. */ 538169689Skan bitmap def; /* The set of registers set in this block. */ 539169689Skan bitmap use; /* The set of registers used in this block. */ 54090075Sobrien 541169689Skan /* The results of the dataflow problem. */ 542169689Skan bitmap in; /* At the top of the block. */ 543169689Skan bitmap out; /* At the bottom of the block. */ 544169689Skan}; 54590075Sobrien 54690075Sobrien 547169689Skan/* Uninitialized registers. All bitmaps are referenced by the register number. */ 548169689Skanstruct df_ur_bb_info 549169689Skan{ 550169689Skan /* Local sets to describe the basic blocks. */ 551169689Skan bitmap kill; /* The set of registers unset in this block. Calls, 552169689Skan for instance, unset registers. */ 553169689Skan bitmap gen; /* The set of registers set in this block. */ 55490075Sobrien 555169689Skan /* The results of the dataflow problem. */ 556169689Skan bitmap in; /* At the top of the block. */ 557169689Skan bitmap out; /* At the bottom of the block. */ 558169689Skan}; 55990075Sobrien 560169689Skan/* Uninitialized registers. All bitmaps are referenced by the register number. */ 561169689Skanstruct df_urec_bb_info 562169689Skan{ 563169689Skan /* Local sets to describe the basic blocks. */ 564169689Skan bitmap earlyclobber; /* The set of registers that are referenced 565169689Skan with an an early clobber mode. */ 566169689Skan /* Kill and gen are defined as in the UR problem. */ 567169689Skan bitmap kill; 568169689Skan bitmap gen; 56990075Sobrien 570169689Skan /* The results of the dataflow problem. */ 571169689Skan bitmap in; /* At the top of the block. */ 572169689Skan bitmap out; /* At the bottom of the block. */ 573169689Skan}; 57490075Sobrien 57590075Sobrien 576169689Skan#define df_finish(df) {df_finish1(df); df=NULL;} 57790075Sobrien 578169689Skan/* Functions defined in df-core.c. */ 57990075Sobrien 580169689Skanextern struct df *df_init (int); 581169689Skanextern struct dataflow *df_add_problem (struct df *, struct df_problem *, int); 582169689Skanextern int df_set_flags (struct dataflow *, int); 583169689Skanextern int df_clear_flags (struct dataflow *, int); 584169689Skanextern void df_set_blocks (struct df*, bitmap); 585169689Skanextern void df_delete_basic_block (struct df *, int); 586169689Skanextern void df_finish1 (struct df *); 587169689Skanextern void df_analyze_problem (struct dataflow *, bitmap, bitmap, bitmap, int *, int, bool); 588169689Skanextern void df_analyze (struct df *); 589169689Skanextern void df_compact_blocks (struct df *); 590169689Skanextern void df_bb_replace (struct df *, int, basic_block); 591169689Skanextern struct df_ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int); 592169689Skanextern struct df_ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int); 593169689Skanextern struct df_ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int); 594169689Skanextern bool df_insn_regno_def_p (struct df *, rtx, unsigned int); 595169689Skanextern struct df_ref *df_find_def (struct df *, rtx, rtx); 596169689Skanextern bool df_reg_defined (struct df *, rtx, rtx); 597169689Skanextern struct df_ref *df_find_use (struct df *, rtx, rtx); 598169689Skanextern bool df_reg_used (struct df *, rtx, rtx); 599169689Skanextern void df_iterative_dataflow (struct dataflow *, bitmap, bitmap, int *, int, bool); 600169689Skanextern void df_dump (struct df *, FILE *); 601169689Skanextern void df_refs_chain_dump (struct df_ref *, bool, FILE *); 602169689Skanextern void df_regs_chain_dump (struct df *, struct df_ref *, FILE *); 603169689Skanextern void df_insn_debug (struct df *, rtx, bool, FILE *); 604169689Skanextern void df_insn_debug_regno (struct df *, rtx, FILE *); 605169689Skanextern void df_regno_debug (struct df *, unsigned int, FILE *); 606169689Skanextern void df_ref_debug (struct df_ref *, FILE *); 607132718Skanextern void debug_df_insn (rtx); 608132718Skanextern void debug_df_regno (unsigned int); 609132718Skanextern void debug_df_reg (rtx); 610132718Skanextern void debug_df_defno (unsigned int); 611132718Skanextern void debug_df_useno (unsigned int); 612169689Skanextern void debug_df_ref (struct df_ref *); 613169689Skanextern void debug_df_chain (struct df_link *); 614169689Skan/* An instance of df that can be shared between passes. */ 615169689Skanextern struct df *shared_df; 61690075Sobrien 61790075Sobrien 618169689Skan/* Functions defined in df-problems.c. */ 619132718Skan 620169689Skanextern struct df_link *df_chain_create (struct dataflow *, struct df_ref *, struct df_ref *); 621169689Skanextern void df_chain_unlink (struct dataflow *, struct df_ref *, struct df_link *); 622169689Skanextern void df_chain_copy (struct dataflow *, struct df_ref *, struct df_link *); 623169689Skanextern bitmap df_get_live_in (struct df *, basic_block); 624169689Skanextern bitmap df_get_live_out (struct df *, basic_block); 625169689Skanextern void df_grow_bb_info (struct dataflow *); 626169689Skanextern void df_chain_dump (struct df_link *, FILE *); 627169689Skanextern void df_print_bb_index (basic_block bb, FILE *file); 628169689Skanextern struct dataflow *df_ru_add_problem (struct df *, int); 629169689Skanextern struct df_ru_bb_info *df_ru_get_bb_info (struct dataflow *, unsigned int); 630169689Skanextern struct dataflow *df_rd_add_problem (struct df *, int); 631169689Skanextern struct df_rd_bb_info *df_rd_get_bb_info (struct dataflow *, unsigned int); 632169689Skanextern struct dataflow *df_lr_add_problem (struct df *, int); 633169689Skanextern struct df_lr_bb_info *df_lr_get_bb_info (struct dataflow *, unsigned int); 634169689Skanextern struct dataflow *df_ur_add_problem (struct df *, int); 635169689Skanextern struct df_ur_bb_info *df_ur_get_bb_info (struct dataflow *, unsigned int); 636169689Skanextern struct dataflow *df_urec_add_problem (struct df *, int); 637169689Skanextern struct df_urec_bb_info *df_urec_get_bb_info (struct dataflow *, unsigned int); 638169689Skanextern struct dataflow *df_chain_add_problem (struct df *, int); 639169689Skanextern struct dataflow *df_ri_add_problem (struct df *, int); 640132718Skan 641132718Skan 642169689Skan/* Functions defined in df-scan.c. */ 643132718Skan 644169689Skanextern struct df_scan_bb_info *df_scan_get_bb_info (struct dataflow *, unsigned int); 645169689Skanextern struct dataflow *df_scan_add_problem (struct df *, int); 646169689Skanextern void df_rescan_blocks (struct df *, bitmap); 647169689Skanextern struct df_ref *df_ref_create (struct df *, rtx, rtx *, rtx,basic_block,enum df_ref_type, enum df_ref_flags); 648169689Skanextern struct df_ref *df_get_artificial_defs (struct df *, unsigned int); 649169689Skanextern struct df_ref *df_get_artificial_uses (struct df *, unsigned int); 650169689Skanextern void df_reg_chain_create (struct df_reg_info *, struct df_ref *); 651169689Skanextern struct df_ref *df_reg_chain_unlink (struct dataflow *, struct df_ref *); 652169689Skanextern void df_ref_remove (struct df *, struct df_ref *); 653169689Skanextern void df_insn_refs_delete (struct dataflow *, rtx); 654169689Skanextern void df_bb_refs_delete (struct dataflow *, int); 655169689Skanextern void df_refs_delete (struct dataflow *, bitmap); 656169689Skanextern void df_reorganize_refs (struct df_ref_info *); 657169689Skanextern void df_hard_reg_init (void); 658169689Skanextern bool df_read_modify_subreg_p (rtx); 659132718Skan 660132718Skan 661169689Skan/* web */ 66290075Sobrien 663169689Skan/* This entry is allocated for each reference in the insn stream. */ 664169689Skanstruct web_entry 665169689Skan{ 666169689Skan /* Pointer to the parent in the union/find tree. */ 667169689Skan struct web_entry *pred; 668169689Skan /* Newly assigned register to the entry. Set only for roots. */ 669169689Skan rtx reg; 670169689Skan void* extra_info; 671169689Skan}; 67290075Sobrien 673169689Skanextern struct web_entry *unionfind_root (struct web_entry *); 674169689Skanextern bool unionfind_union (struct web_entry *, struct web_entry *); 675169689Skanextern void union_defs (struct df *, struct df_ref *, 676169689Skan struct web_entry *, struct web_entry *, 677169689Skan bool (*fun) (struct web_entry *, struct web_entry *)); 678132718Skan 679132718Skan 680169689Skan#endif /* GCC_DF_H */ 681