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 BITSET_WORD *adjacency; 96 97 struct util_dynarray adjacency_list; 98 /** @} */ 99 100 unsigned int class; 101 102 /* Client-assigned register, if assigned, or NO_REG. */ 103 unsigned int forced_reg; 104 105 /* Register, if assigned, or NO_REG. */ 106 unsigned int reg; 107 108 /** 109 * The q total, as defined in the Runeson/Nyström paper, for all the 110 * interfering nodes not in the stack. 111 */ 112 unsigned int q_total; 113 114 /* For an implementation that needs register spilling, this is the 115 * approximate cost of spilling this node. 116 */ 117 float spill_cost; 118 119 /* Temporary data for the algorithm to scratch around in */ 120 struct { 121 /** 122 * Temporary version of q_total which we decrement as things are placed 123 * into the stack. 124 */ 125 unsigned int q_total; 126 } tmp; 127 }; 128 129 struct ra_graph { 130 struct ra_regs *regs; 131 /** 132 * the variables that need register allocation. 133 */ 134 struct ra_node *nodes; 135 unsigned int count; /**< count of nodes. */ 136 137 unsigned int alloc; /**< count of nodes allocated. */ 138 139 ra_select_reg_callback select_reg_callback; 140 void *select_reg_callback_data; 141 142 /* Temporary data for the algorithm to scratch around in */ 143 struct { 144 unsigned int *stack; 145 unsigned int stack_count; 146 147 /** Bit-set indicating, for each register, if it's in the stack */ 148 BITSET_WORD *in_stack; 149 150 /** Bit-set indicating, for each register, if it pre-assigned */ 151 BITSET_WORD *reg_assigned; 152 153 /** Bit-set indicating, for each register, the value of the pq test */ 154 BITSET_WORD *pq_test; 155 156 /** For each BITSET_WORD, the minimum q value or ~0 if unknown */ 157 unsigned int *min_q_total; 158 159 /* 160 * * For each BITSET_WORD, the node with the minimum q_total if 161 * min_q_total[i] != ~0. 162 */ 163 unsigned int *min_q_node; 164 165 /** 166 * Tracks the start of the set of optimistically-colored registers in the 167 * stack. 168 */ 169 unsigned int stack_optimistic_start; 170 } tmp; 171 }; 172 173 bool ra_class_allocations_conflict(struct ra_class *c1, unsigned int r1, 174 struct ra_class *c2, unsigned int r2); 175 176 #ifdef __cplusplus 177 } /* extern "C" */ 178 179 #undef class 180 #endif 181 182 #endif /* REGISTER_ALLOCATE_INTERNAL_H */ 183