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