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