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