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_REGISTER_ALLOCATOR_VERIFIER_H_
      6 #define V8_REGISTER_ALLOCATOR_VERIFIER_H_
      7 
      8 #include "src/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:
     55   AssessmentKind kind() const { return kind_; }
     56 
     57  protected:
     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:
     73   explicit PendingAssessment(const InstructionBlock* origin,
     74                              InstructionOperand operand)
     75       : Assessment(Pending), origin_(origin), operand_(operand) {}
     76 
     77   static const PendingAssessment* cast(const Assessment* assessment) {
     78     CHECK(assessment->kind() == Pending);
     79     return static_cast<const PendingAssessment*>(assessment);
     80   }
     81 
     82   const InstructionBlock* origin() const { return origin_; }
     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)
     98       : Assessment(Final),
     99         virtual_register_(virtual_register),
    100         original_pending_assessment_(original_pending) {}
    101 
    102   int virtual_register() const { return virtual_register_; }
    103   static const FinalAssessment* cast(const Assessment* assessment) {
    104     CHECK(assessment->kind() == Final);
    105     return static_cast<const FinalAssessment*>(assessment);
    106   }
    107 
    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 {
    120   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;
    130   explicit BlockAssessments(Zone* zone)
    131       : map_(zone), map_for_moves_(zone), zone_(zone) {}
    132   void Drop(InstructionOperand operand) { map_.erase(operand); }
    133   void DropRegisters();
    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);
    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 
    152   OperandMap& map() { return 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     kFPSlot,
    182     kFixedSlot,
    183     kNone,
    184     kNoneFP,
    185     kExplicit,
    186     kSameAsFirst,
    187     kRegisterAndSlot
    188   };
    189 
    190   struct OperandConstraint {
    191     ConstraintType type_;
    192     int value_;  // subkind index when relevant
    193     int spilled_slot_;
    194     int virtual_register_;
    195   };
    196 
    197   struct InstructionConstraint {
    198     const Instruction* instruction_;
    199     size_t operand_constaints_size_;
    200     OperandConstraint* operand_constraints_;
    201   };
    202 
    203   typedef ZoneVector<InstructionConstraint> Constraints;
    204 
    205   class DelayedAssessments : public ZoneObject {
    206    public:
    207     explicit DelayedAssessments(Zone* zone) : map_(zone) {}
    208 
    209     const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const {
    210       return map_;
    211     }
    212 
    213     void AddDelayedAssessment(InstructionOperand op, int vreg) {
    214       auto it = map_.find(op);
    215       if (it == map_.end()) {
    216         map_.insert(std::make_pair(op, vreg));
    217       } else {
    218         CHECK_EQ(it->second, vreg);
    219       }
    220     }
    221 
    222    private:
    223     ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_;
    224   };
    225 
    226   Zone* zone() const { return zone_; }
    227   const RegisterConfiguration* config() { return config_; }
    228   const InstructionSequence* sequence() const { return sequence_; }
    229   Constraints* constraints() { return &constraints_; }
    230 
    231   static void VerifyInput(const OperandConstraint& constraint);
    232   static void VerifyTemp(const OperandConstraint& constraint);
    233   static void VerifyOutput(const OperandConstraint& constraint);
    234 
    235   void BuildConstraint(const InstructionOperand* op,
    236                        OperandConstraint* constraint);
    237   void CheckConstraint(const InstructionOperand* op,
    238                        const OperandConstraint* constraint);
    239   BlockAssessments* CreateForBlock(const InstructionBlock* block);
    240 
    241   void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op,
    242                                  BlockAssessments* current_assessments,
    243                                  const PendingAssessment* assessment,
    244                                  int virtual_register);
    245   void ValidateFinalAssessment(RpoNumber block_id, InstructionOperand op,
    246                                BlockAssessments* current_assessments,
    247                                const FinalAssessment* assessment,
    248                                int virtual_register);
    249   void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments,
    250                    InstructionOperand op, int virtual_register);
    251 
    252   Zone* const zone_;
    253   const RegisterConfiguration* config_;
    254   const InstructionSequence* const sequence_;
    255   Constraints constraints_;
    256   ZoneMap<RpoNumber, BlockAssessments*> assessments_;
    257   ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_;
    258 
    259   DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier);
    260 };
    261 
    262 }  // namespace compiler
    263 }  // namespace internal
    264 }  // namespace v8
    265 
    266 #endif
    267