ByteCode.cpp | Explore in Territory

//===- ByteCode.cpp - Pattern ByteCode Interpreter ------------------------===//
//
// 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 MLIR to byte-code generation and the interpreter.
//
//===----------------------------------------------------------------------===//

#include "ByteCode.h"
#include "mlir/Analysis/Liveness.h"
#include "mlir/Dialect/PDL/IR/PDLTypes.h"
#include "mlir/Dialect/PDLInterp/IR/PDLInterp.h"
#include "mlir/IR/BuiltinOps.h"
#include "mlir/IR/RegionGraphTraits.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/FormatVariadic.h"
#include <numeric>
#include <optional>

#define DEBUG_TYPE …

usingnamespacemlir;
usingnamespacemlir::detail;

//===----------------------------------------------------------------------===//
// PDLByteCodePattern
//===----------------------------------------------------------------------===//

PDLByteCodePattern PDLByteCodePattern::create(pdl_interp::RecordMatchOp matchOp,
                                              PDLPatternConfigSet *configSet,
                                              ByteCodeAddr rewriterAddr) { … }

//===----------------------------------------------------------------------===//
// PDLByteCodeMutableState
//===----------------------------------------------------------------------===//

/// Set the new benefit for a bytecode pattern. The `patternIndex` corresponds
/// to the position of the pattern within the range returned by
/// `PDLByteCode::getPatterns`.
void PDLByteCodeMutableState::updatePatternBenefit(unsigned patternIndex,
                                                   PatternBenefit benefit) { … }

/// Cleanup any allocated state after a full match/rewrite has been completed.
/// This method should be called irregardless of whether the match+rewrite was a
/// success or not.
void PDLByteCodeMutableState::cleanupAfterMatchAndRewrite() { … }

//===----------------------------------------------------------------------===//
// Bytecode OpCodes
//===----------------------------------------------------------------------===//

namespace {
enum OpCode : ByteCodeField { … };
} // namespace

/// A marker used to indicate if an operation should infer types.
static constexpr ByteCodeField kInferTypesMarker = …;

//===----------------------------------------------------------------------===//
// ByteCode Generation
//===----------------------------------------------------------------------===//

//===----------------------------------------------------------------------===//
// Generator

namespace {
struct ByteCodeLiveRange;
struct ByteCodeWriter;

/// Check if the given class `T` can be converted to an opaque pointer.
has_pointer_traits;

/// This class represents the main generator for the pattern bytecode.
class Generator { … };

/// This class provides utilities for writing a bytecode stream.
struct ByteCodeWriter { … };

/// This class represents a live range of PDL Interpreter values, containing
/// information about when values are live within a match/rewrite.
struct ByteCodeLiveRange { … };
} // namespace

void Generator::generate(ModuleOp module) { … }

void Generator::allocateMemoryIndices(pdl_interp::FuncOp matcherFunc,
                                      ModuleOp rewriterModule) { … }

void Generator::generate(Region *region, ByteCodeWriter &writer) { … }

void Generator::generate(Operation *op, ByteCodeWriter &writer) { … }

void Generator::generate(pdl_interp::ApplyConstraintOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::ApplyRewriteOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::AreEqualOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::BranchOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckAttributeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckOperandCountOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckOperationNameOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckResultCountOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckTypeOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CheckTypesOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::ContinueOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CreateAttributeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CreateOperationOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CreateRangeOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CreateTypeOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::CreateTypesOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::EraseOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::ExtractOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::FinalizeOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::ForEachOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetAttributeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetAttributeTypeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetDefiningOpOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetOperandOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetOperandsOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetResultOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetResultsOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetUsersOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::GetValueTypeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::IsNotNullOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::RecordMatchOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::ReplaceOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchAttributeOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchOperandCountOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchOperationNameOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchResultCountOp op,
                         ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchTypeOp op, ByteCodeWriter &writer) { … }
void Generator::generate(pdl_interp::SwitchTypesOp op, ByteCodeWriter &writer) { … }

//===----------------------------------------------------------------------===//
// PDLByteCode
//===----------------------------------------------------------------------===//

PDLByteCode::PDLByteCode(
    ModuleOp module, SmallVector<std::unique_ptr<PDLPatternConfigSet>> configs,
    const DenseMap<Operation *, PDLPatternConfigSet *> &configMap,
    llvm::StringMap<PDLConstraintFunction> constraintFns,
    llvm::StringMap<PDLRewriteFunction> rewriteFns)
    : … { … }

/// Initialize the given state such that it can be used to execute the current
/// bytecode.
void PDLByteCode::initializeMutableState(PDLByteCodeMutableState &state) const { … }

//===----------------------------------------------------------------------===//
// ByteCode Execution

namespace {
/// This class is an instantiation of the PDLResultList that provides access to
/// the returned results. This API is not on `PDLResultList` to avoid
/// overexposing access to information specific solely to the ByteCode.
class ByteCodeRewriteResultList : public PDLResultList { … };

/// This class provides support for executing a bytecode stream.
class ByteCodeExecutor { … };
} // namespace

void ByteCodeExecutor::executeApplyConstraint(PatternRewriter &rewriter) { … }

LogicalResult ByteCodeExecutor::executeApplyRewrite(PatternRewriter &rewriter) { … }

void ByteCodeExecutor::processNativeFunResults(
    ByteCodeRewriteResultList &results, unsigned numResults,
    LogicalResult &rewriteResult) { … }

void ByteCodeExecutor::executeAreEqual() { … }

void ByteCodeExecutor::executeAreRangesEqual() { … }

void ByteCodeExecutor::executeBranch() { … }

void ByteCodeExecutor::executeCheckOperandCount() { … }

void ByteCodeExecutor::executeCheckOperationName() { … }

void ByteCodeExecutor::executeCheckResultCount() { … }

void ByteCodeExecutor::executeCheckTypes() { … }

void ByteCodeExecutor::executeContinue() { … }

void ByteCodeExecutor::executeCreateConstantTypeRange() { … }

void ByteCodeExecutor::executeCreateOperation(PatternRewriter &rewriter,
                                              Location mainRewriteLoc) { … }

template <typename T>
void ByteCodeExecutor::executeDynamicCreateRange(StringRef type) { … }

void ByteCodeExecutor::executeEraseOp(PatternRewriter &rewriter) { … }

template <typename T, typename Range, PDLValue::Kind kind>
void ByteCodeExecutor::executeExtract() { … }

void ByteCodeExecutor::executeFinalize() { … }

void ByteCodeExecutor::executeForEach() { … }

void ByteCodeExecutor::executeGetAttribute() { … }

void ByteCodeExecutor::executeGetAttributeType() { … }

void ByteCodeExecutor::executeGetDefiningOp() { … }

void ByteCodeExecutor::executeGetOperand(unsigned index) { … }

/// This function is the internal implementation of `GetResults` and
/// `GetOperands` that provides support for extracting a value range from the
/// given operation.
template <template <typename> class AttrSizedSegmentsT, typename RangeT>
static void *
executeGetOperandsResults(RangeT values, Operation *op, unsigned index,
                          ByteCodeField rangeIndex, StringRef attrSizedSegments,
                          MutableArrayRef<ValueRange> valueRangeMemory) { … }

void ByteCodeExecutor::executeGetOperands() { … }

void ByteCodeExecutor::executeGetResult(unsigned index) { … }

void ByteCodeExecutor::executeGetResults() { … }

void ByteCodeExecutor::executeGetUsers() { … }

void ByteCodeExecutor::executeGetValueType() { … }

void ByteCodeExecutor::executeGetValueRangeTypes() { … }

void ByteCodeExecutor::executeIsNotNull() { … }

void ByteCodeExecutor::executeRecordMatch(
    PatternRewriter &rewriter,
    SmallVectorImpl<PDLByteCode::MatchResult> &matches) { … }

void ByteCodeExecutor::executeReplaceOp(PatternRewriter &rewriter) { … }

void ByteCodeExecutor::executeSwitchAttribute() { … }

void ByteCodeExecutor::executeSwitchOperandCount() { … }

void ByteCodeExecutor::executeSwitchOperationName() { … }

void ByteCodeExecutor::executeSwitchResultCount() { … }

void ByteCodeExecutor::executeSwitchType() { … }

void ByteCodeExecutor::executeSwitchTypes() { … }

LogicalResult
ByteCodeExecutor::execute(PatternRewriter &rewriter,
                          SmallVectorImpl<PDLByteCode::MatchResult> *matches,
                          std::optional<Location> mainRewriteLoc) { … }

void PDLByteCode::match(Operation *op, PatternRewriter &rewriter,
                        SmallVectorImpl<MatchResult> &matches,
                        PDLByteCodeMutableState &state) const { … }

LogicalResult PDLByteCode::rewrite(PatternRewriter &rewriter,
                                   const MatchResult &match,
                                   PDLByteCodeMutableState &state) const { … }
llvm/mlir/lib/Rewrite/ByteCode.cpp
