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