// 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/jump-threading.h"
#include "src/compiler/code-generator-impl.h"

namespace v8 {
namespace internal {
namespace compiler {

typedef BasicBlock::RpoNumber RpoNumber;

#define TRACE(x) \
  if (FLAG_trace_turbo_jt) PrintF x

struct JumpThreadingState {
  bool forwarded;
  ZoneVector<RpoNumber>& result;
  ZoneStack<RpoNumber>& stack;

  void Clear(size_t count) { result.assign(count, unvisited()); }
  void PushIfUnvisited(RpoNumber num) {
    if (result[num.ToInt()] == unvisited()) {
      stack.push(num);
      result[num.ToInt()] = onstack();
    }
  }
  void Forward(RpoNumber to) {
    RpoNumber from = stack.top();
    RpoNumber to_to = result[to.ToInt()];
    bool pop = true;
    if (to == from) {
      TRACE(("  xx %d\n", from.ToInt()));
      result[from.ToInt()] = from;
    } else if (to_to == unvisited()) {
      TRACE(("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt()));
      stack.push(to);
      result[to.ToInt()] = onstack();
      pop = false;  // recurse.
    } else if (to_to == onstack()) {
      TRACE(("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt()));
      result[from.ToInt()] = to;  // break the cycle.
      forwarded = true;
    } else {
      TRACE(("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt()));
      result[from.ToInt()] = to_to;  // forward the block.
      forwarded = true;
    }
    if (pop) stack.pop();
  }
  RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
  RpoNumber onstack() { return RpoNumber::FromInt(-2); }
};


bool JumpThreading::ComputeForwarding(Zone* local_zone,
                                      ZoneVector<RpoNumber>& result,
                                      InstructionSequence* code) {
  ZoneStack<RpoNumber> stack(local_zone);
  JumpThreadingState state = {false, result, stack};
  state.Clear(code->InstructionBlockCount());

  // Iterate over the blocks forward, pushing the blocks onto the stack.
  for (auto const block : code->instruction_blocks()) {
    RpoNumber current = block->rpo_number();
    state.PushIfUnvisited(current);

    // Process the stack, which implements DFS through empty blocks.
    while (!state.stack.empty()) {
      InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
      // Process the instructions in a block up to a non-empty instruction.
      TRACE(("jt [%d] B%d RPO%d\n", static_cast<int>(stack.size()),
             block->id().ToInt(), block->rpo_number().ToInt()));
      bool fallthru = true;
      RpoNumber fw = block->rpo_number();
      for (int i = block->code_start(); i < block->code_end(); ++i) {
        Instruction* instr = code->InstructionAt(i);
        if (instr->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) {
          // skip redundant gap moves.
          TRACE(("  nop gap\n"));
          continue;
        } else if (instr->IsSourcePosition()) {
          // skip source positions.
          TRACE(("  src pos\n"));
          continue;
        } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
          // can't skip instructions with flags continuations.
          TRACE(("  flags\n"));
          fallthru = false;
        } else if (instr->IsNop()) {
          // skip nops.
          TRACE(("  nop\n"));
          continue;
        } else if (instr->arch_opcode() == kArchJmp) {
          // try to forward the jump instruction.
          TRACE(("  jmp\n"));
          fw = code->InputRpo(instr, 0);
          fallthru = false;
        } else {
          // can't skip other instructions.
          TRACE(("  other\n"));
          fallthru = false;
        }
        break;
      }
      if (fallthru) {
        int next = 1 + block->rpo_number().ToInt();
        if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
      }
      state.Forward(fw);
    }
  }

#ifdef DEBUG
  for (RpoNumber num : result) {
    CHECK(num.IsValid());
  }
#endif

  if (FLAG_trace_turbo_jt) {
    for (int i = 0; i < static_cast<int>(result.size()); i++) {
      TRACE(("RPO%d B%d ", i,
             code->InstructionBlockAt(RpoNumber::FromInt(i))->id().ToInt()));
      int to = result[i].ToInt();
      if (i != to) {
        TRACE(("-> B%d\n",
               code->InstructionBlockAt(RpoNumber::FromInt(to))->id().ToInt()));
      } else {
        TRACE(("\n"));
      }
    }
  }

  return state.forwarded;
}


void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
                                    InstructionSequence* code) {
  if (!FLAG_turbo_jt) return;

  Zone local_zone(code->zone()->isolate());
  ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);

  // Skip empty blocks when the previous block doesn't fall through.
  bool prev_fallthru = true;
  for (auto const block : code->instruction_blocks()) {
    int block_num = block->rpo_number().ToInt();
    skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;

    bool fallthru = true;
    for (int i = block->code_start(); i < block->code_end(); ++i) {
      Instruction* instr = code->InstructionAt(i);
      if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
        fallthru = false;  // branches don't fall through to the next block.
      } else if (instr->arch_opcode() == kArchJmp) {
        if (skip[block_num]) {
          // Overwrite a redundant jump with a nop.
          TRACE(("jt-fw nop @%d\n", i));
          instr->OverwriteWithNop();
        }
        fallthru = false;  // jumps don't fall through to the next block.
      }
    }
    prev_fallthru = fallthru;
  }

  // Patch RPO immediates.
  InstructionSequence::Immediates& immediates = code->immediates();
  for (size_t i = 0; i < immediates.size(); i++) {
    Constant constant = immediates[i];
    if (constant.type() == Constant::kRpoNumber) {
      RpoNumber rpo = constant.ToRpoNumber();
      RpoNumber fw = result[rpo.ToInt()];
      if (!(fw == rpo)) immediates[i] = Constant(fw);
    }
  }

  // Recompute assembly order numbers.
  int ao = 0;
  for (auto const block : code->instruction_blocks()) {
    if (!block->IsDeferred()) {
      block->set_ao_number(RpoNumber::FromInt(ao));
      if (!skip[block->rpo_number().ToInt()]) ao++;
    }
  }
  for (auto const block : code->instruction_blocks()) {
    if (block->IsDeferred()) {
      block->set_ao_number(RpoNumber::FromInt(ao));
      if (!skip[block->rpo_number().ToInt()]) ao++;
    }
  }
}

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