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 #ifndef VIXL_AARCH64_DECODER_AARCH64_H_ 28 #define VIXL_AARCH64_DECODER_AARCH64_H_ 29 30 #include <list> 31 #include <map> 32 #include <string> 33 34 #include "../globals-vixl.h" 35 36 #include "instructions-aarch64.h" 37 38 // List macro containing all visitors needed by the decoder class. 39 #define VISITOR_LIST_THAT_RETURN(V) \ 40 V(AddSubExtended) \ 41 V(AddSubImmediate) \ 42 V(AddSubShifted) \ 43 V(AddSubWithCarry) \ 44 V(AtomicMemory) \ 45 V(Bitfield) \ 46 V(CompareBranch) \ 47 V(ConditionalBranch) \ 48 V(ConditionalCompareImmediate) \ 49 V(ConditionalCompareRegister) \ 50 V(ConditionalSelect) \ 51 V(Crypto2RegSHA) \ 52 V(Crypto3RegSHA) \ 53 V(CryptoAES) \ 54 V(DataProcessing1Source) \ 55 V(DataProcessing2Source) \ 56 V(DataProcessing3Source) \ 57 V(EvaluateIntoFlags) \ 58 V(Exception) \ 59 V(Extract) \ 60 V(FPCompare) \ 61 V(FPConditionalCompare) \ 62 V(FPConditionalSelect) \ 63 V(FPDataProcessing1Source) \ 64 V(FPDataProcessing2Source) \ 65 V(FPDataProcessing3Source) \ 66 V(FPFixedPointConvert) \ 67 V(FPImmediate) \ 68 V(FPIntegerConvert) \ 69 V(LoadLiteral) \ 70 V(LoadStoreExclusive) \ 71 V(LoadStorePAC) \ 72 V(LoadStorePairNonTemporal) \ 73 V(LoadStorePairOffset) \ 74 V(LoadStorePairPostIndex) \ 75 V(LoadStorePairPreIndex) \ 76 V(LoadStorePostIndex) \ 77 V(LoadStorePreIndex) \ 78 V(LoadStoreRCpcUnscaledOffset) \ 79 V(LoadStoreRegisterOffset) \ 80 V(LoadStoreUnscaledOffset) \ 81 V(LoadStoreUnsignedOffset) \ 82 V(LogicalImmediate) \ 83 V(LogicalShifted) \ 84 V(MoveWideImmediate) \ 85 V(NEON2RegMisc) \ 86 V(NEON2RegMiscFP16) \ 87 V(NEON3Different) \ 88 V(NEON3Same) \ 89 V(NEON3SameExtra) \ 90 V(NEON3SameFP16) \ 91 V(NEONAcrossLanes) \ 92 V(NEONByIndexedElement) \ 93 V(NEONCopy) \ 94 V(NEONExtract) \ 95 V(NEONLoadStoreMultiStruct) \ 96 V(NEONLoadStoreMultiStructPostIndex) \ 97 V(NEONLoadStoreSingleStruct) \ 98 V(NEONLoadStoreSingleStructPostIndex) \ 99 V(NEONModifiedImmediate) \ 100 V(NEONPerm) \ 101 V(NEONScalar2RegMisc) \ 102 V(NEONScalar2RegMiscFP16) \ 103 V(NEONScalar3Diff) \ 104 V(NEONScalar3Same) \ 105 V(NEONScalar3SameExtra) \ 106 V(NEONScalar3SameFP16) \ 107 V(NEONScalarByIndexedElement) \ 108 V(NEONScalarCopy) \ 109 V(NEONScalarPairwise) \ 110 V(NEONScalarShiftImmediate) \ 111 V(NEONShiftImmediate) \ 112 V(NEONTable) \ 113 V(PCRelAddressing) \ 114 V(RotateRightIntoFlags) \ 115 V(SVE32BitGatherLoad_ScalarPlus32BitUnscaledOffsets) \ 116 V(SVE32BitGatherLoad_VectorPlusImm) \ 117 V(SVE32BitGatherLoadHalfwords_ScalarPlus32BitScaledOffsets) \ 118 V(SVE32BitGatherLoadWords_ScalarPlus32BitScaledOffsets) \ 119 V(SVE32BitGatherPrefetch_ScalarPlus32BitScaledOffsets) \ 120 V(SVE32BitGatherPrefetch_VectorPlusImm) \ 121 V(SVE32BitScatterStore_ScalarPlus32BitScaledOffsets) \ 122 V(SVE32BitScatterStore_ScalarPlus32BitUnscaledOffsets) \ 123 V(SVE32BitScatterStore_VectorPlusImm) \ 124 V(SVE64BitGatherLoad_ScalarPlus32BitUnpackedScaledOffsets) \ 125 V(SVE64BitGatherLoad_ScalarPlus64BitScaledOffsets) \ 126 V(SVE64BitGatherLoad_ScalarPlus64BitUnscaledOffsets) \ 127 V(SVE64BitGatherLoad_ScalarPlusUnpacked32BitUnscaledOffsets) \ 128 V(SVE64BitGatherLoad_VectorPlusImm) \ 129 V(SVE64BitGatherPrefetch_ScalarPlus64BitScaledOffsets) \ 130 V(SVE64BitGatherPrefetch_ScalarPlusUnpacked32BitScaledOffsets) \ 131 V(SVE64BitGatherPrefetch_VectorPlusImm) \ 132 V(SVE64BitScatterStore_ScalarPlus64BitScaledOffsets) \ 133 V(SVE64BitScatterStore_ScalarPlus64BitUnscaledOffsets) \ 134 V(SVE64BitScatterStore_ScalarPlusUnpacked32BitScaledOffsets) \ 135 V(SVE64BitScatterStore_ScalarPlusUnpacked32BitUnscaledOffsets) \ 136 V(SVE64BitScatterStore_VectorPlusImm) \ 137 V(SVEAddressGeneration) \ 138 V(SVEBitwiseLogicalUnpredicated) \ 139 V(SVEBitwiseShiftUnpredicated) \ 140 V(SVEFFRInitialise) \ 141 V(SVEFFRWriteFromPredicate) \ 142 V(SVEFPAccumulatingReduction) \ 143 V(SVEFPArithmeticUnpredicated) \ 144 V(SVEFPCompareVectors) \ 145 V(SVEFPCompareWithZero) \ 146 V(SVEFPComplexAddition) \ 147 V(SVEFPComplexMulAdd) \ 148 V(SVEFPComplexMulAddIndex) \ 149 V(SVEFPFastReduction) \ 150 V(SVEFPMulIndex) \ 151 V(SVEFPMulAdd) \ 152 V(SVEFPMulAddIndex) \ 153 V(SVEFPUnaryOpUnpredicated) \ 154 V(SVEIncDecByPredicateCount) \ 155 V(SVEIndexGeneration) \ 156 V(SVEIntArithmeticUnpredicated) \ 157 V(SVEIntCompareSignedImm) \ 158 V(SVEIntCompareUnsignedImm) \ 159 V(SVEIntCompareVectors) \ 160 V(SVEIntMulAddPredicated) \ 161 V(SVEIntMulAddUnpredicated) \ 162 V(SVEIntReduction) \ 163 V(SVEIntUnaryArithmeticPredicated) \ 164 V(SVEMovprfx) \ 165 V(SVEMulIndex) \ 166 V(SVEPermuteVectorExtract) \ 167 V(SVEPermuteVectorInterleaving) \ 168 V(SVEPredicateCount) \ 169 V(SVEPredicateLogical) \ 170 V(SVEPropagateBreak) \ 171 V(SVEStackFrameAdjustment) \ 172 V(SVEStackFrameSize) \ 173 V(SVEVectorSelect) \ 174 V(SVEBitwiseLogical_Predicated) \ 175 V(SVEBitwiseLogicalWithImm_Unpredicated) \ 176 V(SVEBitwiseShiftByImm_Predicated) \ 177 V(SVEBitwiseShiftByVector_Predicated) \ 178 V(SVEBitwiseShiftByWideElements_Predicated) \ 179 V(SVEBroadcastBitmaskImm) \ 180 V(SVEBroadcastFPImm_Unpredicated) \ 181 V(SVEBroadcastGeneralRegister) \ 182 V(SVEBroadcastIndexElement) \ 183 V(SVEBroadcastIntImm_Unpredicated) \ 184 V(SVECompressActiveElements) \ 185 V(SVEConditionallyBroadcastElementToVector) \ 186 V(SVEConditionallyExtractElementToSIMDFPScalar) \ 187 V(SVEConditionallyExtractElementToGeneralRegister) \ 188 V(SVEConditionallyTerminateScalars) \ 189 V(SVEConstructivePrefix_Unpredicated) \ 190 V(SVEContiguousFirstFaultLoad_ScalarPlusScalar) \ 191 V(SVEContiguousLoad_ScalarPlusImm) \ 192 V(SVEContiguousLoad_ScalarPlusScalar) \ 193 V(SVEContiguousNonFaultLoad_ScalarPlusImm) \ 194 V(SVEContiguousNonTemporalLoad_ScalarPlusImm) \ 195 V(SVEContiguousNonTemporalLoad_ScalarPlusScalar) \ 196 V(SVEContiguousNonTemporalStore_ScalarPlusImm) \ 197 V(SVEContiguousNonTemporalStore_ScalarPlusScalar) \ 198 V(SVEContiguousPrefetch_ScalarPlusImm) \ 199 V(SVEContiguousPrefetch_ScalarPlusScalar) \ 200 V(SVEContiguousStore_ScalarPlusImm) \ 201 V(SVEContiguousStore_ScalarPlusScalar) \ 202 V(SVECopySIMDFPScalarRegisterToVector_Predicated) \ 203 V(SVECopyFPImm_Predicated) \ 204 V(SVECopyGeneralRegisterToVector_Predicated) \ 205 V(SVECopyIntImm_Predicated) \ 206 V(SVEElementCount) \ 207 V(SVEExtractElementToSIMDFPScalarRegister) \ 208 V(SVEExtractElementToGeneralRegister) \ 209 V(SVEFPArithmetic_Predicated) \ 210 V(SVEFPArithmeticWithImm_Predicated) \ 211 V(SVEFPConvertPrecision) \ 212 V(SVEFPConvertToInt) \ 213 V(SVEFPExponentialAccelerator) \ 214 V(SVEFPRoundToIntegralValue) \ 215 V(SVEFPTrigMulAddCoefficient) \ 216 V(SVEFPTrigSelectCoefficient) \ 217 V(SVEFPUnaryOp) \ 218 V(SVEIncDecRegisterByElementCount) \ 219 V(SVEIncDecVectorByElementCount) \ 220 V(SVEInsertSIMDFPScalarRegister) \ 221 V(SVEInsertGeneralRegister) \ 222 V(SVEIntAddSubtractImm_Unpredicated) \ 223 V(SVEIntAddSubtractVectors_Predicated) \ 224 V(SVEIntCompareScalarCountAndLimit) \ 225 V(SVEIntConvertToFP) \ 226 V(SVEIntDivideVectors_Predicated) \ 227 V(SVEIntMinMaxImm_Unpredicated) \ 228 V(SVEIntMinMaxDifference_Predicated) \ 229 V(SVEIntMulImm_Unpredicated) \ 230 V(SVEIntMulVectors_Predicated) \ 231 V(SVELoadAndBroadcastElement) \ 232 V(SVELoadAndBroadcastQOWord_ScalarPlusImm) \ 233 V(SVELoadAndBroadcastQOWord_ScalarPlusScalar) \ 234 V(SVELoadMultipleStructures_ScalarPlusImm) \ 235 V(SVELoadMultipleStructures_ScalarPlusScalar) \ 236 V(SVELoadPredicateRegister) \ 237 V(SVELoadVectorRegister) \ 238 V(SVEPartitionBreakCondition) \ 239 V(SVEPermutePredicateElements) \ 240 V(SVEPredicateFirstActive) \ 241 V(SVEPredicateInitialize) \ 242 V(SVEPredicateNextActive) \ 243 V(SVEPredicateReadFromFFR_Predicated) \ 244 V(SVEPredicateReadFromFFR_Unpredicated) \ 245 V(SVEPredicateTest) \ 246 V(SVEPredicateZero) \ 247 V(SVEPropagateBreakToNextPartition) \ 248 V(SVEReversePredicateElements) \ 249 V(SVEReverseVectorElements) \ 250 V(SVEReverseWithinElements) \ 251 V(SVESaturatingIncDecRegisterByElementCount) \ 252 V(SVESaturatingIncDecVectorByElementCount) \ 253 V(SVEStoreMultipleStructures_ScalarPlusImm) \ 254 V(SVEStoreMultipleStructures_ScalarPlusScalar) \ 255 V(SVEStorePredicateRegister) \ 256 V(SVEStoreVectorRegister) \ 257 V(SVETableLookup) \ 258 V(SVEUnpackPredicateElements) \ 259 V(SVEUnpackVectorElements) \ 260 V(SVEVectorSplice) \ 261 V(System) \ 262 V(TestBranch) \ 263 V(Unallocated) \ 264 V(UnconditionalBranch) \ 265 V(UnconditionalBranchToRegister) \ 266 V(Unimplemented) 267 268 #define VISITOR_LIST_THAT_DONT_RETURN(V) V(Reserved) 269 270 #define VISITOR_LIST(V) \ 271 VISITOR_LIST_THAT_RETURN(V) \ 272 VISITOR_LIST_THAT_DONT_RETURN(V) 273 274 namespace vixl { 275 namespace aarch64 { 276 277 using Metadata = std::map<std::string, std::string>; 278 279 // The Visitor interface consists only of the Visit() method. User classes 280 // that inherit from this one must provide an implementation of the method. 281 // Information about the instruction encountered by the Decoder is available 282 // via the metadata pointer. 283 class DecoderVisitor { 284 public: 285 enum VisitorConstness { kConstVisitor, kNonConstVisitor }; 286 explicit DecoderVisitor(VisitorConstness constness = kConstVisitor) constness_(constness)287 : constness_(constness) {} 288 ~DecoderVisitor()289 virtual ~DecoderVisitor() {} 290 291 virtual void Visit(Metadata* metadata, const Instruction* instr) = 0; 292 IsConstVisitor()293 bool IsConstVisitor() const { return constness_ == kConstVisitor; } MutableInstruction(const Instruction * instr)294 Instruction* MutableInstruction(const Instruction* instr) { 295 VIXL_ASSERT(!IsConstVisitor()); 296 return const_cast<Instruction*>(instr); 297 } 298 299 private: 300 const VisitorConstness constness_; 301 }; 302 303 class DecodeNode; 304 class CompiledDecodeNode; 305 306 // The instruction decoder is constructed from a graph of decode nodes. At each 307 // node, a number of bits are sampled from the instruction being decoded. The 308 // resulting value is used to look up the next node in the graph, which then 309 // samples other bits, and moves to other decode nodes. Eventually, a visitor 310 // node is reached, and the corresponding visitor function is called, which 311 // handles the instruction. 312 class Decoder { 313 public: Decoder()314 Decoder() { ConstructDecodeGraph(); } 315 316 // Top-level wrappers around the actual decoding function. 317 void Decode(const Instruction* instr); 318 void Decode(Instruction* instr); 319 320 // Decode all instructions from start (inclusive) to end (exclusive). 321 template <typename T> Decode(T start,T end)322 void Decode(T start, T end) { 323 for (T instr = start; instr < end; instr = instr->GetNextInstruction()) { 324 Decode(instr); 325 } 326 } 327 328 // Register a new visitor class with the decoder. 329 // Decode() will call the corresponding visitor method from all registered 330 // visitor classes when decoding reaches the leaf node of the instruction 331 // decode tree. 332 // Visitors are called in order. 333 // A visitor can be registered multiple times. 334 // 335 // d.AppendVisitor(V1); 336 // d.AppendVisitor(V2); 337 // d.PrependVisitor(V2); 338 // d.AppendVisitor(V3); 339 // 340 // d.Decode(i); 341 // 342 // will call in order visitor methods in V2, V1, V2, V3. 343 void AppendVisitor(DecoderVisitor* visitor); 344 void PrependVisitor(DecoderVisitor* visitor); 345 // These helpers register `new_visitor` before or after the first instance of 346 // `registered_visiter` in the list. 347 // So if 348 // V1, V2, V1, V2 349 // are registered in this order in the decoder, calls to 350 // d.InsertVisitorAfter(V3, V1); 351 // d.InsertVisitorBefore(V4, V2); 352 // will yield the order 353 // V1, V3, V4, V2, V1, V2 354 // 355 // For more complex modifications of the order of registered visitors, one can 356 // directly access and modify the list of visitors via the `visitors()' 357 // accessor. 358 void InsertVisitorBefore(DecoderVisitor* new_visitor, 359 DecoderVisitor* registered_visitor); 360 void InsertVisitorAfter(DecoderVisitor* new_visitor, 361 DecoderVisitor* registered_visitor); 362 363 // Remove all instances of a previously registered visitor class from the list 364 // of visitors stored by the decoder. 365 void RemoveVisitor(DecoderVisitor* visitor); 366 367 void VisitNamedInstruction(const Instruction* instr, const std::string& name); 368 visitors()369 std::list<DecoderVisitor*>* visitors() { return &visitors_; } 370 371 // Get a DecodeNode by name from the Decoder's map. 372 DecodeNode* GetDecodeNode(std::string name); 373 374 private: 375 // Decodes an instruction and calls the visitor functions registered with the 376 // Decoder class. 377 void DecodeInstruction(const Instruction* instr); 378 379 // Add an initialised DecodeNode to the decode_node_ map. 380 void AddDecodeNode(const DecodeNode& node); 381 382 // Visitors are registered in a list. 383 std::list<DecoderVisitor*> visitors_; 384 385 // Compile the dynamically generated decode graph based on the static 386 // information in kDecodeMapping and kVisitorNodes. 387 void ConstructDecodeGraph(); 388 389 // Root node for the compiled decoder graph, stored here to avoid a map lookup 390 // for every instruction decoded. 391 CompiledDecodeNode* compiled_decoder_root_; 392 393 // Map of node names to DecodeNodes. 394 std::map<std::string, DecodeNode> decode_nodes_; 395 }; 396 397 typedef void (Decoder::*DecodeFnPtr)(const Instruction*); 398 typedef uint32_t (Instruction::*BitExtractFn)(void) const; 399 400 // A Visitor node maps the name of a visitor to the function that handles it. 401 struct VisitorNode { 402 const char* name; 403 const DecodeFnPtr visitor_fn; 404 }; 405 406 // DecodePattern and DecodeMapping represent the input data to the decoder 407 // compilation stage. After compilation, the decoder is embodied in the graph 408 // of CompiledDecodeNodes pointer to by compiled_decoder_root_. 409 410 // A DecodePattern maps a pattern of set/unset/don't care (1, 0, x) bits encoded 411 // as uint32_t to its handler. 412 // The encoding uses two bits per symbol: 0 => 0b00, 1 => 0b01, x => 0b10. 413 // 0b11 marks the edge of the most-significant bits of the pattern, which is 414 // required to determine the length. For example, the pattern "1x01"_b is 415 // encoded in a uint32_t as 0b11_01_10_00_01. 416 struct DecodePattern { 417 uint32_t pattern; 418 const char* handler; 419 }; 420 421 // A DecodeMapping consists of the name of a handler, the bits sampled in the 422 // instruction by that handler, and a mapping from the pattern that those 423 // sampled bits match to the corresponding name of a node. 424 struct DecodeMapping { 425 const char* name; 426 const std::vector<uint8_t> sampled_bits; 427 const std::vector<DecodePattern> mapping; 428 }; 429 430 // For speed, before nodes can be used for decoding instructions, they must 431 // be compiled. This converts the mapping "bit pattern strings to decoder name 432 // string" stored in DecodeNodes to an array look up for the pointer to the next 433 // node, stored in CompiledDecodeNodes. Compilation may also apply other 434 // optimisations for simple decode patterns. 435 class CompiledDecodeNode { 436 public: 437 // Constructor for decode node, containing a decode table and pointer to a 438 // function that extracts the bits to be sampled. CompiledDecodeNode(BitExtractFn bit_extract_fn,size_t decode_table_size)439 CompiledDecodeNode(BitExtractFn bit_extract_fn, size_t decode_table_size) 440 : bit_extract_fn_(bit_extract_fn), 441 instruction_name_("node"), 442 decode_table_size_(decode_table_size), 443 decoder_(NULL) { 444 decode_table_ = new CompiledDecodeNode*[decode_table_size_]; 445 memset(decode_table_, 0, decode_table_size_ * sizeof(decode_table_[0])); 446 } 447 448 // Constructor for wrappers around visitor functions. These require no 449 // decoding, so no bit extraction function or decode table is assigned. CompiledDecodeNode(std::string iname,Decoder * decoder)450 explicit CompiledDecodeNode(std::string iname, Decoder* decoder) 451 : bit_extract_fn_(NULL), 452 instruction_name_(iname), 453 decode_table_(NULL), 454 decode_table_size_(0), 455 decoder_(decoder) {} 456 ~CompiledDecodeNode()457 ~CompiledDecodeNode() VIXL_NEGATIVE_TESTING_ALLOW_EXCEPTION { 458 // Free the decode table, if this is a compiled, non-leaf node. 459 if (decode_table_ != NULL) { 460 VIXL_ASSERT(!IsLeafNode()); 461 delete[] decode_table_; 462 } 463 } 464 465 // Decode the instruction by either sampling the bits using the bit extract 466 // function to find the next node, or, if we're at a leaf, calling the visitor 467 // function. 468 void Decode(const Instruction* instr) const; 469 470 // A leaf node is a wrapper for a visitor function. IsLeafNode()471 bool IsLeafNode() const { 472 VIXL_ASSERT(((instruction_name_ == "node") && (bit_extract_fn_ != NULL)) || 473 ((instruction_name_ != "node") && (bit_extract_fn_ == NULL))); 474 return instruction_name_ != "node"; 475 } 476 477 // Get a pointer to the next node required in the decode process, based on the 478 // bits sampled by the current node. GetNodeForBits(uint32_t bits)479 CompiledDecodeNode* GetNodeForBits(uint32_t bits) const { 480 VIXL_ASSERT(bits < decode_table_size_); 481 return decode_table_[bits]; 482 } 483 484 // Set the next node in the decode process for the pattern of sampled bits in 485 // the current node. SetNodeForBits(uint32_t bits,CompiledDecodeNode * n)486 void SetNodeForBits(uint32_t bits, CompiledDecodeNode* n) { 487 VIXL_ASSERT(bits < decode_table_size_); 488 VIXL_ASSERT(n != NULL); 489 decode_table_[bits] = n; 490 } 491 492 private: 493 // Pointer to an instantiated template function for extracting the bits 494 // sampled by this node. Set to NULL for leaf nodes. 495 const BitExtractFn bit_extract_fn_; 496 497 // Visitor function that handles the instruction identified. Set only for 498 // leaf nodes, where no extra decoding is required, otherwise NULL. 499 std::string instruction_name_; 500 501 // Mapping table from instruction bits to next decode stage. 502 CompiledDecodeNode** decode_table_; 503 const size_t decode_table_size_; 504 505 // Pointer to the decoder containing this node, used to call its visitor 506 // function for leaf nodes. Set to NULL for non-leaf nodes. 507 Decoder* decoder_; 508 }; 509 510 class DecodeNode { 511 public: 512 // Default constructor needed for map initialisation. DecodeNode()513 DecodeNode() 514 : sampled_bits_(DecodeNode::kEmptySampledBits), 515 pattern_table_(DecodeNode::kEmptyPatternTable), 516 compiled_node_(NULL) {} 517 518 // Constructor for DecodeNode wrappers around visitor functions. These are 519 // marked as "compiled", as there is no decoding left to do. DecodeNode(const std::string & iname,Decoder * decoder)520 explicit DecodeNode(const std::string& iname, Decoder* decoder) 521 : name_(iname), 522 sampled_bits_(DecodeNode::kEmptySampledBits), 523 instruction_name_(iname), 524 pattern_table_(DecodeNode::kEmptyPatternTable), 525 decoder_(decoder), 526 compiled_node_(NULL) {} 527 528 // Constructor for DecodeNodes that map bit patterns to other DecodeNodes. 529 explicit DecodeNode(const DecodeMapping& map, Decoder* decoder = NULL) 530 : name_(map.name), 531 sampled_bits_(map.sampled_bits), 532 instruction_name_("node"), 533 pattern_table_(map.mapping), 534 decoder_(decoder), 535 compiled_node_(NULL) { 536 // With the current two bits per symbol encoding scheme, the maximum pattern 537 // length is (32 - 2) / 2 = 15 bits. 538 VIXL_CHECK(GetPatternLength(map.mapping[0].pattern) <= 15); 539 for (const DecodePattern& p : map.mapping) { 540 VIXL_CHECK(GetPatternLength(p.pattern) == map.sampled_bits.size()); 541 } 542 } 543 ~DecodeNode()544 ~DecodeNode() { 545 // Delete the compiled version of this node, if one was created. 546 if (compiled_node_ != NULL) { 547 delete compiled_node_; 548 } 549 } 550 551 // Get the bits sampled from the instruction by this node. GetSampledBits()552 const std::vector<uint8_t>& GetSampledBits() const { return sampled_bits_; } 553 554 // Get the number of bits sampled from the instruction by this node. GetSampledBitsCount()555 size_t GetSampledBitsCount() const { return sampled_bits_.size(); } 556 557 // A leaf node is a DecodeNode that wraps the visitor function for the 558 // identified instruction class. IsLeafNode()559 bool IsLeafNode() const { return instruction_name_ != "node"; } 560 GetName()561 std::string GetName() const { return name_; } 562 563 // Create a CompiledDecodeNode of specified table size that uses 564 // bit_extract_fn to sample bits from the instruction. CreateCompiledNode(BitExtractFn bit_extract_fn,size_t table_size)565 void CreateCompiledNode(BitExtractFn bit_extract_fn, size_t table_size) { 566 VIXL_ASSERT(bit_extract_fn != NULL); 567 VIXL_ASSERT(table_size > 0); 568 compiled_node_ = new CompiledDecodeNode(bit_extract_fn, table_size); 569 } 570 571 // Create a CompiledDecodeNode wrapping a visitor function. No decoding is 572 // required for this node; the visitor function is called instead. CreateVisitorNode()573 void CreateVisitorNode() { 574 compiled_node_ = new CompiledDecodeNode(instruction_name_, decoder_); 575 } 576 577 // Find and compile the DecodeNode named "name", and set it as the node for 578 // the pattern "bits". 579 void CompileNodeForBits(Decoder* decoder, std::string name, uint32_t bits); 580 581 // Get a pointer to an instruction method that extracts the instruction bits 582 // specified by the mask argument, and returns those sampled bits as a 583 // contiguous sequence, suitable for indexing an array. 584 // For example, a mask of 0b1010 returns a function that, given an instruction 585 // 0bXYZW, will return 0bXZ. GetBitExtractFunction(uint32_t mask)586 BitExtractFn GetBitExtractFunction(uint32_t mask) { 587 return GetBitExtractFunctionHelper(mask, 0); 588 } 589 590 // Get a pointer to an Instruction method that applies a mask to the 591 // instruction bits, and tests if the result is equal to value. The returned 592 // function gives a 1 result if (inst & mask == value), 0 otherwise. GetBitExtractFunction(uint32_t mask,uint32_t value)593 BitExtractFn GetBitExtractFunction(uint32_t mask, uint32_t value) { 594 return GetBitExtractFunctionHelper(value, mask); 595 } 596 597 // Compile this DecodeNode into a new CompiledDecodeNode and returns a pointer 598 // to it. This pointer is also stored inside the DecodeNode itself. Destroying 599 // a DecodeNode frees its associated CompiledDecodeNode. 600 CompiledDecodeNode* Compile(Decoder* decoder); 601 602 // Get a pointer to the CompiledDecodeNode associated with this DecodeNode. 603 // Returns NULL if the node has not been compiled yet. GetCompiledNode()604 CompiledDecodeNode* GetCompiledNode() const { return compiled_node_; } IsCompiled()605 bool IsCompiled() const { return GetCompiledNode() != NULL; } 606 607 enum class PatternSymbol { kSymbol0 = 0, kSymbol1 = 1, kSymbolX = 2 }; 608 static const uint32_t kEndOfPattern = 3; 609 static const uint32_t kPatternSymbolMask = 3; 610 GetPatternLength(uint32_t pattern)611 size_t GetPatternLength(uint32_t pattern) const { 612 uint32_t hsb = HighestSetBitPosition(pattern); 613 // The pattern length is signified by two set bits in a two bit-aligned 614 // position. Ensure that the pattern has a highest set bit, it's at an odd 615 // bit position, and that the bit to the right of the hsb is also set. 616 VIXL_ASSERT(((hsb % 2) == 1) && (pattern >> (hsb - 1)) == kEndOfPattern); 617 return hsb / 2; 618 } 619 PatternContainsSymbol(uint32_t pattern,PatternSymbol symbol)620 bool PatternContainsSymbol(uint32_t pattern, PatternSymbol symbol) const { 621 while ((pattern & kPatternSymbolMask) != kEndOfPattern) { 622 if (static_cast<PatternSymbol>(pattern & kPatternSymbolMask) == symbol) 623 return true; 624 pattern >>= 2; 625 } 626 return false; 627 } 628 GetSymbolAt(uint32_t pattern,size_t pos)629 PatternSymbol GetSymbolAt(uint32_t pattern, size_t pos) const { 630 size_t len = GetPatternLength(pattern); 631 VIXL_ASSERT((pos < 15) && (pos < len)); 632 uint32_t shift = static_cast<uint32_t>(2 * (len - pos - 1)); 633 uint32_t sym = (pattern >> shift) & kPatternSymbolMask; 634 return static_cast<PatternSymbol>(sym); 635 } 636 637 private: 638 // Generate a mask and value pair from a pattern constructed from 0, 1 and x 639 // (don't care) 2-bit symbols. 640 // For example "10x1"_b should return mask = 0b1101, value = 0b1001. 641 typedef std::pair<Instr, Instr> MaskValuePair; 642 MaskValuePair GenerateMaskValuePair(uint32_t pattern) const; 643 644 // Generate a pattern ordered by the bit positions sampled by this node. 645 // The symbol corresponding to the lowest sample position is placed in the 646 // least-significant bits of the result pattern. 647 // For example, a pattern of "1x0"_b expected when sampling bits 31, 1 and 30 648 // returns the pattern "x01"_b; bit 1 should be 'x', bit 30 '0' and bit 31 649 // '1'. 650 // This output makes comparisons easier between the pattern and bits sampled 651 // from an instruction using the fast "compress" algorithm. See 652 // Instruction::Compress(). 653 uint32_t GenerateOrderedPattern(uint32_t pattern) const; 654 655 // Generate a mask with a bit set at each sample position. 656 uint32_t GenerateSampledBitsMask() const; 657 658 // Try to compile a more optimised decode operation for this node, returning 659 // true if successful. 660 bool TryCompileOptimisedDecodeTable(Decoder* decoder); 661 662 // Helper function that returns a bit extracting function. If y is zero, 663 // x is a bit extraction mask. Otherwise, y is the mask, and x is the value 664 // to match after masking. 665 BitExtractFn GetBitExtractFunctionHelper(uint32_t x, uint32_t y); 666 667 // Name of this decoder node, used to construct edges in the decode graph. 668 std::string name_; 669 670 // Vector of bits sampled from an instruction to determine which node to look 671 // up next in the decode process. 672 const std::vector<uint8_t>& sampled_bits_; 673 static const std::vector<uint8_t> kEmptySampledBits; 674 675 // For leaf nodes, this is the name of the instruction form that the node 676 // represents. For other nodes, this is always set to "node". 677 std::string instruction_name_; 678 679 // Source mapping from bit pattern to name of next decode stage. 680 const std::vector<DecodePattern>& pattern_table_; 681 static const std::vector<DecodePattern> kEmptyPatternTable; 682 683 // Pointer to the decoder containing this node, used to call its visitor 684 // function for leaf nodes. 685 Decoder* decoder_; 686 687 // Pointer to the compiled version of this node. Is this node hasn't been 688 // compiled yet, this pointer is NULL. 689 CompiledDecodeNode* compiled_node_; 690 }; 691 692 } // namespace aarch64 693 } // namespace vixl 694 695 #endif // VIXL_AARCH64_DECODER_AARCH64_H_ 696