#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"

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< bool >	llvm::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 >	llvm::DisableIndirectCalls ("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))

cl::opt< bool >	llvm::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 >	llvm::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]	CurrentSrcTgtNumberMapping	current mapping of global value numbers from source IRSimilarityCandidate to target IRSimilarityCandidate.
[in]	SourceArgVal	The global value number for an operand in the in the original candidate.
[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.

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
	)

Definition at line 1485 of file IRSimilarityIdentifier.cpp.

References llvm::PassRegistry::getPassRegistry(), and llvm::initializeIRSimilarityIdentifierWrapperPassPass().

Namespaces

Typedefs

Functions

Variables

Typedef Documentation

◆ ZippedRelativeLocationsT

Function Documentation

◆ CheckLargerCands()

◆ checkNumberingAndReplace()

◆ checkNumberingAndReplaceCommutative()

◆ createCandidatesFromSuffixTree()

◆ findCandidateStructures()

◆ INITIALIZE_PASS()