LLVM  13.0.0git
IRSimilarityIdentifier.h
Go to the documentation of this file.
1 //===- IRSimilarityIdentifier.h - 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 // Interface file for the IRSimilarityIdentifier for identifying similarities in
11 // IR including the IRInstructionMapper, which maps an Instruction to unsigned
12 // integers.
13 //
14 // Two sequences of instructions are called "similar" if they perform the same
15 // series of operations for all inputs.
16 //
17 // \code
18 // %1 = add i32 %a, 10
19 // %2 = add i32 %a, %1
20 // %3 = icmp slt icmp %1, %2
21 // \endcode
22 //
23 // and
24 //
25 // \code
26 // %1 = add i32 11, %a
27 // %2 = sub i32 %a, %1
28 // %3 = icmp sgt icmp %2, %1
29 // \endcode
30 //
31 // ultimately have the same result, even if the inputs, and structure are
32 // slightly different.
33 //
34 // For instructions, we do not worry about operands that do not have fixed
35 // semantic meaning to the program. We consider the opcode that the instruction
36 // has, the types, parameters, and extra information such as the function name,
37 // or comparison predicate. These are used to create a hash to map instructions
38 // to integers to be used in similarity matching in sequences of instructions
39 //
40 // Terminology:
41 // An IRSimilarityCandidate is a region of IRInstructionData (wrapped
42 // Instructions), usually used to denote a region of similarity has been found.
43 //
44 // A SimilarityGroup is a set of IRSimilarityCandidates that are structurally
45 // similar to one another.
46 //
47 //===----------------------------------------------------------------------===//
48 
49 #ifndef LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
50 #define LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
51 
52 #include "llvm/IR/InstVisitor.h"
53 #include "llvm/IR/Instructions.h"
54 #include "llvm/IR/Module.h"
55 #include "llvm/IR/PassManager.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Allocator.h"
58 
59 namespace llvm {
60 namespace IRSimilarity {
61 
63 
64 /// This represents what is and is not supported when finding similarity in
65 /// Instructions.
66 ///
67 /// Legal Instructions are considered when looking at similarity between
68 /// Instructions.
69 ///
70 /// Illegal Instructions cannot be considered when looking for similarity
71 /// between Instructions. They act as boundaries between similarity regions.
72 ///
73 /// Invisible Instructions are skipped over during analysis.
74 // TODO: Shared with MachineOutliner
76 
77 /// This provides the utilities for hashing an Instruction to an unsigned
78 /// integer. Two IRInstructionDatas produce the same hash value when their
79 /// underlying Instructions perform the same operation (even if they don't have
80 /// the same input operands.)
81 /// As a more concrete example, consider the following:
82 ///
83 /// \code
84 /// %add1 = add i32 %a, %b
85 /// %add2 = add i32 %c, %d
86 /// %add3 = add i64 %e, %f
87 /// \endcode
88 ///
89 // Then the IRInstructionData wrappers for these Instructions may be hashed like
90 /// so:
91 ///
92 /// \code
93 /// ; These two adds have the same types and operand types, so they hash to the
94 /// ; same number.
95 /// %add1 = add i32 %a, %b ; Hash: 1
96 /// %add2 = add i32 %c, %d ; Hash: 1
97 /// ; This add produces an i64. This differentiates it from %add1 and %add2. So,
98 /// ; it hashes to a different number.
99 /// %add3 = add i64 %e, %f; Hash: 2
100 /// \endcode
101 ///
102 ///
103 /// This hashing scheme will be used to represent the program as a very long
104 /// string. This string can then be placed in a data structure which can be used
105 /// for similarity queries.
106 ///
107 /// TODO: Handle types of Instructions which can be equal even with different
108 /// operands. (E.g. comparisons with swapped predicates.)
109 /// TODO: Handle CallInsts, which are only checked for function type
110 /// by \ref isSameOperationAs.
111 /// TODO: Handle GetElementPtrInsts, as some of the operands have to be the
112 /// exact same, and some do not.
113 struct IRInstructionData : ilist_node<IRInstructionData> {
114 
115  /// The source Instruction that is being wrapped.
116  Instruction *Inst = nullptr;
117  /// The values of the operands in the Instruction.
119  /// The legality of the wrapped instruction. This is informed by InstrType,
120  /// and is used when checking when two instructions are considered similar.
121  /// If either instruction is not legal, the instructions are automatically not
122  /// considered similar.
123  bool Legal;
124 
125  /// This is only relevant if we are wrapping a CmpInst where we needed to
126  /// change the predicate of a compare instruction from a greater than form
127  /// to a less than form. It is None otherwise.
129 
130  /// Gather the information that is difficult to gather for an Instruction, or
131  /// is changed. i.e. the operands of an Instruction and the Types of those
132  /// operands. This extra information allows for similarity matching to make
133  /// assertions that allow for more flexibility when checking for whether an
134  /// Instruction performs the same operation.
136 
137  /// Get the predicate that the compare instruction is using for hashing the
138  /// instruction. the IRInstructionData must be wrapping a CmpInst.
140 
141  /// A function that swaps the predicates to their less than form if they are
142  /// in a greater than form. Otherwise, the predicate is unchanged.
143  ///
144  /// \param CI - The comparison operation to find a consistent preidcate for.
145  /// \return the consistent comparison predicate.
147 
148  /// Hashes \p Value based on its opcode, types, and operand types.
149  /// Two IRInstructionData instances produce the same hash when they perform
150  /// the same operation.
151  ///
152  /// As a simple example, consider the following instructions.
153  ///
154  /// \code
155  /// %add1 = add i32 %x1, %y1
156  /// %add2 = add i32 %x2, %y2
157  ///
158  /// %sub = sub i32 %x1, %y1
159  ///
160  /// %add_i64 = add i64 %x2, %y2
161  /// \endcode
162  ///
163  /// Because the first two adds operate the same types, and are performing the
164  /// same action, they will be hashed to the same value.
165  ///
166  /// However, the subtraction instruction is not the same as an addition, and
167  /// will be hashed to a different value.
168  ///
169  /// Finally, the last add has a different type compared to the first two add
170  /// instructions, so it will also be hashed to a different value that any of
171  /// the previous instructions.
172  ///
173  /// \param [in] ID - The IRInstructionData instance to be hashed.
174  /// \returns A hash_value of the IRInstructionData.
176  SmallVector<Type *, 4> OperTypes;
177  for (Value *V : ID.OperVals)
178  OperTypes.push_back(V->getType());
179 
180  if (isa<CmpInst>(ID.Inst))
181  return llvm::hash_combine(
182  llvm::hash_value(ID.Inst->getOpcode()),
183  llvm::hash_value(ID.Inst->getType()),
184  llvm::hash_value(ID.getPredicate()),
185  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
186  else if (CallInst *CI = dyn_cast<CallInst>(ID.Inst))
187  return llvm::hash_combine(
188  llvm::hash_value(ID.Inst->getOpcode()),
189  llvm::hash_value(ID.Inst->getType()),
190  llvm::hash_value(CI->getCalledFunction()->getName().str()),
191  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
192  return llvm::hash_combine(
193  llvm::hash_value(ID.Inst->getOpcode()),
194  llvm::hash_value(ID.Inst->getType()),
195  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
196  }
197 
199 };
200 
201 struct IRInstructionDataList : simple_ilist<IRInstructionData> {};
202 
203 /// Compare one IRInstructionData class to another IRInstructionData class for
204 /// whether they are performing a the same operation, and can mapped to the
205 /// same value. For regular instructions if the hash value is the same, then
206 /// they will also be close.
207 ///
208 /// \param A - The first IRInstructionData class to compare
209 /// \param B - The second IRInstructionData class to compare
210 /// \returns true if \p A and \p B are similar enough to be mapped to the same
211 /// value.
212 bool isClose(const IRInstructionData &A, const IRInstructionData &B);
213 
214 struct IRInstructionDataTraits : DenseMapInfo<IRInstructionData *> {
215  static inline IRInstructionData *getEmptyKey() { return nullptr; }
217  return reinterpret_cast<IRInstructionData *>(-1);
218  }
219 
220  static unsigned getHashValue(const IRInstructionData *E) {
221  using llvm::hash_value;
222  assert(E && "IRInstructionData is a nullptr?");
223  return hash_value(*E);
224  }
225 
226  static bool isEqual(const IRInstructionData *LHS,
227  const IRInstructionData *RHS) {
228  if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
229  LHS == getEmptyKey() || LHS == getTombstoneKey())
230  return LHS == RHS;
231 
232  assert(LHS && RHS && "nullptr should have been caught by getEmptyKey?");
233  return isClose(*LHS, *RHS);
234  }
235 };
236 
237 /// Helper struct for converting the Instructions in a Module into a vector of
238 /// unsigned integers. This vector of unsigned integers can be thought of as a
239 /// "numeric string". This numeric string can then be queried by, for example,
240 /// data structures that find repeated substrings.
241 ///
242 /// This hashing is done per BasicBlock in the module. To hash Instructions
243 /// based off of their operations, each Instruction is wrapped in an
244 /// IRInstructionData struct. The unsigned integer for an IRInstructionData
245 /// depends on:
246 /// - The hash provided by the IRInstructionData.
247 /// - Which member of InstrType the IRInstructionData is classified as.
248 // See InstrType for more details on the possible classifications, and how they
249 // manifest in the numeric string.
250 ///
251 /// The numeric string for an individual BasicBlock is terminated by an unique
252 /// unsigned integer. This prevents data structures which rely on repetition
253 /// from matching across BasicBlocks. (For example, the SuffixTree.)
254 /// As a concrete example, if we have the following two BasicBlocks:
255 /// \code
256 /// bb0:
257 /// %add1 = add i32 %a, %b
258 /// %add2 = add i32 %c, %d
259 /// %add3 = add i64 %e, %f
260 /// bb1:
261 /// %sub = sub i32 %c, %d
262 /// \endcode
263 /// We may hash the Instructions like this (via IRInstructionData):
264 /// \code
265 /// bb0:
266 /// %add1 = add i32 %a, %b ; Hash: 1
267 /// %add2 = add i32 %c, %d; Hash: 1
268 /// %add3 = add i64 %e, %f; Hash: 2
269 /// bb1:
270 /// %sub = sub i32 %c, %d; Hash: 3
271 /// %add4 = add i32 %c, %d ; Hash: 1
272 /// \endcode
273 /// And produce a "numeric string representation" like so:
274 /// 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2
275 ///
276 /// TODO: This is very similar to the MachineOutliner, and should be
277 /// consolidated into the same interface.
279  /// The starting illegal instruction number to map to.
280  ///
281  /// Set to -3 for compatibility with DenseMapInfo<unsigned>.
282  unsigned IllegalInstrNumber = static_cast<unsigned>(-3);
283 
284  /// The next available integer to assign to a legal Instruction to.
285  unsigned LegalInstrNumber = 0;
286 
287  /// Correspondence from IRInstructionData to unsigned integers.
290 
291  /// Set if we added an illegal number in the previous step.
292  /// Since each illegal number is unique, we only need one of them between
293  /// each range of legal numbers. This lets us make sure we don't add more
294  /// than one illegal number per range.
295  bool AddedIllegalLastTime = false;
296 
297  /// Marks whether we found a illegal instruction in the previous step.
299 
300  /// Marks whether we have found a set of instructions that is long enough
301  /// to be considered for similarity.
302  bool HaveLegalRange = false;
303 
304  /// This allocator pointer is in charge of holding on to the IRInstructionData
305  /// so it is not deallocated until whatever external tool is using it is done
306  /// with the information.
308 
309  /// This allocator pointer is in charge of creating the IRInstructionDataList
310  /// so it is not deallocated until whatever external tool is using it is done
311  /// with the information.
313 
314  /// Get an allocated IRInstructionData struct using the InstDataAllocator.
315  ///
316  /// \param I - The Instruction to wrap with IRInstructionData.
317  /// \param Legality - A boolean value that is true if the instruction is to
318  /// be considered for similarity, and false if not.
319  /// \param IDL - The InstructionDataList that the IRInstructionData is
320  /// inserted into.
321  /// \returns An allocated IRInstructionData struct.
324 
325  /// Get an allocated IRInstructionDataList object using the IDLAllocator.
326  ///
327  /// \returns An allocated IRInstructionDataList object.
329 
331 
332  /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers
333  /// determined by \p InstrType. Two Instructions are mapped to the same value
334  /// if they are close as defined by the InstructionData class above.
335  ///
336  /// \param [in] BB - The BasicBlock to be mapped to integers.
337  /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
338  /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to.
340  std::vector<IRInstructionData *> &InstrList,
341  std::vector<unsigned> &IntegerMapping);
342 
343  /// Maps an Instruction to a legal integer.
344  ///
345  /// \param [in] It - The Instruction to be mapped to an integer.
346  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
347  /// append to.
348  /// \param [in,out] InstrListForBB - Vector of InstructionData to append to.
349  /// \returns The integer \p It was mapped to.
351  std::vector<unsigned> &IntegerMappingForBB,
352  std::vector<IRInstructionData *> &InstrListForBB);
353 
354  /// Maps an Instruction to an illegal integer.
355  ///
356  /// \param [in] It - The \p Instruction to be mapped to an integer.
357  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
358  /// append to.
359  /// \param [in,out] InstrListForBB - Vector of IRInstructionData to append to.
360  /// \param End - true if creating a dummy IRInstructionData at the end of a
361  /// basic block.
362  /// \returns The integer \p It was mapped to.
363  unsigned mapToIllegalUnsigned(
364  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
365  std::vector<IRInstructionData *> &InstrListForBB, bool End = false);
366 
369  : InstDataAllocator(IDA), IDLAllocator(IDLA) {
370  // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
371  // changed.
372  assert(DenseMapInfo<unsigned>::getEmptyKey() == static_cast<unsigned>(-1) &&
373  "DenseMapInfo<unsigned>'s empty key isn't -1!");
375  static_cast<unsigned>(-2) &&
376  "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
377 
378  IDL = new (IDLAllocator->Allocate())
380  }
381 
382  /// Custom InstVisitor to classify different instructions for whether it can
383  /// be analyzed for similarity.
385  : public InstVisitor<InstructionClassification, InstrType> {
387 
388  // TODO: Determine a scheme to resolve when the label is similar enough.
390  // TODO: Determine a scheme to resolve when the labels are similar enough.
392  // TODO: Handle allocas.
394  // We exclude variable argument instructions since variable arguments
395  // requires extra checking of the argument list.
397  // We exclude all exception handling cases since they are so context
398  // dependent.
401  // DebugInfo should be included in the regions, but should not be
402  // analyzed for similarity as it has no bearing on the outcome of the
403  // program.
405  // TODO: Handle specific intrinsics.
407  // We only allow call instructions where the function has a name and
408  // is not an indirect call.
410  Function *F = CI.getCalledFunction();
411  if (!F || CI.isIndirectCall() || !F->hasName())
412  return Illegal;
413  return Legal;
414  }
415  // TODO: We do not current handle similarity that changes the control flow.
417  // TODO: We do not current handle similarity that changes the control flow.
419  // TODO: Handle interblock similarity.
422  };
423 
424  /// Maps an Instruction to a member of InstrType.
426 };
427 
428 /// This is a class that wraps a range of IRInstructionData from one point to
429 /// another in the vector of IRInstructionData, which is a region of the
430 /// program. It is also responsible for defining the structure within this
431 /// region of instructions.
432 ///
433 /// The structure of a region is defined through a value numbering system
434 /// assigned to each unique value in a region at the creation of the
435 /// IRSimilarityCandidate.
436 ///
437 /// For example, for each Instruction we add a mapping for each new
438 /// value seen in that Instruction.
439 /// IR: Mapping Added:
440 /// %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2
441 /// %add2 = add i32 %a, %1 %add2 -> 4
442 /// %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5
443 ///
444 /// We can compare IRSimilarityCandidates against one another.
445 /// The \ref isSimilar function compares each IRInstructionData against one
446 /// another and if we have the same sequences of IRInstructionData that would
447 /// create the same hash, we have similar IRSimilarityCandidates.
448 ///
449 /// We can also compare the structure of IRSimilarityCandidates. If we can
450 /// create a mapping of registers in the region contained by one
451 /// IRSimilarityCandidate to the region contained by different
452 /// IRSimilarityCandidate, they can be considered structurally similar.
453 ///
454 /// IRSimilarityCandidate1: IRSimilarityCandidate2:
455 /// %add1 = add i32 %a, %b %add1 = add i32 %d, %e
456 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f
457 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4
458 ///
459 /// Can have the following mapping from candidate to candidate of:
460 /// %a -> %d, %b -> %e, %c -> %f, c1 -> c3, c2 -> c4
461 /// and can be considered similar.
462 ///
463 /// IRSimilarityCandidate1: IRSimilarityCandidate2:
464 /// %add1 = add i32 %a, %b %add1 = add i32 %d, c4
465 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f
466 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4
467 ///
468 /// We cannot create the same mapping since the use of c4 is not used in the
469 /// same way as %b or c2.
471 private:
472  /// The start index of this IRSimilarityCandidate in the instruction list.
473  unsigned StartIdx = 0;
474 
475  /// The number of instructions in this IRSimilarityCandidate.
476  unsigned Len = 0;
477 
478  /// The first instruction in this IRSimilarityCandidate.
479  IRInstructionData *FirstInst = nullptr;
480 
481  /// The last instruction in this IRSimilarityCandidate.
482  IRInstructionData *LastInst = nullptr;
483 
484  /// Global Value Numbering structures
485  /// @{
486  /// Stores the mapping of the value to the number assigned to it in the
487  /// IRSimilarityCandidate.
488  DenseMap<Value *, unsigned> ValueToNumber;
489  /// Stores the mapping of the number to the value assigned this number.
490  DenseMap<unsigned, Value *> NumberToValue;
491  /// @}
492 
493 public:
494  /// \param StartIdx - The starting location of the region.
495  /// \param Len - The length of the region.
496  /// \param FirstInstIt - The starting IRInstructionData of the region.
497  /// \param LastInstIt - The ending IRInstructionData of the region.
498  IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
499  IRInstructionData *FirstInstIt,
500  IRInstructionData *LastInstIt);
501 
502  /// \param A - The first IRInstructionCandidate to compare.
503  /// \param B - The second IRInstructionCandidate to compare.
504  /// \returns True when every IRInstructionData in \p A is similar to every
505  /// IRInstructionData in \p B.
506  static bool isSimilar(const IRSimilarityCandidate &A,
507  const IRSimilarityCandidate &B);
508 
509  /// \param A - The first IRInstructionCandidate to compare.
510  /// \param B - The second IRInstructionCandidate to compare.
511  /// \returns True when every IRInstructionData in \p A is structurally similar
512  /// to \p B.
513  static bool compareStructure(const IRSimilarityCandidate &A,
514  const IRSimilarityCandidate &B);
515 
516  struct OperandMapping {
517  /// The IRSimilarityCandidate that holds the instruction the OperVals were
518  /// pulled from.
520 
521  /// The operand values to be analyzed.
523 
524  /// The current mapping of global value numbers from one IRSimilarityCandidate
525  /// to another IRSimilarityCandidate.
527  };
528 
529  /// Compare the operands in \p A and \p B and check that the current mapping
530  /// of global value numbers from \p A to \p B and \p B to \A is consistent.
531  ///
532  /// \param A - The first IRInstructionCandidate, operand values, and current
533  /// operand mappings to compare.
534  /// \param B - The second IRInstructionCandidate, operand values, and current
535  /// operand mappings to compare.
536  /// \returns true if the IRSimilarityCandidates operands are compatible.
538  OperandMapping B);
539 
540  /// Compare the operands in \p A and \p B and check that the current mapping
541  /// of global value numbers from \p A to \p B and \p B to \A is consistent
542  /// given that the operands are commutative.
543  ///
544  /// \param A - The first IRInstructionCandidate, operand values, and current
545  /// operand mappings to compare.
546  /// \param B - The second IRInstructionCandidate, operand values, and current
547  /// operand mappings to compare.
548  /// \returns true if the IRSimilarityCandidates operands are compatible.
550  OperandMapping B);
551 
552  /// Compare the start and end indices of the two IRSimilarityCandidates for
553  /// whether they overlap. If the start instruction of one
554  /// IRSimilarityCandidate is less than the end instruction of the other, and
555  /// the start instruction of one is greater than the start instruction of the
556  /// other, they overlap.
557  ///
558  /// \returns true if the IRSimilarityCandidates do not have overlapping
559  /// instructions.
560  static bool overlap(const IRSimilarityCandidate &A,
561  const IRSimilarityCandidate &B);
562 
563  /// \returns the number of instructions in this Candidate.
564  unsigned getLength() const { return Len; }
565 
566  /// \returns the start index of this IRSimilarityCandidate.
567  unsigned getStartIdx() const { return StartIdx; }
568 
569  /// \returns the end index of this IRSimilarityCandidate.
570  unsigned getEndIdx() const { return StartIdx + Len - 1; }
571 
572  /// \returns The first IRInstructionData.
573  IRInstructionData *front() const { return FirstInst; }
574  /// \returns The last IRInstructionData.
575  IRInstructionData *back() const { return LastInst; }
576 
577  /// \returns The first Instruction.
578  Instruction *frontInstruction() { return FirstInst->Inst; }
579  /// \returns The last Instruction
580  Instruction *backInstruction() { return LastInst->Inst; }
581 
582  /// \returns The BasicBlock the IRSimilarityCandidate starts in.
583  BasicBlock *getStartBB() { return FirstInst->Inst->getParent(); }
584  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
585  BasicBlock *getEndBB() { return LastInst->Inst->getParent(); }
586 
587  /// \returns The Function that the IRSimilarityCandidate is located in.
589 
590  /// Finds the positive number associated with \p V if it has been mapped.
591  /// \param [in] V - the Value to find.
592  /// \returns The positive number corresponding to the value.
593  /// \returns None if not present.
595  assert(V != nullptr && "Value is a nullptr?");
596  DenseMap<Value *, unsigned>::iterator VNIt = ValueToNumber.find(V);
597  if (VNIt == ValueToNumber.end())
598  return None;
599  return VNIt->second;
600  }
601 
602  /// Finds the Value associate with \p Num if it exists.
603  /// \param [in] Num - the number to find.
604  /// \returns The Value associated with the number.
605  /// \returns None if not present.
606  Optional<Value *> fromGVN(unsigned Num) {
607  DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num);
608  if (VNIt == NumberToValue.end())
609  return None;
610  assert(VNIt->second != nullptr && "Found value is a nullptr!");
611  return VNIt->second;
612  }
613 
614  /// \param RHS -The IRSimilarityCandidate to compare against
615  /// \returns true if the IRSimilarityCandidate is occurs after the
616  /// IRSimilarityCandidate in the program.
617  bool operator<(const IRSimilarityCandidate &RHS) const {
618  return getStartIdx() > RHS.getStartIdx();
619  }
620 
622  iterator begin() const { return iterator(front()); }
623  iterator end() const { return std::next(iterator(back())); }
624 };
625 
626 typedef std::vector<IRSimilarityCandidate> SimilarityGroup;
627 typedef std::vector<SimilarityGroup> SimilarityGroupList;
628 
629 /// This class puts all the pieces of the IRInstructionData,
630 /// IRInstructionMapper, IRSimilarityCandidate together.
631 ///
632 /// It first feeds the Module or vector of Modules into the IRInstructionMapper,
633 /// and puts all the mapped instructions into a single long list of
634 /// IRInstructionData.
635 ///
636 /// The list of unsigned integers is given to the Suffix Tree or similar data
637 /// structure to find repeated subsequences. We construct an
638 /// IRSimilarityCandidate for each instance of the subsequence. We compare them
639 /// against one another since These repeated subsequences can have different
640 /// structure. For each different kind of structure found, we create a
641 /// similarity group.
642 ///
643 /// If we had four IRSimilarityCandidates A, B, C, and D where A, B and D are
644 /// structurally similar to one another, while C is different we would have two
645 /// SimilarityGroups:
646 ///
647 /// SimilarityGroup 1: SimilarityGroup 2
648 /// A, B, D C
649 ///
650 /// A list of the different similarity groups is then returned after
651 /// analyzing the module.
653 public:
655  : Mapper(&InstDataAllocator, &InstDataListAllocator) {}
656 
657  /// \param M the module to find similarity in.
659  : Mapper(&InstDataAllocator, &InstDataListAllocator) {
660  findSimilarity(M);
661  }
662 
663 private:
664  /// Map the instructions in the module to unsigned integers, using mapping
665  /// already present in the Mapper if possible.
666  ///
667  /// \param [in] M Module - To map to integers.
668  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
669  /// \param [in,out] IntegerMapping - The vector to append integers to.
670  void populateMapper(Module &M, std::vector<IRInstructionData *> &InstrList,
671  std::vector<unsigned> &IntegerMapping);
672 
673  /// Map the instructions in the modules vector to unsigned integers, using
674  /// mapping already present in the mapper if possible.
675  ///
676  /// \param [in] Modules - The list of modules to use to populate the mapper
677  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
678  /// \param [in,out] IntegerMapping - The vector to append integers to.
679  void populateMapper(ArrayRef<std::unique_ptr<Module>> &Modules,
680  std::vector<IRInstructionData *> &InstrList,
681  std::vector<unsigned> &IntegerMapping);
682 
683  /// Find the similarity candidates in \p InstrList and corresponding
684  /// \p UnsignedVec
685  ///
686  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
687  /// \param [in,out] IntegerMapping - The vector to append integers to.
688  /// candidates found in the program.
689  void findCandidates(std::vector<IRInstructionData *> &InstrList,
690  std::vector<unsigned> &IntegerMapping);
691 
692 public:
693  // Find the IRSimilarityCandidates in the \p Modules and group by structural
694  // similarity in a SimilarityGroup, each group is returned in a
695  // SimilarityGroupList.
696  //
697  // \param [in] Modules - the modules to analyze.
698  // \returns The groups of similarity ranges found in the modules.
700  findSimilarity(ArrayRef<std::unique_ptr<Module>> Modules);
701 
702  // Find the IRSimilarityCandidates in the given Module grouped by structural
703  // similarity in a SimilarityGroup, contained inside a SimilarityGroupList.
704  //
705  // \param [in] M - the module to analyze.
706  // \returns The groups of similarity ranges found in the module.
708 
709  // Clears \ref SimilarityCandidates if it is already filled by a previous run.
711  // If we've already analyzed a Module or set of Modules, so we must clear
712  // the SimilarityCandidates to make sure we do not have only old values
713  // hanging around.
714  if (SimilarityCandidates.hasValue())
715  SimilarityCandidates->clear();
716  else
717  SimilarityCandidates = SimilarityGroupList();
718  }
719 
720  // \returns The groups of similarity ranges found in the most recently passed
721  // set of modules.
723  return SimilarityCandidates;
724  }
725 
726 private:
727  /// The allocator for IRInstructionData.
729 
730  /// The allocator for IRInstructionDataLists.
732 
733  /// Map Instructions to unsigned integers and wraps the Instruction in an
734  /// instance of IRInstructionData.
735  IRInstructionMapper Mapper;
736 
737  /// The SimilarityGroups found with the most recent run of \ref
738  /// findSimilarity. None if there is no recent run.
739  Optional<SimilarityGroupList> SimilarityCandidates;
740 };
741 
742 } // end namespace IRSimilarity
743 
744 /// An analysis pass based on legacy pass manager that runs and returns
745 /// IRSimilarityIdentifier run on the Module.
747  std::unique_ptr<IRSimilarity::IRSimilarityIdentifier> IRSI;
748 
749 public:
750  static char ID;
752 
754  const IRSimilarity::IRSimilarityIdentifier &getIRSI() const { return *IRSI; }
755 
756  bool doInitialization(Module &M) override;
757  bool doFinalization(Module &M) override;
758  bool runOnModule(Module &M) override;
759  void getAnalysisUsage(AnalysisUsage &AU) const override {
760  AU.setPreservesAll();
761  }
762 };
763 
764 /// An analysis pass that runs and returns the IRSimilarityIdentifier run on the
765 /// Module.
766 class IRSimilarityAnalysis : public AnalysisInfoMixin<IRSimilarityAnalysis> {
767 public:
769 
771 
772 private:
774  static AnalysisKey Key;
775 };
776 
777 /// Printer pass that uses \c IRSimilarityAnalysis.
779  : public PassInfoMixin<IRSimilarityAnalysisPrinterPass> {
780  raw_ostream &OS;
781 
782 public:
785 };
786 
787 } // end namespace llvm
788 
789 #endif // LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping::ValueNumberMapping
DenseMap< unsigned, DenseSet< unsigned > > & ValueNumberMapping
The current mapping of global value numbers from one IRSimilarityCandidate to another IRSimilarityCan...
Definition: IRSimilarityIdentifier.h:526
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::IRSimilarity::IRInstructionDataTraits::isEqual
static bool isEqual(const IRInstructionData *LHS, const IRInstructionData *RHS)
Definition: IRSimilarityIdentifier.h:226
llvm::IRSimilarity::IRSimilarityCandidate::backInstruction
Instruction * backInstruction()
Definition: IRSimilarityIdentifier.h:580
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::InstructionClassification
InstructionClassification()
Definition: IRSimilarityIdentifier.h:386
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:531
llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity
SimilarityGroupList & findSimilarity(ArrayRef< std::unique_ptr< Module >> Modules)
Definition: IRSimilarityIdentifier.cpp:859
llvm
Definition: AllocatorList.h:23
llvm::IRSimilarityAnalysis::Result
IRSimilarity::IRSimilarityIdentifier Result
Definition: IRSimilarityIdentifier.h:768
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::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1838
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:84
llvm::IRSimilarity::IRInstructionDataList
Definition: IRSimilarityIdentifier.h:201
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
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::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::IRSimilarity::IRInstructionMapper::LegalInstrNumber
unsigned LegalInstrNumber
The next available integer to assign to a legal Instruction to.
Definition: IRSimilarityIdentifier.h:285
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::IRSimilarity::IRSimilarityCandidate::compareStructure
static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:566
Pass.h
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:766
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2852
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:497
Allocator.h
llvm::IRSimilarityIdentifierWrapperPass::getIRSI
const IRSimilarity::IRSimilarityIdentifier & getIRSI() const
Definition: IRSimilarityIdentifier.h:754
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:75
llvm::SpecificBumpPtrAllocator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:376
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::IRSimilarity::IRSimilarityIdentifier::getSimilarity
Optional< SimilarityGroupList > & getSimilarity()
Definition: IRSimilarityIdentifier.h:722
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:128
Module.h
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:626
llvm::Optional< CmpInst::Predicate >
llvm::IRSimilarity::IRSimilarityIdentifier::resetSimilarityCandidates
void resetSimilarityCandidates()
Definition: IRSimilarityIdentifier.h:710
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:627
llvm::hash_value
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4810
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:312
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::IRSimilarity::IRInstructionMapper::IDL
IRInstructionDataList * IDL
Definition: IRSimilarityIdentifier.h:330
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::IRSimilarity::IRSimilarityCandidate::fromGVN
Optional< Value * > fromGVN(unsigned Num)
Finds the Value associate with Num if it exists.
Definition: IRSimilarityIdentifier.h:606
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
llvm::IRSimilarity::IRSimilarityCandidate::IRSimilarityCandidate
IRSimilarityCandidate(unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt)
Definition: IRSimilarityIdentifier.cpp:277
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::IRSimilarity::IRSimilarityIdentifier::IRSimilarityIdentifier
IRSimilarityIdentifier()
Definition: IRSimilarityIdentifier.h:654
llvm::IRSimilarityIdentifierWrapperPass
An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...
Definition: IRSimilarityIdentifier.h:746
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:1396
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitAllocaInst
InstrType visitAllocaInst(AllocaInst &AI)
Definition: IRSimilarityIdentifier.h:393
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::IRSimilarity::IRInstructionData::IDL
IRInstructionDataList * IDL
Definition: IRSimilarityIdentifier.h:198
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitCallBrInst
InstrType visitCallBrInst(CallBrInst &CBI)
Definition: IRSimilarityIdentifier.h:418
llvm::IRSimilarity::IRInstructionMapper
Helper struct for converting the Instructions in a Module into a vector of unsigned integers.
Definition: IRSimilarityIdentifier.h:278
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping
Definition: IRSimilarityIdentifier.h:516
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:302
llvm::Instruction
Definition: Instruction.h:45
llvm::IRSimilarity::IRSimilarityCandidate::isSimilar
static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:334
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::IRSimilarity::IRSimilarityCandidate::begin
iterator begin() const
Definition: IRSimilarityIdentifier.h:622
llvm::DbgInfoIntrinsic
This is the common base class for debug info intrinsics.
Definition: IntrinsicInst.h:134
llvm::IRSimilarity::IRSimilarityCandidate::iterator
IRInstructionDataList::iterator iterator
Definition: IRSimilarityIdentifier.h:621
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:307
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitInstruction
InstrType visitInstruction(Instruction &I)
Definition: IRSimilarityIdentifier.h:421
llvm::IRSimilarity::IRInstructionMapper::InstClassifier
InstructionClassification InstClassifier
Maps an Instruction to a member of InstrType.
Definition: IRSimilarityIdentifier.h:425
llvm::None
const NoneType None
Definition: None.h:23
llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx
unsigned getEndIdx() const
Definition: IRSimilarityIdentifier.h:570
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3716
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
llvm::IRSimilarity::IRSimilarityCandidate::getFunction
Function * getFunction()
Definition: IRSimilarityIdentifier.h:588
llvm::IRSimilarityIdentifierWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: IRSimilarityIdentifier.cpp:903
llvm::IRSimilarity::IRSimilarityCandidate::getStartBB
BasicBlock * getStartBB()
Definition: IRSimilarityIdentifier.h:583
llvm::IRSimilarity::IRInstructionMapper::InstructionIntegerMap
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits > InstructionIntegerMap
Correspondence from IRInstructionData to unsigned integers.
Definition: IRSimilarityIdentifier.h:289
VI
@ VI
Definition: SIInstrInfo.cpp:7494
llvm::IRSimilarity::IRSimilarityIdentifier::IRSimilarityIdentifier
IRSimilarityIdentifier(Module &M)
Definition: IRSimilarityIdentifier.h:658
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:75
llvm::simple_ilist< IRInstructionData >::iterator
ilist_iterator< OptionsT, false, false > iterator
Definition: simple_ilist.h:95
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:639
llvm::IRSimilarityIdentifierWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: IRSimilarityIdentifier.h:759
llvm::IRSimilarity::IRInstructionDataTraits::getHashValue
static unsigned getHashValue(const IRInstructionData *E)
Definition: IRSimilarityIdentifier.h:220
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3925
llvm::IRSimilarityIdentifierWrapperPass::getIRSI
IRSimilarity::IRSimilarityIdentifier & getIRSI()
Definition: IRSimilarityIdentifier.h:753
llvm::IRSimilarityAnalysis::run
Result run(Module &M, ModuleAnalysisManager &)
Definition: IRSimilarityIdentifier.cpp:910
llvm::IRSimilarity::IRInstructionMapper::allocateIRInstructionData
IRInstructionData * allocateIRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)
Get an allocated IRInstructionData struct using the InstDataAllocator.
Definition: IRSimilarityIdentifier.cpp:233
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::IRSimilarity::IRSimilarityCandidate::operator<
bool operator<(const IRSimilarityCandidate &RHS) const
Definition: IRSimilarityIdentifier.h:617
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::IRSimilarity::InstrType
InstrType
This represents what is and is not supported when finding similarity in Instructions.
Definition: IRSimilarityIdentifier.h:75
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:151
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:898
llvm::IRSimilarity::IRSimilarityCandidate::back
IRInstructionData * back() const
Definition: IRSimilarityIdentifier.h:575
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitPHINode
InstrType visitPHINode(PHINode &PN)
Definition: IRSimilarityIdentifier.h:391
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:52
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification
Custom InstVisitor to classify different instructions for whether it can be analyzed for similarity.
Definition: IRSimilarityIdentifier.h:384
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IRSimilarity::IRInstructionData
This provides the utilities for hashing an Instruction to an unsigned integer.
Definition: IRSimilarityIdentifier.h:113
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping::OperVals
ArrayRef< Value * > & OperVals
The operand values to be analyzed.
Definition: IRSimilarityIdentifier.h:522
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:26
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping::IRSC
const IRSimilarityCandidate & IRSC
The IRSimilarityCandidate that holds the instruction the OperVals were pulled from.
Definition: IRSimilarityIdentifier.h:519
llvm::IRSimilarity::IRSimilarityCandidate::getGVN
Optional< unsigned > getGVN(Value *V)
Finds the positive number associated with V if it has been mapped.
Definition: IRSimilarityIdentifier.h:594
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:245
llvm::IRSimilarityAnalysisPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: IRSimilarityIdentifier.cpp:917
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitFuncletPadInst
InstrType visitFuncletPadInst(FuncletPadInst &FPI)
Definition: IRSimilarityIdentifier.h:400
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:391
llvm::IRSimilarity::IRSimilarityCandidate::end
iterator end() const
Definition: IRSimilarityIdentifier.h:623
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitLandingPadInst
InstrType visitLandingPadInst(LandingPadInst &LPI)
Definition: IRSimilarityIdentifier.h:399
llvm::IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass
IRSimilarityIdentifierWrapperPass()
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitVAArgInst
InstrType visitVAArgInst(VAArgInst &VI)
Definition: IRSimilarityIdentifier.h:396
llvm::IRSimilarity::IRSimilarityCandidate::front
IRInstructionData * front() const
Definition: IRSimilarityIdentifier.h:573
llvm::IRSimilarity::IRInstructionData::Legal
bool Legal
The legality of the wrapped instruction.
Definition: IRSimilarityIdentifier.h:123
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::IRSimilarity::IRInstructionData::Inst
Instruction * Inst
The source Instruction that is being wrapped.
Definition: IRSimilarityIdentifier.h:116
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitIntrinsicInst
InstrType visitIntrinsicInst(IntrinsicInst &II)
Definition: IRSimilarityIdentifier.h:406
InstVisitor.h
llvm::IRSimilarityIdentifierWrapperPass::ID
static char ID
Definition: IRSimilarityIdentifier.h:750
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:188
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:79
llvm::ilist_node
Definition: ilist_node.h:148
llvm::IRSimilarityIdentifierWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: IRSimilarityIdentifier.cpp:893
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitInvokeInst
InstrType visitInvokeInst(InvokeInst &II)
Definition: IRSimilarityIdentifier.h:416
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::IRSimilarity::IRInstructionMapper::IllegalInstrNumber
unsigned IllegalInstrNumber
The starting illegal instruction number to map to.
Definition: IRSimilarityIdentifier.h:282
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:239
llvm::IRSimilarity::IRInstructionMapper::IRInstructionMapper
IRInstructionMapper(SpecificBumpPtrAllocator< IRInstructionData > *IDA, SpecificBumpPtrAllocator< IRInstructionDataList > *IDLA)
Definition: IRSimilarityIdentifier.h:367
llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx
unsigned getStartIdx() const
Definition: IRSimilarityIdentifier.h:567
llvm::IRSimilarity::IRSimilarityCandidate::frontInstruction
Instruction * frontInstruction()
Definition: IRSimilarityIdentifier.h:578
llvm::CallBase::isIndirectCall
bool isIndirectCall() const
Return true if the callsite is an indirect call.
Definition: Instructions.cpp:285
PassManager.h
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:470
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::IRSimilarity::IRInstructionDataTraits::getTombstoneKey
static IRInstructionData * getTombstoneKey()
Definition: IRSimilarityIdentifier.h:216
Instructions.h
llvm::IRSimilarity::IRSimilarityCandidate::getEndBB
BasicBlock * getEndBB()
Definition: IRSimilarityIdentifier.h:585
llvm::FuncletPadInst
Definition: InstrTypes.h:2290
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:604
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitCallInst
InstrType visitCallInst(CallInst &CI)
Definition: IRSimilarityIdentifier.h:409
llvm::IRSimilarity::IRInstructionData::getPredicate
CmpInst::Predicate getPredicate() const
Get the predicate that the compare instruction is using for hashing the instruction.
Definition: IRSimilarityIdentifier.cpp:68
llvm::IRSimilarity::IRInstructionDataTraits::getEmptyKey
static IRInstructionData * getEmptyKey()
Definition: IRSimilarityIdentifier.h:215
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:482
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::IRSimilarity::IRInstructionDataTraits
Definition: IRSimilarityIdentifier.h:214
llvm::IRSimilarity::IRSimilarityCandidate::getLength
unsigned getLength() const
Definition: IRSimilarityIdentifier.h:564
llvm::IRSimilarity::IRInstructionMapper::AddedIllegalLastTime
bool AddedIllegalLastTime
Set if we added an illegal number in the previous step.
Definition: IRSimilarityIdentifier.h:295
llvm::PHINode
Definition: Instructions.h:2600
llvm::simple_ilist
A simple intrusive list implementation.
Definition: simple_ilist.h:78
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitBranchInst
InstrType visitBranchInst(BranchInst &BI)
Definition: IRSimilarityIdentifier.h:389
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:298
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:118
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
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:652
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitTerminator
InstrType visitTerminator(Instruction &I)
Definition: IRSimilarityIdentifier.h:420
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::IRSimilarityAnalysisPrinterPass
Printer pass that uses IRSimilarityAnalysis.
Definition: IRSimilarityIdentifier.h:778
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitDbgInfoIntrinsic
InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII)
Definition: IRSimilarityIdentifier.h:404
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3035
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::IRSimilarity::IRInstructionData::hash_value
friend hash_code hash_value(const IRInstructionData &ID)
Hashes Value based on its opcode, types, and operand types.
Definition: IRSimilarityIdentifier.h:175
llvm::IRSimilarityAnalysisPrinterPass::IRSimilarityAnalysisPrinterPass
IRSimilarityAnalysisPrinterPass(raw_ostream &OS)
Definition: IRSimilarityIdentifier.h:783
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:72