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)

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

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:872

Returns

The last IRInstructionData.

llvm::Instruction* backInstruction()

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:877

Returns

The last Instruction

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)

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)

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)

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)

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)

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)

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)

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

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:946

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)

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

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:870

Returns

The first IRInstructionData.

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

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

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)

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()

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:882

Returns

The BasicBlock the IRSimilarityCandidate ends in.

unsigned int getEndIdx() const

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:867

Returns

the end index of this IRSimilarityCandidate.

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)

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

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:861

Returns

the number of instructions in this Candidate.

llvm::BasicBlock* getStartBB()

Declared at: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h:880

Returns

The BasicBlock the IRSimilarityCandidate starts in.

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)

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)

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.