Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1 | // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_REGISTER_ALLOCATOR_VERIFIER_H_ |
| 6 | #define V8_REGISTER_ALLOCATOR_VERIFIER_H_ |
| 7 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 8 | #include "src/zone-containers.h" |
| 9 | |
| 10 | namespace v8 { |
| 11 | namespace internal { |
| 12 | namespace compiler { |
| 13 | |
| 14 | class InstructionOperand; |
| 15 | class InstructionSequence; |
| 16 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 17 | // The register allocator validator traverses instructions in the instruction |
| 18 | // sequence, and verifies the correctness of machine operand substitutions of |
| 19 | // virtual registers. It collects the virtual register instruction signatures |
| 20 | // before register allocation. Then, after the register allocation pipeline |
| 21 | // completes, it compares the operand substitutions against the pre-allocation |
| 22 | // data. |
| 23 | // At a high level, validation works as follows: we iterate through each block, |
| 24 | // and, in a block, through each instruction; then: |
| 25 | // - when an operand is the output of an instruction, we associate it to the |
| 26 | // virtual register that the instruction sequence declares as its output. We |
| 27 | // use the concept of "FinalAssessment" to model this. |
| 28 | // - when an operand is used in an instruction, we check that the assessment |
| 29 | // matches the expectation of the instruction |
| 30 | // - moves simply copy the assessment over to the new operand |
| 31 | // - blocks with more than one predecessor associate to each operand a "Pending" |
| 32 | // assessment. The pending assessment remembers the operand and block where it |
| 33 | // was created. Then, when the value is used (which may be as a different |
| 34 | // operand, because of moves), we check that the virtual register at the use |
| 35 | // site matches the definition of this pending operand: either the phi inputs |
| 36 | // match, or, if it's not a phi, all the predecessors at the point the pending |
| 37 | // assessment was defined have that operand assigned to the given virtual |
| 38 | // register. |
| 39 | // If a block is a loop header - so one or more of its predecessors are it or |
| 40 | // below - we still treat uses of operands as above, but we record which operand |
| 41 | // assessments haven't been made yet, and what virtual register they must |
| 42 | // correspond to, and verify that when we are done with the respective |
| 43 | // predecessor blocks. |
| 44 | // This way, the algorithm always makes a final decision about the operands |
| 45 | // in an instruction, ensuring convergence. |
| 46 | // Operand assessments are recorded per block, as the result at the exit from |
| 47 | // the block. When moving to a new block, we copy assessments from its single |
| 48 | // predecessor, or, if the block has multiple predecessors, the mechanism was |
| 49 | // described already. |
| 50 | |
| 51 | enum AssessmentKind { Final, Pending }; |
| 52 | |
| 53 | class Assessment : public ZoneObject { |
| 54 | public: |
| 55 | AssessmentKind kind() const { return kind_; } |
| 56 | |
| 57 | protected: |
| 58 | explicit Assessment(AssessmentKind kind) : kind_(kind) {} |
| 59 | AssessmentKind kind_; |
| 60 | |
| 61 | private: |
| 62 | DISALLOW_COPY_AND_ASSIGN(Assessment); |
| 63 | }; |
| 64 | |
| 65 | // PendingAssessments are associated to operands coming from the multiple |
| 66 | // predecessors of a block. We only record the operand and the block, and |
| 67 | // will determine if the way the operand is defined (from the predecessors) |
| 68 | // matches a particular use. This handles scenarios where multiple phis are |
| 69 | // defined with identical operands, and the move optimizer moved down the moves |
| 70 | // separating the 2 phis in the block defining them. |
| 71 | class PendingAssessment final : public Assessment { |
| 72 | public: |
| 73 | explicit PendingAssessment(const InstructionBlock* origin, |
| 74 | InstructionOperand operand) |
| 75 | : Assessment(Pending), origin_(origin), operand_(operand) {} |
| 76 | |
| 77 | static const PendingAssessment* cast(const Assessment* assessment) { |
| 78 | CHECK(assessment->kind() == Pending); |
| 79 | return static_cast<const PendingAssessment*>(assessment); |
| 80 | } |
| 81 | |
| 82 | const InstructionBlock* origin() const { return origin_; } |
| 83 | InstructionOperand operand() const { return operand_; } |
| 84 | |
| 85 | private: |
| 86 | const InstructionBlock* const origin_; |
| 87 | InstructionOperand operand_; |
| 88 | |
| 89 | DISALLOW_COPY_AND_ASSIGN(PendingAssessment); |
| 90 | }; |
| 91 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 92 | // FinalAssessments are associated to operands that we know to be a certain |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 93 | // virtual register. |
| 94 | class FinalAssessment final : public Assessment { |
| 95 | public: |
| 96 | explicit FinalAssessment(int virtual_register, |
| 97 | const PendingAssessment* original_pending = nullptr) |
| 98 | : Assessment(Final), |
| 99 | virtual_register_(virtual_register), |
| 100 | original_pending_assessment_(original_pending) {} |
| 101 | |
| 102 | int virtual_register() const { return virtual_register_; } |
| 103 | static const FinalAssessment* cast(const Assessment* assessment) { |
| 104 | CHECK(assessment->kind() == Final); |
| 105 | return static_cast<const FinalAssessment*>(assessment); |
| 106 | } |
| 107 | |
| 108 | const PendingAssessment* original_pending_assessment() const { |
| 109 | return original_pending_assessment_; |
| 110 | } |
| 111 | |
| 112 | private: |
| 113 | int virtual_register_; |
| 114 | const PendingAssessment* original_pending_assessment_; |
| 115 | |
| 116 | DISALLOW_COPY_AND_ASSIGN(FinalAssessment); |
| 117 | }; |
| 118 | |
| 119 | struct OperandAsKeyLess { |
| 120 | bool operator()(const InstructionOperand& a, |
| 121 | const InstructionOperand& b) const { |
| 122 | return a.CompareCanonicalized(b); |
| 123 | } |
| 124 | }; |
| 125 | |
| 126 | // Assessments associated with a basic block. |
| 127 | class BlockAssessments : public ZoneObject { |
| 128 | public: |
| 129 | typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap; |
| 130 | explicit BlockAssessments(Zone* zone) |
| 131 | : map_(zone), map_for_moves_(zone), zone_(zone) {} |
| 132 | void Drop(InstructionOperand operand) { map_.erase(operand); } |
| 133 | void DropRegisters(); |
| 134 | void AddDefinition(InstructionOperand operand, int virtual_register) { |
| 135 | auto existent = map_.find(operand); |
| 136 | if (existent != map_.end()) { |
| 137 | // Drop the assignment |
| 138 | map_.erase(existent); |
| 139 | } |
| 140 | map_.insert( |
| 141 | std::make_pair(operand, new (zone_) FinalAssessment(virtual_register))); |
| 142 | } |
| 143 | |
| 144 | void PerformMoves(const Instruction* instruction); |
| 145 | void PerformParallelMoves(const ParallelMove* moves); |
| 146 | void CopyFrom(const BlockAssessments* other) { |
| 147 | CHECK(map_.empty()); |
| 148 | CHECK_NOT_NULL(other); |
| 149 | map_.insert(other->map_.begin(), other->map_.end()); |
| 150 | } |
| 151 | |
| 152 | OperandMap& map() { return map_; } |
| 153 | const OperandMap& map() const { return map_; } |
| 154 | void Print() const; |
| 155 | |
| 156 | private: |
| 157 | OperandMap map_; |
| 158 | OperandMap map_for_moves_; |
| 159 | Zone* zone_; |
| 160 | |
| 161 | DISALLOW_COPY_AND_ASSIGN(BlockAssessments); |
| 162 | }; |
| 163 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 164 | class RegisterAllocatorVerifier final : public ZoneObject { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 165 | public: |
| 166 | RegisterAllocatorVerifier(Zone* zone, const RegisterConfiguration* config, |
| 167 | const InstructionSequence* sequence); |
| 168 | |
| 169 | void VerifyAssignment(); |
| 170 | void VerifyGapMoves(); |
| 171 | |
| 172 | private: |
| 173 | enum ConstraintType { |
| 174 | kConstant, |
| 175 | kImmediate, |
| 176 | kRegister, |
| 177 | kFixedRegister, |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 178 | kFPRegister, |
| 179 | kFixedFPRegister, |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 180 | kSlot, |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 181 | kFPSlot, |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 182 | kFixedSlot, |
| 183 | kNone, |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 184 | kNoneFP, |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 185 | kExplicit, |
| 186 | kSameAsFirst, |
| 187 | kRegisterAndSlot |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 188 | }; |
| 189 | |
| 190 | struct OperandConstraint { |
| 191 | ConstraintType type_; |
| 192 | int value_; // subkind index when relevant |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 193 | int spilled_slot_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 194 | int virtual_register_; |
| 195 | }; |
| 196 | |
| 197 | struct InstructionConstraint { |
| 198 | const Instruction* instruction_; |
| 199 | size_t operand_constaints_size_; |
| 200 | OperandConstraint* operand_constraints_; |
| 201 | }; |
| 202 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 203 | typedef ZoneVector<InstructionConstraint> Constraints; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 204 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 205 | class DelayedAssessments : public ZoneObject { |
| 206 | public: |
| 207 | explicit DelayedAssessments(Zone* zone) : map_(zone) {} |
| 208 | |
| 209 | const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const { |
| 210 | return map_; |
| 211 | } |
| 212 | |
| 213 | void AddDelayedAssessment(InstructionOperand op, int vreg) { |
| 214 | auto it = map_.find(op); |
| 215 | if (it == map_.end()) { |
| 216 | map_.insert(std::make_pair(op, vreg)); |
| 217 | } else { |
| 218 | CHECK_EQ(it->second, vreg); |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | private: |
| 223 | ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_; |
| 224 | }; |
| 225 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 226 | Zone* zone() const { return zone_; } |
| 227 | const RegisterConfiguration* config() { return config_; } |
| 228 | const InstructionSequence* sequence() const { return sequence_; } |
| 229 | Constraints* constraints() { return &constraints_; } |
| 230 | |
| 231 | static void VerifyInput(const OperandConstraint& constraint); |
| 232 | static void VerifyTemp(const OperandConstraint& constraint); |
| 233 | static void VerifyOutput(const OperandConstraint& constraint); |
| 234 | |
| 235 | void BuildConstraint(const InstructionOperand* op, |
| 236 | OperandConstraint* constraint); |
| 237 | void CheckConstraint(const InstructionOperand* op, |
| 238 | const OperandConstraint* constraint); |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 239 | BlockAssessments* CreateForBlock(const InstructionBlock* block); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 240 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 241 | void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op, |
| 242 | BlockAssessments* current_assessments, |
| 243 | const PendingAssessment* assessment, |
| 244 | int virtual_register); |
| 245 | void ValidateFinalAssessment(RpoNumber block_id, InstructionOperand op, |
| 246 | BlockAssessments* current_assessments, |
| 247 | const FinalAssessment* assessment, |
| 248 | int virtual_register); |
| 249 | void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments, |
| 250 | InstructionOperand op, int virtual_register); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 251 | |
| 252 | Zone* const zone_; |
| 253 | const RegisterConfiguration* config_; |
| 254 | const InstructionSequence* const sequence_; |
| 255 | Constraints constraints_; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 256 | ZoneMap<RpoNumber, BlockAssessments*> assessments_; |
| 257 | ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 258 | |
| 259 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier); |
| 260 | }; |
| 261 | |
| 262 | } // namespace compiler |
| 263 | } // namespace internal |
| 264 | } // namespace v8 |
| 265 | |
| 266 | #endif |