LLVM  14.0.0git
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
llvm::IRSimilarity::IRSimilarityCandidate Class Reference

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. More...
 
void getBasicBlocks (DenseSet< BasicBlock * > &BBSet) const
 
void getBasicBlocks (DenseSet< BasicBlock * > &BBSet, SmallVector< BasicBlock * > &BBList) const
 
unsigned getLength () const
 
unsigned getStartIdx () const
 
unsigned getEndIdx () const
 
IRInstructionDatafront () const
 
IRInstructionDataback () const
 
InstructionfrontInstruction ()
 
InstructionbackInstruction ()
 
BasicBlockgetStartBB ()
 
BasicBlockgetEndBB ()
 
FunctiongetFunction ()
 
Optional< unsigned > getGVN (Value *V)
 Finds the positive number associated with V if it has been mapped. More...
 
Optional< Value * > fromGVN (unsigned Num)
 Finds the Value associate with Num if it exists. More...
 
Optional< unsigned > getCanonicalNum (unsigned N)
 Find the canonical number from the global value number N stored in the candidate. More...
 
Optional< unsigned > fromCanonicalNum (unsigned N)
 Find the global value number from the canonical number N stored in the candidate. More...
 
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. More...
 
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. More...
 
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. More...
 
static void createCanonicalMappingFor (IRSimilarityCandidate &CurrCand)
 Create a mapping from the value numbering to a different separate set of numbers. More...
 
static bool overlap (const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
 Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap. More...
 

Detailed 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 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 549 of file IRSimilarityIdentifier.h.

Member Typedef Documentation

◆ iterator

Definition at line 849 of file IRSimilarityIdentifier.h.

Constructor & Destructor Documentation

◆ IRSimilarityCandidate()

IRSimilarityCandidate::IRSimilarityCandidate ( unsigned  StartIdx,
unsigned  Len,
IRInstructionData FirstInstIt,
IRInstructionData LastInstIt 
)
Parameters
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 325 of file IRSimilarityIdentifier.cpp.

References Arg, assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Member Function Documentation

◆ back()

IRInstructionData* llvm::IRSimilarity::IRSimilarityCandidate::back ( ) const
inline
Returns
The last IRInstructionData.

Definition at line 777 of file IRSimilarityIdentifier.h.

Referenced by end().

◆ backInstruction()

Instruction* llvm::IRSimilarity::IRSimilarityCandidate::backInstruction ( )
inline
Returns
The last Instruction

Definition at line 782 of file IRSimilarityIdentifier.h.

References llvm::IRSimilarity::IRInstructionData::Inst.

◆ begin()

iterator llvm::IRSimilarity::IRSimilarityCandidate::begin ( ) const
inline

Definition at line 850 of file IRSimilarityIdentifier.h.

References front().

◆ checkRelativeLocations()

bool IRSimilarityCandidate::checkRelativeLocations ( RelativeLocMapping  A,
RelativeLocMapping  B 
)
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:

br i1 %0, label %block_1, label %block_3
block_0:
br i1 %0, label %block_1, label %block_2
block_1:
br i1 %0, label %block_2, label %block_3
block_2:
br i1 %1, label %block_1, label %block_4
block_3:
br i1 %2, label %block_2, label %block_5

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.

Parameters
A- The first IRInstructionCandidate, relative location value, and incoming block.
B- The second IRInstructionCandidate, relative location value, and incoming block.
Returns
true if the relative locations match.

Definition at line 614 of file IRSimilarityIdentifier.cpp.

References B, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end(), and llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::find().

Referenced by compareStructure().

◆ compareCommutativeOperandMapping()

bool IRSimilarityCandidate::compareCommutativeOperandMapping ( OperandMapping  A,
OperandMapping  B 
)
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.

Parameters
A- The first IRInstructionCandidate, operand values, and current operand mappings to compare.
B- The second IRInstructionCandidate, operand values, and current operand mappings to compare.
Returns
true if the IRSimilarityCandidates operands are compatible.

Definition at line 579 of file IRSimilarityIdentifier.cpp.

References B, checkNumberingAndReplaceCommutative(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().

Referenced by compareStructure().

◆ compareNonCommutativeOperandMapping()

bool IRSimilarityCandidate::compareNonCommutativeOperandMapping ( OperandMapping  A,
OperandMapping  B 
)
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.

Parameters
A- The first IRInstructionCandidate, operand values, and current operand mappings to compare.
B- The second IRInstructionCandidate, operand values, and current operand mappings to compare.
Returns
true if the IRSimilarityCandidates operands are compatible.

Definition at line 545 of file IRSimilarityIdentifier.cpp.

References B, checkNumberingAndReplace(), and if().

Referenced by compareStructure().

◆ compareStructure() [1/2]

bool IRSimilarityCandidate::compareStructure ( const IRSimilarityCandidate A,
const IRSimilarityCandidate B 
)
static
Parameters
[in]A- The first IRInstructionCandidate to compare.
[in]B- The second IRInstructionCandidate to compare.
Returns
True when every IRInstructionData in A is structurally similar to B.

Definition at line 642 of file IRSimilarityIdentifier.cpp.

References B.

Referenced by findCandidateStructures().

◆ compareStructure() [2/2]

bool IRSimilarityCandidate::compareStructure ( const IRSimilarityCandidate A,
const IRSimilarityCandidate B,
DenseMap< unsigned, DenseSet< unsigned >> &  ValueNumberMappingA,
DenseMap< unsigned, DenseSet< unsigned >> &  ValueNumberMappingB 
)
static
Parameters
[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.
Returns
True when every IRInstructionData in A is structurally similar to B.

Definition at line 654 of file IRSimilarityIdentifier.cpp.

References llvm::any_of(), B, checkRelativeLocations(), compareCommutativeOperandMapping(), compareNonCommutativeOperandMapping(), llvm::IRSimilarity::isClose(), llvm::Instruction::isCommutative(), llvm::ArrayRef< T >::size(), and llvm::zip().

◆ createCanonicalMappingFor()

void IRSimilarityCandidate::createCanonicalMappingFor ( IRSimilarityCandidate CurrCand)
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.

Parameters
[in,out]CurrCand- The IRSimilarityCandidate to create a canonical numbering for.

Definition at line 929 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().

◆ createCanonicalRelationFrom()

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.

Parameters
[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 868 of file IRSimilarityIdentifier.cpp.

References assert(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::end(), 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 >::find(), getCanonicalNum(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size().

◆ end()

iterator llvm::IRSimilarity::IRSimilarityCandidate::end ( ) const
inline

Definition at line 851 of file IRSimilarityIdentifier.h.

References back().

◆ fromCanonicalNum()

Optional<unsigned> llvm::IRSimilarity::IRSimilarityCandidate::fromCanonicalNum ( unsigned  N)
inline

Find the global value number from the canonical number N stored in the candidate.

Parameters
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.

Definition at line 835 of file IRSimilarityIdentifier.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), N, and llvm::None.

◆ fromGVN()

Optional<Value *> llvm::IRSimilarity::IRSimilarityCandidate::fromGVN ( unsigned  Num)
inline

◆ front()

IRInstructionData* llvm::IRSimilarity::IRSimilarityCandidate::front ( ) const
inline
Returns
The first IRInstructionData.

Definition at line 775 of file IRSimilarityIdentifier.h.

Referenced by begin().

◆ frontInstruction()

Instruction* llvm::IRSimilarity::IRSimilarityCandidate::frontInstruction ( )
inline
Returns
The first Instruction.

Definition at line 780 of file IRSimilarityIdentifier.h.

References llvm::IRSimilarity::IRInstructionData::Inst.

◆ getBasicBlocks() [1/2]

void llvm::IRSimilarity::IRSimilarityCandidate::getBasicBlocks ( DenseSet< BasicBlock * > &  BBSet) const
inline

◆ getBasicBlocks() [2/2]

void llvm::IRSimilarity::IRSimilarityCandidate::getBasicBlocks ( DenseSet< BasicBlock * > &  BBSet,
SmallVector< BasicBlock * > &  BBList 
) const
inline

◆ getCanonicalNum()

Optional<unsigned> llvm::IRSimilarity::IRSimilarityCandidate::getCanonicalNum ( unsigned  N)
inline

Find the canonical number from the global value number N stored in the candidate.

Parameters
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.

Definition at line 822 of file IRSimilarityIdentifier.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), N, and llvm::None.

Referenced by createCanonicalRelationFrom().

◆ getEndBB()

BasicBlock* llvm::IRSimilarity::IRSimilarityCandidate::getEndBB ( )
inline

◆ getEndIdx()

unsigned llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx ( ) const
inline
Returns
the end index of this IRSimilarityCandidate.

Definition at line 772 of file IRSimilarityIdentifier.h.

◆ getFunction()

Function* llvm::IRSimilarity::IRSimilarityCandidate::getFunction ( )
inline
Returns
The Function that the IRSimilarityCandidate is located in.

Definition at line 790 of file IRSimilarityIdentifier.h.

References llvm::BasicBlock::getParent(), and getStartBB().

◆ getGVN()

Optional<unsigned> llvm::IRSimilarity::IRSimilarityCandidate::getGVN ( Value V)
inline

Finds the positive number associated with V if it has been mapped.

Parameters
[in]V- the Value to find.
Returns
The positive number corresponding to the value.
None if not present.

Definition at line 796 of file IRSimilarityIdentifier.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::None.

◆ getLength()

unsigned llvm::IRSimilarity::IRSimilarityCandidate::getLength ( ) const
inline
Returns
the number of instructions in this Candidate.

Definition at line 766 of file IRSimilarityIdentifier.h.

◆ getStartBB()

BasicBlock* llvm::IRSimilarity::IRSimilarityCandidate::getStartBB ( )
inline

◆ getStartIdx()

unsigned llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx ( ) const
inline
Returns
the start index of this IRSimilarityCandidate.

Definition at line 769 of file IRSimilarityIdentifier.h.

Referenced by operator<().

◆ isSimilar()

bool IRSimilarityCandidate::isSimilar ( const IRSimilarityCandidate A,
const IRSimilarityCandidate B 
)
static
Parameters
A- The first IRInstructionCandidate to compare.
B- The second IRInstructionCandidate to compare.
Returns
True when every IRInstructionData in A is similar to every IRInstructionData in B.

Definition at line 382 of file IRSimilarityIdentifier.cpp.

References llvm::all_of(), B, llvm::IRSimilarity::isClose(), llvm::make_range(), and llvm::zip().

◆ operator<()

bool llvm::IRSimilarity::IRSimilarityCandidate::operator< ( const IRSimilarityCandidate RHS) const
inline
Parameters
RHS-The IRSimilarityCandidate to compare against
Returns
true if the IRSimilarityCandidate is occurs after the IRSimilarityCandidate in the program.

Definition at line 845 of file IRSimilarityIdentifier.h.

References getStartIdx().

◆ overlap()

bool IRSimilarityCandidate::overlap ( const IRSimilarityCandidate A,
const IRSimilarityCandidate B 
)
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.

Returns
true if the IRSimilarityCandidates do not have overlapping instructions.

Definition at line 758 of file IRSimilarityIdentifier.cpp.

References B, X, and Y.


The documentation for this class was generated from the following files:
i1
Decimal Convert From to National Zoned Signed int_ppc_altivec_bcdcfno i1
Definition: README_P9.txt:147
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339