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