LLVM  16.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 
34  DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false),
36  cl::desc("disable outlining indirect calls."));
37 
39  MatchCallsByName("ir-sim-calls-by-name", cl::init(false), cl::ReallyHidden,
40  cl::desc("only allow matching call instructions if the "
41  "name and type signature match."));
42 
44  DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden,
45  cl::desc("Don't match or outline intrinsics"));
46 } // namespace llvm
47 
49  IRInstructionDataList &IDList)
50  : Inst(&I), Legal(Legality), IDL(&IDList) {
52 }
53 
55  // We check for whether we have a comparison instruction. If it is, we
56  // find the "less than" version of the predicate for consistency for
57  // comparison instructions throught the program.
58  if (CmpInst *C = dyn_cast<CmpInst>(Inst)) {
60  if (Predicate != C->getPredicate())
62  }
63 
64  // Here we collect the operands and their types for determining whether
65  // the structure of the operand use matches between two different candidates.
66  for (Use &OI : Inst->operands()) {
67  if (isa<CmpInst>(Inst) && RevisedPredicate) {
68  // If we have a CmpInst where the predicate is reversed, it means the
69  // operands must be reversed as well.
70  OperVals.insert(OperVals.begin(), OI.get());
71  continue;
72  }
73 
74  OperVals.push_back(OI.get());
75  }
76 
77  // We capture the incoming BasicBlocks as values as well as the incoming
78  // Values in order to check for structural similarity.
79  if (PHINode *PN = dyn_cast<PHINode>(Inst))
80  for (BasicBlock *BB : PN->blocks())
81  OperVals.push_back(BB);
82 }
83 
85  : IDL(&IDList) {}
86 
88  DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) {
89  assert(isa<BranchInst>(Inst) && "Instruction must be branch");
90 
91  BranchInst *BI = cast<BranchInst>(Inst);
93 
94  BBNumIt = BasicBlockToInteger.find(BI->getParent());
95  assert(BBNumIt != BasicBlockToInteger.end() &&
96  "Could not find location for BasicBlock!");
97 
98  int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
99 
100  for (BasicBlock *Successor : BI->successors()) {
101  BBNumIt = BasicBlockToInteger.find(Successor);
102  assert(BBNumIt != BasicBlockToInteger.end() &&
103  "Could not find number for BasicBlock!");
104  int OtherBlockNumber = static_cast<int>(BBNumIt->second);
105 
106  int Relative = OtherBlockNumber - CurrentBlockNumber;
107  RelativeBlockLocations.push_back(Relative);
108  }
109 }
110 
111 void IRInstructionData::setCalleeName(bool MatchByName) {
112  CallInst *CI = dyn_cast<CallInst>(Inst);
113  assert(CI && "Instruction must be call");
114 
115  CalleeName = "";
116  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
117  // To hash intrinsics, we use the opcode, and types like the other
118  // instructions, but also, the Intrinsic ID, and the Name of the
119  // intrinsic.
120  Intrinsic::ID IntrinsicID = II->getIntrinsicID();
121  FunctionType *FT = II->getFunctionType();
122  // If there is an overloaded name, we have to use the complex version
123  // of getName to get the entire string.
124  if (Intrinsic::isOverloaded(IntrinsicID))
125  CalleeName =
126  Intrinsic::getName(IntrinsicID, FT->params(), II->getModule(), FT);
127  // If there is not an overloaded name, we only need to use this version.
128  else
129  CalleeName = Intrinsic::getName(IntrinsicID).str();
130 
131  return;
132  }
133 
134  if (!CI->isIndirectCall() && MatchByName)
136 }
137 
139  DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) {
140  assert(isa<PHINode>(Inst) && "Instruction must be phi node");
141 
142  PHINode *PN = cast<PHINode>(Inst);
144 
145  BBNumIt = BasicBlockToInteger.find(PN->getParent());
146  assert(BBNumIt != BasicBlockToInteger.end() &&
147  "Could not find location for BasicBlock!");
148 
149  int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
150 
151  // Convert the incoming blocks of the PHINode to an integer value, based on
152  // the relative distances between the current block and the incoming block.
153  for (unsigned Idx = 0; Idx < PN->getNumIncomingValues(); Idx++) {
154  BasicBlock *Incoming = PN->getIncomingBlock(Idx);
155  BBNumIt = BasicBlockToInteger.find(Incoming);
156  assert(BBNumIt != BasicBlockToInteger.end() &&
157  "Could not find number for BasicBlock!");
158  int OtherBlockNumber = static_cast<int>(BBNumIt->second);
159 
160  int Relative = OtherBlockNumber - CurrentBlockNumber;
161  RelativeBlockLocations.push_back(Relative);
162  RelativeBlockLocations.push_back(Relative);
163  }
164 }
165 
167  switch (CI->getPredicate()) {
168  case CmpInst::FCMP_OGT:
169  case CmpInst::FCMP_UGT:
170  case CmpInst::FCMP_OGE:
171  case CmpInst::FCMP_UGE:
172  case CmpInst::ICMP_SGT:
173  case CmpInst::ICMP_UGT:
174  case CmpInst::ICMP_SGE:
175  case CmpInst::ICMP_UGE:
176  return CI->getSwappedPredicate();
177  default:
178  return CI->getPredicate();
179  }
180 }
181 
183  assert(isa<CmpInst>(Inst) &&
184  "Can only get a predicate from a compare instruction");
185 
186  if (RevisedPredicate)
187  return RevisedPredicate.value();
188 
189  return cast<CmpInst>(Inst)->getPredicate();
190 }
191 
193  assert(isa<CallInst>(Inst) &&
194  "Can only get a name from a call instruction");
195 
196  assert(CalleeName && "CalleeName has not been set");
197 
198  return *CalleeName;
199 }
200 
202  const IRInstructionData &B) {
203 
204  if (!A.Legal || !B.Legal)
205  return false;
206 
207  // Check if we are performing the same sort of operation on the same types
208  // but not on the same values.
209  if (!A.Inst->isSameOperationAs(B.Inst)) {
210  // If there is a predicate, this means that either there is a swapped
211  // predicate, or that the types are different, we want to make sure that
212  // the predicates are equivalent via swapping.
213  if (isa<CmpInst>(A.Inst) && isa<CmpInst>(B.Inst)) {
214 
215  if (A.getPredicate() != B.getPredicate())
216  return false;
217 
218  // If the predicates are the same via swap, make sure that the types are
219  // still the same.
220  auto ZippedTypes = zip(A.OperVals, B.OperVals);
221 
222  return all_of(
223  ZippedTypes, [](std::tuple<llvm::Value *, llvm::Value *> R) {
224  return std::get<0>(R)->getType() == std::get<1>(R)->getType();
225  });
226  }
227 
228  return false;
229  }
230 
231  // Since any GEP Instruction operands after the first operand cannot be
232  // defined by a register, we must make sure that the operands after the first
233  // are the same in the two instructions
234  if (auto *GEP = dyn_cast<GetElementPtrInst>(A.Inst)) {
235  auto *OtherGEP = cast<GetElementPtrInst>(B.Inst);
236 
237  // If the instructions do not have the same inbounds restrictions, we do
238  // not consider them the same.
239  if (GEP->isInBounds() != OtherGEP->isInBounds())
240  return false;
241 
242  auto ZippedOperands = zip(GEP->indices(), OtherGEP->indices());
243 
244  // We increment here since we do not care about the first instruction,
245  // we only care about the following operands since they must be the
246  // exact same to be considered similar.
247  return all_of(drop_begin(ZippedOperands),
248  [](std::tuple<llvm::Use &, llvm::Use &> R) {
249  return std::get<0>(R) == std::get<1>(R);
250  });
251  }
252 
253  // If the instructions are functions calls, we make sure that the function
254  // name is the same. We already know that the types are since is
255  // isSameOperationAs is true.
256  if (isa<CallInst>(A.Inst) && isa<CallInst>(B.Inst)) {
257  if (A.getCalleeName().str() != B.getCalleeName().str())
258  return false;
259  }
260 
261  if (isa<BranchInst>(A.Inst) && isa<BranchInst>(B.Inst) &&
262  A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())
263  return false;
264 
265  return true;
266 }
267 
268 // TODO: This is the same as the MachineOutliner, and should be consolidated
269 // into the same interface.
271  BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
272  std::vector<unsigned> &IntegerMapping) {
273  BasicBlock::iterator It = BB.begin();
274 
275  std::vector<unsigned> IntegerMappingForBB;
276  std::vector<IRInstructionData *> InstrListForBB;
277 
278  for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
279  switch (InstClassifier.visit(*It)) {
280  case InstrType::Legal:
281  mapToLegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
282  break;
283  case InstrType::Illegal:
284  mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB);
285  break;
287  AddedIllegalLastTime = false;
288  break;
289  }
290  }
291 
293  mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
294  for (IRInstructionData *ID : InstrListForBB)
295  this->IDL->push_back(*ID);
296  llvm::append_range(InstrList, InstrListForBB);
297  llvm::append_range(IntegerMapping, IntegerMappingForBB);
298 }
299 
300 // TODO: This is the same as the MachineOutliner, and should be consolidated
301 // into the same interface.
303  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
304  std::vector<IRInstructionData *> &InstrListForBB) {
305  // We added something legal, so we should unset the AddedLegalLastTime
306  // flag.
307  AddedIllegalLastTime = false;
308 
309  // If we have at least two adjacent legal instructions (which may have
310  // invisible instructions in between), remember that.
312  HaveLegalRange = true;
314 
315  // Get the integer for this instruction or give it the current
316  // LegalInstrNumber.
318  InstrListForBB.push_back(ID);
319 
320  if (isa<BranchInst>(*It))
321  ID->setBranchSuccessors(BasicBlockToInteger);
322 
323  if (isa<CallInst>(*It))
324  ID->setCalleeName(EnableMatchCallsByName);
325 
326  if (isa<PHINode>(*It))
327  ID->setPHIPredecessors(BasicBlockToInteger);
328 
329  // Add to the instruction list
330  bool WasInserted;
332  ResultIt;
333  std::tie(ResultIt, WasInserted) =
334  InstructionIntegerMap.insert(std::make_pair(ID, LegalInstrNumber));
335  unsigned INumber = ResultIt->second;
336 
337  // There was an insertion.
338  if (WasInserted)
340 
341  IntegerMappingForBB.push_back(INumber);
342 
343  // Make sure we don't overflow or use any integers reserved by the DenseMap.
345  "Instruction mapping overflow!");
346 
348  "Tried to assign DenseMap tombstone or empty key to instruction.");
350  "Tried to assign DenseMap tombstone or empty key to instruction.");
351 
352  return INumber;
353 }
354 
357  IRInstructionDataList &IDL) {
358  return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
359 }
360 
363  return new (InstDataAllocator->Allocate()) IRInstructionData(IDL);
364 }
365 
368  return new (IDLAllocator->Allocate()) IRInstructionDataList();
369 }
370 
371 // TODO: This is the same as the MachineOutliner, and should be consolidated
372 // into the same interface.
374  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
375  std::vector<IRInstructionData *> &InstrListForBB, bool End) {
376  // Can't combine an illegal instruction. Set the flag.
377  CanCombineWithPrevInstr = false;
378 
379  // Only add one illegal number per range of legal numbers.
381  return IllegalInstrNumber;
382 
383  IRInstructionData *ID = nullptr;
384  if (!End)
385  ID = allocateIRInstructionData(*It, false, *IDL);
386  else
388  InstrListForBB.push_back(ID);
389 
390  // Remember that we added an illegal number last time.
391  AddedIllegalLastTime = true;
392  unsigned INumber = IllegalInstrNumber;
393  IntegerMappingForBB.push_back(IllegalInstrNumber--);
394 
396  "Instruction mapping overflow!");
397 
399  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
400 
402  "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
403 
404  return INumber;
405 }
406 
407 IRSimilarityCandidate::IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
408  IRInstructionData *FirstInstIt,
409  IRInstructionData *LastInstIt)
410  : StartIdx(StartIdx), Len(Len) {
411 
412  assert(FirstInstIt != nullptr && "Instruction is nullptr!");
413  assert(LastInstIt != nullptr && "Instruction is nullptr!");
414  assert(StartIdx + Len > StartIdx &&
415  "Overflow for IRSimilarityCandidate range?");
416  assert(Len - 1 == static_cast<unsigned>(std::distance(
417  iterator(FirstInstIt), iterator(LastInstIt))) &&
418  "Length of the first and last IRInstructionData do not match the "
419  "given length");
420 
421  // We iterate over the given instructions, and map each unique value
422  // to a unique number in the IRSimilarityCandidate ValueToNumber and
423  // NumberToValue maps. A constant get its own value globally, the individual
424  // uses of the constants are not considered to be unique.
425  //
426  // IR: Mapping Added:
427  // %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2
428  // %add2 = add i32 %a, %1 %add2 -> 4
429  // %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5
430  //
431  // when replace with global values, starting from 1, would be
432  //
433  // 3 = add i32 1, 2
434  // 4 = add i32 1, 3
435  // 6 = add i32 5, 2
436  unsigned LocalValNumber = 1;
438  for (unsigned Loc = StartIdx; Loc < StartIdx + Len; Loc++, ID++) {
439  // Map the operand values to an unsigned integer if it does not already
440  // have an unsigned integer assigned to it.
441  for (Value *Arg : ID->OperVals)
442  if (ValueToNumber.find(Arg) == ValueToNumber.end()) {
443  ValueToNumber.try_emplace(Arg, LocalValNumber);
444  NumberToValue.try_emplace(LocalValNumber, Arg);
445  LocalValNumber++;
446  }
447 
448  // Mapping the instructions to an unsigned integer if it is not already
449  // exist in the mapping.
450  if (ValueToNumber.find(ID->Inst) == ValueToNumber.end()) {
451  ValueToNumber.try_emplace(ID->Inst, LocalValNumber);
452  NumberToValue.try_emplace(LocalValNumber, ID->Inst);
453  LocalValNumber++;
454  }
455  }
456 
457  // Setting the first and last instruction data pointers for the candidate. If
458  // we got through the entire for loop without hitting an assert, we know
459  // that both of these instructions are not nullptrs.
460  FirstInst = FirstInstIt;
461  LastInst = LastInstIt;
462 
463  // Add the basic blocks contained in the set into the global value numbering.
465  getBasicBlocks(BBSet);
466  for (BasicBlock *BB : BBSet) {
467  if (ValueToNumber.find(BB) != ValueToNumber.end())
468  continue;
469 
470  ValueToNumber.try_emplace(BB, LocalValNumber);
471  NumberToValue.try_emplace(LocalValNumber, BB);
472  LocalValNumber++;
473  }
474 }
475 
477  const IRSimilarityCandidate &B) {
478  if (A.getLength() != B.getLength())
479  return false;
480 
481  auto InstrDataForBoth =
482  zip(make_range(A.begin(), A.end()), make_range(B.begin(), B.end()));
483 
484  return all_of(InstrDataForBoth,
485  [](std::tuple<IRInstructionData &, IRInstructionData &> R) {
486  IRInstructionData &A = std::get<0>(R);
487  IRInstructionData &B = std::get<1>(R);
488  if (!A.Legal || !B.Legal)
489  return false;
490  return isClose(A, B);
491  });
492 }
493 
494 /// Determine if one or more of the assigned global value numbers for the
495 /// operands in \p TargetValueNumbers is in the current mapping set for operand
496 /// numbers in \p SourceOperands. The set of possible corresponding global
497 /// value numbers are replaced with the most recent version of compatible
498 /// values.
499 ///
500 /// \param [in] SourceValueToNumberMapping - The mapping of a Value to global
501 /// value number for the source IRInstructionCandidate.
502 /// \param [in, out] CurrentSrcTgtNumberMapping - The current mapping of source
503 /// IRSimilarityCandidate global value numbers to a set of possible numbers in
504 /// the target.
505 /// \param [in] SourceOperands - The operands in the original
506 /// IRSimilarityCandidate in the current instruction.
507 /// \param [in] TargetValueNumbers - The global value numbers of the operands in
508 /// the corresponding Instruction in the other IRSimilarityCandidate.
509 /// \returns true if there exists a possible mapping between the source
510 /// Instruction operands and the target Instruction operands, and false if not.
512  const DenseMap<Value *, unsigned> &SourceValueToNumberMapping,
513  DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
514  ArrayRef<Value *> &SourceOperands,
515  DenseSet<unsigned> &TargetValueNumbers){
516 
517  DenseMap<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
518 
519  unsigned ArgVal;
520  bool WasInserted;
521 
522  // Iterate over the operands in the source IRSimilarityCandidate to determine
523  // whether there exists an operand in the other IRSimilarityCandidate that
524  // creates a valid mapping of Value to Value between the
525  // IRSimilarityCaniddates.
526  for (Value *V : SourceOperands) {
527  ArgVal = SourceValueToNumberMapping.find(V)->second;
528 
529  // Instead of finding a current mapping, we attempt to insert a set.
530  std::tie(ValueMappingIt, WasInserted) = CurrentSrcTgtNumberMapping.insert(
531  std::make_pair(ArgVal, TargetValueNumbers));
532 
533  // We need to iterate over the items in other IRSimilarityCandidate's
534  // Instruction to determine whether there is a valid mapping of
535  // Value to Value.
536  DenseSet<unsigned> NewSet;
537  for (unsigned &Curr : ValueMappingIt->second)
538  // If we can find the value in the mapping, we add it to the new set.
539  if (TargetValueNumbers.contains(Curr))
540  NewSet.insert(Curr);
541 
542  // If we could not find a Value, return 0.
543  if (NewSet.empty())
544  return false;
545 
546  // Otherwise replace the old mapping with the newly constructed one.
547  if (NewSet.size() != ValueMappingIt->second.size())
548  ValueMappingIt->second.swap(NewSet);
549 
550  // We have reached no conclusions about the mapping, and cannot remove
551  // any items from the other operands, so we move to check the next operand.
552  if (ValueMappingIt->second.size() != 1)
553  continue;
554 
555  unsigned ValToRemove = *ValueMappingIt->second.begin();
556  // When there is only one item left in the mapping for and operand, remove
557  // the value from the other operands. If it results in there being no
558  // mapping, return false, it means the mapping is wrong
559  for (Value *InnerV : SourceOperands) {
560  if (V == InnerV)
561  continue;
562 
563  unsigned InnerVal = SourceValueToNumberMapping.find(InnerV)->second;
564  ValueMappingIt = CurrentSrcTgtNumberMapping.find(InnerVal);
565  if (ValueMappingIt == CurrentSrcTgtNumberMapping.end())
566  continue;
567 
568  ValueMappingIt->second.erase(ValToRemove);
569  if (ValueMappingIt->second.empty())
570  return false;
571  }
572  }
573 
574  return true;
575 }
576 
577 /// Determine if operand number \p TargetArgVal is in the current mapping set
578 /// for operand number \p SourceArgVal.
579 ///
580 /// \param [in, out] CurrentSrcTgtNumberMapping current mapping of global
581 /// value numbers from source IRSimilarityCandidate to target
582 /// IRSimilarityCandidate.
583 /// \param [in] SourceArgVal The global value number for an operand in the
584 /// in the original candidate.
585 /// \param [in] TargetArgVal The global value number for the corresponding
586 /// operand in the other candidate.
587 /// \returns True if there exists a mapping and false if not.
589  DenseMap<unsigned, DenseSet<unsigned>> &CurrentSrcTgtNumberMapping,
590  unsigned SourceArgVal, unsigned TargetArgVal) {
591  // We are given two unsigned integers representing the global values of
592  // the operands in different IRSimilarityCandidates and a current mapping
593  // between the two.
594  //
595  // Source Operand GVN: 1
596  // Target Operand GVN: 2
597  // CurrentMapping: {1: {1, 2}}
598  //
599  // Since we have mapping, and the target operand is contained in the set, we
600  // update it to:
601  // CurrentMapping: {1: {2}}
602  // and can return true. But, if the mapping was
603  // CurrentMapping: {1: {3}}
604  // we would return false.
605 
606  bool WasInserted;
608 
609  std::tie(Val, WasInserted) = CurrentSrcTgtNumberMapping.insert(
610  std::make_pair(SourceArgVal, DenseSet<unsigned>({TargetArgVal})));
611 
612  // If we created a new mapping, then we are done.
613  if (WasInserted)
614  return true;
615 
616  // If there is more than one option in the mapping set, and the target value
617  // is included in the mapping set replace that set with one that only includes
618  // the target value, as it is the only valid mapping via the non commutative
619  // instruction.
620 
621  DenseSet<unsigned> &TargetSet = Val->second;
622  if (TargetSet.size() > 1 && TargetSet.contains(TargetArgVal)) {
623  TargetSet.clear();
624  TargetSet.insert(TargetArgVal);
625  return true;
626  }
627 
628  // Return true if we can find the value in the set.
629  return TargetSet.contains(TargetArgVal);
630 }
631 
634  // Iterators to keep track of where we are in the operands for each
635  // Instruction.
636  ArrayRef<Value *>::iterator VItA = A.OperVals.begin();
637  ArrayRef<Value *>::iterator VItB = B.OperVals.begin();
638  unsigned OperandLength = A.OperVals.size();
639 
640  // For each operand, get the value numbering and ensure it is consistent.
641  for (unsigned Idx = 0; Idx < OperandLength; Idx++, VItA++, VItB++) {
642  unsigned OperValA = A.IRSC.ValueToNumber.find(*VItA)->second;
643  unsigned OperValB = B.IRSC.ValueToNumber.find(*VItB)->second;
644 
645  // Attempt to add a set with only the target value. If there is no mapping
646  // we can create it here.
647  //
648  // For an instruction like a subtraction:
649  // IRSimilarityCandidateA: IRSimilarityCandidateB:
650  // %resultA = sub %a, %b %resultB = sub %d, %e
651  //
652  // We map %a -> %d and %b -> %e.
653  //
654  // And check to see whether their mapping is consistent in
655  // checkNumberingAndReplace.
656 
657  if (!checkNumberingAndReplace(A.ValueNumberMapping, OperValA, OperValB))
658  return false;
659 
660  if (!checkNumberingAndReplace(B.ValueNumberMapping, OperValB, OperValA))
661  return false;
662  }
663  return true;
664 }
665 
668  DenseSet<unsigned> ValueNumbersA;
669  DenseSet<unsigned> ValueNumbersB;
670 
671  ArrayRef<Value *>::iterator VItA = A.OperVals.begin();
672  ArrayRef<Value *>::iterator VItB = B.OperVals.begin();
673  unsigned OperandLength = A.OperVals.size();
674 
675  // Find the value number sets for the operands.
676  for (unsigned Idx = 0; Idx < OperandLength;
677  Idx++, VItA++, VItB++) {
678  ValueNumbersA.insert(A.IRSC.ValueToNumber.find(*VItA)->second);
679  ValueNumbersB.insert(B.IRSC.ValueToNumber.find(*VItB)->second);
680  }
681 
682  // Iterate over the operands in the first IRSimilarityCandidate and make sure
683  // there exists a possible mapping with the operands in the second
684  // IRSimilarityCandidate.
685  if (!checkNumberingAndReplaceCommutative(A.IRSC.ValueToNumber,
686  A.ValueNumberMapping, A.OperVals,
687  ValueNumbersB))
688  return false;
689 
690  // Iterate over the operands in the second IRSimilarityCandidate and make sure
691  // there exists a possible mapping with the operands in the first
692  // IRSimilarityCandidate.
693  if (!checkNumberingAndReplaceCommutative(B.IRSC.ValueToNumber,
694  B.ValueNumberMapping, B.OperVals,
695  ValueNumbersA))
696  return false;
697 
698  return true;
699 }
700 
703  // Get the basic blocks the label refers to.
704  BasicBlock *ABB = static_cast<BasicBlock *>(A.OperVal);
705  BasicBlock *BBB = static_cast<BasicBlock *>(B.OperVal);
706 
707  // Get the basic blocks contained in each region.
708  DenseSet<BasicBlock *> BasicBlockA;
709  DenseSet<BasicBlock *> BasicBlockB;
710  A.IRSC.getBasicBlocks(BasicBlockA);
711  B.IRSC.getBasicBlocks(BasicBlockB);
712 
713  // Determine if the block is contained in the region.
714  bool AContained = BasicBlockA.contains(ABB);
715  bool BContained = BasicBlockB.contains(BBB);
716 
717  // Both blocks need to be contained in the region, or both need to be outside
718  // the reigon.
719  if (AContained != BContained)
720  return false;
721 
722  // If both are contained, then we need to make sure that the relative
723  // distance to the target blocks are the same.
724  if (AContained)
725  return A.RelativeLocation == B.RelativeLocation;
726  return true;
727 }
728 
730  const IRSimilarityCandidate &B) {
733  return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB);
734 }
735 
740 
743  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
744  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) {
745  if (A.getLength() != B.getLength())
746  return false;
747 
748  if (A.ValueToNumber.size() != B.ValueToNumber.size())
749  return false;
750 
751  iterator ItA = A.begin();
752  iterator ItB = B.begin();
753 
754  // These ValueNumber Mapping sets create a create a mapping between the values
755  // in one candidate to values in the other candidate. If we create a set with
756  // one element, and that same element maps to the original element in the
757  // candidate we have a good mapping.
759 
760 
761  // Iterate over the instructions contained in each candidate
762  unsigned SectionLength = A.getStartIdx() + A.getLength();
763  for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
764  ItA++, ItB++, Loc++) {
765  // Make sure the instructions are similar to one another.
766  if (!isClose(*ItA, *ItB))
767  return false;
768 
769  Instruction *IA = ItA->Inst;
770  Instruction *IB = ItB->Inst;
771 
772  if (!ItA->Legal || !ItB->Legal)
773  return false;
774 
775  // Get the operand sets for the instructions.
776  ArrayRef<Value *> OperValsA = ItA->OperVals;
777  ArrayRef<Value *> OperValsB = ItB->OperVals;
778 
779  unsigned InstValA = A.ValueToNumber.find(IA)->second;
780  unsigned InstValB = B.ValueToNumber.find(IB)->second;
781 
782  bool WasInserted;
783  // Ensure that the mappings for the instructions exists.
784  std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(
785  std::make_pair(InstValA, DenseSet<unsigned>({InstValB})));
786  if (!WasInserted && !ValueMappingIt->second.contains(InstValB))
787  return false;
788 
789  std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingB.insert(
790  std::make_pair(InstValB, DenseSet<unsigned>({InstValA})));
791  if (!WasInserted && !ValueMappingIt->second.contains(InstValA))
792  return false;
793 
794  // We have different paths for commutative instructions and non-commutative
795  // instructions since commutative instructions could allow multiple mappings
796  // to certain values.
797  if (IA->isCommutative() && !isa<FPMathOperator>(IA) &&
798  !isa<IntrinsicInst>(IA)) {
800  {A, OperValsA, ValueNumberMappingA},
801  {B, OperValsB, ValueNumberMappingB}))
802  return false;
803  continue;
804  }
805 
806  // Handle the non-commutative cases.
808  {A, OperValsA, ValueNumberMappingA},
809  {B, OperValsB, ValueNumberMappingB}))
810  return false;
811 
812  // Here we check that between two corresponding instructions,
813  // when referring to a basic block in the same region, the
814  // relative locations are the same. And, that the instructions refer to
815  // basic blocks outside the region in the same corresponding locations.
816 
817  // We are able to make the assumption about blocks outside of the region
818  // since the target block labels are considered values and will follow the
819  // same number matching that we defined for the other instructions in the
820  // region. So, at this point, in each location we target a specific block
821  // outside the region, we are targeting a corresponding block in each
822  // analagous location in the region we are comparing to.
823  if (!(isa<BranchInst>(IA) && isa<BranchInst>(IB)) &&
824  !(isa<PHINode>(IA) && isa<PHINode>(IB)))
825  continue;
826 
827  SmallVector<int, 4> &RelBlockLocsA = ItA->RelativeBlockLocations;
828  SmallVector<int, 4> &RelBlockLocsB = ItB->RelativeBlockLocations;
829  if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
830  OperValsA.size() != OperValsB.size())
831  return false;
832 
833  ZippedRelativeLocationsT ZippedRelativeLocations =
834  zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
835  if (any_of(ZippedRelativeLocations,
836  [&A, &B](std::tuple<int, int, Value *, Value *> R) {
837  return !checkRelativeLocations(
838  {A, std::get<0>(R), std::get<2>(R)},
839  {B, std::get<1>(R), std::get<3>(R)});
840  }))
841  return false;
842  }
843  return true;
844 }
845 
847  const IRSimilarityCandidate &B) {
848  auto DoesOverlap = [](const IRSimilarityCandidate &X,
849  const IRSimilarityCandidate &Y) {
850  // Check:
851  // XXXXXX X starts before Y ends
852  // YYYYYYY Y starts after X starts
853  return X.StartIdx <= Y.getEndIdx() && Y.StartIdx >= X.StartIdx;
854  };
855 
856  return DoesOverlap(A, B) || DoesOverlap(B, A);
857 }
858 
859 void IRSimilarityIdentifier::populateMapper(
860  Module &M, std::vector<IRInstructionData *> &InstrList,
861  std::vector<unsigned> &IntegerMapping) {
862 
863  std::vector<IRInstructionData *> InstrListForModule;
864  std::vector<unsigned> IntegerMappingForModule;
865  // Iterate over the functions in the module to map each Instruction in each
866  // BasicBlock to an unsigned integer.
867  Mapper.initializeForBBs(M);
868 
869  for (Function &F : M) {
870 
871  if (F.empty())
872  continue;
873 
874  for (BasicBlock &BB : F) {
875 
876  // BB has potential to have similarity since it has a size greater than 2
877  // and can therefore match other regions greater than 2. Map it to a list
878  // of unsigned integers.
879  Mapper.convertToUnsignedVec(BB, InstrListForModule,
880  IntegerMappingForModule);
881  }
882 
883  BasicBlock::iterator It = F.begin()->end();
884  Mapper.mapToIllegalUnsigned(It, IntegerMappingForModule, InstrListForModule,
885  true);
886  if (InstrListForModule.size() > 0)
887  Mapper.IDL->push_back(*InstrListForModule.back());
888  }
889 
890  // Insert the InstrListForModule at the end of the overall InstrList so that
891  // we can have a long InstrList for the entire set of Modules being analyzed.
892  llvm::append_range(InstrList, InstrListForModule);
893  // Do the same as above, but for IntegerMapping.
894  llvm::append_range(IntegerMapping, IntegerMappingForModule);
895 }
896 
897 void IRSimilarityIdentifier::populateMapper(
898  ArrayRef<std::unique_ptr<Module>> &Modules,
899  std::vector<IRInstructionData *> &InstrList,
900  std::vector<unsigned> &IntegerMapping) {
901 
902  // Iterate over, and map the instructions in each module.
903  for (const std::unique_ptr<Module> &M : Modules)
904  populateMapper(*M, InstrList, IntegerMapping);
905 }
906 
907 /// From a repeated subsequence, find all the different instances of the
908 /// subsequence from the \p InstrList, and create an IRSimilarityCandidate from
909 /// the IRInstructionData in subsequence.
910 ///
911 /// \param [in] Mapper - The instruction mapper for basic correctness checks.
912 /// \param [in] InstrList - The vector that holds the instruction data.
913 /// \param [in] IntegerMapping - The vector that holds the mapped integers.
914 /// \param [out] CandsForRepSubstring - The vector to store the generated
915 /// IRSimilarityCandidates.
917  const IRInstructionMapper& Mapper, std::vector<IRInstructionData *> &InstrList,
918  std::vector<unsigned> &IntegerMapping, SuffixTree::RepeatedSubstring &RS,
919  std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
920 
921  unsigned StringLen = RS.Length;
922  if (StringLen < 2)
923  return;
924 
925  // Create an IRSimilarityCandidate for instance of this subsequence \p RS.
926  for (const unsigned &StartIdx : RS.StartIndices) {
927  unsigned EndIdx = StartIdx + StringLen - 1;
928 
929  // Check that this subsequence does not contain an illegal instruction.
930  bool ContainsIllegal = false;
931  for (unsigned CurrIdx = StartIdx; CurrIdx <= EndIdx; CurrIdx++) {
932  unsigned Key = IntegerMapping[CurrIdx];
933  if (Key > Mapper.IllegalInstrNumber) {
934  ContainsIllegal = true;
935  break;
936  }
937  }
938 
939  // If we have an illegal instruction, we should not create an
940  // IRSimilarityCandidate for this region.
941  if (ContainsIllegal)
942  continue;
943 
944  // We are getting iterators to the instructions in this region of code
945  // by advancing the start and end indices from the start of the
946  // InstrList.
947  std::vector<IRInstructionData *>::iterator StartIt = InstrList.begin();
948  std::advance(StartIt, StartIdx);
949  std::vector<IRInstructionData *>::iterator EndIt = InstrList.begin();
950  std::advance(EndIt, EndIdx);
951 
952  CandsForRepSubstring.emplace_back(StartIdx, StringLen, *StartIt, *EndIt);
953  }
954 }
955 
957  IRSimilarityCandidate &SourceCand,
958  DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
959  DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping) {
960  assert(SourceCand.CanonNumToNumber.size() != 0 &&
961  "Base canonical relationship is empty!");
962  assert(SourceCand.NumberToCanonNum.size() != 0 &&
963  "Base canonical relationship is empty!");
964 
965  assert(CanonNumToNumber.size() == 0 && "Canonical Relationship is non-empty");
966  assert(NumberToCanonNum.size() == 0 && "Canonical Relationship is non-empty");
967 
968  DenseSet<unsigned> UsedGVNs;
969  // Iterate over the mappings provided from this candidate to SourceCand. We
970  // are then able to map the GVN in this candidate to the same canonical number
971  // given to the corresponding GVN in SourceCand.
972  for (std::pair<unsigned, DenseSet<unsigned>> &GVNMapping : ToSourceMapping) {
973  unsigned SourceGVN = GVNMapping.first;
974 
975  assert(GVNMapping.second.size() != 0 && "Possible GVNs is 0!");
976 
977  unsigned ResultGVN;
978  // We need special handling if we have more than one potential value. This
979  // means that there are at least two GVNs that could correspond to this GVN.
980  // This could lead to potential swapping later on, so we make a decision
981  // here to ensure a one-to-one mapping.
982  if (GVNMapping.second.size() > 1) {
983  bool Found = false;
984  for (unsigned Val : GVNMapping.second) {
985  // We make sure the target value number hasn't already been reserved.
986  if (UsedGVNs.contains(Val))
987  continue;
988 
989  // We make sure that the opposite mapping is still consistent.
991  FromSourceMapping.find(Val);
992 
993  if (!It->second.contains(SourceGVN))
994  continue;
995 
996  // We pick the first item that satisfies these conditions.
997  Found = true;
998  ResultGVN = Val;
999  break;
1000  }
1001 
1002  assert(Found && "Could not find matching value for source GVN");
1003  (void)Found;
1004 
1005  } else
1006  ResultGVN = *GVNMapping.second.begin();
1007 
1008  // Whatever GVN is found, we mark it as used.
1009  UsedGVNs.insert(ResultGVN);
1010 
1011  unsigned CanonNum = *SourceCand.getCanonicalNum(ResultGVN);
1012  CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN));
1013  NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum));
1014  }
1015 
1016  DenseSet<BasicBlock *> BBSet;
1017  getBasicBlocks(BBSet);
1018  // Find canonical numbers for the BasicBlocks in the current candidate.
1019  // This is done by finding the corresponding value for the first instruction
1020  // in the block in the current candidate, finding the matching value in the
1021  // source candidate. Then by finding the parent of this value, use the
1022  // canonical number of the block in the source candidate for the canonical
1023  // number in the current candidate.
1024  for (BasicBlock *BB : BBSet) {
1025  unsigned BBGVNForCurrCand = ValueToNumber.find(BB)->second;
1026 
1027  // We can skip the BasicBlock if the canonical numbering has already been
1028  // found in a separate instruction.
1029  if (NumberToCanonNum.find(BBGVNForCurrCand) != NumberToCanonNum.end())
1030  continue;
1031 
1032  // If the basic block is the starting block, then the shared instruction may
1033  // not be the first instruction in the block, it will be the first
1034  // instruction in the similarity region.
1035  Value *FirstOutlineInst = BB == getStartBB()
1036  ? frontInstruction()
1037  : &*BB->instructionsWithoutDebug().begin();
1038 
1039  unsigned FirstInstGVN = *getGVN(FirstOutlineInst);
1040  unsigned FirstInstCanonNum = *getCanonicalNum(FirstInstGVN);
1041  unsigned SourceGVN = *SourceCand.fromCanonicalNum(FirstInstCanonNum);
1042  Value *SourceV = *SourceCand.fromGVN(SourceGVN);
1043  BasicBlock *SourceBB = cast<Instruction>(SourceV)->getParent();
1044  unsigned SourceBBGVN = *SourceCand.getGVN(SourceBB);
1045  unsigned SourceCanonBBGVN = *SourceCand.getCanonicalNum(SourceBBGVN);
1046  CanonNumToNumber.insert(std::make_pair(SourceCanonBBGVN, BBGVNForCurrCand));
1047  NumberToCanonNum.insert(std::make_pair(BBGVNForCurrCand, SourceCanonBBGVN));
1048  }
1049 }
1050 
1052  IRSimilarityCandidate &CurrCand) {
1053  assert(CurrCand.CanonNumToNumber.size() == 0 &&
1054  "Canonical Relationship is non-empty");
1055  assert(CurrCand.NumberToCanonNum.size() == 0 &&
1056  "Canonical Relationship is non-empty");
1057 
1058  unsigned CanonNum = 0;
1059  // Iterate over the value numbers found, the order does not matter in this
1060  // case.
1061  for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {
1062  CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum));
1063  CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first));
1064  CanonNum++;
1065  }
1066 }
1067 
1068 /// From the list of IRSimilarityCandidates, perform a comparison between each
1069 /// IRSimilarityCandidate to determine if there are overlapping
1070 /// IRInstructionData, or if they do not have the same structure.
1071 ///
1072 /// \param [in] CandsForRepSubstring - The vector containing the
1073 /// IRSimilarityCandidates.
1074 /// \param [out] StructuralGroups - the mapping of unsigned integers to vector
1075 /// of IRSimilarityCandidates where each of the IRSimilarityCandidates in the
1076 /// vector are structurally similar to one another.
1078  std::vector<IRSimilarityCandidate> &CandsForRepSubstring,
1079  DenseMap<unsigned, SimilarityGroup> &StructuralGroups) {
1080  std::vector<IRSimilarityCandidate>::iterator CandIt, CandEndIt, InnerCandIt,
1081  InnerCandEndIt;
1082 
1083  // IRSimilarityCandidates each have a structure for operand use. It is
1084  // possible that two instances of the same subsequences have different
1085  // structure. Each type of structure found is assigned a number. This
1086  // DenseMap maps an IRSimilarityCandidate to which type of similarity
1087  // discovered it fits within.
1089 
1090  // Find the compatibility from each candidate to the others to determine
1091  // which candidates overlap and which have the same structure by mapping
1092  // each structure to a different group.
1093  bool SameStructure;
1094  bool Inserted;
1095  unsigned CurrentGroupNum = 0;
1096  unsigned OuterGroupNum;
1100 
1101  // Iterate over the candidates to determine its structural and overlapping
1102  // compatibility with other instructions
1103  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
1104  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingB;
1105  for (CandIt = CandsForRepSubstring.begin(),
1106  CandEndIt = CandsForRepSubstring.end();
1107  CandIt != CandEndIt; CandIt++) {
1108 
1109  // Determine if it has an assigned structural group already.
1110  CandToGroupIt = CandToGroup.find(&*CandIt);
1111  if (CandToGroupIt == CandToGroup.end()) {
1112  // If not, we assign it one, and add it to our mapping.
1113  std::tie(CandToGroupIt, Inserted) =
1114  CandToGroup.insert(std::make_pair(&*CandIt, CurrentGroupNum++));
1115  }
1116 
1117  // Get the structural group number from the iterator.
1118  OuterGroupNum = CandToGroupIt->second;
1119 
1120  // Check if we already have a list of IRSimilarityCandidates for the current
1121  // structural group. Create one if one does not exist.
1122  CurrentGroupPair = StructuralGroups.find(OuterGroupNum);
1123  if (CurrentGroupPair == StructuralGroups.end()) {
1125  std::tie(CurrentGroupPair, Inserted) = StructuralGroups.insert(
1126  std::make_pair(OuterGroupNum, SimilarityGroup({*CandIt})));
1127  }
1128 
1129  // Iterate over the IRSimilarityCandidates following the current
1130  // IRSimilarityCandidate in the list to determine whether the two
1131  // IRSimilarityCandidates are compatible. This is so we do not repeat pairs
1132  // of IRSimilarityCandidates.
1133  for (InnerCandIt = std::next(CandIt),
1134  InnerCandEndIt = CandsForRepSubstring.end();
1135  InnerCandIt != InnerCandEndIt; InnerCandIt++) {
1136 
1137  // We check if the inner item has a group already, if it does, we skip it.
1138  CandToGroupItInner = CandToGroup.find(&*InnerCandIt);
1139  if (CandToGroupItInner != CandToGroup.end())
1140  continue;
1141 
1142  // Otherwise we determine if they have the same structure and add it to
1143  // vector if they match.
1144  ValueNumberMappingA.clear();
1145  ValueNumberMappingB.clear();
1147  *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);
1148  if (!SameStructure)
1149  continue;
1150 
1151  InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA,
1152  ValueNumberMappingB);
1153  CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
1154  CurrentGroupPair->second.push_back(*InnerCandIt);
1155  }
1156  }
1157 }
1158 
1159 void IRSimilarityIdentifier::findCandidates(
1160  std::vector<IRInstructionData *> &InstrList,
1161  std::vector<unsigned> &IntegerMapping) {
1162  SuffixTree ST(IntegerMapping);
1163 
1164  std::vector<IRSimilarityCandidate> CandsForRepSubstring;
1165  std::vector<SimilarityGroup> NewCandidateGroups;
1166 
1167  DenseMap<unsigned, SimilarityGroup> StructuralGroups;
1168 
1169  // Iterate over the subsequences found by the Suffix Tree to create
1170  // IRSimilarityCandidates for each repeated subsequence and determine which
1171  // instances are structurally similar to one another.
1172  for (SuffixTree::RepeatedSubstring &RS : ST) {
1173  createCandidatesFromSuffixTree(Mapper, InstrList, IntegerMapping, RS,
1174  CandsForRepSubstring);
1175 
1176  if (CandsForRepSubstring.size() < 2)
1177  continue;
1178 
1179  findCandidateStructures(CandsForRepSubstring, StructuralGroups);
1180  for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups)
1181  // We only add the group if it contains more than one
1182  // IRSimilarityCandidate. If there is only one, that means there is no
1183  // other repeated subsequence with the same structure.
1184  if (Group.second.size() > 1)
1185  SimilarityCandidates->push_back(Group.second);
1186 
1187  CandsForRepSubstring.clear();
1188  StructuralGroups.clear();
1189  NewCandidateGroups.clear();
1190  }
1191 }
1192 
1194  ArrayRef<std::unique_ptr<Module>> Modules) {
1196 
1197  std::vector<IRInstructionData *> InstrList;
1198  std::vector<unsigned> IntegerMapping;
1199  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
1200  Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;
1201  Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;
1202  Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;
1203  Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;
1204 
1205  populateMapper(Modules, InstrList, IntegerMapping);
1206  findCandidates(InstrList, IntegerMapping);
1207 
1208  return *SimilarityCandidates;
1209 }
1210 
1213  Mapper.InstClassifier.EnableBranches = this->EnableBranches;
1214  Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;
1215  Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;
1216  Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;
1217  Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;
1218 
1219  std::vector<IRInstructionData *> InstrList;
1220  std::vector<unsigned> IntegerMapping;
1221 
1222  populateMapper(M, InstrList, IntegerMapping);
1223  findCandidates(InstrList, IntegerMapping);
1224 
1225  return *SimilarityCandidates;
1226 }
1227 
1229  "ir-similarity-identifier", false, true)
1230 
1232  : ModulePass(ID) {
1235 }
1236 
1240  false));
1241  return false;
1242 }
1243 
1245  IRSI.reset();
1246  return false;
1247 }
1248 
1250  IRSI->findSimilarity(M);
1251  return false;
1252 }
1253 
1254 AnalysisKey IRSimilarityAnalysis::Key;
1259  false);
1260  IRSI.findSimilarity(M);
1261  return IRSI;
1262 }
1263 
1267  Optional<SimilarityGroupList> &SimilarityCandidatesOpt = IRSI.getSimilarity();
1268 
1269  for (std::vector<IRSimilarityCandidate> &CandVec : *SimilarityCandidatesOpt) {
1270  OS << CandVec.size() << " candidates of length "
1271  << CandVec.begin()->getLength() << ". Found in: \n";
1272  for (IRSimilarityCandidate &Cand : CandVec) {
1273  OS << " Function: " << Cand.front()->Inst->getFunction()->getName().str()
1274  << ", Basic Block: ";
1275  if (Cand.front()->Inst->getParent()->getName().str() == "")
1276  OS << "(unnamed)";
1277  else
1278  OS << Cand.front()->Inst->getParent()->getName().str();
1279  OS << "\n Start Instruction: ";
1280  Cand.frontInstruction()->print(OS);
1281  OS << "\n End Instruction: ";
1282  Cand.backInstruction()->print(OS);
1283  OS << "\n";
1284  }
1285  }
1286 
1287  return PreservedAnalyses::all();
1288 }
1289 
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::SuffixTree::RepeatedSubstring::Length
unsigned Length
The length of the string.
Definition: SuffixTree.h:145
llvm::DisableIntrinsics
cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))
Definition: IROutliner.cpp:47
llvm::Intrinsic::isOverloaded
bool isOverloaded(ID id)
Returns true if the intrinsic can be overloaded.
Definition: Function.cpp:1398
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:917
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:849
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:666
llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity
SimilarityGroupList & findSimilarity(ArrayRef< std::unique_ptr< Module >> Modules)
Definition: IRSimilarityIdentifier.cpp:1193
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:268
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:87
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3244
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:201
llvm::IRSimilarity::IRInstructionDataList
Definition: IRSimilarityIdentifier.h:297
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:390
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::EnableIntrinsics
bool EnableIntrinsics
Definition: IRSimilarityIdentifier.h:595
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::IRSimilarity::IRInstructionMapper::LegalInstrNumber
unsigned LegalInstrNumber
The next available integer to assign to a legal Instruction to.
Definition: IRSimilarityIdentifier.h:382
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:774
llvm::Function
Definition: Function.h:60
llvm::IRSimilarity::IRSimilarityCandidate::compareStructure
static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:729
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:1115
llvm::ArrayRef::iterator
const_pointer iterator
Definition: ArrayRef.h:49
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:632
llvm::Intrinsic::getName
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:882
llvm::IRSimilarity::IRSimilarityCandidate::getBasicBlocks
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const
Definition: IRSimilarityIdentifier.h:831
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:76
llvm::SPIRV::InstrList
SmallVector< MachineInstr * > InstrList
Definition: SPIRVModuleAnalysis.h:115
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:75
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::IRSimilarity::IRSimilarityIdentifier::getSimilarity
Optional< SimilarityGroupList > & getSimilarity()
Definition: IRSimilarityIdentifier.h:1050
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:130
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:39
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:952
llvm::Optional< SimilarityGroupList >
llvm::IRSimilarity::IRSimilarityIdentifier::resetSimilarityCandidates
void resetSimilarityCandidates()
Definition: IRSimilarityIdentifier.h:1038
llvm::IRSimilarity::IRSimilarityCandidate::fromCanonicalNum
Optional< unsigned > fromCanonicalNum(unsigned N)
Find the global value number from the canonical number N stored in the candidate.
Definition: IRSimilarityIdentifier.h:930
Operator.h
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:953
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:723
llvm::cl::ReallyHidden
@ ReallyHidden
Definition: CommandLine.h:140
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:417
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::IRSimilarity::IRInstructionMapper::IDL
IRInstructionDataList * IDL
Definition: IRSimilarityIdentifier.h:443
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::IRSimilarity::IRSimilarityCandidate::fromGVN
Optional< Value * > fromGVN(unsigned Num)
Finds the Value associate with Num if it exists.
Definition: IRSimilarityIdentifier.h:903
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::IRSimilarity::IRSimilarityCandidate::IRSimilarityCandidate
IRSimilarityCandidate(unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt)
Definition: IRSimilarityIdentifier.cpp:407
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:1590
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::EnableBranches
bool EnableBranches
Definition: IRSimilarityIdentifier.h:587
llvm::IRSimilarityIdentifierWrapperPass
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
Definition: IRSimilarityIdentifier.h:1095
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::IRSimilarity::Illegal
@ Illegal
Definition: IRSimilarityIdentifier.h:76
llvm::IRSimilarity::IRInstructionData::setPHIPredecessors
void setPHIPredecessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)
For an IRInstructionData containing a PHINode, finds the relative distances from the incoming basic b...
Definition: IRSimilarityIdentifier.cpp:138
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
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:1077
llvm::CmpInst::FCMP_UGE
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:732
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::IRSimilarity::IRInstructionMapper
Helper struct for converting the Instructions in a Module into a vector of unsigned integers.
Definition: IRSimilarityIdentifier.h:375
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::EnableIndirectCalls
bool EnableIndirectCalls
Definition: IRSimilarityIdentifier.h:591
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping
Definition: IRSimilarityIdentifier.h:714
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:403
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:42
llvm::IRSimilarity::IRSimilarityCandidate::isSimilar
static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:476
llvm::FunctionType::params
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:130
llvm::IRSimilarity::IRSimilarityCandidate::iterator
IRInstructionDataList::iterator iterator
Definition: IRSimilarityIdentifier.h:944
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:412
llvm::IRSimilarity::IRInstructionMapper::InstClassifier
InstructionClassification InstClassifier
Maps an Instruction to a member of InstrType.
Definition: IRSimilarityIdentifier.h:603
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:796
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:588
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
ZippedRelativeLocationsT
detail::zippy< detail::zip_shortest, SmallVector< int, 4 > &, SmallVector< int, 4 > &, ArrayRef< Value * > &, ArrayRef< Value * > & > ZippedRelativeLocationsT
Definition: IRSimilarityIdentifier.cpp:739
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::cl::opt< bool >
llvm::IRSimilarity::IRInstructionMapper::EnableMatchCallsByName
bool EnableMatchCallsByName
Marks whether we should use exact function names, as well as types to find similarity between calls.
Definition: IRSimilarityIdentifier.h:407
llvm::IRSimilarityIdentifierWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: IRSimilarityIdentifier.cpp:1249
llvm::IRSimilarity::IRSimilarityCandidate::getStartBB
BasicBlock * getStartBB()
Definition: IRSimilarityIdentifier.h:880
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:386
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:511
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:110
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:76
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:846
llvm::SuffixTree::RepeatedSubstring
A repeated substring in the tree.
Definition: SuffixTree.h:143
llvm::IRSimilarityAnalysis::run
Result run(Module &M, ModuleAnalysisManager &)
Definition: IRSimilarityIdentifier.cpp:1255
llvm::IRSimilarity::IRInstructionMapper::allocateIRInstructionData
IRInstructionData * allocateIRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Get an allocated IRInstructionData struct using the InstDataAllocator.
Definition: IRSimilarityIdentifier.cpp:356
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:69
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:439
llvm::InstVisitor::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
llvm::detail::zippy
Definition: STLExtras.h:722
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:270
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:1244
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:166
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:145
SuffixTree.h
llvm::CmpInst::FCMP_OGE
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:724
llvm::IRSimilarity::IRInstructionData
This provides the utilities for hashing an Instruction to an unsigned integer.
Definition: IRSimilarityIdentifier.h:114
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
llvm::IRSimilarity::IRInstructionData::getCalleeName
StringRef getCalleeName() const
Get the callee name that the call instruction is using for hashing the instruction.
Definition: IRSimilarityIdentifier.cpp:192
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:48
llvm::IRSimilarity::IRSimilarityCandidate::getGVN
Optional< unsigned > getGVN(Value *V)
Finds the positive number associated with V if it has been mapped.
Definition: IRSimilarityIdentifier.h:891
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:373
llvm::DisableIndirectCalls
cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))
Definition: IROutliner.cpp:43
llvm::initializeIRSimilarityIdentifierWrapperPassPass
void initializeIRSimilarityIdentifierWrapperPassPass(PassRegistry &)
llvm::IRSimilarityAnalysisPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: IRSimilarityIdentifier.cpp:1265
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:755
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
bool empty() const
Definition: DenseMap.h:98
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:1051
llvm::IRSimilarity::IRInstructionData::setCalleeName
void setCalleeName(bool MatchByName=true)
For an IRInstructionData containing a CallInst, set the function name appropriately.
Definition: IRSimilarityIdentifier.cpp:111
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:164
llvm::IRSimilarity::IRInstructionData::Inst
Instruction * Inst
The source Instruction that is being wrapped.
Definition: IRSimilarityIdentifier.h:118
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:1597
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::IRSimilarityIdentifierWrapperPass::ID
static char ID
Definition: IRSimilarityIdentifier.h:1099
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:1818
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:302
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::IRSimilarity::IRInstructionData::CalleeName
Optional< std::string > CalleeName
This is only relevant if we are wrapping a CallInst.
Definition: IRSimilarityIdentifier.h:140
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::EnableMustTailCalls
bool EnableMustTailCalls
Definition: IRSimilarityIdentifier.h:599
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:956
llvm::CmpInst::FCMP_UGT
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:731
llvm::IRSimilarityIdentifierWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: IRSimilarityIdentifier.cpp:1237
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::IRSimilarity::IRInstructionMapper::IllegalInstrNumber
unsigned IllegalInstrNumber
The starting illegal instruction number to map to.
Definition: IRSimilarityIdentifier.h:379
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:367
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:701
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:99
llvm::IRSimilarity::IRSimilarityCandidate::frontInstruction
Instruction * frontInstruction()
Definition: IRSimilarityIdentifier.h:875
llvm::CallBase::isIndirectCall
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Definition: Instructions.cpp:290
llvm::MatchCallsByName
cl::opt< bool > MatchCallsByName("ir-sim-calls-by-name", cl::init(false), cl::ReallyHidden, cl::desc("only allow matching call instructions if the " "name and type signature match."))
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:648
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
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:450
Predicate
llvm::IRSimilarity::IRInstructionData::initializeInstruction
void initializeInstruction()
Fills data stuctures for IRInstructionData when it is constructed from a.
Definition: IRSimilarityIdentifier.cpp:54
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:182
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:742
llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping
A helper struct to hold the candidate, for a branch instruction, the relative location of a label,...
Definition: IRSimilarityIdentifier.h:730
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:91
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:809
INITIALIZE_PASS
INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier", "ir-similarity-identifier", false, true) IRSimilarityIdentifierWrapperPass
Definition: IRSimilarityIdentifier.cpp:1228
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::IRSimilarity::IRInstructionMapper::AddedIllegalLastTime
bool AddedIllegalLastTime
Set if we added an illegal number in the previous step.
Definition: IRSimilarityIdentifier.h:396
llvm::PHINode
Definition: Instructions.h:2699
llvm::Optional::value
constexpr const T & value() const &
Definition: Optional.h:313
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:916
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::StringRef::str
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:221
llvm::IRSimilarity::IRInstructionMapper::CanCombineWithPrevInstr
bool CanCombineWithPrevInstr
Marks whether we found a illegal instruction in the previous step.
Definition: IRSimilarityIdentifier.h:399
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
llvm::IRSimilarity::IRInstructionData::OperVals
SmallVector< Value *, 4 > OperVals
The values of the operands in the Instruction.
Definition: IRSimilarityIdentifier.h:120
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:171
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:978
llvm::cl::desc
Definition: CommandLine.h:412
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38