LLVM  14.0.0git
Public Member Functions | Static Public Member Functions | Public Attributes | Friends | List of all members
llvm::IRSimilarity::IRInstructionData Struct Reference

This provides the utilities for hashing an Instruction to an unsigned integer. More...

#include "llvm/Analysis/IRSimilarityIdentifier.h"

Inheritance diagram for llvm::IRSimilarity::IRInstructionData:
Inheritance graph
[legend]
Collaboration diagram for llvm::IRSimilarity::IRInstructionData:
Collaboration graph
[legend]

Public Member Functions

 IRInstructionData (Instruction &I, bool Legality, IRInstructionDataList &IDL)
 Gather the information that is difficult to gather for an Instruction, or is changed. More...
 
 IRInstructionData (IRInstructionDataList &IDL)
 
void initializeInstruction ()
 Fills data stuctures for IRInstructionData when it is constructed from a. More...
 
CmpInst::Predicate getPredicate () const
 Get the predicate that the compare instruction is using for hashing the instruction. More...
 
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. More...
 
- Public Member Functions inherited from llvm::ilist_node_impl< ilist_detail::compute_node_options< IRInstructionData, Options... >::type >
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. More...
 

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

Public Attributes

InstructionInst = nullptr
 The source Instruction that is being wrapped. More...
 
SmallVector< Value *, 4 > OperVals
 The values of the operands in the Instruction. More...
 
bool Legal
 The legality of the wrapped instruction. More...
 
Optional< CmpInst::PredicateRevisedPredicate
 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. More...
 
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. More...
 
IRInstructionDataListIDL = nullptr
 

Friends

hash_code hash_value (const IRInstructionData &ID)
 Hashes Value based on its opcode, types, and operand types. More...
 

Additional Inherited Members

- Protected Types inherited from llvm::ilist_node_impl< ilist_detail::compute_node_options< IRInstructionData, Options... >::type >
using self_iterator = ilist_iterator< ilist_detail::compute_node_options< IRInstructionData, Options... >::type, false, false >
 
using const_self_iterator = ilist_iterator< ilist_detail::compute_node_options< IRInstructionData, Options... >::type, false, true >
 
using reverse_self_iterator = ilist_iterator< ilist_detail::compute_node_options< IRInstructionData, Options... >::type, true, false >
 
using const_reverse_self_iterator = ilist_iterator< ilist_detail::compute_node_options< IRInstructionData, Options... >::type, true, true >
 
- Protected Member Functions inherited from llvm::ilist_node_impl< ilist_detail::compute_node_options< IRInstructionData, Options... >::type >
 ilist_node_impl ()=default
 

Detailed Description

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:

%add1 = add i32 %a, %b
%add2 = add i32 %c, %d
%add3 = add i64 %e, %f

so:

; These two adds have the same types and operand types, so they hash to the
; same number.
%add1 = add i32 %a, %b ; Hash: 1
%add2 = add i32 %c, %d ; Hash: 1
; This add produces an i64. This differentiates it from %add1 and %add2. So,
; it hashes to a different number.
%add3 = add i64 %e, %f; Hash: 2

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

Constructor & Destructor Documentation

◆ IRInstructionData() [1/2]

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

References initializeInstruction().

◆ IRInstructionData() [2/2]

IRInstructionData::IRInstructionData ( IRInstructionDataList IDL)

Definition at line 62 of file IRSimilarityIdentifier.cpp.

Member Function Documentation

◆ getPredicate()

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

References assert(), llvm::Optional< T >::getValue(), llvm::Optional< T >::hasValue(), Inst, and RevisedPredicate.

◆ initializeInstruction()

void IRInstructionData::initializeInstruction ( )

Fills data stuctures for IRInstructionData when it is constructed from a.

Definition at line 38 of file IRSimilarityIdentifier.cpp.

References llvm::Optional< T >::hasValue(), Inst, llvm::User::operands(), OperVals, predicateForConsistency(), and RevisedPredicate.

Referenced by IRInstructionData().

◆ predicateForConsistency()

CmpInst::Predicate IRInstructionData::predicateForConsistency ( CmpInst CI)
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.

Parameters
CI- The comparison operation to find a consistent preidcate for.
Returns
the consistent comparison predicate.

Definition at line 89 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().

◆ setBranchSuccessors()

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.

Parameters
BasicBlockToInteger- The mapping of basic blocks to their location in the module.

Definition at line 65 of file IRSimilarityIdentifier.cpp.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::Instruction::getParent(), Inst, RelativeBlockLocations, llvm::Successor, and llvm::BranchInst::successors().

Friends And Related Function Documentation

◆ hash_value

hash_code hash_value ( const IRInstructionData ID)
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.

%add1 = add i32 %x1, %y1
%add2 = add i32 %x2, %y2
%sub = sub i32 %x1, %y1
%add_i64 = add i64 %x2, %y2

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.

Parameters
[in]ID- The IRInstructionData instance to be hashed.
Returns
A hash_value of the IRInstructionData.

Definition at line 215 of file IRSimilarityIdentifier.h.

Member Data Documentation

◆ IDL

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

Definition at line 238 of file IRSimilarityIdentifier.h.

◆ Inst

Instruction* llvm::IRSimilarity::IRInstructionData::Inst = nullptr

◆ Legal

bool llvm::IRSimilarity::IRInstructionData::Legal

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

◆ OperVals

SmallVector<Value *, 4> llvm::IRSimilarity::IRInstructionData::OperVals

The values of the operands in the Instruction.

Definition at line 119 of file IRSimilarityIdentifier.h.

Referenced by initializeInstruction().

◆ RelativeBlockLocations

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:

block_1:
br i1 %0, label %block_2, label %block_3
block_2:
br i1 %1, label %block_1, label %block_2
block_3:
br i1 %2, label %block_2, label %block_1
; Replacing the labels with relative values, this becomes:
block_1:
br i1 %0, distance 1, distance 2
block_2:
br i1 %1, distance -1, distance 0
block_3:
br i1 %2, distance -1, distance -2

Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is "ahead" of block_2.

Definition at line 153 of file IRSimilarityIdentifier.h.

Referenced by setBranchSuccessors().

◆ RevisedPredicate

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 None otherwise.

Definition at line 129 of file IRSimilarityIdentifier.h.

Referenced by getPredicate(), and initializeInstruction().


The documentation for this struct was generated from the following files:
produces
entry stw r5 blr GCC produces
Definition: README.txt:174
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
to
Should compile to
Definition: README.txt:449
i1
Decimal Convert From to National Zoned Signed int_ppc_altivec_bcdcfno i1
Definition: README_P9.txt:147
and
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
Definition: README.txt:1271
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
different
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause different(semantically equivalent) instructions to be used in place of the requested instruction
i64
Clang compiles this i64
Definition: README.txt:504
So
So we should use XX3Form_Rcr to implement instrinsic Convert DP outs ins xscvdpsp So
Definition: README_P9.txt:331
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
x2
gcc mainline compiles it x2(%rip)
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:697
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
This
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 This
Definition: README.txt:418
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