1 /*
2 * Copyright (c) 2013, Red Hat Inc.
3 * All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 */
21
22 #include <stdlib.h>
23 #include "immediate_aarch64.hpp"
24
25 // there are at most 2^13 possible logical immediate encodings
26 // however, some combinations of immr and imms are invalid
27 static const unsigned LI_TABLE_SIZE = (1 << 13);
28
29 static int li_table_entry_count;
30
31 // for forward lookup we just use a direct array lookup
32 // and assume that the cient has supplied a valid encoding
33 // table[encoding] = immediate
34 static u_int64_t LITable[LI_TABLE_SIZE];
35
36 // for reverse lookup we need a sparse map so we store a table of
37 // immediate and encoding pairs sorted by immediate value
38
39 struct li_pair {
40 u_int64_t immediate;
41 u_int32_t encoding;
42 };
43
44 static struct li_pair InverseLITable[LI_TABLE_SIZE];
45
46 // comparator to sort entries in the inverse table
47 int compare_immediate_pair(const void *i1, const void *i2)
48 {
49 struct li_pair *li1 = (struct li_pair *)i1;
50 struct li_pair *li2 = (struct li_pair *)i2;
51 if (li1->immediate < li2->immediate) {
52 return -1;
53 }
54 if (li1->immediate > li2->immediate) {
55 return 1;
56 }
57 return 0;
58 }
59
60 // helper functions used by expandLogicalImmediate
61
62 // for i = 1, ... N result<i-1> = 1 other bits are zero
63 static inline u_int64_t ones(int N)
64 {
65 return (N == 64 ? (u_int64_t)-1UL : ((1UL << N) - 1));
66 }
67
68 /*
69 * bit twiddling helpers for instruction decode
70 */
71
72 // 32 bit mask with bits [hi,...,lo] set
73 static inline u_int32_t mask32(int hi = 31, int lo = 0)
74 {
75 int nbits = (hi + 1) - lo;
76 return ((1 << nbits) - 1) << lo;
77 }
78
79 static inline u_int64_t mask64(int hi = 63, int lo = 0)
80 {
81 int nbits = (hi + 1) - lo;
82 return ((1L << nbits) - 1) << lo;
83 }
84
85 // pick bits [hi,...,lo] from val
86 static inline u_int32_t pick32(u_int32_t val, int hi = 31, int lo = 0)
87 {
88 return (val & mask32(hi, lo));
89 }
90
91 // pick bits [hi,...,lo] from val
92 static inline u_int64_t pick64(u_int64_t val, int hi = 31, int lo = 0)
93 {
94 return (val & mask64(hi, lo));
95 }
96
97 // mask [hi,lo] and shift down to start at bit 0
98 static inline u_int32_t pickbits32(u_int32_t val, int hi = 31, int lo = 0)
99 {
100 return (pick32(val, hi, lo) >> lo);
101 }
102
103 // mask [hi,lo] and shift down to start at bit 0
104 static inline u_int64_t pickbits64(u_int64_t val, int hi = 63, int lo = 0)
105 {
106 return (pick64(val, hi, lo) >> lo);
107 }
108
109 // result<0> to val<N>
110 static inline u_int64_t pickbit(u_int64_t val, int N)
111 {
112 return pickbits64(val, N, N);
113 }
114
115 static inline u_int32_t uimm(u_int32_t val, int hi, int lo)
116 {
117 return pickbits32(val, hi, lo);
118 }
119
120 // SPEC bits(M*N) Replicate(bits(M) x, integer N);
121 // this is just an educated guess
122
123 u_int64_t replicate(u_int64_t bits, int nbits, int count)
124 {
125 u_int64_t result = 0;
126 // nbits may be 64 in which case we want mask to be -1
127 u_int64_t mask = ones(nbits);
128 for (int i = 0; i < count ; i++) {
129 result <<= nbits;
130 result |= (bits & mask);
131 }
132 return result;
133 }
134
135 // this function writes the supplied bimm reference and returns a
136 // boolean to indicate success (1) or fail (0) because an illegal
137 // encoding must be treated as an UNALLOC instruction
138
139 // construct a 32 bit immediate value for a logical immediate operation
140 int expandLogicalImmediate(u_int32_t immN, u_int32_t immr,
141 u_int32_t imms, u_int64_t &bimm)
142 {
143 int len; // ought to be <= 6
144 u_int32_t levels; // 6 bits
145 u_int32_t tmask_and; // 6 bits
146 u_int32_t wmask_and; // 6 bits
147 u_int32_t tmask_or; // 6 bits
148 u_int32_t wmask_or; // 6 bits
149 u_int64_t imm64; // 64 bits
150 u_int64_t tmask, wmask; // 64 bits
151 u_int32_t S, R, diff; // 6 bits?
152
153 if (immN == 1) {
154 len = 6; // looks like 7 given the spec above but this cannot be!
155 } else {
156 len = 0;
157 u_int32_t val = (~imms & 0x3f);
158 for (int i = 5; i > 0; i--) {
159 if (val & (1 << i)) {
160 len = i;
161 break;
162 }
163 }
164 if (len < 1) {
165 return 0;
166 }
167 // for valid inputs leading 1s in immr must be less than leading
168 // zeros in imms
169 int len2 = 0; // ought to be < len
170 u_int32_t val2 = (~immr & 0x3f);
171 for (int i = 5; i > 0; i--) {
172 if (!(val2 & (1 << i))) {
173 len2 = i;
174 break;
175 }
176 }
177 if (len2 >= len) {
178 return 0;
179 }
180 }
181
182 levels = (1 << len) - 1;
183
184 if ((imms & levels) == levels) {
185 return 0;
186 }
187
188 S = imms & levels;
189 R = immr & levels;
190
191 // 6 bit arithmetic!
192 diff = S - R;
193 tmask_and = (diff | ~levels) & 0x3f;
194 tmask_or = (diff & levels) & 0x3f;
195 tmask = 0xffffffffffffffffULL;
196
197 for (int i = 0; i < 6; i++) {
198 int nbits = 1 << i;
199 u_int64_t and_bit = pickbit(tmask_and, i);
200 u_int64_t or_bit = pickbit(tmask_or, i);
201 u_int64_t and_bits_sub = replicate(and_bit, 1, nbits);
202 u_int64_t or_bits_sub = replicate(or_bit, 1, nbits);
203 u_int64_t and_bits_top = (and_bits_sub << nbits) | ones(nbits);
204 u_int64_t or_bits_top = (0 << nbits) | or_bits_sub;
205
206 tmask = ((tmask
207 & (replicate(and_bits_top, 2 * nbits, 32 / nbits)))
208 | replicate(or_bits_top, 2 * nbits, 32 / nbits));
209 }
210
211 wmask_and = (immr | ~levels) & 0x3f;
212 wmask_or = (immr & levels) & 0x3f;
213
214 wmask = 0;
215
216 for (int i = 0; i < 6; i++) {
217 int nbits = 1 << i;
218 u_int64_t and_bit = pickbit(wmask_and, i);
219 u_int64_t or_bit = pickbit(wmask_or, i);
220 u_int64_t and_bits_sub = replicate(and_bit, 1, nbits);
221 u_int64_t or_bits_sub = replicate(or_bit, 1, nbits);
222 u_int64_t and_bits_top = (ones(nbits) << nbits) | and_bits_sub;
223 u_int64_t or_bits_top = (or_bits_sub << nbits) | 0;
224
225 wmask = ((wmask
226 & (replicate(and_bits_top, 2 * nbits, 32 / nbits)))
227 | replicate(or_bits_top, 2 * nbits, 32 / nbits));
228 }
229
230 if (diff & (1U << 6)) {
231 imm64 = tmask & wmask;
232 } else {
233 imm64 = tmask | wmask;
234 }
235
236
237 bimm = imm64;
238 return 1;
239 }
240
241 // constructor to initialise the lookup tables
242
243 static void initLITables() __attribute__ ((constructor));
244 static void initLITables()
245 {
246 li_table_entry_count = 0;
247 for (unsigned index = 0; index < LI_TABLE_SIZE; index++) {
248 u_int32_t N = uimm(index, 12, 12);
249 u_int32_t immr = uimm(index, 11, 6);
250 u_int32_t imms = uimm(index, 5, 0);
251 if (expandLogicalImmediate(N, immr, imms, LITable[index])) {
252 InverseLITable[li_table_entry_count].immediate = LITable[index];
253 InverseLITable[li_table_entry_count].encoding = index;
254 li_table_entry_count++;
255 }
256 }
257 // now sort the inverse table
258 qsort(InverseLITable, li_table_entry_count,
259 sizeof(InverseLITable[0]), compare_immediate_pair);
260 }
261
262 // public APIs provided for logical immediate lookup and reverse lookup
263
264 u_int64_t logical_immediate_for_encoding(u_int32_t encoding)
265 {
266 return LITable[encoding];
267 }
268
269 u_int32_t encoding_for_logical_immediate(u_int64_t immediate)
270 {
271 struct li_pair pair;
272 struct li_pair *result;
273
274 pair.immediate = immediate;
275
276 result = (struct li_pair *)
277 bsearch(&pair, InverseLITable, li_table_entry_count,
278 sizeof(InverseLITable[0]), compare_immediate_pair);
279
280 if (result) {
281 return result->encoding;
282 }
283
284 return 0xffffffff;
285 }
286
287 // floating point immediates are encoded in 8 bits
288 // fpimm[7] = sign bit
289 // fpimm[6:4] = signed exponent
290 // fpimm[3:0] = fraction (assuming leading 1)
291 // i.e. F = s * 1.f * 2^(e - b)
292
293 u_int64_t fp_immediate_for_encoding(u_int32_t imm8, int is_dp)
294 {
295 union {
296 float fpval;
297 double dpval;
298 u_int64_t val;
299 };
300
301 u_int32_t s, e, f;
302 s = (imm8 >> 7 ) & 0x1;
303 e = (imm8 >> 4) & 0x7;
304 f = imm8 & 0xf;
305 // the fp value is s * n/16 * 2r where n is 16+e
306 fpval = (16.0 + f) / 16.0;
307 // n.b. exponent is signed
308 if (e < 4) {
309 int epos = e;
310 for (int i = 0; i <= epos; i++) {
311 fpval *= 2.0;
312 }
313 } else {
314 int eneg = 7 - e;
315 for (int i = 0; i < eneg; i++) {
316 fpval /= 2.0;
317 }
318 }
319
320 if (s) {
321 fpval = -fpval;
322 }
323 if (is_dp) {
324 dpval = (double)fpval;
325 }
326 return val;
327 }
328
329 u_int32_t encoding_for_fp_immediate(float immediate)
330 {
331 // given a float which is of the form
332 //
333 // s * n/16 * 2r
334 //
335 // where n is 16+f and imm1:s, imm4:f, simm3:r
336 // return the imm8 result [s:r:f]
337 //
338
339 union {
340 float fpval;
341 u_int32_t val;
342 };
343 fpval = immediate;
344 u_int32_t s, r, f, res;
345 // sign bit is 31
346 s = (val >> 31) & 0x1;
347 // exponent is bits 30-23 but we only want the bottom 3 bits
348 // strictly we ought to check that the bits bits 30-25 are
349 // either all 1s or all 0s
350 r = (val >> 23) & 0x7;
351 // fraction is bits 22-0
352 f = (val >> 19) & 0xf;
353 res = (s << 7) | (r << 4) | f;
354 return res;
355 }
356