LLVM 20.0.0git
Namespaces | Typedefs | Functions | Variables
IRSimilarityIdentifier.cpp File Reference
#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"

Go to the source code of this file.

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Typedefs

typedef detail::zippy< detail::zip_shortest, SmallVector< int, 4 > &, SmallVector< int, 4 > &, ArrayRef< Value * > &, ArrayRef< Value * > & > ZippedRelativeLocationsT
 

Functions

static bool checkNumberingAndReplaceCommutative (const DenseMap< Value *, unsigned > &SourceValueToNumberMapping, DenseMap< unsigned, DenseSet< unsigned > > &CurrentSrcTgtNumberMapping, ArrayRef< Value * > &SourceOperands, DenseSet< unsigned > &TargetValueNumbers)
 Determine if one or more of the assigned global value numbers for the operands in TargetValueNumbers is in the current mapping set for operand numbers in SourceOperands.
 
bool checkNumberingAndReplace (DenseMap< unsigned, DenseSet< unsigned > > &CurrentSrcTgtNumberMapping, unsigned SourceArgVal, unsigned TargetArgVal)
 Determine if operand number TargetArgVal is in the current mapping set for operand number SourceArgVal.
 
static void createCandidatesFromSuffixTree (const IRInstructionMapper &Mapper, std::vector< IRInstructionData * > &InstrList, std::vector< unsigned > &IntegerMapping, SuffixTree::RepeatedSubstring &RS, std::vector< IRSimilarityCandidate > &CandsForRepSubstring)
 From a repeated subsequence, find all the different instances of the subsequence from the InstrList, and create an IRSimilarityCandidate from the IRInstructionData in subsequence.
 
static std::optional< std::pair< IRSimilarityCandidate *, IRSimilarityCandidate * > > CheckLargerCands (IRSimilarityCandidate &CandA, IRSimilarityCandidate &CandB, DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &IndexToIncludedCand, DenseMap< IRSimilarityCandidate *, unsigned > &CandToGroup)
 Look for larger IRSimilarityCandidates From the previously matched IRSimilarityCandidates that fully contain CandA or CandB.
 
static void findCandidateStructures (std::vector< IRSimilarityCandidate > &CandsForRepSubstring, DenseMap< unsigned, SimilarityGroup > &StructuralGroups, DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &IndexToIncludedCand, DenseMap< IRSimilarityCandidate *, unsigned > &CandToOverallGroup)
 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.
 
 INITIALIZE_PASS (IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier", "ir-similarity-identifier", false, true) IRSimilarityIdentifierWrapperPass
 

Variables

cl::opt< boolllvm::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< boolllvm::DisableIndirectCalls ("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))
 
cl::opt< boolllvm::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< boolllvm::DisableIntrinsics ("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))
 

Typedef Documentation

◆ ZippedRelativeLocationsT

typedef detail::zippy<detail::zip_shortest, SmallVector<int, 4> &, SmallVector<int, 4> &, ArrayRef<Value *> &, ArrayRef<Value *> &> ZippedRelativeLocationsT

Definition at line 787 of file IRSimilarityIdentifier.cpp.

Function Documentation

◆ CheckLargerCands()

static std::optional< std::pair< IRSimilarityCandidate *, IRSimilarityCandidate * > > CheckLargerCands ( IRSimilarityCandidate CandA,
IRSimilarityCandidate CandB,
DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &  IndexToIncludedCand,
DenseMap< IRSimilarityCandidate *, unsigned > &  CandToGroup 
)
static

Look for larger IRSimilarityCandidates From the previously matched IRSimilarityCandidates that fully contain CandA or CandB.

If there is an overlap, return a pair of structurally similar, larger IRSimilarityCandidates.

Parameters
[in]CandA- The first candidate we are trying to determine the structure of.
[in]CandB- The second candidate we are trying to determine the structure of.
[in]IndexToIncludedCand- Mapping of index of the an instruction in a circuit to the IRSimilarityCandidates that include this instruction.
[in]CandToOverallGroup- Mapping of IRSimilarityCandidate to a number representing the structural group assigned to it.

Definition at line 1206 of file IRSimilarityIdentifier.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::begin(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::find(), llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx(), llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and llvm::set_intersect().

Referenced by findCandidateStructures().

◆ checkNumberingAndReplace()

bool checkNumberingAndReplace ( DenseMap< unsigned, DenseSet< unsigned > > &  CurrentSrcTgtNumberMapping,
unsigned  SourceArgVal,
unsigned  TargetArgVal 
)

Determine if operand number TargetArgVal is in the current mapping set for operand number SourceArgVal.

Parameters
[in,out]CurrentSrcTgtNumberMappingcurrent mapping of global value numbers from source IRSimilarityCandidate to target IRSimilarityCandidate.
[in]SourceArgValThe global value number for an operand in the in the original candidate.
[in]TargetArgValThe global value number for the corresponding operand in the other candidate.
Returns
True if there exists a mapping and false if not.

Definition at line 608 of file IRSimilarityIdentifier.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size().

Referenced by llvm::IRSimilarity::IRSimilarityCandidate::compareNonCommutativeOperandMapping().

◆ checkNumberingAndReplaceCommutative()

static bool checkNumberingAndReplaceCommutative ( const DenseMap< Value *, unsigned > &  SourceValueToNumberMapping,
DenseMap< unsigned, DenseSet< unsigned > > &  CurrentSrcTgtNumberMapping,
ArrayRef< Value * > &  SourceOperands,
DenseSet< unsigned > &  TargetValueNumbers 
)
static

Determine if one or more of the assigned global value numbers for the operands in TargetValueNumbers is in the current mapping set for operand numbers in SourceOperands.

The set of possible corresponding global value numbers are replaced with the most recent version of compatible values.

Parameters
[in]SourceValueToNumberMapping- The mapping of a Value to global value number for the source IRInstructionCandidate.
[in,out]CurrentSrcTgtNumberMapping- The current mapping of source IRSimilarityCandidate global value numbers to a set of possible numbers in the target.
[in]SourceOperands- The operands in the original IRSimilarityCandidate in the current instruction.
[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.

Definition at line 531 of file IRSimilarityIdentifier.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::begin(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), and llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT >::swap().

Referenced by llvm::IRSimilarity::IRSimilarityCandidate::compareCommutativeOperandMapping().

◆ createCandidatesFromSuffixTree()

static void createCandidatesFromSuffixTree ( const IRInstructionMapper Mapper,
std::vector< IRInstructionData * > &  InstrList,
std::vector< unsigned > &  IntegerMapping,
SuffixTree::RepeatedSubstring RS,
std::vector< IRSimilarityCandidate > &  CandsForRepSubstring 
)
static

From a repeated subsequence, find all the different instances of the subsequence from the InstrList, and create an IRSimilarityCandidate from the IRInstructionData in subsequence.

Parameters
[in]Mapper- The instruction mapper for basic correctness checks.
[in]InstrList- The vector that holds the instruction data.
[in]IntegerMapping- The vector that holds the mapped integers.
[out]CandsForRepSubstring- The vector to store the generated IRSimilarityCandidates.

Definition at line 969 of file IRSimilarityIdentifier.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::IRSimilarity::IRInstructionMapper::IllegalInstrNumber, llvm::SuffixTree::RepeatedSubstring::Length, and llvm::SuffixTree::RepeatedSubstring::StartIndices.

◆ findCandidateStructures()

static void findCandidateStructures ( std::vector< IRSimilarityCandidate > &  CandsForRepSubstring,
DenseMap< unsigned, SimilarityGroup > &  StructuralGroups,
DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &  IndexToIncludedCand,
DenseMap< IRSimilarityCandidate *, unsigned > &  CandToOverallGroup 
)
static

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.

Parameters
[in]CandsForRepSubstring- The vector containing the IRSimilarityCandidates.
[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.
[in]IndexToIncludedCand- Mapping of index of the an instruction in a circuit to the IRSimilarityCandidates that include this instruction.
[in]CandToOverallGroup- Mapping of IRSimilarityCandidate to a number representing the structural group assigned to it.

Definition at line 1279 of file IRSimilarityIdentifier.cpp.

References CheckLargerCands(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::IRSimilarity::IRSimilarityCandidate::compareStructure(), llvm::IRSimilarity::IRSimilarityCandidate::createCanonicalMappingFor(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ INITIALIZE_PASS()

INITIALIZE_PASS ( IRSimilarityIdentifierWrapperPass  ,
"ir-similarity-identifier"  ,
"ir-similarity-identifier"  ,
false  ,
true   
)