// Copyright 2026 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 "irregexp/imported/regexp-bytecode-analysis.h"

#include <utility>

#include "irregexp/imported/regexp-bytecode-iterator-inl.h"
#include "irregexp/imported/regexp-bytecodes-inl.h"
#include "irregexp/imported/regexp-bytecodes.h"

namespace v8 {
namespace internal {
namespace regexp {

BytecodeAnalysis::BytecodeAnalysis(Isolate* isolate, Zone* zone,
                                   DirectHandle<TrustedByteArray> bytecode)
    : zone_(zone),
      bytecode_(*bytecode, isolate),
      length_(bytecode->ulength().value()),
      offset_to_prev_bytecode_(bytecode->ulength().value() + kSlotAtLength, 0,
                               zone),
      backtrack_targets_(zone),
      block_starts_(zone),
      offset_to_block_id_(length_, -1, zone),
      offset_to_ebb_id_(length_, -1, zone),
      predecessors_(zone),
      loops_(zone),
      is_loop_header_(0, zone),
      is_back_edge_(length_, zone),
      uses_current_char_(0, zone),
      loads_current_char_(0, zone) {}

void BytecodeAnalysis::Analyze() {
  // TODO(jgruber): Analysis passes need to be optimized before being used in
  // production. We are quite wasteful currently.
  FindBasicBlocks();
  AnalyzeControlFlow();
  AnalyzeDataFlow();
}

void BytecodeAnalysis::PrintBlock(uint32_t block_id) {
  const char* kGrey = "\e[0;32m";
  const char* kReset = "\033[0m";
  const char* prefix = "-- ";

  const uint32_t block_start = BlockStart(block_id);
  PrintF("%s%sb%02d, ebb%02d, [%x,%x), attrs {", kGrey, prefix, block_id,
         GetEbbId(block_start), block_start, BlockEnd(block_id));
  if (IsLoopHeader(block_id)) PrintF(" header");
  if (UsesCurrentChar(block_id)) PrintF(" use_cc");
  if (LoadsCurrentChar(block_id)) PrintF(" load_cc");

  {
    PrintF("}, pred {");
    bool printed_first = false;
    for (uint32_t pred : predecessors_[block_id]) {
      PrintF("%sb%02d", printed_first ? "," : "", pred);
      printed_first = true;
    }
  }
  {
    PrintF("}, succ {");
    bool printed_first = false;
    ForEachSuccessor(
        block_id,
        [&](uint32_t successor, uint32_t jump_offset, bool is_backtrack) {
          PrintF("%sb%02d", printed_first ? "," : "", successor);
          printed_first = true;
          if (IsBackEdge(jump_offset)) PrintF(" backedge");
        },
        true);
  }
  {
    // Loop membership.
    PrintF("}, loops {");
    bool printed_first = false;
    for (const auto& loop : loops_) {
      if (!loop.members.Contains(block_id)) continue;
      PrintF("%sb%02d", printed_first ? "," : "", loop.header_block_id);
      printed_first = true;
      for (const auto& exit : loop.exits) {
        if (exit.first == block_id) {
          PrintF(" exit");
          break;
        }
      }
    }
    PrintF("}");
  }
  PrintF("%s\n", kReset);

  // Loop headers have one addtl line with infos:
  if (IsLoopHeader(block_id)) {
    for (const auto& loop : loops_) {
      if (loop.header_block_id == block_id) {
        PrintF("%s%s  loop members {", kGrey, prefix);
        for (int member : loop.members) {
          PrintF(" b%02d", member);
        }
        PrintF("} exits {");
        for (const auto& exit : loop.exits) {
          PrintF(" b%02d->b%02d", exit.first, exit.second);
        }
        PrintF("}%s\n", kReset);
      }
    }
  }
}

uint32_t BytecodeAnalysis::GetBlockId(uint32_t bytecode_offset) const {
  DCHECK_LT(bytecode_offset, length_);
  int id = offset_to_block_id_[bytecode_offset];
  DCHECK_GE(id, 0);
  return static_cast<uint32_t>(id);
}

int BytecodeAnalysis::GetEbbId(uint32_t bytecode_offset) const {
  DCHECK_LT(bytecode_offset, length_);
  // Can be uninitialized for dead code so negative ids are valid.
  return offset_to_ebb_id_[bytecode_offset];
}

uint32_t BytecodeAnalysis::BlockStart(uint32_t block_id) const {
  DCHECK_LT(block_id, block_count());
  return block_starts_[block_id];
}

uint32_t BytecodeAnalysis::BlockEnd(uint32_t block_id) const {
  DCHECK_LT(block_id, block_count());
  return block_starts_[block_id + 1];
}

bool BytecodeAnalysis::IsLoopHeader(uint32_t block_id) const {
  return is_loop_header_.Contains(block_id);
}

bool BytecodeAnalysis::IsBackEdge(uint32_t bytecode_offset) const {
  return is_back_edge_.Contains(bytecode_offset);
}

void BytecodeAnalysis::FindBasicBlocks() {
  // Potential optimizations
  // * Simple xmm reg allocation, with constant hoisting.
  //   * Only do this if the code actually uses the xmm regs.
  //   * Careful around caller-saved xmms (for outgoing calls) and callee-saved
  //     for returns.
  // * Push callee-saved xmm regs in the prologue,epilogue, and when calling to
  //   C.
  // * Simdify much smaller chunks, e.g. AndCheck4Chars. But: reloading the
  //   current string into vector regs is expensive.
  //   The ..Masked optimization is hard to beat because it implicitly assumes
  //   that it's okay to be a bit fuzzy wrt fast simd candidate location - the
  //   scalar suffix will filter out bad matches.
  // * Load elimination. We could always load 8/4 byte chunks and eliminate
  //   following LoadCurrentCharacter with cp_offset inside this range. Loop
  //   unrolling could create more opportunities. Comparison ops would have to
  //   be updated to mask appropriately.
  // * Fold the repeated Load1-Check1 sequence.
  //    * EBB analysis.
  //    * Single use for each of the char loads.
  //    * cp_offset is (almost) consecutive.
  //    * The uses are all CheckFoo where Foo is the same in all uses (modulo
  //      Not), and the jump target is the same.
  // * Dead code elimination.
  // * Backtrack elimination (if only one backtrack target exists)
  //    * Remove all pushbacktracks.
  //    * Replace kBacktrack by Goto.
  // * Likewise, if the Backtrack bytecode is dead.
  // * Regexp stack check elimination (Extended Basic Blocks).
  // * Align loop headers.

  // Pass 1: Identify leaders.
  // A leader is:
  // 1. The first instruction (offset 0).
  // 2. The target of any jump.
  // 3. The instruction following a terminator.

  BitVector leaders(length_ + kSlotAtLength, zone_);
  leaders.Add(0);

  uint32_t prev_offset = 0;
  for (BytecodeIterator it(bytecode_); !it.done(); it.advance()) {
    const Bytecode bytecode = it.current_bytecode();
    const BytecodeFlags flags = Bytecodes::Flags(bytecode);
    const uint32_t current_offset = it.current_offset();
    const uint32_t next_offset = current_offset + Bytecodes::Size(bytecode);

    const bool is_fallthrough = (flags & ReBcFlag::kNoFallthrough) == 0;
    bool treat_as_fallthrough = is_fallthrough;

    // Gather offsets for backward walks.
    DCHECK(current_offset > prev_offset || current_offset == 0);
    DCHECK(is_uint8(current_offset - prev_offset));
    offset_to_prev_bytecode_[current_offset] = current_offset - prev_offset;
    prev_offset = current_offset;

    // Gather jump targets.
    bool has_jumptarget_operand = false;
    bool has_nontrivial_jumptarget = false;
    Bytecodes::DispatchOnBytecode(bytecode, [&]<Bytecode bc>() {
      using Operands = BytecodeOperands<bc>;
      Operands::ForEachOperand([&]<auto op>() {
        if constexpr (Operands::Type(op) == BytecodeOperandType::kJumpTarget) {
          uint32_t target =
              Operands::template Get<op>(it.current_address(), no_gc_);
          DCHECK_LT(target, length_);
          if constexpr (bc == Bytecode::kPushBacktrack) {
            // The target is pushed to the stack, not branched to.
            backtrack_targets_.push_back(target);
            leaders.Add(target);
            return;
          }
          has_jumptarget_operand = true;
          if (target == next_offset) {
            treat_as_fallthrough = true;
            return;
          }
          has_nontrivial_jumptarget = true;
          leaders.Add(target);
        }
      });
    });

    if (treat_as_fallthrough && has_nontrivial_jumptarget) {
      // Bytecodes that have multiple targets terminate the block.
      leaders.Add(next_offset);
    } else if (!treat_as_fallthrough) {
      // Bytecodes that don't fallthrough terminate the block.
      leaders.Add(next_offset);
    } else {
      // Execution always resumes at the next bytecode.
      DCHECK(treat_as_fallthrough && !has_nontrivial_jumptarget);
    }
  }

  // And for backwards walks from the end:
  DCHECK_GT(length_, prev_offset);
  DCHECK(is_uint8(length_ - prev_offset));
  offset_to_prev_bytecode_[length_] = length_ - prev_offset;

  // Pass 2: Create blocks.
  for (uint32_t leader : leaders) {
    block_starts_.push_back(leader);
  }

  // Pass 3: Map offsets to block IDs.
  uint32_t current_block_id = 0;
  uint32_t next_block_start = block_starts_[current_block_id + 1];
  for (uint32_t pc = 0; pc < length_; ++pc) {
    if (pc == next_block_start) {
      current_block_id++;
      next_block_start = block_starts_[current_block_id + 1];
      DCHECK_GT(next_block_start, pc);
    }
    offset_to_block_id_[pc] = current_block_id;
  }
}

template <typename Callback>
void BytecodeAnalysis::ForEachSuccessor(uint32_t block_id, Callback callback,
                                        bool include_backtrack) {
  uint32_t end = BlockEnd(block_id);
  DCHECK_GT(offset_to_prev_bytecode_[end], 0);
  DCHECK_GE(end, offset_to_prev_bytecode_[end]);
  uint32_t current_offset = end - offset_to_prev_bytecode_[end];

  // To find successors, we only need to look at the last instruction of the
  // block.

  BytecodeIterator iterator(bytecode_, current_offset);
  Bytecode bytecode = iterator.current_bytecode();

  // Backtrack may jump to any backtrack target.
  if (bytecode == Bytecode::kBacktrack) {
    if (include_backtrack) {
      for (uint32_t target : backtrack_targets_) {
        callback(GetBlockId(target), current_offset, true);
      }
    }
    return;
  }

  const BytecodeFlags flags = Bytecodes::Flags(bytecode);
  const bool may_branch =
      (flags & ReBcFlag::kNoBranchDespiteJumpTargetOperand) == 0;
  const bool is_fallthrough = (flags & ReBcFlag::kNoFallthrough) == 0;

  if (may_branch) {
    Bytecodes::DispatchOnBytecode(bytecode, [&]<Bytecode bc>() {
      using Operands = BytecodeOperands<bc>;
      Operands::ForEachOperand([&]<auto op>() {
        if constexpr (Operands::Type(op) == BytecodeOperandType::kJumpTarget) {
          uint32_t target =
              Operands::template Get<op>(iterator.current_address(), no_gc_);
          CHECK_LT(target, length_);
          // TODO(jgruber): Maybe we also want to store the offset of the
          // current operand.
          callback(GetBlockId(target), current_offset, false);
        }
      });
    });
  }

  if (is_fallthrough && end < length_) {
    callback(GetBlockId(end), current_offset, false);
  }
}

void BytecodeAnalysis::AnalyzeControlFlow() {
  const uint32_t num_blocks = block_count();

  predecessors_.assign(num_blocks, ZoneSet<int>(zone_));
  is_loop_header_.Resize(num_blocks, zone_);

  BitVector visited(num_blocks, zone_);
  BitVector recursion_stack(num_blocks, zone_);
  ZoneVector<std::pair<uint32_t, uint32_t>> back_edges(zone_);

  struct Frame {
    uint32_t block_id;
    int ebb_id;
    bool successors_visited;
  };

  ZoneStack<Frame> dfs_stack(zone_);
  dfs_stack.push({0, 0, false});

  while (!dfs_stack.empty()) {
    Frame& frame = dfs_stack.top();
    const uint32_t u = frame.block_id;

    if (frame.successors_visited) {
      // Post-order.
      recursion_stack.Remove(u);
      dfs_stack.pop();
      continue;
    }

    if (visited.Contains(u)) {
      dfs_stack.pop();
      continue;
    }

    // Pre-order.
    visited.Add(u);
    recursion_stack.Add(u);
    frame.successors_visited = true;

    ForEachSuccessor(
        u,
        [&](uint32_t v, uint32_t jump_offset, bool is_backtrack) {
          predecessors_[v].emplace(u);
          if (!is_backtrack && recursion_stack.Contains(v)) {
            // Back-edge detected.
            is_loop_header_.Add(v);
            is_back_edge_.Add(jump_offset);
            back_edges.push_back({u, v});
          } else if (!visited.Contains(v)) {
            dfs_stack.push({v, 0, false});
          }
        },
        true);
  }

  // Now that we have information about predecessors, find extended basic
  // blocks.
  visited.Clear();
  int next_ebb_id = 0;
  offset_to_ebb_id_[0] = next_ebb_id;
  dfs_stack.push({0, next_ebb_id++, false});

  while (!dfs_stack.empty()) {
    Frame frame = dfs_stack.top();
    dfs_stack.pop();

    const uint32_t u = frame.block_id;
    if (visited.Contains(u)) {
      continue;
    }

    visited.Add(u);

    ForEachSuccessor(
        u,
        [&](uint32_t v, uint32_t jump_offset, bool is_backtrack) {
          if (visited.Contains(v)) return;
          int ebb_id = GetEbbId(BlockStart(v));
          if (ebb_id == -1) {
            ebb_id = frame.ebb_id;
            if (predecessors_[v].size() > 1 || is_backtrack) {
              ebb_id = next_ebb_id++;
            }

            // Only record at block start.
            offset_to_ebb_id_[BlockStart(v)] = ebb_id;
          }
          dfs_stack.push({v, ebb_id, false});
        },
        true);
  }

  ComputeLoops(back_edges);
}

void BytecodeAnalysis::ComputeLoops(
    const ZoneVector<std::pair<uint32_t, uint32_t>>& back_edges) {
  uint32_t num_blocks = block_count();

  for (const auto& edge : back_edges) {
    uint32_t header = edge.second;
    uint32_t latch = edge.first;

    // Find or create loop info for this header.
    // TODO(jgruber): not linear search. BlockInfo could point at LoopInfo.
    LoopInfo* loop = nullptr;
    for (auto& l : loops_) {
      if (l.header_block_id == header) {
        loop = &l;
        break;
      }
    }
    if (loop == nullptr) {
      loops_.emplace_back(header, num_blocks, zone_);
      loop = &loops_.back();
      loop->members.Add(header);
    }

    // Add blocks to loop body by walking backwards from latch to header.
    ZoneVector<uint32_t> worklist(zone_);
    worklist.push_back(latch);
    loop->members.Add(latch);

    while (!worklist.empty()) {
      uint32_t block = worklist.back();
      worklist.pop_back();

      if (block == header) continue;

      for (uint32_t pred : predecessors_[block]) {
        if (!loop->members.Contains(pred)) {
          loop->members.Add(pred);
          worklist.push_back(pred);
        }
      }
    }
  }

  // Compute loop exits now that loop infos are complete.
  for (auto& loop : loops_) {
    for (uint32_t block : loop.members) {
      ForEachSuccessor(
          block,
          [&](uint32_t successor, uint32_t jump_offset, bool is_backtrack) {
            if (!loop.members.Contains(successor)) {
              loop.exits.push_back({block, successor});
            }
          },
          true);
    }
  }
}

bool BytecodeAnalysis::UsesCurrentChar(uint32_t block_id) const {
  return uses_current_char_.Contains(block_id);
}

bool BytecodeAnalysis::LoadsCurrentChar(uint32_t block_id) const {
  return loads_current_char_.Contains(block_id);
}

void BytecodeAnalysis::AnalyzeDataFlow() {
  uint32_t num_blocks = block_count();
  uses_current_char_.Resize(num_blocks, zone_);
  loads_current_char_.Resize(num_blocks, zone_);

  // Annotate blocks for current_character usage. A block "uses"
  // current_character if any use exists before a load in the same block; any
  // uses after a local load are not counted.

  for (uint32_t block_id = 0; block_id < num_blocks; ++block_id) {
    uint32_t start = BlockStart(block_id);
    uint32_t end = BlockEnd(block_id);

    BytecodeIterator iterator(bytecode_, start);
    bool locally_loaded = false;

    while (iterator.current_offset() < end) {
      Bytecode bytecode = iterator.current_bytecode();

      const BytecodeFlags flags = Bytecodes::Flags(bytecode);
      const bool loads = (flags & ReBcFlag::kLoadsCC) != 0;
      const bool uses = (flags & ReBcFlag::kUsesCC) != 0;

      if (uses && !locally_loaded) {
        uses_current_char_.Add(block_id);
      }
      if (loads) {
        loads_current_char_.Add(block_id);
        locally_loaded = true;
      }

      iterator.advance();
    }
  }
}

}  // namespace regexp
}  // namespace internal
}  // namespace v8