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 4 Free Software Foundation, Inc. 5 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz) 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 2, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24#ifndef GCC_DF_H 25#define GCC_DF_H 26 27#include "bitmap.h" 28#include "basic-block.h" 29 30#define DF_RD 1 /* Reaching definitions. */ 31#define DF_RU 2 /* Reaching uses. */ 32#define DF_LR 4 /* Live registers. */ 33#define DF_DU_CHAIN 8 /* Def-use chain. */ 34#define DF_UD_CHAIN 16 /* Use-def chain. */ 35#define DF_REG_INFO 32 /* Register info. */ 36#define DF_RD_CHAIN 64 /* Reg-def chain. */ 37#define DF_RU_CHAIN 128 /* Reg-use chain. */ 38#define DF_ALL 255 39#define DF_HARD_REGS 1024 /* Mark hard registers. */ 40#define DF_EQUIV_NOTES 2048 /* Mark uses present in EQUIV/EQUAL notes. */ 41#define DF_SUBREGS 4096 /* Return subregs rather than the inner reg. */ 42 43enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD, 44 DF_REF_REG_MEM_STORE}; 45 46#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"} 47 48/* Link on a def-use or use-def chain. */ 49struct df_link 50{ 51 struct df_link *next; 52 struct ref *ref; 53}; 54 55enum df_ref_flags 56 { 57 /* Read-modify-write refs generate both a use and a def and 58 these are marked with this flag to show that they are not 59 independent. */ 60 DF_REF_READ_WRITE = 1, 61 62 /* This flag is set, if we stripped the subreg from the reference. 63 In this case we must make conservative guesses, at what the 64 outer mode was. */ 65 DF_REF_STRIPPED = 2 66 }; 67 68 69/* Define a register reference structure. One of these is allocated 70 for every register reference (use or def). Note some register 71 references (e.g., post_inc, subreg) generate both a def and a use. */ 72struct ref 73{ 74 rtx reg; /* The register referenced. */ 75 rtx insn; /* Insn containing ref. */ 76 rtx *loc; /* The location of the reg. */ 77 struct df_link *chain; /* Head of def-use or use-def chain. */ 78 unsigned int id; /* Ref index. */ 79 enum df_ref_type type; /* Type of ref. */ 80 enum df_ref_flags flags; /* Various flags. */ 81 void *data; /* The data assigned to it by user. */ 82}; 83 84 85/* One of these structures is allocated for every insn. */ 86struct insn_info 87{ 88 struct df_link *defs; /* Head of insn-def chain. */ 89 struct df_link *uses; /* Head of insn-use chain. */ 90 /* ???? The following luid field should be considered private so that 91 we can change it on the fly to accommodate new insns? */ 92 int luid; /* Logical UID. */ 93}; 94 95 96/* One of these structures is allocated for every reg. */ 97struct reg_info 98{ 99 struct df_link *defs; /* Head of reg-def chain. */ 100 struct df_link *uses; /* Head of reg-use chain. */ 101 int lifetime; 102 int n_defs; 103 int n_uses; 104}; 105 106 107/* One of these structures is allocated for every basic block. */ 108struct bb_info 109{ 110 /* Reaching def bitmaps have def_id elements. */ 111 bitmap rd_kill; 112 bitmap rd_gen; 113 bitmap rd_in; 114 bitmap rd_out; 115 /* Reaching use bitmaps have use_id elements. */ 116 bitmap ru_kill; 117 bitmap ru_gen; 118 bitmap ru_in; 119 bitmap ru_out; 120 /* Live variable bitmaps have n_regs elements. */ 121 bitmap lr_def; 122 bitmap lr_use; 123 bitmap lr_in; 124 bitmap lr_out; 125 int rd_valid; 126 int ru_valid; 127 int lr_valid; 128}; 129 130 131struct df 132{ 133 int flags; /* Indicates what's recorded. */ 134 struct bb_info *bbs; /* Basic block table. */ 135 struct ref **defs; /* Def table, indexed by def_id. */ 136 struct ref **uses; /* Use table, indexed by use_id. */ 137 struct ref **reg_def_last; /* Indexed by regno. */ 138 struct reg_info *regs; /* Regs table, index by regno. */ 139 unsigned int reg_size; /* Size of regs table. */ 140 struct insn_info *insns; /* Insn table, indexed by insn UID. */ 141 unsigned int insn_size; /* Size of insn table. */ 142 unsigned int def_id; /* Next def ID. */ 143 unsigned int def_size; /* Size of def table. */ 144 unsigned int n_defs; /* Size of def bitmaps. */ 145 unsigned int use_id; /* Next use ID. */ 146 unsigned int use_size; /* Size of use table. */ 147 unsigned int n_uses; /* Size of use bitmaps. */ 148 unsigned int n_bbs; /* Number of basic blocks. */ 149 unsigned int n_regs; /* Number of regs. */ 150 unsigned int def_id_save; /* Saved next def ID. */ 151 unsigned int use_id_save; /* Saved next use ID. */ 152 bitmap insns_modified; /* Insns that (may) have changed. */ 153 bitmap bbs_modified; /* Blocks that (may) have changed. */ 154 bitmap all_blocks; /* All blocks in CFG. */ 155 int *dfs_order; /* DFS order -> block number. */ 156 int *rc_order; /* Reverse completion order -> block number. */ 157 int *rts_order; /* Reverse top sort order -> block number. */ 158 int *inverse_rc_map; /* Block number -> reverse completion order. */ 159 int *inverse_dfs_map; /* Block number -> DFS order. */ 160 int *inverse_rts_map; /* Block number -> reverse top-sort order. */ 161}; 162 163 164struct df_map 165{ 166 rtx old; 167 rtx new; 168}; 169 170 171#define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index]) 172 173 174/* Macros to access the elements within the ref structure. */ 175 176#define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \ 177 ? SUBREG_REG ((REF)->reg) : ((REF)->reg)) 178#define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF)) 179#define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \ 180 ? &SUBREG_REG ((REF)->reg) : ((REF)->loc)) 181#define DF_REF_REG(REF) ((REF)->reg) 182#define DF_REF_LOC(REF) ((REF)->loc) 183#define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn)) 184#define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index) 185#define DF_REF_INSN(REF) ((REF)->insn) 186#define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn)) 187#define DF_REF_TYPE(REF) ((REF)->type) 188#define DF_REF_CHAIN(REF) ((REF)->chain) 189#define DF_REF_ID(REF) ((REF)->id) 190#define DF_REF_FLAGS(REF) ((REF)->flags) 191#define DF_REF_DATA(REF) ((REF)->data) 192 193/* Macros to determine the reference type. */ 194 195#define DF_REF_REG_DEF_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_DEF) 196#define DF_REF_REG_USE_P(REF) ((REF) && ! DF_REF_REG_DEF_P (REF)) 197#define DF_REF_REG_MEM_STORE_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_STORE) 198#define DF_REF_REG_MEM_LOAD_P(REF) (DF_REF_TYPE (REF) == DF_REF_REG_MEM_LOAD) 199#define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \ 200 || DF_REF_REG_MEM_LOAD_P (REF)) 201 202 203/* Macros to access the elements within the reg_info structure table. */ 204 205#define DF_REGNO_FIRST_DEF(DF, REGNUM) \ 206((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0) 207#define DF_REGNO_LAST_USE(DF, REGNUM) \ 208((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0) 209 210#define DF_REGNO_FIRST_BB(DF, REGNUM) \ 211((DF)->regs[REGNUM].defs ? DF_REF_BB ((DF)->regs[REGNUM].defs->ref) : 0) 212#define DF_REGNO_LAST_BB(DF, REGNUM) \ 213((DF)->regs[REGNUM].uses ? DF_REF_BB ((DF)->regs[REGNUM].uses->ref) : 0) 214 215 216/* Macros to access the elements within the insn_info structure table. */ 217 218#define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid) 219#define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs) 220#define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses) 221 222 223/* Functions to build and analyze dataflow information. */ 224 225extern struct df *df_init (void); 226 227extern int df_analyze (struct df *, bitmap, int); 228extern void df_analyze_subcfg (struct df *, bitmap, int); 229 230extern void df_finish (struct df *); 231 232extern void df_dump (struct df *, int, FILE *); 233 234 235/* Functions to modify insns. */ 236 237extern bool df_insn_modified_p (struct df *, rtx); 238 239extern void df_insn_modify (struct df *, basic_block, rtx); 240 241extern rtx df_insn_delete (struct df *, basic_block, rtx); 242 243extern rtx df_pattern_emit_before (struct df *, rtx, basic_block, rtx); 244 245extern rtx df_jump_pattern_emit_after (struct df *, rtx, basic_block, rtx); 246 247extern rtx df_pattern_emit_after (struct df *, rtx, basic_block, rtx); 248 249extern rtx df_insn_move_before (struct df *, basic_block, rtx, basic_block, 250 rtx); 251 252extern int df_reg_replace (struct df *, bitmap, rtx, rtx); 253 254extern int df_ref_reg_replace (struct df *, struct ref *, rtx, rtx); 255 256extern int df_ref_remove (struct df *, struct ref *); 257 258extern int df_insn_mem_replace (struct df *, basic_block, rtx, rtx, rtx); 259 260extern struct ref *df_bb_def_use_swap (struct df *, basic_block, rtx, rtx, 261 unsigned int); 262 263 264/* Functions to query dataflow information. */ 265 266extern basic_block df_regno_bb (struct df *, unsigned int); 267 268extern int df_reg_lifetime (struct df *, rtx); 269 270extern int df_reg_global_p (struct df *, rtx); 271 272extern int df_insn_regno_def_p (struct df *, basic_block, rtx, unsigned int); 273 274extern int df_insn_dominates_all_uses_p (struct df *, basic_block, rtx); 275 276extern int df_insn_dominates_uses_p (struct df *, basic_block, rtx, bitmap); 277 278extern int df_bb_reg_live_start_p (struct df *, basic_block, rtx); 279 280extern int df_bb_reg_live_end_p (struct df *, basic_block, rtx); 281 282extern int df_bb_regs_lives_compare (struct df *, basic_block, rtx, rtx); 283 284extern bool df_local_def_available_p (struct df *, struct ref *, struct ref *); 285 286extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx, 287 rtx); 288extern struct ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int); 289 290extern struct ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int); 291 292extern struct ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int); 293 294extern struct ref *df_find_def (struct df *, rtx, rtx); 295 296extern int df_reg_used (struct df *, rtx, rtx); 297 298/* Functions for debugging from GDB. */ 299 300extern void debug_df_insn (rtx); 301 302extern void debug_df_regno (unsigned int); 303 304extern void debug_df_reg (rtx); 305 306extern void debug_df_defno (unsigned int); 307 308extern void debug_df_useno (unsigned int); 309 310extern void debug_df_ref (struct ref *); 311 312extern void debug_df_chain (struct df_link *); 313 314extern void df_insn_debug (struct df *, rtx, FILE *); 315 316extern void df_insn_debug_regno (struct df *, rtx, FILE *); 317 318 319/* Meet over any path (UNION) or meet over all paths (INTERSECTION). */ 320enum df_confluence_op 321 { 322 DF_UNION, 323 DF_INTERSECTION 324 }; 325 326 327/* Dataflow direction. */ 328enum df_flow_dir 329 { 330 DF_FORWARD, 331 DF_BACKWARD 332 }; 333 334 335typedef void (*transfer_function) (int, int *, void *, void *, 336 void *, void *, void *); 337 338/* The description of a dataflow problem to solve. */ 339 340enum set_representation 341{ 342 SR_SBITMAP, /* Represent sets by bitmaps. */ 343 SR_BITMAP /* Represent sets by sbitmaps. */ 344}; 345 346struct dataflow 347{ 348 enum set_representation repr; /* The way the sets are represented. */ 349 350 /* The following arrays are indexed by block indices, so they must always 351 be large enough even if we restrict ourselves just to a subset of cfg. */ 352 void **gen, **kill; /* Gen and kill sets. */ 353 void **in, **out; /* Results. */ 354 355 enum df_flow_dir dir; /* Dataflow direction. */ 356 enum df_confluence_op conf_op; /* Confluence operator. */ 357 unsigned n_blocks; /* Number of basic blocks in the 358 order. */ 359 int *order; /* The list of basic blocks to work 360 with, in the order they should 361 be processed in. */ 362 transfer_function transfun; /* The transfer function. */ 363 void *data; /* Data used by the transfer 364 function. */ 365}; 366 367extern void iterative_dataflow (struct dataflow *); 368extern bool read_modify_subreg_p (rtx); 369 370#endif /* GCC_DF_H */ 371