CaptureAnalysis.cpp

Go to the documentation of this file.

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
 
#include "CaptureAnalysis.h"
#include "slang/ast/ASTVisitor.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/Support/SaveAndRestore.h"
 
using namespace slang::ast;
using namespace circt;
using namespace circt::ImportVerilog;
 
/// Check whether `var` is local to `func`. Walk up from the variable's parent
/// scope; if we reach `func` before hitting another function boundary, the
/// variable is local.
static bool isLocalToFunction(const ValueSymbol &var,
                              const SubroutineSymbol &func) {
  for (const Scope *scope = var.getParentScope(); scope;
       scope = scope->asSymbol().getParentScope()) {
    if (&scope->asSymbol() == &func)
      return true;
    if (scope->asSymbol().kind == SymbolKind::Subroutine)
      return false;
  }
  return false;
}
 
/// Workaround for a slang deficiency: when accessing a member of a virtual
/// interface (e.g., `vif.data`), slang resolves the entire dotted path during
/// name lookup and produces a `NamedValueExpression` that directly references
/// the signal symbol inside the interface's `InstanceBody`. Unlike struct
/// fields and class properties, which produce a `MemberAccessExpression`, there
/// is no syntactic indication on the expression that this was a member
/// projection.
///
/// This check matches variables that live inside an interface instance body.
/// A `NamedValueExpression` referencing such a symbol is the result of slang's
/// virtual interface member resolution, not a genuine variable capture. This is
/// expected to be fixed upstream in slang.
///
/// See https://github.com/MikePopoloski/slang/discussions/1770
static bool isVirtualInterfaceMemberAccess(const ValueSymbol &var) {
  // Walk up from the variable to find the nearest enclosing InstanceBody.
  for (const Scope *scope = var.getParentScope(); scope;
       scope = scope->asSymbol().getParentScope()) {
    auto *body = scope->asSymbol().as_if<InstanceBodySymbol>();
    if (!body)
      continue;
    return body->getDefinition().definitionKind == DefinitionKind::Interface;
  }
  return false;
}
 
/// Check whether `var` is a global variable. Walk up from the variable's parent
/// scope; if we hit a function or instance body, it's not global. Otherwise
/// (package, compilation unit, root) it is.
static bool isGlobalVariable(const ValueSymbol &var) {
  for (const Scope *scope = var.getParentScope(); scope;
       scope = scope->asSymbol().getParentScope()) {
    switch (scope->asSymbol().kind) {
    case SymbolKind::Subroutine:
    case SymbolKind::InstanceBody:
      return false;
    default:
      break;
    }
  }
  return true;
}
 
bool circt::ImportVerilog::isCompileTimeConstant(SymbolKind kind) {
  return kind == SymbolKind::Parameter || kind == SymbolKind::EnumValue ||
         kind == SymbolKind::Genvar || kind == SymbolKind::Specparam;
}
 
const InstanceSymbol *
circt::ImportVerilog::getRootInstance(const HierarchicalReference &ref) {
  for (auto &elem : ref.path)
    if (auto *inst = elem.symbol->as_if<InstanceSymbol>())
      return inst;
  return nullptr;
}
 
namespace {
 
/// Walk the entire AST to collect captured variables and the call graph for
/// each function. Uses slang's `ASTVisitor` with both statement and expression
/// visiting enabled so that we recurse into all function bodies.
struct CaptureWalker
    : public ASTVisitor<CaptureWalker, VisitFlags::AllCanonical> {
 
  /// The function whose body we are currently inside, or nullptr if we are at
  /// a scope outside any function.
  const SubroutineSymbol *currentFunc = nullptr;
 
  /// Captured variables per function.
  CaptureMap capturedVars;
 
  mlir::DenseSet<const InstanceBodySymbol *> visitedInstanceBodies;
 
  /// Inverse call graph: maps each callee to the set of callers that call it.
  /// Used to propagate captures from callees to their callers. Uses MapVector
  /// for deterministic iteration order during propagation.
  MapVector<const SubroutineSymbol *,
            SmallSetVector<const SubroutineSymbol *, 4>>
      callers;
 
  /// For each (function, captured symbol) pair, the instance through wich
  /// the hierarchical reference was first reached. Used to detect captures
  /// that resolve to one symbol through several instances.
  DenseMap<std::pair<const SubroutineSymbol *, const ValueSymbol *>,
           const InstanceSymbol *>
      hierCaptureRootInstance;
 
  /// Captures that were reached through more than one instance reported as
  /// errors since they cannot be wired to a single instance.
  SmallVector<AmbiguousHierCapture> ambiguousHierCaptures;
 
  /// Track which root instance each hierarchical capture was reached through;
  /// the same symbol seen through two different instances is ambiguous.
  void noteHierCapture(const SubroutineSymbol &func, const ValueSymbol &var,
                       const InstanceSymbol *rootInst) {
    if (!rootInst)
      return;
    auto key = std::make_pair(&func, &var);
    auto [it, inserted] = hierCaptureRootInstance.try_emplace(key, rootInst);
    if (!inserted && it->second != rootInst)
      ambiguousHierCaptures.push_back({&func, &var});
  }
 
  /// When we enter a function body, record it as the current function and
  /// recurse into its members and body statements.
  void handle(const SubroutineSymbol &func) {
    llvm::SaveAndRestore guard(currentFunc, &func);
    visitDefault(func);
  }
 
  /// When we see a named value reference inside a function, check if it needs
  /// to be captured.
  void handle(const NamedValueExpression &expr) {
    if (!currentFunc)
      return;
 
    auto &var = expr.symbol;
 
    // Class properties are accessed through `this`, not captured.
    if (var.kind == SymbolKind::ClassProperty)
      return;
 
    // Function arguments are local by definition.
    if (var.kind == SymbolKind::FormalArgument)
      return;
 
    if (isCompileTimeConstant(var.kind))
      return;
 
    // Only capture variables that are non-local and non-global.
    if (isLocalToFunction(var, *currentFunc) || isGlobalVariable(var))
      return;
 
    // Work around a slang deficiency where virtual interface member accesses
    // are resolved to NamedValueExpressions referencing symbols inside the
    // interface's instance body, indistinguishable from direct variable
    // references. See isVirtualInterfaceMemberAccess for details.
    if (isVirtualInterfaceMemberAccess(var))
      return;
 
    capturedVars[currentFunc].insert(&var);
  }
 
  /// Hierarchical references (`inst.var`) are captured like ordinary
  /// non-local variables. Interface-port references are excluded: they are
  /// handled by the interface lowering machinery, not as captures.
  void handle(const HierarchicalValueExpression &expr) {
    if (!currentFunc)
      return;
    if (expr.ref.isViaIfacePort())
      return;
    auto &var = expr.symbol;
    if (isCompileTimeConstant(var.kind))
      return;
    noteHierCapture(*currentFunc, var, getRootInstance(expr.ref));
    capturedVars[currentFunc].insert(&var);
  }
 
  /// Record call graph edges when we see a function call.
  void handle(const CallExpression &expr) {
    if (currentFunc)
      if (auto *const *callee =
              std::get_if<const SubroutineSymbol *>(&expr.subroutine))
        callers[*callee].insert(currentFunc);
    visitDefault(expr);
  }
 
  /// `VisitCanonical` is set above, so this visits the canonical instance body
  /// if there is one. If there is and we've already visited it via some
  /// other instance, don't process it again.
  void handle(const InstanceBodySymbol &instance) {
    if (visitedInstanceBodies.insert(&instance).second) {
      visitDefault(instance);
    }
  }
 
  /// Propagate captures transitively through the call graph. For each callee
  /// that has captures, push each captured variable upward through all
  /// transitive callers using a worklist. A captured variable is only
  /// propagated to a caller if it is not local to that caller.
  void propagateCaptures() {
    using WorkItem = std::pair<const SubroutineSymbol *, const ValueSymbol *>;
    SmallSetVector<WorkItem, 16> worklist;
 
    for (auto &[func, _] : callers) {
      // Check if this function captures any variables. Nothing to do if it
      // doesn't.
      auto it = capturedVars.find(func);
      if (it == capturedVars.end())
        continue;
 
      // Prime the worklist with the captured variables.
      for (auto *var : it->second)
        worklist.insert({func, var});
 
      // Push each captured variables to the func's callers transitively.
      while (!worklist.empty()) {
        auto [func, cap] = worklist.pop_back_val();
        auto callersIt = callers.find(func);
        if (callersIt == callers.end())
          continue;
        for (auto *caller : callersIt->second) {
          if (!isLocalToFunction(*cap, *caller)) {
            noteHierCapture(*caller, *cap,
                            hierCaptureRootInstance.lookup({func, cap}));
            if (capturedVars[caller].insert(cap))
              worklist.insert({caller, cap});
          }
        }
      }
    }
  }
};
 
} // namespace
 
CaptureMap ImportVerilog::analyzeFunctionCaptures(
    const RootSymbol &root, SmallVectorImpl<AmbiguousHierCapture> &ambiguous) {
  CaptureWalker walker;
  root.visit(walker);
  walker.propagateCaptures();
  ambiguous.assign(walker.ambiguousHierCaptures.begin(),
                   walker.ambiguousHierCaptures.end());
  return std::move(walker.capturedVars);
}