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