[turbofan] New Register Allocator Validator

src/compiler/register-allocator-verifier.h

Index: src/compiler/register-allocator-verifier.h
diff --git a/src/compiler/register-allocator-verifier.h b/src/compiler/register-allocator-verifier.h
index f3ab54f01818788ae70fb2a6aa59714aefd9e776..31f8336823bff4d8509a2bbfafcca0d630f0cca6 100644
--- a/src/compiler/register-allocator-verifier.h
+++ b/src/compiler/register-allocator-verifier.h
@@ -14,6 +14,145 @@ namespace compiler {
 class InstructionOperand;
 class InstructionSequence;
 
+// The register allocator validator traverses instructions in the instruction
+// sequence, and verifies the correctness of machine operand substitutions of
+// virtual registers. It collects the virtual register instruction signatures
+// before register allocation. Then, after the register allocation pipeline
+// completes, it compares the operand substitutions against the pre-allocation
+// data.
+// At a high level, validation works as follows: we iterate through each block,
+// and, in a block, through each instruction; then:
+// - when an operand is the output of an instruction, we associate it to the
+// virtual register that the instruction sequence declares as its output. We
+// use the concept of "FinalAssessment" to model this.
+// - when an operand is used in an instruction, we check that the assessment
+// matches the expectation of the instruction
+// - moves simply copy the assessment over to the new operand
+// - blocks with more than one predecessor associate to each operand a "Pending"
+// assessment. The pending assessment remembers the operand and block where it
+// was created. Then, when the value is used (which may be as a different
+// operand, because of moves), we check that the virtual register at the use
+// site matches the definition of this pending operand: either the phi inputs
+// match, or, if it's not a phi, all the predecessors at the point the pending
+// assessment was defined have that operand assigned to the given virtual
+// register.
+// If a block is a loop header - so one or more of its predecessors are it or
+// below - we still treat uses of operands as above, but we record which operand
+// assessments haven't been made yet, and what virtual register they must
+// correspond to, and verify that when we are done with the respective
+// predecessor blocks.
+// This way, the algorithm always makes a final decision about the operands
+// in an instruction, ensuring convergence.
+// Operand assessments are recorded per block, as the result at the exit from
+// the block. When moving to a new block, we copy assessments from its single
+// predecessor, or, if the block has multiple predecessors, the mechanism was
+// described already.
+
+enum AssessmentKind { Final, Pending };
+
+class Assessment : public ZoneObject {
+ public:
+  AssessmentKind kind() const { return kind_; }
+
+ protected:
+  explicit Assessment(AssessmentKind kind) : kind_(kind) {}
+  AssessmentKind kind_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Assessment);
+};
+
+// FinalAssessmens are associated to operands that we know to be a certain
+// virtual register.
+class FinalAssessment final : public Assessment {
+ public:
+  explicit FinalAssessment(int virtual_register)
+      : Assessment(Final), virtual_register_(virtual_register) {}
+
+  int virtual_register() const { return virtual_register_; }
+  static const FinalAssessment* cast(const Assessment* assessment) {
+    CHECK(assessment->kind() == Final);
+    return static_cast<const FinalAssessment*>(assessment);
+  }
+
+ private:
+  int virtual_register_;
+
+  DISALLOW_COPY_AND_ASSIGN(FinalAssessment);
+};
+
+// PendingAssessments are associated to operands coming from the multiple
+// predecessors of a block. We only record the operand and the block, and
+// will determine if the way the operand is defined (from the predecessors)
+// matches a particular use. This handles scenarios where multiple phis are
+// defined with identical operands, and the move optimizer moved down the moves
+// separating the 2 phis in the block defining them.
+class PendingAssessment final : public Assessment {
+ public:
+  explicit PendingAssessment(const InstructionBlock* origin,
+                             InstructionOperand operand)
+      : Assessment(Pending), origin_(origin), operand_(operand) {}
+
+  static PendingAssessment* cast(Assessment* assessment) {
+    CHECK(assessment->kind() == Pending);
+    return static_cast<PendingAssessment*>(assessment);
+  }
+
+  const InstructionBlock* origin() const { return origin_; }
+  InstructionOperand operand() const { return operand_; }
+
+ private:
+  const InstructionBlock* const origin_;
+  InstructionOperand operand_;
+
+  DISALLOW_COPY_AND_ASSIGN(PendingAssessment);
+};
+
+struct OperandAsKeyLess {
+  bool operator()(const InstructionOperand& a,
+                  const InstructionOperand& b) const {
+    return a.CompareCanonicalized(b);
+  }
+};
+
+// Assessments associated with a basic block.
+class BlockAssessments : public ZoneObject {
+ public:
+  typedef ZoneMap<InstructionOperand, Assessment*, OperandAsKeyLess> OperandMap;
+  explicit BlockAssessments(Zone* zone)
+      : map_(zone), map_for_moves_(zone), zone_(zone) {}
+  void Drop(InstructionOperand operand) { map_.erase(operand); }
+  void DropRegisters();
+  void AddDefinition(InstructionOperand operand, int virtual_register) {
+    auto existent = map_.find(operand);
+    if (existent != map_.end()) {
+      // Drop the assignment
+      map_.erase(existent);
+    }
+    map_.insert(
+        std::make_pair(operand, new (zone_) FinalAssessment(virtual_register)));
+  }
+
+  void PerformMoves(const Instruction* instruction);
+  void PerformParallelMoves(const ParallelMove* moves);
+  void CopyFrom(const BlockAssessments* other) {
+    CHECK(map_.empty());
+    CHECK_NOT_NULL(other);
+    map_.insert(other->map_.begin(), other->map_.end());
+  }
+
+  OperandMap& map() { return map_; }
+  const OperandMap& map() const { return map_; }
+  void Print() const;
+
+ private:
+  OperandMap map_;
+  OperandMap map_for_moves_;
+  Zone* zone_;
+
+  DISALLOW_COPY_AND_ASSIGN(BlockAssessments);
+};
+
 class RegisterAllocatorVerifier final : public ZoneObject {
  public:
   RegisterAllocatorVerifier(Zone* zone, const RegisterConfiguration* config,
@@ -53,10 +192,29 @@ class RegisterAllocatorVerifier final : public ZoneObject {
     OperandConstraint* operand_constraints_;
   };
 
-  class BlockMaps;
-
   typedef ZoneVector<InstructionConstraint> Constraints;
 
+  class DelayedAssessments : public ZoneObject {
+   public:
+    explicit DelayedAssessments(Zone* zone) : map_(zone) {}
+
+    const ZoneMap<InstructionOperand, int, OperandAsKeyLess>& map() const {
+      return map_;
+    }
+
+    void AddDelayedAssessment(InstructionOperand op, int vreg) {
+      auto exists = map_.find(op);

[Benedikt Meurer, 2016/04/18 04:22:12]

Nit: s/exists/it/

[Mircea Trofin, 2016/04/18 04:38:25]

Done.

+      if (exists == map_.end()) {
+        map_.insert(std::make_pair(op, vreg));
+      } else {
+        CHECK_EQ(exists->second, vreg);
+      }
+    }
+
+   private:
+    ZoneMap<InstructionOperand, int, OperandAsKeyLess> map_;
+  };
+
   Zone* zone() const { return zone_; }
   const RegisterConfiguration* config() { return config_; }
   const InstructionSequence* sequence() const { return sequence_; }
@@ -70,13 +228,25 @@ class RegisterAllocatorVerifier final : public ZoneObject {
                        OperandConstraint* constraint);
   void CheckConstraint(const InstructionOperand* op,
                        const OperandConstraint* constraint);
+  BlockAssessments* CreateForBlock(const InstructionBlock* block);
 
-  void VerifyGapMoves(BlockMaps* outgoing_mappings, bool initial_pass);
+  void ValidatePendingAssessment(RpoNumber block_id, InstructionOperand op,
+                                 PendingAssessment* assessment,
+                                 int virtual_register);
+  void ValidateUse(RpoNumber block_id, BlockAssessments* current_assessments,
+                   InstructionOperand op, int virtual_register);
 
   Zone* const zone_;
   const RegisterConfiguration* config_;
   const InstructionSequence* const sequence_;
   Constraints constraints_;
+  ZoneMap<RpoNumber, BlockAssessments*> assessments_;
+  ZoneMap<RpoNumber, DelayedAssessments*> outstanding_assessments_;
+
+  // Cached structures, to avoid memory churn. Needed solely in
+  // ValidatePendingAssessment.
+  ZoneQueue<std::pair<PendingAssessment*, int>> worklist_;
+  ZoneSet<RpoNumber> seen_;
 
   DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorVerifier);
 };