Go to the documentation of this file.
24 using namespace IRSimilarity;
30 cl::desc(
"disable similarity matching, and outlining, "
31 "across branches for debugging purposes."));
36 cl::desc(
"disable outlining indirect calls."));
40 cl::desc(
"only allow matching call instructions if the "
41 "name and type signature match."));
45 cl::desc(
"Don't match or outline intrinsics"));
50 : Inst(&
I),
Legal(Legality), IDL(&IDList) {
89 assert(isa<BranchInst>(
Inst) &&
"Instruction must be branch");
95 assert(BBNumIt != BasicBlockToInteger.
end() &&
96 "Could not find location for BasicBlock!");
98 int CurrentBlockNumber =
static_cast<int>(BBNumIt->second);
102 assert(BBNumIt != BasicBlockToInteger.
end() &&
103 "Could not find number for BasicBlock!");
104 int OtherBlockNumber =
static_cast<int>(BBNumIt->second);
106 int Relative = OtherBlockNumber - CurrentBlockNumber;
113 assert(CI &&
"Instruction must be call");
140 assert(isa<PHINode>(
Inst) &&
"Instruction must be phi node");
146 assert(BBNumIt != BasicBlockToInteger.
end() &&
147 "Could not find location for BasicBlock!");
149 int CurrentBlockNumber =
static_cast<int>(BBNumIt->second);
155 BBNumIt = BasicBlockToInteger.
find(Incoming);
156 assert(BBNumIt != BasicBlockToInteger.
end() &&
157 "Could not find number for BasicBlock!");
158 int OtherBlockNumber =
static_cast<int>(BBNumIt->second);
160 int Relative = OtherBlockNumber - CurrentBlockNumber;
184 "Can only get a predicate from a compare instruction");
189 return cast<CmpInst>(
Inst)->getPredicate();
194 "Can only get a name from a call instruction");
204 if (!A.Legal || !
B.Legal)
209 if (!A.Inst->isSameOperationAs(
B.Inst)) {
213 if (isa<CmpInst>(A.Inst) && isa<CmpInst>(
B.Inst)) {
215 if (A.getPredicate() !=
B.getPredicate())
220 auto ZippedTypes =
zip(A.OperVals,
B.OperVals);
223 ZippedTypes, [](std::tuple<llvm::Value *, llvm::Value *> R) {
224 return std::get<0>(R)->getType() == std::get<1>(R)->getType();
234 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(A.Inst)) {
235 auto *OtherGEP = cast<GetElementPtrInst>(
B.Inst);
239 if (
GEP->isInBounds() != OtherGEP->isInBounds())
242 auto ZippedOperands =
zip(
GEP->indices(), OtherGEP->indices());
248 [](std::tuple<llvm::Use &, llvm::Use &> R) {
249 return std::get<0>(R) == std::get<1>(R);
256 if (isa<CallInst>(A.Inst) && isa<CallInst>(
B.Inst)) {
257 if (A.getCalleeName().str() !=
B.getCalleeName().str())
261 if (isa<BranchInst>(A.Inst) && isa<BranchInst>(
B.Inst) &&
262 A.RelativeBlockLocations.size() !=
B.RelativeBlockLocations.size())
272 std::vector<unsigned> &IntegerMapping) {
275 std::vector<unsigned> IntegerMappingForBB;
276 std::vector<IRInstructionData *> InstrListForBB;
304 std::vector<IRInstructionData *> &InstrListForBB) {
318 InstrListForBB.push_back(
ID);
320 if (isa<BranchInst>(*It))
323 if (isa<CallInst>(*It))
326 if (isa<PHINode>(*It))
333 std::tie(ResultIt, WasInserted) =
335 unsigned INumber = ResultIt->second;
341 IntegerMappingForBB.push_back(INumber);
345 "Instruction mapping overflow!");
348 "Tried to assign DenseMap tombstone or empty key to instruction.");
350 "Tried to assign DenseMap tombstone or empty key to instruction.");
375 std::vector<IRInstructionData *> &InstrListForBB,
bool End) {
388 InstrListForBB.push_back(
ID);
396 "Instruction mapping overflow!");
399 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
402 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
410 : StartIdx(StartIdx), Len(Len) {
412 assert(FirstInstIt !=
nullptr &&
"Instruction is nullptr!");
413 assert(LastInstIt !=
nullptr &&
"Instruction is nullptr!");
414 assert(StartIdx + Len > StartIdx &&
415 "Overflow for IRSimilarityCandidate range?");
416 assert(Len - 1 ==
static_cast<unsigned>(std::distance(
418 "Length of the first and last IRInstructionData do not match the "
436 unsigned LocalValNumber = 1;
438 for (
unsigned Loc = StartIdx; Loc < StartIdx + Len; Loc++,
ID++) {
442 if (ValueToNumber.
find(
Arg) == ValueToNumber.
end()) {
444 NumberToValue.try_emplace(LocalValNumber,
Arg);
450 if (ValueToNumber.
find(
ID->Inst) == ValueToNumber.
end()) {
452 NumberToValue.try_emplace(LocalValNumber,
ID->Inst);
460 FirstInst = FirstInstIt;
461 LastInst = LastInstIt;
467 if (ValueToNumber.
find(
BB) != ValueToNumber.
end())
471 NumberToValue.try_emplace(LocalValNumber,
BB);
478 if (A.getLength() !=
B.getLength())
481 auto InstrDataForBoth =
484 return all_of(InstrDataForBoth,
485 [](std::tuple<IRInstructionData &, IRInstructionData &> R) {
488 if (!A.Legal || !
B.Legal)
526 for (
Value *V : SourceOperands) {
527 ArgVal = SourceValueToNumberMapping.
find(V)->second;
530 std::tie(ValueMappingIt, WasInserted) = CurrentSrcTgtNumberMapping.insert(
531 std::make_pair(ArgVal, TargetValueNumbers));
537 for (
unsigned &Curr : ValueMappingIt->second)
539 if (TargetValueNumbers.
contains(Curr))
547 if (NewSet.
size() != ValueMappingIt->second.
size())
548 ValueMappingIt->second.
swap(NewSet);
552 if (ValueMappingIt->second.
size() != 1)
555 unsigned ValToRemove = *ValueMappingIt->second.
begin();
559 for (
Value *InnerV : SourceOperands) {
563 unsigned InnerVal = SourceValueToNumberMapping.
find(InnerV)->second;
564 ValueMappingIt = CurrentSrcTgtNumberMapping.
find(InnerVal);
565 if (ValueMappingIt == CurrentSrcTgtNumberMapping.
end())
568 ValueMappingIt->second.
erase(ValToRemove);
569 if (ValueMappingIt->second.
empty())
590 unsigned SourceArgVal,
unsigned TargetArgVal) {
609 std::tie(Val, WasInserted) = CurrentSrcTgtNumberMapping.
insert(
622 if (TargetSet.
size() > 1 && TargetSet.
contains(TargetArgVal)) {
624 TargetSet.
insert(TargetArgVal);
629 return TargetSet.
contains(TargetArgVal);
638 unsigned OperandLength = A.OperVals.size();
641 for (
unsigned Idx = 0; Idx < OperandLength; Idx++, VItA++, VItB++) {
642 unsigned OperValA = A.IRSC.ValueToNumber.find(*VItA)->second;
643 unsigned OperValB =
B.IRSC.ValueToNumber.find(*VItB)->second;
673 unsigned OperandLength = A.OperVals.size();
676 for (
unsigned Idx = 0; Idx < OperandLength;
677 Idx++, VItA++, VItB++) {
678 ValueNumbersA.
insert(A.IRSC.ValueToNumber.find(*VItA)->second);
679 ValueNumbersB.
insert(
B.IRSC.ValueToNumber.find(*VItB)->second);
686 A.ValueNumberMapping, A.OperVals,
694 B.ValueNumberMapping,
B.OperVals,
710 A.IRSC.getBasicBlocks(BasicBlockA);
711 B.IRSC.getBasicBlocks(BasicBlockB);
714 bool AContained = BasicBlockA.
contains(ABB);
715 bool BContained = BasicBlockB.
contains(BBB);
719 if (AContained != BContained)
725 return A.RelativeLocation ==
B.RelativeLocation;
745 if (A.getLength() !=
B.getLength())
748 if (A.ValueToNumber.size() !=
B.ValueToNumber.size())
762 unsigned SectionLength = A.getStartIdx() + A.getLength();
763 for (
unsigned Loc = A.getStartIdx(); Loc < SectionLength;
764 ItA++, ItB++, Loc++) {
772 if (!ItA->Legal || !ItB->Legal)
779 unsigned InstValA = A.ValueToNumber.find(
IA)->second;
780 unsigned InstValB =
B.ValueToNumber.find(
IB)->second;
784 std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(
786 if (!WasInserted && !ValueMappingIt->second.contains(InstValB))
789 std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingB.insert(
791 if (!WasInserted && !ValueMappingIt->second.contains(InstValA))
797 if (
IA->isCommutative() && !isa<FPMathOperator>(
IA) &&
798 !isa<IntrinsicInst>(
IA)) {
800 {A, OperValsA, ValueNumberMappingA},
801 {
B, OperValsB, ValueNumberMappingB}))
808 {A, OperValsA, ValueNumberMappingA},
809 {
B, OperValsB, ValueNumberMappingB}))
823 if (!(isa<BranchInst>(
IA) && isa<BranchInst>(
IB)) &&
824 !(isa<PHINode>(
IA) && isa<PHINode>(
IB)))
829 if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
830 OperValsA.
size() != OperValsB.
size())
834 zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
835 if (
any_of(ZippedRelativeLocations,
836 [&A, &
B](std::tuple<int, int, Value *, Value *> R) {
838 {A, std::get<0>(R), std::get<2>(R)},
839 {
B, std::get<1>(R), std::get<3>(R)});
853 return X.StartIdx <=
Y.getEndIdx() &&
Y.StartIdx >=
X.StartIdx;
856 return DoesOverlap(A,
B) || DoesOverlap(
B, A);
859 void IRSimilarityIdentifier::populateMapper(
861 std::vector<unsigned> &IntegerMapping) {
863 std::vector<IRInstructionData *> InstrListForModule;
864 std::vector<unsigned> IntegerMappingForModule;
880 IntegerMappingForModule);
886 if (InstrListForModule.size() > 0)
897 void IRSimilarityIdentifier::populateMapper(
898 ArrayRef<std::unique_ptr<Module>> &Modules,
899 std::vector<IRInstructionData *> &
InstrList,
900 std::vector<unsigned> &IntegerMapping) {
903 for (
const std::unique_ptr<Module> &M : Modules)
904 populateMapper(*M,
InstrList, IntegerMapping);
919 std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
921 unsigned StringLen = RS.
Length;
927 unsigned EndIdx = StartIdx + StringLen - 1;
930 bool ContainsIllegal =
false;
931 for (
unsigned CurrIdx = StartIdx; CurrIdx <= EndIdx; CurrIdx++) {
932 unsigned Key = IntegerMapping[CurrIdx];
934 ContainsIllegal =
true;
947 std::vector<IRInstructionData *>::iterator StartIt =
InstrList.begin();
948 std::advance(StartIt, StartIdx);
949 std::vector<IRInstructionData *>::iterator EndIt =
InstrList.begin();
950 std::advance(EndIt, EndIdx);
952 CandsForRepSubstring.emplace_back(StartIdx, StringLen, *StartIt, *EndIt);
960 assert(SourceCand.CanonNumToNumber.
size() != 0 &&
961 "Base canonical relationship is empty!");
962 assert(SourceCand.NumberToCanonNum.
size() != 0 &&
963 "Base canonical relationship is empty!");
965 assert(CanonNumToNumber.
size() == 0 &&
"Canonical Relationship is non-empty");
966 assert(NumberToCanonNum.
size() == 0 &&
"Canonical Relationship is non-empty");
973 unsigned SourceGVN = GVNMapping.first;
975 assert(GVNMapping.second.size() != 0 &&
"Possible GVNs is 0!");
982 if (GVNMapping.second.size() > 1) {
984 for (
unsigned Val : GVNMapping.second) {
991 FromSourceMapping.find(Val);
993 if (!It->second.contains(SourceGVN))
1002 assert(Found &&
"Could not find matching value for source GVN");
1006 ResultGVN = *GVNMapping.second.begin();
1009 UsedGVNs.
insert(ResultGVN);
1012 CanonNumToNumber.
insert(std::make_pair(CanonNum, SourceGVN));
1013 NumberToCanonNum.
insert(std::make_pair(SourceGVN, CanonNum));
1025 unsigned BBGVNForCurrCand = ValueToNumber.
find(
BB)->second;
1029 if (NumberToCanonNum.
find(BBGVNForCurrCand) != NumberToCanonNum.
end())
1037 : &*
BB->instructionsWithoutDebug().begin();
1039 unsigned FirstInstGVN = *
getGVN(FirstOutlineInst);
1044 unsigned SourceBBGVN = *SourceCand.
getGVN(SourceBB);
1046 CanonNumToNumber.
insert(std::make_pair(SourceCanonBBGVN, BBGVNForCurrCand));
1047 NumberToCanonNum.
insert(std::make_pair(BBGVNForCurrCand, SourceCanonBBGVN));
1053 assert(CurrCand.CanonNumToNumber.
size() == 0 &&
1054 "Canonical Relationship is non-empty");
1055 assert(CurrCand.NumberToCanonNum.
size() == 0 &&
1056 "Canonical Relationship is non-empty");
1058 unsigned CanonNum = 0;
1061 for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {
1062 CurrCand.NumberToCanonNum.
insert(std::make_pair(NumToVal.first, CanonNum));
1063 CurrCand.CanonNumToNumber.
insert(std::make_pair(CanonNum, NumToVal.first));
1078 std::vector<IRSimilarityCandidate> &CandsForRepSubstring,
1080 std::vector<IRSimilarityCandidate>::iterator CandIt, CandEndIt, InnerCandIt,
1095 unsigned CurrentGroupNum = 0;
1096 unsigned OuterGroupNum;
1105 for (CandIt = CandsForRepSubstring.begin(),
1106 CandEndIt = CandsForRepSubstring.end();
1107 CandIt != CandEndIt; CandIt++) {
1110 CandToGroupIt = CandToGroup.
find(&*CandIt);
1111 if (CandToGroupIt == CandToGroup.
end()) {
1113 std::tie(CandToGroupIt, Inserted) =
1114 CandToGroup.
insert(std::make_pair(&*CandIt, CurrentGroupNum++));
1118 OuterGroupNum = CandToGroupIt->second;
1122 CurrentGroupPair = StructuralGroups.
find(OuterGroupNum);
1123 if (CurrentGroupPair == StructuralGroups.
end()) {
1125 std::tie(CurrentGroupPair, Inserted) = StructuralGroups.
insert(
1133 for (InnerCandIt = std::next(CandIt),
1134 InnerCandEndIt = CandsForRepSubstring.end();
1135 InnerCandIt != InnerCandEndIt; InnerCandIt++) {
1138 CandToGroupItInner = CandToGroup.
find(&*InnerCandIt);
1139 if (CandToGroupItInner != CandToGroup.
end())
1144 ValueNumberMappingA.
clear();
1145 ValueNumberMappingB.
clear();
1147 *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);
1151 InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA,
1152 ValueNumberMappingB);
1153 CandToGroup.
insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
1154 CurrentGroupPair->second.push_back(*InnerCandIt);
1159 void IRSimilarityIdentifier::findCandidates(
1160 std::vector<IRInstructionData *> &
InstrList,
1161 std::vector<unsigned> &IntegerMapping) {
1164 std::vector<IRSimilarityCandidate> CandsForRepSubstring;
1165 std::vector<SimilarityGroup> NewCandidateGroups;
1174 CandsForRepSubstring);
1176 if (CandsForRepSubstring.size() < 2)
1180 for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups)
1184 if (Group.second.size() > 1)
1185 SimilarityCandidates->push_back(Group.second);
1187 CandsForRepSubstring.clear();
1188 StructuralGroups.clear();
1189 NewCandidateGroups.clear();
1194 ArrayRef<std::unique_ptr<Module>> Modules) {
1197 std::vector<IRInstructionData *>
InstrList;
1198 std::vector<unsigned> IntegerMapping;
1205 populateMapper(Modules,
InstrList, IntegerMapping);
1206 findCandidates(
InstrList, IntegerMapping);
1208 return *SimilarityCandidates;
1219 std::vector<IRInstructionData *>
InstrList;
1220 std::vector<unsigned> IntegerMapping;
1222 populateMapper(
M,
InstrList, IntegerMapping);
1223 findCandidates(
InstrList, IntegerMapping);
1225 return *SimilarityCandidates;
1229 "ir-similarity-identifier",
false,
true)
1250 IRSI->findSimilarity(
M);
1260 IRSI.findSimilarity(
M);
1267 std::optional<SimilarityGroupList> &SimilarityCandidatesOpt =
1270 for (std::vector<IRSimilarityCandidate> &CandVec : *SimilarityCandidatesOpt) {
1271 OS << CandVec.size() <<
" candidates of length "
1272 << CandVec.begin()->getLength() <<
". Found in: \n";
1274 OS <<
" Function: " << Cand.front()->Inst->getFunction()->getName().str()
1275 <<
", Basic Block: ";
1276 if (Cand.front()->Inst->getParent()->getName().str() ==
"")
1279 OS << Cand.front()->Inst->getParent()->getName().str();
1280 OS <<
"\n Start Instruction: ";
1281 Cand.frontInstruction()->print(OS);
1282 OS <<
"\n End Instruction: ";
1283 Cand.backInstruction()->print(OS);
A set of analyses that are preserved following a run of a transformation pass.
unsigned Length
The length of the string.
cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))
bool isOverloaded(ID id)
Returns true if the intrinsic can be overloaded.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static bool compareCommutativeOperandMapping(OperandMapping A, OperandMapping B)
Compare the operands in A and B and check that the current mapping of global value numbers from A to ...
SimilarityGroupList & findSimilarity(ArrayRef< std::unique_ptr< Module >> Modules)
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void setBranchSuccessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)
For an IRInstructionData containing a branch, finds the relative distances from the source basic bloc...
iterator_range< succ_op_iterator > successors()
bool isClose(const IRInstructionData &A, const IRInstructionData &B)
Compare one IRInstructionData class to another IRInstructionData class for whether they are performin...
DenseMap< BasicBlock *, unsigned > BasicBlockToInteger
A mapping for a basic block in a module to its assigned number/location in the module.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
InstListType::iterator iterator
Instruction iterators...
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
const Function * getParent() const
Return the enclosing method, or null if none.
unsigned LegalInstrNumber
The next available integer to assign to a legal Instruction to.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
static bool compareNonCommutativeOperandMapping(OperandMapping A, OperandMapping B)
Compare the operands in A and B and check that the current mapping of global value numbers from A to ...
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const
SmallVector< MachineInstr * > InstrList
std::vector< unsigned > StartIndices
The start indices of each occurrence.
bool erase(const KeyT &Val)
@ ICMP_SGT
signed greater than
A data structure for fast substring queries.
cl::opt< bool > DisableBranches("no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden, cl::desc("disable similarity matching, and outlining, " "across branches for debugging purposes."))
std::vector< IRSimilarityCandidate > SimilarityGroup
void resetSimilarityCandidates()
std::optional< CmpInst::Predicate > RevisedPredicate
This is only relevant if we are wrapping a CmpInst where we needed to change the predicate of a compa...
std::optional< unsigned > getGVN(Value *V)
Finds the positive number associated with V if it has been mapped.
std::optional< std::string > CalleeName
This is only relevant if we are wrapping a CallInst.
std::vector< SimilarityGroup > SimilarityGroupList
std::pair< iterator, bool > insert(const ValueT &V)
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
SpecificBumpPtrAllocator< IRInstructionDataList > * IDLAllocator
This allocator pointer is in charge of creating the IRInstructionDataList so it is not deallocated un...
IRInstructionDataList * IDL
LLVM Basic Block Representation.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
IRSimilarityCandidate(unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt)
An information struct used to provide DenseMap with the various necessary components for a given valu...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
(vector float) vec_cmpeq(*A, *B) C
void setPHIPredecessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)
For an IRInstructionData containing a PHINode, finds the relative distances from the incoming basic b...
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
static void findCandidateStructures(std::vector< IRSimilarityCandidate > &CandsForRepSubstring, DenseMap< unsigned, SimilarityGroup > &StructuralGroups)
From the list of IRSimilarityCandidates, perform a comparison between each IRSimilarityCandidate to d...
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Helper struct for converting the Instructions in a Module into a vector of unsigned integers.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool HaveLegalRange
Marks whether we have found a set of instructions that is long enough to be considered for similarity...
std::optional< Value * > fromGVN(unsigned Num)
Finds the Value associate with Num if it exists.
static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
ArrayRef< Type * > params() const
IRInstructionDataList::iterator iterator
SpecificBumpPtrAllocator< IRInstructionData > * InstDataAllocator
This allocator pointer is in charge of holding on to the IRInstructionData so it is not deallocated u...
InstructionClassification InstClassifier
Maps an Instruction to a member of InstrType.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool checkNumberingAndReplace(DenseMap< unsigned, DenseSet< unsigned >> &CurrentSrcTgtNumberMapping, unsigned SourceArgVal, unsigned TargetArgVal)
Determine if operand number TargetArgVal is in the current mapping set for operand number SourceArgVa...
This class is the base class for the comparison instructions.
detail::zippy< detail::zip_shortest, SmallVector< int, 4 > &, SmallVector< int, 4 > &, ArrayRef< Value * > &, ArrayRef< Value * > & > ZippedRelativeLocationsT
bool EnableMatchCallsByName
Marks whether we should use exact function names, as well as types to find similarity between calls.
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
BasicBlock * getStartBB()
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits > InstructionIntegerMap
Correspondence from IRInstructionData to unsigned integers.
static bool checkNumberingAndReplaceCommutative(const DenseMap< Value *, unsigned > &SourceValueToNumberMapping, DenseMap< unsigned, DenseSet< unsigned >> &CurrentSrcTgtNumberMapping, ArrayRef< Value * > &SourceOperands, DenseSet< unsigned > &TargetValueNumbers)
Determine if one or more of the assigned global value numbers for the operands in TargetValueNumbers ...
static bool overlap(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap.
A repeated substring in the tree.
Result run(Module &M, ModuleAnalysisManager &)
IRInstructionData * allocateIRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Get an allocated IRInstructionData struct using the InstDataAllocator.
A special type used by analysis passes to provide an address that identifies that particular analysis...
initializer< Ty > init(const Ty &Val)
void visit(Iterator Start, Iterator End)
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.
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
iterator find(const_arg_type_t< KeyT > Val)
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.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void push_back(reference Node)
Insert a node at the back; never copies.
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
This provides the utilities for hashing an Instruction to an unsigned integer.
@ ICMP_UGE
unsigned greater or equal
StringRef getCalleeName() const
Get the callee name that the call instruction is using for hashing the instruction.
IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Gather the information that is difficult to gather for an Instruction, or is changed.
unsigned mapToIllegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB, bool End=false)
Maps an Instruction to an illegal integer.
cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))
void initializeIRSimilarityIdentifierWrapperPassPass(PassRegistry &)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
A Module instance is used to store all the information related to an LLVM module.
static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand)
Create a mapping from the value numbering to a different separate set of numbers.
void setCalleeName(bool MatchByName=true)
For an IRInstructionData containing a CallInst, set the function name appropriately.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
SmallVector< int, 4 > RelativeBlockLocations
This structure holds the distances of how far "ahead of" or "behind" the target blocks of a branch,...
Instruction * Inst
The source Instruction that is being wrapped.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
StringRef - Represent a constant reference to a string, i.e.
if(llvm_vc STREQUAL "") set(fake_version_inc "$
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
unsigned mapToLegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)
Maps an Instruction to a legal integer.
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void createCanonicalRelationFrom(IRSimilarityCandidate &SourceCand, DenseMap< unsigned, DenseSet< unsigned >> &ToSourceMapping, DenseMap< unsigned, DenseSet< unsigned >> &FromSourceMapping)
Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separat...
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
unsigned IllegalInstrNumber
The starting illegal instruction number to map to.
Iterator for intrusive lists based on ilist_node.
std::optional< unsigned > fromCanonicalNum(unsigned N)
Find the global value number from the canonical number N stored in the candidate.
IRInstructionDataList * allocateIRInstructionDataList()
Get an allocated IRInstructionDataList object using the IDLAllocator.
static bool checkRelativeLocations(RelativeLocMapping A, RelativeLocMapping B)
Compare the relative locations in A and B and check that the distances match if both locations are co...
Instruction * frontInstruction()
bool isIndirectCall() const
Return true if the callsite is an indirect call.
cl::opt< bool > MatchCallsByName("ir-sim-calls-by-name", cl::init(false), cl::ReallyHidden, cl::desc("only allow matching call instructions if the " "name and type signature match."))
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...
@ ICMP_SGE
signed greater or equal
A wrapper class for inspecting calls to intrinsic functions.
void initializeForBBs(Function &F, unsigned &BBNumber)
Assigns values to all the basic blocks in function F starting from integer BBNumber.
void initializeInstruction()
Fills data stuctures for IRInstructionData when it is constructed from a.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
CmpInst::Predicate getPredicate() const
Get the predicate that the compare instruction is using for hashing the instruction.
@ ICMP_UGT
unsigned greater than
A helper struct to hold the candidate, for a branch instruction, the relative location of a label,...
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
const BasicBlock * getParent() const
Predicate getPredicate() const
Return the predicate for this instruction.
INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier", "ir-similarity-identifier", false, true) IRSimilarityIdentifierWrapperPass
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
size_t size() const
size - Get the array size.
bool AddedIllegalLastTime
Set if we added an illegal number in the previous step.
static void createCandidatesFromSuffixTree(const IRInstructionMapper &Mapper, std::vector< IRInstructionData * > &InstrList, std::vector< unsigned > &IntegerMapping, SuffixTree::RepeatedSubstring &RS, std::vector< IRSimilarityCandidate > &CandsForRepSubstring)
From a repeated subsequence, find all the different instances of the subsequence from the InstrList,...
A container for analyses that lazily runs them and caches their results.
std::string str() const
str - Get the contents as an std::string.
bool CanCombineWithPrevInstr
Marks whether we found a illegal instruction in the previous step.
This class represents a function call, abstracting a target machine's calling convention.
SmallVector< Value *, 4 > OperVals
The values of the operands in the Instruction.
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 BB
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Conditional or Unconditional Branch instruction.
std::optional< unsigned > getCanonicalNum(unsigned N)
Find the canonical number from the global value number N stored in the candidate.
LLVM Value Representation.
std::optional< SimilarityGroupList > & getSimilarity()
Class to represent function types.
A Use represents the edge between a Value definition and its users.