LLVM  14.0.0git
Classes | Public Member Functions | Public Attributes | List of all members
llvm::IRSimilarity::IRInstructionMapper Struct Reference

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

#include "llvm/Analysis/IRSimilarityIdentifier.h"

Collaboration diagram for llvm::IRSimilarity::IRInstructionMapper:
Collaboration graph
[legend]

Classes

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

Public Member Functions

IRInstructionDataallocateIRInstructionData (Instruction &I, bool Legality, IRInstructionDataList &IDL)
 Get an allocated IRInstructionData struct using the InstDataAllocator. More...
 
IRInstructionDataallocateIRInstructionData (IRInstructionDataList &IDL)
 Get an empty allocated IRInstructionData struct using the InstDataAllocator. More...
 
IRInstructionDataListallocateIRInstructionDataList ()
 Get an allocated IRInstructionDataList object using the IDLAllocator. More...
 
void initializeForBBs (Function &F, unsigned &BBNumber)
 Assigns values to all the basic blocks in function F starting from integer BBNumber. More...
 
void initializeForBBs (Module &M)
 Assigns values to all the basic blocks in Module M. More...
 
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. More...
 
unsigned mapToLegalUnsigned (BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)
 Maps an Instruction to a legal integer. More...
 
unsigned mapToIllegalUnsigned (BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB, bool End=false)
 Maps an Instruction to an illegal integer. More...
 
 IRInstructionMapper (SpecificBumpPtrAllocator< IRInstructionData > *IDA, SpecificBumpPtrAllocator< IRInstructionDataList > *IDLA)
 

Public Attributes

unsigned IllegalInstrNumber = static_cast<unsigned>(-3)
 The starting illegal instruction number to map to. More...
 
unsigned LegalInstrNumber = 0
 The next available integer to assign to a legal Instruction to. More...
 
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraitsInstructionIntegerMap
 Correspondence from IRInstructionData to unsigned integers. More...
 
DenseMap< BasicBlock *, unsigned > BasicBlockToInteger
 A mapping for a basic block in a module to its assigned number/location in the module. More...
 
bool AddedIllegalLastTime = false
 Set if we added an illegal number in the previous step. More...
 
bool CanCombineWithPrevInstr = false
 Marks whether we found a illegal instruction in the previous step. More...
 
bool HaveLegalRange = false
 Marks whether we have found a set of instructions that is long enough to be considered for similarity. More...
 
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. More...
 
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. More...
 
IRInstructionDataListIDL = nullptr
 
InstructionClassification InstClassifier
 Maps an Instruction to a member of InstrType. More...
 

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:

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

Definition at line 319 of file IRSimilarityIdentifier.h.

Constructor & Destructor Documentation

◆ IRInstructionMapper()

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

Definition at line 438 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 274 of file IRSimilarityIdentifier.cpp.

References I, IDL, and InstDataAllocator.

Referenced by 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 280 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 285 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 192 of file IRSimilarityIdentifier.cpp.

References AddedIllegalLastTime, llvm::append_range(), BB, HaveLegalRange, 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 390 of file IRSimilarityIdentifier.h.

References BasicBlockToInteger, BB, F, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

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

References F, initializeForBBs(), and M.

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

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

References AddedIllegalLastTime, allocateIRInstructionData(), assert(), BasicBlockToInteger, CanCombineWithPrevInstr, 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 340 of file IRSimilarityIdentifier.h.

Referenced by convertToUnsignedVec(), 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 334 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 343 of file IRSimilarityIdentifier.h.

Referenced by 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 347 of file IRSimilarityIdentifier.h.

Referenced by convertToUnsignedVec(), and mapToLegalUnsigned().

◆ IDL

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

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

Referenced by createCandidatesFromSuffixTree(), and mapToLegalUnsigned().

◆ InstClassifier

InstructionClassification llvm::IRSimilarity::IRInstructionMapper::InstClassifier

Maps an Instruction to a member of InstrType.

Definition at line 504 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 352 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 330 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 326 of file IRSimilarityIdentifier.h.

Referenced by mapToLegalUnsigned().


The documentation for this struct was generated from the following files:
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
i64
Clang compiles this i64
Definition: README.txt:504
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
c
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int c
Definition: README.txt:418
i32
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32
Definition: README.txt:122
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
sub
we currently eax ecx subl eax ret We would use one fewer register if codegen d eax neg eax eax ret Note that this isn t beneficial if the load can be folded into the sub In this we want a sub
Definition: README.txt:460
d
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int int d
Definition: README.txt:418