vendor/llvm/llvm-trunk-r375505vendor/llvm

14 files changed, 982 insertions, 0 deletions

diff --git a/tools/llvm-reduce/deltas/Delta.cpp b/tools/llvm-reduce/deltas/Delta.cpp
new file mode 100644
index 0000000000000..0642241ddebd6
--- /dev/null
+++ b/tools/llvm-reduce/deltas/Delta.cpp
@@ -0,0 +1,162 @@
+//===- 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"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include <fstream>
+#include <set>
+
+using namespace llvm;
+
+bool IsReduced(Module &M, TestRunner &Test, SmallString<128> &CurrentFilepath) {
+  // Write Module to tmp file
+  int FD;
+  std::error_code EC =
+      sys::fs::createTemporaryFile("llvm-reduce", "ll", FD, CurrentFilepath);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  ToolOutputFile Out(CurrentFilepath, FD);
+  M.print(Out.os(), /*AnnotationWriter=*/nullptr);
+  Out.os().close();
+  if (Out.os().has_error()) {
+    errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n";
+    exit(1);
+  }
+
+  // Current Chunks aren't interesting
+  return Test.run(CurrentFilepath);
+}
+
+/// Counts the amount of lines for a given file
+static int getLines(StringRef Filepath) {
+  int 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) {
+  errs() << "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;
+    errs() << "Success! New Chunks:\n";
+    for (auto C : Chunks) {
+      errs() << '\t';
+      C.print();
+      errs() << '\n';
+    }
+  }
+  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, int Targets,
+    std::function<void(const std::vector<Chunk> &, Module *)>
+        ExtractChunksFromModule) {
+  assert(Targets >= 0);
+  if (!Targets) {
+    errs() << "\nNothing to reduce\n";
+    return;
+  }
+
+  if (Module *Program = Test.getProgram()) {
+    SmallString<128> CurrentFilepath;
+    if (!IsReduced(*Program, Test, CurrentFilepath)) {
+      errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
+      exit(1);
+    }
+  }
+
+  std::vector<Chunk> Chunks = {{1, Targets}};
+  std::set<Chunk> UninterestingChunks;
+  std::unique_ptr<Module> ReducedProgram;
+
+  if (!increaseGranularity(Chunks)) {
+    errs() << "\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());
+
+      errs() << "Ignoring: ";
+      Chunks[I].print();
+      for (auto C : UninterestingChunks)
+        C.print();
+
+
+
+      SmallString<128> CurrentFilepath;
+      if (!IsReduced(*Clone, Test, CurrentFilepath)) {
+        errs() << "\n";
+        continue;
+      }
+
+      UninterestingChunks.insert(Chunks[I]);
+      ReducedProgram = std::move(Clone);
+      errs() << " **** 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));
+  errs() << "Couldn't increase anymore.\n";
+}
diff --git a/tools/llvm-reduce/deltas/Delta.h b/tools/llvm-reduce/deltas/Delta.h
new file mode 100644
index 0000000000000..dbb18e4bd07fe
--- /dev/null
+++ b/tools/llvm-reduce/deltas/Delta.h
@@ -0,0 +1,76 @@
+//===- 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 <vector>
+#include <utility>
+#include <functional>
+
+namespace llvm {
+
+struct Chunk {
+  int begin;
+  int end;
+
+  /// Helper function to verify if a given Target-index is inside the Chunk
+  bool contains(int Index) const { return Index >= begin && Index <= end; }
+
+  void print() const {
+    errs() << "[" << begin;
+    if (end - begin != 0)
+      errs() << "," << end;
+    errs() << "]";
+  }
+
+  /// 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);
+  }
+};
+
+/// 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, int Targets,
+                  std::function<void(const std::vector<Chunk> &, Module *)>
+                      ExtractChunksFromModule);
+} // namespace llvm
+
+#endif
diff --git a/tools/llvm-reduce/deltas/ReduceArguments.cpp b/tools/llvm-reduce/deltas/ReduceArguments.cpp
new file mode 100644
index 0000000000000..f5f14b83f42cd
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceArguments.cpp
@@ -0,0 +1,125 @@
+//===- 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"
+#include "Delta.h"
+#include "llvm/ADT/SmallVector.h"
+#include <set>
+#include <vector>
+
+using namespace llvm;
+
+/// Goes over OldF calls and replaces them with a call to NewF
+static void replaceFunctionCalls(Function &OldF, Function &NewF,
+                                 const std::set<int> &ArgIndexesToKeep) {
+  const auto &Users = OldF.users();
+  for (auto I = Users.begin(), E = Users.end(); I != E; )
+    if (auto *CI = dyn_cast<CallInst>(*I++)) {
+      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);
+    }
+}
+
+/// Removes out-of-chunk arguments from functions, and modifies their calls
+/// accordingly. It also removes allocations of out-of-chunk arguments.
+static void extractArgumentsFromModule(std::vector<Chunk> ChunksToKeep,
+                                       Module *Program) {
+  int 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 < (int)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);
+    // Rename Cloned Function to Old's name
+    std::string 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 &A : F.args())
+        outs() << "\t" << ++ArgsCount << ": " << A.getName() << "\n";
+
+      outs() << "----------------------------\n";
+    }
+
+  return ArgsCount;
+}
+
+void llvm::reduceArgumentsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Arguments...\n";
+  int ArgCount = countArguments(Test.getProgram());
+  runDeltaPass(Test, ArgCount, extractArgumentsFromModule);
+}
diff --git a/tools/llvm-reduce/deltas/ReduceArguments.h b/tools/llvm-reduce/deltas/ReduceArguments.h
new file mode 100644
index 0000000000000..d9682b44f74d7
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceArguments.h
@@ -0,0 +1,21 @@
+//===- 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
diff --git a/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp b/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp
new file mode 100644
index 0000000000000..03c3962d2fd9d
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp
@@ -0,0 +1,146 @@
+//===- 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 "ReduceBasicBlocks.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/raw_ostream.h"
+#include <vector>
+
+using namespace llvm;
+
+/// Replaces BB Terminator with one that only contains Chunk BBs
+static void replaceBranchTerminator(BasicBlock &BB,
+                                    std::set<BasicBlock *> BBsToKeep) {
+  auto Term = BB.getTerminator();
+  std::vector<BasicBlock *> ChunkSucessors;
+  for (auto Succ : successors(&BB))
+    if (BBsToKeep.count(Succ))
+      ChunkSucessors.push_back(Succ);
+
+  // BB only references Chunk BBs
+  if (ChunkSucessors.size() == Term->getNumSuccessors())
+    return;
+
+  bool IsBranch = isa<BranchInst>(Term);
+  Value *Address = nullptr;
+  if (auto IndBI = dyn_cast<IndirectBrInst>(Term))
+    Address = IndBI->getAddress();
+
+  Term->eraseFromParent();
+
+  if (ChunkSucessors.empty()) {
+    ReturnInst::Create(BB.getContext(), nullptr, &BB);
+    return;
+  }
+
+  if (IsBranch)
+    BranchInst::Create(ChunkSucessors[0], &BB);
+
+  if (Address) {
+    auto NewIndBI =
+        IndirectBrInst::Create(Address, ChunkSucessors.size(), &BB);
+    for (auto Dest : ChunkSucessors)
+      NewIndBI->addDestination(Dest);
+  }
+}
+
+/// Removes uninteresting BBs from switch, if the default case ends up being
+/// uninteresting, the switch is replaced with a void return (since it has to be
+/// replace with something)
+static void removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
+                                             std::set<BasicBlock *> BBsToKeep) {
+  if (!BBsToKeep.count(SwInst.getDefaultDest())) {
+    ReturnInst::Create(SwInst.getContext(), nullptr, SwInst.getParent());
+    SwInst.eraseFromParent();
+  } else
+    for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
+      auto Case = SwInst.case_begin() + I;
+      if (!BBsToKeep.count(Case->getCaseSuccessor())) {
+        SwInst.removeCase(Case);
+        --I;
+        --E;
+      }
+    }
+}
+
+/// Removes out-of-chunk arguments from functions, and modifies their calls
+/// accordingly. It also removes allocations of out-of-chunk arguments.
+static void extractBasicBlocksFromModule(std::vector<Chunk> ChunksToKeep,
+                                         Module *Program) {
+  int I = 0, BBCount = 0;
+  std::set<BasicBlock *> BBsToKeep;
+
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      if (I < (int)ChunksToKeep.size()) {
+        if (ChunksToKeep[I].contains(++BBCount))
+          BBsToKeep.insert(&BB);
+        if (ChunksToKeep[I].end == BBCount)
+          ++I;
+      }
+
+  std::vector<BasicBlock *> BBsToDelete;
+  for (auto &F : *Program)
+    for (auto &BB : F) {
+      if (!BBsToKeep.count(&BB)) {
+        BBsToDelete.push_back(&BB);
+        // Remove out-of-chunk BB from successor phi nodes
+        for (auto *Succ : successors(&BB))
+          Succ->removePredecessor(&BB);
+      }
+    }
+
+  // Replace terminators that reference out-of-chunk BBs
+  for (auto &F : *Program)
+    for (auto &BB : F) {
+      if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
+        removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
+      else
+        replaceBranchTerminator(BB, BBsToKeep);
+    }
+
+  // Replace out-of-chunk switch uses
+  for (auto &BB : BBsToDelete) {
+    // Instructions might be referenced in other BBs
+    for (auto &I : *BB)
+      I.replaceAllUsesWith(UndefValue::get(I.getType()));
+    BB->eraseFromParent();
+  }
+}
+
+/// Counts the amount of basic blocks and prints their name & respective index
+static int countBasicBlocks(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  int BBCount = 0;
+  for (auto &F : *Program)
+    for (auto &BB : F) {
+      if (BB.hasName())
+        outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
+      else
+        outs() << "\t" << ++BBCount << ": Unnamed\n";
+    }
+
+  return BBCount;
+}
+
+void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Basic Blocks...\n";
+  int BBCount = countBasicBlocks(Test.getProgram());
+  runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
+}
diff --git a/tools/llvm-reduce/deltas/ReduceBasicBlocks.h b/tools/llvm-reduce/deltas/ReduceBasicBlocks.h
new file mode 100644
index 0000000000000..cf76a0abbcd7a
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceBasicBlocks.h
@@ -0,0 +1,20 @@
+//===- 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/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceBasicBlocksDeltaPass(TestRunner &Test);
+} // namespace llvm
diff --git a/tools/llvm-reduce/deltas/ReduceFunctions.cpp b/tools/llvm-reduce/deltas/ReduceFunctions.cpp
new file mode 100644
index 0000000000000..3382f35a945a4
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceFunctions.cpp
@@ -0,0 +1,77 @@
+//===- 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"
+#include "Delta.h"
+#include "llvm/ADT/SetVector.h"
+#include <set>
+
+using namespace llvm;
+
+/// Removes all the Defined Functions (as well as their calls)
+/// that aren't inside any of the desired Chunks.
+static void extractFunctionsFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                       Module *Program) {
+  // Get functions inside desired chunks
+  std::set<Function *> FuncsToKeep;
+  int I = 0, FunctionCount = 0;
+  for (auto &F : *Program)
+    if (I < (int)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;
+  SetVector<CallInst *> CallsToRemove;
+  for (auto &F : *Program)
+    if (!FuncsToKeep.count(&F)) {
+      for (auto U : F.users())
+        if (auto *Call = dyn_cast<CallInst>(U)) {
+          Call->replaceAllUsesWith(UndefValue::get(Call->getType()));
+          CallsToRemove.insert(Call);
+        }
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      FuncsToRemove.push_back(&F);
+    }
+
+  for (auto *C : CallsToRemove)
+    C->eraseFromParent();
+
+  for (auto *F : FuncsToRemove)
+    F->eraseFromParent();
+}
+
+/// Counts the amount of non-declaration functions and prints their
+/// respective name & index
+static int countFunctions(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  errs() << "----------------------------\n";
+  errs() << "Function Index Reference:\n";
+  int FunctionCount = 0;
+  for (auto &F : *Program)
+    errs() << "\t" << ++FunctionCount << ": " << F.getName() << "\n";
+
+  errs() << "----------------------------\n";
+  return FunctionCount;
+}
+
+void llvm::reduceFunctionsDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Functions...\n";
+  int Functions = countFunctions(Test.getProgram());
+  runDeltaPass(Test, Functions, extractFunctionsFromModule);
+  errs() << "----------------------------\n";
+}
diff --git a/tools/llvm-reduce/deltas/ReduceFunctions.h b/tools/llvm-reduce/deltas/ReduceFunctions.h
new file mode 100644
index 0000000000000..7c2cd3f33e9f2
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceFunctions.h
@@ -0,0 +1,20 @@
+//===- 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
diff --git a/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp b/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp
new file mode 100644
index 0000000000000..5732208ee0a96
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp
@@ -0,0 +1,74 @@
+//===- 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"
+#include <set>
+
+using namespace llvm;
+
+/// Removes all the Initialized GVs that aren't inside the desired Chunks.
+static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
+                                 Module *Program) {
+  // Get GVs inside desired chunks
+  std::set<GlobalVariable *> GVsToKeep;
+  int I = 0, GVCount = 0;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer() && I < (int)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";
+  int GVCount = countGVs(Test.getProgram());
+  runDeltaPass(Test, GVCount, extractGVsFromModule);
+}
diff --git a/tools/llvm-reduce/deltas/ReduceGlobalVars.h b/tools/llvm-reduce/deltas/ReduceGlobalVars.h
new file mode 100644
index 0000000000000..d4a870aded581
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceGlobalVars.h
@@ -0,0 +1,20 @@
+//===- 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
diff --git a/tools/llvm-reduce/deltas/ReduceInstructions.cpp b/tools/llvm-reduce/deltas/ReduceInstructions.cpp
new file mode 100644
index 0000000000000..b3497ad2dc02d
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceInstructions.cpp
@@ -0,0 +1,65 @@
+//===- 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 "ReduceInstructions.h"
+
+using namespace llvm;
+
+/// Removes out-of-chunk arguments from functions, and modifies their calls
+/// accordingly. It also removes allocations of out-of-chunk arguments.
+static void extractInstrFromModule(std::vector<Chunk> ChunksToKeep,
+                                   Module *Program) {
+  int I = 0, InstCount = 0;
+  std::set<Instruction *> InstToKeep;
+
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        if (I < (int)ChunksToKeep.size()) {
+          if (ChunksToKeep[I].contains(++InstCount))
+            InstToKeep.insert(&Inst);
+          if (ChunksToKeep[I].end == InstCount)
+            ++I;
+        }
+
+  std::vector<Instruction *> InstToDelete;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        if (!InstToKeep.count(&Inst)) {
+          Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
+          InstToDelete.push_back(&Inst);
+        }
+
+  for (auto &I : InstToDelete)
+    I->eraseFromParent();
+}
+
+/// Counts the amount of basic blocks and prints their name & respective index
+static unsigned countInstructions(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  int InstCount = 0;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+        InstCount += BB.getInstList().size();
+  outs() << "Number of instructions: " << InstCount << "\n";
+
+  return InstCount;
+}
+
+void llvm::reduceInstructionsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Insructions...\n";
+  unsigned InstCount = countInstructions(Test.getProgram());
+  runDeltaPass(Test, InstCount, extractInstrFromModule);
+}
diff --git a/tools/llvm-reduce/deltas/ReduceInstructions.h b/tools/llvm-reduce/deltas/ReduceInstructions.h
new file mode 100644
index 0000000000000..a9266acd051a3
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceInstructions.h
@@ -0,0 +1,20 @@
+//===- 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/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceInstructionsDeltaPass(TestRunner &Test);
+} // namespace llvm
diff --git a/tools/llvm-reduce/deltas/ReduceMetadata.cpp b/tools/llvm-reduce/deltas/ReduceMetadata.cpp
new file mode 100644
index 0000000000000..4ea223546efa3
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceMetadata.cpp
@@ -0,0 +1,138 @@
+//===- 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 nodes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceMetadata.h"
+#include "Delta.h"
+#include "llvm/ADT/SmallVector.h"
+#include <set>
+#include <vector>
+
+using namespace llvm;
+
+/// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set
+template <class T>
+static void getChunkMetadataNodes(T &MDUser, int &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 < (int)ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(SeenNodes.size()))
+        NodesToKeep.insert(MD.second);
+      if (ChunksToKeep[I].end == (int)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);
+}
+
+/// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
+/// functions that aren't inside the desired Chunks.
+static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                      Module *Program) {
+  std::set<MDNode *> SeenNodes;
+  std::set<MDNode *> NodesToKeep;
+  int 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);
+
+  for (auto &F : *Program) {
+    eraseMetadataIfOutsideChunk(F, NodesToKeep);
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        eraseMetadataIfOutsideChunk(Inst, NodesToKeep);
+  }
+
+
+  // Get out-of-chunk Named metadata nodes
+  unsigned MetadataCount = SeenNodes.size();
+  std::vector<NamedMDNode *> NamedNodesToDelete;
+  for (auto &MD : Program->named_metadata()) {
+    if (I < (int)ChunksToKeep.size()) {
+      if (!ChunksToKeep[I].contains(++MetadataCount))
+        NamedNodesToDelete.push_back(&MD);
+      if (ChunksToKeep[I].end == (int)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
+static int countMetadataTargets(Module *Program) {
+  std::set<MDNode *> UnnamedNodes;
+  int NamedMetadataNodes = Program->named_metadata_size();
+
+  // 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) {
+    addMetadataToSet(F, UnnamedNodes);
+    for (auto &BB : F)
+      for (auto &I : BB)
+        addMetadataToSet(I, UnnamedNodes);
+  }
+
+  return UnnamedNodes.size() + NamedMetadataNodes;
+}
+
+void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Metadata...\n";
+  int MDCount = countMetadataTargets(Test.getProgram());
+  runDeltaPass(Test, MDCount, extractMetadataFromModule);
+  outs() << "----------------------------\n";
+}
diff --git a/tools/llvm-reduce/deltas/ReduceMetadata.h b/tools/llvm-reduce/deltas/ReduceMetadata.h
new file mode 100644
index 0000000000000..275b44c2aa7de
--- /dev/null
+++ b/tools/llvm-reduce/deltas/ReduceMetadata.h
@@ -0,0 +1,18 @@
+//===- 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 nodes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+
+namespace llvm {
+void reduceMetadataDeltaPass(TestRunner &Test);
+} // namespace llvm