sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 1 | |
| 2 | /*---------------------------------------------------------------*/ |
| 3 | /*--- ---*/ |
| 4 | /*--- This file (reg_alloc.c) is ---*/ |
| 5 | /*--- Copyright (c) 2004 OpenWorks LLP. All rights reserved. ---*/ |
| 6 | /*--- ---*/ |
| 7 | /*---------------------------------------------------------------*/ |
| 8 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 9 | #include <stdio.h> |
| 10 | #include <malloc.h> |
| 11 | |
| 12 | #include "basictypes.h" |
| 13 | #include "host_regs.h" |
| 14 | |
| 15 | |
| 16 | /* How many 64-bit sized spill slots do we have? */ |
| 17 | #define N_SPILL64S 16 |
| 18 | |
| 19 | |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 20 | /* TODO (critical) |
| 21 | - Need a way to statically establish the vreg classes, |
| 22 | else we can't allocate spill slots properly. |
| 23 | - Better consistency checking from what isMove tells us. |
| 24 | */ |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 25 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 26 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 27 | /* Records information on virtual register live ranges. Computed once |
| 28 | and remains unchanged after that. */ |
| 29 | typedef |
| 30 | struct { |
| 31 | /* Becomes live for the first time after this insn ... */ |
| 32 | Int live_after; |
| 33 | /* Becomes dead for the last time before this insn ... */ |
| 34 | Int dead_before; |
| 35 | /* The "home" spill slot, if needed. Never changes. */ |
| 36 | Int spill_offset; |
| 37 | Int spill_size; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 38 | /* What kind of register this is. */ |
| 39 | HRegClass reg_class; |
| 40 | /* Preferencing info, if any. Currently unused. */ |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 41 | Bool has_preference; |
| 42 | HReg preferred_rreg; /* if True, where I would like to be */ |
| 43 | } |
| 44 | VRegInfo; |
| 45 | |
| 46 | |
| 47 | /* Records information on real-register live ranges. Computed once |
| 48 | and remains unchanged after that. */ |
| 49 | typedef |
| 50 | struct { |
| 51 | HReg rreg; |
| 52 | /* Becomes live after this insn ... */ |
| 53 | Int live_after; |
| 54 | /* Becomes dead before this insn ... */ |
| 55 | Int dead_before; |
| 56 | } |
| 57 | RRegInfo; |
| 58 | |
| 59 | |
| 60 | /* An array of the following structs comprises the running state of |
| 61 | the allocator. It indicates what the current disposition of each |
| 62 | allocatable real register is. The array gets updated as the |
| 63 | allocator processes instructions. */ |
| 64 | typedef |
| 65 | struct { |
| 66 | /* Which rreg is this for? */ |
| 67 | HReg rreg; |
| 68 | /* What's it's current disposition? */ |
| 69 | enum { Free, /* available for use */ |
| 70 | Unavail, /* in a real-reg live range */ |
| 71 | Bound /* in use (holding value of some vreg) */ |
| 72 | } |
| 73 | disp; |
| 74 | /* If RRegBound, what vreg is it bound to? */ |
| 75 | HReg vreg; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 76 | /* Used when .disp == Bound and we are looking for vregs to |
| 77 | spill. */ |
| 78 | Bool is_spill_cand; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 79 | } |
| 80 | RRegState; |
| 81 | |
| 82 | |
| 83 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 84 | /* Does this instruction mention a particular reg? */ |
| 85 | static Bool instrMentionsReg ( |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 86 | void (*getRegUsage) (HRegUsage*, HInstr*), |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 87 | HInstr* instr, |
| 88 | HReg r |
| 89 | ) |
| 90 | { |
| 91 | Int i; |
| 92 | HRegUsage reg_usage; |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 93 | (*getRegUsage)(®_usage, instr); |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 94 | for (i = 0; i < reg_usage.n_used; i++) |
| 95 | if (reg_usage.hreg[i] == r) |
| 96 | return True; |
| 97 | return False; |
| 98 | } |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 99 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 100 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 101 | /* Search forward from some given point in the incoming instruction |
| 102 | sequence. Point is to select a virtual register to spill, by |
| 103 | finding the vreg which is mentioned as far ahead as possible, in |
| 104 | the hope that this will minimise the number of consequent reloads. |
| 105 | |
| 106 | Only do the search for vregs which are Bound in the running state, |
| 107 | and for which the .mark field is set. This allows the caller to |
| 108 | arbitrarily restrict the set of spill candidates to be considered. |
| 109 | |
| 110 | Returns an index into the state array indicating the (v,r) pair to |
| 111 | spill, or -1 if none was found. */ |
| 112 | static |
| 113 | Int findMostDistantlyMentionedVReg ( |
| 114 | void (*getRegUsage) (HRegUsage*, HInstr*), |
| 115 | HInstrArray* instrs_in, |
| 116 | Int search_from_instr, |
| 117 | RRegState* state, |
| 118 | Int n_state |
| 119 | ) |
| 120 | { |
| 121 | Int k, m; |
| 122 | Int furthest_k = -1; |
| 123 | Int furthest = -1; |
| 124 | assert(search_from_instr >= 0); |
| 125 | for (k = 0; k < n_state; k++) { |
| 126 | if (!state[k].is_spill_cand) |
| 127 | continue; |
| 128 | assert(state[k].disp == Bound); |
| 129 | for (m = search_from_instr; m < instrs_in->arr_used; m++) { |
| 130 | if (instrMentionsReg(getRegUsage, |
| 131 | instrs_in->arr[m], state[k].vreg)) |
| 132 | break; |
| 133 | } |
| 134 | if (m > furthest) { |
| 135 | furthest = m; |
| 136 | furthest_k = k; |
| 137 | } |
| 138 | } |
| 139 | return furthest_k; |
| 140 | } |
| 141 | |
| 142 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 143 | /* A target-independent register allocator for Valgrind. Requires |
| 144 | various functions which it uses to deal abstractly with |
| 145 | instructions and registers, since it cannot have any |
| 146 | target-specific knowledge. |
| 147 | |
| 148 | Returns a new list of instructions, which, as a result of the |
| 149 | behaviour of mapRegs, will be in-place modifications of the |
| 150 | original instructions. |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 151 | |
| 152 | Requires that the incoming code has been generated using |
| 153 | vreg numbers 0, 1 .. n_vregs-1. Appearance of a vreg outside |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 154 | that range is a checked run-time error. |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 155 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 156 | Takes an expandable array of pointers to unallocated insns. |
| 157 | Returns an expandable array of pointers to allocated insns. |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 158 | */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 159 | HInstrArray* doRegisterAllocation ( |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 160 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 161 | /* Incoming virtual-registerised code. */ |
| 162 | HInstrArray* instrs_in, |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 163 | |
| 164 | /* An array listing all the real registers the allocator may use, |
| 165 | in no particular order. */ |
| 166 | HReg* available_real_regs, |
| 167 | Int n_available_real_regs, |
| 168 | |
| 169 | /* Return True iff the given insn is a reg-reg move, in which |
| 170 | case also return the src and dst regs. */ |
| 171 | Bool (*isMove) (HInstr*, HReg*, HReg*), |
| 172 | |
| 173 | /* Get info about register usage in this insn. */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 174 | void (*getRegUsage) (HRegUsage*, HInstr*), |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 175 | |
| 176 | /* Apply a reg-reg mapping to an insn. */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 177 | void (*mapRegs) (HRegRemap*, HInstr*), |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 178 | |
| 179 | /* Return an insn to spill/restore a real reg to a spill slot |
| 180 | offset. */ |
| 181 | HInstr* (*genSpill) ( HReg, Int ), |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 182 | HInstr* (*genReload) ( HReg, Int ) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 183 | ) |
| 184 | { |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 185 | /* Iterators and temporaries. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 186 | Int ii, j, k, m, spillee; |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 187 | HReg rreg, vreg, vregS, vregD; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 188 | HRegUsage reg_usage; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 189 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 190 | /* Info on vregs and rregs. Computed once and remains |
| 191 | unchanged. */ |
| 192 | VRegInfo* vreg_info; |
| 193 | RRegInfo* rreg_info; |
| 194 | Int rreg_info_size; |
| 195 | Int rreg_info_used; |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 196 | Int n_vregs; |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 197 | |
| 198 | /* Used when constructing vreg_info (for allocating stack |
| 199 | slots). */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 200 | Int ss_busy_until_before[N_SPILL64S]; |
| 201 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 202 | /* Used when constructing rreg_info. */ |
| 203 | Int* rreg_live_after; |
| 204 | Int* rreg_dead_before; |
| 205 | |
| 206 | /* Running state of the core allocation algorithm. */ |
| 207 | RRegState* state; |
| 208 | Int n_state; |
| 209 | |
| 210 | /* The vreg -> rreg map constructed and then applied to each |
| 211 | instr. */ |
| 212 | HRegRemap remap; |
| 213 | |
| 214 | /* The output array of instructions. */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 215 | HInstrArray* instrs_out; |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 216 | |
| 217 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 218 | # define INVALID_INSTRNO (-2) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 219 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 220 | # define EMIT_INSTR(_instr) \ |
| 221 | do { \ |
| 222 | HInstr* _tmp = (_instr); \ |
| 223 | if (1) { \ |
| 224 | fprintf(stdout, "** "); \ |
| 225 | ppX86Instr(stdout, _tmp); \ |
| 226 | fprintf(stdout, "\n"); \ |
| 227 | } \ |
| 228 | addHInstr ( instrs_out, _tmp ); \ |
| 229 | } while (0) |
| 230 | |
| 231 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 232 | /* --------- Stage 0: set up output array. --------- */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 233 | instrs_out = newHInstrArray(); |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 234 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 235 | |
| 236 | /* --------- Stage 1: compute vreg live ranges. --------- */ |
| 237 | |
| 238 | /* This is relatively simple, because (1) we only seek the complete |
| 239 | end-to-end live range of each vreg, and are not interested in |
| 240 | any holes in it, and (2) the vregs are conveniently numbered 0 |
| 241 | .. n_vregs-1, so we can just dump the results in a pre-allocated |
| 242 | array. */ |
| 243 | |
sewardj | 194d54a | 2004-07-03 19:08:18 +0000 | [diff] [blame] | 244 | n_vregs = instrs_in->n_vregs; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 245 | vreg_info = NULL; |
| 246 | if (n_vregs > 0) |
| 247 | vreg_info = malloc(sizeof(VRegInfo) * n_vregs); |
| 248 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 249 | for (j = 0; j < n_vregs; j++) { |
| 250 | vreg_info[j].live_after = INVALID_INSTRNO; |
| 251 | vreg_info[j].dead_before = INVALID_INSTRNO; |
| 252 | vreg_info[j].spill_offset = 0; |
| 253 | vreg_info[j].spill_size = 0; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 254 | vreg_info[j].reg_class = HRcINVALID; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 255 | vreg_info[j].has_preference = False; |
| 256 | vreg_info[j].preferred_rreg = INVALID_HREG; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 257 | } |
| 258 | |
| 259 | /* for each insn ... */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 260 | for (ii = 0; ii < instrs_in->arr_used; ii++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 261 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 262 | (*getRegUsage)( ®_usage, instrs_in->arr[ii] ); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 263 | |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 264 | fprintf(stdout, "\n%d stage1: ", ii); |
| 265 | ppX86Instr(stdout, instrs_in->arr[ii]); |
| 266 | fprintf(stdout, "\n"); |
| 267 | ppHRegUsage(stdout, ®_usage); |
| 268 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 269 | /* for each reg mentioned in the insn ... */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 270 | for (j = 0; j < reg_usage.n_used; j++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 271 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 272 | vreg = reg_usage.hreg[j]; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 273 | /* only interested in virtual registers right now. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 274 | if (!hregIsVirtual(vreg)) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 275 | continue; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 276 | k = hregNumber(vreg); |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 277 | if (k < 0 || k >= n_vregs) |
| 278 | panic("doRegisterAllocation: out-of-range vreg"); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 279 | |
| 280 | /* Take the opportunity to note its regclass. We'll need |
| 281 | that when allocating spill slots. */ |
| 282 | if (vreg_info[k].reg_class == HRcINVALID) { |
| 283 | /* First mention of this vreg. */ |
| 284 | vreg_info[k].reg_class = hregClass(vreg); |
| 285 | } else { |
| 286 | /* Seen it before, so check for consistency. */ |
| 287 | assert(vreg_info[k].reg_class == hregClass(vreg)); |
| 288 | } |
| 289 | |
| 290 | /* Now consider live ranges. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 291 | switch (reg_usage.mode[j]) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 292 | case HRmRead: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 293 | if (vreg_info[k].live_after == INVALID_INSTRNO) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 294 | panic("doRegisterAllocation: " |
| 295 | "first event for vreg is Read"); |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 296 | vreg_info[k].dead_before = ii; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 297 | break; |
| 298 | case HRmWrite: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 299 | if (vreg_info[k].live_after == INVALID_INSTRNO) |
| 300 | vreg_info[k].live_after = ii; |
| 301 | vreg_info[k].dead_before = ii + 1; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 302 | break; |
| 303 | case HRmModify: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 304 | if (vreg_info[k].live_after == INVALID_INSTRNO) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 305 | panic("doRegisterAllocation: " |
| 306 | "first event for vreg is Modify"); |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 307 | vreg_info[k].dead_before = ii + 1; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 308 | break; |
| 309 | default: |
| 310 | panic("doRegisterAllocation(1)"); |
| 311 | } /* switch */ |
| 312 | |
| 313 | } /* iterate over registers */ |
| 314 | |
| 315 | } /* iterate over insns */ |
| 316 | |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 317 | for (j = 0; j < n_vregs; j++) { |
| 318 | fprintf(stdout, "vreg %d: la = %d, db = %d\n", |
| 319 | j, vreg_info[j].live_after, vreg_info[j].dead_before ); |
| 320 | } |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 321 | |
| 322 | /* --------- Stage 2: compute rreg live ranges. --------- */ |
| 323 | |
| 324 | /* This is more complex than Stage 1, because we need to compute |
| 325 | exactly all the live ranges of all the allocatable real regs, |
| 326 | and we don't know in advance how many there will be. */ |
| 327 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 328 | rreg_info_used = 0; |
| 329 | rreg_info_size = 4; |
| 330 | rreg_info = malloc(rreg_info_size * sizeof(RRegInfo)); |
| 331 | |
| 332 | /* We'll need to track live range start/end points seperately for |
| 333 | each rreg. Sigh. */ |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 334 | assert(n_available_real_regs > 0); |
| 335 | rreg_live_after = malloc(n_available_real_regs * sizeof(Int)); |
| 336 | rreg_dead_before = malloc(n_available_real_regs * sizeof(Int)); |
| 337 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 338 | for (j = 0; j < n_available_real_regs; j++) |
| 339 | rreg_live_after[j] = |
| 340 | rreg_dead_before[j] = INVALID_INSTRNO; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 341 | |
| 342 | /* for each insn ... */ |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 343 | for (ii = 0; ii < instrs_in->arr_used; ii++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 344 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 345 | (*getRegUsage)( ®_usage, instrs_in->arr[ii] ); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 346 | |
| 347 | /* for each reg mentioned in the insn ... */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 348 | for (j = 0; j < reg_usage.n_used; j++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 349 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 350 | /* Dummy initialisations of flush_la and flush_db to avoid |
| 351 | possible bogus uninit-var warnings from gcc. */ |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 352 | Int flush_la = INVALID_INSTRNO, flush_db = INVALID_INSTRNO; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 353 | Bool flush; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 354 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 355 | rreg = reg_usage.hreg[j]; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 356 | |
| 357 | /* only interested in real registers right now. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 358 | if (hregIsVirtual(rreg)) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 359 | continue; |
| 360 | |
| 361 | /* Furthermore, we're not interested in this rreg unless it's |
| 362 | one of the allocatable ones. For example, it could be a |
| 363 | stack pointer register, or some other register beyond our |
| 364 | control, in which case we should just ignore it. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 365 | for (k = 0; k < n_available_real_regs; k++) |
| 366 | if (available_real_regs[k] == rreg) |
| 367 | break; |
| 368 | if (k == n_available_real_regs) |
| 369 | continue; /* not found -- ignore. */ |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 370 | flush = False; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 371 | switch (reg_usage.mode[j]) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 372 | case HRmWrite: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 373 | flush_la = rreg_live_after[k]; |
| 374 | flush_db = rreg_dead_before[k]; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 375 | if (flush_la != INVALID_INSTRNO |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 376 | && flush_db != INVALID_INSTRNO) |
| 377 | flush = True; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 378 | rreg_live_after[k] = ii; |
| 379 | rreg_dead_before[k] = ii+1; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 380 | break; |
| 381 | case HRmRead: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 382 | if (rreg_live_after[k] == INVALID_INSTRNO) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 383 | panic("doRegisterAllocation: " |
| 384 | "first event for rreg is Read"); |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 385 | rreg_dead_before[k] = ii; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 386 | break; |
| 387 | case HRmModify: |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 388 | if (rreg_live_after[k] == INVALID_INSTRNO) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 389 | panic("doRegisterAllocation: " |
| 390 | "first event for rreg is Modify"); |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 391 | rreg_dead_before[k] = ii+1; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 392 | break; |
| 393 | default: |
| 394 | panic("doRegisterAllocation(2)"); |
| 395 | } |
| 396 | |
| 397 | if (flush) { |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 398 | assert(flush_la != INVALID_INSTRNO); |
| 399 | assert(flush_db != INVALID_INSTRNO); |
| 400 | printf("FLUSH 1 (%d,%d)\n", flush_la, flush_db); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 401 | if (rreg_info_used == rreg_info_size) { |
| 402 | panic("make rreg info array bigger(1)"); |
| 403 | } |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 404 | rreg_info[rreg_info_used].rreg = rreg; |
| 405 | rreg_info[rreg_info_used].live_after = flush_la; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 406 | rreg_info[rreg_info_used].dead_before = flush_db; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 407 | rreg_info_used++; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 408 | } |
| 409 | |
| 410 | } /* iterate over regs in the instr */ |
| 411 | |
| 412 | } /* iterate over instrs */ |
| 413 | |
| 414 | /* Now finish up any live ranges left over. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 415 | for (j = 0; j < n_available_real_regs; j++) { |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 416 | |
| 417 | # if 0 |
| 418 | printf("residual %d: %d %d\n", j, rreg_live_after[j], |
| 419 | rreg_dead_before[j]); |
| 420 | # endif |
| 421 | assert( (rreg_live_after[j] == INVALID_INSTRNO |
| 422 | && rreg_dead_before[j] == INVALID_INSTRNO) |
| 423 | || |
| 424 | (rreg_live_after[j] != INVALID_INSTRNO |
| 425 | && rreg_dead_before[j] != INVALID_INSTRNO) |
| 426 | ); |
| 427 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 428 | if (rreg_live_after[j] == INVALID_INSTRNO) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 429 | continue; |
| 430 | if (rreg_info_used == rreg_info_size) { |
| 431 | panic("make rreg info array bigger(2)"); |
| 432 | } |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 433 | rreg_info[rreg_info_used].rreg = available_real_regs[j]; |
| 434 | rreg_info[rreg_info_used].live_after = rreg_live_after[j]; |
| 435 | rreg_info[rreg_info_used].dead_before = rreg_dead_before[j]; |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 436 | rreg_info_used++; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 437 | } |
| 438 | |
| 439 | free(rreg_live_after); |
| 440 | free(rreg_dead_before); |
| 441 | |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 442 | # if 1 |
| 443 | for (j = 0; j < rreg_info_used; j++) { |
| 444 | ppHReg(stdout, rreg_info[j].rreg); |
| 445 | fprintf(stdout, " la = %d, db = %d\n", |
| 446 | rreg_info[j].live_after, rreg_info[j].dead_before ); |
| 447 | } |
| 448 | # endif |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 449 | |
| 450 | /* --------- Stage 3: allocate spill slots. --------- */ |
| 451 | |
| 452 | /* Each spill slot is 8 bytes long. For 128-bit vregs |
| 453 | we'll have to allocate two spill slots. For now, tho, |
| 454 | ignore the 128-bit problem. |
| 455 | |
| 456 | Do a rank-based allocation of vregs to spill slot numbers. We |
| 457 | put as few values as possible in spill slows, but nevertheless |
| 458 | need to have a spill slot available for all vregs, just in case. |
| 459 | */ |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 460 | /* max_ss_no = -1; */ |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 461 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 462 | for (j = 0; j < N_SPILL64S; j++) |
| 463 | ss_busy_until_before[j] = 0; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 464 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 465 | for (j = 0; j < n_vregs; j++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 466 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 467 | /* True iff this vreg is unused. In which case we also expect |
| 468 | that the reg_class field for it has not been set. */ |
| 469 | if (vreg_info[j].live_after == INVALID_INSTRNO) { |
| 470 | assert(vreg_info[j].reg_class == HRcINVALID); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 471 | continue; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 472 | } |
| 473 | |
| 474 | /* Need to allocate two 64-bit spill slots for this. */ |
| 475 | if (vreg_info[j].reg_class == HRcVector128) |
| 476 | panic("can't deal with spilling 128-bit values (yet)"); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 477 | |
| 478 | /* Find the lowest-numbered spill slot which is available at the |
| 479 | start point of this interval, and assign the interval to |
| 480 | it. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 481 | for (k = 0; k < N_SPILL64S; k++) |
| 482 | if (ss_busy_until_before[k] <= vreg_info[j].live_after) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 483 | break; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 484 | if (k == N_SPILL64S) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 485 | panic("N_SPILL64S is too low"); |
| 486 | } |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 487 | ss_busy_until_before[k] = vreg_info[j].dead_before; |
| 488 | vreg_info[j].spill_offset = k * 8; |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 489 | /* if (j > max_ss_no) */ |
| 490 | /* max_ss_no = j; */ |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 491 | } |
| 492 | |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 493 | fprintf(stdout, "\n\n"); |
| 494 | for (j = 0; j < n_vregs; j++) |
| 495 | fprintf(stdout, "vreg %d --> spill offset %d\n", |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 496 | j, vreg_info[j].spill_offset); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 497 | |
| 498 | /* --------- Stage 4: establish rreg preferences --------- */ |
| 499 | |
| 500 | /* It may be advantageous to allocating certain vregs to specific |
| 501 | rregs, as a way of avoiding reg-reg moves later. Here we |
| 502 | establish which, if any, rreg each vreg would prefer to be in. |
| 503 | Note that this constrains the allocator -- ideally we end up |
| 504 | with as few as possible vregs expressing a preference. */ |
| 505 | |
| 506 | /* For now, ignore this. It's only an optimisation, not needed for |
| 507 | correctness. */ |
| 508 | |
| 509 | |
| 510 | /* --------- Stage 5: process instructions --------- */ |
| 511 | |
| 512 | /* This is the main loop of the allocator. First, we need to |
| 513 | correctly set up our running state, which tracks the status of |
| 514 | each real register. */ |
| 515 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 516 | /* n_state is no more than a short name for n_available_real_regs. */ |
| 517 | n_state = n_available_real_regs; |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 518 | state = malloc(n_available_real_regs * sizeof(RRegState)); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 519 | |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 520 | for (j = 0; j < n_state; j++) { |
| 521 | state[j].rreg = available_real_regs[j]; |
| 522 | state[j].disp = Free; |
| 523 | state[j].vreg = INVALID_HREG; |
| 524 | state[j].is_spill_cand = False; |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 525 | } |
| 526 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 527 | /* ------ BEGIN: Process each insn in turn. ------ */ |
| 528 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 529 | for (ii = 0; ii < instrs_in->arr_used; ii++) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 530 | |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 531 | fprintf(stdout, "\n-----------\n%d ", ii); |
| 532 | ppX86Instr(stdout, instrs_in->arr[ii]); |
| 533 | fprintf(stdout, "\n"); |
| 534 | for (j = 0; j < n_state; j++) { |
| 535 | ppHReg(stdout, state[j].rreg); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 536 | fprintf(stdout, "\t "); |
| 537 | switch (state[j].disp) { |
| 538 | case Free: fprintf(stdout, "Free\n"); break; |
| 539 | case Unavail: fprintf(stdout, "Unavail\n"); break; |
| 540 | case Bound: fprintf(stdout, "BoundTo "); |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 541 | ppHReg(stdout, state[j].vreg); |
| 542 | fprintf(stdout, "\n"); break; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 543 | } |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 544 | } |
| 545 | fprintf(stdout, "\n"); |
| 546 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 547 | /* ------ Sanity checks ------ */ |
| 548 | |
| 549 | /* Sanity check 1: all rregs with a hard live range crossing |
| 550 | this insn must be marked as unavailable in the running |
| 551 | state. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 552 | for (j = 0; j < rreg_info_used; j++) { |
| 553 | if (rreg_info[j].live_after < ii |
| 554 | && ii < rreg_info[j].dead_before) { |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 555 | /* ii is the middle of a hard live range for some real reg. |
| 556 | Check it's marked as such in the running state. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 557 | assert(state[rreg_info[j].rreg].disp == Unavail); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 558 | } |
| 559 | } |
| 560 | |
| 561 | /* Sanity check 2: conversely, all rregs marked as unavailable in |
| 562 | the running state must have a corresponding hard live range |
| 563 | entry in the rreg_info array. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 564 | for (j = 0; j < n_available_real_regs; j++) { |
| 565 | assert(state[j].disp == Free |
| 566 | || state[j].disp == Unavail |
| 567 | || state[j].disp == Bound); |
| 568 | if (state[j].disp != Unavail) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 569 | continue; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 570 | for (k = 0; k < rreg_info_used; k++) |
| 571 | if (rreg_info[k].rreg == state[j].rreg |
| 572 | && rreg_info[k].live_after < ii |
| 573 | && ii < rreg_info[k].dead_before) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 574 | break; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 575 | /* If this assertion fails, we couldn't find a correspond |
| 576 | HLR. */ |
| 577 | assert(k < rreg_info_used); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 578 | } |
| 579 | |
| 580 | /* Sanity check 3: No vreg is bound to more than one rreg. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 581 | for (j = 0; j < n_state; j++) { |
| 582 | if (state[j].disp != Bound) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 583 | continue; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 584 | for (k = j+1; k < n_state; k++) |
| 585 | if (state[k].disp == Bound) |
| 586 | assert(state[k].vreg != state[j].vreg); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 587 | } |
| 588 | |
| 589 | /* Sanity check 4: all vreg-rreg bindings must bind registers of |
| 590 | the same class. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 591 | for (j = 0; j < n_state; j++) { |
| 592 | if (state[j].disp != Bound) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 593 | continue; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 594 | assert(hregClass(state[j].rreg) == hregClass(state[j].vreg)); |
| 595 | assert( hregIsVirtual(state[j].vreg)); |
| 596 | assert(!hregIsVirtual(state[j].rreg)); |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 597 | } |
| 598 | |
| 599 | /* ------ end of Sanity checks ------ */ |
| 600 | |
| 601 | /* Do various optimisations pertaining to register coalescing |
| 602 | and preferencing: |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 603 | MOV v <-> v coalescing (done here). |
| 604 | MOV v <-> r coalescing (not yet, if ever) |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 605 | */ |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 606 | /* If doing a reg-reg move between two vregs, and the src's live |
| 607 | range ends here and the dst's live range starts here, bind |
| 608 | the dst to the src's rreg, and that's all. */ |
| 609 | if ( (*isMove)( instrs_in->arr[ii], &vregS, &vregD ) ) { |
| 610 | if (!hregIsVirtual(vregS)) goto cannot_coalesce; |
| 611 | if (!hregIsVirtual(vregD)) goto cannot_coalesce; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 612 | /* Check that *isMove is not telling us a bunch of lies ... */ |
| 613 | assert(hregClass(vregS) == hregClass(vregD)); |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 614 | k = hregNumber(vregS); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 615 | m = hregNumber(vregD); |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 616 | assert(k >= 0 && k < n_vregs); |
| 617 | assert(m >= 0 && m < n_vregs); |
| 618 | if (vreg_info[k].dead_before != ii) goto cannot_coalesce; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 619 | if (vreg_info[m].live_after != ii) goto cannot_coalesce; |
| 620 | printf("COALESCE "); |
| 621 | ppHReg(stdout, vregS); |
| 622 | printf(" -> "); |
| 623 | ppHReg(stdout, vregD); |
| 624 | printf("\n"); |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 625 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 626 | /* Find the state entry for vregS. */ |
| 627 | for (m = 0; m < n_state; m++) |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 628 | if (state[m].disp == Bound && state[m].vreg == vregS) |
| 629 | break; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 630 | if (m == n_state) |
| 631 | /* We failed to find a binding for vregS, which means it's |
| 632 | currently not in a register. So we can't do the |
| 633 | coalescing. Give up. */ |
| 634 | goto cannot_coalesce; |
| 635 | |
| 636 | /* Finally, we can do the coalescing. It's trivial -- merely |
| 637 | claim vregS's register for vregD. */ |
| 638 | state[m].vreg = vregD; |
| 639 | /* Don't bother to copy this insn, just move on to the next |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 640 | insn. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 641 | continue; |
sewardj | 968396e | 2004-07-03 14:50:33 +0000 | [diff] [blame] | 642 | } |
| 643 | cannot_coalesce: |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 644 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 645 | /* ------ Pre-instruction actions for fixed rreg uses ------ */ |
sewardj | 8149744 | 2004-07-02 17:30:07 +0000 | [diff] [blame] | 646 | |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 647 | /* Now we have to deal with rregs which are about to be made |
| 648 | live by this instruction -- in other words, are entering into |
| 649 | one of their live ranges. If any such rreg holds a vreg, we |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 650 | will have to free up the rreg. The simplest solution which |
| 651 | is correct is to spill the rreg. |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 652 | |
| 653 | Note we could do better: |
| 654 | * Could move it into some other free rreg, if one is available |
| 655 | * Don't bother to spill if the spill-slot value is known to |
| 656 | be consistent. |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 657 | * If the associated vreg live range ends at this insn, |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 658 | no point in spilling or moving, since (in principle) the |
| 659 | rreg will be free anyway after that. |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 660 | |
| 661 | Simplest way to do this is to iterate over the collection |
| 662 | of rreg live ranges. |
| 663 | */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 664 | for (j = 0; j < rreg_info_used; j++) { |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 665 | if (rreg_info[j].live_after == ii) { |
| 666 | /* rreg_info[j].rreg needs to be freed up. Find |
| 667 | the associated state entry. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 668 | /* Note, re rreg_info[j].live_after == ii. Real register |
| 669 | live ranges are guaranteed to be well-formed in that |
| 670 | they start with a write to the register -- Stage 2 |
| 671 | rejects any code not satisfying this. So the correct |
| 672 | question to ask is whether rreg_info[j].live_after == |
| 673 | ii, that is, whether the reg becomes live after this |
| 674 | insn -- rather than before it. */ |
| 675 | printf("need to free up rreg: "); |
| 676 | ppHReg(stdout, rreg_info[j].rreg); |
| 677 | printf("\n"); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 678 | for (k = 0; k < n_state; k++) |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 679 | if (state[k].rreg == rreg_info[j].rreg) |
| 680 | break; |
| 681 | /* If this fails, we don't have an entry for this rreg. |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 682 | Which we should. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 683 | assert(k < n_state); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 684 | if (state[k].disp == Bound) { |
| 685 | /* Yes, there is an associated vreg. Spill it if it's |
| 686 | still live. */ |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 687 | m = hregNumber(state[k].vreg); |
| 688 | assert(m >= 0 && m < n_vregs); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 689 | if (vreg_info[m].dead_before > ii) { |
| 690 | assert(vreg_info[m].reg_class != HRcINVALID); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 691 | EMIT_INSTR( (*genSpill)( state[k].rreg, |
| 692 | vreg_info[m].spill_offset ) ); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 693 | } |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 694 | } |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 695 | state[k].disp = Unavail; |
| 696 | state[k].vreg = INVALID_HREG; |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 697 | } |
| 698 | } |
| 699 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 700 | /* ------ Deal with the current instruction. ------ */ |
| 701 | |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 702 | /* Finally we can begin the processing of this instruction |
| 703 | itself. The aim is to free up enough rregs for this insn. |
| 704 | This may generate spill stores since we may have to evict |
| 705 | some vregs currently in rregs. Also generates spill loads. |
| 706 | We also build up the final vreg->rreg mapping to be applied |
| 707 | to the insn. */ |
| 708 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 709 | (*getRegUsage)( ®_usage, instrs_in->arr[ii] ); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 710 | |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 711 | initHRegRemap(&remap); |
| 712 | |
| 713 | /* for each reg mentioned in the insn ... */ |
| 714 | for (j = 0; j < reg_usage.n_used; j++) { |
| 715 | |
| 716 | vreg = reg_usage.hreg[j]; |
| 717 | |
| 718 | /* only interested in virtual registers right now. */ |
| 719 | if (!hregIsVirtual(vreg)) |
| 720 | continue; |
| 721 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 722 | printf("considering "); ppHReg(stdout, vreg); printf("\n"); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 723 | |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 724 | /* Now we're trying to find a rreg for "vreg". First of all, |
| 725 | if it already has an rreg assigned, we don't need to do |
| 726 | anything more. Search the current state to find out. */ |
| 727 | for (k = 0; k < n_state; k++) |
| 728 | if (state[k].vreg == vreg && state[k].disp == Bound) |
| 729 | break; |
| 730 | if (k < n_state) { |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 731 | addToHRegRemap(&remap, vreg, state[k].rreg); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 732 | continue; |
| 733 | } |
| 734 | |
| 735 | /* No luck. The next thing to do is see if there is a |
| 736 | currently free rreg available, of the correct class. If |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 737 | so, bag it. NOTE, we could improve this by selecting an |
| 738 | rreg for which the next live-range event is as far ahead |
| 739 | as possible. */ |
| 740 | for (k = 0; k < n_state; k++) { |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 741 | if (state[k].disp == Free |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 742 | && hregClass(state[k].rreg) == hregClass(vreg)) |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 743 | break; |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 744 | } |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 745 | if (k < n_state) { |
| 746 | state[k].disp = Bound; |
| 747 | state[k].vreg = vreg; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 748 | addToHRegRemap(&remap, vreg, state[k].rreg); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 749 | /* Generate a reload if needed. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 750 | if (reg_usage.mode[j] != HRmWrite) { |
| 751 | m = hregNumber(vreg); |
| 752 | assert(m >= 0 && m < n_vregs); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 753 | assert(vreg_info[m].reg_class != HRcINVALID); |
| 754 | EMIT_INSTR( (*genReload)( state[k].rreg, |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 755 | vreg_info[m].spill_offset ) ); |
| 756 | } |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 757 | continue; |
| 758 | } |
| 759 | |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 760 | /* There are no free rregs, but perhaps we can find one which |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 761 | is bound to a vreg which is now dead. If so, use that. |
| 762 | NOTE, we could improve this by selecting an rreg for which |
| 763 | the next live-range event is as far ahead as possible. */ |
| 764 | for (k = 0; k < n_state; k++) { |
| 765 | if (state[k].disp == Bound |
| 766 | && hregClass(state[k].rreg) == hregClass(vreg)) { |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 767 | m = hregNumber(state[k].vreg); |
| 768 | assert(m >= 0 && m < n_vregs); |
| 769 | if (vreg_info[m].dead_before <= ii) { |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 770 | /* Ok, it's gone dead before this insn. We can use |
| 771 | it. */ |
| 772 | break; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 773 | } |
| 774 | } |
| 775 | } |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 776 | if (k < n_state) { |
| 777 | assert(state[k].disp == Bound); |
| 778 | state[k].vreg = vreg; |
| 779 | addToHRegRemap(&remap, vreg, state[k].rreg); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 780 | /* Generate a reload if needed. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 781 | if (reg_usage.mode[j] != HRmWrite) { |
| 782 | m = hregNumber(vreg); |
| 783 | assert(m >= 0 && m < n_vregs); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 784 | assert(vreg_info[m].reg_class != HRcINVALID); |
| 785 | EMIT_INSTR( (*genReload)( state[k].rreg, |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 786 | vreg_info[m].spill_offset ) ); |
| 787 | } |
| 788 | continue; |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 789 | } |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 790 | |
| 791 | /* Well, now we have no option but to spill a vreg. It's |
| 792 | important to make a good choice of vreg to spill, and of |
| 793 | course we need to be careful not to spill a vreg which is |
| 794 | needed by this insn. */ |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 795 | |
| 796 | /* First, mark in the state, those rregs which are not spill |
| 797 | candidates, due to holding a vreg mentioned by this |
| 798 | instruction. Or being of the wrong class. */ |
| 799 | for (k = 0; k < n_state; k++) { |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 800 | state[k].is_spill_cand = False; |
| 801 | if (state[k].disp != Bound) |
| 802 | continue; |
| 803 | if (hregClass(state[k].rreg) != hregClass(vreg)) |
| 804 | continue; |
| 805 | state[k].is_spill_cand = True; |
| 806 | for (m = 0; m < reg_usage.n_used; m++) { |
| 807 | if (state[k].vreg == reg_usage.hreg[m]) { |
| 808 | state[k].is_spill_cand = False; |
| 809 | break; |
| 810 | } |
| 811 | } |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 812 | } |
| 813 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 814 | /* We can choose to spill any rreg satisfying |
| 815 | state[r].is_spill_cand (so to speak). Choose r so that |
| 816 | the next use of its associated vreg is as far ahead as |
| 817 | possible, in the hope that this will minimise the number |
| 818 | of consequent reloads required. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 819 | spillee |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 820 | = findMostDistantlyMentionedVReg ( |
| 821 | getRegUsage, instrs_in, ii+1, state, n_state ); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 822 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 823 | if (spillee == -1) { |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 824 | /* Hmmmmm. There don't appear to be any spill candidates. |
| 825 | We're hosed. */ |
| 826 | fprintf(stderr, "reg_alloc: can't find a register in class: "); |
| 827 | ppHRegClass(stderr, hregClass(vreg)); |
| 828 | fprintf(stderr, "\n"); |
| 829 | panic("reg_alloc: can't create a free register."); |
| 830 | } |
| 831 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 832 | /* Right. So we're going to spill state[spillee]. */ |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 833 | assert(spillee >= 0 && spillee < n_state); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 834 | assert(state[spillee].disp == Bound); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 835 | /* check it's the right class */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 836 | assert(hregClass(state[spillee].rreg) == hregClass(vreg)); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 837 | /* check we're not ejecting the vreg for which we are trying |
| 838 | to free up a register. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 839 | assert(state[spillee].vreg != vreg); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 840 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 841 | m = hregNumber(state[spillee].vreg); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 842 | assert(m >= 0 && m < n_vregs); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 843 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 844 | /* So here's the spill store. Assert that we're spilling a |
| 845 | live vreg. */ |
| 846 | assert(vreg_info[m].dead_before > ii); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 847 | assert(vreg_info[m].reg_class != HRcINVALID); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 848 | EMIT_INSTR( (*genSpill)( state[spillee].rreg, |
| 849 | vreg_info[m].spill_offset ) ); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 850 | |
| 851 | /* Update the state to reflect the new assignment for this |
| 852 | rreg. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 853 | state[spillee].vreg = vreg; |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 854 | |
| 855 | /* Now, if this vreg is being read or modified (as opposed to |
| 856 | written), we have to generate a reload for it. */ |
| 857 | if (reg_usage.mode[j] != HRmWrite) { |
| 858 | m = hregNumber(vreg); |
| 859 | assert(m >= 0 && m < n_vregs); |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 860 | assert(vreg_info[m].reg_class != HRcINVALID); |
| 861 | EMIT_INSTR( (*genReload)( state[spillee].rreg, |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 862 | vreg_info[m].spill_offset ) ); |
| 863 | |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 864 | } |
| 865 | |
| 866 | /* So after much twisting and turning, we have vreg mapped to |
| 867 | state[furthest_k].rreg. Note that in the map. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 868 | addToHRegRemap(&remap, vreg, state[spillee].rreg); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 869 | |
| 870 | } /* iterate over registers in this instruction. */ |
| 871 | |
| 872 | /* We've finished clowning around with registers in this instruction. |
| 873 | Three results: |
| 874 | - the running state[] has been updated |
| 875 | - a suitable vreg->rreg mapping for this instruction has been |
| 876 | constructed |
| 877 | - spill and reload instructions may have been emitted. |
| 878 | |
| 879 | The final step is to apply the mapping to the instruction, |
| 880 | and emit that. |
| 881 | */ |
| 882 | |
sewardj | 2cd80dc | 2004-07-02 15:20:40 +0000 | [diff] [blame] | 883 | /* NOTE, DESTRUCTIVELY MODIFIES instrs_in->arr[ii]. */ |
| 884 | (*mapRegs)( &remap, instrs_in->arr[ii] ); |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 885 | EMIT_INSTR( instrs_in->arr[ii] ); |
| 886 | |
| 887 | /* ------ Post-instruction actions for fixed rreg uses ------ */ |
| 888 | |
| 889 | /* Now we need to check for rregs exiting fixed live ranges |
sewardj | 6f37cce | 2004-07-03 19:44:54 +0000 | [diff] [blame] | 890 | after this instruction, and if so mark them as free. */ |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 891 | |
| 892 | for (j = 0; j < rreg_info_used; j++) { |
| 893 | if (rreg_info[j].dead_before == ii+1) { |
| 894 | /* rreg_info[j].rreg is exiting a hard live range. Mark |
| 895 | it as such in the main state array. */ |
| 896 | for (k = 0; k < n_state; k++) |
| 897 | if (state[k].rreg == rreg_info[j].rreg) |
| 898 | break; |
| 899 | /* If this assertion fails, we don't have an entry for |
| 900 | this rreg. Which we should. */ |
| 901 | assert(k < n_state); |
| 902 | assert(state[k].disp == Unavail); |
| 903 | state[k].disp = Free; |
| 904 | state[k].vreg = INVALID_HREG; |
| 905 | } |
| 906 | } |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 907 | |
| 908 | } /* iterate over insns */ |
| 909 | |
sewardj | 0ec3325 | 2004-07-03 13:30:00 +0000 | [diff] [blame] | 910 | /* ------ END: Process each insn in turn. ------ */ |
| 911 | |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 912 | free(state); |
sewardj | 62c4142 | 2004-07-01 21:00:22 +0000 | [diff] [blame] | 913 | free(rreg_info); |
| 914 | if (vreg_info) free(vreg_info); |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 915 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 916 | return instrs_out; |
sewardj | af5a522 | 2004-07-01 23:14:42 +0000 | [diff] [blame] | 917 | |
sewardj | b3d4ce7 | 2004-07-02 07:09:23 +0000 | [diff] [blame] | 918 | # undef INVALID_INSTRNO |
| 919 | # undef EMIT_INSTR |
sewardj | 73b58bc | 2004-07-01 18:30:56 +0000 | [diff] [blame] | 920 | } |
| 921 | |
| 922 | |
| 923 | |
| 924 | /*---------------------------------------------------------------*/ |
| 925 | /*--- reg_alloc.c ---*/ |
| 926 | /*---------------------------------------------------------------*/ |