[IRSim] Adding basic implementation of llvm-sim.

[AndrewLitteken]

Summary

This is a similarity visualization tool that accepts a Module and passes it to the IRSimilarityIdentifier. The resulting SimilarityGroups are output in a JSON file.

Tests are found in test/tools/llvm-sim and check for the file not found, a bad module, and that the JSON is created correctly.

Example of what can be built on top of the JSON output:

[AndrewLitteken]

Updating for clang-format.

[jroelofs]

llvm/tools/llvm-sim/FindSimilarities.cpp

50 ↗

(On Diff #289470)

A useful pattern for tools like this (and I think this might forbid?) is to support reading from stdin / writing to stdout when the filename is -. That's also useful for the tests, because it lets you eliminate the cat %t RUN lines.

llvm/tools/llvm-sim/FindSimilarities.h

27 ↗

(On Diff #289470)

StringRef?

58 ↗

(On Diff #289470)

StringRef?

llvm/tools/llvm-sim/JSONExporter.h

44 ↗

(On Diff #289470)

A free function would probably be fine. The class doesn't seem to be buying you much here.

llvm/tools/llvm-sim/llvm-sim.cpp

37

I think it would clean up the error handling a bit if the file handling & bitcode reading all happened here, and then have this transfer ownership of the constructed module into the tool object.

That said, the tool object isn't buying you much either. I'd probably end up folding most/all of it into this file, with helper functions as needed.

[AndrewLitteken]

Reorganization, and implication of string handling.

[jroelofs]

LGTM

[vsk]

llvm/tools/llvm-sim/llvm-sim.cpp

133

If it's not necessary/desirable to number meta-instructions (e.g. debug info intrinsics), BB.instructionsWithoutDebug() might be a better fit here.

[vsk]

llvm/tools/llvm-sim/llvm-sim.cpp

134

Very minor nit -- any reason not to prefer a shorter way to write this, maybe 'map[&I] = Num++' or 'map.emplace(&I, Num++)' if it's necessary to avoid default-constructing a DenseMapPair?

[AndrewLitteken]

llvm/tools/llvm-sim/llvm-sim.cpp

133

I agree, that would probably be better here.

134

I don't think so. I just didn't realize those shortcuts existed.

[AndrewLitteken]

Excluding debug instructions, and updating how we add to the DenseMap.

[vsk]

(This is really nice work! FTR, my comments were drive-bys, I didn't intend for them to be blocking.)

[MaskRay]

llvm/test/tools/llvm-sim/fail-cases.test

3

For FileCheck, double-dash --check-prefix is preferred

llvm/test/tools/llvm-sim/single-sim-file.test

3

FileCheck %s < %t

[AndrewLitteken]

Fixing CMakeLists.txt to accurately reflect what needs to be linked, and flags and redirection for the tests themselves.

[AndrewLitteken]

Updating LLVMBuild.txt as well.

[AndrewLitteken]

These are updates to try to fix the build problem of the llvm-sim executable not being found for tests on Windows and some Linux builds. Unfortunately, I do not have the errors anymore. Is there something else that will need added to add llvm-sim as a tool? The changes I've made reflect what I've found has been done for other tools.

[paquette]

I think if the errors on Windows and Linux are gone, it's fine to recommit.

[AndrewLitteken]

There's a bug with one of the Windows buildbots where the error message doesn't match (even though it looks like it does), but I haven't quite been able to figure out why it's failing yet. I think it has something do to with the fact that it's reporting an error, and that there is a FileCheck prefix.

https://lab.llvm.org/buildbot#builders/123/builds/3498

[zero9178]

In D86974#2641788, @AndrewLitteken wrote:

There's a bug with one of the Windows buildbots where the error message doesn't match (even though it looks like it does), but I haven't quite been able to figure out why it's failing yet. I think it has something do to with the fact that it's reporting an error, and that there is a FileCheck prefix.

https://lab.llvm.org/buildbot#builders/123/builds/3498

Visual Studios Standard library starts their errors in lower case, which do not match the hardcoded values you used in your tests. Take a look at the lit feature added here https://reviews.llvm.org/rGc52fe0b02172e707aa2ba38cd2e01a1fc70dd0da, you should be able to use it to expand to the correct platform specific error message

[AndrewLitteken]

Visual Studios Standard library starts their errors in lower case, which do not match the hardcoded values you used in your tests. Take a look at the lit feature added here https://reviews.llvm.org/rGc52fe0b02172e707aa2ba38cd2e01a1fc70dd0da, you should be able to use it to expand to the correct platform specific error message

Ah I see, that only applies to the second part of the error right? The first part (Could not open file) is LLVM generated I think.

[zero9178]

In D86974#2642100, @AndrewLitteken wrote:

Visual Studios Standard library starts their errors in lower case, which do not match the hardcoded values you used in your tests. Take a look at the lit feature added here https://reviews.llvm.org/rGc52fe0b02172e707aa2ba38cd2e01a1fc70dd0da, you should be able to use it to expand to the correct platform specific error message

Ah I see, that only applies to the second part of the error right? The first part (Could not open file) is LLVM generated I think.

Looks like it to me yes

[AndrewLitteken]

Updating message for the failure case where the file does not exist to be platform agnostic.

[AndrewLitteken]

I think with the generalization this should be good to try to land again?

[thakis]

This seems to break tests everywhere, eg http://45.33.8.238/linux/48721/step_12.txt

Please take a look and revert for now if it takes a while to fix.

[AndrewLitteken]

In D86974#2814286, @thakis wrote:

This seems to break tests everywhere, eg http://45.33.8.238/linux/48721/step_12.txt

Please take a look and revert for now if it takes a while to fix.

Is this build on the buildbot site? Or do you have any insights how to fix it? It seems related to the gn build system, which I don't have any experience with.

llvm/test/tools/llvm-sim/Inputs/sim1.ll

+define void @similar_func1() {
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %c = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  store i32 4, i32* %c, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %cl = load i32, i32* %c
+  ret void
+}
+
+define void @similar_func2() {
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %c = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  store i32 4, i32* %c, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %cl = load i32, i32* %c
+  ret void
+}

llvm/test/tools/llvm-sim/fail-cases.test

+# RUN: not llvm-sim %s 2>&1 | FileCheck %s
+# RUN: not llvm-sim %s.2 2>&1 | FileCheck %s -check-prefix=EXIST
+
+# File reading error messaging tests.
+
+# CHECK: error: expected top-level entity
+
+# EXIST: error: Could not open input file: No such file or directory

llvm/test/tools/llvm-sim/single-sim-file.test

+# RUN: llvm-sim -o %t %S/Inputs/sim1.ll
+# RUN: cat %t | FileCheck %s
+
+# Checking the output of a single module test.
+
+# CHECK: {
+# CHECK-NEXT:  "1": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 8,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 18,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "2": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 7,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 17,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "3": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 6,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 16,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "4": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 5,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 15,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "5": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 4,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 14,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ]
+# CHECK-NEXT: }

llvm/test/tools/llvm-sim/single-sim.test

+# RUN: llvm-sim -o - %S/Inputs/sim1.ll | FileCheck %s
+
+# Checking the output of a single module test.
+
+# CHECK: {
+# CHECK-NEXT:  "1": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 8,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 18,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "2": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 7,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 17,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "3": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 6,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 16,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "4": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 5,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 15,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ],
+# CHECK-NEXT:  "5": [
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 4,
+# CHECK-NEXT:    "end": 9
+# CHECK-NEXT:   },
+# CHECK-NEXT:   {
+# CHECK-NEXT:    "start": 14,
+# CHECK-NEXT:    "end": 19
+# CHECK-NEXT:   }
+# CHECK-NEXT:  ]
+# CHECK-NEXT: }

llvm/tools/LLVMBuild.txt

  llvm-nm
  llvm-objcopy
  llvm-objdump
  llvm-pdbutil
  llvm-profdata
  llvm-rc
  llvm-reduce
  llvm-rtdyld
+ llvm-sim
  llvm-size
  llvm-split
  llvm-undname
  opt
  verify-uselistorder
 
 [component_0]
 type = Group
 name = Tools
 parent = $ROOT

llvm/tools/llvm-sim/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS core support object coverage AsmParser IRReader TransformUtils ipo)
+
+add_llvm_tool(llvm-sim
+  llvm-sim.cpp
+)

llvm/tools/llvm-sim/LLVMBuild.txt

+;===- ./tools/llvm-sim/LLVMBuild.txt ---------------------------*- Conf -*--===;
+;
+; Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+; See https://llvm.org/LICENSE.txt for license information.
+; SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Tool
+name = llvm-sim
+parent = Tools
+required_libraries = Core Support AsmParser IRReader IPO

llvm/tools/llvm-sim/llvm-sim.cpp

+//===-- llvm-sim.cpp - Find  similar sections of programs -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This program finds similar sections of a Module, and exports them as a JSON
+// file.
+//
+// To find similarities contained across multiple modules, please use llvm-link
+// first to merge the modules.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/IRSimilarityIdentifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/JSON.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/ToolOutputFile.h"
+
+using namespace llvm;
+using namespace IRSimilarity;
+
+static cl::opt<std::string> OutputFilename("o", cl::desc("Output Filename"),
+                                           cl::init("-"),
+                                           cl::value_desc("filename"));
+
+static cl::opt<std::string> InputSourceFile(cl::Positional,
+                                            cl::desc("<Source file>"),
+                                            cl::init("-"),
+                                            cl::value_desc("filename"));
+
+/// Retrieve the unique number \p I was mapped to in parseBitcodeFile.
+///
+/// \param I - The Instruction to find the instruction number for.
+/// \param LLVMInstNum - The mapping of Instructions to their location in the
+/// module represented by an unsigned integer.
+/// \returns The instruction number for \p I if it exists.
+Optional<unsigned>
+getPositionInModule(const Instruction *I,
+                    const DenseMap<Instruction *, unsigned> &LLVMInstNum) {
+  assert(I && "Instruction is nullptr!");
+  DenseMap<Instruction *, unsigned>::const_iterator It = LLVMInstNum.find(I);
+  if (It == LLVMInstNum.end())
+    return None;
+  return It->second;
+}
+
+/// Exports the given SimilarityGroups to a JSON file at \p FilePath.
+///
+/// \param FilePath - The path to the output location.
+/// \param SimSections - The similarity groups to process.
+/// \param LLVMInstNum - The mapping of Instructions to their location in the
+/// module represented by an unsigned integer.
+/// \returns A nonzero error code if there was a failure creating the file.
+std::error_code
+exportToFile(const StringRef FilePath,
+             const SimilarityGroupList &SimSections,
+             const DenseMap<Instruction *, unsigned> &LLVMInstNum) {
+  std::error_code EC;
+  std::unique_ptr<ToolOutputFile> Out(
+      new ToolOutputFile(FilePath, EC, sys::fs::OF_None));
+  if (EC)
+    return EC;
+
+  json::OStream J(Out->os(), 1);
+  J.objectBegin();
+
+  unsigned SimOption = 1;
+  // Process each list of SimilarityGroups organized by the Module.
+  for (const SimilarityGroup &G : SimSections) {
+    std::string SimOptionStr = std::to_string(SimOption);
+    J.attributeBegin(SimOptionStr);
+    J.arrayBegin();
+    // For each file there is a list of the range where the similarity
+    // exists.
+    for (const IRSimilarityCandidate &C : G) {
+      Optional<unsigned> Start =
+          getPositionInModule((*C.front()).Inst, LLVMInstNum);
+      Optional<unsigned> End =
+          getPositionInModule((*C.back()).Inst, LLVMInstNum);
+
+      assert(Start.hasValue() &&
+             "Could not find instruction number for first instruction");
+      assert(End.hasValue() &&
+             "Could not find instruction number for last instruction");
+
+      J.object([&] {
+        J.attribute("start", Start.getValue());
+        J.attribute("end", End.getValue());
+      });
+    }
+    J.arrayEnd();
+    J.attributeEnd();
+    SimOption++;
+  }
+  J.objectEnd();
+
+  Out->keep();
+
+  return EC;
+}
+
+int main(int argc, const char *argv[]) {
+  InitLLVM X(argc, argv);
+
+  cl::ParseCommandLineOptions(argc, argv, "LLVM IR Similarity Visualizer\n");
+
+  LLVMContext CurrContext;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> ModuleToAnalyze =
+      parseIRFile(InputSourceFile, Err, CurrContext);
+
+  if (!ModuleToAnalyze) {
+    Err.print(argv[0], errs());
+    return 1;
+  }
+
+  // Mapping from an Instruction pointer to its occurrence in a sequential
+  // list of all the Instructions in a Module.
+  DenseMap<Instruction *, unsigned> LLVMInstNum;
+
+  // We give each instruction a number, which gives us a start and end value
+  // for the beginning and end of each IRSimilarityCandidate.
+  unsigned InstructionNumber = 1;
+  for (Function &F : *ModuleToAnalyze)
+    for (BasicBlock &BB : F)
+      for (Instruction &I : BB)
+        LLVMInstNum.insert(std::make_pair(&I, InstructionNumber++));
+
+  // The similarity identifier we will use to find the similar sections.
+  IRSimilarityIdentifier SimIdent;
+  SimilarityGroupList SimilaritySections =
+      SimIdent.findSimilarity(*ModuleToAnalyze);
+
+  std::error_code E =
+      exportToFile(OutputFilename, SimilaritySections, LLVMInstNum);
+  if (E) {
+    errs() << argv[0] << ": " << E.message() << '\n';
+    return 2;
+  }
+
+  return 0;
+}