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