gcc/ra.h

   1 /* Define per-register tables for data flow info and register allocation.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_RA_H
  21 #define GCC_RA_H
  22
  23 #include "regs.h"
  24
  25 struct allocno
  26 {
  27   int reg;
  28   /* Gives the number of consecutive hard registers needed by that
  29      pseudo reg.  */
  30   int size;
  31
  32   /* Number of calls crossed by each allocno.  */
  33   int calls_crossed;
  34
  35   /* Estimated frequency of crossing call by each allocno.  */
  36   int freq_calls_crossed;
  37
  38   /* Number of calls that might throw crossed by each allocno.  */
  39   int throwing_calls_crossed;
  40
  41   /* Number of refs to each allocno.  */
  42   int n_refs;
  43
  44   /* Frequency of uses of each allocno.  */
  45   int freq;
  46
  47   /* Guess at live length of each allocno.
  48      This is actually the max of the live lengths of the regs.  */
  49   int live_length;
  50
  51   /* Set of hard regs conflicting with allocno N.  */
  52
  53   HARD_REG_SET hard_reg_conflicts;
  54
  55   /* Set of hard regs preferred by allocno N.
  56      This is used to make allocnos go into regs that are copied to or from them,
  57      when possible, to reduce register shuffling.  */
  58
  59   HARD_REG_SET hard_reg_preferences;
  60
  61   /* Similar, but just counts register preferences made in simple copy
  62      operations, rather than arithmetic.  These are given priority because
  63      we can always eliminate an insn by using these, but using a register
  64      in the above list won't always eliminate an insn.  */
  65
  66   HARD_REG_SET hard_reg_copy_preferences;
  67
  68   /* Similar to hard_reg_preferences, but includes bits for subsequent
  69      registers when an allocno is multi-word.  The above variable is used for
  70      allocation while this is used to build reg_someone_prefers, below.  */
  71
  72   HARD_REG_SET hard_reg_full_preferences;
  73
  74   /* Set of hard registers that some later allocno has a preference for.  */
  75
  76   HARD_REG_SET regs_someone_prefers;
  77
  78 #ifdef EH_RETURN_DATA_REGNO
  79   /* Set to true if allocno can't be allocated in an eh register.  */
  80   unsigned int no_eh_reg:1;
  81 #endif
  82
  83 #ifdef STACK_REGS
  84   /* Set to true if allocno can't be allocated in the stack register.  */
  85   unsigned int no_stack_reg:1;
  86 #endif
  87 };
  88 extern struct allocno *allocno;
  89
  90 /* In ra-conflict.c  */
  91
  92 /* Number of pseudo-registers which are candidates for allocation.  */
  93
  94 extern int max_allocno;
  95
  96 /* max_allocno by max_allocno compressed triangular bit matrix,
  97    recording whether two allocnos conflict (can't go in the same
  98    hardware register).  */
  99
 100 extern HOST_WIDEST_FAST_INT *conflicts;
 101
 102 /* Indexed by (pseudo) reg number, gives the allocno, or -1
 103    for pseudo registers which are not to be allocated.  */
 104
 105 extern int *reg_allocno;
 106
 107 /* Precalculated partial bit number in the compressed triangular bit matrix.
 108    For two allocnos, the final bit number is: partial_bitnum[LOW] + HIGH.  */
 109
 110 extern HOST_WIDE_INT *partial_bitnum;
 111
 112 /* Size in bits of the compressed triangular bit matrix.  */
 113
 114 extern HOST_WIDE_INT max_bitnum;
 115
 116 /* The pool to allocate the adjacency list elements from.  */
 117
 118 extern alloc_pool adjacency_pool;
 119
 120 /* The maximum number of neighbors stored in the neighbors vector before
 121    we have to chain in another vector.  */
 122
 123 #define ADJACENCY_VEC_LENGTH 30
 124
 125 /* Conflict graph adjacency list.  */
 126
 127 typedef struct adjacency_list_d
 128 {
 129   int neighbors[ADJACENCY_VEC_LENGTH];
 130   unsigned int index;
 131   struct adjacency_list_d *next;
 132 } adjacency_t;
 133
 134 extern adjacency_t **adjacency;
 135
 136 /* Add NEIGHBOR to ALLOC_NO's adjacency list.  It is assumed the caller
 137    has already determined that NEIGHBOR is not already neighbor by
 138    checking the conflict bit matrix.  */
 139
 140 static inline void
 141 add_neighbor (int alloc_no, int neighbor)
 142 {
 143   adjacency_t *adjlist = adjacency[alloc_no];
 144
 145   if (adjlist == NULL || adjlist->index == ADJACENCY_VEC_LENGTH)
 146     {
 147       adjacency_t *new_adj = (adjacency_t *) pool_alloc (adjacency_pool);
 148       new_adj->index = 0;
 149       new_adj->next = adjlist;
 150       adjlist = new_adj;
 151       adjacency[alloc_no] = adjlist;
 152     }
 153
 154   adjlist->neighbors[adjlist->index++] = neighbor;
 155 }
 156
 157 /* Iterator for adjacency lists.  */
 158
 159 typedef struct adjacency_iterator_d
 160 {
 161   adjacency_t *vec;
 162   unsigned int idx;
 163 } adjacency_iter;
 164
 165 /* Initialize a single adjacency list iterator.  */
 166
 167 static inline int
 168 adjacency_iter_init (adjacency_iter *ai, int allocno1)
 169 {
 170   ai->vec = adjacency[allocno1];
 171   ai->idx = 0;
 172   return ai->vec != NULL;
 173 }
 174
 175 /* Test whether we have visited all of the neighbors.  */
 176
 177 static inline int
 178 adjacency_iter_done (adjacency_iter *ai)
 179 {
 180   return ai->idx > ai->vec->index;
 181 }
 182
 183 /* Advance to the next neighbor in AI.  */
 184
 185 static inline int
 186 adjacency_iter_next (adjacency_iter *ai)
 187 {
 188   unsigned int idx = ai->idx;
 189   int neighbor = ai->vec->neighbors[idx++];
 190   if (idx >= ai->vec->index && ai->vec->next != NULL)
 191     {
 192       ai->vec = ai->vec->next;
 193       ai->idx = 0;
 194     }
 195   else
 196     ai->idx = idx;
 197   return neighbor;
 198 }
 199
 200 /* Return the one basic block regno is used in.  If regno is used
 201    in more than one basic block or if it is unknown which block it
 202    is used in, return 0.  */
 203
 204 static inline int
 205 regno_basic_block (int regno)
 206 {
 207   int block = REG_BASIC_BLOCK (regno);
 208   if (block < 0)
 209     block = 0;
 210   return block;
 211 }
 212
 213 extern void global_conflicts (void);
 214
 215 /* In global.c  */
 216
 217 /* Macro to visit all of IN_ALLOCNO's neighbors.  Neighbors are
 218    returned in OUT_ALLOCNO for each iteration of the loop.  */
 219
 220 #define FOR_EACH_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, ITER)                \
 221   if (!adjacency || !adjacency_iter_init (&(ITER), (IN_ALLOCNO)))       \
 222     ;                                                                   \
 223   else                                                                  \
 224     for ((OUT_ALLOCNO) = adjacency_iter_next (&(ITER));                 \
 225          !adjacency_iter_done (&(ITER));                                \
 226          (OUT_ALLOCNO) = adjacency_iter_next (&(ITER)))
 227
 228 extern void ra_init_live_subregs (bool, sbitmap *, int *, int, rtx);
 229 extern bool conflict_p (int, int);
 230
 231 #endif /* GCC_RA_H */