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   /* Number of calls that might throw crossed by each allocno.  */
  36   int throwing_calls_crossed;
  37
  38   /* Number of refs to each allocno.  */
  39   int n_refs;
  40
  41   /* Frequency of uses of each allocno.  */
  42   int freq;
  43
  44   /* Guess at live length of each allocno.
  45      This is actually the max of the live lengths of the regs.  */
  46   int live_length;
  47
  48   /* Set of hard regs conflicting with allocno N.  */
  49
  50   HARD_REG_SET hard_reg_conflicts;
  51
  52   /* Set of hard regs preferred by allocno N.
  53      This is used to make allocnos go into regs that are copied to or from them,
  54      when possible, to reduce register shuffling.  */
  55
  56   HARD_REG_SET hard_reg_preferences;
  57
  58   /* Similar, but just counts register preferences made in simple copy
  59      operations, rather than arithmetic.  These are given priority because
  60      we can always eliminate an insn by using these, but using a register
  61      in the above list won't always eliminate an insn.  */
  62
  63   HARD_REG_SET hard_reg_copy_preferences;
  64
  65   /* Similar to hard_reg_preferences, but includes bits for subsequent
  66      registers when an allocno is multi-word.  The above variable is used for
  67      allocation while this is used to build reg_someone_prefers, below.  */
  68
  69   HARD_REG_SET hard_reg_full_preferences;
  70
  71   /* Set of hard registers that some later allocno has a preference for.  */
  72
  73   HARD_REG_SET regs_someone_prefers;
  74
  75 #ifdef STACK_REGS
  76   /* Set to true if allocno can't be allocated in the stack register.  */
  77   bool no_stack_reg;
  78 #endif
  79 };
  80 extern struct allocno *allocno;
  81
  82 /* In ra-conflict.c  */
  83
  84 /* Number of pseudo-registers which are candidates for allocation.  */
  85
  86 extern int max_allocno;
  87
  88 /* max_allocno by max_allocno compressed triangular bit matrix,
  89    recording whether two allocnos conflict (can't go in the same
  90    hardware register).  */
  91
  92 extern HOST_WIDEST_FAST_INT *conflicts;
  93
  94 /* Indexed by (pseudo) reg number, gives the allocno, or -1
  95    for pseudo registers which are not to be allocated.  */
  96
  97 extern int *reg_allocno;
  98
  99 /* Precalculated partial bit number in the compressed triangular bit matrix.
 100    For two allocnos, the final bit number is: partial_bitnum[LOW] + HIGH.  */
 101
 102 extern HOST_WIDE_INT *partial_bitnum;
 103
 104 /* Size in bits of the compressed triangular bit matrix.  */
 105
 106 extern HOST_WIDE_INT max_bitnum;
 107
 108 /* The pool to allocate the adjacency list elements from.  */
 109
 110 extern alloc_pool adjacency_pool;
 111
 112 /* The maximum number of neighbors stored in the neighbors vector before
 113    we have to chain in another vector.  */
 114
 115 #define ADJACENCY_VEC_LENGTH 30
 116
 117 /* Conflict graph adjacency list.  */
 118
 119 typedef struct adjacency_list_d
 120 {
 121   int neighbors[ADJACENCY_VEC_LENGTH];
 122   unsigned int index;
 123   struct adjacency_list_d *next;
 124 } adjacency_t;
 125
 126 extern adjacency_t **adjacency;
 127
 128 /* Add NEIGHBOR to ALLOC_NO's adjacency list.  It is assumed the caller
 129    has already determined that NEIGHBOR is not already neighbor by
 130    checking the conflict bit matrix.  */
 131
 132 static inline void
 133 add_neighbor (int alloc_no, int neighbor)
 134 {
 135   adjacency_t *adjlist = adjacency[alloc_no];
 136
 137   if (adjlist == NULL || adjlist->index == ADJACENCY_VEC_LENGTH)
 138     {
 139       adjacency_t *new = pool_alloc (adjacency_pool);
 140       new->index = 0;
 141       new->next = adjlist;
 142       adjlist = new;
 143       adjacency[alloc_no] = adjlist;
 144     }
 145
 146   adjlist->neighbors[adjlist->index++] = neighbor;
 147 }
 148
 149 /* Iterator for adjacency lists.  */
 150
 151 typedef struct adjacency_iterator_d
 152 {
 153   adjacency_t *vec;
 154   unsigned int idx;
 155 } adjacency_iter;
 156
 157 /* Initialize a single adjacency list iterator.  */
 158
 159 static inline int
 160 adjacency_iter_init (adjacency_iter *ai, int allocno1)
 161 {
 162   ai->vec = adjacency[allocno1];
 163   ai->idx = 0;
 164   return ai->vec != NULL;
 165 }
 166
 167 /* Test whether we have visited all of the neighbors.  */
 168
 169 static inline int
 170 adjacency_iter_done (adjacency_iter *ai)
 171 {
 172   return ai->idx > ai->vec->index;
 173 }
 174
 175 /* Advance to the next neighbor in AI.  */
 176
 177 static inline int
 178 adjacency_iter_next (adjacency_iter *ai)
 179 {
 180   unsigned int idx = ai->idx;
 181   int neighbor = ai->vec->neighbors[idx++];
 182   if (idx >= ai->vec->index && ai->vec->next != NULL)
 183     {
 184       ai->vec = ai->vec->next;
 185       ai->idx = 0;
 186     }
 187   else
 188     ai->idx = idx;
 189   return neighbor;
 190 }
 191
 192 /* Return the one basic block regno is used in.  If regno is used
 193    in more than one basic block or if it is unknown which block it
 194    is used in, return 0.  */
 195
 196 static inline int
 197 regno_basic_block (int regno)
 198 {
 199   int block = REG_BASIC_BLOCK (regno);
 200   if (block < 0)
 201     block = 0;
 202   return block;
 203 }
 204
 205 extern void global_conflicts (void);
 206
 207 /* In global.c  */
 208
 209 /* Macro to visit all of IN_ALLOCNO's neighbors.  Neighbors are
 210    returned in OUT_ALLOCNO for each iteration of the loop.  */
 211
 212 #define FOR_EACH_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, ITER)                \
 213   if (!adjacency || !adjacency_iter_init (&(ITER), (IN_ALLOCNO)))       \
 214     ;                                                                   \
 215   else                                                                  \
 216     for ((OUT_ALLOCNO) = adjacency_iter_next (&(ITER));                 \
 217          !adjacency_iter_done (&(ITER));                                \
 218          (OUT_ALLOCNO) = adjacency_iter_next (&(ITER)))
 219
 220 extern void ra_init_live_subregs (bool, sbitmap *, int *, int, rtx);
 221 extern bool conflict_p (int, int);
 222
 223 #endif /* GCC_RA_H */