LLVM 20.0.0git
|
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. More...
#include "llvm/Analysis/IRSimilarityIdentifier.h"
Classes | |
struct | OperandMapping |
struct | RelativeLocMapping |
A helper struct to hold the candidate, for a branch instruction, the relative location of a label, and the label itself. More... | |
Public Types | |
using | iterator = IRInstructionDataList::iterator |
Public Member Functions | |
IRSimilarityCandidate (unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt) | |
void | createCanonicalRelationFrom (IRSimilarityCandidate &SourceCand, DenseMap< unsigned, DenseSet< unsigned > > &ToSourceMapping, DenseMap< unsigned, DenseSet< unsigned > > &FromSourceMapping) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand . | |
void | createCanonicalRelationFrom (IRSimilarityCandidate &SourceCand, DenseMap< unsigned, unsigned > &OneToOne, DenseMap< unsigned, DenseSet< unsigned > > &ToSourceMapping, DenseMap< unsigned, DenseSet< unsigned > > &FromSourceMapping) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand . | |
void | createCanonicalRelationFrom (IRSimilarityCandidate &SourceCand, IRSimilarityCandidate &SourceCandLarge, IRSimilarityCandidate &TargetCandLarge) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand . | |
void | getBasicBlocks (DenseSet< BasicBlock * > &BBSet) const |
void | getBasicBlocks (DenseSet< BasicBlock * > &BBSet, SmallVector< BasicBlock * > &BBList) const |
unsigned | getLength () const |
unsigned | getStartIdx () const |
unsigned | getEndIdx () const |
IRInstructionData * | front () const |
IRInstructionData * | back () const |
Instruction * | frontInstruction () |
Instruction * | backInstruction () |
BasicBlock * | getStartBB () |
BasicBlock * | getEndBB () |
Function * | getFunction () |
std::optional< unsigned > | getGVN (Value *V) |
Finds the positive number associated with V if it has been mapped. | |
std::optional< Value * > | fromGVN (unsigned Num) |
Finds the Value associate with Num if it exists. | |
std::optional< unsigned > | getCanonicalNum (unsigned N) |
Find the canonical number from the global value number N stored in the candidate. | |
std::optional< unsigned > | fromCanonicalNum (unsigned N) |
Find the global value number from the canonical number N stored in the candidate. | |
bool | operator< (const IRSimilarityCandidate &RHS) const |
iterator | begin () const |
iterator | end () const |
Static Public Member Functions | |
static bool | isSimilar (const IRSimilarityCandidate &A, const IRSimilarityCandidate &B) |
static bool | compareStructure (const IRSimilarityCandidate &A, const IRSimilarityCandidate &B) |
static bool | compareStructure (const IRSimilarityCandidate &A, const IRSimilarityCandidate &B, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingA, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingB) |
static bool | compareNonCommutativeOperandMapping (OperandMapping A, OperandMapping B) |
Compare the operands in A and B and check that the current mapping of global value numbers from A to B and B to \A is consistent. | |
static bool | compareCommutativeOperandMapping (OperandMapping A, OperandMapping B) |
Compare the operands in A and B and check that the current mapping of global value numbers from A to B and B to \A is consistent given that the operands are commutative. | |
static bool | compareAssignmentMapping (const unsigned InstValA, const unsigned &InstValB, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingA, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingB) |
Compare the GVN of the assignment value in corresponding instructions in IRSimilarityCandidates A and B and check that there exists a mapping between the values and replaces the mapping with a one-to-one value if needed. | |
static bool | checkRelativeLocations (RelativeLocMapping A, RelativeLocMapping B) |
Compare the relative locations in A and 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. | |
static void | createCanonicalMappingFor (IRSimilarityCandidate &CurrCand) |
Create a mapping from the value numbering to a different separate set of numbers. | |
static bool | overlap (const IRSimilarityCandidate &A, const IRSimilarityCandidate &B) |
Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap. | |
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 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.
Definition at line 654 of file IRSimilarityIdentifier.h.
Definition at line 1011 of file IRSimilarityIdentifier.h.
IRSimilarityCandidate::IRSimilarityCandidate | ( | unsigned | StartIdx, |
unsigned | Len, | ||
IRInstructionData * | FirstInstIt, | ||
IRInstructionData * | LastInstIt | ||
) |
StartIdx | - The starting location of the region. |
Len | - The length of the region. |
FirstInstIt | - The starting IRInstructionData of the region. |
LastInstIt | - The ending IRInstructionData of the region. |
Definition at line 427 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), getBasicBlocks(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().
|
inline |
Definition at line 939 of file IRSimilarityIdentifier.h.
Referenced by end().
|
inline |
Definition at line 944 of file IRSimilarityIdentifier.h.
References llvm::IRSimilarity::IRInstructionData::Inst.
Referenced by llvm::OutlinableRegion::splitCandidate().
|
inline |
Definition at line 1012 of file IRSimilarityIdentifier.h.
References front().
Referenced by llvm::OutlinableRegion::reattachCandidate(), and llvm::OutlinableRegion::splitCandidate().
|
static |
Compare the relative locations in A
and 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.
A | - The first IRInstructionCandidate, relative location value, and incoming block. |
B | - The second IRInstructionCandidate, relative location value, and incoming block. |
Definition at line 749 of file IRSimilarityIdentifier.cpp.
References A, B, and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains().
Referenced by compareStructure().
|
static |
Compare the GVN of the assignment value in corresponding instructions in IRSimilarityCandidates A
and B
and check that there exists a mapping between the values and replaces the mapping with a one-to-one value if needed.
InstValA | - The assignment GVN from the first IRSimilarityCandidate. | |
InstValB | - The assignment GVN from the second IRSimilarityCandidate. | |
[in,out] | ValueNumberMappingA | - A mapping of value numbers from candidate A to candidate \B. |
[in,out] | ValueNumberMappingB | - A mapping of value numbers from candidate B to candidate \A. |
Definition at line 721 of file IRSimilarityIdentifier.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), contains(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size().
Referenced by compareStructure().
|
static |
Compare the operands in A
and B
and check that the current mapping of global value numbers from A
to B
and B
to \A is consistent given that the operands are commutative.
A | - The first IRInstructionCandidate, operand values, and current operand mappings to compare. |
B | - The second IRInstructionCandidate, operand values, and current operand mappings to compare. |
Definition at line 686 of file IRSimilarityIdentifier.cpp.
References A, B, checkNumberingAndReplaceCommutative(), Idx, and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
Referenced by compareStructure().
|
static |
Compare the operands in A
and B
and check that the current mapping of global value numbers from A
to B
and B
to \A is consistent.
A | - The first IRInstructionCandidate, operand values, and current operand mappings to compare. |
B | - The second IRInstructionCandidate, operand values, and current operand mappings to compare. |
Definition at line 652 of file IRSimilarityIdentifier.cpp.
References A, B, checkNumberingAndReplace(), Idx, and if().
Referenced by compareStructure().
|
static |
[in] | A | - The first IRInstructionCandidate to compare. |
[in] | B | - The second IRInstructionCandidate to compare. |
A
is structurally similar to B
. Definition at line 777 of file IRSimilarityIdentifier.cpp.
References A, B, and compareStructure().
Referenced by compareStructure(), and findCandidateStructures().
|
static |
[in] | A | - The first IRInstructionCandidate to compare. |
[in] | B | - The second IRInstructionCandidate to compare. |
[in,out] | ValueNumberMappingA | - A mapping of value numbers from candidate A to candidate \B. |
[in,out] | ValueNumberMappingB | - A mapping of value numbers from candidate B to candidate \A. |
A
is structurally similar to B
. Definition at line 789 of file IRSimilarityIdentifier.cpp.
References A, llvm::any_of(), assert(), B, checkRelativeLocations(), compareAssignmentMapping(), compareCommutativeOperandMapping(), compareNonCommutativeOperandMapping(), llvm::IRSimilarity::isClose(), llvm::ArrayRef< T >::size(), llvm::SmallVectorBase< Size_T >::size(), and llvm::zip().
|
static |
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.
[in,out] | CurrCand | - The IRSimilarityCandidate to create a canonical numbering for. |
Definition at line 1174 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size().
Referenced by findCandidateStructures().
void IRSimilarityCandidate::createCanonicalRelationFrom | ( | IRSimilarityCandidate & | SourceCand, |
DenseMap< unsigned, DenseSet< unsigned > > & | ToSourceMapping, | ||
DenseMap< unsigned, DenseSet< unsigned > > & | FromSourceMapping | ||
) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand
.
These are defined based on the found mappings in ToSourceMapping
and FromSourceMapping
. Both of these relationships should have the same information, just in opposite directions.
[in,out] | SourceCand | - The IRSimilarityCandidate to create a canonical numbering from. |
ToSourceMapping | - The mapping of value numbers from this candidate to SourceCand . | |
FromSourceMapping | - The mapping of value numbers from SoureCand to this candidate. |
Definition at line 1009 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), fromCanonicalNum(), fromGVN(), frontInstruction(), getBasicBlocks(), getCanonicalNum(), getGVN(), llvm::BasicBlock::getParent(), getStartBB(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size().
void llvm::IRSimilarity::IRSimilarityCandidate::createCanonicalRelationFrom | ( | IRSimilarityCandidate & | SourceCand, |
DenseMap< unsigned, unsigned > & | OneToOne, | ||
DenseMap< unsigned, DenseSet< unsigned > > & | ToSourceMapping, | ||
DenseMap< unsigned, DenseSet< unsigned > > & | FromSourceMapping | ||
) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand
.
These are defined based on the found mappings in ToSourceMapping
and FromSourceMapping
. Both of these relationships should have the same information, just in opposite directions. Uses the OneToOne
mapping from target candidate to SourceCand
GVNs to determine the mapping first for values with multiple mappings. This mapping is created by the ordering of operands in the instruction they are first seen in the candidates.
[in,out] | SourceCand | - The IRSimilarityCandidate to create a canonical numbering from. |
[in,out] | OneToOne | - A mapping of value numbers from candidate A to candidate \B using the structure of the original instructions. |
ToSourceMapping | - The mapping of value numbers from this candidate to SourceCand . | |
FromSourceMapping | - The mapping of value numbers from SoureCand to this candidate. |
void IRSimilarityCandidate::createCanonicalRelationFrom | ( | IRSimilarityCandidate & | SourceCand, |
IRSimilarityCandidate & | SourceCandLarge, | ||
IRSimilarityCandidate & | TargetCandLarge | ||
) |
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separate set of numbers, based on the canonical ordering in SourceCand
.
These are defined based on the canonical mapping defined between SoureCandLarge
and TargetCandLarge
. These IRSimilarityCandidates are already structurally similar, and fully encapsulate the IRSimilarityCandidates in question. These are used as a "bridge" from the SourceCand
to the target.
[in,out] | SourceCand | - The IRSimilarityCandidate to create a canonical numbering from. |
SoureCandLarge | - The IRSimilarityCandidate fully containing SourceCand . | |
TargetCandLarge | - The IRSimilarityCandidate fully containing this Candidate. |
Definition at line 1104 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), fromCanonicalNum(), fromGVN(), getCanonicalNum(), getGVN(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().
|
inline |
Definition at line 1013 of file IRSimilarityIdentifier.h.
References back().
Referenced by llvm::OutlinableRegion::splitCandidate().
|
inline |
Find the global value number from the canonical number N
stored in the candidate.
N | - The canonical number to find the global vlaue number for. |
Definition at line 997 of file IRSimilarityIdentifier.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and N.
Referenced by createCanonicalRelationFrom().
Finds the Value associate with Num
if it exists.
[in] | Num | - the number to find. |
Definition at line 970 of file IRSimilarityIdentifier.h.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by createCanonicalRelationFrom().
|
inline |
Definition at line 937 of file IRSimilarityIdentifier.h.
Referenced by begin().
|
inline |
Definition at line 942 of file IRSimilarityIdentifier.h.
References llvm::IRSimilarity::IRInstructionData::Inst.
Referenced by createCanonicalRelationFrom().
|
inline |
[in,out] | BBSet | - The set to track the basic blocks. |
Definition at line 898 of file IRSimilarityIdentifier.h.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
Referenced by createCanonicalRelationFrom(), findCostForOutputBlocks(), IRSimilarityCandidate(), llvm::OutlinableRegion::reattachCandidate(), and llvm::OutlinableRegion::splitCandidate().
|
inline |
[in,out] | BBSet | - The set to track the basic blocks. |
[in,out] | BBList | - A list in order of use to track the basic blocks. |
Definition at line 907 of file IRSimilarityIdentifier.h.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
|
inline |
Find the canonical number from the global value number N
stored in the candidate.
N | - The global value number to find the canonical number for. |
Definition at line 984 of file IRSimilarityIdentifier.h.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and N.
Referenced by createCanonicalRelationFrom(), llvm::OutlinableRegion::findCorrespondingValueIn(), and getGVNForPHINode().
|
inline |
Definition at line 949 of file IRSimilarityIdentifier.h.
References llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and llvm::IRSimilarity::IRInstructionData::Inst.
|
inline |
Definition at line 934 of file IRSimilarityIdentifier.h.
Referenced by CheckLargerCands().
|
inline |
Definition at line 952 of file IRSimilarityIdentifier.h.
References llvm::BasicBlock::getParent(), and getStartBB().
Finds the positive number associated with V
if it has been mapped.
[in] | V | - the Value to find. |
Definition at line 958 of file IRSimilarityIdentifier.h.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by createCanonicalRelationFrom(), llvm::OutlinableRegion::findCorrespondingValueIn(), and getGVNForPHINode().
|
inline |
Definition at line 928 of file IRSimilarityIdentifier.h.
|
inline |
Definition at line 947 of file IRSimilarityIdentifier.h.
References llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and llvm::IRSimilarity::IRInstructionData::Inst.
Referenced by createCanonicalRelationFrom(), getFunction(), and getGVNForPHINode().
|
inline |
Definition at line 931 of file IRSimilarityIdentifier.h.
Referenced by CheckLargerCands(), and operator<().
|
static |
A | - The first IRInstructionCandidate to compare. |
B | - The second IRInstructionCandidate to compare. |
A
is similar to every IRInstructionData in B
. Definition at line 496 of file IRSimilarityIdentifier.cpp.
References A, llvm::all_of(), B, llvm::IRSimilarity::isClose(), llvm::make_range(), and llvm::zip().
|
inline |
RHS | -The IRSimilarityCandidate to compare against |
Definition at line 1007 of file IRSimilarityIdentifier.h.
References getStartIdx(), and RHS.
|
static |
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.
Definition at line 899 of file IRSimilarityIdentifier.cpp.