// 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 <algorithm>
#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()),
      backtrack_targets_(zone),
      block_starts_(zone),
      block_to_ebb_id_(zone),
      successors_(zone),
      predecessors_(zone),
      loops_(zone),
      is_loop_header_(0, zone),
      uses_current_char_(0, zone),
      loads_current_char_(0, zone),
      terminates_with_backtrack_(0, zone),
      back_edges_(zone) {}

void BytecodeAnalysis::Analyze() {
  BuildBlocks();
  AnalyzeControlFlow();
}

void BytecodeAnalysis::PrintBlock(uint32_t block_id) {
  if (block_id == backtrack_dispatch_id()) return;

  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_id), 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]) {
      if (pred == backtrack_dispatch_id()) {
        PrintF("%sdispatch", printed_first ? "," : "");
      } else {
        PrintF("%sb%02d", printed_first ? "," : "", pred);
      }
      printed_first = true;
    }
  }
  {
    PrintF("}, succ {");
    bool printed_first = false;
    for (uint32_t successor : successors_[block_id]) {
      if (successor == backtrack_dispatch_id()) {
        PrintF("%sdispatch", printed_first ? "," : "");
      } else {
        PrintF("%sb%02d", printed_first ? "," : "", successor);
      }
      printed_first = true;
      if (std::find(back_edges_.begin(), back_edges_.end(),
                    std::pair<uint32_t, uint32_t>{block_id, successor}) !=
          back_edges_.end()) {
        PrintF(" backedge");
      }
    }
  }
  {
    // 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) {
          if (member == static_cast<int>(backtrack_dispatch_id())) {
            PrintF(" dispatch");
          } else {
            PrintF(" b%02d", member);
          }
        }
        PrintF("} exits {");
        for (const auto& exit : loop.exits) {
          if (exit.first == backtrack_dispatch_id()) {
            PrintF(" dispatch->b%02d", exit.second);
          } else if (exit.second == backtrack_dispatch_id()) {
            PrintF(" b%02d->dispatch", exit.first);
          } else {
            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_);
  auto it = std::upper_bound(block_starts_.begin(), block_starts_.end(),
                             bytecode_offset);
  DCHECK(it != block_starts_.begin());
  return static_cast<uint32_t>(std::distance(block_starts_.begin(), it) - 1);
}

int BytecodeAnalysis::GetEbbId(uint32_t block_id) const {
  DCHECK_LT(block_id, total_block_count());
  return block_to_ebb_id_[block_id];
}

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::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::BuildBlocks() {
  // 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.
  //
  // This phase collects all bytecode offsets that start a new basic block.

  ZoneVector<uint32_t> leaders(zone_);
  leaders.push_back(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;

    // Collect jump targets. Some bytecodes (like kPushBacktrack) don't
    // immediately branch, but their target will eventually be a leader.
    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) {
            backtrack_targets_.push_back(target);
            leaders.push_back(target);
            return;
          }
          if (target == next_offset) {
            treat_as_fallthrough = true;
            return;
          }
          has_nontrivial_jumptarget = true;
          leaders.push_back(target);
        }
      });
    });

    // If we have a jump target AND can fall through, the fall-through must
    // start a new block. Similarly, if we cannot fall through, the next
    // instruction starts a new block.
    if (treat_as_fallthrough && has_nontrivial_jumptarget) {
      leaders.push_back(next_offset);
    } else if (!treat_as_fallthrough) {
      leaders.push_back(next_offset);
    }
  }

  // Finalize block boundaries. We sort and unique the leaders to get a clean
  // list of block starts.
  leaders.push_back(length_);
  std::sort(leaders.begin(), leaders.end());
  leaders.erase(std::unique(leaders.begin(), leaders.end()), leaders.end());
  block_starts_ = std::move(leaders);

  const uint32_t num_blocks = block_count();
  const uint32_t total_blocks = total_block_count();

  // Initialize data structures for the graph.
  successors_.assign(total_blocks, ZoneVector<uint32_t>(zone_));
  predecessors_.assign(total_blocks, ZoneVector<uint32_t>(zone_));
  uses_current_char_.Resize(total_blocks, zone_);
  loads_current_char_.Resize(total_blocks, zone_);
  terminates_with_backtrack_.Resize(total_blocks, zone_);

  // Backtrack canonicalization: instead of edges from every 'Backtrack' site
  // to every 'PushBacktrack' target, we create a single backtrack dispatch
  // node. All 'Backtrack' sites point to it, and it points to all unique
  // target blocks.
  ZoneVector<uint32_t> backtrack_target_blocks(zone_);
  for (uint32_t target : backtrack_targets_) {
    backtrack_target_blocks.push_back(GetBlockId(target));
  }
  std::sort(backtrack_target_blocks.begin(), backtrack_target_blocks.end());
  backtrack_target_blocks.erase(std::unique(backtrack_target_blocks.begin(),
                                            backtrack_target_blocks.end()),
                                backtrack_target_blocks.end());

  successors_[backtrack_dispatch_id()] = backtrack_target_blocks;

  // Pass 2: Construct edges and annotate data-flow properties.
  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 it(bytecode_, start);
    bool locally_loaded = false;

    // 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 because they
    // consume the locally loaded value.
    while (it.current_offset() < end) {
      Bytecode bytecode = it.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;
      }

      const uint8_t* current_address = it.current_address();
      it.advance();

      // Only the last instruction of a block can have non-fallthrough
      // successors.
      if (it.current_offset() == end) {
        if (bytecode == Bytecode::kBacktrack) {
          terminates_with_backtrack_.Add(block_id);
          successors_[block_id].push_back(backtrack_dispatch_id());
        } else {
          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::template ForEachOperandOfType<
                  BytecodeOperandType::kJumpTarget>([&]<auto op>() {
                uint32_t target =
                    Operands::template Get<op>(current_address, no_gc_);
                successors_[block_id].push_back(GetBlockId(target));
              });
            });
          }

          if (is_fallthrough && end < length_) {
            successors_[block_id].push_back(GetBlockId(end));
          }
        }
      }
    }

    // Sort and unique successors to ensure clean adjacency lists.
    auto& succs = successors_[block_id];
    std::sort(succs.begin(), succs.end());
    succs.erase(std::unique(succs.begin(), succs.end()), succs.end());

    // Build predecessors from successors.
    for (uint32_t succ : succs) {
      predecessors_[succ].push_back(block_id);
    }
  }

  // Predecessors for the backtrack dispatch node's targets.
  auto& dispatch_succs = successors_[backtrack_dispatch_id()];
  for (uint32_t succ : dispatch_succs) {
    predecessors_[succ].push_back(backtrack_dispatch_id());
  }

  // Finalize predecessors by sorting and uniquing.
  for (uint32_t block_id = 0; block_id < total_blocks; ++block_id) {
    auto& preds = predecessors_[block_id];
    std::sort(preds.begin(), preds.end());
    preds.erase(std::unique(preds.begin(), preds.end()), preds.end());
  }
}

void BytecodeAnalysis::AnalyzeControlFlow() {
  const uint32_t total_blocks = total_block_count();

  is_loop_header_.Resize(total_blocks, zone_);
  block_to_ebb_id_.assign(total_blocks, -1);

  BitVector visited(total_blocks, zone_);
  BitVector recursion_stack(total_blocks, zone_);

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

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

  // Iterative DFS for loop detection and reachability.
  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;

    for (uint32_t v : successors_[u]) {
      // Edges involving the backtrack dispatch node are not real
      // control flow — they model the runtime backtrack stack, not loops.
      bool is_backtrack_edge =
          u == backtrack_dispatch_id() || v == backtrack_dispatch_id();
      if (!is_backtrack_edge && recursion_stack.Contains(v)) {
        is_loop_header_.Add(v);
        back_edges_.push_back({u, v});
      } else if (!visited.Contains(v)) {
        dfs_stack.push({v, 0, false});
      }
    }
  }

  // Extended Basic Block (EBB) identification.
  // An EBB starts at:
  // 1. The entry block (0).
  // 2. Any block with multiple predecessors.
  // 3. Any block that is the target of a backtrack edge.
  visited.Clear();
  int next_ebb_id = 0;
  block_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);

    for (uint32_t v : successors_[u]) {
      if (visited.Contains(v)) continue;

      int ebb_id = block_to_ebb_id_[v];
      if (ebb_id == -1) {
        ebb_id = frame.ebb_id;
        bool is_backtrack_edge =
            u == backtrack_dispatch_id() || v == backtrack_dispatch_id();
        if (predecessors_[v].size() > 1 || is_backtrack_edge) {
          ebb_id = next_ebb_id++;
        }
        block_to_ebb_id_[v] = ebb_id;
      }
      dfs_stack.push({v, ebb_id, false});
    }
  }

  // Loop member identification.
  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, total_blocks, zone_);
      loop = &loops_.back();
      loop->members.Add(header);
    }

    // Add blocks to loop body by walking backwards from latch to header
    // using the predecessor edges.
    if (!loop->members.Contains(latch)) {
      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) {
      for (uint32_t successor : successors_[block]) {
        if (!loop.members.Contains(successor)) {
          loop.exits.push_back({block, successor});
        }
      }
    }
  }
}

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