1 /* 2 * Copyright © 2010 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 * 23 * Authors: 24 * Eric Anholt <eric@anholt.net> 25 * 26 */ 27 28 #ifndef REGISTER_ALLOCATE_INTERNAL_H 29 #define REGISTER_ALLOCATE_INTERNAL_H 30 31 #include <stdbool.h> 32 #include "util/bitset.h" 33 #include "util/u_dynarray.h" 34 35 #ifdef __cplusplus 36 extern "C" { 37 38 #define class klass 39 #endif 40 41 struct ra_list { 42 unsigned int *elems; 43 unsigned int size; 44 unsigned int cap; 45 }; 46 47 struct ra_reg { 48 BITSET_WORD *conflicts; 49 struct ra_list conflict_list; 50 }; 51 52 struct ra_regs { 53 struct ra_reg *regs; 54 unsigned int count; 55 56 struct ra_class **classes; 57 unsigned int class_count; 58 59 bool round_robin; 60 bool uses_conflict_lists; 61 }; 62 63 struct ra_class { 64 struct ra_regs *regset; 65 66 /** 67 * Bitset indicating which registers belong to this class. 68 * 69 * (If bit N is set, then register N belongs to this class.) 70 */ 71 BITSET_WORD *regs; 72 73 /** 74 * Number of regs after each bit in *regs that are also conflicted by an 75 * allocation to that reg for this class. 76 */ 77 int contig_len; 78 79 /** 80 * p(B) in Runeson/Nyström paper. 81 * 82 * This is "how many regs are in the set." 83 */ 84 unsigned int p; 85 86 /** 87 * q(B,C) (indexed by C, B is this register class) in 88 * Runeson/Nyström paper. This is "how many registers of B could 89 * the worst choice register from C conflict with". 90 */ 91 unsigned int *q; 92 93 int index; 94 }; 95 96 struct ra_node { 97 /** @{ 98 * 99 * List of which nodes this node interferes with. This should be 100 * symmetric with the other node. 101 */ 102 struct ra_list adjacency; 103 /** @} */ 104 105 unsigned int class; 106 107 /* Register, if assigned, or NO_REG. */ 108 unsigned int reg; 109 110 /** 111 * The q total, as defined in the Runeson/Nyström paper, for all the 112 * interfering nodes not in the stack. 113 */ 114 unsigned int q_total; 115 116 /* Temporary data for the algorithm to scratch around in */ 117 struct { 118 /** 119 * Temporary version of q_total which we decrement as things are placed 120 * into the stack. 121 */ 122 unsigned int q_total; 123 } tmp; 124 }; 125 126 struct ra_node_extra { 127 /* For an implementation that needs register spilling, this is the 128 * approximate cost of spilling this node. 129 */ 130 float spill_cost; 131 132 /* Client-assigned register, if assigned, or NO_REG. Same size and 133 * capacity as the nodes array. 134 */ 135 unsigned int forced_reg; 136 }; 137 138 struct ra_graph { 139 struct ra_regs *regs; 140 /** 141 * the variables that need register allocation. 142 */ 143 struct ra_node *nodes; 144 145 /* Less used per-node data. Keep it out of the tight loops. */ 146 struct ra_node_extra *nodes_extra; 147 148 BITSET_WORD *adjacency; 149 unsigned int count; /**< count of nodes. */ 150 151 unsigned int alloc; /**< count of nodes allocated. */ 152 153 ra_select_reg_callback select_reg_callback; 154 void *select_reg_callback_data; 155 156 /* Temporary data for the algorithm to scratch around in */ 157 struct { 158 unsigned int *stack; 159 unsigned int stack_count; 160 161 /** Bit-set indicating, for each register, if it's in the stack */ 162 BITSET_WORD *in_stack; 163 164 /** Bit-set indicating, for each register, if it pre-assigned */ 165 BITSET_WORD *reg_assigned; 166 167 /** Bit-set indicating, for each register, the value of the pq test */ 168 BITSET_WORD *pq_test; 169 170 /** For each BITSET_WORD, the minimum q value or ~0 if unknown */ 171 unsigned int *min_q_total; 172 173 /* 174 * * For each BITSET_WORD, the node with the minimum q_total if 175 * min_q_total[i] != ~0. 176 */ 177 unsigned int *min_q_node; 178 179 /** 180 * Tracks the start of the set of optimistically-colored registers in the 181 * stack. 182 */ 183 unsigned int stack_optimistic_start; 184 } tmp; 185 }; 186 187 bool ra_class_allocations_conflict(struct ra_class *c1, unsigned int r1, 188 struct ra_class *c2, unsigned int r2); 189 190 #ifdef __cplusplus 191 } /* extern "C" */ 192 193 #undef class 194 #endif 195 196 #endif /* REGISTER_ALLOCATE_INTERNAL_H */ 197