llvm/llvm/lib/Analysis/IRSimilarityIdentifier.cpp

//===- IRSimilarityIdentifier.cpp - Find similarity in a module -----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// \file
// Implementation file for the IRSimilarityIdentifier for identifying
// similarities in IR including the IRInstructionMapper.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/IRSimilarityIdentifier.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/User.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/SuffixTree.h"

usingnamespacellvm;
usingnamespaceIRSimilarity;

namespace llvm {
cl::opt<bool>
    DisableBranches("no-ir-sim-branch-matching", cl::init(false),
                    cl::ReallyHidden,
                    cl::desc("disable similarity matching, and outlining, "
                             "across branches for debugging purposes."));

cl::opt<bool>
    DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false),
                         cl::ReallyHidden,
                         cl::desc("disable outlining indirect calls."));

cl::opt<bool>
    MatchCallsByName("ir-sim-calls-by-name", cl::init(false), cl::ReallyHidden,
                     cl::desc("only allow matching call instructions if the "
                              "name and type signature match."));

cl::opt<bool>
    DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden,
                      cl::desc("Don't match or outline intrinsics"));
} // namespace llvm

IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
                                     IRInstructionDataList &IDList)
    : … { … }

void IRInstructionData::initializeInstruction() { … }

IRInstructionData::IRInstructionData(IRInstructionDataList &IDList)
    : … { … }

void IRInstructionData::setBranchSuccessors(
    DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) { … }

ArrayRef<Value *> IRInstructionData::getBlockOperVals() { … }

void IRInstructionData::setCalleeName(bool MatchByName) { … }

void IRInstructionData::setPHIPredecessors(
    DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) { … }

CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) { … }

CmpInst::Predicate IRInstructionData::getPredicate() const { … }

StringRef IRInstructionData::getCalleeName() const { … }

bool IRSimilarity::isClose(const IRInstructionData &A,
                           const IRInstructionData &B) { … }

// TODO: This is the same as the MachineOutliner, and should be consolidated
// into the same interface.
void IRInstructionMapper::convertToUnsignedVec(
    BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
    std::vector<unsigned> &IntegerMapping) { … }

// TODO: This is the same as the MachineOutliner, and should be consolidated
// into the same interface.
unsigned IRInstructionMapper::mapToLegalUnsigned(
    BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
    std::vector<IRInstructionData *> &InstrListForBB) { … }

IRInstructionData *
IRInstructionMapper::allocateIRInstructionData(Instruction &I, bool Legality,
                                               IRInstructionDataList &IDL) { … }

IRInstructionData *
IRInstructionMapper::allocateIRInstructionData(IRInstructionDataList &IDL) { … }

IRInstructionDataList *
IRInstructionMapper::allocateIRInstructionDataList() { … }

// TODO: This is the same as the MachineOutliner, and should be consolidated
// into the same interface.
unsigned IRInstructionMapper::mapToIllegalUnsigned(
    BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
    std::vector<IRInstructionData *> &InstrListForBB, bool End) { … }

IRSimilarityCandidate::IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
                                             IRInstructionData *FirstInstIt,
                                             IRInstructionData *LastInstIt)
    : … { … }

bool IRSimilarityCandidate::isSimilar(const IRSimilarityCandidate &A,
                                      const IRSimilarityCandidate &B) { … }

/// Determine if one or more of the assigned global value numbers for the
/// operands in \p TargetValueNumbers is in the current mapping set for operand
/// numbers in \p SourceOperands.  The set of possible corresponding global
/// value numbers are replaced with the most recent version of compatible
/// values.
///
/// \param [in] SourceValueToNumberMapping - The mapping of a Value to global
/// value number for the source IRInstructionCandidate.
/// \param [in, out] CurrentSrcTgtNumberMapping - The current mapping of source
/// IRSimilarityCandidate global value numbers to a set of possible numbers in
/// the target.
/// \param [in] SourceOperands - The operands in the original
/// IRSimilarityCandidate in the current instruction.
/// \param [in] TargetValueNumbers - The global value numbers of the operands in
/// the corresponding Instruction in the other IRSimilarityCandidate.
/// \returns true if there exists a possible mapping between the source
/// Instruction operands and the target Instruction operands, and false if not.
static bool checkNumberingAndReplaceCommutative(
  const DenseMap<Value *, unsigned> &SourceValueToNumberMapping,
  DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
  ArrayRef<Value *> &SourceOperands,
  DenseSet<unsigned> &TargetValueNumbers){ … }

/// Determine if operand number \p TargetArgVal is in the current mapping set
/// for operand number \p SourceArgVal.
///
/// \param [in, out] CurrentSrcTgtNumberMapping current mapping of global
/// value numbers from source IRSimilarityCandidate to target
/// IRSimilarityCandidate.
/// \param [in] SourceArgVal The global value number for an operand in the
/// in the original candidate.
/// \param [in] TargetArgVal The global value number for the corresponding
/// operand in the other candidate.
/// \returns True if there exists a mapping and false if not.
bool checkNumberingAndReplace(
    DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
    unsigned SourceArgVal, unsigned TargetArgVal) { … }

bool IRSimilarityCandidate::compareNonCommutativeOperandMapping(
    OperandMapping A, OperandMapping B) { … }

bool IRSimilarityCandidate::compareCommutativeOperandMapping(
    OperandMapping A, OperandMapping B) { … }

bool IRSimilarityCandidate::compareAssignmentMapping(
    const unsigned InstValA, const unsigned &InstValB,
    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) { … }

bool IRSimilarityCandidate::checkRelativeLocations(RelativeLocMapping A,
                                                   RelativeLocMapping B) { … }

bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
                                             const IRSimilarityCandidate &B) { … }

ZippedRelativeLocationsT;

bool IRSimilarityCandidate::compareStructure(
    const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) { … }

bool IRSimilarityCandidate::overlap(const IRSimilarityCandidate &A,
                                    const IRSimilarityCandidate &B) { … }

void IRSimilarityIdentifier::populateMapper(
    Module &M, std::vector<IRInstructionData *> &InstrList,
    std::vector<unsigned> &IntegerMapping) { … }

void IRSimilarityIdentifier::populateMapper(
    ArrayRef<std::unique_ptr<Module>> &Modules,
    std::vector<IRInstructionData *> &InstrList,
    std::vector<unsigned> &IntegerMapping) { … }

/// From a repeated subsequence, find all the different instances of the
/// subsequence from the \p InstrList, and create an IRSimilarityCandidate from
/// the IRInstructionData in subsequence.
///
/// \param [in] Mapper - The instruction mapper for basic correctness checks.
/// \param [in] InstrList - The vector that holds the instruction data.
/// \param [in] IntegerMapping - The vector that holds the mapped integers.
/// \param [out] CandsForRepSubstring - The vector to store the generated
/// IRSimilarityCandidates.
static void createCandidatesFromSuffixTree(
    const IRInstructionMapper& Mapper, std::vector<IRInstructionData *> &InstrList,
    std::vector<unsigned> &IntegerMapping, SuffixTree::RepeatedSubstring &RS,
    std::vector<IRSimilarityCandidate> &CandsForRepSubstring) { … }

void IRSimilarityCandidate::createCanonicalRelationFrom(
    IRSimilarityCandidate &SourceCand,
    DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
    DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping) { … }

void IRSimilarityCandidate::createCanonicalRelationFrom(
    IRSimilarityCandidate &SourceCand, IRSimilarityCandidate &SourceCandLarge,
    IRSimilarityCandidate &TargetCandLarge) { … }

void IRSimilarityCandidate::createCanonicalMappingFor(
    IRSimilarityCandidate &CurrCand) { … }

/// Look for larger IRSimilarityCandidates From the previously matched
/// IRSimilarityCandidates that fully contain \p CandA or \p CandB.  If there is
/// an overlap, return a pair of structurally similar, larger
/// IRSimilarityCandidates.
///
/// \param [in] CandA - The first candidate we are trying to determine the
/// structure of.
/// \param [in] CandB - The second candidate we are trying to determine the
/// structure of.
/// \param [in] IndexToIncludedCand - Mapping of index of the an instruction in
/// a circuit to the IRSimilarityCandidates that include this instruction.
/// \param [in] CandToOverallGroup - Mapping of IRSimilarityCandidate to a
/// number representing the structural group assigned to it.
static std::optional<
    std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>
CheckLargerCands(
    IRSimilarityCandidate &CandA, IRSimilarityCandidate &CandB,
    DenseMap<unsigned, DenseSet<IRSimilarityCandidate *>> &IndexToIncludedCand,
    DenseMap<IRSimilarityCandidate *, unsigned> &CandToGroup) { … }

/// From the list of IRSimilarityCandidates, perform a comparison between each
/// IRSimilarityCandidate to determine if there are overlapping
/// IRInstructionData, or if they do not have the same structure.
///
/// \param [in] CandsForRepSubstring - The vector containing the
/// IRSimilarityCandidates.
/// \param [out] StructuralGroups - the mapping of unsigned integers to vector
/// of IRSimilarityCandidates where each of the IRSimilarityCandidates in the
/// vector are structurally similar to one another.
/// \param [in] IndexToIncludedCand - Mapping of index of the an instruction in
/// a circuit to the IRSimilarityCandidates that include this instruction.
/// \param [in] CandToOverallGroup - Mapping of IRSimilarityCandidate to a
/// number representing the structural group assigned to it.
static void findCandidateStructures(
    std::vector<IRSimilarityCandidate> &CandsForRepSubstring,
    DenseMap<unsigned, SimilarityGroup> &StructuralGroups,
    DenseMap<unsigned,  DenseSet<IRSimilarityCandidate *>> &IndexToIncludedCand,
    DenseMap<IRSimilarityCandidate *, unsigned> &CandToOverallGroup
    ) { … }

void IRSimilarityIdentifier::findCandidates(
    std::vector<IRInstructionData *> &InstrList,
    std::vector<unsigned> &IntegerMapping) { … }

SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
    ArrayRef<std::unique_ptr<Module>> Modules) { … }

SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) { … }

INITIALIZE_PASS(…)

IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass()
    : … { … }

bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) { … }

bool IRSimilarityIdentifierWrapperPass::doFinalization(Module &M) { … }

bool IRSimilarityIdentifierWrapperPass::runOnModule(Module &M) { … }

AnalysisKey IRSimilarityAnalysis::Key;
IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
                                                 ModuleAnalysisManager &) { … }

PreservedAnalyses
IRSimilarityAnalysisPrinterPass::run(Module &M, ModuleAnalysisManager &AM) { … }

char IRSimilarityIdentifierWrapperPass::ID = …;