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
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. 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
53enum AssessmentKind { Final, Pending };
54
55class Assessment : public ZoneObject {
56 public:
57  Assessment(const Assessment&) = delete;
58  Assessment& operator=(const Assessment&) = delete;
59
60  AssessmentKind kind() const { return kind_; }
61
62 protected:
63  explicit Assessment(AssessmentKind kind) : kind_(kind) {}
64  AssessmentKind kind_;
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.
74class 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        aliases_(zone) {}
82
83  PendingAssessment(const PendingAssessment&) = delete;
84  PendingAssessment& operator=(const PendingAssessment&) = delete;
85
86  static const PendingAssessment* cast(const Assessment* assessment) {
87    CHECK(assessment->kind() == Pending);
88    return static_cast<const PendingAssessment*>(assessment);
89  }
90
91  static PendingAssessment* cast(Assessment* assessment) {
92    CHECK(assessment->kind() == Pending);
93    return static_cast<PendingAssessment*>(assessment);
94  }
95
96  const InstructionBlock* origin() const { return origin_; }
97  InstructionOperand operand() const { return operand_; }
98  bool IsAliasOf(int vreg) const { return aliases_.count(vreg) > 0; }
99  void AddAlias(int vreg) { aliases_.insert(vreg); }
100
101 private:
102  const InstructionBlock* const origin_;
103  InstructionOperand operand_;
104  ZoneSet<int> aliases_;
105};
106
107// FinalAssessments are associated to operands that we know to be a certain
108// virtual register.
109class FinalAssessment final : public Assessment {
110 public:
111  explicit FinalAssessment(int virtual_register)
112      : Assessment(Final), virtual_register_(virtual_register) {}
113  FinalAssessment(const FinalAssessment&) = delete;
114  FinalAssessment& operator=(const FinalAssessment&) = delete;
115
116  int virtual_register() const { return virtual_register_; }
117  static const FinalAssessment* cast(const Assessment* assessment) {
118    CHECK(assessment->kind() == Final);
119    return static_cast<const FinalAssessment*>(assessment);
120  }
121
122 private:
123  int virtual_register_;
124};
125
126struct OperandAsKeyLess {
127  bool operator()(const InstructionOperand& a,
128                  const InstructionOperand& b) const {
129    return a.CompareCanonicalized(b);
130  }
131};
132
133// Assessments associated with a basic block.
134class BlockAssessments : public ZoneObject {
135 public:
136  using OperandMap = ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess>;
137  using OperandSet = ZoneSet<InstructionOperand, OperandAsKeyLess>;
138  explicit BlockAssessments(Zone* zone, int spill_slot_delta)
139      : map_(zone),
140        map_for_moves_(zone),
141        stale_ref_stack_slots_(zone),
142        spill_slot_delta_(spill_slot_delta),
143        zone_(zone) {}
144  BlockAssessments(const BlockAssessments&) = delete;
145  BlockAssessments& operator=(const BlockAssessments&) = delete;
146
147  void Drop(InstructionOperand operand) {
148    map_.erase(operand);
149    stale_ref_stack_slots_.erase(operand);
150  }
151  void DropRegisters();
152  void AddDefinition(InstructionOperand operand, int virtual_register) {
153    auto existent = map_.find(operand);
154    if (existent != map_.end()) {
155      // Drop the assignment
156      map_.erase(existent);
157      // Destination operand is no longer a stale reference.
158      stale_ref_stack_slots_.erase(operand);
159    }
160    map_.insert(
161        std::make_pair(operand, zone_->New<FinalAssessment>(virtual_register)));
162  }
163
164  void PerformMoves(const Instruction* instruction);
165  void PerformParallelMoves(const ParallelMove* moves);
166  void CopyFrom(const BlockAssessments* other) {
167    CHECK(map_.empty());
168    CHECK(stale_ref_stack_slots_.empty());
169    CHECK_NOT_NULL(other);
170    map_.insert(other->map_.begin(), other->map_.end());
171    stale_ref_stack_slots_.insert(other->stale_ref_stack_slots_.begin(),
172                                  other->stale_ref_stack_slots_.end());
173  }
174  void CheckReferenceMap(const ReferenceMap* reference_map);
175  bool IsStaleReferenceStackSlot(InstructionOperand op);
176
177  OperandMap& map() { return map_; }
178  const OperandMap& map() const { return map_; }
179
180  OperandSet& stale_ref_stack_slots() { return stale_ref_stack_slots_; }
181  const OperandSet& stale_ref_stack_slots() const {
182    return stale_ref_stack_slots_;
183  }
184
185  int spill_slot_delta() const { return spill_slot_delta_; }
186
187  void Print() const;
188
189 private:
190  OperandMap map_;
191  OperandMap map_for_moves_;
192  OperandSet stale_ref_stack_slots_;
193  int spill_slot_delta_;
194  Zone* zone_;
195};
196
197class RegisterAllocatorVerifier final : public ZoneObject {
198 public:
199  RegisterAllocatorVerifier(Zone* zone, const RegisterConfiguration* config,
200                            const InstructionSequence* sequence,
201                            const Frame* frame);
202  RegisterAllocatorVerifier(const RegisterAllocatorVerifier&) = delete;
203  RegisterAllocatorVerifier& operator=(const RegisterAllocatorVerifier&) =
204      delete;
205
206  void VerifyAssignment(const char* caller_info);
207  void VerifyGapMoves();
208
209 private:
210  enum ConstraintType {
211    kConstant,
212    kImmediate,
213    kRegister,
214    kFixedRegister,
215    kFPRegister,
216    kFixedFPRegister,
217    kSlot,
218    kFixedSlot,
219    kRegisterOrSlot,
220    kRegisterOrSlotFP,
221    kRegisterOrSlotOrConstant,
222    kSameAsInput,
223    kRegisterAndSlot
224  };
225
226  struct OperandConstraint {
227    ConstraintType type_;
228    // Constant or immediate value, register code, slot index, or slot size
229    // when relevant.
230    int value_;
231    int spilled_slot_;
232    int virtual_register_;
233  };
234
235  struct InstructionConstraint {
236    const Instruction* instruction_;
237    size_t operand_constaints_size_;
238    OperandConstraint* operand_constraints_;
239  };
240
241  using Constraints = ZoneVector<InstructionConstraint>;
242
243  class DelayedAssessments : public ZoneObject {
244   public:
245    explicit DelayedAssessments(Zone* zone) : map_(zone) {}
246
247    const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const {
248      return map_;
249    }
250
251    void AddDelayedAssessment(InstructionOperand op, int vreg) {
252      auto it = map_.find(op);
253      if (it == map_.end()) {
254        map_.insert(std::make_pair(op, vreg));
255      } else {
256        CHECK_EQ(it->second, vreg);
257      }
258    }
259
260   private:
261    ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_;
262  };
263
264  Zone* zone() const { return zone_; }
265  const RegisterConfiguration* config() { return config_; }
266  const InstructionSequence* sequence() const { return sequence_; }
267  Constraints* constraints() { return &constraints_; }
268  int spill_slot_delta() const { return spill_slot_delta_; }
269
270  static void VerifyInput(const OperandConstraint& constraint);
271  static void VerifyTemp(const OperandConstraint& constraint);
272  static void VerifyOutput(const OperandConstraint& constraint);
273
274  void BuildConstraint(const InstructionOperand* op,
275                       OperandConstraint* constraint);
276  void CheckConstraint(const InstructionOperand* op,
277                       const OperandConstraint* constraint);
278  BlockAssessments* CreateForBlock(const InstructionBlock* block);
279
280  // Prove that this operand is an alias of this virtual register in the given
281  // block. Update the assessment if that's the case.
282  void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op,
283                                 const BlockAssessments* current_assessments,
284                                 PendingAssessment* const assessment,
285                                 int virtual_register);
286  void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments,
287                   InstructionOperand op, int virtual_register);
288
289  Zone* const zone_;
290  const RegisterConfiguration* config_;
291  const InstructionSequence* const sequence_;
292  Constraints constraints_;
293  ZoneMap<RpoNumber, BlockAssessments*> assessments_;
294  ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_;
295  int spill_slot_delta_;
296  // TODO(chromium:725559): remove after we understand this bug's root cause.
297  const char* caller_info_ = nullptr;
298};
299
300}  // namespace compiler
301}  // namespace internal
302}  // namespace v8
303
304#endif  // V8_COMPILER_BACKEND_REGISTER_ALLOCATOR_VERIFIER_H_
305