1 // Copyright 2019, VIXL authors
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //
7 // * Redistributions of source code must retain the above copyright notice,
8 // this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above copyright notice,
10 // this list of conditions and the following disclaimer in the documentation
11 // and/or other materials provided with the distribution.
12 // * Neither the name of ARM Limited nor the names of its contributors may be
13 // used to endorse or promote products derived from this software without
14 // specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27 #include <string>
28
29 #include "../globals-vixl.h"
30 #include "../utils-vixl.h"
31
32 #include "decoder-aarch64.h"
33 #include "decoder-constants-aarch64.h"
34
35 namespace vixl {
36 namespace aarch64 {
37
Decode(const Instruction * instr)38 void Decoder::Decode(const Instruction* instr) {
39 std::list<DecoderVisitor*>::iterator it;
40 for (it = visitors_.begin(); it != visitors_.end(); it++) {
41 VIXL_ASSERT((*it)->IsConstVisitor());
42 }
43 VIXL_ASSERT(compiled_decoder_root_ != NULL);
44 compiled_decoder_root_->Decode(instr);
45 }
46
Decode(Instruction * instr)47 void Decoder::Decode(Instruction* instr) {
48 compiled_decoder_root_->Decode(const_cast<const Instruction*>(instr));
49 }
50
AddDecodeNode(const DecodeNode & node)51 void Decoder::AddDecodeNode(const DecodeNode& node) {
52 if (decode_nodes_.count(node.GetName()) == 0) {
53 decode_nodes_.insert(std::make_pair(node.GetName(), node));
54 }
55 }
56
GetDecodeNode(std::string name)57 DecodeNode* Decoder::GetDecodeNode(std::string name) {
58 if (decode_nodes_.count(name) != 1) {
59 std::string msg = "Can't find decode node " + name + ".\n";
60 VIXL_ABORT_WITH_MSG(msg.c_str());
61 }
62 return &decode_nodes_[name];
63 }
64
ConstructDecodeGraph()65 void Decoder::ConstructDecodeGraph() {
66 // Add all of the decoding nodes to the Decoder.
67 for (unsigned i = 0; i < ArrayLength(kDecodeMapping); i++) {
68 AddDecodeNode(DecodeNode(kDecodeMapping[i], this));
69
70 // Add a node for each instruction form named, identified by having no '_'
71 // prefix on the node name.
72 const DecodeMapping& map = kDecodeMapping[i];
73 for (unsigned j = 0; j < map.mapping.size(); j++) {
74 if ((map.mapping[j].handler != NULL) &&
75 (map.mapping[j].handler[0] != '_')) {
76 AddDecodeNode(DecodeNode(map.mapping[j].handler, this));
77 }
78 }
79 }
80
81 // Add an "unallocated" node, used when an instruction encoding is not
82 // recognised by the decoding graph.
83 AddDecodeNode(DecodeNode("unallocated", this));
84
85 // Compile the graph from the root.
86 compiled_decoder_root_ = GetDecodeNode("Root")->Compile(this);
87 }
88
AppendVisitor(DecoderVisitor * new_visitor)89 void Decoder::AppendVisitor(DecoderVisitor* new_visitor) {
90 visitors_.push_back(new_visitor);
91 }
92
93
PrependVisitor(DecoderVisitor * new_visitor)94 void Decoder::PrependVisitor(DecoderVisitor* new_visitor) {
95 visitors_.push_front(new_visitor);
96 }
97
98
InsertVisitorBefore(DecoderVisitor * new_visitor,DecoderVisitor * registered_visitor)99 void Decoder::InsertVisitorBefore(DecoderVisitor* new_visitor,
100 DecoderVisitor* registered_visitor) {
101 std::list<DecoderVisitor*>::iterator it;
102 for (it = visitors_.begin(); it != visitors_.end(); it++) {
103 if (*it == registered_visitor) {
104 visitors_.insert(it, new_visitor);
105 return;
106 }
107 }
108 // We reached the end of the list. The last element must be
109 // registered_visitor.
110 VIXL_ASSERT(*it == registered_visitor);
111 visitors_.insert(it, new_visitor);
112 }
113
114
InsertVisitorAfter(DecoderVisitor * new_visitor,DecoderVisitor * registered_visitor)115 void Decoder::InsertVisitorAfter(DecoderVisitor* new_visitor,
116 DecoderVisitor* registered_visitor) {
117 std::list<DecoderVisitor*>::iterator it;
118 for (it = visitors_.begin(); it != visitors_.end(); it++) {
119 if (*it == registered_visitor) {
120 it++;
121 visitors_.insert(it, new_visitor);
122 return;
123 }
124 }
125 // We reached the end of the list. The last element must be
126 // registered_visitor.
127 VIXL_ASSERT(*it == registered_visitor);
128 visitors_.push_back(new_visitor);
129 }
130
131
RemoveVisitor(DecoderVisitor * visitor)132 void Decoder::RemoveVisitor(DecoderVisitor* visitor) {
133 visitors_.remove(visitor);
134 }
135
VisitNamedInstruction(const Instruction * instr,const std::string & name)136 void Decoder::VisitNamedInstruction(const Instruction* instr,
137 const std::string& name) {
138 std::list<DecoderVisitor*>::iterator it;
139 Metadata m = {{"form", name}};
140 for (it = visitors_.begin(); it != visitors_.end(); it++) {
141 (*it)->Visit(&m, instr);
142 }
143 }
144
145 // Initialise empty vectors for sampled bits and pattern table.
146 const std::vector<uint8_t> DecodeNode::kEmptySampledBits;
147 const std::vector<DecodePattern> DecodeNode::kEmptyPatternTable;
148
CompileNodeForBits(Decoder * decoder,std::string name,uint32_t bits)149 void DecodeNode::CompileNodeForBits(Decoder* decoder,
150 std::string name,
151 uint32_t bits) {
152 DecodeNode* n = decoder->GetDecodeNode(name);
153 VIXL_ASSERT(n != NULL);
154 if (!n->IsCompiled()) {
155 n->Compile(decoder);
156 }
157 VIXL_ASSERT(n->IsCompiled());
158 compiled_node_->SetNodeForBits(bits, n->GetCompiledNode());
159 }
160
161
162 #define INSTANTIATE_TEMPLATE_M(M) \
163 case 0x##M: \
164 bit_extract_fn = &Instruction::ExtractBits<0x##M>; \
165 break;
166 #define INSTANTIATE_TEMPLATE_MV(M, V) \
167 case 0x##M##V: \
168 bit_extract_fn = &Instruction::IsMaskedValue<0x##M, 0x##V>; \
169 break;
170
GetBitExtractFunctionHelper(uint32_t x,uint32_t y)171 BitExtractFn DecodeNode::GetBitExtractFunctionHelper(uint32_t x, uint32_t y) {
172 // Instantiate a templated bit extraction function for every pattern we
173 // might encounter. If the assertion in the default clause is reached, add a
174 // new instantiation below using the information in the failure message.
175 BitExtractFn bit_extract_fn = NULL;
176
177 // The arguments x and y represent the mask and value. If y is 0, x is the
178 // mask. Otherwise, y is the mask, and x is the value to compare against a
179 // masked result.
180 uint64_t signature = (static_cast<uint64_t>(y) << 32) | x;
181 switch (signature) {
182 INSTANTIATE_TEMPLATE_M(00000001);
183 INSTANTIATE_TEMPLATE_M(00000010);
184 INSTANTIATE_TEMPLATE_M(0000001f);
185 INSTANTIATE_TEMPLATE_M(00000060);
186 INSTANTIATE_TEMPLATE_M(00000100);
187 INSTANTIATE_TEMPLATE_M(00000200);
188 INSTANTIATE_TEMPLATE_M(00000400);
189 INSTANTIATE_TEMPLATE_M(00000800);
190 INSTANTIATE_TEMPLATE_M(00000c00);
191 INSTANTIATE_TEMPLATE_M(00000c10);
192 INSTANTIATE_TEMPLATE_M(00000fc0);
193 INSTANTIATE_TEMPLATE_M(00001000);
194 INSTANTIATE_TEMPLATE_M(00001400);
195 INSTANTIATE_TEMPLATE_M(00001800);
196 INSTANTIATE_TEMPLATE_M(00001c00);
197 INSTANTIATE_TEMPLATE_M(00002000);
198 INSTANTIATE_TEMPLATE_M(00002010);
199 INSTANTIATE_TEMPLATE_M(00002400);
200 INSTANTIATE_TEMPLATE_M(00003000);
201 INSTANTIATE_TEMPLATE_M(00003020);
202 INSTANTIATE_TEMPLATE_M(00003400);
203 INSTANTIATE_TEMPLATE_M(00003800);
204 INSTANTIATE_TEMPLATE_M(00003c00);
205 INSTANTIATE_TEMPLATE_M(00013000);
206 INSTANTIATE_TEMPLATE_M(00020000);
207 INSTANTIATE_TEMPLATE_M(00020010);
208 INSTANTIATE_TEMPLATE_M(000203e0);
209 INSTANTIATE_TEMPLATE_M(000303e0);
210 INSTANTIATE_TEMPLATE_M(00060000);
211 INSTANTIATE_TEMPLATE_M(00061000);
212 INSTANTIATE_TEMPLATE_M(00070000);
213 INSTANTIATE_TEMPLATE_M(000703c0);
214 INSTANTIATE_TEMPLATE_M(00080000);
215 INSTANTIATE_TEMPLATE_M(00090000);
216 INSTANTIATE_TEMPLATE_M(000f0000);
217 INSTANTIATE_TEMPLATE_M(000f0010);
218 INSTANTIATE_TEMPLATE_M(00100000);
219 INSTANTIATE_TEMPLATE_M(00180000);
220 INSTANTIATE_TEMPLATE_M(001d1c00);
221 INSTANTIATE_TEMPLATE_M(001f0000);
222 INSTANTIATE_TEMPLATE_M(001f2000);
223 INSTANTIATE_TEMPLATE_M(001f3000);
224 INSTANTIATE_TEMPLATE_M(00400000);
225 INSTANTIATE_TEMPLATE_M(00400800);
226 INSTANTIATE_TEMPLATE_M(00403000);
227 INSTANTIATE_TEMPLATE_M(00500800);
228 INSTANTIATE_TEMPLATE_M(00583000);
229 INSTANTIATE_TEMPLATE_M(005f0000);
230 INSTANTIATE_TEMPLATE_M(00800000);
231 INSTANTIATE_TEMPLATE_M(00800400);
232 INSTANTIATE_TEMPLATE_M(00800c1e);
233 INSTANTIATE_TEMPLATE_M(0080101f);
234 INSTANTIATE_TEMPLATE_M(00801c00);
235 INSTANTIATE_TEMPLATE_M(00803000);
236 INSTANTIATE_TEMPLATE_M(00803c00);
237 INSTANTIATE_TEMPLATE_M(009f0000);
238 INSTANTIATE_TEMPLATE_M(009f2000);
239 INSTANTIATE_TEMPLATE_M(00c00000);
240 INSTANTIATE_TEMPLATE_M(00c00010);
241 INSTANTIATE_TEMPLATE_M(00c0001f);
242 INSTANTIATE_TEMPLATE_M(00c00200);
243 INSTANTIATE_TEMPLATE_M(00c00400);
244 INSTANTIATE_TEMPLATE_M(00c00c00);
245 INSTANTIATE_TEMPLATE_M(00c00c1c);
246 INSTANTIATE_TEMPLATE_M(00c01000);
247 INSTANTIATE_TEMPLATE_M(00c01400);
248 INSTANTIATE_TEMPLATE_M(00c01c00);
249 INSTANTIATE_TEMPLATE_M(00c02000);
250 INSTANTIATE_TEMPLATE_M(00c03000);
251 INSTANTIATE_TEMPLATE_M(00c03c00);
252 INSTANTIATE_TEMPLATE_M(00c83000);
253 INSTANTIATE_TEMPLATE_M(00cf0000);
254 INSTANTIATE_TEMPLATE_M(00d00200);
255 INSTANTIATE_TEMPLATE_M(00d80800);
256 INSTANTIATE_TEMPLATE_M(00d81800);
257 INSTANTIATE_TEMPLATE_M(00d81c00);
258 INSTANTIATE_TEMPLATE_M(00d82800);
259 INSTANTIATE_TEMPLATE_M(00d82c00);
260 INSTANTIATE_TEMPLATE_M(00d92400);
261 INSTANTIATE_TEMPLATE_M(00d93000);
262 INSTANTIATE_TEMPLATE_M(00db0000);
263 INSTANTIATE_TEMPLATE_M(00dc0000);
264 INSTANTIATE_TEMPLATE_M(00dc2000);
265 INSTANTIATE_TEMPLATE_M(00dd2000);
266 INSTANTIATE_TEMPLATE_M(00df0000);
267 INSTANTIATE_TEMPLATE_M(40000000);
268 INSTANTIATE_TEMPLATE_M(40000010);
269 INSTANTIATE_TEMPLATE_M(40000c00);
270 INSTANTIATE_TEMPLATE_M(40002000);
271 INSTANTIATE_TEMPLATE_M(40002010);
272 INSTANTIATE_TEMPLATE_M(40003000);
273 INSTANTIATE_TEMPLATE_M(40003c00);
274 INSTANTIATE_TEMPLATE_M(400f0000);
275 INSTANTIATE_TEMPLATE_M(400f0400);
276 INSTANTIATE_TEMPLATE_M(401f2000);
277 INSTANTIATE_TEMPLATE_M(40400800);
278 INSTANTIATE_TEMPLATE_M(40400c00);
279 INSTANTIATE_TEMPLATE_M(40403c00);
280 INSTANTIATE_TEMPLATE_M(40800000);
281 INSTANTIATE_TEMPLATE_M(40800c00);
282 INSTANTIATE_TEMPLATE_M(40802000);
283 INSTANTIATE_TEMPLATE_M(40802010);
284 INSTANTIATE_TEMPLATE_M(40803400);
285 INSTANTIATE_TEMPLATE_M(40803c00);
286 INSTANTIATE_TEMPLATE_M(40c00000);
287 INSTANTIATE_TEMPLATE_M(40c00c00);
288 INSTANTIATE_TEMPLATE_M(40c00c10);
289 INSTANTIATE_TEMPLATE_M(40c01c00);
290 INSTANTIATE_TEMPLATE_M(40c02000);
291 INSTANTIATE_TEMPLATE_M(40c02010);
292 INSTANTIATE_TEMPLATE_M(40c02c00);
293 INSTANTIATE_TEMPLATE_M(40c03c00);
294 INSTANTIATE_TEMPLATE_M(40c80000);
295 INSTANTIATE_TEMPLATE_M(40c90000);
296 INSTANTIATE_TEMPLATE_M(40cf0000);
297 INSTANTIATE_TEMPLATE_M(40d02000);
298 INSTANTIATE_TEMPLATE_M(40d02010);
299 INSTANTIATE_TEMPLATE_M(40d80000);
300 INSTANTIATE_TEMPLATE_M(40d81800);
301 INSTANTIATE_TEMPLATE_M(bf20c000);
302 INSTANTIATE_TEMPLATE_MV(00000003, 00000000);
303 INSTANTIATE_TEMPLATE_MV(00000003, 00000003);
304 INSTANTIATE_TEMPLATE_MV(0000001f, 0000001f);
305 INSTANTIATE_TEMPLATE_MV(00000210, 00000000);
306 INSTANTIATE_TEMPLATE_MV(000003e0, 00000000);
307 INSTANTIATE_TEMPLATE_MV(000003e0, 000003e0);
308 INSTANTIATE_TEMPLATE_MV(000003e1, 000003e0);
309 INSTANTIATE_TEMPLATE_MV(000003e3, 000003e0);
310 INSTANTIATE_TEMPLATE_MV(000003e3, 000003e3);
311 INSTANTIATE_TEMPLATE_MV(00000c00, 00000000);
312 INSTANTIATE_TEMPLATE_MV(00000fc0, 00000000);
313 INSTANTIATE_TEMPLATE_MV(000013e0, 00001000);
314 INSTANTIATE_TEMPLATE_MV(00001c00, 00000000);
315 INSTANTIATE_TEMPLATE_MV(00002400, 00000000);
316 INSTANTIATE_TEMPLATE_MV(00003000, 00000000);
317 INSTANTIATE_TEMPLATE_MV(00003000, 00001000);
318 INSTANTIATE_TEMPLATE_MV(00003000, 00002000);
319 INSTANTIATE_TEMPLATE_MV(00003000, 00003000);
320 INSTANTIATE_TEMPLATE_MV(00003010, 00000000);
321 INSTANTIATE_TEMPLATE_MV(00060000, 00000000);
322 INSTANTIATE_TEMPLATE_MV(00061000, 00000000);
323 INSTANTIATE_TEMPLATE_MV(00070000, 00030000);
324 INSTANTIATE_TEMPLATE_MV(0007309f, 0000001f);
325 INSTANTIATE_TEMPLATE_MV(00073ee0, 00033060);
326 INSTANTIATE_TEMPLATE_MV(000f0000, 00000000);
327 INSTANTIATE_TEMPLATE_MV(000f0010, 00000000);
328 INSTANTIATE_TEMPLATE_MV(00100200, 00000000);
329 INSTANTIATE_TEMPLATE_MV(00100210, 00000000);
330 INSTANTIATE_TEMPLATE_MV(00160000, 00000000);
331 INSTANTIATE_TEMPLATE_MV(00170000, 00000000);
332 INSTANTIATE_TEMPLATE_MV(001c0000, 00000000);
333 INSTANTIATE_TEMPLATE_MV(001d0000, 00000000);
334 INSTANTIATE_TEMPLATE_MV(001e0000, 00000000);
335 INSTANTIATE_TEMPLATE_MV(001f0000, 00000000);
336 INSTANTIATE_TEMPLATE_MV(001f0000, 00010000);
337 INSTANTIATE_TEMPLATE_MV(001f0000, 00100000);
338 INSTANTIATE_TEMPLATE_MV(001f0000, 001f0000);
339 INSTANTIATE_TEMPLATE_MV(001f3000, 00000000);
340 INSTANTIATE_TEMPLATE_MV(001f3000, 001f0000);
341 INSTANTIATE_TEMPLATE_MV(001f300f, 0000000d);
342 INSTANTIATE_TEMPLATE_MV(001f301f, 0000000d);
343 INSTANTIATE_TEMPLATE_MV(001f33e0, 000103e0);
344 INSTANTIATE_TEMPLATE_MV(001f3800, 00000000);
345 INSTANTIATE_TEMPLATE_MV(00401000, 00400000);
346 INSTANTIATE_TEMPLATE_MV(00403000, 00000000);
347 INSTANTIATE_TEMPLATE_MV(005f3000, 001f0000);
348 INSTANTIATE_TEMPLATE_MV(005f3000, 001f1000);
349 INSTANTIATE_TEMPLATE_MV(00800010, 00000000);
350 INSTANTIATE_TEMPLATE_MV(00800400, 00000000);
351 INSTANTIATE_TEMPLATE_MV(00800410, 00000000);
352 INSTANTIATE_TEMPLATE_MV(00803000, 00002000);
353 INSTANTIATE_TEMPLATE_MV(00870000, 00000000);
354 INSTANTIATE_TEMPLATE_MV(009f0000, 00010000);
355 INSTANTIATE_TEMPLATE_MV(00c00000, 00000000);
356 INSTANTIATE_TEMPLATE_MV(00c00000, 00400000);
357 INSTANTIATE_TEMPLATE_MV(00c0001f, 00000000);
358 INSTANTIATE_TEMPLATE_MV(00c001ff, 00000000);
359 INSTANTIATE_TEMPLATE_MV(00c00200, 00400000);
360 INSTANTIATE_TEMPLATE_MV(00c0020f, 00400000);
361 INSTANTIATE_TEMPLATE_MV(00c003e0, 00000000);
362 INSTANTIATE_TEMPLATE_MV(00c00800, 00000000);
363 INSTANTIATE_TEMPLATE_MV(00d80800, 00000000);
364 INSTANTIATE_TEMPLATE_MV(00df0000, 00000000);
365 INSTANTIATE_TEMPLATE_MV(00df3800, 001f0800);
366 INSTANTIATE_TEMPLATE_MV(40002000, 40000000);
367 INSTANTIATE_TEMPLATE_MV(40003c00, 00000000);
368 INSTANTIATE_TEMPLATE_MV(40040000, 00000000);
369 INSTANTIATE_TEMPLATE_MV(40800c00, 40000400);
370 INSTANTIATE_TEMPLATE_MV(40c00000, 00000000);
371 INSTANTIATE_TEMPLATE_MV(40c00000, 00400000);
372 INSTANTIATE_TEMPLATE_MV(40c00000, 40000000);
373 INSTANTIATE_TEMPLATE_MV(40c00000, 40800000);
374 INSTANTIATE_TEMPLATE_MV(40df0000, 00000000);
375 default: {
376 static bool printed_preamble = false;
377 if (!printed_preamble) {
378 printf("One or more missing template instantiations.\n");
379 printf(
380 "Add the following to either GetBitExtractFunction() "
381 "implementations\n");
382 printf("in %s near line %d:\n", __FILE__, __LINE__);
383 printed_preamble = true;
384 }
385
386 if (y == 0) {
387 printf(" INSTANTIATE_TEMPLATE_M(%08x);\n", x);
388 bit_extract_fn = &Instruction::ExtractBitsAbsent;
389 } else {
390 printf(" INSTANTIATE_TEMPLATE_MV(%08x, %08x);\n", y, x);
391 bit_extract_fn = &Instruction::IsMaskedValueAbsent;
392 }
393 }
394 }
395 return bit_extract_fn;
396 }
397
398 #undef INSTANTIATE_TEMPLATE_M
399 #undef INSTANTIATE_TEMPLATE_MV
400
TryCompileOptimisedDecodeTable(Decoder * decoder)401 bool DecodeNode::TryCompileOptimisedDecodeTable(Decoder* decoder) {
402 // EitherOr optimisation: if there are only one or two patterns in the table,
403 // try to optimise the node to exploit that.
404 size_t table_size = pattern_table_.size();
405 if ((table_size <= 2) && (GetSampledBitsCount() > 1)) {
406 // TODO: support 'x' in this optimisation by dropping the sampled bit
407 // positions before making the mask/value.
408 if (!PatternContainsSymbol(pattern_table_[0].pattern,
409 PatternSymbol::kSymbolX) &&
410 (table_size == 1)) {
411 // A pattern table consisting of a fixed pattern with no x's, and an
412 // "otherwise" or absent case. Optimise this into an instruction mask and
413 // value test.
414 uint32_t single_decode_mask = 0;
415 uint32_t single_decode_value = 0;
416 const std::vector<uint8_t>& bits = GetSampledBits();
417
418 // Construct the instruction mask and value from the pattern.
419 VIXL_ASSERT(bits.size() == GetPatternLength(pattern_table_[0].pattern));
420 for (size_t i = 0; i < bits.size(); i++) {
421 single_decode_mask |= 1U << bits[i];
422 if (GetSymbolAt(pattern_table_[0].pattern, i) ==
423 PatternSymbol::kSymbol1) {
424 single_decode_value |= 1U << bits[i];
425 }
426 }
427 BitExtractFn bit_extract_fn =
428 GetBitExtractFunction(single_decode_mask, single_decode_value);
429
430 // Create a compiled node that contains a two entry table for the
431 // either/or cases.
432 CreateCompiledNode(bit_extract_fn, 2);
433
434 // Set DecodeNode for when the instruction after masking doesn't match the
435 // value.
436 CompileNodeForBits(decoder, "unallocated", 0);
437
438 // Set DecodeNode for when it does match.
439 CompileNodeForBits(decoder, pattern_table_[0].handler, 1);
440
441 return true;
442 }
443 }
444 return false;
445 }
446
Compile(Decoder * decoder)447 CompiledDecodeNode* DecodeNode::Compile(Decoder* decoder) {
448 if (IsLeafNode()) {
449 // A leaf node is a simple wrapper around a visitor function, with no
450 // instruction decoding to do.
451 CreateVisitorNode();
452 } else if (!TryCompileOptimisedDecodeTable(decoder)) {
453 // The "otherwise" node is the default next node if no pattern matches.
454 std::string otherwise = "unallocated";
455
456 // For each pattern in pattern_table_, create an entry in matches that
457 // has a corresponding mask and value for the pattern.
458 std::vector<MaskValuePair> matches;
459 for (size_t i = 0; i < pattern_table_.size(); i++) {
460 matches.push_back(GenerateMaskValuePair(
461 GenerateOrderedPattern(pattern_table_[i].pattern)));
462 }
463
464 BitExtractFn bit_extract_fn =
465 GetBitExtractFunction(GenerateSampledBitsMask());
466
467 // Create a compiled node that contains a table with an entry for every bit
468 // pattern.
469 CreateCompiledNode(bit_extract_fn, 1U << GetSampledBitsCount());
470 VIXL_ASSERT(compiled_node_ != NULL);
471
472 // When we find a pattern matches the representation, set the node's decode
473 // function for that representation to the corresponding function.
474 for (uint32_t bits = 0; bits < (1U << GetSampledBitsCount()); bits++) {
475 for (size_t i = 0; i < matches.size(); i++) {
476 if ((bits & matches[i].first) == matches[i].second) {
477 // Only one instruction class should match for each value of bits, so
478 // if we get here, the node pointed to should still be unallocated.
479 VIXL_ASSERT(compiled_node_->GetNodeForBits(bits) == NULL);
480 CompileNodeForBits(decoder, pattern_table_[i].handler, bits);
481 break;
482 }
483 }
484
485 // If the decode_table_ entry for these bits is still NULL, the
486 // instruction must be handled by the "otherwise" case, which by default
487 // is the Unallocated visitor.
488 if (compiled_node_->GetNodeForBits(bits) == NULL) {
489 CompileNodeForBits(decoder, otherwise, bits);
490 }
491 }
492 }
493
494 VIXL_ASSERT(compiled_node_ != NULL);
495 return compiled_node_;
496 }
497
Decode(const Instruction * instr) const498 void CompiledDecodeNode::Decode(const Instruction* instr) const {
499 if (IsLeafNode()) {
500 // If this node is a leaf, call the registered visitor function.
501 VIXL_ASSERT(decoder_ != NULL);
502 decoder_->VisitNamedInstruction(instr, instruction_name_);
503 } else {
504 // Otherwise, using the sampled bit extractor for this node, look up the
505 // next node in the decode tree, and call its Decode method.
506 VIXL_ASSERT(bit_extract_fn_ != NULL);
507 VIXL_ASSERT((instr->*bit_extract_fn_)() < decode_table_size_);
508 VIXL_ASSERT(decode_table_[(instr->*bit_extract_fn_)()] != NULL);
509 decode_table_[(instr->*bit_extract_fn_)()]->Decode(instr);
510 }
511 }
512
GenerateMaskValuePair(uint32_t pattern) const513 DecodeNode::MaskValuePair DecodeNode::GenerateMaskValuePair(
514 uint32_t pattern) const {
515 uint32_t mask = 0, value = 0;
516 for (size_t i = 0; i < GetPatternLength(pattern); i++) {
517 PatternSymbol sym = GetSymbolAt(pattern, i);
518 mask = (mask << 1) | ((sym == PatternSymbol::kSymbolX) ? 0 : 1);
519 value = (value << 1) | (static_cast<uint32_t>(sym) & 1);
520 }
521 return std::make_pair(mask, value);
522 }
523
GenerateOrderedPattern(uint32_t pattern) const524 uint32_t DecodeNode::GenerateOrderedPattern(uint32_t pattern) const {
525 const std::vector<uint8_t>& sampled_bits = GetSampledBits();
526 uint64_t temp = 0xffffffffffffffff;
527
528 // Place symbols into the field of set bits. Symbols are two bits wide and
529 // take values 0, 1 or 2, so 3 will represent "no symbol".
530 for (size_t i = 0; i < sampled_bits.size(); i++) {
531 int shift = sampled_bits[i] * 2;
532 temp ^= static_cast<uint64_t>(kEndOfPattern) << shift;
533 temp |= static_cast<uint64_t>(GetSymbolAt(pattern, i)) << shift;
534 }
535
536 // Iterate over temp and extract new pattern ordered by sample position.
537 uint32_t result = kEndOfPattern; // End of pattern marker.
538
539 // Iterate over the pattern one symbol (two bits) at a time.
540 for (int i = 62; i >= 0; i -= 2) {
541 uint32_t sym = (temp >> i) & kPatternSymbolMask;
542
543 // If this is a valid symbol, shift into the result.
544 if (sym != kEndOfPattern) {
545 result = (result << 2) | sym;
546 }
547 }
548
549 // The length of the ordered pattern must be the same as the input pattern,
550 // and the number of sampled bits.
551 VIXL_ASSERT(GetPatternLength(result) == GetPatternLength(pattern));
552 VIXL_ASSERT(GetPatternLength(result) == sampled_bits.size());
553
554 return result;
555 }
556
GenerateSampledBitsMask() const557 uint32_t DecodeNode::GenerateSampledBitsMask() const {
558 uint32_t mask = 0;
559 for (int bit : GetSampledBits()) {
560 mask |= 1 << bit;
561 }
562 return mask;
563 }
564
565 } // namespace aarch64
566 } // namespace vixl
567