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
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15class InstructionBlock;
16class 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
53enum AssessmentKind { Final, Pending };
54
55class 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.
74class 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.
108class 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
125struct 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.
133class 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
170class 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