Line data Source code
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 512 : AssessmentKind kind() const { return kind_; }
58 :
59 : protected:
60 485 : 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 235 : 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 153 : 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 250 : : Assessment(Final), virtual_register_(virtual_register) {}
112 :
113 : int virtual_register() const { return virtual_register_; }
114 : static const FinalAssessment* cast(const Assessment* assessment) {
115 359 : 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 144 : : map_(zone), map_for_moves_(zone), zone_(zone) {}
138 : void Drop(InstructionOperand operand) { map_.erase(operand); }
139 : void DropRegisters();
140 250 : void AddDefinition(InstructionOperand operand, int virtual_register) {
141 : auto existent = map_.find(operand);
142 250 : if (existent != map_.end()) {
143 : // Drop the assignment
144 : map_.erase(existent);
145 : }
146 : map_.insert(
147 750 : std::make_pair(operand, new (zone_) FinalAssessment(virtual_register)));
148 250 : }
149 :
150 : void PerformMoves(const Instruction* instruction);
151 : void PerformParallelMoves(const ParallelMove* moves);
152 82 : void CopyFrom(const BlockAssessments* other) {
153 82 : CHECK(map_.empty());
154 82 : CHECK_NOT_NULL(other);
155 : map_.insert(other->map_.begin(), other->map_.end());
156 82 : }
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 6 : void AddDelayedAssessment(InstructionOperand op, int vreg) {
222 : auto it = map_.find(op);
223 6 : if (it == map_.end()) {
224 12 : map_.insert(std::make_pair(op, vreg));
225 : } else {
226 0 : CHECK_EQ(it->second, vreg);
227 : }
228 6 : }
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_
|
