decoder-aarch64.cc (22362B)
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 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 48 void Decoder::Decode(Instruction* instr) { 49 compiled_decoder_root_->Decode(const_cast<const Instruction*>(instr)); 50 } 51 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 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 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 90 void Decoder::AppendVisitor(DecoderVisitor* new_visitor) { 91 visitors_.push_back(new_visitor); 92 } 93 94 95 void Decoder::PrependVisitor(DecoderVisitor* new_visitor) { 96 visitors_.push_front(new_visitor); 97 } 98 99 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 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 133 void Decoder::RemoveVisitor(DecoderVisitor* visitor) { 134 visitors_.remove(visitor); 135 } 136 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 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 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 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 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 508 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 523 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 534 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 567 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