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_REGISTER_ALLOCATOR_VERIFIER_H_
6 : #define V8_REGISTER_ALLOCATOR_VERIFIER_H_
7 :
8 : #include "src/compiler/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 654 : AssessmentKind kind() const { return kind_; }
58 :
59 : protected:
60 322 : 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 145 : 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 89 : static PendingAssessment* cast(Assessment* assessment) {
89 89 : CHECK(assessment->kind() == Pending);
90 89 : 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 177 : : Assessment(Final), virtual_register_(virtual_register) {}
112 :
113 : int virtual_register() const { return virtual_register_; }
114 238 : static const FinalAssessment* cast(const Assessment* assessment) {
115 238 : CHECK(assessment->kind() == Final);
116 238 : 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 : typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap;
136 : explicit BlockAssessments(Zone* zone)
137 142 : : map_(zone), map_for_moves_(zone), zone_(zone) {}
138 : void Drop(InstructionOperand operand) { map_.erase(operand); }
139 : void DropRegisters();
140 177 : void AddDefinition(InstructionOperand operand, int virtual_register) {
141 : auto existent = map_.find(operand);
142 177 : if (existent != map_.end()) {
143 : // Drop the assignment
144 : map_.erase(existent);
145 : }
146 : map_.insert(
147 531 : std::make_pair(operand, new (zone_) FinalAssessment(virtual_register)));
148 177 : }
149 :
150 : void PerformMoves(const Instruction* instruction);
151 : void PerformParallelMoves(const ParallelMove* moves);
152 79 : void CopyFrom(const BlockAssessments* other) {
153 79 : CHECK(map_.empty());
154 79 : CHECK_NOT_NULL(other);
155 : map_.insert(other->map_.begin(), other->map_.end());
156 79 : }
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 : kNone,
189 : kNoneFP,
190 : kExplicit,
191 : kSameAsFirst,
192 : kRegisterAndSlot
193 : };
194 :
195 : struct OperandConstraint {
196 : ConstraintType type_;
197 : // Constant or immediate value, register code, slot index, or slot size
198 : // when relevant.
199 : int value_;
200 : int spilled_slot_;
201 : int virtual_register_;
202 : };
203 :
204 : struct InstructionConstraint {
205 : const Instruction* instruction_;
206 : size_t operand_constaints_size_;
207 : OperandConstraint* operand_constraints_;
208 : };
209 :
210 : typedef ZoneVector<InstructionConstraint> Constraints;
211 :
212 : class DelayedAssessments : public ZoneObject {
213 : public:
214 : explicit DelayedAssessments(Zone* zone) : map_(zone) {}
215 :
216 : const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const {
217 : return map_;
218 : }
219 :
220 6 : void AddDelayedAssessment(InstructionOperand op, int vreg) {
221 : auto it = map_.find(op);
222 6 : if (it == map_.end()) {
223 12 : map_.insert(std::make_pair(op, vreg));
224 : } else {
225 0 : CHECK_EQ(it->second, vreg);
226 : }
227 6 : }
228 :
229 : private:
230 : ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_;
231 : };
232 :
233 : Zone* zone() const { return zone_; }
234 : const RegisterConfiguration* config() { return config_; }
235 : const InstructionSequence* sequence() const { return sequence_; }
236 : Constraints* constraints() { return &constraints_; }
237 :
238 : static void VerifyInput(const OperandConstraint& constraint);
239 : static void VerifyTemp(const OperandConstraint& constraint);
240 : static void VerifyOutput(const OperandConstraint& constraint);
241 :
242 : void BuildConstraint(const InstructionOperand* op,
243 : OperandConstraint* constraint);
244 : void CheckConstraint(const InstructionOperand* op,
245 : const OperandConstraint* constraint);
246 : BlockAssessments* CreateForBlock(const InstructionBlock* block);
247 :
248 : // Prove that this operand is an alias of this virtual register in the given
249 : // block. Update the assessment if that's the case.
250 : void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op,
251 : const BlockAssessments* current_assessments,
252 : PendingAssessment* const assessment,
253 : int virtual_register);
254 : void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments,
255 : InstructionOperand op, int virtual_register);
256 :
257 : Zone* const zone_;
258 : const RegisterConfiguration* config_;
259 : const InstructionSequence* const sequence_;
260 : Constraints constraints_;
261 : ZoneMap<RpoNumber, BlockAssessments*> assessments_;
262 : ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_;
263 : // TODO(chromium:725559): remove after we understand this bug's root cause.
264 : const char* caller_info_ = nullptr;
265 :
266 : DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier);
267 : };
268 :
269 : } // namespace compiler
270 : } // namespace internal
271 : } // namespace v8
272 :
273 : #endif
|
