LLVM 20.0.0git
|
This provides the utilities for hashing an Instruction to an unsigned integer. More...
#include "llvm/Analysis/IRSimilarityIdentifier.h"
Public Member Functions | |
IRInstructionData (Instruction &I, bool Legality, IRInstructionDataList &IDL) | |
Gather the information that is difficult to gather for an Instruction, or is changed. | |
IRInstructionData (IRInstructionDataList &IDL) | |
void | initializeInstruction () |
Fills data stuctures for IRInstructionData when it is constructed from a. | |
CmpInst::Predicate | getPredicate () const |
Get the predicate that the compare instruction is using for hashing the instruction. | |
StringRef | getCalleeName () const |
Get the callee name that the call instruction is using for hashing the instruction. | |
void | setBranchSuccessors (DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger) |
For an IRInstructionData containing a branch, finds the relative distances from the source basic block to the target by taking the difference of the number assigned to the current basic block and the target basic block of the branch. | |
void | setCalleeName (bool MatchByName=true) |
For an IRInstructionData containing a CallInst, set the function name appropriately. | |
void | setPHIPredecessors (DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger) |
For an IRInstructionData containing a PHINode, finds the relative distances from the incoming basic block to the current block by taking the difference of the number assigned to the current basic block and the incoming basic block of the branch. | |
ArrayRef< Value * > | getBlockOperVals () |
Get the BasicBlock based operands for PHINodes and BranchInsts. | |
Public Member Functions inherited from llvm::ilist_node_impl< OptionsT > | |
self_iterator | getIterator () |
const_self_iterator | getIterator () const |
reverse_self_iterator | getReverseIterator () |
const_reverse_self_iterator | getReverseIterator () const |
bool | isSentinel () const |
Check whether this is the sentinel node. | |
Public Member Functions inherited from llvm::ilist_detail::node_parent_access< ilist_node_impl< OptionsT >, OptionsT::parent_ty > | |
const OptionsT::parent_ty * | getParent () const |
OptionsT::parent_ty * | getParent () |
void | setParent (OptionsT::parent_ty *Parent) |
Static Public Member Functions | |
static CmpInst::Predicate | predicateForConsistency (CmpInst *CI) |
A function that swaps the predicates to their less than form if they are in a greater than form. | |
Public Attributes | |
Instruction * | Inst = nullptr |
The source Instruction that is being wrapped. | |
SmallVector< Value *, 4 > | OperVals |
The values of the operands in the Instruction. | |
bool | Legal = false |
The legality of the wrapped instruction. | |
std::optional< CmpInst::Predicate > | RevisedPredicate |
This is only relevant if we are wrapping a CmpInst where we needed to change the predicate of a compare instruction from a greater than form to a less than form. | |
std::optional< std::string > | CalleeName |
This is only relevant if we are wrapping a CallInst. | |
SmallVector< int, 4 > | RelativeBlockLocations |
This structure holds the distances of how far "ahead of" or "behind" the target blocks of a branch, or the incoming blocks of a phi nodes are. | |
IRInstructionDataList * | IDL = nullptr |
Friends | |
hash_code | hash_value (const IRInstructionData &ID) |
Hashes Value based on its opcode, types, and operand types. | |
Additional Inherited Members | |
Protected Types inherited from llvm::ilist_node_impl< OptionsT > | |
using | self_iterator = typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, false, false >::type |
using | const_self_iterator = typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, false, true >::type |
using | reverse_self_iterator = typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, true, false >::type |
using | const_reverse_self_iterator = typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, true, true >::type |
Protected Member Functions inherited from llvm::ilist_node_impl< OptionsT > | |
ilist_node_impl ()=default | |
This provides the utilities for hashing an Instruction to an unsigned integer.
Two IRInstructionDatas produce the same hash value when their underlying Instructions perform the same operation (even if they don't have the same input operands.) As a more concrete example, consider the following:
so:
This hashing scheme will be used to represent the program as a very long string. This string can then be placed in a data structure which can be used for similarity queries.
TODO: Handle types of Instructions which can be equal even with different operands. (E.g. comparisons with swapped predicates.) TODO: Handle CallInsts, which are only checked for function type by isSameOperationAs. TODO: Handle GetElementPtrInsts, as some of the operands have to be the exact same, and some do not.
Definition at line 115 of file IRSimilarityIdentifier.h.
IRInstructionData::IRInstructionData | ( | Instruction & | I, |
bool | Legality, | ||
IRInstructionDataList & | IDL | ||
) |
Gather the information that is difficult to gather for an Instruction, or is changed.
i.e. the operands of an Instruction and the Types of those operands. This extra information allows for similarity matching to make assertions that allow for more flexibility when checking for whether an Instruction performs the same operation.
Definition at line 49 of file IRSimilarityIdentifier.cpp.
References initializeInstruction().
IRInstructionData::IRInstructionData | ( | IRInstructionDataList & | IDL | ) |
Definition at line 85 of file IRSimilarityIdentifier.cpp.
Get the BasicBlock based operands for PHINodes and BranchInsts.
Definition at line 113 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), Inst, and OperVals.
Referenced by setBranchSuccessors().
StringRef IRInstructionData::getCalleeName | ( | ) | const |
Get the callee name that the call instruction is using for hashing the instruction.
The IRInstructionData must be wrapping a CallInst.
Definition at line 212 of file IRSimilarityIdentifier.cpp.
References assert(), CalleeName, and Inst.
CmpInst::Predicate IRInstructionData::getPredicate | ( | ) | const |
Get the predicate that the compare instruction is using for hashing the instruction.
the IRInstructionData must be wrapping a CmpInst.
Definition at line 202 of file IRSimilarityIdentifier.cpp.
References assert(), Inst, and RevisedPredicate.
void IRInstructionData::initializeInstruction | ( | ) |
Fills data stuctures for IRInstructionData when it is constructed from a.
Definition at line 55 of file IRSimilarityIdentifier.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, llvm::SmallVectorImpl< T >::insert(), Inst, llvm::User::operands(), OperVals, predicateForConsistency(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and RevisedPredicate.
Referenced by IRInstructionData().
|
static |
A function that swaps the predicates to their less than form if they are in a greater than form.
Otherwise, the predicate is unchanged.
CI | - The comparison operation to find a consistent preidcate for. |
Definition at line 186 of file IRSimilarityIdentifier.cpp.
References llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_UGE, llvm::CmpInst::FCMP_UGT, llvm::CmpInst::getPredicate(), llvm::CmpInst::getSwappedPredicate(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_UGE, and llvm::CmpInst::ICMP_UGT.
Referenced by initializeInstruction().
void IRInstructionData::setBranchSuccessors | ( | DenseMap< BasicBlock *, unsigned > & | BasicBlockToInteger | ) |
For an IRInstructionData containing a branch, finds the relative distances from the source basic block to the target by taking the difference of the number assigned to the current basic block and the target basic block of the branch.
BasicBlockToInteger | - The mapping of basic blocks to their location in the module. |
Definition at line 88 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), getBlockOperVals(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), Inst, llvm::SmallVectorTemplateBase< T, bool >::push_back(), RelativeBlockLocations, and llvm::Successor.
For an IRInstructionData containing a CallInst, set the function name appropriately.
This will be an empty string if it is an indirect call, or we are not matching by name of the called function. It will be the name of the function if MatchByName
is true and it is not an indirect call. We may decide not to match by name in order to expand the size of the regions we can match. If a function name has the same type signature, but the different name, the region of code is still almost the same. Since function names can be treated as constants, the name itself could be extrapolated away. However, matching by name provides a specificity and more "identical" code than not matching by name.
MatchByName | - A flag to mark whether we are using the called function name as a differentiating parameter. |
Definition at line 132 of file IRSimilarityIdentifier.cpp.
References assert(), CalleeName, llvm::CallBase::getCalledFunction(), llvm::Value::getName(), llvm::Intrinsic::getName(), II, Inst, llvm::CallBase::isIndirectCall(), llvm::Intrinsic::isOverloaded(), llvm::FunctionType::params(), and llvm::StringRef::str().
void IRInstructionData::setPHIPredecessors | ( | DenseMap< BasicBlock *, unsigned > & | BasicBlockToInteger | ) |
For an IRInstructionData containing a PHINode, finds the relative distances from the incoming basic block to the current block by taking the difference of the number assigned to the current basic block and the incoming basic block of the branch.
BasicBlockToInteger | - The mapping of basic blocks to their location in the module. |
Definition at line 159 of file IRSimilarityIdentifier.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), Idx, Inst, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and RelativeBlockLocations.
|
friend |
Hashes Value
based on its opcode, types, and operand types.
Two IRInstructionData instances produce the same hash when they perform the same operation.
As a simple example, consider the following instructions.
Because the first two adds operate the same types, and are performing the same action, they will be hashed to the same value.
However, the subtraction instruction is not the same as an addition, and will be hashed to a different value.
Finally, the last add has a different type compared to the first two add instructions, so it will also be hashed to a different value that any of the previous instructions.
[in] | ID | - The IRInstructionData instance to be hashed. |
Definition at line 261 of file IRSimilarityIdentifier.h.
std::optional<std::string> llvm::IRSimilarity::IRInstructionData::CalleeName |
This is only relevant if we are wrapping a CallInst.
If we are requiring that the function calls have matching names as well as types, and the call is not an indirect call, this will hold the name of the function. If it is an indirect string, it will be the empty string. However, if this requirement is not in place it will be the empty string regardless of the function call type. The value held here is used to create the hash of the instruction, and check to make sure two instructions are close to one another.
Definition at line 141 of file IRSimilarityIdentifier.h.
Referenced by getCalleeName(), and setCalleeName().
IRInstructionDataList* llvm::IRSimilarity::IRInstructionData::IDL = nullptr |
Definition at line 300 of file IRSimilarityIdentifier.h.
Instruction* llvm::IRSimilarity::IRInstructionData::Inst = nullptr |
The source Instruction that is being wrapped.
Definition at line 119 of file IRSimilarityIdentifier.h.
Referenced by llvm::IRSimilarity::IRSimilarityCandidate::backInstruction(), llvm::IRSimilarity::IRSimilarityCandidate::frontInstruction(), getBlockOperVals(), getCalleeName(), llvm::IRSimilarity::IRSimilarityCandidate::getEndBB(), getPredicate(), llvm::IRSimilarity::IRSimilarityCandidate::getStartBB(), initializeInstruction(), setBranchSuccessors(), setCalleeName(), and setPHIPredecessors().
bool llvm::IRSimilarity::IRInstructionData::Legal = false |
The legality of the wrapped instruction.
This is informed by InstrType, and is used when checking when two instructions are considered similar. If either instruction is not legal, the instructions are automatically not considered similar.
Definition at line 126 of file IRSimilarityIdentifier.h.
SmallVector<Value *, 4> llvm::IRSimilarity::IRInstructionData::OperVals |
The values of the operands in the Instruction.
Definition at line 121 of file IRSimilarityIdentifier.h.
Referenced by getBlockOperVals(), and initializeInstruction().
SmallVector<int, 4> llvm::IRSimilarity::IRInstructionData::RelativeBlockLocations |
This structure holds the distances of how far "ahead of" or "behind" the target blocks of a branch, or the incoming blocks of a phi nodes are.
If the value is negative, it means that the block was registered before the block of this instruction in terms of blocks in the function. Code Example:
Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is "ahead" of block_2.
Definition at line 165 of file IRSimilarityIdentifier.h.
Referenced by setBranchSuccessors(), and setPHIPredecessors().
std::optional<CmpInst::Predicate> llvm::IRSimilarity::IRInstructionData::RevisedPredicate |
This is only relevant if we are wrapping a CmpInst where we needed to change the predicate of a compare instruction from a greater than form to a less than form.
It is std::nullopt otherwise.
Definition at line 131 of file IRSimilarityIdentifier.h.
Referenced by getPredicate(), and initializeInstruction().