1958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Copyright 2014 the V8 project authors. All rights reserved. 2958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Use of this source code is governed by a BSD-style license that can be 3958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// found in the LICENSE file. 4958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 5958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#ifndef V8_REGISTER_ALLOCATOR_VERIFIER_H_ 6958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#define V8_REGISTER_ALLOCATOR_VERIFIER_H_ 7958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch#include "src/compiler/instruction.h" 9f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 10958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 11958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace v8 { 12958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace internal { 13958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace compiler { 14958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 1562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdochclass InstructionBlock; 16958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass InstructionSequence; 17958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 18bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// The register allocator validator traverses instructions in the instruction 19bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// sequence, and verifies the correctness of machine operand substitutions of 20bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// virtual registers. It collects the virtual register instruction signatures 21bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// before register allocation. Then, after the register allocation pipeline 22bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// completes, it compares the operand substitutions against the pre-allocation 23bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// data. 24bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// At a high level, validation works as follows: we iterate through each block, 25bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// and, in a block, through each instruction; then: 26bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// - when an operand is the output of an instruction, we associate it to the 27bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// virtual register that the instruction sequence declares as its output. We 28bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// use the concept of "FinalAssessment" to model this. 29bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// - when an operand is used in an instruction, we check that the assessment 30bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// matches the expectation of the instruction 31bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// - moves simply copy the assessment over to the new operand 32bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// - blocks with more than one predecessor associate to each operand a "Pending" 33bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// assessment. The pending assessment remembers the operand and block where it 34bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// was created. Then, when the value is used (which may be as a different 35bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// operand, because of moves), we check that the virtual register at the use 36bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// site matches the definition of this pending operand: either the phi inputs 37bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// match, or, if it's not a phi, all the predecessors at the point the pending 38bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// assessment was defined have that operand assigned to the given virtual 39bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// register. 40bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// If a block is a loop header - so one or more of its predecessors are it or 41bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// below - we still treat uses of operands as above, but we record which operand 42bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// assessments haven't been made yet, and what virtual register they must 43bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// correspond to, and verify that when we are done with the respective 44bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// predecessor blocks. 45bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// This way, the algorithm always makes a final decision about the operands 46bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// in an instruction, ensuring convergence. 47bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Operand assessments are recorded per block, as the result at the exit from 48bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// the block. When moving to a new block, we copy assessments from its single 49bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// predecessor, or, if the block has multiple predecessors, the mechanism was 50bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// described already. 51bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 52bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochenum AssessmentKind { Final, Pending }; 53bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 54bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass Assessment : public ZoneObject { 55bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 56bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AssessmentKind kind() const { return kind_; } 57bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 58bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch protected: 59bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit Assessment(AssessmentKind kind) : kind_(kind) {} 60bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch AssessmentKind kind_; 61bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 62bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 63bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_COPY_AND_ASSIGN(Assessment); 64bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 65bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 66bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// PendingAssessments are associated to operands coming from the multiple 67bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// predecessors of a block. We only record the operand and the block, and 68bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// will determine if the way the operand is defined (from the predecessors) 69bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// matches a particular use. This handles scenarios where multiple phis are 70bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// defined with identical operands, and the move optimizer moved down the moves 71bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// separating the 2 phis in the block defining them. 72bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass PendingAssessment final : public Assessment { 73bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 74bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit PendingAssessment(const InstructionBlock* origin, 75bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch InstructionOperand operand) 76bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch : Assessment(Pending), origin_(origin), operand_(operand) {} 77bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 78bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch static const PendingAssessment* cast(const Assessment* assessment) { 79bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CHECK(assessment->kind() == Pending); 80bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return static_cast<const PendingAssessment*>(assessment); 81bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 82bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 83bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const InstructionBlock* origin() const { return origin_; } 84bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch InstructionOperand operand() const { return operand_; } 85bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 86bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 87bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const InstructionBlock* const origin_; 88bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch InstructionOperand operand_; 89bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 90bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_COPY_AND_ASSIGN(PendingAssessment); 91bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 92bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 9313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// FinalAssessments are associated to operands that we know to be a certain 94bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// virtual register. 95bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass FinalAssessment final : public Assessment { 96bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 97bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit FinalAssessment(int virtual_register, 98bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const PendingAssessment* original_pending = nullptr) 99bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch : Assessment(Final), 100bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch virtual_register_(virtual_register), 101bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch original_pending_assessment_(original_pending) {} 102bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 103bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int virtual_register() const { return virtual_register_; } 104bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch static const FinalAssessment* cast(const Assessment* assessment) { 105bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CHECK(assessment->kind() == Final); 106bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return static_cast<const FinalAssessment*>(assessment); 107bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 108bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 109bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const PendingAssessment* original_pending_assessment() const { 110bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return original_pending_assessment_; 111bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 112bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 113bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 114bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int virtual_register_; 115bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const PendingAssessment* original_pending_assessment_; 116bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 117bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_COPY_AND_ASSIGN(FinalAssessment); 118bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 119bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 120bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochstruct OperandAsKeyLess { 121bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool operator()(const InstructionOperand& a, 122bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const InstructionOperand& b) const { 123bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return a.CompareCanonicalized(b); 124bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 125bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 126bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 127bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Assessments associated with a basic block. 128bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass BlockAssessments : public ZoneObject { 129bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 130bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap; 131bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit BlockAssessments(Zone* zone) 132bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch : map_(zone), map_for_moves_(zone), zone_(zone) {} 133bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void Drop(InstructionOperand operand) { map_.erase(operand); } 134bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void DropRegisters(); 135bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void AddDefinition(InstructionOperand operand, int virtual_register) { 136bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch auto existent = map_.find(operand); 137bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (existent != map_.end()) { 138bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // Drop the assignment 139bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch map_.erase(existent); 140bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 141bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch map_.insert( 142bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch std::make_pair(operand, new (zone_) FinalAssessment(virtual_register))); 143bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 144bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 145bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void PerformMoves(const Instruction* instruction); 146bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void PerformParallelMoves(const ParallelMove* moves); 147bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void CopyFrom(const BlockAssessments* other) { 148bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CHECK(map_.empty()); 149bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CHECK_NOT_NULL(other); 150bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch map_.insert(other->map_.begin(), other->map_.end()); 151bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 152bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 153bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch OperandMap& map() { return map_; } 154bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const OperandMap& map() const { return map_; } 155bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void Print() const; 156bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 157bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 158bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch OperandMap map_; 159bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch OperandMap map_for_moves_; 160bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch Zone* zone_; 161bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 162bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DISALLOW_COPY_AND_ASSIGN(BlockAssessments); 163bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch}; 164bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass RegisterAllocatorVerifier final : public ZoneObject { 166958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier RegisterAllocatorVerifier(Zone* zone, const RegisterConfiguration* config, 168958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const InstructionSequence* sequence); 169958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 170958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void VerifyAssignment(); 171958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void VerifyGapMoves(); 172958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 173958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 174958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier enum ConstraintType { 175958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kConstant, 176958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kImmediate, 177958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kRegister, 178958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kFixedRegister, 17913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch kFPRegister, 18013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch kFixedFPRegister, 181014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kSlot, 182958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kFixedSlot, 183958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier kNone, 18413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch kNoneFP, 185014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kExplicit, 186014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kSameAsFirst, 187014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kRegisterAndSlot 188958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 189958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 190958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier struct OperandConstraint { 191958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier ConstraintType type_; 192f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Constant or immediate value, register code, slot index, or slot size 193f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // when relevant. 194f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch int value_; 195014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int spilled_slot_; 196958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int virtual_register_; 197958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 198958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 199958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier struct InstructionConstraint { 200958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const Instruction* instruction_; 201958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t operand_constaints_size_; 202958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier OperandConstraint* operand_constraints_; 203958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 204958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 205958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef ZoneVector<InstructionConstraint> Constraints; 206958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 207bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch class DelayedAssessments : public ZoneObject { 208bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch public: 209bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch explicit DelayedAssessments(Zone* zone) : map_(zone) {} 210bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 211bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const { 212bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return map_; 213bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 214bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 215bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void AddDelayedAssessment(InstructionOperand op, int vreg) { 216bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch auto it = map_.find(op); 217bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (it == map_.end()) { 218bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch map_.insert(std::make_pair(op, vreg)); 219bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } else { 220bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch CHECK_EQ(it->second, vreg); 221bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 222bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 223bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 224bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch private: 225bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_; 226bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch }; 227bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 228958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* zone() const { return zone_; } 229958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const RegisterConfiguration* config() { return config_; } 230958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const InstructionSequence* sequence() const { return sequence_; } 231958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Constraints* constraints() { return &constraints_; } 232958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 233958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static void VerifyInput(const OperandConstraint& constraint); 234958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static void VerifyTemp(const OperandConstraint& constraint); 235958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static void VerifyOutput(const OperandConstraint& constraint); 236958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 237958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void BuildConstraint(const InstructionOperand* op, 238958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier OperandConstraint* constraint); 239958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void CheckConstraint(const InstructionOperand* op, 240958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const OperandConstraint* constraint); 241bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BlockAssessments* CreateForBlock(const InstructionBlock* block); 242958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 243bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op, 244bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BlockAssessments* current_assessments, 245bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const PendingAssessment* assessment, 246bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int virtual_register); 247bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void ValidateFinalAssessment(RpoNumber block_id, InstructionOperand op, 248bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BlockAssessments* current_assessments, 249bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch const FinalAssessment* assessment, 250bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch int virtual_register); 251bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments, 252bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch InstructionOperand op, int virtual_register); 253958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 254958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* const zone_; 255958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const RegisterConfiguration* config_; 256958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const InstructionSequence* const sequence_; 257958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Constraints constraints_; 258bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneMap<RpoNumber, BlockAssessments*> assessments_; 259bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_; 260958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 261958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier); 262958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 263958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 264958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 265958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 266958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 267958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 268958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#endif 269