LLVM  14.0.0git
Typedefs | Functions | Variables
IRSimilarityIdentifier.cpp File Reference
#include "llvm/Analysis/IRSimilarityIdentifier.h"
#include "llvm/ADT/DenseMap.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"
Include dependency graph for IRSimilarityIdentifier.cpp:

Go to the source code of this file.

Typedefs

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

Functions

static StringRef getCalledFunctionName (CallInst &CI)
 
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. More...
 
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. More...
 
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. More...
 
static void findCandidateStructures (std::vector< IRSimilarityCandidate > &CandsForRepSubstring, DenseMap< unsigned, SimilarityGroup > &StructuralGroups)
 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. More...
 
 INITIALIZE_PASS (IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier", "ir-similarity-identifier", false, true) IRSimilarityIdentifierWrapperPass
 

Variables

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."))
 

Typedef Documentation

◆ ZippedRelativeLocationsT

Definition at line 652 of file IRSimilarityIdentifier.cpp.

Function Documentation

◆ 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 501 of file IRSimilarityIdentifier.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::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 417 of file IRSimilarityIdentifier.cpp.

References llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::begin(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::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 sanity 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 828 of file IRSimilarityIdentifier.cpp.

References 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 
)
static

◆ getCalledFunctionName()

static StringRef getCalledFunctionName ( CallInst CI)
static

◆ INITIALIZE_PASS()

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

Variable Documentation

◆ DisableBranches

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."))