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 #define DF_SUBREGS      4096    /* Return subregs rather than the inner reg.  */
  42
  43 enum 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.  */
  49 struct df_link
  50 {
  51   struct df_link *next;
  52   struct ref *ref;
  53 };
  54
  55 enum 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.  */
  72 struct 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.  */
  86 struct 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.  */
  97 struct 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.  */
 108 struct 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
 131 struct 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
 164 struct 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
 225 extern struct df *df_init (void);
 226
 227 extern int df_analyze (struct df *, bitmap, int);
 228 extern void df_analyze_subcfg (struct df *, bitmap, int);
 229
 230 extern void df_finish (struct df *);
 231
 232 extern void df_dump (struct df *, int, FILE *);
 233
 234
 235 /* Functions to modify insns.  */
 236
 237 extern bool df_insn_modified_p (struct df *, rtx);
 238
 239 extern void df_insn_modify (struct df *, basic_block, rtx);
 240
 241 extern rtx df_insn_delete (struct df *, basic_block, rtx);
 242
 243 extern rtx df_pattern_emit_before (struct df *, rtx, basic_block, rtx);
 244
 245 extern rtx df_jump_pattern_emit_after (struct df *, rtx, basic_block, rtx);
 246
 247 extern rtx df_pattern_emit_after (struct df *, rtx, basic_block, rtx);
 248
 249 extern rtx df_insn_move_before (struct df *, basic_block, rtx, basic_block,
 250                                 rtx);
 251
 252 extern int df_reg_replace (struct df *, bitmap, rtx, rtx);
 253
 254 extern int df_ref_reg_replace (struct df *, struct ref *, rtx, rtx);
 255
 256 extern int df_ref_remove (struct df *, struct ref *);
 257
 258 extern int df_insn_mem_replace (struct df *, basic_block, rtx, rtx, rtx);
 259
 260 extern 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
 266 extern basic_block df_regno_bb (struct df *, unsigned int);
 267
 268 extern int df_reg_lifetime (struct df *, rtx);
 269
 270 extern int df_reg_global_p (struct df *, rtx);
 271
 272 extern int df_insn_regno_def_p (struct df *, basic_block, rtx, unsigned int);
 273
 274 extern int df_insn_dominates_all_uses_p (struct df *, basic_block, rtx);
 275
 276 extern int df_insn_dominates_uses_p (struct df *, basic_block, rtx, bitmap);
 277
 278 extern int df_bb_reg_live_start_p (struct df *, basic_block, rtx);
 279
 280 extern int df_bb_reg_live_end_p (struct df *, basic_block, rtx);
 281
 282 extern int df_bb_regs_lives_compare (struct df *, basic_block, rtx, rtx);
 283
 284 extern bool df_local_def_available_p (struct df *, struct ref *, struct ref *);
 285
 286 extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx,
 287                                            rtx);
 288 extern struct ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int);
 289
 290 extern struct ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int);
 291
 292 extern struct ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
 293
 294 extern struct ref *df_find_def (struct df *, rtx, rtx);
 295
 296 extern int df_reg_used (struct df *, rtx, rtx);
 297
 298 /* Functions for debugging from GDB.  */
 299
 300 extern void debug_df_insn (rtx);
 301
 302 extern void debug_df_regno (unsigned int);
 303
 304 extern void debug_df_reg (rtx);
 305
 306 extern void debug_df_defno (unsigned int);
 307
 308 extern void debug_df_useno (unsigned int);
 309
 310 extern void debug_df_ref (struct ref *);
 311
 312 extern void debug_df_chain (struct df_link *);
 313
 314 extern void df_insn_debug (struct df *, rtx, FILE *);
 315
 316 extern void df_insn_debug_regno (struct df *, rtx, FILE *);
 317
 318
 319 /* Meet over any path (UNION) or meet over all paths (INTERSECTION).  */
 320 enum df_confluence_op
 321   {
 322     DF_UNION,
 323     DF_INTERSECTION
 324   };
 325
 326
 327 /* Dataflow direction.  */
 328 enum df_flow_dir
 329   {
 330     DF_FORWARD,
 331     DF_BACKWARD
 332   };
 333
 334
 335 typedef void (*transfer_function) (int, int *, void *, void *,
 336                                    void *, void *, void *);
 337
 338 /* The description of a dataflow problem to solve.  */
 339
 340 enum set_representation
 341 {
 342   SR_SBITMAP,           /* Represent sets by bitmaps.  */
 343   SR_BITMAP             /* Represent sets by sbitmaps.  */
 344 };
 345
 346 struct 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
 367 extern void iterative_dataflow (struct dataflow *);
 368 extern bool read_modify_subreg_p (rtx);
 369
 370 #endif /* GCC_DF_H */