gcc/df.h

   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
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-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
  35 enum 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.  */
  45 struct df_link
  46 {
  47   struct df_link *next;
  48   struct ref *ref;
  49 };
  50
  51 enum df_ref_flags
  52   {
  53     DF_REF_READ_WRITE = 1
  54   };
  55
  56 /* Define a register reference structure.  */
  57 struct 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.  */
  70 struct 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.  */
  84 struct 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.  */
  95 struct 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
 118 struct 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
 154 struct 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
 220 extern struct df *df_init PARAMS ((void));
 221
 222 extern int df_analyse PARAMS ((struct df *, bitmap, int));
 223
 224 extern void df_finish PARAMS ((struct df *));
 225
 226 extern void df_dump PARAMS ((struct df *, int, FILE *));
 227
 228 /* Functions to modify insns.  */
 229
 230 extern void df_insn_modify PARAMS ((struct df *, basic_block, rtx));
 231
 232 extern rtx df_insn_delete PARAMS ((struct df *, basic_block, rtx));
 233
 234 extern rtx df_pattern_emit_before PARAMS ((struct df *, rtx,
 235                                            basic_block, rtx));
 236
 237 extern rtx df_jump_pattern_emit_after PARAMS ((struct df *, rtx,
 238                                                basic_block, rtx));
 239
 240 extern rtx df_pattern_emit_after PARAMS ((struct df *, rtx,
 241                                            basic_block, rtx));
 242
 243 extern rtx df_insn_move_before PARAMS ((struct df *, basic_block, rtx,
 244                                         basic_block, rtx));
 245
 246 extern int df_reg_replace PARAMS ((struct df *, bitmap, rtx, rtx));
 247
 248 extern int df_ref_reg_replace PARAMS ((struct df *, struct ref *, rtx, rtx));
 249
 250 extern int df_ref_remove PARAMS ((struct df *, struct ref *));
 251
 252 extern int df_insn_reg_replace PARAMS ((struct df *, basic_block,
 253                                         rtx, rtx, rtx));
 254
 255 extern int df_insn_mem_replace PARAMS ((struct df *, basic_block,
 256                                         rtx, rtx, rtx));
 257
 258 extern 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
 264 extern basic_block df_regno_bb PARAMS((struct df *, unsigned int));
 265
 266 extern int df_reg_lifetime PARAMS ((struct df *, rtx));
 267
 268 extern int df_reg_global_p PARAMS ((struct df *, rtx));
 269
 270 extern int df_insn_regno_def_p PARAMS ((struct df *,
 271                                         basic_block, rtx, unsigned int));
 272
 273 extern int df_insn_dominates_all_uses_p PARAMS ((struct df *,
 274                                                  basic_block, rtx));
 275
 276 extern int df_insn_dominates_uses_p PARAMS ((struct df *, basic_block,
 277                                              rtx, bitmap));
 278
 279 extern int df_bb_reg_live_start_p PARAMS ((struct df *, basic_block, rtx));
 280
 281 extern int df_bb_reg_live_end_p PARAMS ((struct df *, basic_block, rtx));
 282
 283 extern int df_bb_regs_lives_compare PARAMS ((struct df *, basic_block,
 284                                              rtx, rtx));
 285
 286 extern 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
 292 extern void debug_df_insn PARAMS ((rtx));
 293
 294 extern void debug_df_regno PARAMS ((unsigned int));
 295
 296 extern void debug_df_reg PARAMS ((rtx));
 297
 298 extern void debug_df_defno PARAMS ((unsigned int));
 299
 300 extern void debug_df_useno PARAMS ((unsigned int));
 301
 302 extern void debug_df_ref PARAMS ((struct ref *));
 303
 304 extern void debug_df_chain PARAMS ((struct df_link *));
 305 extern void df_insn_debug PARAMS ((struct df *, rtx, FILE *));
 306 extern void df_insn_debug_regno PARAMS ((struct df *, rtx, FILE *));
 307 /* Meet over any path (UNION) or meet over all paths (INTERSECTION) */
 308 enum df_confluence_op
 309   {
 310     UNION,
 311     INTERSECTION
 312   };
 313 /* Dataflow direction */
 314 enum df_flow_dir
 315   {
 316     FORWARD,
 317     BACKWARD
 318   };
 319
 320 typedef void (*transfer_function_sbitmap) PARAMS ((int, int *, sbitmap, sbitmap,
 321                                            sbitmap, sbitmap, void *));
 322 typedef void (*transfer_function_bitmap) PARAMS ((int, int *, bitmap, bitmap,
 323                                           bitmap, bitmap, void *));
 324
 325 extern 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 *));
 331 extern 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 *));