// Copyright (c) 2019, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#if !defined(DART_PRECOMPILED_RUNTIME)
#if defined(DEBUG)

#include "vm/compiler/backend/flow_graph_checker.h"

#include "vm/compiler/backend/flow_graph.h"
#include "vm/compiler/backend/il.h"

namespace dart {

FlowGraphChecker::FlowGraphChecker(FlowGraph* flow_graph)
    : flow_graph_(flow_graph) {}

static bool IsPred(BlockEntryInstr* block, BlockEntryInstr* succ) {
  for (intptr_t i = 0; i < succ->PredecessorCount(); ++i) {
    if (succ->PredecessorAt(i) == block) {
      return true;
    }
  }
  return false;
}

static bool IsSucc(BlockEntryInstr* block, BlockEntryInstr* pred) {
  Instruction* last = pred->last_instruction();
  for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
    if (last->SuccessorAt(i) == block) {
      return true;
    }
  }
  return false;
}

static bool IsDominated(BlockEntryInstr* block, BlockEntryInstr* dom) {
  for (intptr_t i = 0; i < dom->dominated_blocks().length(); ++i) {
    if (dom->dominated_blocks()[i] == block) {
      return true;
    }
  }
  return false;
}

void FlowGraphChecker::CheckBasicBlocks() {
  const GrowableArray<BlockEntryInstr*>& preorder = flow_graph_->preorder();
  const GrowableArray<BlockEntryInstr*>& postorder = flow_graph_->postorder();
  const GrowableArray<BlockEntryInstr*>& rev_postorder =
      flow_graph_->reverse_postorder();

  // Make sure lengths match.
  const intptr_t block_count = preorder.length();
  ASSERT(block_count == postorder.length());
  ASSERT(block_count == rev_postorder.length());

  // Make sure postorder has true reverse.
  for (intptr_t i = 0; i < block_count; ++i) {
    ASSERT(postorder[i] == rev_postorder[block_count - i - 1]);
  }

  // Iterate over all basic blocks.
  const intptr_t max_block_id = flow_graph_->max_block_id();
  for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
       !block_it.Done(); block_it.Advance()) {
    BlockEntryInstr* block = block_it.Current();
    ASSERT(block->block_id() <= max_block_id);
    // Make sure ordering is consistent.
    ASSERT(block->preorder_number() <= block_count);
    ASSERT(block->postorder_number() <= block_count);
    ASSERT(preorder[block->preorder_number()] == block);
    ASSERT(postorder[block->postorder_number()] == block);
    // Make sure predecessors and successors agree.
    Instruction* last = block->last_instruction();
    for (intptr_t i = 0; i < last->SuccessorCount(); ++i) {
      ASSERT(IsPred(block, last->SuccessorAt(i)));
    }
    for (intptr_t i = 0; i < block->PredecessorCount(); ++i) {
      ASSERT(IsSucc(block, block->PredecessorAt(i)));
    }
    // Make sure dominance relations agree.
    const intptr_t num_dom = block->dominated_blocks().length();
    for (intptr_t i = 0; i < num_dom; ++i) {
      ASSERT(block->dominated_blocks()[i]->dominator() == block);
    }
    if (block->dominator() != nullptr) {
      ASSERT(IsDominated(block, block->dominator()));
    }
    // Visit all instructions in this block.
    CheckInstructions(block);
  }
}

void FlowGraphChecker::CheckInstructions(BlockEntryInstr* block) {
  Instruction* prev = block;
  for (ForwardInstructionIterator instr_it(block); !instr_it.Done();
       instr_it.Advance()) {
    Instruction* instruction = instr_it.Current();
    // Make sure linked list agrees.
    ASSERT(prev->next() == instruction);
    ASSERT(instruction->previous() == prev);
    prev = instruction;
  }
}

// Main entry point of graph checker.
void FlowGraphChecker::Check() {
  ASSERT(flow_graph_ != nullptr);
  CheckBasicBlocks();
}

}  // namespace dart

#endif  // defined(DEBUG)
#endif  // !defined(DART_PRECOMPILED_RUNTIME)