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 STACK_REGS
  79   /* Set to true if allocno can't be allocated in the stack register.  */
  80   bool no_stack_reg;
  81 #endif
  82 };
  83 extern struct allocno *allocno;
  84
  85 /* In ra-conflict.c  */
  86
  87 /* Number of pseudo-registers which are candidates for allocation.  */
  88
  89 extern int max_allocno;
  90
  91 /* max_allocno by max_allocno compressed triangular bit matrix,
  92    recording whether two allocnos conflict (can't go in the same
  93    hardware register).  */
  94
  95 extern HOST_WIDEST_FAST_INT *conflicts;
  96
  97 /* Indexed by (pseudo) reg number, gives the allocno, or -1
  98    for pseudo registers which are not to be allocated.  */
  99
 100 extern int *reg_allocno;
 101
 102 /* Precalculated partial bit number in the compressed triangular bit matrix.
 103    For two allocnos, the final bit number is: partial_bitnum[LOW] + HIGH.  */
 104
 105 extern HOST_WIDE_INT *partial_bitnum;
 106
 107 /* Size in bits of the compressed triangular bit matrix.  */
 108
 109 extern HOST_WIDE_INT max_bitnum;
 110
 111 /* The pool to allocate the adjacency list elements from.  */
 112
 113 extern alloc_pool adjacency_pool;
 114
 115 /* The maximum number of neighbors stored in the neighbors vector before
 116    we have to chain in another vector.  */
 117
 118 #define ADJACENCY_VEC_LENGTH 30
 119
 120 /* Conflict graph adjacency list.  */
 121
 122 typedef struct adjacency_list_d
 123 {
 124   int neighbors[ADJACENCY_VEC_LENGTH];
 125   unsigned int index;
 126   struct adjacency_list_d *next;
 127 } adjacency_t;
 128
 129 extern adjacency_t **adjacency;
 130
 131 /* Add NEIGHBOR to ALLOC_NO's adjacency list.  It is assumed the caller
 132    has already determined that NEIGHBOR is not already neighbor by
 133    checking the conflict bit matrix.  */
 134
 135 static inline void
 136 add_neighbor (int alloc_no, int neighbor)
 137 {
 138   adjacency_t *adjlist = adjacency[alloc_no];
 139
 140   if (adjlist == NULL || adjlist->index == ADJACENCY_VEC_LENGTH)
 141     {
 142       adjacency_t *new = pool_alloc (adjacency_pool);
 143       new->index = 0;
 144       new->next = adjlist;
 145       adjlist = new;
 146       adjacency[alloc_no] = adjlist;
 147     }
 148
 149   adjlist->neighbors[adjlist->index++] = neighbor;
 150 }
 151
 152 /* Iterator for adjacency lists.  */
 153
 154 typedef struct adjacency_iterator_d
 155 {
 156   adjacency_t *vec;
 157   unsigned int idx;
 158 } adjacency_iter;
 159
 160 /* Initialize a single adjacency list iterator.  */
 161
 162 static inline int
 163 adjacency_iter_init (adjacency_iter *ai, int allocno1)
 164 {
 165   ai->vec = adjacency[allocno1];
 166   ai->idx = 0;
 167   return ai->vec != NULL;
 168 }
 169
 170 /* Test whether we have visited all of the neighbors.  */
 171
 172 static inline int
 173 adjacency_iter_done (adjacency_iter *ai)
 174 {
 175   return ai->idx > ai->vec->index;
 176 }
 177
 178 /* Advance to the next neighbor in AI.  */
 179
 180 static inline int
 181 adjacency_iter_next (adjacency_iter *ai)
 182 {
 183   unsigned int idx = ai->idx;
 184   int neighbor = ai->vec->neighbors[idx++];
 185   if (idx >= ai->vec->index && ai->vec->next != NULL)
 186     {
 187       ai->vec = ai->vec->next;
 188       ai->idx = 0;
 189     }
 190   else
 191     ai->idx = idx;
 192   return neighbor;
 193 }
 194
 195 /* Return the one basic block regno is used in.  If regno is used
 196    in more than one basic block or if it is unknown which block it
 197    is used in, return 0.  */
 198
 199 static inline int
 200 regno_basic_block (int regno)
 201 {
 202   int block = REG_BASIC_BLOCK (regno);
 203   if (block < 0)
 204     block = 0;
 205   return block;
 206 }
 207
 208 extern void global_conflicts (void);
 209
 210 /* In global.c  */
 211
 212 /* Macro to visit all of IN_ALLOCNO's neighbors.  Neighbors are
 213    returned in OUT_ALLOCNO for each iteration of the loop.  */
 214
 215 #define FOR_EACH_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, ITER)                \
 216   if (!adjacency || !adjacency_iter_init (&(ITER), (IN_ALLOCNO)))       \
 217     ;                                                                   \
 218   else                                                                  \
 219     for ((OUT_ALLOCNO) = adjacency_iter_next (&(ITER));                 \
 220          !adjacency_iter_done (&(ITER));                                \
 221          (OUT_ALLOCNO) = adjacency_iter_next (&(ITER)))
 222
 223 extern void ra_init_live_subregs (bool, sbitmap *, int *, int, rtx);
 224 extern bool conflict_p (int, int);
 225
 226 #endif /* GCC_RA_H */