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