[Bugpoint redesign] Added Pass to Remove Global Variables

[diegotf]

Summary

This pass tries to remove Global Variables as well as their direct uses, for example if a given GV @x is deemed uninteresting and it's used by %call and %call2. Both the GV as well as its calls would be deleted (any uses of the calls would be replaced with undef)

Depends on D63672

[fhahn]

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

2

file name needs updating I think

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

2

file name needs updating I think

[diegotf]

Fixed top-level comments to fit actual filename & description.

Reworded doxygen comment on eraseDerivedUsers

[diegotf]

Changed commit so it only has changes made to parent diff (D63672)

[dblaikie]

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

9–15

Might be stronger to:

CHECK-NOT: "global" on either side of the "CHECK: @interesting = global"

That way it'd be resilient to any reordering, for instance (where you could silently pass the test if LLVM IR happened to print 2, 3, unnumbered, 1)

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

54

Is the indentation off here? (clang-format can be handy to clean up stuff like this)

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

24–32

Classes to group static functions are somewhat to be avoided, I think - should this be a helper namespace, or maybe leaving the functions in the 'llvm' namespace while making the names more specific?

[diegotf]

Fixed out-of-range bug on specialized passes when getting Targets

Refactored removal of uninteresting chunks in Delta.h, since erasing them whilst iterating crashed when last Chunk was erased

Re-ran clang-format

[diegotf]

Refactored Delta Debugging Algorithm from a template class to an inline function in LLVM namespace; the specialized behaviour called by the generic Delta pass is given as parameters to the function instead of being given as a class template and then called statically in order to reduce confusion.

Note: Specialized Delta passes are also now inline functions instead of classes that groupped static functions.

[diegotf]

Re-worded header comments to fit new implementation

[diegotf]

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

9–15

Good catch! I hadn't thought of that.

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

24–32

I've refactored the Generic Delta pass in order to avoid this problem. I believe it's also simpler and easier to read.

[dblaikie]

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

24–25

(non-member) Static functions aren't appropriate in header files (they lead to code size increases and ODR violations).

You could move these into some sort of implementation namespace (llvm::impl or something like that) or I guess they could be stateless lambdas - or moved out-of-line into a .cpp file instead. (moving the removeGlobalsDeltaPass definition out of line so it can refer to the implementation functions in the .cpp file (where those functions can/should be 'static' in that case))

[diegotf]

Moved Delta pass function definitions from header to cpp files in order to avoid ODR violations.

[dblaikie]

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

67

This 'inline' keyword probably needs to be removed. I'm surprised if this code links as-is (or compiles - some sort of warning/error like this:

inl.cpp:1:13: warning: inline function 'f' is not defined [-Wundefined-inline]
inline void f();

^

inl.cpp:3:3: note: used here

f();
^

[diegotf]

Removed inline keyword from function declarations (since it's defined out-of-line)

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

67

Yeah, I goofed up and uploaded a wrong commit

[diegotf]

Added license & file header to cpp files

[diegotf]

Changed Pass behavior so it doesnt delete derived uses anymore.

[diegotf]

Re-added behavior to delete direct uses opf GVs (accidentally deleted)

[diegotf]

Remove Metadata pass from DeltaManager.h and CMakeLists.txt

[diegotf]

Update diff so it only show changes made to D63672

[diegotf]

Changed GV unit test to fit to a more targeted interesting-ness test

[diegotf]

Changed it to show only changes to D63672

[dblaikie]

hmm, hard to review - the baseline review (D63672) seems inconsistent with the API usage here - so I'm not sure what's authoritative, which design changes have been discussed/finalized, etc..

[diegotf]

In D64176#1619418, @dblaikie wrote:

hmm, hard to review - the baseline review (D63672) seems inconsistent with the API usage here - so I'm not sure what's authoritative, which design changes have been discussed/finalized, etc..

I'll update this (and the child diffs) to fit the changes in baseline

[diegotf]

Formatting changes & added llvm-reduce as dependency to tests

[diegotf]

Update diff to reflect changes on baseline & moved interesting-ness test to python

[diegotf]

General Formatting

[dblaikie]

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

9–15

seems good to have it on both sides (CHECK-NOT before and after the CHECK @interesting).

19–33

Should these CHECK-NOTs also have some CHECKs that demonstrate what these have been transformed into? (showing the undefs appear)

Also - are there differences between uninteresting1/2/3 that's interesting/important to testing here, or could there be similar test coverage with 1 uninteresting/removed global?

[dblaikie]

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

123–126

This change appears independent of the rest of this patch - if that's the case, please commit it separately. (no need to send it for review if it's nothing too interesting - if it's just reducing the scope of variables as is generally good)

[diegotf]

Simplified test & added check to verify that direct uses are replaced with undef

[diegotf]

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

19–33

Agreed, i'll add the checks. And yeah, uninteresting 2&3 might be overkill. I'll update the test accordingly

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

123–126

I'll move it to another then :)

[dblaikie]

Looks good - thanks (:

[diegotf]

Re-ran clang-format

[xbolva00]

Surprisingly test remove-global-vars.ll fails on buildbot

http://lab.llvm.org:8011/builders/lld-x86_64-ubuntu-fast/builds/4649

Previous build was OK and this test case worked.

Either this testcase is unstable or something was miscompiled after
[X86] Add custom type legalization for bitcasting mmx to v2i32/v4i16/v8i8 to use movq2dq instead of going through memory.

cc @craig.topper

[xbolva00]

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

6

This looks weird

[diegotf]

Patch here: D66314

[diegotf]

Changed test so reduced version is printed to STDOUT

[xbolva00]

Hi,

Bots warn;
srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp:17:6: warning: '@returns' command used in a comment that is attached to a function returning void [-Wdocumentation]
1 warning generated.

Can you fix this small issue? Thanks

[dblaikie]

In D64176#1634377, @xbolva00 wrote:

Hi,

Bots warn;
srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp:17:6: warning: '@returns' command used in a comment that is attached to a function returning void [-Wdocumentation]
1 warning generated.

Can you fix this small issue? Thanks

@bkramer fixed this in r369848 - thanks Ben!

llvm/test/Reduce/Inputs/interestingness-test.sh

 #!/bin/sh
 
 # lli is passed as a test-arg so lit can recognize it
 ret=$($2 $1)
 
 if [[ $ret = 10 ]]; then
   exit 0
 else
   exit 1
 fi

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.sh --test-arg %lli %s
+; RUN: llvm-reduce --test %p/Inputs/interestingness-test.sh --test-arg %lli %s
 ; RUN: cat reduced.ll | FileCheck %s
 ; REQUIRES: plugins, shell
 
 @.str = private unnamed_addr constant [4 x i8] c"%i\0A\00", align 1
 
 ; CHECK-NOT: uninteresting1()
 define i32 @uninteresting1() {
 entry:

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

+; Test that llvm-reduce can remove uninteresting Global Variables as well as
+; their uses (both direct and derived).
+;
+; RUN: llvm-reduce --test %p/Inputs/interestingness-test.sh --test-arg %lli %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins, shell
+
+@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
+@.str = private unnamed_addr constant [4 x i8] c"%i\0A\00", align 1
+
+define void @func(i32* dereferenceable(4) %x) {
+entry:
+  %x.addr = alloca i32*, align 8
+  store i32* %x, i32** %x.addr, align 8
+  %0 = load i32*, i32** %x.addr, align 8
+  %1 = load i32, i32* %0, align 4
+  %inc = add nsw i32 %1, 1
+  store i32 %inc, i32* %0, align 4
+  ret void
+}
+
+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
+  ; CHECK: store i32 10, i32* @interesting, align 4
+  store i32 10, i32* @interesting, align 4
+  ; CHECK-NOT: call void @func(i32* dereferenceable(4) @uninteresting1)
+  call void @func(i32* dereferenceable(4) @uninteresting1)
+  %4 = load i32, i32* @interesting, align 4
+  %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4)
+  ret i32 0
+}
+
+declare i32 @printf(i8*, ...)

llvm/tools/llvm-reduce/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   )
 
 # Support plugins.
 set(LLVM_NO_DEAD_STRIP 1)
 
 add_llvm_tool(llvm-reduce
   llvm-reduce.cpp
   TestRunner.cpp
-  deltas/RemoveFunctions.cpp
-  deltas/RemoveGlobals.cpp
 
   DEPENDS
   intrinsics_gen
   )
 export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

-//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
+//===- 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 class calls each specialized Delta pass by passing it as a template to
-// the generic Delta Pass.
+// This file calls each specialized Delta pass in order to reduce the input IR
+// file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/RemoveFunctions.h"
-#include "deltas/RemoveGlobals.h"
+#include "deltas/RemoveGlobalVars.h"
+#include "deltas/RemoveMetadata.h"
 
 namespace llvm {
 
 inline void runDeltaPasses(TestRunner &Tester) {
+  // TODO: Add option to only call certain delta passes
   outs() << "Reducing functions...\n";
-  Delta<RemoveFunctions>::run(Tester);
-  // TODO: Implement the rest of the Delta Passes
+  removeFunctionsDeltaPass(Tester);
+  outs() << "Reducing GVs...\n";
+  removeGlobalsDeltaPass(Tester);
+  // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

llvm/tools/llvm-reduce/TestRunner.h

-//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
+//===-- 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

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;
 
 TestRunner::TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
                        StringRef ReducedFilepath, SmallString<128> TmpDirectory)
     : TestName(TestName), TestArgs(TestArgs), ReducedFilepath(ReducedFilepath),
       TmpDirectory(TmpDirectory) {}

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

-//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
+//===- 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:
struct Chunk {
   }
 
   /// Operator used for sets
   friend bool operator<(const Chunk &C1, const Chunk &C2) {
     return C1.begin < C2.begin;
   }
 };
 
-/// Writes IR code to the given Filepath
-inline 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 outputs
-/// the module inside it.
-inline SmallString<128> createTmpFile(Module *M, StringRef TmpDir) {
-  SmallString<128> UniqueFilepath;
-  int UniqueFD;
-
-  std::error_code EC = sys::fs::createUniqueFile(TmpDir + "/tmp-%%%.ll",
-                                                 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].
-inline void printChunks(std::vector<Chunk> Chunks, bool Oneline = false) {
-  for (auto C : Chunks) {
-    if (!Oneline)
-      outs() << '\t';
-    outs() << "[" << C.begin;
-    if (C.end - C.begin != 0)
-      outs() << "," << C.end;
-    outs() << "]";
-    if (!Oneline)
-      outs() << '\n';
-  }
-}
-
-/// Counts the amount of lines for a given file
-inline 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.
-inline 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 {
-      int 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;
-}
-
 namespace llvm {
 
-/// This class implements the Delta Debugging algorithm, it receives a set 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. Otherwise, the algorithm will attempt to split
-/// the Chunks in half and start the process again, until it can't split chunks
+/// 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.
 ///
-/// The class is intended to be called statically by the DeltaManager class
-/// alongside a specialized delta pass (e.g. RemoveFunctions) passed as a
-/// template.
-/// This specialized pass implements two functions:
-///   * getTargetCount, which returns the amount of targets (e.g. Functions)
-///     there are in the Module.
-///   * extractChunksFromModule, which clones the given Module and modifies it
-///     so it only contains Chunk Targets.
+/// 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 be found in the
-/// CReduce, Delta, and Lithium projects.
-template <class P> class Delta {
-public:
-  /// Runs the Delta Debugging algorithm, splits the code into chunks and
-  /// reduces the amount of chunks that are considered interesting by the
-  /// given test.
-  static void run(TestRunner &Test) {
-    int TargetCount = P::getTargetCount(Test.getProgram());
-    std::vector<Chunk> Chunks = {{1, TargetCount}};
-    std::set<Chunk> UninterestingChunks;
-    std::unique_ptr<Module> ReducedProgram;
-
-    if (Test.run(Test.getReducedFilepath()))
-      increaseGranularity(Chunks);
-    else {
-      outs() << "Error: input file isnt interesting\n";
-      exit(1);
-    }
-
-    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);
-
-        // Generate Module with only Targets inside Current Chunks
-        std::unique_ptr<Module> CurrentProgram =
-            P::extractChunksFromModule(CurrentChunks, Test.getProgram());
-        // Write Module to tmp file
-        SmallString<128> CurrentFilepath =
-            createTmpFile(CurrentProgram.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;
-        }
-        // We only care about interesting chunks if they reduce the testcase
-        if (getLines(CurrentFilepath) < getLines(Test.getReducedFilepath())) {
-          UninterestingChunks.insert(Chunks[I]);
-          Test.setReducedFilepath(CurrentFilepath);
-          ReducedProgram = std::move(CurrentProgram);
-          outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath);
-        }
-        outs() << "\n";
-      }
-      // Delete uninteresting chunks
-      auto It = Chunks.begin(), E = Chunks.end();
-      while (It != E) {
-        if (UninterestingChunks.count(*It))
-          It = Chunks.erase(It);
-        else
-          ++It;
-      }
-    } 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";
-  }
-};
+/// Other implementations of the Delta Debugging algorithm can also be found in
+/// the CReduce, Delta, and Lithium projects.
+inline void runDeltaPass(
+    TestRunner &Test, int Targets,
+    std::function<std::unique_ptr<Module>(std::vector<Chunk>, Module *)>
+        ExtractChunksFromModule);
 
 } // namespace llvm
 
 #endif

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

+#include "Delta.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;
+
+  std::error_code EC = sys::fs::createUniqueFile(TmpDir + "/tmp-%%%.ll",
+                                                 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) {
+  for (auto C : Chunks) {
+    if (!Oneline)
+      outs() << '\t';
+    outs() << "[" << C.begin;
+    if (C.end - C.begin != 0)
+      outs() << "," << C.end;
+    outs() << "]";
+    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 {
+      int 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;
+}
+
+void runDeltaPass(
+    TestRunner &Test, int Targets,
+    std::function<std::unique_ptr<Module>(std::vector<Chunk>, Module *)>
+        ExtractChunksFromModule) {
+  if (!Targets)
+    return;
+
+  std::vector<Chunk> Chunks = {{1, Targets}};
+  std::set<Chunk> UninterestingChunks;
+  std::unique_ptr<Module> ReducedProgram;
+
+  if (!Test.run(Test.getReducedFilepath()) || !increaseGranularity(Chunks)) {
+    outs() << "\nCouldn't reduce\n";
+    outs() << "----------------------------\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())
+        break;
+
+      // Generate Module with only Targets inside Current Chunks
+      std::unique_ptr<Module> CurrentProgram =
+          ExtractChunksFromModule(CurrentChunks, Test.getProgram());
+      // Write Module to tmp file
+      SmallString<128> CurrentFilepath =
+          createTmpFile(CurrentProgram.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;
+      }
+      // We only care about interesting chunks if they reduce the testcase
+      if (getLines(CurrentFilepath) < getLines(Test.getReducedFilepath())) {
+        UninterestingChunks.insert(Chunks[I]);
+        Test.setReducedFilepath(CurrentFilepath);
+        ReducedProgram = std::move(CurrentProgram);
+        outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath);
+      }
+      outs() << "\n";
+    }
+    // Delete uninteresting chunks
+    auto UnwantedChunks = Chunks.end();
+    UnwantedChunks = std::remove_if(Chunks.begin(), Chunks.end(),
+                                    [UninterestingChunks](const Chunk &C) {
+                                      return UninterestingChunks.count(C);
+                                    });
+    Chunks.erase(UnwantedChunks, Chunks.end());
+
+  } 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";
+  outs() << "----------------------------\n";
+}
 No newline at end of file

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

-//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
+//===- RemoveFunctions.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 is a Specialized Delta Pass, which removes the functions that are
-// not in the provided function-chunks.
+// 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 {
-
-class RemoveFunctions {
-public:
-  /// Outputs the number of Functions in the given Module
-  static int getTargetCount(Module *Program);
-  /// Clones module and returns it with chunk functions only
-  static std::unique_ptr<Module>
-  extractChunksFromModule(std::vector<Chunk> ChunksToKeep, Module *Program);
-};
-
+inline void removeFunctionsDeltaPass(TestRunner &Test);
 } // namespace llvm

llvm/tools/llvm-reduce/deltas/RemoveFunctions.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 file is a Specialized Delta Pass, which removes the functions that are
-// not in the provided function-chunks.
-//
-//===----------------------------------------------------------------------===//
-
 #include "RemoveFunctions.h"
 
 using namespace llvm;
 
 /// 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
-std::unique_ptr<Module>
-RemoveFunctions::extractChunksFromModule(std::vector<Chunk> ChunksToKeep,
-                                         Module *Program) {
+static std::unique_ptr<Module>
+extractFunctionsFromModule(std::vector<Chunk> ChunksToKeep, Module *Program) {
   std::unique_ptr<Module> Clone = CloneModule(*Program);
 
   // Get functions inside desired chunks
   std::set<Function *> FuncsToKeep;
   int I = 0, FunctionCount = 1;
   for (auto &F : *Clone) {
-    if (!F.isDeclaration()) {
+    if (!F.isDeclaration() && I < ChunksToKeep.size()) {
       if (FunctionCount >= ChunksToKeep[I].begin &&
-          FunctionCount <= ChunksToKeep[I].end) {
+          FunctionCount <= ChunksToKeep[I].end)
         FuncsToKeep.insert(&F);
-      }
-      if (FunctionCount >= ChunksToKeep[I].end)
+      if (FunctionCount == ChunksToKeep[I].end)
         ++I;
       ++FunctionCount;
     }
   }
 
   // Delete out-of-chunk functions, and replace their calls with undef
   std::vector<Function *> FuncsToRemove;
   for (auto &F : *Clone) {
extractFunctionsFromModule(std::vector<Chunk> ChunksToKeep, Module *Program) {
 
   for (auto *I : InstToRemove)
     I->eraseFromParent();
 
   return Clone;
 }
 
 /// Counts the amount of non-declaration functions and prints their
-/// respective index & name
-int RemoveFunctions::getTargetCount(Module *Program) {
+/// respective name & index
+static int countFunctions(Module *Program) {
   // TODO: Silence index with --quiet flag
   outs() << "----------------------------\n";
-  outs() << "Chunk Index Reference:\n";
+  outs() << "Function Index Reference:\n";
   int FunctionCount = 0;
   for (auto &F : *Program)
     if (!F.isDeclaration()) {
       ++FunctionCount;
       outs() << "\t" << FunctionCount << ": " << F.getName() << "\n";
     }
   outs() << "----------------------------\n";
   return FunctionCount;
 }
+
+void removeFunctionsDeltaPass(TestRunner &Test) {
+  int FunctionCount = countFunctions(Test.getProgram());
+  runDeltaPass(Test, FunctionCount, extractFunctionsFromModule);
+}
 No newline at end of file

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

+//===- RemoveGlobalVars.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, as well as any derived uses in the
+// provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+inline void removeGlobalsDeltaPass(TestRunner &Test);
+} // namespace llvm

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

+#include "RemoveGlobalVars.h"
+
+using namespace llvm;
+
+/// Goes over the users of a given instruction and erases them.
+/// For example, if @x is used by %call1 and %call2, both calls and the
+/// GV declaration would be erased. Moreover, if any of the calls are used
+/// elsewhere, those uses would be erased and so on recursively.
+static void eraseDerivedUsers(Instruction *Inst,
+                              std::set<Instruction *> &InstToRemove) {
+  if (!Inst->use_empty())
+    for (auto U : Inst->users())
+      if (auto *I = dyn_cast<Instruction>(U))
+        eraseDerivedUsers(I, InstToRemove);
+
+  InstToRemove.insert(Inst);
+  Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
+}
+
+/// Removes all the Initialized GVs (as well as their direct and indirect uses)
+/// that aren't inside the desired Chunks.
+/// @returns the Module stripped of out-of-chunk GVs
+static std::unique_ptr<Module>
+extractGVsFromModule(std::vector<Chunk> ChunksToKeep, Module *Program) {
+  std::unique_ptr<Module> Clone = CloneModule(*Program);
+
+  // Get GVs inside desired chunks
+  std::set<GlobalVariable *> GVsToKeep;
+  int I = 0, GVCount = 1;
+  for (auto &GV : Clone->globals()) {
+    if (GV.hasInitializer() && I < ChunksToKeep.size()) {
+      if (GVCount >= ChunksToKeep[I].begin && GVCount <= ChunksToKeep[I].end)
+        GVsToKeep.insert(&GV);
+      if (GVCount == ChunksToKeep[I].end)
+        ++I;
+      ++GVCount;
+    }
+  }
+
+  // Delete out-of-chunk GVs as well as their respective users
+  std::vector<GlobalVariable *> ToRemove;
+  std::set<Instruction *> InstToRemove;
+  for (auto &GV : Clone->globals()) {
+    if (GV.hasInitializer() && !GVsToKeep.count(&GV)) {
+      // Delete any instructions that use the GV, both direct and indirectly
+      for (auto U : GV.users())
+        if (auto *I = dyn_cast<Instruction>(U))
+          eraseDerivedUsers(I, InstToRemove);
+
+      GV.replaceAllUsesWith(UndefValue::get(GV.getType()));
+      ToRemove.push_back(&GV);
+    }
+  }
+  for (auto *GV : ToRemove)
+    GV->eraseFromParent();
+
+  for (auto *I : InstToRemove)
+    I->eraseFromParent();
+
+  return Clone;
+}
+
+/// 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()) {
+      ++GVCount;
+      outs() << "\t" << GVCount << ": " << GV.getName() << "\n";
+    }
+  outs() << "----------------------------\n";
+  return GVCount;
+}
+
+inline void removeGlobalsDeltaPass(TestRunner &Test) {
+  int GVCount = countGVs(Test.getProgram());
+  runDeltaPass(Test, GVCount, extractGVsFromModule);
+}
 No newline at end of file

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 *temporary* tool that will eventually
-// be integrated into the bugpoint tool itself.
+// 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"