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.
40 : // If a block is a loop header - so one or more of its predecessors are it or
41 : // below - we still treat uses of operands as above, but we record which operand
42 : // assessments haven't been made yet, and what virtual register they must
43 : // correspond to, and verify that when we are done with the respective
44 : // predecessor blocks.
45 : // This way, the algorithm always makes a final decision about the operands
46 : // in an instruction, ensuring convergence.
47 : // Operand assessments are recorded per block, as the result at the exit from
48 : // the block. When moving to a new block, we copy assessments from its single
49 : // predecessor, or, if the block has multiple predecessors, the mechanism was
50 : // described already.
51 :
52 : enum AssessmentKind { Final, Pending };
53 :
54 : class Assessment : public ZoneObject {
55 : public:
56 658 : AssessmentKind kind() const { return kind_; }
57 :
58 : protected:
59 373 : explicit Assessment(AssessmentKind kind) : kind_(kind) {}
60 : AssessmentKind kind_;
61 :
62 : private:
63 : DISALLOW_COPY_AND_ASSIGN(Assessment);
64 : };
65 :
66 : // PendingAssessments are associated to operands coming from the multiple
67 : // predecessors of a block. We only record the operand and the block, and
68 : // will determine if the way the operand is defined (from the predecessors)
69 : // matches a particular use. This handles scenarios where multiple phis are
70 : // defined with identical operands, and the move optimizer moved down the moves
71 : // separating the 2 phis in the block defining them.
72 : class PendingAssessment final : public Assessment {
73 : public:
74 : explicit PendingAssessment(const InstructionBlock* origin,
75 : InstructionOperand operand)
76 145 : : Assessment(Pending), origin_(origin), operand_(operand) {}
77 :
78 87 : static const PendingAssessment* cast(const Assessment* assessment) {
79 87 : CHECK(assessment->kind() == Pending);
80 87 : return static_cast<const PendingAssessment*>(assessment);
81 : }
82 :
83 : const InstructionBlock* origin() const { return origin_; }
84 : InstructionOperand operand() const { return operand_; }
85 :
86 : private:
87 : const InstructionBlock* const origin_;
88 : InstructionOperand operand_;
89 :
90 : DISALLOW_COPY_AND_ASSIGN(PendingAssessment);
91 : };
92 :
93 : // FinalAssessments are associated to operands that we know to be a certain
94 : // virtual register.
95 : class FinalAssessment final : public Assessment {
96 : public:
97 : explicit FinalAssessment(int virtual_register,
98 : const PendingAssessment* original_pending = nullptr)
99 : : Assessment(Final),
100 : virtual_register_(virtual_register),
101 228 : original_pending_assessment_(original_pending) {}
102 :
103 : int virtual_register() const { return virtual_register_; }
104 242 : static const FinalAssessment* cast(const Assessment* assessment) {
105 242 : CHECK(assessment->kind() == Final);
106 242 : return static_cast<const FinalAssessment*>(assessment);
107 : }
108 :
109 : const PendingAssessment* original_pending_assessment() const {
110 : return original_pending_assessment_;
111 : }
112 :
113 : private:
114 : int virtual_register_;
115 : const PendingAssessment* original_pending_assessment_;
116 :
117 : DISALLOW_COPY_AND_ASSIGN(FinalAssessment);
118 : };
119 :
120 : struct OperandAsKeyLess {
121 : bool operator()(const InstructionOperand& a,
122 : const InstructionOperand& b) const {
123 : return a.CompareCanonicalized(b);
124 : }
125 : };
126 :
127 : // Assessments associated with a basic block.
128 : class BlockAssessments : public ZoneObject {
129 : public:
130 : typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap;
131 : explicit BlockAssessments(Zone* zone)
132 142 : : map_(zone), map_for_moves_(zone), zone_(zone) {}
133 : void Drop(InstructionOperand operand) { map_.erase(operand); }
134 : void DropRegisters();
135 177 : void AddDefinition(InstructionOperand operand, int virtual_register) {
136 : auto existent = map_.find(operand);
137 177 : if (existent != map_.end()) {
138 : // Drop the assignment
139 : map_.erase(existent);
140 : }
141 : map_.insert(
142 531 : std::make_pair(operand, new (zone_) FinalAssessment(virtual_register)));
143 177 : }
144 :
145 : void PerformMoves(const Instruction* instruction);
146 : void PerformParallelMoves(const ParallelMove* moves);
147 79 : void CopyFrom(const BlockAssessments* other) {
148 79 : CHECK(map_.empty());
149 79 : CHECK_NOT_NULL(other);
150 : map_.insert(other->map_.begin(), other->map_.end());
151 79 : }
152 :
153 : OperandMap& map() { return map_; }
154 : const OperandMap& map() const { return map_; }
155 : void Print() const;
156 :
157 : private:
158 : OperandMap map_;
159 : OperandMap map_for_moves_;
160 : Zone* zone_;
161 :
162 : DISALLOW_COPY_AND_ASSIGN(BlockAssessments);
163 : };
164 :
165 : class RegisterAllocatorVerifier final : public ZoneObject {
166 : public:
167 : RegisterAllocatorVerifier(Zone* zone, const RegisterConfiguration* config,
168 : const InstructionSequence* sequence);
169 :
170 : void VerifyAssignment();
171 : void VerifyGapMoves();
172 :
173 : private:
174 : enum ConstraintType {
175 : kConstant,
176 : kImmediate,
177 : kRegister,
178 : kFixedRegister,
179 : kFPRegister,
180 : kFixedFPRegister,
181 : kSlot,
182 : kFixedSlot,
183 : kNone,
184 : kNoneFP,
185 : kExplicit,
186 : kSameAsFirst,
187 : kRegisterAndSlot
188 : };
189 :
190 : struct OperandConstraint {
191 : ConstraintType type_;
192 : // Constant or immediate value, register code, slot index, or slot size
193 : // when relevant.
194 : int value_;
195 : int spilled_slot_;
196 : int virtual_register_;
197 : };
198 :
199 : struct InstructionConstraint {
200 : const Instruction* instruction_;
201 : size_t operand_constaints_size_;
202 : OperandConstraint* operand_constraints_;
203 : };
204 :
205 : typedef ZoneVector<InstructionConstraint> Constraints;
206 :
207 : class DelayedAssessments : public ZoneObject {
208 : public:
209 : explicit DelayedAssessments(Zone* zone) : map_(zone) {}
210 :
211 : const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const {
212 : return map_;
213 : }
214 :
215 6 : void AddDelayedAssessment(InstructionOperand op, int vreg) {
216 : auto it = map_.find(op);
217 6 : if (it == map_.end()) {
218 12 : map_.insert(std::make_pair(op, vreg));
219 : } else {
220 0 : CHECK_EQ(it->second, vreg);
221 : }
222 6 : }
223 :
224 : private:
225 : ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_;
226 : };
227 :
228 : Zone* zone() const { return zone_; }
229 : const RegisterConfiguration* config() { return config_; }
230 : const InstructionSequence* sequence() const { return sequence_; }
231 : Constraints* constraints() { return &constraints_; }
232 :
233 : static void VerifyInput(const OperandConstraint& constraint);
234 : static void VerifyTemp(const OperandConstraint& constraint);
235 : static void VerifyOutput(const OperandConstraint& constraint);
236 :
237 : void BuildConstraint(const InstructionOperand* op,
238 : OperandConstraint* constraint);
239 : void CheckConstraint(const InstructionOperand* op,
240 : const OperandConstraint* constraint);
241 : BlockAssessments* CreateForBlock(const InstructionBlock* block);
242 :
243 : void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op,
244 : BlockAssessments* current_assessments,
245 : const PendingAssessment* assessment,
246 : int virtual_register);
247 : void ValidateFinalAssessment(RpoNumber block_id, InstructionOperand op,
248 : BlockAssessments* current_assessments,
249 : const FinalAssessment* assessment,
250 : int virtual_register);
251 : void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments,
252 : InstructionOperand op, int virtual_register);
253 :
254 : Zone* const zone_;
255 : const RegisterConfiguration* config_;
256 : const InstructionSequence* const sequence_;
257 : Constraints constraints_;
258 : ZoneMap<RpoNumber, BlockAssessments*> assessments_;
259 : ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_;
260 :
261 : DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier);
262 : };
263 :
264 : } // namespace compiler
265 : } // namespace internal
266 : } // namespace v8
267 :
268 : #endif
|
