llvm/mlir/lib/Transforms/Utils/Inliner.cpp

//===- Inliner.cpp ---- SCC-based inliner ---------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements Inliner that uses a basic inlining
// algorithm that operates bottom up over the Strongly Connect Components(SCCs)
// of the CallGraph. This enables a more incremental propagation of inlining
// decisions from the leafs to the roots of the callgraph.
//
//===----------------------------------------------------------------------===//

#include "mlir/Transforms/Inliner.h"
#include "mlir/IR/Threading.h"
#include "mlir/Interfaces/CallInterfaces.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Support/DebugStringHelper.h"
#include "mlir/Transforms/InliningUtils.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Debug.h"

#define DEBUG_TYPE …

usingnamespacemlir;

ResolvedCall;

//===----------------------------------------------------------------------===//
// Symbol Use Tracking
//===----------------------------------------------------------------------===//

/// Walk all of the used symbol callgraph nodes referenced with the given op.
static void walkReferencedSymbolNodes(
    Operation *op, CallGraph &cg, SymbolTableCollection &symbolTable,
    DenseMap<Attribute, CallGraphNode *> &resolvedRefs,
    function_ref<void(CallGraphNode *, Operation *)> callback) { … }

//===----------------------------------------------------------------------===//
// CGUseList

namespace {
/// This struct tracks the uses of callgraph nodes that can be dropped when
/// use_empty. It directly tracks and manages a use-list for all of the
/// call-graph nodes. This is necessary because many callgraph nodes are
/// referenced by SymbolRefAttr, which has no mechanism akin to the SSA `Use`
/// class.
struct CGUseList { … };
} // namespace

CGUseList::CGUseList(Operation *op, CallGraph &cg,
                     SymbolTableCollection &symbolTable)
    : … { … }

void CGUseList::dropCallUses(CallGraphNode *userNode, Operation *callOp,
                             CallGraph &cg) { … }

void CGUseList::eraseNode(CallGraphNode *node) { … }

bool CGUseList::isDead(CallGraphNode *node) const { … }

bool CGUseList::hasOneUseAndDiscardable(CallGraphNode *node) const { … }

void CGUseList::recomputeUses(CallGraphNode *node, CallGraph &cg) { … }

void CGUseList::mergeUsesAfterInlining(CallGraphNode *lhs, CallGraphNode *rhs) { … }

void CGUseList::decrementDiscardableUses(CGUser &uses) { … }

//===----------------------------------------------------------------------===//
// CallGraph traversal
//===----------------------------------------------------------------------===//

namespace {
/// This class represents a specific callgraph SCC.
class CallGraphSCC { … };
} // namespace

/// Run a given transformation over the SCCs of the callgraph in a bottom up
/// traversal.
static LogicalResult runTransformOnCGSCCs(
    const CallGraph &cg,
    function_ref<LogicalResult(CallGraphSCC &)> sccTransformer) { … }

/// Collect all of the callable operations within the given range of blocks. If
/// `traverseNestedCGNodes` is true, this will also collect call operations
/// inside of nested callgraph nodes.
static void collectCallOps(iterator_range<Region::iterator> blocks,
                           CallGraphNode *sourceNode, CallGraph &cg,
                           SymbolTableCollection &symbolTable,
                           SmallVectorImpl<ResolvedCall> &calls,
                           bool traverseNestedCGNodes) { … }

//===----------------------------------------------------------------------===//
// InlinerInterfaceImpl
//===----------------------------------------------------------------------===//

#ifndef NDEBUG
static std::string getNodeName(CallOpInterface op) {
  if (llvm::dyn_cast_if_present<SymbolRefAttr>(op.getCallableForCallee()))
    return debugString(op);
  return "_unnamed_callee_";
}
#endif

/// Return true if the specified `inlineHistoryID`  indicates an inline history
/// that already includes `node`.
static bool inlineHistoryIncludes(
    CallGraphNode *node, std::optional<size_t> inlineHistoryID,
    MutableArrayRef<std::pair<CallGraphNode *, std::optional<size_t>>>
        inlineHistory) { … }

namespace {
/// This class provides a specialization of the main inlining interface.
struct InlinerInterfaceImpl : public InlinerInterface { … };
} // namespace

namespace mlir {

class Inliner::Impl { … };

LogicalResult Inliner::Impl::inlineSCC(InlinerInterfaceImpl &inlinerIface,
                                       CGUseList &useList,
                                       CallGraphSCC &currentSCC,
                                       MLIRContext *context) { … }

LogicalResult Inliner::Impl::optimizeSCC(CallGraph &cg, CGUseList &useList,
                                         CallGraphSCC &currentSCC,
                                         MLIRContext *context) { … }

LogicalResult
Inliner::Impl::optimizeSCCAsync(MutableArrayRef<CallGraphNode *> nodesToVisit,
                                MLIRContext *ctx) { … }

LogicalResult
Inliner::Impl::optimizeCallable(CallGraphNode *node,
                                llvm::StringMap<OpPassManager> &pipelines) { … }

/// Attempt to inline calls within the given scc. This function returns
/// success if any calls were inlined, failure otherwise.
LogicalResult
Inliner::Impl::inlineCallsInSCC(InlinerInterfaceImpl &inlinerIface,
                                CGUseList &useList, CallGraphSCC &currentSCC) { … }

/// Returns true if the given call should be inlined.
bool Inliner::Impl::shouldInline(ResolvedCall &resolvedCall) { … }

LogicalResult Inliner::doInlining() { … }
} // namespace mlir