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