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