LLVM  16.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/PassManager.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Allocator.h"
57 
58 namespace llvm {
59 class Module;
60 
61 namespace IRSimilarity {
62 
64 
65 /// This represents what is and is not supported when finding similarity in
66 /// Instructions.
67 ///
68 /// Legal Instructions are considered when looking at similarity between
69 /// Instructions.
70 ///
71 /// Illegal Instructions cannot be considered when looking for similarity
72 /// between Instructions. They act as boundaries between similarity regions.
73 ///
74 /// Invisible Instructions are skipped over during analysis.
75 // TODO: Shared with MachineOutliner
77 
78 /// This provides the utilities for hashing an Instruction to an unsigned
79 /// integer. Two IRInstructionDatas produce the same hash value when their
80 /// underlying Instructions perform the same operation (even if they don't have
81 /// the same input operands.)
82 /// As a more concrete example, consider the following:
83 ///
84 /// \code
85 /// %add1 = add i32 %a, %b
86 /// %add2 = add i32 %c, %d
87 /// %add3 = add i64 %e, %f
88 /// \endcode
89 ///
90 // Then the IRInstructionData wrappers for these Instructions may be hashed like
91 /// so:
92 ///
93 /// \code
94 /// ; These two adds have the same types and operand types, so they hash to the
95 /// ; same number.
96 /// %add1 = add i32 %a, %b ; Hash: 1
97 /// %add2 = add i32 %c, %d ; Hash: 1
98 /// ; This add produces an i64. This differentiates it from %add1 and %add2. So,
99 /// ; it hashes to a different number.
100 /// %add3 = add i64 %e, %f; Hash: 2
101 /// \endcode
102 ///
103 ///
104 /// This hashing scheme will be used to represent the program as a very long
105 /// string. This string can then be placed in a data structure which can be used
106 /// for similarity queries.
107 ///
108 /// TODO: Handle types of Instructions which can be equal even with different
109 /// operands. (E.g. comparisons with swapped predicates.)
110 /// TODO: Handle CallInsts, which are only checked for function type
111 /// by \ref isSameOperationAs.
112 /// TODO: Handle GetElementPtrInsts, as some of the operands have to be the
113 /// exact same, and some do not.
115  : ilist_node<IRInstructionData, ilist_sentinel_tracking<true>> {
116 
117  /// The source Instruction that is being wrapped.
118  Instruction *Inst = nullptr;
119  /// The values of the operands in the Instruction.
121  /// The legality of the wrapped instruction. This is informed by InstrType,
122  /// and is used when checking when two instructions are considered similar.
123  /// If either instruction is not legal, the instructions are automatically not
124  /// considered similar.
125  bool Legal = false;
126 
127  /// This is only relevant if we are wrapping a CmpInst where we needed to
128  /// change the predicate of a compare instruction from a greater than form
129  /// to a less than form. It is None otherwise.
131 
132  /// This is only relevant if we are wrapping a CallInst. If we are requiring
133  /// that the function calls have matching names as well as types, and the
134  /// call is not an indirect call, this will hold the name of the function. If
135  /// it is an indirect string, it will be the empty string. However, if this
136  /// requirement is not in place it will be the empty string regardless of the
137  /// function call type. The value held here is used to create the hash of the
138  /// instruction, and check to make sure two instructions are close to one
139  /// another.
141 
142  /// This structure holds the distances of how far "ahead of" or "behind" the
143  /// target blocks of a branch, or the incoming blocks of a phi nodes are.
144  /// If the value is negative, it means that the block was registered before
145  /// the block of this instruction in terms of blocks in the function.
146  /// Code Example:
147  /// \code
148  /// block_1:
149  /// br i1 %0, label %block_2, label %block_3
150  /// block_2:
151  /// br i1 %1, label %block_1, label %block_2
152  /// block_3:
153  /// br i1 %2, label %block_2, label %block_1
154  /// ; Replacing the labels with relative values, this becomes:
155  /// block_1:
156  /// br i1 %0, distance 1, distance 2
157  /// block_2:
158  /// br i1 %1, distance -1, distance 0
159  /// block_3:
160  /// br i1 %2, distance -1, distance -2
161  /// \endcode
162  /// Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is
163  /// "ahead" of block_2.
165 
166  /// Gather the information that is difficult to gather for an Instruction, or
167  /// is changed. i.e. the operands of an Instruction and the Types of those
168  /// operands. This extra information allows for similarity matching to make
169  /// assertions that allow for more flexibility when checking for whether an
170  /// Instruction performs the same operation.
173 
174  /// Fills data stuctures for IRInstructionData when it is constructed from a
175  // reference or a pointer.
176  void initializeInstruction();
177 
178  /// Get the predicate that the compare instruction is using for hashing the
179  /// instruction. the IRInstructionData must be wrapping a CmpInst.
181 
182  /// Get the callee name that the call instruction is using for hashing the
183  /// instruction. The IRInstructionData must be wrapping a CallInst.
184  StringRef getCalleeName() const;
185 
186  /// A function that swaps the predicates to their less than form if they are
187  /// in a greater than form. Otherwise, the predicate is unchanged.
188  ///
189  /// \param CI - The comparison operation to find a consistent preidcate for.
190  /// \return the consistent comparison predicate.
192 
193  /// For an IRInstructionData containing a branch, finds the
194  /// relative distances from the source basic block to the target by taking
195  /// the difference of the number assigned to the current basic block and the
196  /// target basic block of the branch.
197  ///
198  /// \param BasicBlockToInteger - The mapping of basic blocks to their location
199  /// in the module.
200  void
202 
203  /// For an IRInstructionData containing a CallInst, set the function name
204  /// appropriately. This will be an empty string if it is an indirect call,
205  /// or we are not matching by name of the called function. It will be the
206  /// name of the function if \p MatchByName is true and it is not an indirect
207  /// call. We may decide not to match by name in order to expand the
208  /// size of the regions we can match. If a function name has the same type
209  /// signature, but the different name, the region of code is still almost the
210  /// same. Since function names can be treated as constants, the name itself
211  /// could be extrapolated away. However, matching by name provides a
212  /// specificity and more "identical" code than not matching by name.
213  ///
214  /// \param MatchByName - A flag to mark whether we are using the called
215  /// function name as a differentiating parameter.
216  void setCalleeName(bool MatchByName = true);
217 
218  /// For an IRInstructionData containing a PHINode, finds the
219  /// relative distances from the incoming basic block to the current block by
220  /// taking the difference of the number assigned to the current basic block
221  /// and the incoming basic block of the branch.
222  ///
223  /// \param BasicBlockToInteger - The mapping of basic blocks to their location
224  /// in the module.
225  void
227 
228  /// Hashes \p Value based on its opcode, types, and operand types.
229  /// Two IRInstructionData instances produce the same hash when they perform
230  /// the same operation.
231  ///
232  /// As a simple example, consider the following instructions.
233  ///
234  /// \code
235  /// %add1 = add i32 %x1, %y1
236  /// %add2 = add i32 %x2, %y2
237  ///
238  /// %sub = sub i32 %x1, %y1
239  ///
240  /// %add_i64 = add i64 %x2, %y2
241  /// \endcode
242  ///
243  /// Because the first two adds operate the same types, and are performing the
244  /// same action, they will be hashed to the same value.
245  ///
246  /// However, the subtraction instruction is not the same as an addition, and
247  /// will be hashed to a different value.
248  ///
249  /// Finally, the last add has a different type compared to the first two add
250  /// instructions, so it will also be hashed to a different value that any of
251  /// the previous instructions.
252  ///
253  /// \param [in] ID - The IRInstructionData instance to be hashed.
254  /// \returns A hash_value of the IRInstructionData.
256  SmallVector<Type *, 4> OperTypes;
257  for (Value *V : ID.OperVals)
258  OperTypes.push_back(V->getType());
259 
260  if (isa<CmpInst>(ID.Inst))
261  return llvm::hash_combine(
262  llvm::hash_value(ID.Inst->getOpcode()),
263  llvm::hash_value(ID.Inst->getType()),
264  llvm::hash_value(ID.getPredicate()),
265  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
266 
267  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(ID.Inst)) {
268  // To hash intrinsics, we use the opcode, and types like the other
269  // instructions, but also, the Intrinsic ID, and the Name of the
270  // intrinsic.
271  Intrinsic::ID IntrinsicID = II->getIntrinsicID();
272  return llvm::hash_combine(
273  llvm::hash_value(ID.Inst->getOpcode()),
274  llvm::hash_value(ID.Inst->getType()), llvm::hash_value(IntrinsicID),
275  llvm::hash_value(*ID.CalleeName),
276  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
277  }
278 
279  if (isa<CallInst>(ID.Inst)) {
280  std::string FunctionName = *ID.CalleeName;
281  return llvm::hash_combine(
282  llvm::hash_value(ID.Inst->getOpcode()),
283  llvm::hash_value(ID.Inst->getType()),
284  llvm::hash_value(ID.Inst->getType()), llvm::hash_value(FunctionName),
285  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
286  }
287 
288  return llvm::hash_combine(
289  llvm::hash_value(ID.Inst->getOpcode()),
290  llvm::hash_value(ID.Inst->getType()),
291  llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
292  }
293 
295 };
296 
298  : simple_ilist<IRInstructionData, ilist_sentinel_tracking<true>> {};
299 
300 /// Compare one IRInstructionData class to another IRInstructionData class for
301 /// whether they are performing a the same operation, and can mapped to the
302 /// same value. For regular instructions if the hash value is the same, then
303 /// they will also be close.
304 ///
305 /// \param A - The first IRInstructionData class to compare
306 /// \param B - The second IRInstructionData class to compare
307 /// \returns true if \p A and \p B are similar enough to be mapped to the same
308 /// value.
309 bool isClose(const IRInstructionData &A, const IRInstructionData &B);
310 
311 struct IRInstructionDataTraits : DenseMapInfo<IRInstructionData *> {
312  static inline IRInstructionData *getEmptyKey() { return nullptr; }
314  return reinterpret_cast<IRInstructionData *>(-1);
315  }
316 
317  static unsigned getHashValue(const IRInstructionData *E) {
318  using llvm::hash_value;
319  assert(E && "IRInstructionData is a nullptr?");
320  return hash_value(*E);
321  }
322 
323  static bool isEqual(const IRInstructionData *LHS,
324  const IRInstructionData *RHS) {
325  if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
326  LHS == getEmptyKey() || LHS == getTombstoneKey())
327  return LHS == RHS;
328 
329  assert(LHS && RHS && "nullptr should have been caught by getEmptyKey?");
330  return isClose(*LHS, *RHS);
331  }
332 };
333 
334 /// Helper struct for converting the Instructions in a Module into a vector of
335 /// unsigned integers. This vector of unsigned integers can be thought of as a
336 /// "numeric string". This numeric string can then be queried by, for example,
337 /// data structures that find repeated substrings.
338 ///
339 /// This hashing is done per BasicBlock in the module. To hash Instructions
340 /// based off of their operations, each Instruction is wrapped in an
341 /// IRInstructionData struct. The unsigned integer for an IRInstructionData
342 /// depends on:
343 /// - The hash provided by the IRInstructionData.
344 /// - Which member of InstrType the IRInstructionData is classified as.
345 // See InstrType for more details on the possible classifications, and how they
346 // manifest in the numeric string.
347 ///
348 /// The numeric string for an individual BasicBlock is terminated by an unique
349 /// unsigned integer. This prevents data structures which rely on repetition
350 /// from matching across BasicBlocks. (For example, the SuffixTree.)
351 /// As a concrete example, if we have the following two BasicBlocks:
352 /// \code
353 /// bb0:
354 /// %add1 = add i32 %a, %b
355 /// %add2 = add i32 %c, %d
356 /// %add3 = add i64 %e, %f
357 /// bb1:
358 /// %sub = sub i32 %c, %d
359 /// \endcode
360 /// We may hash the Instructions like this (via IRInstructionData):
361 /// \code
362 /// bb0:
363 /// %add1 = add i32 %a, %b ; Hash: 1
364 /// %add2 = add i32 %c, %d; Hash: 1
365 /// %add3 = add i64 %e, %f; Hash: 2
366 /// bb1:
367 /// %sub = sub i32 %c, %d; Hash: 3
368 /// %add4 = add i32 %c, %d ; Hash: 1
369 /// \endcode
370 /// And produce a "numeric string representation" like so:
371 /// 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2
372 ///
373 /// TODO: This is very similar to the MachineOutliner, and should be
374 /// consolidated into the same interface.
376  /// The starting illegal instruction number to map to.
377  ///
378  /// Set to -3 for compatibility with DenseMapInfo<unsigned>.
379  unsigned IllegalInstrNumber = static_cast<unsigned>(-3);
380 
381  /// The next available integer to assign to a legal Instruction to.
382  unsigned LegalInstrNumber = 0;
383 
384  /// Correspondence from IRInstructionData to unsigned integers.
387 
388  /// A mapping for a basic block in a module to its assigned number/location
389  /// in the module.
391 
392  /// Set if we added an illegal number in the previous step.
393  /// Since each illegal number is unique, we only need one of them between
394  /// each range of legal numbers. This lets us make sure we don't add more
395  /// than one illegal number per range.
396  bool AddedIllegalLastTime = false;
397 
398  /// Marks whether we found a illegal instruction in the previous step.
400 
401  /// Marks whether we have found a set of instructions that is long enough
402  /// to be considered for similarity.
403  bool HaveLegalRange = false;
404 
405  /// Marks whether we should use exact function names, as well as types to
406  /// find similarity between calls.
408 
409  /// This allocator pointer is in charge of holding on to the IRInstructionData
410  /// so it is not deallocated until whatever external tool is using it is done
411  /// with the information.
413 
414  /// This allocator pointer is in charge of creating the IRInstructionDataList
415  /// so it is not deallocated until whatever external tool is using it is done
416  /// with the information.
418 
419  /// Get an allocated IRInstructionData struct using the InstDataAllocator.
420  ///
421  /// \param I - The Instruction to wrap with IRInstructionData.
422  /// \param Legality - A boolean value that is true if the instruction is to
423  /// be considered for similarity, and false if not.
424  /// \param IDL - The InstructionDataList that the IRInstructionData is
425  /// inserted into.
426  /// \returns An allocated IRInstructionData struct.
429 
430  /// Get an empty allocated IRInstructionData struct using the
431  /// InstDataAllocator.
432  ///
433  /// \param IDL - The InstructionDataList that the IRInstructionData is
434  /// inserted into.
435  /// \returns An allocated IRInstructionData struct.
437 
438  /// Get an allocated IRInstructionDataList object using the IDLAllocator.
439  ///
440  /// \returns An allocated IRInstructionDataList object.
442 
444 
445  /// Assigns values to all the basic blocks in function \p F starting from
446  /// integer \p BBNumber.
447  ///
448  /// \param F - The function containing the basic blocks to assign numbers to.
449  /// \param BBNumber - The number to start from.
450  void initializeForBBs(Function &F, unsigned &BBNumber) {
451  for (BasicBlock &BB : F)
452  BasicBlockToInteger.insert(std::make_pair(&BB, BBNumber++));
453  }
454 
455  /// Assigns values to all the basic blocks in Module \p M.
456  /// \param M - The module containing the basic blocks to assign numbers to.
458  unsigned BBNumber = 0;
459  for (Function &F : M)
460  initializeForBBs(F, BBNumber);
461  }
462 
463  /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers
464  /// determined by \p InstrType. Two Instructions are mapped to the same value
465  /// if they are close as defined by the InstructionData class above.
466  ///
467  /// \param [in] BB - The BasicBlock to be mapped to integers.
468  /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
469  /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to.
471  std::vector<IRInstructionData *> &InstrList,
472  std::vector<unsigned> &IntegerMapping);
473 
474  /// Maps an Instruction to a legal integer.
475  ///
476  /// \param [in] It - The Instruction to be mapped to an integer.
477  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
478  /// append to.
479  /// \param [in,out] InstrListForBB - Vector of InstructionData to append to.
480  /// \returns The integer \p It was mapped to.
482  std::vector<unsigned> &IntegerMappingForBB,
483  std::vector<IRInstructionData *> &InstrListForBB);
484 
485  /// Maps an Instruction to an illegal integer.
486  ///
487  /// \param [in] It - The \p Instruction to be mapped to an integer.
488  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
489  /// append to.
490  /// \param [in,out] InstrListForBB - Vector of IRInstructionData to append to.
491  /// \param End - true if creating a dummy IRInstructionData at the end of a
492  /// basic block.
493  /// \returns The integer \p It was mapped to.
494  unsigned mapToIllegalUnsigned(
495  BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
496  std::vector<IRInstructionData *> &InstrListForBB, bool End = false);
497 
500  : InstDataAllocator(IDA), IDLAllocator(IDLA) {
501  // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
502  // changed.
503  assert(DenseMapInfo<unsigned>::getEmptyKey() == static_cast<unsigned>(-1) &&
504  "DenseMapInfo<unsigned>'s empty key isn't -1!");
506  static_cast<unsigned>(-2) &&
507  "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
508 
509  IDL = new (IDLAllocator->Allocate())
511  }
512 
513  /// Custom InstVisitor to classify different instructions for whether it can
514  /// be analyzed for similarity.
516  : public InstVisitor<InstructionClassification, InstrType> {
517  InstructionClassification() = default;
518 
519  // TODO: Determine a scheme to resolve when the label is similar enough.
521  if (EnableBranches)
522  return Legal;
523  return Illegal;
524  }
526  if (EnableBranches)
527  return Legal;
528  return Illegal;
529  }
530  // TODO: Handle allocas.
532  // We exclude variable argument instructions since variable arguments
533  // requires extra checking of the argument list.
535  // We exclude all exception handling cases since they are so context
536  // dependent.
539  // DebugInfo should be included in the regions, but should not be
540  // analyzed for similarity as it has no bearing on the outcome of the
541  // program.
544  // These are disabled due to complications in the CodeExtractor when
545  // outlining these instructions. For instance, It is unclear what we
546  // should do when moving only the start or end lifetime instruction into
547  // an outlined function. Also, assume-like intrinsics could be removed
548  // from the region, removing arguments, causing discrepencies in the
549  // number of inputs between different regions.
550  if (II.isAssumeLikeIntrinsic())
551  return Illegal;
552  return EnableIntrinsics ? Legal : Illegal;
553  }
554  // We only allow call instructions where the function has a name and
555  // is not an indirect call.
557  Function *F = CI.getCalledFunction();
558  bool IsIndirectCall = CI.isIndirectCall();
559  if (IsIndirectCall && !EnableIndirectCalls)
560  return Illegal;
561  if (!F && !IsIndirectCall)
562  return Illegal;
563  // Functions marked with the swifttailcc and tailcc calling conventions
564  // require special handling when outlining musttail functions. The
565  // calling convention must be passed down to the outlined function as
566  // well. Further, there is special handling for musttail calls as well,
567  // requiring a return call directly after. For now, the outliner does not
568  // support this, so we do not handle matching this case either.
569  if ((CI.getCallingConv() == CallingConv::SwiftTail ||
572  return Illegal;
573  if (CI.isMustTailCall() && !EnableMustTailCalls)
574  return Illegal;
575  return Legal;
576  }
577  // TODO: We do not current handle similarity that changes the control flow.
579  // TODO: We do not current handle similarity that changes the control flow.
581  // TODO: Handle interblock similarity.
584 
585  // The flag variable that lets the classifier know whether we should
586  // allow branches to be checked for similarity.
587  bool EnableBranches = false;
588 
589  // The flag variable that lets the classifier know whether we should
590  // allow indirect calls to be considered legal instructions.
591  bool EnableIndirectCalls = false;
592 
593  // Flag that lets the classifier know whether we should allow intrinsics to
594  // be checked for similarity.
595  bool EnableIntrinsics = false;
596 
597  // Flag that lets the classifier know whether we should allow tail calls to
598  // be checked for similarity.
599  bool EnableMustTailCalls = false;
600  };
601 
602  /// Maps an Instruction to a member of InstrType.
604 };
605 
606 /// This is a class that wraps a range of IRInstructionData from one point to
607 /// another in the vector of IRInstructionData, which is a region of the
608 /// program. It is also responsible for defining the structure within this
609 /// region of instructions.
610 ///
611 /// The structure of a region is defined through a value numbering system
612 /// assigned to each unique value in a region at the creation of the
613 /// IRSimilarityCandidate.
614 ///
615 /// For example, for each Instruction we add a mapping for each new
616 /// value seen in that Instruction.
617 /// IR: Mapping Added:
618 /// %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2
619 /// %add2 = add i32 %a, %1 %add2 -> 4
620 /// %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5
621 ///
622 /// We can compare IRSimilarityCandidates against one another.
623 /// The \ref isSimilar function compares each IRInstructionData against one
624 /// another and if we have the same sequences of IRInstructionData that would
625 /// create the same hash, we have similar IRSimilarityCandidates.
626 ///
627 /// We can also compare the structure of IRSimilarityCandidates. If we can
628 /// create a mapping of registers in the region contained by one
629 /// IRSimilarityCandidate to the region contained by different
630 /// IRSimilarityCandidate, they can be considered structurally similar.
631 ///
632 /// IRSimilarityCandidate1: IRSimilarityCandidate2:
633 /// %add1 = add i32 %a, %b %add1 = add i32 %d, %e
634 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f
635 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4
636 ///
637 /// Can have the following mapping from candidate to candidate of:
638 /// %a -> %d, %b -> %e, %c -> %f, c1 -> c3, c2 -> c4
639 /// and can be considered similar.
640 ///
641 /// IRSimilarityCandidate1: IRSimilarityCandidate2:
642 /// %add1 = add i32 %a, %b %add1 = add i32 %d, c4
643 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f
644 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4
645 ///
646 /// We cannot create the same mapping since the use of c4 is not used in the
647 /// same way as %b or c2.
649 private:
650  /// The start index of this IRSimilarityCandidate in the instruction list.
651  unsigned StartIdx = 0;
652 
653  /// The number of instructions in this IRSimilarityCandidate.
654  unsigned Len = 0;
655 
656  /// The first instruction in this IRSimilarityCandidate.
657  IRInstructionData *FirstInst = nullptr;
658 
659  /// The last instruction in this IRSimilarityCandidate.
660  IRInstructionData *LastInst = nullptr;
661 
662  /// Global Value Numbering structures
663  /// @{
664  /// Stores the mapping of the value to the number assigned to it in the
665  /// IRSimilarityCandidate.
666  DenseMap<Value *, unsigned> ValueToNumber;
667  /// Stores the mapping of the number to the value assigned this number.
668  DenseMap<unsigned, Value *> NumberToValue;
669  /// Stores the mapping of a value's number to canonical numbering in the
670  /// candidate's respective similarity group.
671  DenseMap<unsigned, unsigned> NumberToCanonNum;
672  /// Stores the mapping of canonical number in the candidate's respective
673  /// similarity group to a value number.
674  DenseMap<unsigned, unsigned> CanonNumToNumber;
675  /// @}
676 
677 public:
678  /// \param StartIdx - The starting location of the region.
679  /// \param Len - The length of the region.
680  /// \param FirstInstIt - The starting IRInstructionData of the region.
681  /// \param LastInstIt - The ending IRInstructionData of the region.
682  IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
683  IRInstructionData *FirstInstIt,
684  IRInstructionData *LastInstIt);
685 
686  /// \param A - The first IRInstructionCandidate to compare.
687  /// \param B - The second IRInstructionCandidate to compare.
688  /// \returns True when every IRInstructionData in \p A is similar to every
689  /// IRInstructionData in \p B.
690  static bool isSimilar(const IRSimilarityCandidate &A,
691  const IRSimilarityCandidate &B);
692 
693  /// \param [in] A - The first IRInstructionCandidate to compare.
694  /// \param [in] B - The second IRInstructionCandidate to compare.
695  /// \returns True when every IRInstructionData in \p A is structurally similar
696  /// to \p B.
697  static bool compareStructure(const IRSimilarityCandidate &A,
698  const IRSimilarityCandidate &B);
699 
700  /// \param [in] A - The first IRInstructionCandidate to compare.
701  /// \param [in] B - The second IRInstructionCandidate to compare.
702  /// \param [in,out] ValueNumberMappingA - A mapping of value numbers from
703  /// candidate \p A to candidate \B.
704  /// \param [in,out] ValueNumberMappingB - A mapping of value numbers from
705  /// candidate \p B to candidate \A.
706  /// \returns True when every IRInstructionData in \p A is structurally similar
707  /// to \p B.
708  static bool
710  const IRSimilarityCandidate &B,
711  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
712  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB);
713 
714  struct OperandMapping {
715  /// The IRSimilarityCandidate that holds the instruction the OperVals were
716  /// pulled from.
718 
719  /// The operand values to be analyzed.
721 
722  /// The current mapping of global value numbers from one IRSimilarityCandidate
723  /// to another IRSimilarityCandidate.
725  };
726 
727  /// A helper struct to hold the candidate, for a branch instruction, the
728  /// relative location of a label, and the label itself. This is mostly to
729  /// group the values together before passing them as a bundle to a function.
731  /// The IRSimilarityCandidate that holds the instruction the relative
732  /// location was pulled from.
734 
735  /// The relative location to be analyzed.
737 
738  /// The corresponding value.
740  };
741 
742  /// Compare the operands in \p A and \p B and check that the current mapping
743  /// of global value numbers from \p A to \p B and \p B to \A is consistent.
744  ///
745  /// \param A - The first IRInstructionCandidate, operand values, and current
746  /// operand mappings to compare.
747  /// \param B - The second IRInstructionCandidate, operand values, and current
748  /// operand mappings to compare.
749  /// \returns true if the IRSimilarityCandidates operands are compatible.
751  OperandMapping B);
752 
753  /// Compare the operands in \p A and \p B and check that the current mapping
754  /// of global value numbers from \p A to \p B and \p B to \A is consistent
755  /// given that the operands are commutative.
756  ///
757  /// \param A - The first IRInstructionCandidate, operand values, and current
758  /// operand mappings to compare.
759  /// \param B - The second IRInstructionCandidate, operand values, and current
760  /// operand mappings to compare.
761  /// \returns true if the IRSimilarityCandidates operands are compatible.
763  OperandMapping B);
764 
765  /// Compare the relative locations in \p A and \p B and check that the
766  /// distances match if both locations are contained in the region, and that
767  /// the branches both point outside the region if they do not.
768  /// Example Region:
769  /// \code
770  /// entry:
771  /// br i1 %0, label %block_1, label %block_3
772  /// block_0:
773  /// br i1 %0, label %block_1, label %block_2
774  /// block_1:
775  /// br i1 %0, label %block_2, label %block_3
776  /// block_2:
777  /// br i1 %1, label %block_1, label %block_4
778  /// block_3:
779  /// br i1 %2, label %block_2, label %block_5
780  /// \endcode
781  /// If we compare the branches in block_0 and block_1 the relative values are
782  /// 1 and 2 for both, so we consider this a match.
783  ///
784  /// If we compare the branches in entry and block_0 the relative values are
785  /// 2 and 3, and 1 and 2 respectively. Since these are not the same we do not
786  /// consider them a match.
787  ///
788  /// If we compare the branches in block_1 and block_2 the relative values are
789  /// 1 and 2, and -1 and None respectively. As a result we do not consider
790  /// these to be the same
791  ///
792  /// If we compare the branches in block_2 and block_3 the relative values are
793  /// -1 and None for both. We do consider these to be a match.
794  ///
795  /// \param A - The first IRInstructionCandidate, relative location value,
796  /// and incoming block.
797  /// \param B - The second IRInstructionCandidate, relative location value,
798  /// and incoming block.
799  /// \returns true if the relative locations match.
802 
803  /// Create a mapping from the value numbering to a different separate set of
804  /// numbers. This will serve as a guide for relating one candidate to another.
805  /// The canonical number gives use the ability identify which global value
806  /// number in one candidate relates to the global value number in the other.
807  ///
808  /// \param [in, out] CurrCand - The IRSimilarityCandidate to create a
809  /// canonical numbering for.
810  static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand);
811 
812  /// Create a mapping for the value numbering of the calling
813  /// IRSimilarityCandidate, to a different separate set of numbers, based on
814  /// the canonical ordering in \p SourceCand. These are defined based on the
815  /// found mappings in \p ToSourceMapping and \p FromSourceMapping. Both of
816  /// these relationships should have the same information, just in opposite
817  /// directions.
818  ///
819  /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a
820  /// canonical numbering from.
821  /// \param ToSourceMapping - The mapping of value numbers from this candidate
822  /// to \p SourceCand.
823  /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand
824  /// to this candidate.
826  IRSimilarityCandidate &SourceCand,
827  DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
828  DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping);
829 
830  /// \param [in,out] BBSet - The set to track the basic blocks.
832  for (IRInstructionData &ID : *this) {
833  BasicBlock *BB = ID.Inst->getParent();
834  BBSet.insert(BB);
835  }
836  }
837 
838  /// \param [in,out] BBSet - The set to track the basic blocks.
839  /// \param [in,out] BBList - A list in order of use to track the basic blocks.
841  SmallVector<BasicBlock *> &BBList) const {
842  for (IRInstructionData &ID : *this) {
843  BasicBlock *BB = ID.Inst->getParent();
844  if (BBSet.insert(BB).second)
845  BBList.push_back(BB);
846  }
847  }
848 
849  /// Compare the start and end indices of the two IRSimilarityCandidates for
850  /// whether they overlap. If the start instruction of one
851  /// IRSimilarityCandidate is less than the end instruction of the other, and
852  /// the start instruction of one is greater than the start instruction of the
853  /// other, they overlap.
854  ///
855  /// \returns true if the IRSimilarityCandidates do not have overlapping
856  /// instructions.
857  static bool overlap(const IRSimilarityCandidate &A,
858  const IRSimilarityCandidate &B);
859 
860  /// \returns the number of instructions in this Candidate.
861  unsigned getLength() const { return Len; }
862 
863  /// \returns the start index of this IRSimilarityCandidate.
864  unsigned getStartIdx() const { return StartIdx; }
865 
866  /// \returns the end index of this IRSimilarityCandidate.
867  unsigned getEndIdx() const { return StartIdx + Len - 1; }
868 
869  /// \returns The first IRInstructionData.
870  IRInstructionData *front() const { return FirstInst; }
871  /// \returns The last IRInstructionData.
872  IRInstructionData *back() const { return LastInst; }
873 
874  /// \returns The first Instruction.
875  Instruction *frontInstruction() { return FirstInst->Inst; }
876  /// \returns The last Instruction
877  Instruction *backInstruction() { return LastInst->Inst; }
878 
879  /// \returns The BasicBlock the IRSimilarityCandidate starts in.
880  BasicBlock *getStartBB() { return FirstInst->Inst->getParent(); }
881  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
882  BasicBlock *getEndBB() { return LastInst->Inst->getParent(); }
883 
884  /// \returns The Function that the IRSimilarityCandidate is located in.
886 
887  /// Finds the positive number associated with \p V if it has been mapped.
888  /// \param [in] V - the Value to find.
889  /// \returns The positive number corresponding to the value.
890  /// \returns None if not present.
892  assert(V != nullptr && "Value is a nullptr?");
893  DenseMap<Value *, unsigned>::iterator VNIt = ValueToNumber.find(V);
894  if (VNIt == ValueToNumber.end())
895  return None;
896  return VNIt->second;
897  }
898 
899  /// Finds the Value associate with \p Num if it exists.
900  /// \param [in] Num - the number to find.
901  /// \returns The Value associated with the number.
902  /// \returns None if not present.
903  Optional<Value *> fromGVN(unsigned Num) {
904  DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num);
905  if (VNIt == NumberToValue.end())
906  return None;
907  assert(VNIt->second != nullptr && "Found value is a nullptr!");
908  return VNIt->second;
909  }
910 
911  /// Find the canonical number from the global value number \p N stored in the
912  /// candidate.
913  ///
914  /// \param N - The global value number to find the canonical number for.
915  /// \returns An optional containing the value, and None if it could not be
916  /// found.
918  DenseMap<unsigned, unsigned>::iterator NCIt = NumberToCanonNum.find(N);
919  if (NCIt == NumberToCanonNum.end())
920  return None;
921  return NCIt->second;
922  }
923 
924  /// Find the global value number from the canonical number \p N stored in the
925  /// candidate.
926  ///
927  /// \param N - The canonical number to find the global vlaue number for.
928  /// \returns An optional containing the value, and None if it could not be
929  /// found.
931  DenseMap<unsigned, unsigned>::iterator CNIt = CanonNumToNumber.find(N);
932  if (CNIt == CanonNumToNumber.end())
933  return None;
934  return CNIt->second;
935  }
936 
937  /// \param RHS -The IRSimilarityCandidate to compare against
938  /// \returns true if the IRSimilarityCandidate is occurs after the
939  /// IRSimilarityCandidate in the program.
940  bool operator<(const IRSimilarityCandidate &RHS) const {
941  return getStartIdx() > RHS.getStartIdx();
942  }
943 
945  iterator begin() const { return iterator(front()); }
946  iterator end() const { return std::next(iterator(back())); }
947 };
948 
952 typedef std::vector<IRSimilarityCandidate> SimilarityGroup;
953 typedef std::vector<SimilarityGroup> SimilarityGroupList;
954 
955 /// This class puts all the pieces of the IRInstructionData,
956 /// IRInstructionMapper, IRSimilarityCandidate together.
957 ///
958 /// It first feeds the Module or vector of Modules into the IRInstructionMapper,
959 /// and puts all the mapped instructions into a single long list of
960 /// IRInstructionData.
961 ///
962 /// The list of unsigned integers is given to the Suffix Tree or similar data
963 /// structure to find repeated subsequences. We construct an
964 /// IRSimilarityCandidate for each instance of the subsequence. We compare them
965 /// against one another since These repeated subsequences can have different
966 /// structure. For each different kind of structure found, we create a
967 /// similarity group.
968 ///
969 /// If we had four IRSimilarityCandidates A, B, C, and D where A, B and D are
970 /// structurally similar to one another, while C is different we would have two
971 /// SimilarityGroups:
972 ///
973 /// SimilarityGroup 1: SimilarityGroup 2
974 /// A, B, D C
975 ///
976 /// A list of the different similarity groups is then returned after
977 /// analyzing the module.
979 public:
980  IRSimilarityIdentifier(bool MatchBranches = true,
981  bool MatchIndirectCalls = true,
982  bool MatchCallsWithName = false,
983  bool MatchIntrinsics = true,
984  bool MatchMustTailCalls = true)
985  : Mapper(&InstDataAllocator, &InstDataListAllocator),
986  EnableBranches(MatchBranches), EnableIndirectCalls(MatchIndirectCalls),
987  EnableMatchingCallsByName(MatchCallsWithName),
988  EnableIntrinsics(MatchIntrinsics),
989  EnableMustTailCalls(MatchMustTailCalls) {}
990 
991 private:
992  /// Map the instructions in the module to unsigned integers, using mapping
993  /// already present in the Mapper if possible.
994  ///
995  /// \param [in] M Module - To map to integers.
996  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
997  /// \param [in,out] IntegerMapping - The vector to append integers to.
998  void populateMapper(Module &M, std::vector<IRInstructionData *> &InstrList,
999  std::vector<unsigned> &IntegerMapping);
1000 
1001  /// Map the instructions in the modules vector to unsigned integers, using
1002  /// mapping already present in the mapper if possible.
1003  ///
1004  /// \param [in] Modules - The list of modules to use to populate the mapper
1005  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
1006  /// \param [in,out] IntegerMapping - The vector to append integers to.
1007  void populateMapper(ArrayRef<std::unique_ptr<Module>> &Modules,
1008  std::vector<IRInstructionData *> &InstrList,
1009  std::vector<unsigned> &IntegerMapping);
1010 
1011  /// Find the similarity candidates in \p InstrList and corresponding
1012  /// \p UnsignedVec
1013  ///
1014  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
1015  /// \param [in,out] IntegerMapping - The vector to append integers to.
1016  /// candidates found in the program.
1017  void findCandidates(std::vector<IRInstructionData *> &InstrList,
1018  std::vector<unsigned> &IntegerMapping);
1019 
1020 public:
1021  // Find the IRSimilarityCandidates in the \p Modules and group by structural
1022  // similarity in a SimilarityGroup, each group is returned in a
1023  // SimilarityGroupList.
1024  //
1025  // \param [in] Modules - the modules to analyze.
1026  // \returns The groups of similarity ranges found in the modules.
1028  findSimilarity(ArrayRef<std::unique_ptr<Module>> Modules);
1029 
1030  // Find the IRSimilarityCandidates in the given Module grouped by structural
1031  // similarity in a SimilarityGroup, contained inside a SimilarityGroupList.
1032  //
1033  // \param [in] M - the module to analyze.
1034  // \returns The groups of similarity ranges found in the module.
1036 
1037  // Clears \ref SimilarityCandidates if it is already filled by a previous run.
1039  // If we've already analyzed a Module or set of Modules, so we must clear
1040  // the SimilarityCandidates to make sure we do not have only old values
1041  // hanging around.
1042  if (SimilarityCandidates)
1043  SimilarityCandidates->clear();
1044  else
1045  SimilarityCandidates = SimilarityGroupList();
1046  }
1047 
1048  // \returns The groups of similarity ranges found in the most recently passed
1049  // set of modules.
1051  return SimilarityCandidates;
1052  }
1053 
1054 private:
1055  /// The allocator for IRInstructionData.
1057 
1058  /// The allocator for IRInstructionDataLists.
1060 
1061  /// Map Instructions to unsigned integers and wraps the Instruction in an
1062  /// instance of IRInstructionData.
1063  IRInstructionMapper Mapper;
1064 
1065  /// The flag variable that marks whether we should check branches for
1066  /// similarity, or only look within basic blocks.
1067  bool EnableBranches = true;
1068 
1069  /// The flag variable that marks whether we allow indirect calls to be checked
1070  /// for similarity, or exclude them as a legal instruction.
1071  bool EnableIndirectCalls = true;
1072 
1073  /// The flag variable that marks whether we allow calls to be marked as
1074  /// similar if they do not have the same name, only the same calling
1075  /// convention, attributes and type signature.
1076  bool EnableMatchingCallsByName = true;
1077 
1078  /// The flag variable that marks whether we should check intrinsics for
1079  /// similarity.
1080  bool EnableIntrinsics = true;
1081 
1082  // The flag variable that marks whether we should allow tailcalls
1083  // to be checked for similarity.
1084  bool EnableMustTailCalls = false;
1085 
1086  /// The SimilarityGroups found with the most recent run of \ref
1087  /// findSimilarity. None if there is no recent run.
1088  Optional<SimilarityGroupList> SimilarityCandidates;
1089 };
1090 
1091 } // end namespace IRSimilarity
1092 
1093 /// An analysis pass based on legacy pass manager that runs and returns
1094 /// IRSimilarityIdentifier run on the Module.
1096  std::unique_ptr<IRSimilarity::IRSimilarityIdentifier> IRSI;
1097 
1098 public:
1099  static char ID;
1101 
1103  const IRSimilarity::IRSimilarityIdentifier &getIRSI() const { return *IRSI; }
1104 
1105  bool doInitialization(Module &M) override;
1106  bool doFinalization(Module &M) override;
1107  bool runOnModule(Module &M) override;
1108  void getAnalysisUsage(AnalysisUsage &AU) const override {
1109  AU.setPreservesAll();
1110  }
1111 };
1112 
1113 /// An analysis pass that runs and returns the IRSimilarityIdentifier run on the
1114 /// Module.
1115 class IRSimilarityAnalysis : public AnalysisInfoMixin<IRSimilarityAnalysis> {
1116 public:
1118 
1120 
1121 private:
1123  static AnalysisKey Key;
1124 };
1125 
1126 /// Printer pass that uses \c IRSimilarityAnalysis.
1128  : public PassInfoMixin<IRSimilarityAnalysisPrinterPass> {
1129  raw_ostream &OS;
1130 
1131 public:
1134 };
1135 
1136 } // end namespace llvm
1137 
1138 #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:724
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::IRSimilarity::IRInstructionDataTraits::isEqual
static bool isEqual(const IRInstructionData *LHS, const IRInstructionData *RHS)
Definition: IRSimilarityIdentifier.h:323
llvm::IRSimilarity::IRSimilarityCandidate::backInstruction
Instruction * backInstruction()
Definition: IRSimilarityIdentifier.h:877
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::IRSimilarity::CandidateGVNMapping
DenseMap< IRSimilarityCandidate *, DenseMap< unsigned, DenseSet< unsigned > > > CandidateGVNMapping
Definition: IRSimilarityIdentifier.h:951
llvm::IRSimilarity::IRSimilarityIdentifier::IRSimilarityIdentifier
IRSimilarityIdentifier(bool MatchBranches=true, bool MatchIndirectCalls=true, bool MatchCallsWithName=false, bool MatchIntrinsics=true, bool MatchMustTailCalls=true)
Definition: IRSimilarityIdentifier.h:980
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
llvm::IRSimilarityAnalysis::Result
IRSimilarity::IRSimilarityIdentifier Result
Definition: IRSimilarityIdentifier.h:1117
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::IRSimilarity::IRSimilarityCandidate::getBasicBlocks
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet, SmallVector< BasicBlock * > &BBList) const
Definition: IRSimilarityIdentifier.h:840
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1832
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::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::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::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::IRSimilarity::IRSimilarityCandidate::compareStructure
static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:729
Pass.h
llvm::IRSimilarityAnalysis
An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.
Definition: IRSimilarityIdentifier.h:1115
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2951
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::IRSimilarity::IRSimilarityCandidate::getBasicBlocks
void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const
Definition: IRSimilarityIdentifier.h:831
Allocator.h
llvm::IRSimilarityIdentifierWrapperPass::getIRSI
const IRSimilarity::IRSimilarityIdentifier & getIRSI() const
Definition: IRSimilarityIdentifier.h:1103
llvm::IRSimilarity::Invisible
@ Invisible
Definition: IRSimilarityIdentifier.h:76
llvm::SPIRV::InstrList
SmallVector< MachineInstr * > InstrList
Definition: SPIRVModuleAnalysis.h:115
llvm::SpecificBumpPtrAllocator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:382
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
llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping::RelativeLocation
int RelativeLocation
The relative location to be analyzed.
Definition: IRSimilarityIdentifier.h:736
llvm::IRSimilarity::SimilarityGroup
std::vector< IRSimilarityCandidate > SimilarityGroup
Definition: IRSimilarityIdentifier.h:952
llvm::Optional< CmpInst::Predicate >
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
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::IRSimilarity::SimilarityGroupList
std::vector< SimilarityGroup > SimilarityGroupList
Definition: IRSimilarityIdentifier.h:953
llvm::hash_value
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4828
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
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
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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::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
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitAllocaInst
InstrType visitAllocaInst(AllocaInst &AI)
Definition: IRSimilarityIdentifier.h:531
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::IRSimilarity::IRInstructionData::IDL
IRInstructionDataList * IDL
Definition: IRSimilarityIdentifier.h:294
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitCallBrInst
InstrType visitCallBrInst(CallBrInst &CBI)
Definition: IRSimilarityIdentifier.h:580
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::Instruction
Definition: Instruction.h:42
llvm::IRSimilarity::IRSimilarityCandidate::isSimilar
static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)
Definition: IRSimilarityIdentifier.cpp:476
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::IRSimilarity::IRSimilarityCandidate::begin
iterator begin() const
Definition: IRSimilarityIdentifier.h:945
llvm::DbgInfoIntrinsic
This is the common base class for debug info intrinsics.
Definition: IntrinsicInst.h:139
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::CallBase::getCallingConv
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1455
llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping::IRSC
const IRSimilarityCandidate & IRSC
The IRSimilarityCandidate that holds the instruction the relative location was pulled from.
Definition: IRSimilarityIdentifier.h:733
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitInstruction
InstrType visitInstruction(Instruction &I)
Definition: IRSimilarityIdentifier.h:583
llvm::IRSimilarity::IRInstructionMapper::InstClassifier
InstructionClassification InstClassifier
Maps an Instruction to a member of InstrType.
Definition: IRSimilarityIdentifier.h:603
llvm::None
const NoneType None
Definition: None.h:24
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::IRSimilarity::IRSimilarityCandidate::getEndIdx
unsigned getEndIdx() const
Definition: IRSimilarityIdentifier.h:867
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3811
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::DenseSet< unsigned >
llvm::IRSimilarity::IRSimilarityCandidate::getFunction
Function * getFunction()
Definition: IRSimilarityIdentifier.h:885
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::IRSimilarity::IRInstructionMapper::InstructionIntegerMap
DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits > InstructionIntegerMap
Correspondence from IRInstructionData to unsigned integers.
Definition: IRSimilarityIdentifier.h:386
VI
@ VI
Definition: SIInstrInfo.cpp:7877
llvm::IRSimilarity::IRSimilarityCandidate::RelativeLocMapping::OperVal
Value * OperVal
The corresponding value.
Definition: IRSimilarityIdentifier.h:739
llvm::IRSimilarity::IRInstructionMapper::initializeForBBs
void initializeForBBs(Module &M)
Assigns values to all the basic blocks in Module M.
Definition: IRSimilarityIdentifier.h:457
llvm::IRSimilarity::Legal
@ Legal
Definition: IRSimilarityIdentifier.h:76
llvm::simple_ilist< IRInstructionData, ilist_sentinel_tracking< true > >::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:846
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:1108
llvm::IRSimilarity::IRInstructionDataTraits::getHashValue
static unsigned getHashValue(const IRInstructionData *E)
Definition: IRSimilarityIdentifier.h:317
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:4020
llvm::IRSimilarityIdentifierWrapperPass::getIRSI
IRSimilarity::IRSimilarityIdentifier & getIRSI()
Definition: IRSimilarityIdentifier.h:1102
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
llvm::IRSimilarity::IRSimilarityCandidate::operator<
bool operator<(const IRSimilarityCandidate &RHS) const
Definition: IRSimilarityIdentifier.h:940
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::IRSimilarity::InstrType
InstrType
This represents what is and is not supported when finding similarity in Instructions.
Definition: IRSimilarityIdentifier.h:76
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::IRSimilarity::IRSimilarityCandidate::back
IRInstructionData * back() const
Definition: IRSimilarityIdentifier.h:872
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:525
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
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification
Custom InstVisitor to classify different instructions for whether it can be analyzed for similarity.
Definition: IRSimilarityIdentifier.h:515
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:114
llvm::IRSimilarity::IRSimilarityCandidate::OperandMapping::OperVals
ArrayRef< Value * > & OperVals
The operand values to be analyzed.
Definition: IRSimilarityIdentifier.h:720
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::OperandMapping::IRSC
const IRSimilarityCandidate & IRSC
The IRSimilarityCandidate that holds the instruction the OperVals were pulled from.
Definition: IRSimilarityIdentifier.h:717
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::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::IRSimilarity::IRInstructionMapper::InstructionClassification::visitFuncletPadInst
InstrType visitFuncletPadInst(FuncletPadInst &FPI)
Definition: IRSimilarityIdentifier.h:538
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::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
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::IRSimilarity::IRSimilarityCandidate::end
iterator end() const
Definition: IRSimilarityIdentifier.h:946
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitLandingPadInst
InstrType visitLandingPadInst(LandingPadInst &LPI)
Definition: IRSimilarityIdentifier.h:537
llvm::IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass
IRSimilarityIdentifierWrapperPass()
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitVAArgInst
InstrType visitVAArgInst(VAArgInst &VI)
Definition: IRSimilarityIdentifier.h:534
llvm::IRSimilarity::IRSimilarityCandidate::front
IRInstructionData * front() const
Definition: IRSimilarityIdentifier.h:870
llvm::IRSimilarity::IRInstructionData::Legal
bool Legal
The legality of the wrapped instruction.
Definition: IRSimilarityIdentifier.h:125
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::IRSimilarity::IRInstructionMapper::InstructionClassification::visitIntrinsicInst
InstrType visitIntrinsicInst(IntrinsicInst &II)
Definition: IRSimilarityIdentifier.h:543
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
InstVisitor.h
llvm::IRSimilarityIdentifierWrapperPass::ID
static char ID
Definition: IRSimilarityIdentifier.h:1099
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:78
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::CallInst::isMustTailCall
bool isMustTailCall() const
Definition: Instructions.h:1673
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::ilist_node
Definition: ilist_node.h:149
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::IRSimilarityIdentifierWrapperPass::doInitialization
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: IRSimilarityIdentifier.cpp:1237
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:578
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
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::IRInstructionMapper::IRInstructionMapper
IRInstructionMapper(SpecificBumpPtrAllocator< IRInstructionData > *IDA, SpecificBumpPtrAllocator< IRInstructionDataList > *IDLA)
Definition: IRSimilarityIdentifier.h:498
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
llvm::CallingConv::SwiftTail
@ SwiftTail
This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...
Definition: CallingConv.h:87
llvm::IRSimilarity::IRSimilarityCandidate::getStartIdx
unsigned getStartIdx() const
Definition: IRSimilarityIdentifier.h:864
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
PassManager.h
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::InstructionClassification
InstructionClassification()=default
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::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::IRSimilarity::IRInstructionDataTraits::getTombstoneKey
static IRInstructionData * getTombstoneKey()
Definition: IRSimilarityIdentifier.h:313
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
llvm::IRSimilarity::IRInstructionData::initializeInstruction
void initializeInstruction()
Fills data stuctures for IRInstructionData when it is constructed from a.
Definition: IRSimilarityIdentifier.cpp:54
Instructions.h
llvm::IRSimilarity::IRSimilarityCandidate::getEndBB
BasicBlock * getEndBB()
Definition: IRSimilarityIdentifier.h:882
llvm::FuncletPadInst
Definition: InstrTypes.h:2370
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitCallInst
InstrType visitCallInst(CallInst &CI)
Definition: IRSimilarityIdentifier.h:556
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::IRSimilarity::IRInstructionDataTraits::getEmptyKey
static IRInstructionData * getEmptyKey()
Definition: IRSimilarityIdentifier.h:312
N
#define N
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::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::IRSimilarity::IRInstructionDataTraits
Definition: IRSimilarityIdentifier.h:311
llvm::IntrinsicInst::isAssumeLikeIntrinsic
bool isAssumeLikeIntrinsic() const
Checks if the intrinsic is an annotation.
Definition: IntrinsicInst.h:88
llvm::IRSimilarity::IRSimilarityCandidate::getLength
unsigned getLength() const
Definition: IRSimilarityIdentifier.h:861
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::simple_ilist
A simple intrusive list implementation.
Definition: simple_ilist.h:78
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitBranchInst
InstrType visitBranchInst(BranchInst &BI)
Definition: IRSimilarityIdentifier.h:520
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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
llvm::CallingConv::Tail
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
llvm::IRSimilarity::IRSimilarityIdentifier
This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...
Definition: IRSimilarityIdentifier.h:978
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitTerminator
InstrType visitTerminator(Instruction &I)
Definition: IRSimilarityIdentifier.h:582
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
llvm::IRSimilarityAnalysisPrinterPass
Printer pass that uses IRSimilarityAnalysis.
Definition: IRSimilarityIdentifier.h:1127
llvm::IRSimilarity::IRInstructionMapper::InstructionClassification::visitDbgInfoIntrinsic
InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII)
Definition: IRSimilarityIdentifier.h:542
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
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:255
llvm::IRSimilarityAnalysisPrinterPass::IRSimilarityAnalysisPrinterPass
IRSimilarityAnalysisPrinterPass(raw_ostream &OS)
Definition: IRSimilarityIdentifier.h:1132
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73