[IRSim] Adding wrapper pass for IRSimilarityIdentfier

[AndrewLitteken]

Summary

This introduces an analysis pass that wraps IRSimilarityIdentifier, and adds a printer pass to examine in what function similarities are being found.
Test for what the printer pass can find are in test/Analysis/IRSimilarityIdentifier.

[AndrewLitteken]

Updating for clang-format.

[jroelofs]

LGTM

[AndrewLitteken]

Updating for the new Optional in IRSimilarityIdentifier.

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

703

The accessors for Optional do this check for you, so you can just "dereference" it with * or -> as needed without worrying about adding your own assertion on it.

If it's expected that IRSI will always have this populated once it has been constructed, then maybe getSimilarity() ought to be the one to unwrap the Optional.

[AndrewLitteken]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

703

Well findSimilarity needs to have been run, or the constructor where a module has been passed to the IRSI. So, it's possible that you can construct IRSI where the SimilarityCandidates are None.

I'm not sure if that changes what you're proposing. I think it could still make sense to put the derefence in getSimilarity since you shouldn't be calling it unless you've populated the IRSI with a module already.

[AndrewLitteken]

Updating optional handling

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

703

I think it could still make sense to put the derefence in getSimilarity

agreed

707

So maybe this is just:

for (std::vector<IRSimilarityCandidate> &CandVec : IRSI.getSimilarity()) {

or

for (std::vector<IRSimilarityCandidate> &CandVec : *IRSI.getSimilarity()) {

depending on which way you decide to go w/ moving that dereference.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
 #define LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
 
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
 #include "llvm/Support/Allocator.h"
 
 namespace llvm {
 namespace IRSimilarity {
 
 struct IRInstructionDataList;
 
 /// This represents what is and is not supported when finding similarity in
struct IRInstructionData : ilist_node<IRInstructionData> {
   /// \code
   /// %add1 = add i32 %x1, %y1
   /// %add2 = add i32 %x2, %y2
   ///
   /// %sub = sub i32 %x1, %y1
   ///
   /// %add_i64 = add i64 %x2, %y2
   /// \endcode
   /// 
   /// Because the first two adds operate the same types, and are performing the
   /// same action, they will be hashed to the same value.
   ///
   /// However, the subtraction instruction is not the same as an addition, and
   /// will be hashed to a different value.
   ///
   /// Finally, the last add has a different type compared to the first two add
   /// instructions, so it will also be hashed to a different value that any of
   /// the previous instructions.
   ///
   /// \param [in] Value - The IRInstructionData instance to be hashed.
   /// \returns A hash_value of the IRInstructionData.
   friend hash_code hash_value(const IRInstructionData &Value) {
     return hash_combine(
         hash_value(Value.Inst->getOpcode()),
         hash_value(Value.Inst->getType()),
         hash_combine_range(Value.OperTypes.begin(), Value.OperTypes.end()));
   }
 
   IRInstructionDataList *IDL = nullptr;
 };
 
 struct IRInstructionDataList : simple_ilist<IRInstructionData> {};

 /// \endcode
 /// And produce a "numeric string representation" like so:
 /// 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2
 ///
 /// This technique is replicated in the MachineOutliner, but acts on
 /// MachineInstrs, rather than IRInstructionData, the wrapper for an
 /// Instruction.
 struct IRInstructionMapper {
   /// The starting illegal instruction number to map to.  
   ///
   /// Set to -3 for compatibility with \p DenseMapInfo<unsigned>.
   unsigned IllegalInstrNumber = static_cast<unsigned>(-3);
 
   /// The next available integer to assign to a legal Instruction to.
   unsigned LegalInstrNumber = 0;
 
   /// Correspondence from IRInstructionData to unsigned integers.
struct IRInstructionMapper {
   /// \param [in,out] UnsignedVec - Vector of unsigned integers to append to.
   void convertToUnsignedVec(BasicBlock &BB,
                             std::vector<IRInstructionData *> &InstrList,
                             std::vector<unsigned> &UnsignedVec);
 
   /// Maps an Instruction to a legal integer.
   ///
   /// \param [in] It - The Instruction to be mapped to an integer.
   /// \param [in,out] UnsignedVecForBB - Vector of unsigned integers to append to.
   /// \param [in,out] InstrList - Vector of InstructionData to append to.
   /// \returns The integer \p It was mapped to.
   unsigned mapToLegalUnsigned(BasicBlock::iterator &It,
                               std::vector<unsigned> &UnsignedVecForBB,
                               std::vector<IRInstructionData *> &InstrListForBB);
 
   /// Maps an Instruction to an illegal integer.
   ///
   /// \param [in] It - The \p Instruction to be mapped to an integer.
   /// \param [in,out] UnsignedVecForBB -Vector of unsigned integers to append to.
   /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
   /// \param End - true if creating a dummy IRInstructionData at the end of a
   /// basic block.
   /// \returns The integer \p It was mapped to.
   unsigned mapToIllegalUnsigned(
       BasicBlock::iterator &It, std::vector<unsigned> &UnsignedVecForBB,
       std::vector<IRInstructionData *> &InstrListForBB, bool End = false);
 
   IRInstructionMapper(BumpPtrAllocator *IDA) : InstDataAllocator(IDA){
     // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
     // changed.
     assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
            "DenseMapInfo<unsigned>'s empty key isn't -1!");
     assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
            "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
     IDL = new (InstDataAllocator->Allocate<IRInstructionDataList>())
         IRInstructionDataList();
struct InstructionClassification
     InstrType visitVAArgInst(VAArgInst &VI) { return Illegal; }
     // We exclude all exception handling cases since they are so context
     // dependent.
     InstrType visitLandingPadInst(LandingPadInst &LPI) { return Illegal; }
     InstrType visitFuncletPadInst(FuncletPadInst &FPI) { return Illegal; }
     // DebugInfo should be included in the regions, but should not be
     // analyzed for similarity as it has no bearing on the outcome of the
     // program.
     InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII) {
       return Invisible;
     }
     // TODO: Handle GetElementPtrInsts
     InstrType visitGetElementPtrInst(GetElementPtrInst &GEPI) {
       return Illegal;
     }
     // TODO: Handle specific intrinsics.
     InstrType visitIntrinsicInst(IntrinsicInst &II) { return Illegal; }
     // TODO: Handle CallInsts.
     InstrType visitCallInst(CallInst &CI) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitInvokeInst(InvokeInst &II) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; }
     // TODO: Handle interblock similarity.
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { 
       return Legal;
     }
   };
 
   /// Maps an Instruction to a member of InstrType.
   InstructionClassification InstClassifier;
 };
 
public:
 
   /// Compare the operands in \p A and \p B and check that the current mapping
   /// of global value numbers from \p A to \p B and \p B to \A is consistent.
   ///
   /// \param A - the first IRInstructionCandidate to compare.
   /// \param B - The second IRInstructionCandidate to compare.
   /// \param OperValsA - The operands in the instruction from \p A.
   /// \param OperValsB - The operands in the instruction from \p B.
   /// \param ValueNumberMappingA - The current mapping of global values numbering
   /// from \p A to \p B.
   /// \param ValueNumberMappingB - The current mapping of global values 
   /// numbering from \p B to \p A.
   /// \returns true if the IRSimilarityCandidates operands are compatible.
   static bool compareOperandMapping(
       const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
       SmallVector<Value *, 4> &OperValsA, SmallVector<Value *, 4> &OperValsB,
       DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
public:
 
   /// \param RHS -The IRSimilarityCandidate to compare against
   /// \returns true if the IRSimilarityCandidate is occurs after the
   /// IRSimilarityCandidate in the program.
   bool operator<(const IRSimilarityCandidate &RHS) const {
     return getStartIdx() > RHS.getStartIdx();
   }
 
   using iterator =  IRInstructionDataList::iterator;
   iterator begin() const { return iterator(front()); }
   iterator end() const { return std::next(iterator(back())); }
 };
 
 typedef std::vector<IRSimilarityCandidate> SimilarityGroup;
 typedef std::vector<SimilarityGroup> SimilarityGroupList;
 
 /// This class puts all the pieces of the IRInstructionData,

 ///
 /// A list of the different similarity groups is then returned after
 /// analyzing the module.
 class IRSimilarityIdentifier {
 public:
   IRSimilarityIdentifier() : Mapper(&InstDataAllocator) {}
 
   /// \param M the module to find similarity in.
   IRSimilarityIdentifier(Module &M) : Mapper(&InstDataAllocator){
     findSimilarity(M);
     ModulesAnalyzed = true;
   }
 
 private:
 
   /// Map the instructions in the module to unsigned integers, using mapping
   /// already present in the Mapper if possible.
   ///
   /// \param [in] M Module - To map to integers.
   /// \param [in,out] InstrList - The vector to append IRInstructionData to.
   /// \param [in,out] UnsignedVec - The vector to append integers to.
   void populateMapper(Module &M, std::vector<IRInstructionData *> &InstrList,
                       std::vector<unsigned> &UnsignedVec);
private:
   ///
   /// \param [in,out] InstrList - The vector to append IRInstructionData to.
   /// \param [in,out] UnsignedVec - The vector to append integers to.
   /// candidates found in the program.
   void findCandidates(std::vector<IRInstructionData *> &InstrList,
                       std::vector<unsigned> &UnsignedVec);
 
 public:
 
   // Find the IRSimilarityCandidates in the \p Modules and group by structural
   // similarity in a SimilarityGroup, each group is returned in a
   // SimilarityGroupList.
   //
   // \param [in] Modules - the modules to analyze.
   // \returns The groups of similarity ranges found in the modules.
   SimilarityGroupList &
   findSimilarity(std::vector<std::unique_ptr<Module>> &Modules);
private:
   bool ModulesAnalyzed = false;
 
   /// The SimilarityGroups found with the most recent run of \ref
   /// findSimilarity.
   SimilarityGroupList SimilarityCandidates;
 };
 
 } // end namespace IRSimilarity
+
+/// An analysis pass based on legacy pass manager that runs and returns
+/// IRSimilarityIdentifier run on the Module.
+class IRSimilarityIdentifierWrapperPass : public ModulePass {
+  std::unique_ptr<IRSimilarity::IRSimilarityIdentifier> IRSI;
+
+public:
+  static char ID;
+  IRSimilarityIdentifierWrapperPass();
+
+  IRSimilarity::IRSimilarityIdentifier &getIRSI() { return *IRSI; }
+  const IRSimilarity::IRSimilarityIdentifier &getIRSI() const { return *IRSI; }
+
+  bool doInitialization(Module &M) override;
+  bool doFinalization(Module &M) override;
+  bool runOnModule(Module &M) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
+/// An analysis pass that runs and returns the IRSimilarityIdentifier run on the
+/// Module.
+class IRSimilarityAnalysis : public AnalysisInfoMixin<IRSimilarityAnalysis> {
+public:
+  typedef IRSimilarity::IRSimilarityIdentifier Result;
+
+  Result run(Module &M, ModuleAnalysisManager &);
+
+private:
+  friend AnalysisInfoMixin<IRSimilarityAnalysis>;
+  static AnalysisKey Key;
+};
+
+/// Printer pass that uses \c IRSimilarityAnalysis.
+class IRSimilarityAnalysisPrinterPass
+    : public PassInfoMixin<IRSimilarityAnalysisPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit IRSimilarityAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H

llvm/include/llvm/InitializePasses.h

 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
 void initializeHardwareLoopsPass(PassRegistry&);
 void initializeHeapProfilerLegacyPassPass(PassRegistry &);
 void initializeHotColdSplittingLegacyPassPass(PassRegistry&);
 void initializeHWAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeIPSCCPLegacyPassPass(PassRegistry&);
 void initializeIRCELegacyPassPass(PassRegistry&);
+void initializeIRSimilarityIdentifierWrapperPassPass(PassRegistry&);
 void initializeIRTranslatorPass(PassRegistry&);
 void initializeIVUsersWrapperPassPass(PassRegistry&);
 void initializeIfConverterPass(PassRegistry&);
 void initializeImmutableModuleSummaryIndexWrapperPassPass(PassRegistry&);
 void initializeImplicitNullChecksPass(PassRegistry&);
 void initializeIndVarSimplifyLegacyPassPass(PassRegistry&);
 void initializeIndirectBrExpandPassPass(PassRegistry&);
 void initializeInferAddressSpacesPass(PassRegistry&);

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
   initializeAAResultsWrapperPassPass(Registry);
   initializeGlobalsAAWrapperPassPass(Registry);
   initializeIVUsersWrapperPassPass(Registry);
   initializeInstCountLegacyPassPass(Registry);
   initializeIntervalPartitionPass(Registry);
+  initializeIRSimilarityIdentifierWrapperPassPass(Registry);
   initializeLazyBranchProbabilityInfoPassPass(Registry);
   initializeLazyBlockFrequencyInfoPassPass(Registry);
   initializeLazyValueInfoWrapperPassPass(Registry);
   initializeLazyValueInfoPrinterPass(Registry);
   initializeLegacyDivergenceAnalysisPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 // similarities in IR including the IRInstructionMapper.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/User.h"
+#include "llvm/InitializePasses.h"
 #include "llvm/Support/SuffixTree.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
 IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
                                      IRInstructionDataList &IDList)
     : Inst(&I), Legal(Legality), IDL(&IDList) {
for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
     case InstrType::Invisible:
       AddedIllegalLastTime = false;
       break;
     }
   }
 
   if (HaveLegalRange) {
     mapToIllegalUnsigned(It, UnsignedVecForBB, InstrListForBB, true);
     for_each(InstrListForBB, [this](IRInstructionData *ID){
       this->IDL->push_back(*ID);
     });
     InstrList.insert(InstrList.end(), InstrListForBB.begin(),
                      InstrListForBB.end());
     UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForBB.begin(),
                        UnsignedVecForBB.end());
   }
 }

 bool IRSimilarityCandidate::isSimilar(const IRSimilarityCandidate &A,
                                       const IRSimilarityCandidate &B) {
   if (A.getLength() != B.getLength())
     return false;
 
   auto InstrDataForBoth =
       zip(make_range(A.begin(), A.end()), make_range(B.begin(), B.end()));
 
   return all_of(
       InstrDataForBoth,
       [](std::tuple<IRInstructionData &, IRInstructionData &> R) {
         IRInstructionData &A = std::get<0>(R);
         IRInstructionData &B = std::get<0>(R);
         if (!A.Legal || !B.Legal)
           return false;
         return isClose(std::get<0>(R), std::get<1>(R));
       });
bool checkNumberingAndReplace(
   // and can return true. But, if the mapping was
   // CurrentMapping: {1: {3}}
   // we would return false.
 
   bool WasInserted;
   DenseMap<unsigned, DenseSet<unsigned>>::iterator Val;
 
   std::tie(Val, WasInserted) = CurrentSrcTgtNumberMapping.insert(
     std::make_pair(SourceArgVal, DenseSet<unsigned>({TargetArgVal})));
 
   // If we created a new mapping, then we are done.
   if (WasInserted)
     return true;
 
   // If there is more than one option in the mapping set, and the target value
   // is included in the mapping set replace that set with one that only includes
   // the target value, as it is the only valid mapping via the non commutative
   // instruction.
 
   DenseSet<unsigned> &TargetSet = Val->second;
   if (TargetSet.size() > 1 &&
       TargetSet.find(TargetArgVal) != TargetSet.end()) {
     TargetSet.clear();
     TargetSet.insert(TargetArgVal);
     return true;
   } 
 
   // Return true if we can find the value in the set.
   return TargetSet.find(TargetArgVal) != TargetSet.end();
 }
 
 bool IRSimilarityCandidate::compareOperandMapping(
     const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
     SmallVector<Value *, 4> &OperValsA, SmallVector<Value *, 4> &OperValsB,
bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
   if (A.getLength() != B.getLength())
     return false;
 
   if (A.ValueToNumber.size() != B.ValueToNumber.size())
     return false;
 
   iterator It = A.begin();
   iterator OIt = B.begin();
   
   // These sets create a create a mapping between the values in one candidate
   // to values in the other candidate.  If we create a set with one element,
   // and that same element maps to the original element in the candidate
   // we have a good mapping.
   DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMapping;
   DenseMap<unsigned, DenseSet<unsigned>> OtherValueNumberMapping;
   DenseMap<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
 
   bool WasInserted;
 
   // Iterate over the instructions contained in each candidate
   unsigned SectionLength = A.getStartIdx() + A.getLength();
   for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
        It++, OIt++, Loc++) {
     // Make sure the instructions are similar to one another.
     if(!isClose(*It, *OIt))
       return false;
 
     Instruction *I = (*It).Inst;
     Instruction *OI = (*OIt).Inst;
 
     if (!(*It).Legal || !(*OIt).Legal)
       return false;
 
for (BasicBlock &BB : F) {
       // of unsigned integers.
       Mapper.convertToUnsignedVec(BB, InstrListForModule, UnsignedVecForModule);
     }
   }
 
   // Insert the InstrListForModule at the end of the overall InstrList so that
   // we can have a long InstrList for the entire set of Modules being analyzed.
   InstrList.insert(InstrList.end(), InstrListForModule.begin(),
                       InstrListForModule.end());
   // Do the same as above, but for the UnsignedVec.
   UnsignedVec.insert(UnsignedVec.end(), UnsignedVecForModule.begin(),
                         UnsignedVecForModule.end());
 }
 
 void IRSimilarityIdentifier::populateMapper(
     std::vector<std::unique_ptr<Module>> &Modules,
     std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &UnsignedVec) {
 
   // Iterate over, and map the instructions in each module.
for (InnerCandIt = std::next(CandIt),
         continue;
 
       // Otherwise we determine if they have the same structure and add it to
       // vector if they match.
       SameStructure =
           IRSimilarityCandidate::compareStructure(*CandIt, *InnerCandIt);
       if (!SameStructure)
         continue;
       
       CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
       CurrentGroupPair->second.push_back(*InnerCandIt);
     }
   }
 }
 
 void IRSimilarityIdentifier::findCandidates(
     std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &UnsignedVec) {
   SuffixTree ST(UnsignedVec);
 
   std::vector<IRSimilarityCandidate> CandsForRepSubstring;
   std::vector<SimilarityGroup> NewCandidateGroups;
   
   DenseMap<unsigned, SimilarityGroup> StructuralGroups;
 
   // Iterate over the subsequences found by the Suffix Tree to create
   // IRSimilarityCandidates for each repeated subsequence and determine which
   // instances are structurally similar to one another.
   for (auto It = ST.begin(), Et = ST.end(); It != Et; ++It) {
     createCandidatesFromSuffixTree(Mapper, InstrList, UnsignedVec, *It,
                                    CandsForRepSubstring);
 
     if (CandsForRepSubstring.size() < 2)
       continue;
 
     findCandidateStructures(CandsForRepSubstring, StructuralGroups);
     for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups)
       // We only add the group if it contains more than one
       // IRSimilarityCandidate.  If there is only one, that means there is no
       // other repeated subsequence with the same structure.
       if (Group.second.size() > 1)
         SimilarityCandidates.push_back(Group.second);
 
 
     CandsForRepSubstring.clear();
     StructuralGroups.clear();
     NewCandidateGroups.clear();
   }
 }
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
     std::vector<std::unique_ptr<Module>> &Modules) {
SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
 
   populateMapper(Modules, InstrList, UnsignedVec);
   findCandidates(InstrList, UnsignedVec);
 
   ModulesAnalyzed = true;
   return SimilarityCandidates;
 }
 
 SimilarityGroupList &
 IRSimilarityIdentifier::findSimilarity(Module &M) {
   // If we've already analyzed a Module or set of Modules, so we must clear
   // the SimilarityCandidates to make sure we do not have only old values
   // hanging around.
   if (ModulesAnalyzed) {
     ModulesAnalyzed = false;
     SimilarityCandidates.clear();
   }
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
   populateMapper(M, InstrList, UnsignedVec);
   findCandidates(InstrList, UnsignedVec);
 
   ModulesAnalyzed = true;
   return SimilarityCandidates;
 }
+
+INITIALIZE_PASS(IRSimilarityIdentifierWrapperPass, "ir-similarity-identifier",
+                "ir-similarity-identifier", false, true)
+
+IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass()
+    : ModulePass(ID) {
+  initializeIRSimilarityIdentifierWrapperPassPass(
+      *PassRegistry::getPassRegistry());
+}
+
+bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) {
+  IRSI.reset(new IRSimilarityIdentifier(M));
+  return false;
+}
+
+bool IRSimilarityIdentifierWrapperPass::doFinalization(Module &M) {
+  IRSI.reset();
+  return false;
+}
+
+bool IRSimilarityIdentifierWrapperPass::runOnModule(Module &M) {
+  // All the real work is done in the constructor for the pass.
+  IRSI.reset(new IRSimilarityIdentifier(M));
+  return false;
+}
+
+AnalysisKey IRSimilarityAnalysis::Key;
+IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
+                                               ModuleAnalysisManager &) {
+
+  return IRSimilarityIdentifier(M);
+}
+
+PreservedAnalyses
+IRSimilarityAnalysisPrinterPass::run(Module &M, ModuleAnalysisManager &AM) {
+  IRSimilarityIdentifier &IRSI = AM.getResult<IRSimilarityAnalysis>(M);
+
+  for (std::vector<IRSimilarityCandidate> &CandVec : IRSI.getSimilarity()) {
+    OS << CandVec.size() << " candidates of length "
+       << CandVec.begin()->getLength() << ".  Found in: \n";
+    for (IRSimilarityCandidate &Cand : CandVec) {
+      OS << "  Function: " << Cand.front()->Inst->getFunction()->getName().str()
+         << ",  Basic Block: ";
+      if (Cand.front()->Inst->getParent()->getName().str() == "")
+        OS << "(unnamed)\n";
+      else
+        OS << Cand.front()->Inst->getParent()->getName().str() << "\n";
+    }
+  }
+
+  return PreservedAnalyses::all();
+}
+
+char IRSimilarityIdentifierWrapperPass::ID = 0;

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/InlineSizeEstimatorAnalysis.h"
 #include "llvm/Analysis/InstCount.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopCacheAnalysis.h"

llvm/lib/Passes/PassRegistry.def

 MODULE_ANALYSIS("module-summary", ModuleSummaryIndexAnalysis())
 MODULE_ANALYSIS("no-op-module", NoOpModuleAnalysis())
 MODULE_ANALYSIS("profile-summary", ProfileSummaryAnalysis())
 MODULE_ANALYSIS("stack-safety", StackSafetyGlobalAnalysis())
 MODULE_ANALYSIS("verify", VerifierAnalysis())
 MODULE_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 MODULE_ANALYSIS("asan-globals-md", ASanGlobalsMetadataAnalysis())
 MODULE_ANALYSIS("inline-advisor", InlineAdvisorAnalysis())
+MODULE_ANALYSIS("ir-similarity", IRSimilarityAnalysis())
 
 #ifndef MODULE_ALIAS_ANALYSIS
 #define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS)                               \
   MODULE_ANALYSIS(NAME, CREATE_PASS)
 #endif
 MODULE_ALIAS_ANALYSIS("globals-aa", GlobalsAA())
 #undef MODULE_ALIAS_ANALYSIS
 #undef MODULE_ANALYSIS

 MODULE_PASS("inferattrs", InferFunctionAttrsPass())
 MODULE_PASS("inliner-wrapper", ModuleInlinerWrapperPass())
 MODULE_PASS("insert-gcov-profiling", GCOVProfilerPass())
 MODULE_PASS("instrorderfile", InstrOrderFilePass())
 MODULE_PASS("instrprof", InstrProfiling())
 MODULE_PASS("internalize", InternalizePass())
 MODULE_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 MODULE_PASS("ipsccp", IPSCCPPass())
+MODULE_PASS("print-ir-similarity", IRSimilarityAnalysisPrinterPass(dbgs()))
 MODULE_PASS("lowertypetests", LowerTypeTestsPass(nullptr, nullptr))
 MODULE_PASS("mergefunc", MergeFunctionsPass())
 MODULE_PASS("name-anon-globals", NameAnonGlobalPass())
 MODULE_PASS("no-op-module", NoOpModulePass())
 MODULE_PASS("objc-arc", ObjCARCOptPass())
 MODULE_PASS("partial-inliner", PartialInlinerPass())
 MODULE_PASS("pgo-icall-prom", PGOIndirectCallPromotion())
 MODULE_PASS("pgo-instr-gen", PGOInstrumentationGen())

llvm/test/Analysis/IRSimilarityIdentifier/basic.ll

+; RUN: opt -disable-output -S -passes=print-ir-similarity < %s 2>&1 | FileCheck %s
+
+; This is a simple test to make sure the IRSimilarityIdentifier and 
+; IRSimilarityPrinterPass is working.
+
+; CHECK: 4 candidates of length 2.  Found in: 
+; CHECK-NEXT:   Function: cat,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: dog,  Basic Block: entry
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT: 4 candidates of length 3.  Found in: 
+; CHECK-NEXT:   Function: cat,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: dog,  Basic Block: entry
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT: 4 candidates of length 4.  Found in: 
+; CHECK-NEXT:   Function: cat,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: dog,  Basic Block: entry
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT: 4 candidates of length 5.  Found in: 
+; CHECK-NEXT:   Function: cat,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: dog,  Basic Block: entry
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT: 4 candidates of length 6.  Found in: 
+; CHECK-NEXT:   Function: cat,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: dog,  Basic Block: entry
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+
+define linkonce_odr void @fish() {
+entry:
+  %0 = alloca i32, align 4
+  %1 = alloca i32, align 4
+  %2 = alloca i32, align 4
+  %3 = alloca i32, align 4
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  store i32 6, i32* %0, align 4
+  store i32 1, i32* %1, align 4
+  store i32 2, i32* %2, align 4
+  store i32 3, i32* %3, align 4
+  store i32 4, i32* %4, align 4
+  store i32 5, i32* %5, align 4
+  ret void
+}
+
+define void @turtle() {
+  %1 = alloca i32, align 4
+  %2 = alloca i32, align 4
+  %3 = alloca i32, align 4
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  %6 = alloca i32, align 4
+  store i32 1, i32* %1, align 4
+  store i32 2, i32* %2, align 4
+  store i32 3, i32* %3, align 4
+  store i32 4, i32* %4, align 4
+  store i32 5, i32* %5, align 4
+  store i32 6, i32* %6, align 4
+  ret void
+}
+
+define void @cat() {
+entry:
+  %0 = alloca i32, align 4
+  %1 = alloca i32, align 4
+  %2 = alloca i32, align 4
+  %3 = alloca i32, align 4
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  store i32 6, i32* %0, align 4
+  store i32 1, i32* %1, align 4
+  store i32 2, i32* %2, align 4
+  store i32 3, i32* %3, align 4
+  store i32 4, i32* %4, align 4
+  store i32 5, i32* %5, align 4
+  ret void
+}
+
+define void @dog() {
+entry:
+  %0 = alloca i32, align 4
+  %1 = alloca i32, align 4
+  %2 = alloca i32, align 4
+  %3 = alloca i32, align 4
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  store i32 6, i32* %0, align 4
+  store i32 1, i32* %1, align 4
+  store i32 2, i32* %2, align 4
+  store i32 3, i32* %3, align 4
+  store i32 4, i32* %4, align 4
+  store i32 5, i32* %5, align 4
+  ret void
+}

llvm/test/Analysis/IRSimilarityIdentifier/different.ll

+; RUN: opt -disable-output -S -passes=print-ir-similarity < %s 2>&1 | FileCheck --allow-empty %s
+
+; Check to make sure that the IRSimilarityIdentifier and IRSimilarityPrinterPass
+; return items only within the same function when there are different sets of
+; instructions in functions.
+
+; CHECK: 2 candidates of length 3.  Found in: 
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT:   Function: turtle,  Basic Block: (unnamed)
+; CHECK-NEXT: 2 candidates of length 5.  Found in: 
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+; CHECK-NEXT:   Function: fish,  Basic Block: entry
+
+define linkonce_odr void @fish() {
+entry:
+  %0 = alloca i32, align 4
+  %1 = alloca i32, align 4
+  %2 = alloca i32, align 4
+  %3 = alloca i32, align 4
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  store i32 6, i32* %0, align 4
+  store i32 1, i32* %1, align 4
+  store i32 2, i32* %2, align 4
+  store i32 3, i32* %3, align 4
+  store i32 4, i32* %4, align 4
+  store i32 5, i32* %5, align 4
+  ret void
+}
+
+define void @turtle(i32* %0, i32* %1, i32* %2, i32* %3) {
+  %a = load i32, i32* %0
+  %b = load i32, i32* %1
+  %c = load i32, i32* %2
+  %d = load i32, i32* %3
+  ret void
+}
 No newline at end of file

llvm/test/Analysis/IRSimilarityIdentifier/nothing.ll

+; RUN: opt -disable-output -S -passes=print-ir-similarity < %s 2>&1 | FileCheck --allow-empty %s
+
+; This is a simple test to make sure the IRSimilarityPrinterPass returns
+; nothing when there is nothing to analyze.
+
+; CHECK-NOT: Found in
+
+define linkonce_odr void @fish() {
+entry:
+  ret void
+}
 No newline at end of file