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

namespace v8 {
namespace internal {
namespace compiler {

#define TRACE(...)                                \
  do {                                            \
    if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
  } while (false)

namespace {

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 IsBlockWithBranchPoisoning(InstructionSequence* code,
                                InstructionBlock* block) {
  if (block->PredecessorCount() != 1) return false;
  RpoNumber pred_rpo = (block->predecessors())[0];
  const InstructionBlock* pred = code->InstructionBlockAt(pred_rpo);
  if (pred->code_start() == pred->code_end()) return false;
  Instruction* instr = code->InstructionAt(pred->code_end() - 1);
  FlagsMode mode = FlagsModeField::decode(instr->opcode());
  return mode == kFlags_branch_and_poison;
}

}  // namespace

bool JumpThreading::ComputeForwarding(Zone* local_zone,
                                      ZoneVector<RpoNumber>* result,
                                      InstructionSequence* code,
                                      bool frame_at_start) {
  ZoneStack<RpoNumber> stack(local_zone);
  JumpThreadingState state = {false, *result, stack};
  state.Clear(code->InstructionBlockCount());
  RpoNumber empty_deconstruct_frame_return_block = RpoNumber::Invalid();
  int32_t empty_deconstruct_frame_return_size;
  RpoNumber empty_no_deconstruct_frame_return_block = RpoNumber::Invalid();
  int32_t empty_no_deconstruct_frame_return_size;

  // 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\n", static_cast<int>(stack.size()),
            block->rpo_number().ToInt());
      RpoNumber fw = block->rpo_number();
      if (!IsBlockWithBranchPoisoning(code, block)) {
        bool fallthru = true;
        for (int i = block->code_start(); i < block->code_end(); ++i) {
          Instruction* instr = code->InstructionAt(i);
          if (!instr->AreMovesRedundant()) {
            // can't skip instructions with non redundant moves.
            TRACE("  parallel move\n");
            fallthru = false;
          } 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");
            // if this block deconstructs the frame, we can't forward it.
            // TODO(mtrofin): we can still forward if we end up building
            // the frame at start. So we should move the decision of whether
            // to build a frame or not in the register allocator, and trickle it
            // here and to the code generator.
            if (frame_at_start || !(block->must_deconstruct_frame() ||
                                    block->must_construct_frame())) {
              fw = code->InputRpo(instr, 0);
            }
            fallthru = false;
          } else if (instr->IsRet()) {
            TRACE("  ret\n");
            if (fallthru) {
              CHECK_IMPLIES(block->must_construct_frame(),
                            block->must_deconstruct_frame());
              // Only handle returns with immediate/constant operands, since
              // they must always be the same for all returns in a function.
              // Dynamic return values might use different registers at
              // different return sites and therefore cannot be shared.
              if (instr->InputAt(0)->IsImmediate()) {
                int32_t return_size =
                    ImmediateOperand::cast(instr->InputAt(0))->inline_value();
                // Instructions can be shared only for blocks that share
                // the same |must_deconstruct_frame| attribute.
                if (block->must_deconstruct_frame()) {
                  if (empty_deconstruct_frame_return_block ==
                      RpoNumber::Invalid()) {
                    empty_deconstruct_frame_return_block = block->rpo_number();
                    empty_deconstruct_frame_return_size = return_size;
                  } else if (empty_deconstruct_frame_return_size ==
                             return_size) {
                    fw = empty_deconstruct_frame_return_block;
                    block->clear_must_deconstruct_frame();
                  }
                } else {
                  if (empty_no_deconstruct_frame_return_block ==
                      RpoNumber::Invalid()) {
                    empty_no_deconstruct_frame_return_block =
                        block->rpo_number();
                    empty_no_deconstruct_frame_return_size = return_size;
                  } else if (empty_no_deconstruct_frame_return_size ==
                             return_size) {
                    fw = empty_no_deconstruct_frame_return_block;
                  }
                }
              }
            }
            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) {
    DCHECK(num.IsValid());
  }
#endif

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

  return state.forwarded;
}

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

  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()) {
    RpoNumber block_rpo = block->rpo_number();
    int block_num = block_rpo.ToInt();
    RpoNumber result_rpo = result[block_num];
    skip[block_num] = !prev_fallthru && result_rpo != block_rpo;

    if (result_rpo != block_rpo) {
      // We need the handler information to be propagated, so that branch
      // targets are annotated as necessary for control flow integrity
      // checks (when enabled).
      if (code->InstructionBlockAt(block_rpo)->IsHandler()) {
        code->InstructionBlockAt(result_rpo)->MarkHandler();
      }
    }

    bool fallthru = true;
    for (int i = block->code_start(); i < block->code_end(); ++i) {
      Instruction* instr = code->InstructionAt(i);
      FlagsMode mode = FlagsModeField::decode(instr->opcode());
      if (mode == kFlags_branch || mode == kFlags_branch_and_poison) {
        fallthru = false;  // branches don't fall through to the next block.
      } else if (instr->arch_opcode() == kArchJmp ||
                 instr->arch_opcode() == kArchRet) {
        if (skip[block_num]) {
          // Overwrite a redundant jump with a nop.
          TRACE("jt-fw nop @%d\n", i);
          instr->OverwriteWithNop();
          // If this block was marked as a handler, it can be unmarked now.
          code->InstructionBlockAt(block_rpo)->UnmarkHandler();
        }
        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);
    }
  }

  // Renumber the blocks so that IsNextInAssemblyOrder() will return true,
  // even if there are skipped blocks in-between.
  int ao = 0;
  for (auto const block : code->ao_blocks()) {
    block->set_ao_number(RpoNumber::FromInt(ao));
    if (!skip[block->rpo_number().ToInt()]) ao++;
  }
}

#undef TRACE

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