[Bugpoint redesign] Added pass to reduce parameters

[diegotf]

Summary

This diff implements a pass to reduce uninteresting parameters. It also modifies function calls to fit the new function signature, additionally, the pass removes any AllocInst for out-of-chunk arguments.

[diegotf]

Re-ran clang-format

[diegotf]

Renamed extract function to extractArgumentsFromModule

[diegotf]

Updated diff & added python test

[diegotf]

Updated diff so it contains only changes to baseline

[dblaikie]

Having this pass remove AllocaInst too seems like it might be mixing responsibilities - presumably another pass might be invented to remove these AllocaInst separately? (& then it could get otherAllocaInst, other than just the ones used for parameters - like ones used for locals)

[dblaikie]

llvm/test/Reduce/remove-args.ll

13–42

Some comments describing what purpose each part of this IR covers would be good - I probably wouldn't expect 'printf' to be in this test - maybe that one is to test functions declared but not defined? Naming the function to indicate that and/or adding comments to describe it would be helpful. (similarly for the other functions - main+func+func2 - what purpose does each one serve?)

[diegotf]

In D65479#1630098, @dblaikie wrote:

Having this pass remove AllocaInst too seems like it might be mixing responsibilities - presumably another pass might be invented to remove these AllocaInst separately? (& then it could get otherAllocaInst, other than just the ones used for parameters - like ones used for locals)

Yeah, I agree. I'll upload another pass to take care of instructions, and that should cleanup the remaining AllocaInsts

llvm/test/Reduce/remove-args.ll

13–42

That is a great idea, I'll add some comments to clarify each part's purpose.

[diegotf]

Simplified test, and fixed oof-by-one error when replacing function calls

[diegotf]

Updated test so it pipes the reduction to FileCheck directly from STDOUT

llvm/docs/BugpointRedesign.md

+# Bugpoint Redesign
+Author: Diego Treviño ([e-mail])
+
+Date: 2019-06-05
+
+Status: Draft
+
+
+## Introduction
+As use of bugpoint has grown several areas of improvement have been identified
+through years of use: confusing to use, slow, it doesn’t always produce high
+quality test cases, etc. This document proposes a new approach with a narrower
+focus: minimization of IR test cases.
+
+
+## Proposed New Design
+
+
+### Narrow focus: test-case reduction
+The main focus will be a code reduction strategy to obtain much smaller test
+cases that still have the same property as the original one. This will be done
+via classic delta debugging and by adding some IR-specific reductions (e.g.
+replacing globals, removing unused instructions, etc), similar to what
+already exists, but with more in-depth minimization.
+
+
+Granted, if the community differs on this proposal, the legacy code could still
+be present in the tool, but with the caveat of still being documented and
+designed towards delta reduction.
+
+
+### Command-Line Options
+We are proposing to reduce the plethora of bugpoint’s options to just two: an
+interesting-ness test and the arguments for said test, similar to other delta
+reduction tools such as CReduce, Delta, and Lithium; the tool should feel less
+ cluttered, and there should also be no uncertainty about how to operate it.
+
+
+The interesting-ness test that’s going to be run to reduce the code is given
+by name:
+        `--test=<test_name>`
+If a `--test`  option is not given, the program exits; this option is similar
+to bugpoint’s current `-compile-custom` option, which lets the user run a
+custom script.
+
+
+The interesting-ness test would be defined as a script that returns 0 when the
+IR achieves a user-defined behaviour (e.g. failure to compile on clang) and a
+nonzero value when otherwise. Leaving the user the freedom to determine what is
+and isn’t interesting to the tool, and thus, streamlining the process of
+reducing a test-case.
+
+
+If the test accepts any arguments (excluding the input ll/bc file), they are
+given via the following flag:
+        `--test_args=<test_arguments>`
+If unspecified, the test is run as given. It’s worth noting that the input file
+would be passed as a parameter to the test, similar how `-compile-custom`
+currently operates.
+
+
+### Implementation
+The tool would behave similar to CReduce’s functionality in that it would have a
+list of passes that try to minimize the given test-case. We should be able to
+modularize the tool’s behavior, as well as making it easier to maintain and
+expand.
+
+
+The first version of this redesign would try to:
+
+
+* Discard functions, instructions and metadata that don’t influence the
+  interesting-ness test
+* Remove unused parameters from functions
+* Eliminate unvisited conditional paths
+* Rename variables to more regular ones (such as “a”, “b”, “c”, etc.)
+
+
+Once these passes are implemented, more meaningful reductions (such as type
+reduction) would be added to the tool, to even further reduce IR.
+
+
+## Background on historical bugpoint issues
+
+
+### Root Cause Analysis
+Presently, bugpoint takes a long time to find the source problem in a given IR
+file, mainly due to the fact that it tries to debug the input by running
+various strategies to classify the bug, which in turn run multiple optimizer
+and compilation passes over the input, taking up a lot of time. Furthermore,
+when the IR crashes, it tries to reduce it by performing some sub-optimal
+passes (e.g. a lot of unreachable blocks), and sometimes even fails to minimize
+at all.
+
+
+### "Quirky" Interface
+Bugpoint’s current interface overwhelms and confuses the user, the help screen
+alone ends up confusing rather providing guidance, as seen below:
+
+![Bugpoint's help option showcase](https://lh6.googleusercontent.com/sbpaSVHzpVVZKKAgHL9gvfzTWdgh3ju0KiDYql6WmWZfDYrdauOJMcuo9PP_V1dq8JQfMHOSKTv3lJcSpVytUyU8r5tJ2KTlGB0b2ve7jsZ3nVX8K8ItAbsA0JWkFKw67VJnq99m)
+
+And, not only are there numerous features and options, but some of them also
+work in unexpected ways and most of the time the user ends up using a custom
+script. Pruning and simplifying the interface will be worth considering in
+order to make the tool more useful in the general case and easier to maintain.

llvm/test/CMakeLists.txt

set(LLVM_TEST_DEPENDS
           llvm-opt-fuzzer
           llvm-opt-report
           llvm-pdbutil
           llvm-profdata
           llvm-ranlib
           llvm-rc
           llvm-readobj
           llvm-readelf
+          llvm-reduce
           llvm-rtdyld
           llvm-size
           llvm-split
           llvm-strings
           llvm-strip
           llvm-symbolizer
           llvm-tblgen
           llvm-undname

llvm/test/Reduce/Inputs/remove-args.py

+#!/usr/bin/env python
+
+import sys
+
+UsedArgumentPresent = False
+# So ReduceFunctions pass doesn't remove anything
+FunctionCount = 0
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "%used" in line:
+    UsedArgumentPresent = True
+  if "define" in line:
+    FunctionCount += 1
+
+if UsedArgumentPresent and FunctionCount == 3:
+  sys.exit(0) # Interesting!
+else:
+  sys.exit(1)

llvm/test/Reduce/Inputs/remove-funcs.py

+#!/usr/bin/env python
+
+import sys
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "@interesting" in line:
+    sys.exit(0)
+
+sys.exit(1) # IR isn't interesting

llvm/test/Reduce/Inputs/remove-global-vars.py

+#!/usr/bin/env python
+
+import sys
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "@interesting = global" in line:
+    sys.exit(0)
+
+sys.exit(1) # IR isn't interesting

llvm/test/Reduce/Inputs/remove-metadata.py

+#!/usr/bin/env python
+
+import sys
+
+NamedNodePresent = False
+DebugFunctionPresent = False
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "!llvm.module.flags" in line:
+    NamedNodePresent = True
+  if "@llvm.dbg.interesting" in line:
+    DebugFunctionPresent = True
+
+if NamedNodePresent and DebugFunctionPresent:
+  sys.exit(0) # interesting!
+else:
+  sys.exit(1)

llvm/test/Reduce/remove-args.ll

+; Test that llvm-reduce can remove uninteresting function arguments from function definitions as well as their calls.
+; Note: This pass also removes InstAllocs of uninteresting args
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-args.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+@x = global i32 0, align 4
+
+; CHECK: %used
+; CHECK-NOT: %unused
+define void @func(i32* dereferenceable(4) %used, i32 %unused, i32* dereferenceable(4) %unused2) {
+entry:
+  %used.addr = alloca i32*, align 8
+  %unused.addr = alloca i32, align 4
+  %unused2.addr = alloca i32*, align 8
+  store i32* %used, i32** %used.addr, align 8
+  store i32 %unused, i32* %unused.addr, align 4
+  store i32* %unused2, i32** %unused2.addr, align 8
+  %0 = load i32*, i32** %used.addr, align 8
+  store i32 10, i32* %0, align 4
+  ret void
+}
+
+define i32 @func2(i32 %unused) {
+entry:
+  %unused.addr = alloca i32, align 4
+  store i32 %unused, i32* %unused.addr, align 4
+  ret i32 0
+}
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  ; CHECK: call void @func(i32* @x)
+  call void @func(i32* dereferenceable(4) @x, i32 15, i32* dereferenceable(4) @x)
+  ; CHECK: call i32 @func2()
+  %call = call i32 @func2(i32 5)
+  ret i32 0
+}
+
+declare i32 @printf(i8*, ...)

llvm/test/Reduce/remove-funcs.ll

+; Test that llvm-reduce can remove uninteresting functions as well as
+; their InstCalls.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-funcs.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+; CHECK-NOT: uninteresting1()
+define i32 @uninteresting1() {
+entry:
+  ret i32 0
+}
+
+; CHECK: interesting()
+define i32 @interesting() {
+entry:
+  ; CHECK: call i32 @interesting()
+  %call2 = call i32 @interesting()
+  ; CHECK-NOT: call i32 @uninteresting1()
+  %call = call i32 @uninteresting1()
+  ret i32 5
+}
+
+; CHECK-NOT: uninteresting2()
+define i32 @uninteresting2() {
+entry:
+  ret i32 0
+}
+
+; CHECK-NOT: uninteresting3()
+define i32 @uninteresting3() {
+entry:
+  ret i32 10
+}

llvm/test/Reduce/remove-global-vars.ll

+; Test that llvm-reduce can remove uninteresting Global Variables as well as
+; their direct uses.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-global-vars.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+@uninteresting1 = global i32 0, align 4
+; CHECK: @interesting = global
+@interesting = global i32 5, align 4
+; CHECK-NOT: global
+@uninteresting2 = global i32 25, align 4
+@uninteresting3 = global i32 50, align 4
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting2, align 4
+  %0 = load i32, i32* @uninteresting2, align 4
+  store i32 %0, i32* @interesting, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting3, align 4
+  %1 = load i32, i32* @uninteresting3, align 4
+  %dec = add nsw i32 %1, -1
+  ; CHECK-NOT: store i32 %dec, i32* @uninteresting3, align 4
+  store i32 %dec, i32* @uninteresting3, align 4
+  ; CHECK: load i32, i32* @interesting, align 4
+  %2 = load i32, i32* @interesting, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting2, align 4
+  %3 = load i32, i32* @uninteresting2, align 4
+  %add = add nsw i32 %2, %3
+  ; CHECK-NOT: store i32 %add, i32* @uninteresting1, align 4
+  store i32 %add, i32* @uninteresting1, align 4
+  store i32 10, i32* @interesting, align 4
+  ; CHECK: load i32, i32* @interesting, align 4
+  %4 = load i32, i32* @interesting, align 4
+  ret i32 0
+}

llvm/test/Reduce/remove-metadata.ll

+; Test that llvm-reduce can remove uninteresting metadata from an IR file.
+; The Metadata pass erases named & unnamed metadata nodes, as well as debug functions.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-metadata.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+; CHECK: @llvm.dbg.interesting
+declare void @llvm.dbg.interesting(metadata %0, metadata %1, metadata %2)
+declare void @llvm.dbg.uninteresting(metadata %0, metadata %1, metadata %2)
+
+; CHECK-NOT: !dbg
+@x = dso_local global i32 0, align 4, !dbg !0
+
+define dso_local i32 @main() !dbg !13 {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  store i32 10, i32* @x, align 4, !dbg !16
+  %0 = load i32, i32* @x, align 4, !dbg !17
+  %sub = sub nsw i32 %0, 5, !dbg !18
+  %1 = load i32, i32* @x, align 4, !dbg !19
+  ret i32 0, !dbg !20
+}
+
+; CHECK: !llvm.module.flags
+; CHECK-NOT: !llvm.
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!9, !10, !11}
+!llvm.ident = !{!12}
+
+; Since we're only keeping !llvm.module.flags, there should only be 3 unnamed
+; nodes, and due to numbering !3 should not exist.
+; CHECK-NOT: !3
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "x", scope: !2, file: !3, line: 3, type: !8, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang version 9.0.0 (https://github.com/llvm/llvm-project.git ff0a72129a3e97bf7fddca38688808cd4f4e8f7b)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: None)
+!3 = !DIFile(filename: "ints.cpp", directory: "")
+!4 = !{}
+!5 = !{!0, !6}
+!6 = !DIGlobalVariableExpression(var: !7, expr: !DIExpression())
+!7 = distinct !DIGlobalVariable(name: "y", scope: !2, file: !3, line: 4, type: !8, isLocal: false, isDefinition: true)
+!8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!9 = !{i32 2, !"Dwarf Version", i32 4}
+!10 = !{i32 2, !"Debug Info Version", i32 3}
+!11 = !{i32 1, !"wchar_size", i32 4}
+!12 = !{!"clang version 9.0.0 (https://github.com/llvm/llvm-project.git ff0a72129a3e97bf7fddca38688808cd4f4e8f7b)"}
+!13 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 10, type: !14, scopeLine: 10, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !4)
+!14 = !DISubroutineType(types: !15)
+!15 = !{!8}
+!16 = !DILocation(line: 11, column: 5, scope: !13)
+!17 = !DILocation(line: 12, column: 7, scope: !13)
+!18 = !DILocation(line: 12, column: 9, scope: !13)
+!19 = !DILocation(line: 13, column: 18, scope: !13)
+!20 = !DILocation(line: 14, column: 3, scope: !13)

llvm/tools/LLVMBuild.txt

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

llvm/tools/llvm-reduce/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmParsers
+  AllTargetsCodeGens
+  AllTargetsDescs
+  AllTargetsInfos
+  IRReader
+  Support
+  Target
+  TransformUtils
+  )
+
+# Support plugins.
+set(LLVM_NO_DEAD_STRIP 1)
+
+add_llvm_tool(llvm-reduce
+  llvm-reduce.cpp
+  TestRunner.cpp
+  deltas/Delta.cpp
+  deltas/ReduceFunctions.cpp
+  deltas/ReduceGlobalVars.cpp
+  deltas/ReduceMetadata.cpp
+  deltas/ReduceArguments.cpp
+
+  DEPENDS
+  intrinsics_gen
+  )
+export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

+//===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===//
+//
+// 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 file calls each specialized Delta pass in order to reduce the input IR
+// file.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+#include "deltas/Delta.h"
+#include "deltas/ReduceArguments.h"
+#include "deltas/ReduceFunctions.h"
+#include "deltas/ReduceGlobalVars.h"
+#include "deltas/ReduceMetadata.h"
+
+namespace llvm {
+
+// TODO: Add CLI option to run only specified Passes (for unit tests)
+inline void runDeltaPasses(TestRunner &Tester) {
+  reduceFunctionsDeltaPass(Tester);
+  reduceGlobalsDeltaPass(Tester);
+  reduceMetadataDeltaPass(Tester);
+  reduceArgumentsDeltaPass(Tester);
+  // TODO: Implement the remaining Delta Passes
+}
+
+} // namespace llvm

llvm/tools/llvm-reduce/LLVMBuild.txt

-;===- ./tools/LLVMBuild.txt ------------------------------------*- Conf -*--===;
+;===- ./tools/llvm-reduce/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
 ;
 ;===------------------------------------------------------------------------===;
 
-[common]
-subdirectories =
- bugpoint
- dsymutil
- llc
- lli
- llvm-ar
- llvm-as
- llvm-bcanalyzer
- llvm-cat
- llvm-cfi-verify
- llvm-cov
- llvm-cvtres
- llvm-diff
- llvm-dis
- llvm-dwarfdump
- llvm-dwp
- llvm-elfabi
- llvm-exegesis
- llvm-extract
- llvm-jitlistener
- llvm-jitlink
- llvm-link
- llvm-lto
- llvm-mc
- llvm-mca
- llvm-modextract
- llvm-mt
- llvm-nm
- llvm-objcopy
- llvm-objdump
- llvm-pdbutil
- llvm-profdata
- llvm-rc
- llvm-rtdyld
- llvm-size
- llvm-split
- llvm-undname
- opt
- verify-uselistorder
-
 [component_0]
-type = Group
-name = Tools
-parent = $ROOT
+type = Tool
+name = llvm-reduce
+parent = Tools
+required_libraries =
+ BitReader
+ IRReader
+ all-targets

llvm/tools/llvm-reduce/TestRunner.h

+//===-- tools/llvm-reduce/TestRunner.h ---------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
+#define LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
+
+#include "llvm/ADT/SmallString.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Program.h"
+#include <vector>
+
+namespace llvm {
+
+// This class contains all the info necessary for running the provided
+// interesting-ness test, as well as the most reduced module and its
+// respective filename.
+class TestRunner {
+public:
+  TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
+             StringRef ReducedFilepath);
+
+  /// Runs the interesting-ness test for the specified file
+  /// @returns 0 if test was successful, 1 if otherwise
+  int run(StringRef Filename);
+
+  /// Filename to the most reduced testcase
+  StringRef getReducedFilepath() const { return ReducedFilepath; }
+  /// Directory where tmp files are created
+  StringRef getTmpDir() const { return TmpDirectory; }
+  /// Returns the most reduced version of the original testcase
+  Module *getProgram() const { return Program.get(); }
+
+  void setReducedFilepath(SmallString<128> F) {
+    ReducedFilepath = std::move(F);
+  }
+  void setProgram(std::unique_ptr<Module> P) { Program = std::move(P); }
+
+private:
+  SmallString<128> TestName;
+  std::vector<std::string> TestArgs;
+  SmallString<128> ReducedFilepath;
+  SmallString<128> TmpDirectory;
+  std::unique_ptr<Module> Program;
+};
+
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/TestRunner.cpp

+//===-- TestRunner.cpp ----------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+
+using namespace llvm;
+
+/// Gets Current Working Directory and tries to create a Tmp Directory
+static SmallString<128> initializeTmpDirectory() {
+  SmallString<128> CWD;
+  if (std::error_code EC = sys::fs::current_path(CWD)) {
+    errs() << "Error getting current directory: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  SmallString<128> TmpDirectory;
+  sys::path::append(TmpDirectory, CWD, "tmp");
+  if (std::error_code EC = sys::fs::create_directory(TmpDirectory))
+    errs() << "Error creating tmp directory: " << EC.message() << "!\n";
+
+  return TmpDirectory;
+}
+
+TestRunner::TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
+                       StringRef ReducedFilepath)
+    : TestName(TestName), TestArgs(std::move(TestArgs)),
+      ReducedFilepath(ReducedFilepath) {
+  TmpDirectory = initializeTmpDirectory();
+}
+
+/// Runs the interestingness test, passes file to be tested as first argument
+/// and other specified test arguments after that.
+int TestRunner::run(StringRef Filename) {
+  std::vector<StringRef> ProgramArgs;
+  ProgramArgs.push_back(TestName);
+  ProgramArgs.push_back(Filename);
+
+  for (auto Arg : TestArgs)
+    ProgramArgs.push_back(Arg.c_str());
+
+  Optional<StringRef> Redirects[3]; // STDIN, STDOUT, STDERR
+  int Result = sys::ExecuteAndWait(TestName, ProgramArgs, None, Redirects);
+
+  if (Result < 0) {
+    Error E = make_error<StringError>("Error running interesting-ness test\n",
+                                      inconvertibleErrorCode());
+    outs() << toString(std::move(E));
+    exit(1);
+  }
+
+  return !Result;
+}

llvm/tools/llvm-reduce/deltas/Delta.h

+//===- Delta.h - Delta Debugging Algorithm Implementation -----------------===//
+//
+// 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 file contains the implementation for the Delta Debugging Algorithm:
+// it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
+// into chunks and tries to reduce the number chunks that are interesting.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
+#define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
+
+#include "../TestRunner.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include <fstream>
+#include <set>
+#include <vector>
+
+using namespace llvm;
+
+struct Chunk {
+  unsigned begin;
+  unsigned end;
+
+  /// Helper function to verify if a given Target-index is inside the Chunk
+  bool contains(unsigned Index) const { return Index >= begin && Index <= end; }
+
+  void print() const {
+    outs() << "[" << begin;
+    if (end - begin != 0)
+      outs() << "," << end;
+    outs() << "]";
+  }
+
+  /// Operator when populating CurrentChunks in Generic Delta Pass
+  friend bool operator!=(const Chunk &C1, const Chunk &C2) {
+    return C1.begin != C2.begin || C1.end != C2.end;
+  }
+
+  /// Operator used for sets
+  friend bool operator<(const Chunk &C1, const Chunk &C2) {
+    return std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end);
+  }
+};
+
+namespace llvm {
+
+/// This function implements the Delta Debugging algorithm, it receives a
+/// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
+/// splits them in half; these chunks of targets are then tested while ignoring
+/// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
+/// it is removed from consideration. The algorithm will attempt to split the
+/// Chunks in half and start the process again until it can't split chunks
+/// anymore.
+///
+/// This function is intended to be called by each specialized delta pass (e.g.
+/// RemoveFunctions) and receives three key parameters:
+/// * Test: The main TestRunner instance which is used to run the provided
+/// interesting-ness test, as well as to store and access the reduced Program.
+/// * Targets: The amount of Targets that are going to be reduced by the
+/// algorithm, for example, the RemoveGlobalVars pass would send the amount of
+/// initialized GVs.
+/// * ExtractChunksFromModule: A function used to tailor the main program so it
+/// only contains Targets that are inside Chunks of the given iteration.
+/// Note: This function is implemented by each specialized Delta pass
+///
+/// Other implementations of the Delta Debugging algorithm can also be found in
+/// the CReduce, Delta, and Lithium projects.
+void runDeltaPass(TestRunner &Test, unsigned Targets,
+                  std::function<void(const std::vector<Chunk> &, Module *)>
+                      ExtractChunksFromModule);
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/deltas/Delta.cpp

+//===- Delta.cpp - Delta Debugging Algorithm Implementation ---------------===//
+//
+// 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 file contains the implementation for the Delta Debugging Algorithm:
+// it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
+// into chunks and tries to reduce the number chunks that are interesting.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/ADT/STLExtras.h"
+
+/// Writes IR code to the given Filepath
+static bool writeProgramToFile(StringRef Filepath, int FD, const Module &M) {
+  ToolOutputFile Out(Filepath, FD);
+  M.print(Out.os(), /*AnnotationWriter=*/nullptr);
+  Out.os().close();
+
+  if (!Out.os().has_error()) {
+    Out.keep();
+    return false;
+  }
+  return true;
+}
+
+/// Creates a temporary (and unique) file inside the tmp folder and writes
+/// the given module IR.
+static SmallString<128> createTmpFile(Module *M, StringRef TmpDir) {
+  SmallString<128> UniqueFilepath;
+  int UniqueFD;
+
+  SmallString<128> TmpFilepath;
+  sys::path::append(TmpFilepath, TmpDir, "tmp-%%%.ll");
+  std::error_code EC =
+      sys::fs::createUniqueFile(TmpFilepath, UniqueFD, UniqueFilepath);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  if (writeProgramToFile(UniqueFilepath, UniqueFD, *M)) {
+    errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n";
+    exit(1);
+  }
+  return UniqueFilepath;
+}
+
+/// Prints the Chunk Indexes with the following format: [start, end], if
+/// chunk is at minimum size (1), then it just displays [start].
+static void printChunks(std::vector<Chunk> Chunks, bool Oneline = false) {
+  if (Chunks.empty()) {
+    outs() << "No Chunks";
+    return;
+  }
+
+  for (auto C : Chunks) {
+    if (!Oneline)
+      outs() << '\t';
+    C.print();
+    if (!Oneline)
+      outs() << '\n';
+  }
+}
+
+/// Counts the amount of lines for a given file
+static unsigned getLines(StringRef Filepath) {
+  unsigned Lines = 0;
+  std::string CurrLine;
+  std::ifstream FileStream(Filepath);
+
+  while (std::getline(FileStream, CurrLine))
+    ++Lines;
+
+  return Lines;
+}
+
+/// Splits Chunks in half and prints them.
+/// If unable to split (when chunk size is 1) returns false.
+static bool increaseGranularity(std::vector<Chunk> &Chunks) {
+  outs() << "Increasing granularity...";
+  std::vector<Chunk> NewChunks;
+  bool SplitOne = false;
+
+  for (auto &C : Chunks) {
+    if (C.end - C.begin == 0)
+      NewChunks.push_back(C);
+    else {
+      unsigned Half = (C.begin + C.end) / 2;
+      NewChunks.push_back({C.begin, Half});
+      NewChunks.push_back({Half + 1, C.end});
+      SplitOne = true;
+    }
+  }
+  if (SplitOne) {
+    Chunks = NewChunks;
+    outs() << "Success! New Chunks:\n";
+    printChunks(Chunks);
+  }
+  return SplitOne;
+}
+
+/// Runs the Delta Debugging algorithm, splits the code into chunks and
+/// reduces the amount of chunks that are considered interesting by the
+/// given test.
+void llvm::runDeltaPass(
+    TestRunner &Test, unsigned Targets,
+    std::function<void(const std::vector<Chunk> &, Module *)>
+        ExtractChunksFromModule) {
+  if (!Targets) {
+    outs() << "\nNothing to reduce\n";
+    return;
+  }
+  if (!Test.run(Test.getReducedFilepath())) {
+    outs() << "\nInput isn't interesting! Verify interesting-ness test\n";
+    return;
+  }
+
+  std::vector<Chunk> Chunks = {{1, Targets}};
+  std::set<Chunk> UninterestingChunks;
+  std::unique_ptr<Module> ReducedProgram;
+
+  if (!increaseGranularity(Chunks)) {
+    outs() << "\nAlready at minimum size. Cannot reduce anymore.\n";
+    return;
+  }
+
+  do {
+    UninterestingChunks = {};
+    for (int I = Chunks.size() - 1; I >= 0; --I) {
+      std::vector<Chunk> CurrentChunks;
+
+      for (auto C : Chunks)
+        if (!UninterestingChunks.count(C) && C != Chunks[I])
+          CurrentChunks.push_back(C);
+
+      if (CurrentChunks.empty())
+        continue;
+
+      // Clone module before hacking it up..
+      std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram());
+      // Generate Module with only Targets inside Current Chunks
+      ExtractChunksFromModule(CurrentChunks, Clone.get());
+      // Write Module to tmp file
+      SmallString<128> CurrentFilepath =
+          createTmpFile(Clone.get(), Test.getTmpDir());
+
+      outs() << "Testing with: ";
+      printChunks(CurrentChunks, /*Oneline=*/true);
+      outs() << " | " << sys::path::filename(CurrentFilepath);
+
+      // Current Chunks aren't interesting
+      if (!Test.run(CurrentFilepath)) {
+        outs() << "\n";
+        continue;
+      }
+
+      UninterestingChunks.insert(Chunks[I]);
+      Test.setReducedFilepath(CurrentFilepath);
+      ReducedProgram = std::move(Clone);
+      outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
+    }
+    // Delete uninteresting chunks
+    erase_if(Chunks, [&UninterestingChunks](const Chunk &C) {
+      return UninterestingChunks.count(C);
+    });
+
+  } while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
+
+  // If we reduced the testcase replace it
+  if (ReducedProgram)
+    Test.setProgram(std::move(ReducedProgram));
+  outs() << "Couldn't increase anymore.\n";
+}
 No newline at end of file

llvm/tools/llvm-reduce/deltas/ReduceArguments.h

+//===- ReduceArguments.h - Specialized Delta Pass -------------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting Arguments from defined functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/IR/Argument.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceArgumentsDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceArguments.cpp

+//===- ReduceArguments.cpp - Specialized Delta Pass -----------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting Arguments from defined functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceArguments.h"
+
+/// Goes over OldF calls and replaces them with a call to NewF
+static void replaceFunctionCalls(Function *OldF, Function *NewF,
+                                 const std::set<int> &ArgIndexesToKeep) {
+  for (auto U : OldF->users())
+    if (auto *CI = dyn_cast<CallInst>(*&U)) {
+      SmallVector<Value *, 8> Args;
+      for (auto ArgI = CI->arg_begin(), E = CI->arg_end(); ArgI != E; ++ArgI)
+        if (ArgIndexesToKeep.count(ArgI - CI->arg_begin()))
+          Args.push_back(*ArgI);
+
+      CallInst *NewCI = CallInst::Create(NewF, Args);
+      NewCI->setCallingConv(NewF->getCallingConv());
+      if (!CI->use_empty())
+        CI->replaceAllUsesWith(NewCI);
+      ReplaceInstWithInst(CI, NewCI);
+    }
+}
+
+/// Deletes allocation instructions of arguments that are deleted
+static void removeUnusedAllocas(Function *F,
+                                const std::set<int> &ArgIndexesToKeep) {
+  std::vector<AllocaInst *> ToDelete;
+  int AllocaCount = 0;
+  for (auto &BB : *F)
+    for (auto &I : BB)
+      if (auto *AI = dyn_cast<AllocaInst>(&I))
+        if (!ArgIndexesToKeep.count(AllocaCount++))
+          ToDelete.push_back(AI);
+
+  for (auto &AI : ToDelete) {
+    AI->replaceAllUsesWith(UndefValue::get(AI->getType()));
+    AI->eraseFromParent();
+  }
+}
+
+/// Removes out-of-chunk arguments from functions, and modifies their calls
+/// accordingly. It also removes allocations of out-of-chunk arguments.
+/// @returns the Module stripped of out-of-chunk functions
+static void extractArgumentsFromModule(std::vector<Chunk> ChunksToKeep,
+                                       Module *Program) {
+  unsigned I = 0, ArgCount = 0;
+  std::set<Argument *> ArgsToKeep;
+  std::vector<Function *> Funcs;
+  // Get inside-chunk arguments, as well as their parent function
+  for (auto &F : *Program)
+    if (!F.isDeclaration()) {
+      Funcs.push_back(&F);
+      for (auto &A : F.args())
+        if (I < ChunksToKeep.size()) {
+          if (ChunksToKeep[I].contains(++ArgCount))
+            ArgsToKeep.insert(&A);
+          if (ChunksToKeep[I].end == ArgCount)
+            ++I;
+        }
+    }
+
+  for (auto &F : Funcs) {
+    ValueToValueMapTy VMap;
+    std::vector<Instruction *> InstToDelete;
+    for (auto &A : F->args())
+      if (!ArgsToKeep.count(&A)) {
+        // By adding undesired arguments to the VMap, CloneFunction will remove
+        // them from the resulting Function
+        VMap[&A] = UndefValue::get(A.getType());
+        for (auto U : A.users())
+          if (auto *I = dyn_cast<Instruction>(*&U))
+            InstToDelete.push_back(I);
+      }
+    // Delete any instruction that uses the argument
+    for (auto I : InstToDelete) {
+      I->replaceAllUsesWith(UndefValue::get(I->getType()));
+      I->eraseFromParent();
+    }
+
+    // No arguments to reduce
+    if (VMap.empty())
+      continue;
+
+    std::set<int> ArgIndexesToKeep;
+    int ArgI = 0;
+    for (auto &Arg : F->args())
+      if (ArgsToKeep.count(&Arg))
+        ArgIndexesToKeep.insert(ArgI++);
+
+    auto *ClonedFunc = CloneFunction(F, VMap);
+    // In order to preserve function order, we move Clone after old Function
+    ClonedFunc->removeFromParent();
+    Program->getFunctionList().insertAfter(F->getIterator(), ClonedFunc);
+
+    replaceFunctionCalls(F, ClonedFunc, ArgIndexesToKeep);
+    removeUnusedAllocas(ClonedFunc, ArgIndexesToKeep);
+    // Rename Cloned Function to Old's name
+    auto FName = F->getName();
+    F->eraseFromParent();
+    ClonedFunc->setName(FName);
+  }
+}
+
+/// Counts the amount of arguments in non-declaration functions and prints their
+/// respective name, index, and parent function name
+static int countArguments(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "Param Index Reference:\n";
+  int ArgsCount = 0;
+  for (auto &F : *Program)
+    if (!F.isDeclaration() && F.arg_size()) {
+      outs() << "  " << F.getName() << "\n";
+      for (auto &P : F.args())
+        outs() << "\t" << ++ArgsCount << ": " << P.getName() << "\n";
+
+      outs() << "----------------------------\n";
+    }
+
+  return ArgsCount;
+}
+
+void llvm::reduceArgumentsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Arguments...\n";
+  unsigned ArgCount = countArguments(Test.getProgram());
+  runDeltaPass(Test, ArgCount, extractArgumentsFromModule);
+}

llvm/tools/llvm-reduce/deltas/ReduceFunctions.h

+//===- ReduceFunctions.h - Specialized Delta Pass -------------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce functions (and any instruction that calls it) in the provided
+// Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceFunctionsDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp

+//===- ReduceFunctions.cpp - Specialized Delta Pass -----------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce functions (and any instruction that calls it) in the provided
+// Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceFunctions.h"
+
+/// Removes all the Defined Functions (as well as their calls)
+/// that aren't inside any of the desired Chunks.
+/// @returns the Module stripped of out-of-chunk functions
+static void extractFunctionsFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                       Module *Program) {
+  // Get functions inside desired chunks
+  std::set<Function *> FuncsToKeep;
+  unsigned I = 0, FunctionCount = 0;
+  for (auto &F : *Program)
+    if (!F.isDeclaration() && I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(++FunctionCount))
+        FuncsToKeep.insert(&F);
+      if (FunctionCount == ChunksToKeep[I].end)
+        ++I;
+    }
+
+  // Delete out-of-chunk functions, and replace their calls with undef
+  std::vector<Function *> FuncsToRemove;
+  for (auto &F : *Program)
+    if (!F.isDeclaration() && !FuncsToKeep.count(&F)) {
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      FuncsToRemove.push_back(&F);
+    }
+
+  for (auto *F : FuncsToRemove)
+    F->eraseFromParent();
+
+  // Delete instructions with undef calls
+  std::vector<Instruction *> InstToRemove;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &I : BB)
+        if (auto *Call = dyn_cast<CallInst>(&I))
+          if (!Call->getCalledFunction()) {
+            // Instruction might be stored / used somewhere else
+            I.replaceAllUsesWith(UndefValue::get(I.getType()));
+            InstToRemove.push_back(&I);
+          }
+
+  for (auto *I : InstToRemove)
+    I->eraseFromParent();
+}
+
+/// Counts the amount of non-declaration functions and prints their
+/// respective name & index
+static unsigned countDefinedFunctions(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "Function Index Reference:\n";
+  unsigned FunctionCount = 0;
+  for (auto &F : *Program)
+    if (!F.isDeclaration())
+      outs() << "\t" << ++FunctionCount << ": " << F.getName() << "\n";
+
+  outs() << "----------------------------\n";
+  return FunctionCount;
+}
+
+void llvm::reduceFunctionsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Functions...\n";
+  unsigned Functions = countDefinedFunctions(Test.getProgram());
+  runDeltaPass(Test, Functions, extractFunctionsFromModule);
+  outs() << "----------------------------\n";
+}
 No newline at end of file

llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.h

+//===- ReduceGlobalVars.h - Specialized Delta Pass ------------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce initialized Global Variables in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceGlobalsDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp

+//===- ReduceGlobalVars.cpp - Specialized Delta Pass ----------------------===//
+//
+// 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 file implements a function which calls the Generic Delta pass in order
+// to reduce initialized Global Variables in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceGlobalVars.h"
+
+/// Removes all the Initialized GVs that aren't inside the desired Chunks.
+/// @returns the Module stripped of out-of-chunk GVs
+static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
+                                 Module *Program) {
+  // Get GVs inside desired chunks
+  std::set<GlobalVariable *> GVsToKeep;
+  unsigned I = 0, GVCount = 0;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer() && I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(++GVCount))
+        GVsToKeep.insert(&GV);
+      if (GVCount == ChunksToKeep[I].end)
+        ++I;
+    }
+
+  // Delete out-of-chunk GVs and their uses
+  std::vector<GlobalVariable *> ToRemove;
+  std::vector<Instruction *> InstToRemove;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer() && !GVsToKeep.count(&GV)) {
+      for (auto U : GV.users())
+        if (auto *Inst = dyn_cast<Instruction>(U))
+          InstToRemove.push_back(Inst);
+
+      GV.replaceAllUsesWith(UndefValue::get(GV.getType()));
+      ToRemove.push_back(&GV);
+    }
+
+  // Delete Instruction uses of unwanted GVs
+  for (auto *Inst : InstToRemove) {
+    Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
+    Inst->eraseFromParent();
+  }
+
+  for (auto *GV : ToRemove)
+    GV->eraseFromParent();
+}
+
+/// Counts the amount of initialized GVs and displays their
+/// respective name & index
+static int countGVs(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "GlobalVariable Index Reference:\n";
+  int GVCount = 0;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer())
+      outs() << "\t" << ++GVCount << ": " << GV.getName() << "\n";
+  outs() << "----------------------------\n";
+  return GVCount;
+}
+
+void llvm::reduceGlobalsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing GVs...\n";
+  unsigned GVCount = countGVs(Test.getProgram());
+  runDeltaPass(Test, GVCount, extractGVsFromModule);
+}

llvm/tools/llvm-reduce/deltas/ReduceMetadata.h

+//===- ReduceMetadata.h - Specialized Delta Pass ------------------------===//
+//
+// 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 file implements two functions used by the Generic Delta Debugging
+// Algorithm, which are used to reduce Metadata tags, as well as debug
+// functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include <set>
+#include <vector>
+
+namespace llvm {
+void reduceMetadataDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp

+//===- ReduceMetadata.cpp - Specialized Delta Pass ------------------------===//
+//
+// 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 file implements two functions used by the Generic Delta Debugging
+// Algorithm, which are used to reduce Metadata tags, as well as debug
+// functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceMetadata.h"
+
+/// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set
+template <class T>
+static void getChunkMetadataNodes(T *MDUser, unsigned &I,
+                                  const std::vector<Chunk> &ChunksToKeep,
+                                  std::set<MDNode *> &SeenNodes,
+                                  std::set<MDNode *> &NodesToKeep) {
+  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
+  MDUser->getAllMetadata(MDs);
+  for (auto &MD : MDs) {
+    SeenNodes.insert(MD.second);
+    if (I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(SeenNodes.size()))
+        NodesToKeep.insert(MD.second);
+      if (ChunksToKeep[I].end == SeenNodes.size())
+        ++I;
+    }
+  }
+}
+
+/// Erases out-of-chunk unnamed metadata nodes from its user
+template <class T>
+static void eraseMetadataIfOutsideChunk(T *MDUser,
+                                        const std::set<MDNode *> &NodesToKeep) {
+  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
+  MDUser->getAllMetadata(MDs);
+  for (int I = 0, E = MDs.size(); I != E; ++I)
+    if (!NodesToKeep.count(MDs[I].second))
+      MDUser->setMetadata(I, NULL);
+}
+
+/// Erases function and its instruction users. It also replaces the latter with
+/// "undef"
+static void deleteFunctionAndCallers(Function *F) {
+  for (auto U : F->users()) {
+    U->replaceAllUsesWith(UndefValue::get(U->getType()));
+    if (auto *Inst = dyn_cast<Instruction>(U))
+      Inst->eraseFromParent();
+  }
+  F->eraseFromParent();
+}
+
+/// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
+/// functions that aren't inside the desired Chunks.
+/// @returns the Module stripped of out-of-chunk MDNodes
+static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                      Module *Program) {
+  std::set<MDNode *> SeenNodes;
+  std::set<MDNode *> NodesToKeep;
+  unsigned I = 0;
+
+  // Add chunk MDNodes used by GVs, Functions, and Instructions to set
+  for (auto &GV : Program->globals())
+    getChunkMetadataNodes(&GV, I, ChunksToKeep, SeenNodes, NodesToKeep);
+
+  for (auto &F : *Program) {
+    getChunkMetadataNodes(&F, I, ChunksToKeep, SeenNodes, NodesToKeep);
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        getChunkMetadataNodes(&Inst, I, ChunksToKeep, SeenNodes, NodesToKeep);
+  }
+
+  // Once more, go over metadata nodes, but deleting the ones outside chunks
+  for (auto &GV : Program->globals())
+    eraseMetadataIfOutsideChunk(&GV, NodesToKeep);
+
+  // And keeping a list of debug functions
+  std::vector<Function *> DebugFuncs;
+  for (auto &F : *Program) {
+    if (F.getName().startswith("llvm."))
+      DebugFuncs.push_back(&F);
+    else
+      eraseMetadataIfOutsideChunk(&F, NodesToKeep);
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        eraseMetadataIfOutsideChunk(&Inst, NodesToKeep);
+  }
+
+  // Go over debug functions and erase the ones out-of-chunk
+  unsigned MetadataCount = SeenNodes.size();
+  for (auto F : DebugFuncs) {
+    if (I < ChunksToKeep.size()) {
+      if (!ChunksToKeep[I].contains(++MetadataCount))
+        deleteFunctionAndCallers(F);
+      if (ChunksToKeep[I].end == MetadataCount)
+        ++I;
+    } else
+      deleteFunctionAndCallers(F);
+  }
+
+  std::vector<NamedMDNode *> NamedNodesToDelete;
+
+  // Get out-of-chunk Named metadata nodes
+  for (auto &MD : Program->named_metadata()) {
+    ++MetadataCount;
+    if (I < ChunksToKeep.size()) {
+      if (!ChunksToKeep[I].contains(MetadataCount))
+        NamedNodesToDelete.push_back(&MD);
+      if (ChunksToKeep[I].end == SeenNodes.size())
+        ++I;
+    } else
+      NamedNodesToDelete.push_back(&MD);
+  }
+
+  for (auto NN : NamedNodesToDelete) {
+    for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
+      NN->setOperand(I, NULL);
+    NN->eraseFromParent();
+  }
+}
+
+// Gets unnamed metadata nodes used by a given instruction/GV/function and adds
+// them to the set of seen nodes
+template <class T>
+static void addMetadataToSet(T *MDUser, std::set<MDNode *> &UnnamedNodes) {
+  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
+  MDUser->getAllMetadata(MDs);
+  for (auto &MD : MDs)
+    UnnamedNodes.insert(MD.second);
+}
+
+/// Returns the amount of Named and Unnamed Metadata Nodes, and Debug functions
+/// used in the module
+static unsigned countMetadataTargets(Module *Program) {
+  std::set<MDNode *> UnnamedNodes;
+  int NamedMetadataNodes = Program->named_metadata_size();
+  int DebugFunctionsCount = 0;
+
+  // Get metadata nodes used by globals
+  for (auto &GV : Program->globals())
+    addMetadataToSet(&GV, UnnamedNodes);
+
+  // Do the same for nodes used by functions & instructions
+  for (auto &F : *Program) {
+    if (F.getName().startswith("llvm."))
+      ++DebugFunctionsCount;
+    addMetadataToSet(&F, UnnamedNodes);
+    for (auto &BB : F)
+      for (auto &I : BB)
+        addMetadataToSet(&I, UnnamedNodes);
+  }
+
+  return UnnamedNodes.size() + NamedMetadataNodes + DebugFunctionsCount;
+}
+
+void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Metadata...\n";
+  unsigned MDCount = countMetadataTargets(Test.getProgram());
+  runDeltaPass(Test, MDCount, extractMetadataFromModule);
+  outs() << "----------------------------\n";
+}

llvm/tools/llvm-reduce/llvm-reduce.cpp

+//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
+//
+// 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 tries to reduce an IR test case for a given interesting-ness
+// test. It runs multiple delta debugging passes in order to minimize the input
+// file. It's worth noting that this is a part of the bugpoint redesign
+// proposal, and thus a *temporary* tool that will eventually be integrated
+// into the bugpoint tool itself.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DeltaManager.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/raw_ostream.h"
+#include <system_error>
+#include <vector>
+
+using namespace llvm;
+
+static cl::opt<bool> Help("h", cl::desc("Alias for -help"), cl::Hidden);
+static cl::opt<bool> Version("v", cl::desc("Alias for -version"), cl::Hidden);
+
+static cl::opt<std::string> InputFilename(cl::Positional, cl::Required,
+                                          cl::desc("<input llvm ll/bc file>"));
+
+static cl::opt<std::string>
+    TestFilename("test", cl::Required,
+                 cl::desc("Name of the interesting-ness test to be run"));
+
+static cl::list<std::string>
+    TestArguments("test-arg", cl::ZeroOrMore,
+                  cl::desc("Arguments passed onto the interesting-ness test"));
+
+static cl::opt<std::string>
+    OutputFilename("output",
+                   cl::desc("Specify the output file. default: reduced.ll"));
+static cl::alias OutputFileAlias("o", cl::desc("Alias for -output"),
+                                 cl::aliasopt(OutputFilename));
+
+static cl::opt<bool>
+    ReplaceInput("in-place",
+                 cl::desc("WARNING: This option will replace your input file"
+                          "with the reduced version!"));
+
+// Parses IR into a Module and verifies it
+static std::unique_ptr<Module> parseInputFile(StringRef Filename,
+                                              LLVMContext &Ctxt) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
+  if (!Result) {
+    Err.print("llvm-reduce", errs());
+    return Result;
+  }
+
+  if (verifyModule(*Result, &errs())) {
+    errs() << "Error: " << Filename << " - input module is broken!\n";
+    return std::unique_ptr<Module>();
+  }
+
+  return Result;
+}
+
+int main(int argc, char **argv) {
+  InitLLVM X(argc, argv);
+
+  cl::ParseCommandLineOptions(argc, argv, "LLVM automatic testcase reducer.\n");
+
+  LLVMContext Context;
+  std::unique_ptr<Module> OriginalProgram =
+      parseInputFile(InputFilename, Context);
+
+  // Initialize test environment
+  TestRunner Tester(TestFilename, TestArguments, InputFilename);
+  Tester.setProgram(std::move(OriginalProgram));
+
+  // Try to reduce code
+  runDeltaPasses(Tester);
+  StringRef ReducedFilename = sys::path::filename(Tester.getReducedFilepath());
+
+  if (ReducedFilename == sys::path::filename(InputFilename)) {
+    outs() << "\nCouldnt reduce input :/\n";
+  } else {
+    if (ReplaceInput) // In-place
+      OutputFilename = InputFilename.c_str();
+    else if (OutputFilename.empty())
+      OutputFilename = "reduced.ll";
+    else
+      OutputFilename += ".ll";
+
+    sys::fs::copy_file(Tester.getReducedFilepath(), OutputFilename);
+    outs() << "\nDone reducing! Reduced IR to file: " << OutputFilename << "\n";
+  }
+
+  return 0;
+}