class IRSimilarityCandidate
Declaration
class IRSimilarityCandidate { /* full declaration omitted */ };
Description
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IRInstructionData, which is a region of the program. It is also responsible for defining the structure within this region of instructions. The structure of a region is defined through a value numbering system assigned to each unique value in a region at the creation of the IRSimilarityCandidate. For example, for each Instruction we add a mapping for each new value seen in that Instruction. IR: Mapping Added: %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2 %add2 = add i32 %a, %1 %add2 -> 4 %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5 We can compare IRSimilarityCandidates against one another. The \ref isSimilar function compares each IRInstructionData against one another and if we have the same sequences of IRInstructionData that would create the same hash, we have similar IRSimilarityCandidates. We can also compare the structure of IRSimilarityCandidates. If we can create a mapping of registers in the region contained by one IRSimilarityCandidate to the region contained by different IRSimilarityCandidate, they can be considered structurally similar. IRSimilarityCandidate1: IRSimilarityCandidate2: %add1 = add i32 %a, %b %add1 = add i32 %d, %e %add2 = add i32 %a, %c %add2 = add i32 %d, %f %add3 = add i32 c1, c2 %add3 = add i32 c3, c4 Can have the following mapping from candidate to candidate of: %a -> %d, %b -> %e, %c -> %f, c1 -> c3, c2 -> c4 and can be considered similar. IRSimilarityCandidate1: IRSimilarityCandidate2: %add1 = add i32 %a, %b %add1 = add i32 %d, c4 %add2 = add i32 %a, %c %add2 = add i32 %d, %f %add3 = add i32 c1, c2 %add3 = add i32 c3, c4 We cannot create the same mapping since the use of c4 is not used in the same way as %b or c2.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:648
Member Variables
- private unsigned int StartIdx = 0
- The start index of this IRSimilarityCandidate in the instruction list.
- private unsigned int Len = 0
- The number of instructions in this IRSimilarityCandidate.
- private llvm::IRSimilarity::IRInstructionData* FirstInst = nullptr
- The first instruction in this IRSimilarityCandidate.
- private llvm::IRSimilarity::IRInstructionData* LastInst = nullptr
- The last instruction in this IRSimilarityCandidate.
- private DenseMap<llvm::Value*, unsigned int> ValueToNumber
- Global Value Numbering structures @ { Stores the mapping of the value to the number assigned to it in the IRSimilarityCandidate.
- private DenseMap<unsigned int, llvm::Value*> NumberToValue
- Stores the mapping of the number to the value assigned this number.
- private DenseMap<unsigned int, unsigned int> NumberToCanonNum
- Stores the mapping of a value's number to canonical numbering in the candidate's respective similarity group.
- private DenseMap<unsigned int, unsigned int> CanonNumToNumber
- Stores the mapping of canonical number in the candidate's respective similarity group to a value number.
Method Overview
- public IRSimilarityCandidate(unsigned int StartIdx, unsigned int Len, llvm::IRSimilarity::IRInstructionData * FirstInstIt, llvm::IRSimilarity::IRInstructionData * LastInstIt)
- public llvm::IRSimilarity::IRInstructionData * back() const
- public llvm::Instruction * backInstruction()
- public llvm::IRSimilarity::IRSimilarityCandidate::iterator begin() const
- public static bool checkRelativeLocations(llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping A, llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping B)
- public static bool compareCommutativeOperandMapping(llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping A, llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping B)
- public static bool compareNonCommutativeOperandMapping(llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping A, llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping B)
- public static bool compareStructure(const llvm::IRSimilarity::IRSimilarityCandidate & A, const llvm::IRSimilarity::IRSimilarityCandidate & B)
- public static bool compareStructure(const llvm::IRSimilarity::IRSimilarityCandidate & A, const llvm::IRSimilarity::IRSimilarityCandidate & B, DenseMap<unsigned int, DenseSet<unsigned int>> & ValueNumberMappingA, DenseMap<unsigned int, DenseSet<unsigned int>> & ValueNumberMappingB)
- public static void createCanonicalMappingFor(llvm::IRSimilarity::IRSimilarityCandidate & CurrCand)
- public void createCanonicalRelationFrom(llvm::IRSimilarity::IRSimilarityCandidate & SourceCand, DenseMap<unsigned int, DenseSet<unsigned int>> & ToSourceMapping, DenseMap<unsigned int, DenseSet<unsigned int>> & FromSourceMapping)
- public llvm::IRSimilarity::IRSimilarityCandidate::iterator end() const
- public Optional<unsigned int> fromCanonicalNum(unsigned int N)
- public Optional<llvm::Value *> fromGVN(unsigned int Num)
- public llvm::IRSimilarity::IRInstructionData * front() const
- public llvm::Instruction * frontInstruction()
- public void getBasicBlocks(DenseSet<llvm::BasicBlock *> & BBSet, SmallVector<llvm::BasicBlock *> & BBList) const
- public void getBasicBlocks(DenseSet<llvm::BasicBlock *> & BBSet) const
- public Optional<unsigned int> getCanonicalNum(unsigned int N)
- public llvm::BasicBlock * getEndBB()
- public unsigned int getEndIdx() const
- public llvm::Function * getFunction()
- public Optional<unsigned int> getGVN(llvm::Value * V)
- public unsigned int getLength() const
- public llvm::BasicBlock * getStartBB()
- public unsigned int getStartIdx() const
- public static bool isSimilar(const llvm::IRSimilarity::IRSimilarityCandidate & A, const llvm::IRSimilarity::IRSimilarityCandidate & B)
- public static bool overlap(const llvm::IRSimilarity::IRSimilarityCandidate & A, const llvm::IRSimilarity::IRSimilarityCandidate & B)
Methods
¶IRSimilarityCandidate(
unsigned int StartIdx,
unsigned int Len,
llvm::IRSimilarity::IRInstructionData*
FirstInstIt,
llvm::IRSimilarity::IRInstructionData*
LastInstIt)
IRSimilarityCandidate(
unsigned int StartIdx,
unsigned int Len,
llvm::IRSimilarity::IRInstructionData*
FirstInstIt,
llvm::IRSimilarity::IRInstructionData*
LastInstIt)
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:682
Parameters
- unsigned int StartIdx
- - The starting location of the region.
- unsigned int Len
- - The length of the region.
- llvm::IRSimilarity::IRInstructionData* FirstInstIt
- - The starting IRInstructionData of the region.
- llvm::IRSimilarity::IRInstructionData* LastInstIt
- - The ending IRInstructionData of the region.
¶llvm::IRSimilarity::IRInstructionData* back()
const
llvm::IRSimilarity::IRInstructionData* back()
const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:872
Returns
The last IRInstructionData.
¶llvm::Instruction* backInstruction()
llvm::Instruction* backInstruction()
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:877
Returns
The last Instruction
¶llvm::IRSimilarity::IRSimilarityCandidate::
iterator
begin() const
llvm::IRSimilarity::IRSimilarityCandidate::
iterator
begin() const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:945
¶static bool checkRelativeLocations(
llvm::IRSimilarity::IRSimilarityCandidate::
RelativeLocMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
RelativeLocMapping B)
static bool checkRelativeLocations(
llvm::IRSimilarity::IRSimilarityCandidate::
RelativeLocMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
RelativeLocMapping B)
Description
Compare the relative locations in \p A and \p B and check that the distances match if both locations are contained in the region, and that the branches both point outside the region if they do not. Example Region: If we compare the branches in block_0 and block_1 the relative values are 1 and 2 for both, so we consider this a match. If we compare the branches in entry and block_0 the relative values are 2 and 3, and 1 and 2 respectively. Since these are not the same we do not consider them a match. If we compare the branches in block_1 and block_2 the relative values are 1 and 2, and -1 and None respectively. As a result we do not consider these to be the same If we compare the branches in block_2 and block_3 the relative values are -1 and None for both. We do consider these to be a match.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:800
Parameters
- llvm::IRSimilarity::IRSimilarityCandidate:: RelativeLocMapping A
- - The first IRInstructionCandidate, relative location value, and incoming block.
- llvm::IRSimilarity::IRSimilarityCandidate:: RelativeLocMapping B
- - The second IRInstructionCandidate, relative location value, and incoming block.
Returns
true if the relative locations match.
¶static bool compareCommutativeOperandMapping(
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping B)
static bool compareCommutativeOperandMapping(
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping B)
Description
Compare the operands in \p A and \p B and check that the current mapping of global value numbers from \p A to \p B and \p B to \Ais consistent given that the operands are commutative.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:762
Parameters
- llvm::IRSimilarity::IRSimilarityCandidate:: OperandMapping A
- - The first IRInstructionCandidate, operand values, and current operand mappings to compare.
- llvm::IRSimilarity::IRSimilarityCandidate:: OperandMapping B
- - The second IRInstructionCandidate, operand values, and current operand mappings to compare.
Returns
true if the IRSimilarityCandidates operands are compatible.
¶static bool compareNonCommutativeOperandMapping(
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping B)
static bool compareNonCommutativeOperandMapping(
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping A,
llvm::IRSimilarity::IRSimilarityCandidate::
OperandMapping B)
Description
Compare the operands in \p A and \p B and check that the current mapping of global value numbers from \p A to \p B and \p B to \Ais consistent.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:750
Parameters
- llvm::IRSimilarity::IRSimilarityCandidate:: OperandMapping A
- - The first IRInstructionCandidate, operand values, and current operand mappings to compare.
- llvm::IRSimilarity::IRSimilarityCandidate:: OperandMapping B
- - The second IRInstructionCandidate, operand values, and current operand mappings to compare.
Returns
true if the IRSimilarityCandidates operands are compatible.
¶static bool compareStructure(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
static bool compareStructure(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:697
Parameters
- const llvm::IRSimilarity::IRSimilarityCandidate& A
- - The first IRInstructionCandidate to compare.
- const llvm::IRSimilarity::IRSimilarityCandidate& B
- - The second IRInstructionCandidate to compare.
Returns
True when every IRInstructionData in \p A is structurally similar to \p B.
¶static bool compareStructure(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ValueNumberMappingA,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ValueNumberMappingB)
static bool compareStructure(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ValueNumberMappingA,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ValueNumberMappingB)
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:709
Parameters
- const llvm::IRSimilarity::IRSimilarityCandidate& A
- - The first IRInstructionCandidate to compare.
- const llvm::IRSimilarity::IRSimilarityCandidate& B
- - The second IRInstructionCandidate to compare.
- DenseMap<unsigned int, DenseSet<unsigned int>>& ValueNumberMappingA
- - A mapping of value numbers from candidate \p A to candidate \B.
- DenseMap<unsigned int, DenseSet<unsigned int>>& ValueNumberMappingB
- - A mapping of value numbers from candidate \p B to candidate \A.
Returns
True when every IRInstructionData in \p A is structurally similar to \p B.
¶static void createCanonicalMappingFor(
llvm::IRSimilarity::IRSimilarityCandidate&
CurrCand)
static void createCanonicalMappingFor(
llvm::IRSimilarity::IRSimilarityCandidate&
CurrCand)
Description
Create a mapping from the value numbering to a different separate set of numbers. This will serve as a guide for relating one candidate to another. The canonical number gives use the ability identify which global value number in one candidate relates to the global value number in the other.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:810
Parameters
- llvm::IRSimilarity::IRSimilarityCandidate& CurrCand
- - The IRSimilarityCandidate to create a canonical numbering for.
¶void createCanonicalRelationFrom(
llvm::IRSimilarity::IRSimilarityCandidate&
SourceCand,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ToSourceMapping,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
FromSourceMapping)
void createCanonicalRelationFrom(
llvm::IRSimilarity::IRSimilarityCandidate&
SourceCand,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
ToSourceMapping,
DenseMap<unsigned int,
DenseSet<unsigned int>>&
FromSourceMapping)
Description
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in \p SourceCand. These are defined based on the found mappings in \p ToSourceMapping and \p FromSourceMapping. Both of these relationships should have the same information, just in opposite directions.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:825
Parameters
- llvm::IRSimilarity::IRSimilarityCandidate& SourceCand
- - The IRSimilarityCandidate to create a canonical numbering from.
- DenseMap<unsigned int, DenseSet<unsigned int>>& ToSourceMapping
- - The mapping of value numbers from this candidate to \p SourceCand.
- DenseMap<unsigned int, DenseSet<unsigned int>>& FromSourceMapping
- - The mapping of value numbers from \p SoureCand to this candidate.
¶llvm::IRSimilarity::IRSimilarityCandidate::
iterator
end() const
llvm::IRSimilarity::IRSimilarityCandidate::
iterator
end() const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:946
¶Optional<unsigned int> fromCanonicalNum(
unsigned int N)
Optional<unsigned int> fromCanonicalNum(
unsigned int N)
Description
Find the global value number from the canonical number \p N stored in the candidate.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:930
Parameters
- unsigned int N
- - The canonical number to find the global vlaue number for.
Returns
An optional containing the value, and None if it could not be found.
¶Optional<llvm::Value*> fromGVN(unsigned int Num)
Optional<llvm::Value*> fromGVN(unsigned int Num)
Description
Finds the Value associate with \p Num if it exists.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:903
Parameters
- unsigned int Num
- - the number to find.
Returns
None if not present.
¶llvm::IRSimilarity::IRInstructionData* front()
const
llvm::IRSimilarity::IRInstructionData* front()
const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:870
Returns
The first IRInstructionData.
¶llvm::Instruction* frontInstruction()
llvm::Instruction* frontInstruction()
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:875
Returns
The first Instruction.
¶void getBasicBlocks(
DenseSet<llvm::BasicBlock*>& BBSet,
SmallVector<llvm::BasicBlock*>& BBList) const
void getBasicBlocks(
DenseSet<llvm::BasicBlock*>& BBSet,
SmallVector<llvm::BasicBlock*>& BBList) const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:840
Parameters
- DenseSet<llvm::BasicBlock*>& BBSet
- - The set to track the basic blocks.
- SmallVector<llvm::BasicBlock*>& BBList
- - A list in order of use to track the basic blocks.
¶void getBasicBlocks(
DenseSet<llvm::BasicBlock*>& BBSet) const
void getBasicBlocks(
DenseSet<llvm::BasicBlock*>& BBSet) const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:831
Parameters
- DenseSet<llvm::BasicBlock*>& BBSet
- - The set to track the basic blocks.
¶Optional<unsigned int> getCanonicalNum(
unsigned int N)
Optional<unsigned int> getCanonicalNum(
unsigned int N)
Description
Find the canonical number from the global value number \p N stored in the candidate.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:917
Parameters
- unsigned int N
- - The global value number to find the canonical number for.
Returns
An optional containing the value, and None if it could not be found.
¶llvm::BasicBlock* getEndBB()
llvm::BasicBlock* getEndBB()
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:882
Returns
The BasicBlock the IRSimilarityCandidate ends in.
¶unsigned int getEndIdx() const
unsigned int getEndIdx() const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:867
Returns
the end index of this IRSimilarityCandidate.
¶llvm::Function* getFunction()
llvm::Function* getFunction()
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:885
Returns
The Function that the IRSimilarityCandidate is located in.
¶Optional<unsigned int> getGVN(llvm::Value* V)
Optional<unsigned int> getGVN(llvm::Value* V)
Description
Finds the positive number associated with \p V if it has been mapped.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:891
Parameters
- llvm::Value* V
- - the Value to find.
Returns
None if not present.
¶unsigned int getLength() const
unsigned int getLength() const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:861
Returns
the number of instructions in this Candidate.
¶llvm::BasicBlock* getStartBB()
llvm::BasicBlock* getStartBB()
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:880
Returns
The BasicBlock the IRSimilarityCandidate starts in.
¶unsigned int getStartIdx() const
unsigned int getStartIdx() const
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:864
Returns
the start index of this IRSimilarityCandidate.
¶static bool isSimilar(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
static bool isSimilar(
const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:690
Parameters
- const llvm::IRSimilarity::IRSimilarityCandidate& A
- - The first IRInstructionCandidate to compare.
- const llvm::IRSimilarity::IRSimilarityCandidate& B
- - The second IRInstructionCandidate to compare.
Returns
True when every IRInstructionData in \p A is similar to every IRInstructionData in \p B.
¶static bool overlap(const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
static bool overlap(const llvm::IRSimilarity::
IRSimilarityCandidate& A,
const llvm::IRSimilarity::
IRSimilarityCandidate& B)
Description
Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap. If the start instruction of one IRSimilarityCandidate is less than the end instruction of the other, and the start instruction of one is greater than the start instruction of the other, they overlap.
Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:857
Parameters
- const llvm::IRSimilarity::IRSimilarityCandidate& A
- const llvm::IRSimilarity::IRSimilarityCandidate& B
Returns
true if the IRSimilarityCandidates do not have overlapping instructions.