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
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.
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
52enum AssessmentKind { Final, Pending };
53
54class Assessment : public ZoneObject {
55 public:
56  AssessmentKind kind() const { return kind_; }
57
58 protected:
59  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.
72class PendingAssessment final : public Assessment {
73 public:
74  explicit PendingAssessment(const InstructionBlock* origin,
75                             InstructionOperand operand)
76      : Assessment(Pending), origin_(origin), operand_(operand) {}
77
78  static const PendingAssessment* cast(const Assessment* assessment) {
79    CHECK(assessment->kind() == Pending);
80    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.
95class 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        original_pending_assessment_(original_pending) {}
102
103  int virtual_register() const { return virtual_register_; }
104  static const FinalAssessment* cast(const Assessment* assessment) {
105    CHECK(assessment->kind() == Final);
106    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
120struct 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.
128class BlockAssessments : public ZoneObject {
129 public:
130  typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap;
131  explicit BlockAssessments(Zone* zone)
132      : map_(zone), map_for_moves_(zone), zone_(zone) {}
133  void Drop(InstructionOperand operand) { map_.erase(operand); }
134  void DropRegisters();
135  void AddDefinition(InstructionOperand operand, int virtual_register) {
136    auto existent = map_.find(operand);
137    if (existent != map_.end()) {
138      // Drop the assignment
139      map_.erase(existent);
140    }
141    map_.insert(
142        std::make_pair(operand, new (zone_) FinalAssessment(virtual_register)));
143  }
144
145  void PerformMoves(const Instruction* instruction);
146  void PerformParallelMoves(const ParallelMove* moves);
147  void CopyFrom(const BlockAssessments* other) {
148    CHECK(map_.empty());
149    CHECK_NOT_NULL(other);
150    map_.insert(other->map_.begin(), other->map_.end());
151  }
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
165class 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    void AddDelayedAssessment(InstructionOperand op, int vreg) {
216      auto it = map_.find(op);
217      if (it == map_.end()) {
218        map_.insert(std::make_pair(op, vreg));
219      } else {
220        CHECK_EQ(it->second, vreg);
221      }
222    }
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
269