CallGraphAnalyses.cpp

Go to the documentation of this file.

//===-- CallGraphAnalyses.cpp -----------------------------------*- C++ -*-===//
//
// Part of the LLZK Project, under the Apache License v2.0.
// See LICENSE.txt for license information.
// Copyright 2025 Veridise Inc.
// SPDX-License-Identifier: Apache-2.0
//
// The contents of this file are adapted from llvm/lib/Analysis/CallGraph.cpp.
// 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 "llzk/Analysis/CallGraphAnalyses.h"
 
#include "llzk/Dialect/Function/IR/Ops.h"
 
#include <mlir/Interfaces/CallInterfaces.h>
 
#include <llvm/ADT/DepthFirstIterator.h>
#include <llvm/ADT/SmallVector.h>
#include <llvm/Support/ErrorHandling.h>
 
namespace llzk {
 
using namespace function;
 
CallGraphAnalysis::CallGraphAnalysis(mlir::Operation *op) : cg(nullptr) {
  if (auto modOp = llvm::dyn_cast<mlir::ModuleOp>(op)) {
    cg = std::make_unique<llzk::CallGraph>(modOp);
  } else {
    const char *error_message = "CallGraphAnalysis expects provided op to be a ModuleOp!";
    op->emitError(error_message).report();
    llvm::report_fatal_error(error_message);
  }
}

CallGraphReachabilityAnalysis::CallGraphReachabilityAnalysis(
    mlir::Operation *, mlir::AnalysisManager &am
)
    // getting the CallGraphAnalysis will enforce the need for a module op
    : callGraph(am.getAnalysis<CallGraphAnalysis>().getCallGraph()) {}
 
bool CallGraphReachabilityAnalysis::isReachable(
    mlir::CallableOpInterface A, mlir::CallableOpInterface B
) const {
  if (isReachableCached(A, B)) {
    return true;
  }
 
  auto *startNode = callGraph.get().lookupNode(A.getCallableRegion());
  if (!startNode) {
    const char *msg = "CallGraph contains no starting node!";
    A.emitError(msg).report();
    llvm::report_fatal_error(msg);
  }
  auto dfsIt = llvm::df_begin<const CallGraphNode *>(startNode);
  auto dfsEnd = llvm::df_end<const CallGraphNode *>(startNode);
  for (; dfsIt != dfsEnd; ++dfsIt) {
    const CallGraphNode *currNode = *dfsIt;
    if (currNode->isExternal()) {
      continue;
    }
    mlir::CallableOpInterface current = currNode->getCalledFunction();
 
    // Update the cache according to the path before checking if B is reachable.
    for (unsigned i = 0; i < dfsIt.getPathLength(); i++) {
      mlir::CallableOpInterface ancestor = dfsIt.getPath(i)->getCalledFunction();
      reachabilityMap[ancestor].insert(current);
    }
 
    if (isReachableCached(current, B)) {
      return true;
    }
  }
  return false;
}
 
} // namespace llzk