LLVM: llvm::IRSimilarity::IRInstructionMapper Struct Reference (original) (raw)

Helper struct for converting the Instructions in a Module into a vector of unsigned integers. More...

#include "[llvm/Analysis/IRSimilarityIdentifier.h](IRSimilarityIdentifier%5F8h%5Fsource.html)"

Public Member Functions
LLVM_ABI IRInstructionData *	allocateIRInstructionData (Instruction &I, bool Legality, IRInstructionDataList &IDL)
	Get an allocated IRInstructionData struct using the InstDataAllocator.
LLVM_ABI IRInstructionData *	allocateIRInstructionData (IRInstructionDataList &IDL)
	Get an empty allocated IRInstructionData struct using the InstDataAllocator.
LLVM_ABI IRInstructionDataList *	allocateIRInstructionDataList ()
	Get an allocated IRInstructionDataList object using the IDLAllocator.
void	initializeForBBs (Function &F, unsigned &BBNumber)
	Assigns values to all the basic blocks in function F starting from integer BBNumber.
void	initializeForBBs (Module &M)
	Assigns values to all the basic blocks in Module M.
LLVM_ABI void	convertToUnsignedVec (BasicBlock &BB, std::vector< IRInstructionData * > &InstrList, std::vector< unsigned > &IntegerMapping)
	Maps the Instructions in a BasicBlock BB to legal or illegal integers determined by InstrType.
LLVM_ABI unsigned	mapToLegalUnsigned (BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)
	Maps an Instruction to a legal integer.
LLVM_ABI unsigned	mapToIllegalUnsigned (BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB, bool End=false)
	Maps an Instruction to an illegal integer.
	IRInstructionMapper (SpecificBumpPtrAllocator< IRInstructionData > IDA, SpecificBumpPtrAllocator< IRInstructionDataList > IDLA)

Public Attributes
unsigned	IllegalInstrNumber = static_cast<unsigned>(-3)
	The starting illegal instruction number to map to.
unsigned	LegalInstrNumber = 0
	The next available integer to assign to a legal Instruction to.
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits >	InstructionIntegerMap
	Correspondence from IRInstructionData to unsigned integers.
DenseMap< BasicBlock *, unsigned >	BasicBlockToInteger
	A mapping for a basic block in a module to its assigned number/location in the module.
bool	AddedIllegalLastTime = false
	Set if we added an illegal number in the previous step.
bool	CanCombineWithPrevInstr = false
	Marks whether we found a illegal instruction in the previous step.
bool	HaveLegalRange = false
	Marks whether we have found a set of instructions that is long enough to be considered for similarity.
bool	EnableMatchCallsByName = false
	Marks whether we should use exact function names, as well as types to find similarity between calls.
SpecificBumpPtrAllocator< IRInstructionData > *	InstDataAllocator = nullptr
	This allocator pointer is in charge of holding on to the IRInstructionData so it is not deallocated until whatever external tool is using it is done with the information.
SpecificBumpPtrAllocator< IRInstructionDataList > *	IDLAllocator = nullptr
	This allocator pointer is in charge of creating the IRInstructionDataList so it is not deallocated until whatever external tool is using it is done with the information.
IRInstructionDataList *	IDL = nullptr
InstructionClassification	InstClassifier
	Maps an Instruction to a member of InstrType.

Helper struct for converting the Instructions in a Module into a vector of unsigned integers.

This vector of unsigned integers can be thought of as a "numeric string". This numeric string can then be queried by, for example, data structures that find repeated substrings.

This hashing is done per BasicBlock in the module. To hash Instructions based off of their operations, each Instruction is wrapped in an IRInstructionData struct. The unsigned integer for an IRInstructionData depends on:

The hash provided by the IRInstructionData.
Which member of InstrType the IRInstructionData is classified as. The numeric string for an individual BasicBlock is terminated by an unique unsigned integer. This prevents data structures which rely on repetition from matching across BasicBlocks. (For example, the SuffixTree.) As a concrete example, if we have the following two BasicBlocks:
bb0:
%add1 = add i32 %a, %b
%add2 = add i32 %c, %d
%add3 = add i64 %e, %f
bb1:
%sub = sub i32 %c, %d
We may hash the Instructions like this (via IRInstructionData):
bb0:
%add1 = add i32 %a, %b ; Hash: 1
%add2 = add i32 %c, %d; Hash: 1
%add3 = add i64 %e, %f; Hash: 2
bb1:
%sub = sub i32 %c, %d; Hash: 3
%add4 = add i32 %c, %d ; Hash: 1
And produce a "numeric string representation" like so: 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2

TODO: This is very similar to the MachineOutliner, and should be consolidated into the same interface.

Definition at line 380 of file IRSimilarityIdentifier.h.

◆ allocateIRInstructionData() [1/2]

◆ allocateIRInstructionData() [2/2]

◆ allocateIRInstructionDataList()

◆ convertToUnsignedVec()

Maps the Instructions in a BasicBlock BB to legal or illegal integers determined by [InstrType](namespacellvm%5F1%5F1IRSimilarity.html#af46430106334db52bfa7a4107e53a0bd "This represents what is and is not supported when finding similarity in Instructions.").

Two Instructions are mapped to the same value if they are close as defined by the InstructionData class above.

Parameters

[in]	BB	- The BasicBlock to be mapped to integers.
[in,out]	InstrList	- Vector of IRInstructionData to append to.
[in,out]	IntegerMapping	- Vector of unsigned integers to append to.

Definition at line 289 of file IRSimilarityIdentifier.cpp.

References AddedIllegalLastTime, llvm::append_range(), llvm::BasicBlock::begin(), llvm::BasicBlock::end(), IDL, llvm::IRSimilarity::Illegal, InstClassifier, llvm::IRSimilarity::Invisible, llvm::IRSimilarity::Legal, mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ initializeForBBs() [1/2]

void llvm::IRSimilarity::IRInstructionMapper::initializeForBBs ( Function & F, unsigned & BBNumber )	inline

Assigns values to all the basic blocks in function F starting from integer BBNumber.

Parameters

F	- The function containing the basic blocks to assign numbers to.
BBNumber	- The number to start from.

Definition at line 457 of file IRSimilarityIdentifier.h.

References BasicBlockToInteger, and F.

Referenced by initializeForBBs().

◆ initializeForBBs() [2/2]

void llvm::IRSimilarity::IRInstructionMapper::initializeForBBs ( Module & M)	inline

◆ mapToIllegalUnsigned()

◆ mapToLegalUnsigned()

Maps an Instruction to a legal integer.

Parameters

[in]	It	- The Instruction to be mapped to an integer.
[in,out]	IntegerMappingForBB	- Vector of unsigned integers to append to.
[in,out]	InstrListForBB	- Vector of InstructionData to append to.

Returns

The integer It was mapped to.

Definition at line 321 of file IRSimilarityIdentifier.cpp.

References AddedIllegalLastTime, allocateIRInstructionData(), assert(), BasicBlockToInteger, CanCombineWithPrevInstr, EnableMatchCallsByName, HaveLegalRange, IDL, IllegalInstrNumber, InstructionIntegerMap, llvm::isa(), and LegalInstrNumber.

Referenced by convertToUnsignedVec().

◆ AddedIllegalLastTime

bool llvm::IRSimilarity::IRInstructionMapper::AddedIllegalLastTime = false

◆ BasicBlockToInteger

◆ CanCombineWithPrevInstr

bool llvm::IRSimilarity::IRInstructionMapper::CanCombineWithPrevInstr = false

◆ EnableMatchCallsByName

bool llvm::IRSimilarity::IRInstructionMapper::EnableMatchCallsByName = false

◆ HaveLegalRange

bool llvm::IRSimilarity::IRInstructionMapper::HaveLegalRange = false

◆ IDL

◆ IDLAllocator

◆ IllegalInstrNumber

unsigned llvm::IRSimilarity::IRInstructionMapper::IllegalInstrNumber = static_cast<unsigned>(-3)

◆ InstClassifier

◆ InstDataAllocator

◆ InstructionIntegerMap

◆ LegalInstrNumber

unsigned llvm::IRSimilarity::IRInstructionMapper::LegalInstrNumber = 0

The documentation for this struct was generated from the following files:

include/llvm/Analysis/IRSimilarityIdentifier.h
lib/Analysis/IRSimilarityIdentifier.cpp