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_reg { 42 BITSET_WORD *conflicts; 43 struct util_dynarray conflict_list; 44 }; 45 46 struct ra_regs { 47 struct ra_reg *regs; 48 unsigned int count; 49 50 struct ra_class **classes; 51 unsigned int class_count; 52 53 bool round_robin; 54 }; 55 56 struct ra_class { 57 struct ra_regs *regset; 58 59 /** 60 * Bitset indicating which registers belong to this class. 61 * 62 * (If bit N is set, then register N belongs to this class.) 63 */ 64 BITSET_WORD *regs; 65 66 /** 67 * Number of regs after each bit in *regs that are also conflicted by an 68 * allocation to that reg for this class. 69 */ 70 int contig_len; 71 72 /** 73 * p(B) in Runeson/Nyström paper. 74 * 75 * This is "how many regs are in the set." 76 */ 77 unsigned int p; 78 79 /** 80 * q(B,C) (indexed by C, B is this register class) in 81 * Runeson/Nyström paper. This is "how many registers of B could 82 * the worst choice register from C conflict with". 83 */ 84 unsigned int *q; 85 86 int index; 87 }; 88 89 struct ra_node { 90 /** @{ 91 * 92 * List of which nodes this node interferes with. This should be 93 * symmetric with the other node. 94 */ 95 struct util_dynarray adjacency_list; 96 /** @} */ 97 98 unsigned int class; 99 100 /* Client-assigned register, if assigned, or NO_REG. */ 101 unsigned int forced_reg; 102 103 /* Register, if assigned, or NO_REG. */ 104 unsigned int reg; 105 106 /** 107 * The q total, as defined in the Runeson/Nyström paper, for all the 108 * interfering nodes not in the stack. 109 */ 110 unsigned int q_total; 111 112 /* For an implementation that needs register spilling, this is the 113 * approximate cost of spilling this node. 114 */ 115 float spill_cost; 116 117 /* Temporary data for the algorithm to scratch around in */ 118 struct { 119 /** 120 * Temporary version of q_total which we decrement as things are placed 121 * into the stack. 122 */ 123 unsigned int q_total; 124 } tmp; 125 }; 126 127 struct ra_graph { 128 struct ra_regs *regs; 129 /** 130 * the variables that need register allocation. 131 */ 132 struct ra_node *nodes; 133 BITSET_WORD *adjacency; 134 unsigned int count; /**< count of nodes. */ 135 136 unsigned int alloc; /**< count of nodes allocated. */ 137 138 ra_select_reg_callback select_reg_callback; 139 void *select_reg_callback_data; 140 141 /* Temporary data for the algorithm to scratch around in */ 142 struct { 143 unsigned int *stack; 144 unsigned int stack_count; 145 146 /** Bit-set indicating, for each register, if it's in the stack */ 147 BITSET_WORD *in_stack; 148 149 /** Bit-set indicating, for each register, if it pre-assigned */ 150 BITSET_WORD *reg_assigned; 151 152 /** Bit-set indicating, for each register, the value of the pq test */ 153 BITSET_WORD *pq_test; 154 155 /** For each BITSET_WORD, the minimum q value or ~0 if unknown */ 156 unsigned int *min_q_total; 157 158 /* 159 * * For each BITSET_WORD, the node with the minimum q_total if 160 * min_q_total[i] != ~0. 161 */ 162 unsigned int *min_q_node; 163 164 /** 165 * Tracks the start of the set of optimistically-colored registers in the 166 * stack. 167 */ 168 unsigned int stack_optimistic_start; 169 } tmp; 170 }; 171 172 bool ra_class_allocations_conflict(struct ra_class *c1, unsigned int r1, 173 struct ra_class *c2, unsigned int r2); 174 175 #ifdef __cplusplus 176 } /* extern "C" */ 177 178 #undef class 179 #endif 180 181 #endif /* REGISTER_ALLOCATE_INTERNAL_H */ 182