LLVM  14.0.0git
IRSimilarityIdentifier.cpp
Go to the documentation of this file.
1 //===- IRSimilarityIdentifier.cpp - Find similarity in a module -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // \file
10 // Implementation file for the IRSimilarityIdentifier for identifying
11 // similarities in IR including the IRInstructionMapper.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/IR/Intrinsics.h"
18 #include "llvm/IR/Operator.h"
19 #include "llvm/IR/User.h"
20 #include "llvm/InitializePasses.h"
22 
23 using namespace llvm;
24 using namespace IRSimilarity;
25 
27  DisableBranches("no-ir-sim-branch-matching", cl::init(false),
29  cl::desc("disable similarity matching, and outlining, "
30  "across branches for debugging purposes."));
31 
33  IRInstructionDataList &IDList)
34  : Inst(&I), Legal(Legality), IDL(&IDList) {
36 }
37 
39  // We check for whether we have a comparison instruction. If it is, we
40  // find the "less than" version of the predicate for consistency for
41  // comparison instructions throught the program.
42  if (CmpInst *C = dyn_cast<CmpInst>(Inst)) {
44  if (Predicate != C->getPredicate())
46  }
47 
48  // Here we collect the operands and their types for determining whether
49  // the structure of the operand use matches between two different candidates.
50  for (Use &OI : Inst->operands()) {
51  if (isa<CmpInst>(Inst) && RevisedPredicate.hasValue()) {
52  // If we have a CmpInst where the predicate is reversed, it means the
53  // operands must be reversed as well.
54  OperVals.insert(OperVals.begin(), OI.get());
55  continue;
56  }
57 
58  OperVals.push_back(OI.get());
59  }
60 }
61 
63  : Inst(nullptr), Legal(false), IDL(&IDList) {}
64 
66  DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) {
67  assert(isa<BranchInst>(Inst) && "Instruction must be branch");
68 
69  BranchInst *BI = cast<BranchInst>(Inst);
71 
72  BBNumIt = BasicBlockToInteger.find(BI->getParent());
73  assert(BBNumIt != BasicBlockToInteger.end() &&
74  "Could not find location for BasicBlock!");
75 
76  int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
77 
78  for (BasicBlock *Successor : BI->successors()) {
79  BBNumIt = BasicBlockToInteger.find(Successor);
80  assert(BBNumIt != BasicBlockToInteger.end() &&
81  "Could not find number for BasicBlock!");
82  int OtherBlockNumber = static_cast<int>(BBNumIt->second);
83 
84  int Relative = OtherBlockNumber - CurrentBlockNumber;
85  RelativeBlockLocations.push_back(Relative);
86  }
87 }
88 
90  switch (CI->getPredicate()) {
91  case CmpInst::FCMP_OGT:
92  case CmpInst::FCMP_UGT:
93  case CmpInst::FCMP_OGE:
94  case CmpInst::FCMP_UGE:
95  case CmpInst::ICMP_SGT:
96  case CmpInst::ICMP_UGT:
97  case CmpInst::ICMP_SGE:
98  case CmpInst::ICMP_UGE:
99  return CI->getSwappedPredicate();
100  default:
101  return CI->getPredicate();
102  }
103 }
104 
106  assert(isa<CmpInst>(Inst) &&
107  "Can only get a predicate from a compare instruction");
108 
110  return RevisedPredicate.getValue();
111 
112  return cast<CmpInst>(Inst)->getPredicate();
113 }
114 
116  assert(CI.getCalledFunction() != nullptr && "Called Function is nullptr?");
117 
118  return CI.getCalledFunction()->getName();
119 }
120 
122  const IRInstructionData &B) {
123 
124  if (!A.Legal || !B.Legal)
125  return false;
126 
127  // Check if we are performing the same sort of operation on the same types
128  // but not on the same values.
129  if (!A.Inst->isSameOperationAs(B.Inst)) {
130  // If there is a predicate, this means that either there is a swapped
131  // predicate, or that the types are different, we want to make sure that
132  // the predicates are equivalent via swapping.
133  if (isa<CmpInst>(A.Inst) && isa<CmpInst>(B.Inst)) {
134 
135  if (A.getPredicate() != B.getPredicate())
136  return false;
137 
138  // If the predicates are the same via swap, make sure that the types are
139  // still the same.
140  auto ZippedTypes = zip(A.OperVals, B.OperVals);
141 
142  return all_of(
143  ZippedTypes, [](std::tuple<llvm::Value *, llvm::Value *> R) {
144  return std::get<0>(R)->getType() == std::get<1>(R)->getType();
145  });
146  }
147 
148  return false;
149  }
150 
151  // Since any GEP Instruction operands after the first operand cannot be
152  // defined by a register, we must make sure that the operands after the first
153  // are the same in the two instructions
154  if (auto *GEP = dyn_cast<GetElementPtrInst>(A.Inst)) {
155  auto *OtherGEP = cast<GetElementPtrInst>(B.Inst);
156 
157  // If the instructions do not have the same inbounds restrictions, we do
158  // not consider them the same.
159  if (GEP->isInBounds() != OtherGEP->isInBounds())
160  return false;
161 
162  auto ZippedOperands = zip(GEP->indices(), OtherGEP->indices());
163 
164  // We increment here since we do not care about the first instruction,
165  // we only care about the following operands since they must be the
166  // exact same to be considered similar.
167  return all_of(drop_begin(ZippedOperands),
168  [](std::tuple<llvm::Use &, llvm::Use &> R) {
169  return std::get<0>(R) == std::get<1>(R);
170  });
171  }
172 
173  // If the instructions are functions, we make sure that the function name is
174  // the same. We already know that the types are since is isSameOperationAs is
175  // true.
176  if (isa<CallInst>(A.Inst) && isa<CallInst>(B.Inst)) {
177  CallInst *CIA = cast<CallInst>(A.Inst);
178  CallInst *CIB = cast<CallInst>(B.Inst);
180  return false;
181  }
182 
183  if (isa<BranchInst>(A.Inst) && isa<BranchInst>(B.Inst) &&
184  A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())
185  return false;
186 
187  return true;
188 }
189 
190 // TODO: This is the same as the MachineOutliner, and should be consolidated
191 // into the same interface.
193  BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
194  std::vector<unsigned> &IntegerMapping) {
195  BasicBlock::iterator It = BB.begin();
196 
197  std::vector<unsigned> IntegerMappingForBB;
198  std::vector<IRInstructionData *> InstrListForBB;
199 
200  for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
201  switch (InstClassifier.visit(*It)) {
202  case InstrType::Legal:
203  mapToLegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
204  break;
205  case InstrType::Illegal:
206  mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
207  break;
209  AddedIllegalLastTime = false;
210  break;
211  }
212  }
213 
214  if (HaveLegalRange) {
216  mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
217  for (IRInstructionData *ID : InstrListForBB)
218  this->IDL->push_back(*ID);
219  llvm::append_range(InstrList, InstrListForBB);
220  llvm::append_range(IntegerMapping, IntegerMappingForBB);
221  }
222 }
223 
224 // TODO: This is the same as the MachineOutliner, and should be consolidated
225 // into the same interface.
227  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
228  std::vector<IRInstructionData *> &InstrListForBB) {
229  // We added something legal, so we should unset the AddedLegalLastTime
230  // flag.
231  AddedIllegalLastTime = false;
232 
233  // If we have at least two adjacent legal instructions (which may have
234  // invisible instructions in between), remember that.
236  HaveLegalRange = true;
238 
239  // Get the integer for this instruction or give it the current
240  // LegalInstrNumber.
242  InstrListForBB.push_back(ID);
243 
244  if (isa<BranchInst>(*It))
245  ID->setBranchSuccessors(BasicBlockToInteger);
246 
247  // Add to the instruction list
248  bool WasInserted;
250  ResultIt;
251  std::tie(ResultIt, WasInserted) =
252  InstructionIntegerMap.insert(std::make_pair(ID, LegalInstrNumber));
253  unsigned INumber = ResultIt->second;
254 
255  // There was an insertion.
256  if (WasInserted)
258 
259  IntegerMappingForBB.push_back(INumber);
260 
261  // Make sure we don't overflow or use any integers reserved by the DenseMap.
263  "Instruction mapping overflow!");
264 
266  "Tried to assign DenseMap tombstone or empty key to instruction.");
268  "Tried to assign DenseMap tombstone or empty key to instruction.");
269 
270  return INumber;
271 }
272 
275  IRInstructionDataList &IDL) {
276  return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
277 }
278 
281  return new (InstDataAllocator->Allocate()) IRInstructionData(IDL);
282 }
283 
286  return new (IDLAllocator->Allocate()) IRInstructionDataList();
287 }
288 
289 // TODO: This is the same as the MachineOutliner, and should be consolidated
290 // into the same interface.
292  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
293  std::vector<IRInstructionData *> &InstrListForBB, bool End) {
294  // Can't combine an illegal instruction. Set the flag.
295  CanCombineWithPrevInstr = false;
296 
297  // Only add one illegal number per range of legal numbers.
299  return IllegalInstrNumber;
300 
301  IRInstructionData *ID = nullptr;
302  if (!End)
303  ID = allocateIRInstructionData(*It, false, *IDL);
304  else
306  InstrListForBB.push_back(ID);
307 
308  // Remember that we added an illegal number last time.
309  AddedIllegalLastTime = true;
310  unsigned INumber = IllegalInstrNumber;
311  IntegerMappingForBB.push_back(IllegalInstrNumber--);
312 
314  "Instruction mapping overflow!");
315 
317  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
318 
320  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
321 
322  return INumber;
323 }
324 
325 IRSimilarityCandidate::IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
326  IRInstructionData *FirstInstIt,
327  IRInstructionData *LastInstIt)
328  : StartIdx(StartIdx), Len(Len) {
329 
330  assert(FirstInstIt != nullptr && "Instruction is nullptr!");
331  assert(LastInstIt != nullptr && "Instruction is nullptr!");
332  assert(StartIdx + Len > StartIdx &&
333  "Overflow for IRSimilarityCandidate range?");
334  assert(Len - 1 == static_cast<unsigned>(std::distance(
335  iterator(FirstInstIt), iterator(LastInstIt))) &&
336  "Length of the first and last IRInstructionData do not match the "
337  "given length");
338 
339  // We iterate over the given instructions, and map each unique value
340  // to a unique number in the IRSimilarityCandidate ValueToNumber and
341  // NumberToValue maps. A constant get its own value globally, the individual
342  // uses of the constants are not considered to be unique.
343  //
344  // IR: Mapping Added:
345  // %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2
346  // %add2 = add i32 %a, %1 %add2 -> 4
347  // %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5
348  //
349  // when replace with global values, starting from 1, would be
350  //
351  // 3 = add i32 1, 2
352  // 4 = add i32 1, 3
353  // 6 = add i32 5, 2
354  unsigned LocalValNumber = 1;
356  for (unsigned Loc = StartIdx; Loc < StartIdx + Len; Loc++, ID++) {
357  // Map the operand values to an unsigned integer if it does not already
358  // have an unsigned integer assigned to it.
359  for (Value *Arg : ID->OperVals)
360  if (ValueToNumber.find(Arg) == ValueToNumber.end()) {
361  ValueToNumber.try_emplace(Arg, LocalValNumber);
362  NumberToValue.try_emplace(LocalValNumber, Arg);
363  LocalValNumber++;
364  }
365 
366  // Mapping the instructions to an unsigned integer if it is not already
367  // exist in the mapping.
368  if (ValueToNumber.find(ID->Inst) == ValueToNumber.end()) {
369  ValueToNumber.try_emplace(ID->Inst, LocalValNumber);
370  NumberToValue.try_emplace(LocalValNumber, ID->Inst);
371  LocalValNumber++;
372  }
373  }
374 
375  // Setting the first and last instruction data pointers for the candidate. If
376  // we got through the entire for loop without hitting an assert, we know
377  // that both of these instructions are not nullptrs.
378  FirstInst = FirstInstIt;
379  LastInst = LastInstIt;
380 }
381 
383  const IRSimilarityCandidate &B) {
384  if (A.getLength() != B.getLength())
385  return false;
386 
387  auto InstrDataForBoth =
388  zip(make_range(A.begin(), A.end()), make_range(B.begin(), B.end()));
389 
390  return all_of(InstrDataForBoth,
391  [](std::tuple<IRInstructionData &, IRInstructionData &> R) {
392  IRInstructionData &A = std::get<0>(R);
393  IRInstructionData &B = std::get<1>(R);
394  if (!A.Legal || !B.Legal)
395  return false;
396  return isClose(A, B);
397  });
398 }
399 
400 /// Determine if one or more of the assigned global value numbers for the
401 /// operands in \p TargetValueNumbers is in the current mapping set for operand
402 /// numbers in \p SourceOperands. The set of possible corresponding global
403 /// value numbers are replaced with the most recent version of compatible
404 /// values.
405 ///
406 /// \param [in] SourceValueToNumberMapping - The mapping of a Value to global
407 /// value number for the source IRInstructionCandidate.
408 /// \param [in, out] CurrentSrcTgtNumberMapping - The current mapping of source
409 /// IRSimilarityCandidate global value numbers to a set of possible numbers in
410 /// the target.
411 /// \param [in] SourceOperands - The operands in the original
412 /// IRSimilarityCandidate in the current instruction.
413 /// \param [in] TargetValueNumbers - The global value numbers of the operands in
414 /// the corresponding Instruction in the other IRSimilarityCandidate.
415 /// \returns true if there exists a possible mapping between the source
416 /// Instruction operands and the target Instruction operands, and false if not.
418  const DenseMap<Value *, unsigned> &SourceValueToNumberMapping,
419  DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
420  ArrayRef<Value *> &SourceOperands,
421  DenseSet<unsigned> &TargetValueNumbers){
422 
423  DenseMap<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
424 
425  unsigned ArgVal;
426  bool WasInserted;
427 
428  // Iterate over the operands in the source IRSimilarityCandidate to determine
429  // whether there exists an operand in the other IRSimilarityCandidate that
430  // creates a valid mapping of Value to Value between the
431  // IRSimilarityCaniddates.
432  for (Value *V : SourceOperands) {
433  ArgVal = SourceValueToNumberMapping.find(V)->second;
434 
435  std::tie(ValueMappingIt, WasInserted) = CurrentSrcTgtNumberMapping.insert(
436  std::make_pair(ArgVal, TargetValueNumbers));
437 
438  // Instead of finding a current mapping, we inserted a set. This means a
439  // mapping did not exist for the source Instruction operand, it has no
440  // current constraints we need to check.
441  if (WasInserted)
442  continue;
443 
444  // If a mapping already exists for the source operand to the values in the
445  // other IRSimilarityCandidate we need to iterate over the items in other
446  // IRSimilarityCandidate's Instruction to determine whether there is a valid
447  // mapping of Value to Value.
448  DenseSet<unsigned> NewSet;
449  for (unsigned &Curr : ValueMappingIt->second)
450  // If we can find the value in the mapping, we add it to the new set.
451  if (TargetValueNumbers.contains(Curr))
452  NewSet.insert(Curr);
453 
454  // If we could not find a Value, return 0.
455  if (NewSet.empty())
456  return false;
457 
458  // Otherwise replace the old mapping with the newly constructed one.
459  if (NewSet.size() != ValueMappingIt->second.size())
460  ValueMappingIt->second.swap(NewSet);
461 
462  // We have reached no conclusions about the mapping, and cannot remove
463  // any items from the other operands, so we move to check the next operand.
464  if (ValueMappingIt->second.size() != 1)
465  continue;
466 
467 
468  unsigned ValToRemove = *ValueMappingIt->second.begin();
469  // When there is only one item left in the mapping for and operand, remove
470  // the value from the other operands. If it results in there being no
471  // mapping, return false, it means the mapping is wrong
472  for (Value *InnerV : SourceOperands) {
473  if (V == InnerV)
474  continue;
475 
476  unsigned InnerVal = SourceValueToNumberMapping.find(InnerV)->second;
477  ValueMappingIt = CurrentSrcTgtNumberMapping.find(InnerVal);
478  if (ValueMappingIt == CurrentSrcTgtNumberMapping.end())
479  continue;
480 
481  ValueMappingIt->second.erase(ValToRemove);
482  if (ValueMappingIt->second.empty())
483  return false;
484  }
485  }
486 
487  return true;
488 }
489 
490 /// Determine if operand number \p TargetArgVal is in the current mapping set
491 /// for operand number \p SourceArgVal.
492 ///
493 /// \param [in, out] CurrentSrcTgtNumberMapping current mapping of global
494 /// value numbers from source IRSimilarityCandidate to target
495 /// IRSimilarityCandidate.
496 /// \param [in] SourceArgVal The global value number for an operand in the
497 /// in the original candidate.
498 /// \param [in] TargetArgVal The global value number for the corresponding
499 /// operand in the other candidate.
500 /// \returns True if there exists a mapping and false if not.
502  DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
503  unsigned SourceArgVal, unsigned TargetArgVal) {
504  // We are given two unsigned integers representing the global values of
505  // the operands in different IRSimilarityCandidates and a current mapping
506  // between the two.
507  //
508  // Source Operand GVN: 1
509  // Target Operand GVN: 2
510  // CurrentMapping: {1: {1, 2}}
511  //
512  // Since we have mapping, and the target operand is contained in the set, we
513  // update it to:
514  // CurrentMapping: {1: {2}}
515  // and can return true. But, if the mapping was
516  // CurrentMapping: {1: {3}}
517  // we would return false.
518 
519  bool WasInserted;
521 
522  std::tie(Val, WasInserted) = CurrentSrcTgtNumberMapping.insert(
523  std::make_pair(SourceArgVal, DenseSet<unsigned>({TargetArgVal})));
524 
525  // If we created a new mapping, then we are done.
526  if (WasInserted)
527  return true;
528 
529  // If there is more than one option in the mapping set, and the target value
530  // is included in the mapping set replace that set with one that only includes
531  // the target value, as it is the only valid mapping via the non commutative
532  // instruction.
533 
534  DenseSet<unsigned> &TargetSet = Val->second;
535  if (TargetSet.size() > 1 && TargetSet.contains(TargetArgVal)) {
536  TargetSet.clear();
537  TargetSet.insert(TargetArgVal);
538  return true;
539  }
540 
541  // Return true if we can find the value in the set.
542  return TargetSet.contains(TargetArgVal);
543 }
544 
547  // Iterators to keep track of where we are in the operands for each
548  // Instruction.
549  ArrayRef<Value *>::iterator VItA = A.OperVals.begin();
550  ArrayRef<Value *>::iterator VItB = B.OperVals.begin();
551  unsigned OperandLength = A.OperVals.size();
552 
553  // For each operand, get the value numbering and ensure it is consistent.
554  for (unsigned Idx = 0; Idx < OperandLength; Idx++, VItA++, VItB++) {
555  unsigned OperValA = A.IRSC.ValueToNumber.find(*VItA)->second;
556  unsigned OperValB = B.IRSC.ValueToNumber.find(*VItB)->second;
557 
558  // Attempt to add a set with only the target value. If there is no mapping
559  // we can create it here.
560  //
561  // For an instruction like a subtraction:
562  // IRSimilarityCandidateA: IRSimilarityCandidateB:
563  // %resultA = sub %a, %b %resultB = sub %d, %e
564  //
565  // We map %a -> %d and %b -> %e.
566  //
567  // And check to see whether their mapping is consistent in
568  // checkNumberingAndReplace.
569 
570  if (!checkNumberingAndReplace(A.ValueNumberMapping, OperValA, OperValB))
571  return false;
572 
573  if (!checkNumberingAndReplace(B.ValueNumberMapping, OperValB, OperValA))
574  return false;
575  }
576  return true;
577 }
578 
581  DenseSet<unsigned> ValueNumbersA;
582  DenseSet<unsigned> ValueNumbersB;
583 
584  ArrayRef<Value *>::iterator VItA = A.OperVals.begin();
585  ArrayRef<Value *>::iterator VItB = B.OperVals.begin();
586  unsigned OperandLength = A.OperVals.size();
587 
588  // Find the value number sets for the operands.
589  for (unsigned Idx = 0; Idx < OperandLength;
590  Idx++, VItA++, VItB++) {
591  ValueNumbersA.insert(A.IRSC.ValueToNumber.find(*VItA)->second);
592  ValueNumbersB.insert(B.IRSC.ValueToNumber.find(*VItB)->second);
593  }
594 
595  // Iterate over the operands in the first IRSimilarityCandidate and make sure
596  // there exists a possible mapping with the operands in the second
597  // IRSimilarityCandidate.
598  if (!checkNumberingAndReplaceCommutative(A.IRSC.ValueToNumber,
599  A.ValueNumberMapping, A.OperVals,
600  ValueNumbersB))
601  return false;
602 
603  // Iterate over the operands in the second IRSimilarityCandidate and make sure
604  // there exists a possible mapping with the operands in the first
605  // IRSimilarityCandidate.
606  if (!checkNumberingAndReplaceCommutative(B.IRSC.ValueToNumber,
607  B.ValueNumberMapping, B.OperVals,
608  ValueNumbersA))
609  return false;
610 
611  return true;
612 }
613 
616  // Get the basic blocks the label refers to.
617  BasicBlock *ABB = static_cast<BasicBlock *>(A.OperVal);
618  BasicBlock *BBB = static_cast<BasicBlock *>(B.OperVal);
619 
620  // Get the basic blocks contained in each region.
621  DenseSet<BasicBlock *> BasicBlockA;
622  DenseSet<BasicBlock *> BasicBlockB;
623  A.IRSC.getBasicBlocks(BasicBlockA);
624  B.IRSC.getBasicBlocks(BasicBlockB);
625 
626  // Determine if the block is contained in the region.
627  bool AContained = BasicBlockA.find(ABB) != BasicBlockA.end();
628  bool BContained = BasicBlockB.find(BBB) != BasicBlockB.end();
629 
630  // Both blocks need to be contained in the region, or both need to be outside
631  // the reigon.
632  if (AContained != BContained)
633  return false;
634 
635  // If both are contained, then we need to make sure that the relative
636  // distance to the target blocks are the same.
637  if (AContained)
638  return A.RelativeLocation == B.RelativeLocation;
639  return true;
640 }
641 
643  const IRSimilarityCandidate &B) {
646  return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB);
647 }
648 
653 
656  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
657  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) {
658  if (A.getLength() != B.getLength())
659  return false;
660 
661  if (A.ValueToNumber.size() != B.ValueToNumber.size())
662  return false;
663 
664  iterator ItA = A.begin();
665  iterator ItB = B.begin();
666 
667  // These ValueNumber Mapping sets create a create a mapping between the values
668  // in one candidate to values in the other candidate. If we create a set with
669  // one element, and that same element maps to the original element in the
670  // candidate we have a good mapping.
672 
673 
674  // Iterate over the instructions contained in each candidate
675  unsigned SectionLength = A.getStartIdx() + A.getLength();
676  for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
677  ItA++, ItB++, Loc++) {
678  // Make sure the instructions are similar to one another.
679  if (!isClose(*ItA, *ItB))
680  return false;
681 
682  Instruction *IA = ItA->Inst;
683  Instruction *IB = ItB->Inst;
684 
685  if (!ItA->Legal || !ItB->Legal)
686  return false;
687 
688  // Get the operand sets for the instructions.
689  ArrayRef<Value *> OperValsA = ItA->OperVals;
690  ArrayRef<Value *> OperValsB = ItB->OperVals;
691 
692  unsigned InstValA = A.ValueToNumber.find(IA)->second;
693  unsigned InstValB = B.ValueToNumber.find(IB)->second;
694 
695  bool WasInserted;
696  // Ensure that the mappings for the instructions exists.
697  std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(
698  std::make_pair(InstValA, DenseSet<unsigned>({InstValB})));
699  if (!WasInserted && !ValueMappingIt->second.contains(InstValB))
700  return false;
701 
702  std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingB.insert(
703  std::make_pair(InstValB, DenseSet<unsigned>({InstValA})));
704  if (!WasInserted && !ValueMappingIt->second.contains(InstValA))
705  return false;
706 
707  // We have different paths for commutative instructions and non-commutative
708  // instructions since commutative instructions could allow multiple mappings
709  // to certain values.
710  if (IA->isCommutative() && !isa<FPMathOperator>(IA)) {
712  {A, OperValsA, ValueNumberMappingA},
713  {B, OperValsB, ValueNumberMappingB}))
714  return false;
715  continue;
716  }
717 
718  // Handle the non-commutative cases.
720  {A, OperValsA, ValueNumberMappingA},
721  {B, OperValsB, ValueNumberMappingB}))
722  return false;
723 
724  // Here we check that between two corresponding instructions,
725  // when referring to a basic block in the same region, the
726  // relative locations are the same. And, that the instructions refer to
727  // basic blocks outside the region in the same corresponding locations.
728 
729  // We are able to make the assumption about blocks outside of the region
730  // since the target block labels are considered values and will follow the
731  // same number matching that we defined for the other instructions in the
732  // region. So, at this point, in each location we target a specific block
733  // outside the region, we are targeting a corresponding block in each
734  // analagous location in the region we are comparing to.
735  if (!(isa<BranchInst>(IA) && isa<BranchInst>(IB)) &&
736  !(isa<PHINode>(IA) && isa<PHINode>(IB)))
737  continue;
738 
739  SmallVector<int, 4> &RelBlockLocsA = ItA->RelativeBlockLocations;
740  SmallVector<int, 4> &RelBlockLocsB = ItB->RelativeBlockLocations;
741  if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
742  OperValsA.size() != OperValsB.size())
743  return false;
744 
745  ZippedRelativeLocationsT ZippedRelativeLocations =
746  zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
747  if (any_of(ZippedRelativeLocations,
748  [&A, &B](std::tuple<int, int, Value *, Value *> R) {
749  return !checkRelativeLocations(
750  {A, std::get<0>(R), std::get<2>(R)},
751  {B, std::get<1>(R), std::get<3>(R)});
752  }))
753  return false;
754  }
755  return true;
756 }
757 
759  const IRSimilarityCandidate &B) {
760  auto DoesOverlap = [](const IRSimilarityCandidate &X,
761  const IRSimilarityCandidate &Y) {
762  // Check:
763  // XXXXXX X starts before Y ends
764  // YYYYYYY Y starts after X starts
765  return X.StartIdx <= Y.getEndIdx() && Y.StartIdx >= X.StartIdx;
766  };
767 
768  return DoesOverlap(A, B) || DoesOverlap(B, A);
769 }
770 
771 void IRSimilarityIdentifier::populateMapper(
772  Module &M, std::vector<IRInstructionData *> &InstrList,
773  std::vector<unsigned> &IntegerMapping) {
774 
775  std::vector<IRInstructionData *> InstrListForModule;
776  std::vector<unsigned> IntegerMappingForModule;
777  // Iterate over the functions in the module to map each Instruction in each
778  // BasicBlock to an unsigned integer.
779  Mapper.initializeForBBs(M);
780 
781  for (Function &F : M) {
782 
783  if (F.empty())
784  continue;
785 
786  for (BasicBlock &BB : F) {
787 
788  // BB has potential to have similarity since it has a size greater than 2
789  // and can therefore match other regions greater than 2. Map it to a list
790  // of unsigned integers.
791  Mapper.convertToUnsignedVec(BB, InstrListForModule,
792  IntegerMappingForModule);
793  }
794 
795  BasicBlock::iterator It = F.begin()->end();
796  Mapper.mapToIllegalUnsigned(It, IntegerMappingForModule, InstrListForModule,
797  true);
798  if (InstrListForModule.size() > 0)
799  Mapper.IDL->push_back(*InstrListForModule.back());
800  }
801 
802  // Insert the InstrListForModule at the end of the overall InstrList so that
803  // we can have a long InstrList for the entire set of Modules being analyzed.
804  llvm::append_range(InstrList, InstrListForModule);
805  // Do the same as above, but for IntegerMapping.
806  llvm::append_range(IntegerMapping, IntegerMappingForModule);
807 }
808 
809 void IRSimilarityIdentifier::populateMapper(
810  ArrayRef<std::unique_ptr<Module>> &Modules,
811  std::vector<IRInstructionData *> &InstrList,
812  std::vector<unsigned> &IntegerMapping) {
813 
814  // Iterate over, and map the instructions in each module.
815  for (const std::unique_ptr<Module> &M : Modules)
816  populateMapper(*M, InstrList, IntegerMapping);
817 }
818 
819 /// From a repeated subsequence, find all the different instances of the
820 /// subsequence from the \p InstrList, and create an IRSimilarityCandidate from
821 /// the IRInstructionData in subsequence.
822 ///
823 /// \param [in] Mapper - The instruction mapper for sanity checks.
824 /// \param [in] InstrList - The vector that holds the instruction data.
825 /// \param [in] IntegerMapping - The vector that holds the mapped integers.
826 /// \param [out] CandsForRepSubstring - The vector to store the generated
827 /// IRSimilarityCandidates.
829  const IRInstructionMapper& Mapper, std::vector<IRInstructionData *> &InstrList,
830  std::vector<unsigned> &IntegerMapping, SuffixTree::RepeatedSubstring &RS,
831  std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
832 
833  unsigned StringLen = RS.Length;
834  if (StringLen < 2)
835  return;
836 
837  // Create an IRSimilarityCandidate for instance of this subsequence \p RS.
838  for (const unsigned &StartIdx : RS.StartIndices) {
839  unsigned EndIdx = StartIdx + StringLen - 1;
840 
841  // Check that this subsequence does not contain an illegal instruction.
842  bool ContainsIllegal = false;
843  for (unsigned CurrIdx = StartIdx; CurrIdx <= EndIdx; CurrIdx++) {
844  unsigned Key = IntegerMapping[CurrIdx];
845  if (Key > Mapper.IllegalInstrNumber) {
846  ContainsIllegal = true;
847  break;
848  }
849  }
850 
851  // If we have an illegal instruction, we should not create an
852  // IRSimilarityCandidate for this region.
853  if (ContainsIllegal)
854  continue;
855 
856  // We are getting iterators to the instructions in this region of code
857  // by advancing the start and end indices from the start of the
858  // InstrList.
859  std::vector<IRInstructionData *>::iterator StartIt = InstrList.begin();
860  std::advance(StartIt, StartIdx);
861  std::vector<IRInstructionData *>::iterator EndIt = InstrList.begin();
862  std::advance(EndIt, EndIdx);
863 
864  CandsForRepSubstring.emplace_back(StartIdx, StringLen, *StartIt, *EndIt);
865  }
866 }
867 
869  IRSimilarityCandidate &SourceCand,
870  DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
871  DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping) {
872  assert(SourceCand.CanonNumToNumber.size() != 0 &&
873  "Base canonical relationship is empty!");
874  assert(SourceCand.NumberToCanonNum.size() != 0 &&
875  "Base canonical relationship is empty!");
876 
877  assert(CanonNumToNumber.size() == 0 && "Canonical Relationship is non-empty");
878  assert(NumberToCanonNum.size() == 0 && "Canonical Relationship is non-empty");
879 
880  DenseSet<unsigned> UsedGVNs;
881  // Iterate over the mappings provided from this candidate to SourceCand. We
882  // are then able to map the GVN in this candidate to the same canonical number
883  // given to the corresponding GVN in SourceCand.
884  for (std::pair<unsigned, DenseSet<unsigned>> &GVNMapping : ToSourceMapping) {
885  unsigned SourceGVN = GVNMapping.first;
886 
887  assert(GVNMapping.second.size() != 0 && "Possible GVNs is 0!");
888 
889  unsigned ResultGVN;
890  // We need special handling if we have more than one potential value. This
891  // means that there are at least two GVNs that could correspond to this GVN.
892  // This could lead to potential swapping later on, so we make a decision
893  // here to ensure a one-to-one mapping.
894  if (GVNMapping.second.size() > 1) {
895  bool Found = false;
896  for (unsigned Val : GVNMapping.second) {
897  // We make sure the target value number hasn't already been reserved.
898  if (UsedGVNs.find(Val) != UsedGVNs.end())
899  continue;
900 
901  // We make sure that the opposite mapping is still consistent.
903  FromSourceMapping.find(Val);
904 
905  if (It->second.find(SourceGVN) == It->second.end())
906  continue;
907 
908  // We pick the first item that satisfies these conditions.
909  Found = true;
910  ResultGVN = Val;
911  break;
912  }
913 
914  assert(Found && "Could not find matching value for source GVN");
915  (void)Found;
916 
917  } else
918  ResultGVN = *GVNMapping.second.begin();
919 
920  // Whatever GVN is found, we mark it as used.
921  UsedGVNs.insert(ResultGVN);
922 
923  unsigned CanonNum = *SourceCand.getCanonicalNum(ResultGVN);
924  CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN));
925  NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum));
926  }
927 }
928 
930  IRSimilarityCandidate &CurrCand) {
931  assert(CurrCand.CanonNumToNumber.size() == 0 &&
932  "Canonical Relationship is non-empty");
933  assert(CurrCand.NumberToCanonNum.size() == 0 &&
934  "Canonical Relationship is non-empty");
935 
936  unsigned CanonNum = 0;
937  // Iterate over the value numbers found, the order does not matter in this
938  // case.
939  for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {
940  CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum));
941  CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first));
942  CanonNum++;
943  }
944 }
945 
946 /// From the list of IRSimilarityCandidates, perform a comparison between each
947 /// IRSimilarityCandidate to determine if there are overlapping
948 /// IRInstructionData, or if they do not have the same structure.
949 ///
950 /// \param [in] CandsForRepSubstring - The vector containing the
951 /// IRSimilarityCandidates.
952 /// \param [out] StructuralGroups - the mapping of unsigned integers to vector
953 /// of IRSimilarityCandidates where each of the IRSimilarityCandidates in the
954 /// vector are structurally similar to one another.
956  std::vector<IRSimilarityCandidate> &CandsForRepSubstring,
957  DenseMap<unsigned, SimilarityGroup> &StructuralGroups) {
958  std::vector<IRSimilarityCandidate>::iterator CandIt, CandEndIt, InnerCandIt,
959  InnerCandEndIt;
960 
961  // IRSimilarityCandidates each have a structure for operand use. It is
962  // possible that two instances of the same subsequences have different
963  // structure. Each type of structure found is assigned a number. This
964  // DenseMap maps an IRSimilarityCandidate to which type of similarity
965  // discovered it fits within.
967 
968  // Find the compatibility from each candidate to the others to determine
969  // which candidates overlap and which have the same structure by mapping
970  // each structure to a different group.
971  bool SameStructure;
972  bool Inserted;
973  unsigned CurrentGroupNum = 0;
974  unsigned OuterGroupNum;
978 
979  // Iterate over the candidates to determine its structural and overlapping
980  // compatibility with other instructions
981  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
982  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingB;
983  for (CandIt = CandsForRepSubstring.begin(),
984  CandEndIt = CandsForRepSubstring.end();
985  CandIt != CandEndIt; CandIt++) {
986 
987  // Determine if it has an assigned structural group already.
988  CandToGroupIt = CandToGroup.find(&*CandIt);
989  if (CandToGroupIt == CandToGroup.end()) {
990  // If not, we assign it one, and add it to our mapping.
991  std::tie(CandToGroupIt, Inserted) =
992  CandToGroup.insert(std::make_pair(&*CandIt, CurrentGroupNum++));
993  }
994 
995  // Get the structural group number from the iterator.
996  OuterGroupNum = CandToGroupIt->second;
997 
998  // Check if we already have a list of IRSimilarityCandidates for the current
999  // structural group. Create one if one does not exist.
1000  CurrentGroupPair = StructuralGroups.find(OuterGroupNum);
1001  if (CurrentGroupPair == StructuralGroups.end()) {
1003  std::tie(CurrentGroupPair, Inserted) = StructuralGroups.insert(
1004  std::make_pair(OuterGroupNum, SimilarityGroup({*CandIt})));
1005  }
1006 
1007  // Iterate over the IRSimilarityCandidates following the current
1008  // IRSimilarityCandidate in the list to determine whether the two
1009  // IRSimilarityCandidates are compatible. This is so we do not repeat pairs
1010  // of IRSimilarityCandidates.
1011  for (InnerCandIt = std::next(CandIt),
1012  InnerCandEndIt = CandsForRepSubstring.end();
1013  InnerCandIt != InnerCandEndIt; InnerCandIt++) {
1014 
1015  // We check if the inner item has a group already, if it does, we skip it.
1016  CandToGroupItInner = CandToGroup.find(&*InnerCandIt);
1017  if (CandToGroupItInner != CandToGroup.end())
1018  continue;
1019 
1020  // Otherwise we determine if they have the same structure and add it to
1021  // vector if they match.
1022  ValueNumberMappingA.clear();
1023  ValueNumberMappingB.clear();
1025  *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);
1026  if (!SameStructure)
1027  continue;
1028 
1029  InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA,
1030  ValueNumberMappingB);
1031  CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
1032  CurrentGroupPair->second.push_back(*InnerCandIt);
1033  }
1034  }
1035 }
1036 
1037 void IRSimilarityIdentifier::findCandidates(
1038  std::vector<IRInstructionData *> &InstrList,
1039  std::vector<unsigned> &IntegerMapping) {
1040  SuffixTree ST(IntegerMapping);
1041 
1042  std::vector<IRSimilarityCandidate> CandsForRepSubstring;
1043  std::vector<SimilarityGroup> NewCandidateGroups;
1044 
1045  DenseMap<unsigned, SimilarityGroup> StructuralGroups;
1046 
1047  // Iterate over the subsequences found by the Suffix Tree to create
1048  // IRSimilarityCandidates for each repeated subsequence and determine which
1049  // instances are structurally similar to one another.
1050  for (SuffixTree::RepeatedSubstring &RS : ST) {
1051  createCandidatesFromSuffixTree(Mapper, InstrList, IntegerMapping, RS,
1052  CandsForRepSubstring);
1053 
1054  if (CandsForRepSubstring.size() < 2)
1055  continue;
1056 
1057  findCandidateStructures(CandsForRepSubstring, StructuralGroups);
1058  for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups)
1059  // We only add the group if it contains more than one
1060  // IRSimilarityCandidate. If there is only one, that means there is no
1061  // other repeated subsequence with the same structure.
1062  if (Group.second.size() > 1)
1063  SimilarityCandidates->push_back(Group.second);
1064 
1065  CandsForRepSubstring.clear();
1066  StructuralGroups.clear();
1067  NewCandidateGroups.clear();
1068  }
1069 }
1070 
1072  ArrayRef<std::unique_ptr<Module>> Modules) {
1074 
1075  std::vector<IRInstructionData *> InstrList;
1076  std::vector<unsigned> IntegerMapping;
1077  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
1078 
1079  populateMapper(Modules, InstrList, IntegerMapping);
1080  findCandidates(InstrList, IntegerMapping);
1081 
1082  return SimilarityCandidates.getValue();
1083 }
1084 
1087  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
1088 
1089  std::vector<IRInstructionData *> InstrList;
1090  std::vector<unsigned> IntegerMapping;
1091 
1092  populateMapper(M, InstrList, IntegerMapping);
1093  findCandidates(InstrList, IntegerMapping);
1094 
1095  return SimilarityCandidates.getValue();
1096 }
1097 
1099  "ir-similarity-identifier", false, true)
1100 
1102  : ModulePass(ID) {
1105 }
1106 
1108  IRSI.reset(new IRSimilarityIdentifier(!DisableBranches));
1109  return false;
1110 }
1111 
1113  IRSI.reset();
1114  return false;
1115 }
1116 
1118  IRSI->findSimilarity(M);
1119  return false;
1120 }
1121 
1122 AnalysisKey IRSimilarityAnalysis::Key;
1125 
1127  IRSI.findSimilarity(M);
1128  return IRSI;
1129 }
1130 
1134  Optional<SimilarityGroupList> &SimilarityCandidatesOpt = IRSI.getSimilarity();
1135 
1136  for (std::vector<IRSimilarityCandidate> &CandVec : *SimilarityCandidatesOpt) {
1137  OS << CandVec.size() << " candidates of length "
1138  << CandVec.begin()->getLength() << ". Found in: \n";
1139  for (IRSimilarityCandidate &Cand : CandVec) {
1140  OS << " Function: " << Cand.front()->Inst->getFunction()->getName().str()
1141  << ", Basic Block: ";
1142  if (Cand.front()->Inst->getParent()->getName().str() == "")
1143  OS << "(unnamed)";
1144  else
1145  OS << Cand.front()->Inst->getParent()->getName().str();
1146  OS << "\n Start Instruction: ";
1147  Cand.frontInstruction()->print(OS);
1148  OS << "\n End Instruction: ";
1149  Cand.backInstruction()->print(OS);
1150  OS << "\n";
1151  }
1152  }
1153 
1154  return PreservedAnalyses::all();
1155 }
1156 
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::SuffixTree::RepeatedSubstring::Length
unsigned Length
The length of the string.
Definition: SuffixTree.h:145
llvm::IRSimilarity::IRSimilarityCandidate::getCanonicalNum
Optional< unsigned > getCanonicalNum(unsigned N)
Find the canonical number from the global value number N stored in the candidate.
Definition: IRSimilarityIdentifier.h:822
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:836
llvm::IRSimilarity::IRSimilarityCandidate::compareCommutativeOperandMapping
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 ...
Definition: IRSimilarityIdentifier.cpp:579
llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity
SimilarityGroupList & findSimilarity(ArrayRef< std::unique_ptr< Module >> Modules)
Definition: IRSimilarityIdentifier.cpp:1071
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
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
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
llvm::IRSimilarity::IRInstructionData::setBranchSuccessors
void setBranchSuccessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)
For an IRInstructionData containing a branch, finds the relative distances from the source basic bloc...
Definition: IRSimilarityIdentifier.cpp:65
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3178
llvm::IRSimilarity::isClose
bool isClose(const IRInstructionData &A, const IRInstructionData &B)
Compare one IRInstructionData class to another IRInstructionData class for whether they are performin...
Definition: IRSimilarityIdentifier.cpp:121
llvm::IRSimilarity::IRInstructionDataList
Definition: IRSimilarityIdentifier.h:241
llvm::IRSimilarity::IRInstructionMapper::BasicBlockToInteger
DenseMap< BasicBlock *, unsigned > BasicBlockToInteger
A mapping for a basic block in a module to its assigned number/location in the module.
Definition: IRSimilarityIdentifier.h:334
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
llvm::IRSimilarity::IRInstructionMapper::LegalInstrNumber
unsigned LegalInstrNumber
The next available integer to assign to a legal Instruction to.
Definition: IRSimilarityIdentifier.h:326
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::Function
Definition: Function.h:61
llvm::IRSimilarity::IRSimilarityCandidate::compareStructure
static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:642
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:996
llvm::ArrayRef::iterator
const_pointer iterator
Definition: ArrayRef.h:50
llvm::SmallVector< int, 4 >
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::find
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
llvm::IRSimilarity::IRSimilarityCandidate::compareNonCommutativeOperandMapping
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 ...
Definition: IRSimilarityIdentifier.cpp:545
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:75
llvm::SuffixTree::RepeatedSubstring::StartIndices
std::vector< unsigned > StartIndices
The start indices of each occurrence.
Definition: SuffixTree.h:148
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::begin
iterator begin()
Definition: DenseMap.h:74
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::IRSimilarity::IRSimilarityIdentifier::getSimilarity
Optional< SimilarityGroupList > & getSimilarity()
Definition: IRSimilarityIdentifier.h:948
llvm::IRSimilarity::IRInstructionData::RevisedPredicate
Optional< CmpInst::Predicate > RevisedPredicate
This is only relevant if we are wrapping a CmpInst where we needed to change the predicate of a compa...
Definition: IRSimilarityIdentifier.h:129
DenseMap.h
llvm::SuffixTree
A data structure for fast substring queries.
Definition: SuffixTree.h:137
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:857
llvm::Optional< SimilarityGroupList >
llvm::IRSimilarity::IRSimilarityIdentifier::resetSimilarityCandidates
void resetSimilarityCandidates()
Definition: IRSimilarityIdentifier.h:936
Operator.h
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:858
llvm::DenseMap::swap
void swap(DenseMap &RHS)
Definition: DenseMap.h:758
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::CmpInst::FCMP_OGT
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:724
llvm::cl::ReallyHidden
@ ReallyHidden
Definition: CommandLine.h:144
llvm::IRSimilarity::IRInstructionMapper::IDLAllocator
SpecificBumpPtrAllocator< IRInstructionDataList > * IDLAllocator
This allocator pointer is in charge of creating the IRInstructionDataList so it is not deallocated un...
Definition: IRSimilarityIdentifier.h:357
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::IRSimilarity::IRInstructionMapper::IDL
IRInstructionDataList * IDL
Definition: IRSimilarityIdentifier.h:383
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
llvm::IRSimilarity::IRSimilarityCandidate::IRSimilarityCandidate
IRSimilarityCandidate(unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt)
Definition: IRSimilarityIdentifier.cpp:325
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1551
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::EnableBranches
bool EnableBranches
Definition: IRSimilarityIdentifier.h:500
llvm::IRSimilarityIdentifierWrapperPass
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
Definition: IRSimilarityIdentifier.h:976
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::IRSimilarity::Illegal
@ Illegal
Definition: IRSimilarityIdentifier.h:75
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
findCandidateStructures
static void findCandidateStructures(std::vector< IRSimilarityCandidate > &CandsForRepSubstring, DenseMap< unsigned, SimilarityGroup > &StructuralGroups)
From the list of IRSimilarityCandidates, perform a comparison between each IRSimilarityCandidate to d...
Definition: IRSimilarityIdentifier.cpp:955
llvm::CmpInst::FCMP_UGE
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:733
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
false
Definition: StackSlotColoring.cpp:142
llvm::IRSimilarity::IRInstructionMapper
Helper struct for converting the Instructions in a Module into a vector of unsigned integers.
Definition: IRSimilarityIdentifier.h:319
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping
Definition: IRSimilarityIdentifier.h:615
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::IRSimilarity::IRInstructionMapper::HaveLegalRange
bool HaveLegalRange
Marks whether we have found a set of instructions that is long enough to be considered for similarity...
Definition: IRSimilarityIdentifier.h:347
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:45
llvm::IRSimilarity::IRSimilarityCandidate::isSimilar
static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:382
llvm::IRSimilarity::IRSimilarityCandidate::iterator
IRInstructionDataList::iterator iterator
Definition: IRSimilarityIdentifier.h:849
llvm::IRSimilarity::IRInstructionMapper::InstDataAllocator
SpecificBumpPtrAllocator< IRInstructionData > * InstDataAllocator
This allocator pointer is in charge of holding on to the IRInstructionData so it is not deallocated u...
Definition: IRSimilarityIdentifier.h:352
llvm::IRSimilarity::IRInstructionMapper::InstClassifier
InstructionClassification InstClassifier
Maps an Instruction to a member of InstrType.
Definition: IRSimilarityIdentifier.h:504
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:758
checkNumberingAndReplace
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...
Definition: IRSimilarityIdentifier.cpp:501
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
ZippedRelativeLocationsT
detail::zippy< detail::zip_shortest, SmallVector< int, 4 > &, SmallVector< int, 4 > &, ArrayRef< Value * > &, ArrayRef< Value * > & > ZippedRelativeLocationsT
Definition: IRSimilarityIdentifier.cpp:652
llvm::DenseSet< unsigned >
llvm::cl::opt< bool >
llvm::IRSimilarityIdentifierWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: IRSimilarityIdentifier.cpp:1117
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::IRSimilarity::IRInstructionMapper::InstructionIntegerMap
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits > InstructionIntegerMap
Correspondence from IRInstructionData to unsigned integers.
Definition: IRSimilarityIdentifier.h:330
checkNumberingAndReplaceCommutative
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 ...
Definition: IRSimilarityIdentifier.cpp:417
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:75
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::IRSimilarity::IRSimilarityCandidate::overlap
static bool overlap(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap.
Definition: IRSimilarityIdentifier.cpp:758
llvm::SuffixTree::RepeatedSubstring
A repeated substring in the tree.
Definition: SuffixTree.h:143
llvm::IRSimilarityAnalysis::run
Result run(Module &M, ModuleAnalysisManager &)
Definition: IRSimilarityIdentifier.cpp:1123
llvm::IRSimilarity::IRInstructionMapper::allocateIRInstructionData
IRInstructionData * allocateIRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Get an allocated IRInstructionData struct using the InstDataAllocator.
Definition: IRSimilarityIdentifier.cpp:274
llvm::DenseMap< BasicBlock *, unsigned >
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
getCalledFunctionName
static StringRef getCalledFunctionName(CallInst &CI)
Definition: IRSimilarityIdentifier.cpp:115
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::InstVisitor::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:88
llvm::detail::zippy
Definition: STLExtras.h:703
llvm::IRSimilarity::IRInstructionMapper::convertToUnsignedVec
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.
Definition: IRSimilarityIdentifier.cpp:192
llvm::IRSimilarityIdentifierWrapperPass::doFinalization
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: IRSimilarityIdentifier.cpp:1112
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::IRSimilarity::IRInstructionData::predicateForConsistency
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.
Definition: IRSimilarityIdentifier.cpp:89
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::simple_ilist::push_back
void push_back(reference Node)
Insert a node at the back; never copies.
Definition: simple_ilist.h:147
SuffixTree.h
llvm::CmpInst::FCMP_OGE
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:725
llvm::IRSimilarity::IRInstructionData
This provides the utilities for hashing an Instruction to an unsigned integer.
Definition: IRSimilarityIdentifier.h:113
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
llvm::IRSimilarity::IRInstructionData::IRInstructionData
IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Gather the information that is difficult to gather for an Instruction, or is changed.
Definition: IRSimilarityIdentifier.cpp:32
llvm::IRSimilarity::IRInstructionMapper::mapToIllegalUnsigned
unsigned mapToIllegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB, bool End=false)
Maps an Instruction to an illegal integer.
Definition: IRSimilarityIdentifier.cpp:291
llvm::initializeIRSimilarityIdentifierWrapperPassPass
void initializeIRSimilarityIdentifierWrapperPassPass(PassRegistry &)
llvm::IRSimilarityAnalysisPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: IRSimilarityIdentifier.cpp:1132
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:736
llvm::IRSimilarity::IRSimilarityCandidate::createCanonicalMappingFor
static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand)
Create a mapping from the value numbering to a different separate set of numbers.
Definition: IRSimilarityIdentifier.cpp:929
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::IRSimilarity::IRInstructionData::RelativeBlockLocations
SmallVector< int, 4 > RelativeBlockLocations
This structure holds the distances of how far "ahead of" or "behind" the target blocks of a branch,...
Definition: IRSimilarityIdentifier.h:153
llvm::IRSimilarity::IRInstructionData::Inst
Instruction * Inst
The source Instruction that is being wrapped.
Definition: IRSimilarityIdentifier.h:117
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1558
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::IRSimilarityIdentifierWrapperPass::ID
static char ID
Definition: IRSimilarityIdentifier.h:980
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::detail::DenseSetImpl::contains
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
llvm::IRSimilarity::IRInstructionMapper::mapToLegalUnsigned
unsigned mapToLegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)
Maps an Instruction to a legal integer.
Definition: IRSimilarityIdentifier.cpp:226
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::IRSimilarity::IRSimilarityCandidate::createCanonicalRelationFrom
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...
Definition: IRSimilarityIdentifier.cpp:868
llvm::CmpInst::FCMP_UGT
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:732
llvm::IRSimilarityIdentifierWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: IRSimilarityIdentifier.cpp:1107
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::IRSimilarity::IRInstructionMapper::IllegalInstrNumber
unsigned IllegalInstrNumber
The starting illegal instruction number to map to.
Definition: IRSimilarityIdentifier.h:323
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::IRSimilarity::IRInstructionMapper::allocateIRInstructionDataList
IRInstructionDataList * allocateIRInstructionDataList()
Get an allocated IRInstructionDataList object using the IDLAllocator.
Definition: IRSimilarityIdentifier.cpp:285
llvm::IRSimilarity::IRSimilarityCandidate::checkRelativeLocations
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...
Definition: IRSimilarityIdentifier.cpp:614
IRSimilarityIdentifier.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
llvm::IRSimilarity::IRSimilarityCandidate
This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...
Definition: IRSimilarityIdentifier.h:549
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::IRSimilarity::IRInstructionMapper::initializeForBBs
void initializeForBBs(Function &F, unsigned &BBNumber)
Assigns values to all the basic blocks in function F starting from integer BBNumber.
Definition: IRSimilarityIdentifier.h:390
Predicate
llvm::IRSimilarity::IRInstructionData::initializeInstruction
void initializeInstruction()
Fills data stuctures for IRInstructionData when it is constructed from a.
Definition: IRSimilarityIdentifier.cpp:38
User.h
llvm::IRSimilarity::IRInstructionData::getPredicate
CmpInst::Predicate getPredicate() const
Get the predicate that the compare instruction is using for hashing the instruction.
Definition: IRSimilarityIdentifier.cpp:105
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping
A helper struct to hold the candidate, for a branch instruction, the relative location of a label,...
Definition: IRSimilarityIdentifier.h:631
llvm::DenseMapBase::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
INITIALIZE_PASS
INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier", "ir-similarity-identifier", false, true) IRSimilarityIdentifierWrapperPass
Definition: IRSimilarityIdentifier.cpp:1098
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::IRSimilarity::IRInstructionMapper::AddedIllegalLastTime
bool AddedIllegalLastTime
Set if we added an illegal number in the previous step.
Definition: IRSimilarityIdentifier.h:340
DisableBranches
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."))
createCandidatesFromSuffixTree
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,...
Definition: IRSimilarityIdentifier.cpp:828
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::IRSimilarity::IRInstructionMapper::CanCombineWithPrevInstr
bool CanCombineWithPrevInstr
Marks whether we found a illegal instruction in the previous step.
Definition: IRSimilarityIdentifier.h:343
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
llvm::IRSimilarity::IRInstructionData::OperVals
SmallVector< Value *, 4 > OperVals
The values of the operands in the Instruction.
Definition: IRSimilarityIdentifier.h:119
BB
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
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:883
llvm::cl::desc
Definition: CommandLine.h:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::StringRef::compare
LLVM_NODISCARD int compare(StringRef RHS) const
compare - Compare two strings; the result is -1, 0, or 1 if this string is lexicographically less tha...
Definition: StringRef.h:201
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37