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/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.
     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 
     52 enum AssessmentKind { Final, Pending };
     53 
     54 class 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.
     72 class 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.
     95 class 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 
    120 struct 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.
    128 class 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 
    165 class 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