[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

680

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

680

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

680

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

agreed

684

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
private:
   IRInstructionMapper Mapper;
 
   /// The SimilarityGroups found with the most recent run of \ref
   /// findSimilarity. None if there is no recent run.
   Optional<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 initializeMemProfilerLegacyPassPass(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);
   initializeLintLegacyPassPass(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) {
SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) {
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> IntegerMapping;
 
   populateMapper(M, InstrList, IntegerMapping);
   findCandidates(InstrList, IntegerMapping);
 
   return SimilarityCandidates.getValue();
 }
+
+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);
+  Optional<SimilarityGroupList> &SimilarityCandidatesOpt = IRSI.getSimilarity();
+
+  for (std::vector<IRSimilarityCandidate> &CandVec : *SimilarityCandidatesOpt) {
+    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/CallGraph.h"
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/Delinearization.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/Lint.h"
 #include "llvm/Analysis/LoopAccessAnalysis.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("objc-arc-contract", ObjCARCContractPass())
 MODULE_PASS("partial-inliner", PartialInlinerPass())
 MODULE_PASS("pgo-icall-prom", PGOIndirectCallPromotion())

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
+}

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
+}