// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/instruction.h"
#include "src/compiler/register-allocator-verifier.h"

namespace v8 {
namespace internal {
namespace compiler {

static size_t OperandCount(const Instruction* instr) {
  return instr->InputCount() + instr->OutputCount() + instr->TempCount();
}


static void VerifyGapEmpty(const GapInstruction* gap) {
  for (int i = GapInstruction::FIRST_INNER_POSITION;
       i <= GapInstruction::LAST_INNER_POSITION; i++) {
    GapInstruction::InnerPosition inner_pos =
        static_cast<GapInstruction::InnerPosition>(i);
    CHECK_EQ(NULL, gap->GetParallelMove(inner_pos));
  }
}


void RegisterAllocatorVerifier::VerifyInput(
    const OperandConstraint& constraint) {
  CHECK_NE(kSameAsFirst, constraint.type_);
  if (constraint.type_ != kImmediate) {
    CHECK_NE(UnallocatedOperand::kInvalidVirtualRegister,
             constraint.virtual_register_);
  }
}


void RegisterAllocatorVerifier::VerifyTemp(
    const OperandConstraint& constraint) {
  CHECK_NE(kSameAsFirst, constraint.type_);
  CHECK_NE(kImmediate, constraint.type_);
  CHECK_NE(kConstant, constraint.type_);
  CHECK_EQ(UnallocatedOperand::kInvalidVirtualRegister,
           constraint.virtual_register_);
}


void RegisterAllocatorVerifier::VerifyOutput(
    const OperandConstraint& constraint) {
  CHECK_NE(kImmediate, constraint.type_);
  CHECK_NE(UnallocatedOperand::kInvalidVirtualRegister,
           constraint.virtual_register_);
}


RegisterAllocatorVerifier::RegisterAllocatorVerifier(
    Zone* zone, const RegisterConfiguration* config,
    const InstructionSequence* sequence)
    : zone_(zone), config_(config), sequence_(sequence), constraints_(zone) {
  constraints_.reserve(sequence->instructions().size());
  // TODO(dcarney): model unique constraints.
  // Construct OperandConstraints for all InstructionOperands, eliminating
  // kSameAsFirst along the way.
  for (const auto* instr : sequence->instructions()) {
    const size_t operand_count = OperandCount(instr);
    auto* op_constraints =
        zone->NewArray<OperandConstraint>(static_cast<int>(operand_count));
    size_t count = 0;
    for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
      BuildConstraint(instr->InputAt(i), &op_constraints[count]);
      VerifyInput(op_constraints[count]);
    }
    for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
      BuildConstraint(instr->TempAt(i), &op_constraints[count]);
      VerifyTemp(op_constraints[count]);
    }
    for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
      BuildConstraint(instr->OutputAt(i), &op_constraints[count]);
      if (op_constraints[count].type_ == kSameAsFirst) {
        CHECK(instr->InputCount() > 0);
        op_constraints[count].type_ = op_constraints[0].type_;
        op_constraints[count].value_ = op_constraints[0].value_;
      }
      VerifyOutput(op_constraints[count]);
    }
    // All gaps should be totally unallocated at this point.
    if (instr->IsGapMoves()) {
      CHECK(operand_count == 0);
      VerifyGapEmpty(GapInstruction::cast(instr));
    }
    InstructionConstraint instr_constraint = {instr, operand_count,
                                              op_constraints};
    constraints()->push_back(instr_constraint);
  }
}


void RegisterAllocatorVerifier::VerifyAssignment() {
  CHECK(sequence()->instructions().size() == constraints()->size());
  auto instr_it = sequence()->begin();
  for (const auto& instr_constraint : *constraints()) {
    const auto* instr = instr_constraint.instruction_;
    const size_t operand_count = instr_constraint.operand_constaints_size_;
    const auto* op_constraints = instr_constraint.operand_constraints_;
    CHECK_EQ(instr, *instr_it);
    CHECK(operand_count == OperandCount(instr));
    size_t count = 0;
    for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
      CheckConstraint(instr->InputAt(i), &op_constraints[count]);
    }
    for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
      CheckConstraint(instr->TempAt(i), &op_constraints[count]);
    }
    for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
      CheckConstraint(instr->OutputAt(i), &op_constraints[count]);
    }
    ++instr_it;
  }
}


void RegisterAllocatorVerifier::BuildConstraint(const InstructionOperand* op,
                                                OperandConstraint* constraint) {
  constraint->value_ = kMinInt;
  constraint->virtual_register_ = UnallocatedOperand::kInvalidVirtualRegister;
  if (op->IsConstant()) {
    constraint->type_ = kConstant;
    constraint->value_ = ConstantOperand::cast(op)->index();
    constraint->virtual_register_ = constraint->value_;
  } else if (op->IsImmediate()) {
    constraint->type_ = kImmediate;
    constraint->value_ = ImmediateOperand::cast(op)->index();
  } else {
    CHECK(op->IsUnallocated());
    const auto* unallocated = UnallocatedOperand::cast(op);
    int vreg = unallocated->virtual_register();
    constraint->virtual_register_ = vreg;
    if (unallocated->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
      constraint->type_ = kFixedSlot;
      constraint->value_ = unallocated->fixed_slot_index();
    } else {
      switch (unallocated->extended_policy()) {
        case UnallocatedOperand::ANY:
          CHECK(false);
          break;
        case UnallocatedOperand::NONE:
          if (sequence()->IsDouble(vreg)) {
            constraint->type_ = kNoneDouble;
          } else {
            constraint->type_ = kNone;
          }
          break;
        case UnallocatedOperand::FIXED_REGISTER:
          constraint->type_ = kFixedRegister;
          constraint->value_ = unallocated->fixed_register_index();
          break;
        case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
          constraint->type_ = kFixedDoubleRegister;
          constraint->value_ = unallocated->fixed_register_index();
          break;
        case UnallocatedOperand::MUST_HAVE_REGISTER:
          if (sequence()->IsDouble(vreg)) {
            constraint->type_ = kDoubleRegister;
          } else {
            constraint->type_ = kRegister;
          }
          break;
        case UnallocatedOperand::SAME_AS_FIRST_INPUT:
          constraint->type_ = kSameAsFirst;
          break;
      }
    }
  }
}


void RegisterAllocatorVerifier::CheckConstraint(
    const InstructionOperand* op, const OperandConstraint* constraint) {
  switch (constraint->type_) {
    case kConstant:
      CHECK(op->IsConstant());
      CHECK_EQ(op->index(), constraint->value_);
      return;
    case kImmediate:
      CHECK(op->IsImmediate());
      CHECK_EQ(op->index(), constraint->value_);
      return;
    case kRegister:
      CHECK(op->IsRegister());
      return;
    case kFixedRegister:
      CHECK(op->IsRegister());
      CHECK_EQ(op->index(), constraint->value_);
      return;
    case kDoubleRegister:
      CHECK(op->IsDoubleRegister());
      return;
    case kFixedDoubleRegister:
      CHECK(op->IsDoubleRegister());
      CHECK_EQ(op->index(), constraint->value_);
      return;
    case kFixedSlot:
      CHECK(op->IsStackSlot());
      CHECK_EQ(op->index(), constraint->value_);
      return;
    case kNone:
      CHECK(op->IsRegister() || op->IsStackSlot());
      return;
    case kNoneDouble:
      CHECK(op->IsDoubleRegister() || op->IsDoubleStackSlot());
      return;
    case kSameAsFirst:
      CHECK(false);
      return;
  }
}


class RegisterAllocatorVerifier::OutgoingMapping : public ZoneObject {
 public:
  struct OperandLess {
    bool operator()(const InstructionOperand* a,
                    const InstructionOperand* b) const {
      if (a->kind() == b->kind()) return a->index() < b->index();
      return a->kind() < b->kind();
    }
  };

  typedef std::map<
      const InstructionOperand*, int, OperandLess,
      zone_allocator<std::pair<const InstructionOperand*, const int>>>
      LocationMap;

  explicit OutgoingMapping(Zone* zone)
      : locations_(LocationMap::key_compare(),
                   LocationMap::allocator_type(zone)),
        predecessor_intersection_(LocationMap::key_compare(),
                                  LocationMap::allocator_type(zone)) {}

  LocationMap* locations() { return &locations_; }

  void RunPhis(const InstructionSequence* sequence,
               const InstructionBlock* block, size_t phi_index) {
    // This operation is only valid in edge split form.
    size_t predecessor_index = block->predecessors()[phi_index].ToSize();
    CHECK(sequence->instruction_blocks()[predecessor_index]->SuccessorCount() ==
          1);
    for (const auto* phi : block->phis()) {
      auto input = phi->inputs()[phi_index];
      CHECK(locations()->find(input) != locations()->end());
      auto it = locations()->find(phi->output());
      CHECK(it != locations()->end());
      if (input->IsConstant()) {
        CHECK_EQ(it->second, input->index());
      } else {
        CHECK_EQ(it->second, phi->operands()[phi_index]);
      }
      it->second = phi->virtual_register();
    }
  }

  void RunGapInstruction(Zone* zone, const GapInstruction* gap) {
    for (int i = GapInstruction::FIRST_INNER_POSITION;
         i <= GapInstruction::LAST_INNER_POSITION; i++) {
      GapInstruction::InnerPosition inner_pos =
          static_cast<GapInstruction::InnerPosition>(i);
      const ParallelMove* move = gap->GetParallelMove(inner_pos);
      if (move == nullptr) continue;
      RunParallelMoves(zone, move);
    }
  }

  void RunParallelMoves(Zone* zone, const ParallelMove* move) {
    // Compute outgoing mappings.
    LocationMap to_insert((LocationMap::key_compare()),
                          LocationMap::allocator_type(zone));
    auto* moves = move->move_operands();
    for (auto i = moves->begin(); i != moves->end(); ++i) {
      if (i->IsEliminated()) continue;
      auto cur = locations()->find(i->source());
      CHECK(cur != locations()->end());
      to_insert.insert(std::make_pair(i->destination(), cur->second));
    }
    // Drop current mappings.
    for (auto i = moves->begin(); i != moves->end(); ++i) {
      if (i->IsEliminated()) continue;
      auto cur = locations()->find(i->destination());
      if (cur != locations()->end()) locations()->erase(cur);
    }
    // Insert new values.
    locations()->insert(to_insert.begin(), to_insert.end());
  }

  void Map(const InstructionOperand* op, int virtual_register) {
    locations()->insert(std::make_pair(op, virtual_register));
  }

  void Drop(const InstructionOperand* op) {
    auto it = locations()->find(op);
    if (it != locations()->end()) locations()->erase(it);
  }

  void DropRegisters(const RegisterConfiguration* config) {
    for (int i = 0; i < config->num_general_registers(); ++i) {
      InstructionOperand op(InstructionOperand::REGISTER, i);
      Drop(&op);
    }
    for (int i = 0; i < config->num_double_registers(); ++i) {
      InstructionOperand op(InstructionOperand::DOUBLE_REGISTER, i);
      Drop(&op);
    }
  }

  void InitializeFromFirstPredecessor(const InstructionSequence* sequence,
                                      const OutgoingMappings* outgoing_mappings,
                                      const InstructionBlock* block) {
    if (block->predecessors().empty()) return;
    size_t predecessor_index = block->predecessors()[0].ToSize();
    CHECK(predecessor_index < block->rpo_number().ToSize());
    auto* incoming = outgoing_mappings->at(predecessor_index);
    if (block->PredecessorCount() > 1) {
      // Update incoming map with phis. The remaining phis will be checked later
      // as their mappings are not guaranteed to exist yet.
      incoming->RunPhis(sequence, block, 0);
    }
    // Now initialize outgoing mapping for this block with incoming mapping.
    CHECK(locations_.empty());
    locations_ = incoming->locations_;
  }

  void InitializeFromIntersection() { locations_ = predecessor_intersection_; }

  void InitializeIntersection(const OutgoingMapping* incoming) {
    CHECK(predecessor_intersection_.empty());
    predecessor_intersection_ = incoming->locations_;
  }

  void Intersect(const OutgoingMapping* other) {
    if (predecessor_intersection_.empty()) return;
    auto it = predecessor_intersection_.begin();
    OperandLess less;
    for (const auto& o : other->locations_) {
      while (less(it->first, o.first)) {
        ++it;
        if (it == predecessor_intersection_.end()) return;
      }
      if (it->first->Equals(o.first)) {
        if (o.second != it->second) {
          predecessor_intersection_.erase(it++);
        } else {
          ++it;
        }
        if (it == predecessor_intersection_.end()) return;
      }
    }
  }

 private:
  LocationMap locations_;
  LocationMap predecessor_intersection_;

  DISALLOW_COPY_AND_ASSIGN(OutgoingMapping);
};


// Verify that all gap moves move the operands for a virtual register into the
// correct location for every instruction.
void RegisterAllocatorVerifier::VerifyGapMoves() {
  typedef ZoneVector<OutgoingMapping*> OutgoingMappings;
  OutgoingMappings outgoing_mappings(
      static_cast<int>(sequence()->instruction_blocks().size()), nullptr,
      zone());
  // Construct all mappings, ignoring back edges and multiple entries.
  ConstructOutgoingMappings(&outgoing_mappings, true);
  // Run all remaining phis and compute the intersection of all predecessor
  // mappings.
  for (const auto* block : sequence()->instruction_blocks()) {
    if (block->PredecessorCount() == 0) continue;
    const size_t block_index = block->rpo_number().ToSize();
    auto* mapping = outgoing_mappings[block_index];
    bool initialized = false;
    // Walk predecessors in reverse to ensure Intersect is correctly working.
    // If it did nothing, the second pass would do exactly what the first pass
    // did.
    for (size_t phi_input = block->PredecessorCount() - 1; true; --phi_input) {
      const size_t pred_block_index = block->predecessors()[phi_input].ToSize();
      auto* incoming = outgoing_mappings[pred_block_index];
      if (phi_input != 0) incoming->RunPhis(sequence(), block, phi_input);
      if (!initialized) {
        mapping->InitializeIntersection(incoming);
        initialized = true;
      } else {
        mapping->Intersect(incoming);
      }
      if (phi_input == 0) break;
    }
  }
  // Construct all mappings again, this time using the instersection mapping
  // above as the incoming mapping instead of the result from the first
  // predecessor.
  ConstructOutgoingMappings(&outgoing_mappings, false);
}


void RegisterAllocatorVerifier::ConstructOutgoingMappings(
    OutgoingMappings* outgoing_mappings, bool initial_pass) {
  // Compute the locations of all virtual registers leaving every block, using
  // only the first predecessor as source for the input mapping.
  for (const auto* block : sequence()->instruction_blocks()) {
    const size_t block_index = block->rpo_number().ToSize();
    auto* current = outgoing_mappings->at(block_index);
    CHECK(initial_pass == (current == nullptr));
    // Initialize current.
    if (!initial_pass) {
      // Skip check second time around for blocks without multiple predecessors
      // as we have already executed this in the initial run.
      if (block->PredecessorCount() <= 1) continue;
      current->InitializeFromIntersection();
    } else {
      current = new (zone()) OutgoingMapping(zone());
      outgoing_mappings->at(block_index) = current;
      // Copy outgoing values from predecessor block.
      current->InitializeFromFirstPredecessor(sequence(), outgoing_mappings,
                                              block);
    }
    // Update current with gaps and operands for all instructions in block.
    for (int instr_index = block->code_start(); instr_index < block->code_end();
         ++instr_index) {
      const auto& instr_constraint = constraints_[instr_index];
      const auto* instr = instr_constraint.instruction_;
      const auto* op_constraints = instr_constraint.operand_constraints_;
      size_t count = 0;
      for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
        if (op_constraints[count].type_ == kImmediate) continue;
        auto it = current->locations()->find(instr->InputAt(i));
        int virtual_register = op_constraints[count].virtual_register_;
        CHECK(it != current->locations()->end());
        CHECK_EQ(it->second, virtual_register);
      }
      for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
        current->Drop(instr->TempAt(i));
      }
      if (instr->IsCall()) {
        current->DropRegisters(config());
      }
      for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
        current->Drop(instr->OutputAt(i));
        int virtual_register = op_constraints[count].virtual_register_;
        current->Map(instr->OutputAt(i), virtual_register);
      }
      if (instr->IsGapMoves()) {
        const auto* gap = GapInstruction::cast(instr);
        current->RunGapInstruction(zone(), gap);
      }
    }
  }
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8