1 /*
2 * Copyright (c) 2021 Calvin Rose
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20 * IN THE SOFTWARE.
21 */
22
23 #ifndef JANET_AMALG
24 #include "features.h"
25 #include <janet.h>
26 #include "regalloc.h"
27 #include "util.h"
28 #endif
29
janetc_regalloc_init(JanetcRegisterAllocator * ra)30 void janetc_regalloc_init(JanetcRegisterAllocator *ra) {
31 ra->chunks = NULL;
32 ra->count = 0;
33 ra->capacity = 0;
34 ra->max = 0;
35 ra->regtemps = 0;
36 }
37
janetc_regalloc_deinit(JanetcRegisterAllocator * ra)38 void janetc_regalloc_deinit(JanetcRegisterAllocator *ra) {
39 janet_free(ra->chunks);
40 }
41
42 /* Fallbacks for when ctz not available */
43 #ifdef __GNUC__
44 #define count_trailing_zeros(x) __builtin_ctz(x)
45 #define count_trailing_ones(x) __builtin_ctz(~(x))
46 #else
count_trailing_ones(uint32_t x)47 static int32_t count_trailing_ones(uint32_t x) {
48 int32_t ret = 0;
49 while (x & 1) {
50 ret++;
51 x >>= 1;
52 }
53 return ret;
54 }
55 #define count_trailing_zeros(x) count_trailing_ones(~(x))
56 #endif
57
58 /* Get ith bit */
59 #define ithbit(I) ((uint32_t)1 << (I))
60
61 /* Get N bits */
62 #define nbits(N) (ithbit(N) - 1)
63
64 /* Copy a register allocator */
janetc_regalloc_clone(JanetcRegisterAllocator * dest,JanetcRegisterAllocator * src)65 void janetc_regalloc_clone(JanetcRegisterAllocator *dest, JanetcRegisterAllocator *src) {
66 size_t size;
67 dest->count = src->count;
68 dest->capacity = src->capacity;
69 dest->max = src->max;
70 size = sizeof(uint32_t) * (size_t) dest->capacity;
71 dest->regtemps = 0;
72 if (size) {
73 dest->chunks = janet_malloc(size);
74 if (!dest->chunks) {
75 JANET_OUT_OF_MEMORY;
76 }
77 memcpy(dest->chunks, src->chunks, size);
78 } else {
79 dest->chunks = NULL;
80 }
81 }
82
83 /* Allocate one more chunk in chunks */
pushchunk(JanetcRegisterAllocator * ra)84 static void pushchunk(JanetcRegisterAllocator *ra) {
85 /* Registers 240-255 are always allocated (reserved) */
86 uint32_t chunk = ra->count == 7 ? 0xFFFF0000 : 0;
87 int32_t newcount = ra->count + 1;
88 if (newcount > ra->capacity) {
89 int32_t newcapacity = newcount * 2;
90 ra->chunks = janet_realloc(ra->chunks, (size_t) newcapacity * sizeof(uint32_t));
91 if (!ra->chunks) {
92 JANET_OUT_OF_MEMORY;
93 }
94 ra->capacity = newcapacity;
95 }
96 ra->chunks[ra->count] = chunk;
97 ra->count = newcount;
98 }
99
100 /* Reallocate a given register */
janetc_regalloc_touch(JanetcRegisterAllocator * ra,int32_t reg)101 void janetc_regalloc_touch(JanetcRegisterAllocator *ra, int32_t reg) {
102 int32_t chunk = reg >> 5;
103 int32_t bit = reg & 0x1F;
104 while (chunk >= ra->count) pushchunk(ra);
105 ra->chunks[chunk] |= ithbit(bit);
106 }
107
108 /* Allocate one register. */
janetc_regalloc_1(JanetcRegisterAllocator * ra)109 int32_t janetc_regalloc_1(JanetcRegisterAllocator *ra) {
110 /* Get the nth bit in the array */
111 int32_t bit, chunk, nchunks, reg;
112 bit = -1;
113 nchunks = ra->count;
114 for (chunk = 0; chunk < nchunks; chunk++) {
115 uint32_t block = ra->chunks[chunk];
116 if (block == 0xFFFFFFFF) continue;
117 bit = count_trailing_ones(block);
118 break;
119 }
120 /* No reg found */
121 if (bit == -1) {
122 pushchunk(ra);
123 bit = 0;
124 chunk = nchunks;
125 }
126 /* set the bit at index bit in chunk */
127 ra->chunks[chunk] |= ithbit(bit);
128 reg = (chunk << 5) + bit;
129 if (reg > ra->max)
130 ra->max = reg;
131 return reg;
132 }
133
134 /* Free a register. The register must have been previously allocated
135 * without being freed. */
janetc_regalloc_free(JanetcRegisterAllocator * ra,int32_t reg)136 void janetc_regalloc_free(JanetcRegisterAllocator *ra, int32_t reg) {
137 int32_t chunk = reg >> 5;
138 int32_t bit = reg & 0x1F;
139 ra->chunks[chunk] &= ~ithbit(bit);
140 }
141
142 /* Get a register that will fit in 8 bits (< 256). Do not call this
143 * twice with the same value of nth without calling janetc_regalloc_free
144 * on the returned register before. */
janetc_regalloc_temp(JanetcRegisterAllocator * ra,JanetcRegisterTemp nth)145 int32_t janetc_regalloc_temp(JanetcRegisterAllocator *ra, JanetcRegisterTemp nth) {
146 int32_t oldmax = ra->max;
147 if (ra->regtemps & (1 << nth)) {
148 JANET_EXIT("regtemp already allocated");
149 }
150 ra->regtemps |= 1 << nth;
151 int32_t reg = janetc_regalloc_1(ra);
152 if (reg > 0xFF) {
153 reg = 0xF0 + nth;
154 ra->max = (reg > oldmax) ? reg : oldmax;
155 }
156 return reg;
157 }
158
janetc_regalloc_freetemp(JanetcRegisterAllocator * ra,int32_t reg,JanetcRegisterTemp nth)159 void janetc_regalloc_freetemp(JanetcRegisterAllocator *ra, int32_t reg, JanetcRegisterTemp nth) {
160 ra->regtemps &= ~(1 << nth);
161 if (reg < 0xF0)
162 janetc_regalloc_free(ra, reg);
163 }
164