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

#include "llvm/Analysis/IRSimilarityIdentifier.h"

Classes
struct	InstructionClassification
	Custom InstVisitor to classify different instructions for whether it can be analyzed for similarity. More...

Public Member Functions
IRInstructionData *	allocateIRInstructionData (Instruction &I, bool Legality, IRInstructionDataList &IDL)
	Get an allocated IRInstructionData struct using the InstDataAllocator.

IRInstructionData *	allocateIRInstructionData (IRInstructionDataList &IDL)
	Get an empty allocated IRInstructionData struct using the InstDataAllocator.

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

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

unsigned	mapToLegalUnsigned (BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)
	Maps an Instruction to a legal integer.

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.

Detailed Description

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.

Constructor & Destructor Documentation

◆ IRInstructionMapper()

llvm::IRSimilarity::IRInstructionMapper::IRInstructionMapper	(	SpecificBumpPtrAllocator< IRInstructionData > *	IDA,
		SpecificBumpPtrAllocator< IRInstructionDataList > *	IDLA
	)

inline

Definition at line 503 of file IRSimilarityIdentifier.h.

References assert(), IDL, and IDLAllocator.

Member Function Documentation

◆ allocateIRInstructionData() [1/2]

IRInstructionData * IRInstructionMapper::allocateIRInstructionData	(	Instruction &	I,
		bool	Legality,
		IRInstructionDataList &	IDL
	)

Get an allocated IRInstructionData struct using the InstDataAllocator.

Parameters

I	- The Instruction to wrap with IRInstructionData.
Legality	- A boolean value that is true if the instruction is to be considered for similarity, and false if not.
IDL	- The InstructionDataList that the IRInstructionData is inserted into.

Returns: An allocated IRInstructionData struct.

Definition at line 376 of file IRSimilarityIdentifier.cpp.

References I, IDL, and InstDataAllocator.

Referenced by mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ allocateIRInstructionData() [2/2]

IRInstructionData * IRInstructionMapper::allocateIRInstructionData ( IRInstructionDataList & IDL )

Get an empty allocated IRInstructionData struct using the InstDataAllocator.

Parameters

IDL	- The InstructionDataList that the IRInstructionData is inserted into.

Returns: An allocated IRInstructionData struct.

Definition at line 382 of file IRSimilarityIdentifier.cpp.

References IDL, and InstDataAllocator.

◆ allocateIRInstructionDataList()

IRInstructionDataList * IRInstructionMapper::allocateIRInstructionDataList ( )

Get an allocated IRInstructionDataList object using the IDLAllocator.

Returns: An allocated IRInstructionDataList object.

Definition at line 387 of file IRSimilarityIdentifier.cpp.

References IDLAllocator.

◆ convertToUnsignedVec()

void IRInstructionMapper::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.

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 290 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(), mapToLegalUnsigned(), llvm::simple_ilist< T, Options >::push_back(), and llvm::InstVisitor< SubClass, RetTy >::visit().

◆ 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 455 of file IRSimilarityIdentifier.h.

References BasicBlockToInteger, and F.

Referenced by initializeForBBs().

◆ initializeForBBs() [2/2]

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

inline

Assigns values to all the basic blocks in Module M.

Parameters

M	- The module containing the basic blocks to assign numbers to.

Definition at line 462 of file IRSimilarityIdentifier.h.

References F, and initializeForBBs().

◆ mapToIllegalUnsigned()

unsigned IRInstructionMapper::mapToIllegalUnsigned	(	BasicBlock::iterator &	It,
		std::vector< unsigned > &	IntegerMappingForBB,
		std::vector< IRInstructionData * > &	InstrListForBB,
		bool	End = `false`
	)

Maps an Instruction to an illegal 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 IRInstructionData to append to.
	End	- true if creating a dummy IRInstructionData at the end of a basic block.

Returns: The integer It was mapped to.

Definition at line 393 of file IRSimilarityIdentifier.cpp.

References AddedIllegalLastTime, allocateIRInstructionData(), assert(), CanCombineWithPrevInstr, End, IDL, IllegalInstrNumber, and LegalInstrNumber.

Referenced by convertToUnsignedVec().

◆ mapToLegalUnsigned()

unsigned IRInstructionMapper::mapToLegalUnsigned	(	BasicBlock::iterator &	It,
		std::vector< unsigned > &	IntegerMappingForBB,
		std::vector< IRInstructionData * > &	InstrListForBB
	)

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 322 of file IRSimilarityIdentifier.cpp.

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

Referenced by convertToUnsignedVec().

Member Data Documentation

◆ AddedIllegalLastTime

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

Set if we added an illegal number in the previous step.

Since each illegal number is unique, we only need one of them between each range of legal numbers. This lets us make sure we don't add more than one illegal number per range.

Definition at line 401 of file IRSimilarityIdentifier.h.

Referenced by convertToUnsignedVec(), mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ BasicBlockToInteger

DenseMap<BasicBlock *, unsigned> llvm::IRSimilarity::IRInstructionMapper::BasicBlockToInteger

A mapping for a basic block in a module to its assigned number/location in the module.

Definition at line 395 of file IRSimilarityIdentifier.h.

Referenced by initializeForBBs(), and mapToLegalUnsigned().

◆ CanCombineWithPrevInstr

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

Marks whether we found a illegal instruction in the previous step.

Definition at line 404 of file IRSimilarityIdentifier.h.

Referenced by mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ EnableMatchCallsByName

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

Marks whether we should use exact function names, as well as types to find similarity between calls.

Definition at line 412 of file IRSimilarityIdentifier.h.

Referenced by llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity(), and mapToLegalUnsigned().

◆ HaveLegalRange

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

Marks whether we have found a set of instructions that is long enough to be considered for similarity.

Definition at line 408 of file IRSimilarityIdentifier.h.

Referenced by mapToLegalUnsigned().

◆ IDL

IRInstructionDataList* llvm::IRSimilarity::IRInstructionMapper::IDL = nullptr

Definition at line 448 of file IRSimilarityIdentifier.h.

Referenced by allocateIRInstructionData(), convertToUnsignedVec(), IRInstructionMapper(), mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ IDLAllocator

SpecificBumpPtrAllocator<IRInstructionDataList>* llvm::IRSimilarity::IRInstructionMapper::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.

Definition at line 422 of file IRSimilarityIdentifier.h.

Referenced by allocateIRInstructionDataList(), and IRInstructionMapper().

◆ IllegalInstrNumber

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

The starting illegal instruction number to map to.

Set to -3 for compatibility with DenseMapInfo<unsigned>.

Definition at line 384 of file IRSimilarityIdentifier.h.

Referenced by createCandidatesFromSuffixTree(), mapToIllegalUnsigned(), and mapToLegalUnsigned().

◆ InstClassifier

InstructionClassification llvm::IRSimilarity::IRInstructionMapper::InstClassifier

Maps an Instruction to a member of InstrType.

Definition at line 608 of file IRSimilarityIdentifier.h.

Referenced by convertToUnsignedVec(), and llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity().

◆ InstDataAllocator

SpecificBumpPtrAllocator<IRInstructionData>* llvm::IRSimilarity::IRInstructionMapper::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.

Definition at line 417 of file IRSimilarityIdentifier.h.

Referenced by allocateIRInstructionData().

◆ InstructionIntegerMap

DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits> llvm::IRSimilarity::IRInstructionMapper::InstructionIntegerMap

Correspondence from IRInstructionData to unsigned integers.

Definition at line 391 of file IRSimilarityIdentifier.h.

Referenced by mapToLegalUnsigned().

◆ LegalInstrNumber

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

The next available integer to assign to a legal Instruction to.

Definition at line 387 of file IRSimilarityIdentifier.h.

Referenced by mapToIllegalUnsigned(), and mapToLegalUnsigned().

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

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

Classes

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ IRInstructionMapper()

Member Function Documentation

◆ allocateIRInstructionData() [1/2]

◆ allocateIRInstructionData() [2/2]

◆ allocateIRInstructionDataList()

◆ convertToUnsignedVec()

◆ initializeForBBs() [1/2]

◆ initializeForBBs() [2/2]

◆ mapToIllegalUnsigned()

◆ mapToLegalUnsigned()

Member Data Documentation

◆ AddedIllegalLastTime

◆ BasicBlockToInteger

◆ CanCombineWithPrevInstr

◆ EnableMatchCallsByName

◆ HaveLegalRange

◆ IDL

◆ IDLAllocator

◆ IllegalInstrNumber

◆ InstClassifier

◆ InstDataAllocator

◆ InstructionIntegerMap

◆ LegalInstrNumber