gcc/basic-block.h

   1 /* Define control and data flow tables, and regsets.
   2    Copyright (C) 1987, 1997, 1998, 1999 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "bitmap.h"
  23 #include "sbitmap.h"
  24 #include "varray.h"
  25
  26 typedef bitmap regset;          /* Head of register set linked list.  */
  27
  28 /* Clear a register set by freeing up the linked list.  */
  29 #define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD)
  30
  31 /* Copy a register set to another register set.  */
  32 #define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM)
  33
  34 /* Compare two register sets.  */
  35 #define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B)
  36
  37 /* `and' a register set with a second register set.  */
  38 #define AND_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_AND)
  39
  40 /* `and' the complement of a register set with a register set.  */
  41 #define AND_COMPL_REG_SET(TO, FROM) \
  42   bitmap_operation (TO, TO, FROM, BITMAP_AND_COMPL)
  43
  44 /* Inclusive or a register set with a second register set.  */
  45 #define IOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_IOR)
  46
  47 /* Exclusive or a register set with a second register set.  */
  48 #define XOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_XOR)
  49
  50 /* Or into TO the register set FROM1 `and'ed with the complement of FROM2.  */
  51 #define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \
  52   bitmap_ior_and_compl (TO, FROM1, FROM2)
  53
  54 /* Clear a single register in a register set.  */
  55 #define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG)
  56
  57 /* Set a single register in a register set.  */
  58 #define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG)
  59
  60 /* Return true if a register is set in a register set.  */
  61 #define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG)
  62
  63 /* Copy the hard registers in a register set to the hard register set.  */
  64 #define REG_SET_TO_HARD_REG_SET(TO, FROM)                               \
  65 do {                                                                    \
  66   int i_;                                                               \
  67   CLEAR_HARD_REG_SET (TO);                                              \
  68   for (i_ = 0; i_ < FIRST_PSEUDO_REGISTER; i_++)                        \
  69     if (REGNO_REG_SET_P (FROM, i_))                                     \
  70       SET_HARD_REG_BIT (TO, i_);                                        \
  71 } while (0)
  72
  73 /* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the
  74    register number and executing CODE for all registers that are set. */
  75 #define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE)            \
  76   EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE)
  77
  78 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
  79    REGNUM to the register number and executing CODE for all registers that are
  80    set in the first regset and not set in the second. */
  81 #define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
  82   EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)
  83
  84 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
  85    REGNUM to the register number and executing CODE for all registers that are
  86    set in both regsets. */
  87 #define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
  88   EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)
  89
  90 /* Allocate a register set with oballoc.  */
  91 #define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK)
  92
  93 /* Allocate a register set with alloca.  */
  94 #define ALLOCA_REG_SET() BITMAP_ALLOCA ()
  95
  96 /* Do any cleanup needed on a regset when it is no longer used.  */
  97 #define FREE_REG_SET(REGSET) BITMAP_FREE(REGSET)
  98
  99 /* Do any one-time initializations needed for regsets.  */
 100 #define INIT_ONCE_REG_SET() BITMAP_INIT_ONCE ()
 101
 102 /* Grow any tables needed when the number of registers is calculated
 103    or extended.  For the linked list allocation, nothing needs to
 104    be done, other than zero the statistics on the first allocation.  */
 105 #define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P)
 106
 107 /* Control flow edge information.  */
 108 typedef struct edge_def {
 109   /* Links through the predecessor and successor lists.  */
 110   struct edge_def *pred_next, *succ_next;
 111
 112   /* The two blocks at the ends of the edge.  */
 113   struct basic_block_def *src, *dest;
 114
 115   /* Instructions queued on the edge.  */
 116   rtx insns;
 117
 118   /* Auxiliary info specific to a pass.  */
 119   void *aux;
 120
 121   int flags;                    /* see EDGE_* below  */
 122   int probability;              /* biased by REG_BR_PROB_BASE */
 123 } *edge;
 124
 125 #define EDGE_FALLTHRU           1
 126 #define EDGE_CRITICAL           2
 127 #define EDGE_ABNORMAL           4
 128 #define EDGE_ABNORMAL_CALL      8
 129 #define EDGE_EH                 16
 130 #define EDGE_FAKE               32
 131
 132
 133 /* Basic block information indexed by block number.  */
 134 typedef struct basic_block_def {
 135   /* The first and last insns of the block.  */
 136   rtx head, end;
 137
 138   /* The edges into and out of the block.  */
 139   edge pred, succ;
 140
 141   /* Liveness info.  */
 142   regset local_set;
 143   regset global_live_at_start;
 144   regset global_live_at_end;
 145
 146   /* Auxiliary info specific to a pass.  */
 147   void *aux;
 148
 149   /* The index of this block.  */
 150   int index;
 151   /* The loop depth of this block plus one.  */
 152   int loop_depth;
 153
 154   /* The active eh region before head and after end.  */
 155   int eh_beg, eh_end;
 156 } *basic_block;
 157
 158 /* Number of basic blocks in the current function.  */
 159
 160 extern int n_basic_blocks;
 161
 162 /* Number of edges in the current function.  */
 163
 164 extern int n_edges;
 165
 166 /* Index by basic block number, get basic block struct info.  */
 167
 168 extern varray_type basic_block_info;
 169
 170 #define BASIC_BLOCK(N)  (VARRAY_BB (basic_block_info, (N)))
 171
 172 /* What registers are live at the setjmp call.  */
 173
 174 extern regset regs_live_at_setjmp;
 175
 176 /* Indexed by n, gives number of basic block that  (REG n) is used in.
 177    If the value is REG_BLOCK_GLOBAL (-2),
 178    it means (REG n) is used in more than one basic block.
 179    REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
 180    This information remains valid for the rest of the compilation
 181    of the current function; it is used to control register allocation.  */
 182
 183 #define REG_BLOCK_UNKNOWN -1
 184 #define REG_BLOCK_GLOBAL -2
 185
 186 #define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block)
 187
 188 /* List of integers.
 189    These are used for storing things like predecessors, etc.
 190
 191    This scheme isn't very space efficient, especially on 64 bit machines.
 192    The interface is designed so that the implementation can be replaced with
 193    something more efficient if desirable.  */
 194
 195 typedef struct int_list {
 196   struct int_list *next;
 197   int val;
 198 } int_list;
 199
 200 typedef int_list *int_list_ptr;
 201
 202 /* Integer list elements are allocated in blocks to reduce the frequency
 203    of calls to malloc and to reduce the associated space overhead.  */
 204
 205 typedef struct int_list_block {
 206   struct int_list_block *next;
 207   int nodes_left;
 208 #define INT_LIST_NODES_IN_BLK 500
 209   struct int_list nodes[INT_LIST_NODES_IN_BLK];
 210 } int_list_block;
 211
 212 /* Given a pointer to the list, return pointer to first element.  */
 213 #define INT_LIST_FIRST(il) (il)
 214
 215 /* Given a pointer to a list element, return pointer to next element.  */
 216 #define INT_LIST_NEXT(p) ((p)->next)
 217
 218 /* Return non-zero if P points to the end of the list.  */
 219 #define INT_LIST_END(p) ((p) == NULL)
 220
 221 /* Return element pointed to by P.  */
 222 #define INT_LIST_VAL(p) ((p)->val)
 223
 224 #define INT_LIST_SET_VAL(p, new_val) ((p)->val = (new_val))
 225
 226 extern void free_int_list               PROTO ((int_list_block **));
 227 \f
 228 /* Stuff for recording basic block info.  */
 229
 230 #define BLOCK_HEAD(B)      (BASIC_BLOCK (B)->head)
 231 #define BLOCK_END(B)       (BASIC_BLOCK (B)->end)
 232
 233 /* Special block numbers [markers] for entry and exit.  */
 234 #define ENTRY_BLOCK (-1)
 235 #define EXIT_BLOCK (-2)
 236
 237 /* Similarly, block pointers for the edge list.  */
 238 extern struct basic_block_def entry_exit_blocks[2];
 239 #define ENTRY_BLOCK_PTR (&entry_exit_blocks[0])
 240 #define EXIT_BLOCK_PTR  (&entry_exit_blocks[1])
 241
 242 extern varray_type basic_block_for_insn;
 243 #define BLOCK_FOR_INSN(INSN)  VARRAY_BB (basic_block_for_insn, INSN_UID (INSN))
 244 #define BLOCK_NUM(INSN)       (BLOCK_FOR_INSN (INSN)->index + 0)
 245
 246 extern void compute_bb_for_insn         PROTO ((int));
 247 extern void set_block_for_insn          PROTO ((rtx, basic_block));
 248
 249 extern void dump_bb_data                PROTO ((FILE *, int_list_ptr *,
 250                                                 int_list_ptr *, int));
 251 extern void free_bb_mem                 PROTO ((void));
 252 extern void free_basic_block_vars       PROTO ((int));
 253
 254 extern basic_block split_edge           PROTO ((edge));
 255 extern void insert_insn_on_edge         PROTO ((rtx, edge));
 256 extern void commit_edge_insertions      PROTO ((void));
 257 extern void remove_fake_edges           PROTO ((void));
 258 extern void add_noreturn_fake_exit_edges        PROTO ((void));
 259 extern void flow_delete_insn_chain      PROTO((rtx, rtx));
 260
 261 /* This structure maintains an edge list vector.  */
 262 struct edge_list
 263 {
 264   int num_blocks;
 265   int num_edges;
 266   edge *index_to_edge;
 267 };
 268
 269 /* This is the value which indicates no edge is present.  */
 270 #define EDGE_INDEX_NO_EDGE      -1
 271
 272 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
 273    if there is no edge between the 2 basic blocks.  */
 274 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
 275
 276 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
 277    block which is either the pred or succ end of the indexed edge.  */
 278 #define INDEX_EDGE_PRED_BB(el, index)   ((el)->index_to_edge[(index)]->src)
 279 #define INDEX_EDGE_SUCC_BB(el, index)   ((el)->index_to_edge[(index)]->dest)
 280
 281 /* INDEX_EDGE returns a pointer to the edge.  */
 282 #define INDEX_EDGE(el, index)           ((el)->index_to_edge[(index)])
 283
 284 /* Number of edges in the compressed edge list.  */
 285 #define NUM_EDGES(el)                   ((el)->num_edges)
 286
 287 struct edge_list * create_edge_list     PROTO ((void));
 288 void free_edge_list                     PROTO ((struct edge_list *));
 289 void print_edge_list                    PROTO ((FILE *, struct edge_list *));
 290 void verify_edge_list                   PROTO ((FILE *, struct edge_list *));
 291 int find_edge_index                     PROTO ((struct edge_list *,
 292                                                 basic_block, basic_block));
 293
 294 extern void compute_preds_succs         PROTO ((int_list_ptr *, int_list_ptr *,
 295                                                 int *, int *));
 296 extern void compute_dominators          PROTO ((sbitmap *, sbitmap *,
 297                                                 int_list_ptr *,
 298                                                 int_list_ptr *));
 299 extern void compute_flow_dominators     PROTO ((sbitmap *, sbitmap *));
 300 extern void compute_immediate_dominators        PROTO ((int *, sbitmap *));
 301
 302 enum update_life_extent
 303 {
 304   UPDATE_LIFE_LOCAL = 0,
 305   UPDATE_LIFE_GLOBAL = 1,
 306   UPDATE_LIFE_GLOBAL_RM_NOTES = 2,
 307 };
 308
 309 extern void update_life_info    PROTO ((sbitmap, enum update_life_extent));
 310 extern int count_or_remove_death_notes  PROTO ((sbitmap, int));
 311
 312 /* In lcm.c */
 313 extern void pre_lcm                     PROTO ((int, int, int_list_ptr *,
 314                                                 int_list_ptr *,
 315                                                 sbitmap *, sbitmap *,
 316                                                 sbitmap *, sbitmap *));
 317 extern void pre_rev_lcm                 PROTO ((int, int, int_list_ptr *,
 318                                                 int_list_ptr *,
 319                                                 sbitmap *, sbitmap *,
 320                                                 sbitmap *, sbitmap *));