fix ya.make

12 files changed, 5875 insertions, 0 deletions

diff --git a/contrib/libs/llvm12/tools/bugpoint/BugDriver.cpp b/contrib/libs/llvm12/tools/bugpoint/BugDriver.cpp
new file mode 100644
index 0000000000..942028cad8
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/BugDriver.cpp
@@ -0,0 +1,260 @@
+//===- BugDriver.cpp - Top-Level BugPoint class 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 class contains all of the shared state and information that is used by
+// the BugPoint tool to track down errors in optimizations.  This class is the
+// main driver class that invokes all sub-functionality.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ToolRunner.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Linker/Linker.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Support/Host.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+using namespace llvm;
+
+namespace llvm {
+Triple TargetTriple;
+}
+
+DiscardTemp::~DiscardTemp() {
+  if (SaveTemps) {
+    if (Error E = File.keep())
+      errs() << "Failed to keep temp file " << toString(std::move(E)) << '\n';
+    return;
+  }
+  if (Error E = File.discard())
+    errs() << "Failed to delete temp file " << toString(std::move(E)) << '\n';
+}
+
+// Anonymous namespace to define command line options for debugging.
+//
+namespace {
+// Output - The user can specify a file containing the expected output of the
+// program.  If this filename is set, it is used as the reference diff source,
+// otherwise the raw input run through an interpreter is used as the reference
+// source.
+//
+cl::opt<std::string> OutputFile("output",
+                                cl::desc("Specify a reference program output "
+                                         "(for miscompilation detection)"));
+}
+
+/// If we reduce or update the program somehow, call this method to update
+/// bugdriver with it.  This deletes the old module and sets the specified one
+/// as the current program.
+void BugDriver::setNewProgram(std::unique_ptr<Module> M) {
+  Program = std::move(M);
+}
+
+/// getPassesString - Turn a list of passes into a string which indicates the
+/// command line options that must be passed to add the passes.
+///
+std::string llvm::getPassesString(const std::vector<std::string> &Passes) {
+  std::string Result;
+  for (unsigned i = 0, e = Passes.size(); i != e; ++i) {
+    if (i)
+      Result += " ";
+    Result += "-";
+    Result += Passes[i];
+  }
+  return Result;
+}
+
+BugDriver::BugDriver(const char *toolname, bool find_bugs, unsigned timeout,
+                     unsigned memlimit, bool use_valgrind, LLVMContext &ctxt)
+    : Context(ctxt), ToolName(toolname), ReferenceOutputFile(OutputFile),
+      Program(nullptr), Interpreter(nullptr), SafeInterpreter(nullptr),
+      cc(nullptr), run_find_bugs(find_bugs), Timeout(timeout),
+      MemoryLimit(memlimit), UseValgrind(use_valgrind) {}
+
+BugDriver::~BugDriver() {
+  if (Interpreter != SafeInterpreter)
+    delete Interpreter;
+  delete SafeInterpreter;
+  delete cc;
+}
+
+std::unique_ptr<Module> llvm::parseInputFile(StringRef Filename,
+                                             LLVMContext &Ctxt) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
+  if (!Result) {
+    Err.print("bugpoint", errs());
+    return Result;
+  }
+
+  if (verifyModule(*Result, &errs())) {
+    errs() << "bugpoint: " << Filename << ": error: input module is broken!\n";
+    return std::unique_ptr<Module>();
+  }
+
+  // If we don't have an override triple, use the first one to configure
+  // bugpoint, or use the host triple if none provided.
+  if (TargetTriple.getTriple().empty()) {
+    Triple TheTriple(Result->getTargetTriple());
+
+    if (TheTriple.getTriple().empty())
+      TheTriple.setTriple(sys::getDefaultTargetTriple());
+
+    TargetTriple.setTriple(TheTriple.getTriple());
+  }
+
+  Result->setTargetTriple(TargetTriple.getTriple()); // override the triple
+  return Result;
+}
+
+std::unique_ptr<Module> BugDriver::swapProgramIn(std::unique_ptr<Module> M) {
+  std::unique_ptr<Module> OldProgram = std::move(Program);
+  Program = std::move(M);
+  return OldProgram;
+}
+
+// This method takes the specified list of LLVM input files, attempts to load
+// them, either as assembly or bitcode, then link them together. It returns
+// true on failure (if, for example, an input bitcode file could not be
+// parsed), and false on success.
+//
+bool BugDriver::addSources(const std::vector<std::string> &Filenames) {
+  assert(!Program && "Cannot call addSources multiple times!");
+  assert(!Filenames.empty() && "Must specify at least on input filename!");
+
+  // Load the first input file.
+  Program = parseInputFile(Filenames[0], Context);
+  if (!Program)
+    return true;
+
+  outs() << "Read input file      : '" << Filenames[0] << "'\n";
+
+  for (unsigned i = 1, e = Filenames.size(); i != e; ++i) {
+    std::unique_ptr<Module> M = parseInputFile(Filenames[i], Context);
+    if (!M.get())
+      return true;
+
+    outs() << "Linking in input file: '" << Filenames[i] << "'\n";
+    if (Linker::linkModules(*Program, std::move(M)))
+      return true;
+  }
+
+  outs() << "*** All input ok\n";
+
+  // All input files read successfully!
+  return false;
+}
+
+/// run - The top level method that is invoked after all of the instance
+/// variables are set up from command line arguments.
+///
+Error BugDriver::run() {
+  if (run_find_bugs) {
+    // Rearrange the passes and apply them to the program. Repeat this process
+    // until the user kills the program or we find a bug.
+    return runManyPasses(PassesToRun);
+  }
+
+  // If we're not running as a child, the first thing that we must do is
+  // determine what the problem is. Does the optimization series crash the
+  // compiler, or does it produce illegal code?  We make the top-level
+  // decision by trying to run all of the passes on the input program,
+  // which should generate a bitcode file.  If it does generate a bitcode
+  // file, then we know the compiler didn't crash, so try to diagnose a
+  // miscompilation.
+  if (!PassesToRun.empty()) {
+    outs() << "Running selected passes on program to test for crash: ";
+    if (runPasses(*Program, PassesToRun))
+      return debugOptimizerCrash();
+  }
+
+  // Set up the execution environment, selecting a method to run LLVM bitcode.
+  if (Error E = initializeExecutionEnvironment())
+    return E;
+
+  // Test to see if we have a code generator crash.
+  outs() << "Running the code generator to test for a crash: ";
+  if (Error E = compileProgram(*Program)) {
+    outs() << toString(std::move(E));
+    return debugCodeGeneratorCrash();
+  }
+  outs() << '\n';
+
+  // Run the raw input to see where we are coming from.  If a reference output
+  // was specified, make sure that the raw output matches it.  If not, it's a
+  // problem in the front-end or the code generator.
+  //
+  bool CreatedOutput = false;
+  if (ReferenceOutputFile.empty()) {
+    outs() << "Generating reference output from raw program: ";
+    if (Error E = createReferenceFile(*Program)) {
+      errs() << toString(std::move(E));
+      return debugCodeGeneratorCrash();
+    }
+    CreatedOutput = true;
+  }
+
+  // Make sure the reference output file gets deleted on exit from this
+  // function, if appropriate.
+  std::string ROF(ReferenceOutputFile);
+  FileRemover RemoverInstance(ROF, CreatedOutput && !SaveTemps);
+
+  // Diff the output of the raw program against the reference output.  If it
+  // matches, then we assume there is a miscompilation bug and try to
+  // diagnose it.
+  outs() << "*** Checking the code generator...\n";
+  Expected<bool> Diff = diffProgram(*Program, "", "", false);
+  if (Error E = Diff.takeError()) {
+    errs() << toString(std::move(E));
+    return debugCodeGeneratorCrash();
+  }
+  if (!*Diff) {
+    outs() << "\n*** Output matches: Debugging miscompilation!\n";
+    if (Error E = debugMiscompilation()) {
+      errs() << toString(std::move(E));
+      return debugCodeGeneratorCrash();
+    }
+    return Error::success();
+  }
+
+  outs() << "\n*** Input program does not match reference diff!\n";
+  outs() << "Debugging code generator problem!\n";
+  if (Error E = debugCodeGenerator()) {
+    errs() << toString(std::move(E));
+    return debugCodeGeneratorCrash();
+  }
+  return Error::success();
+}
+
+void llvm::PrintFunctionList(const std::vector<Function *> &Funcs) {
+  unsigned NumPrint = Funcs.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0; i != NumPrint; ++i)
+    outs() << " " << Funcs[i]->getName();
+  if (NumPrint < Funcs.size())
+    outs() << "... <" << Funcs.size() << " total>";
+  outs().flush();
+}
+
+void llvm::PrintGlobalVariableList(const std::vector<GlobalVariable *> &GVs) {
+  unsigned NumPrint = GVs.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0; i != NumPrint; ++i)
+    outs() << " " << GVs[i]->getName();
+  if (NumPrint < GVs.size())
+    outs() << "... <" << GVs.size() << " total>";
+  outs().flush();
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/BugDriver.h b/contrib/libs/llvm12/tools/bugpoint/BugDriver.h
new file mode 100644
index 0000000000..fe5201eb2e
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/BugDriver.h
@@ -0,0 +1,309 @@
+//===- BugDriver.h - Top-Level BugPoint class -------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This class contains all of the shared state and information that is used by
+// the BugPoint tool to track down errors in optimizations.  This class is the
+// main driver class that invokes all sub-functionality.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_BUGPOINT_BUGDRIVER_H
+#define LLVM_TOOLS_BUGPOINT_BUGDRIVER_H
+
+#include "llvm/IR/ValueMap.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <memory>
+#include <string>
+#include <vector>
+
+namespace llvm {
+
+class Value;
+class PassInfo;
+class Module;
+class GlobalVariable;
+class Function;
+class BasicBlock;
+class AbstractInterpreter;
+class Instruction;
+class LLVMContext;
+
+class DebugCrashes;
+
+class CC;
+
+extern bool DisableSimplifyCFG;
+
+/// BugpointIsInterrupted - Set to true when the user presses ctrl-c.
+///
+extern bool BugpointIsInterrupted;
+
+class BugDriver {
+  LLVMContext &Context;
+  const char *ToolName;            // argv[0] of bugpoint
+  std::string ReferenceOutputFile; // Name of `good' output file
+  std::unique_ptr<Module> Program; // The raw program, linked together
+  std::vector<std::string> PassesToRun;
+  AbstractInterpreter *Interpreter;     // How to run the program
+  AbstractInterpreter *SafeInterpreter; // To generate reference output, etc.
+  CC *cc;
+  bool run_find_bugs;
+  unsigned Timeout;
+  unsigned MemoryLimit;
+  bool UseValgrind;
+
+  // FIXME: sort out public/private distinctions...
+  friend class ReducePassList;
+  friend class ReduceMisCodegenFunctions;
+
+public:
+  BugDriver(const char *toolname, bool find_bugs, unsigned timeout,
+            unsigned memlimit, bool use_valgrind, LLVMContext &ctxt);
+  ~BugDriver();
+
+  const char *getToolName() const { return ToolName; }
+
+  LLVMContext &getContext() const { return Context; }
+
+  // Set up methods... these methods are used to copy information about the
+  // command line arguments into instance variables of BugDriver.
+  //
+  bool addSources(const std::vector<std::string> &FileNames);
+  void addPass(std::string p) { PassesToRun.push_back(std::move(p)); }
+  void setPassesToRun(const std::vector<std::string> &PTR) {
+    PassesToRun = PTR;
+  }
+  const std::vector<std::string> &getPassesToRun() const { return PassesToRun; }
+
+  /// run - The top level method that is invoked after all of the instance
+  /// variables are set up from command line arguments. The \p as_child argument
+  /// indicates whether the driver is to run in parent mode or child mode.
+  ///
+  Error run();
+
+  /// debugOptimizerCrash - This method is called when some optimizer pass
+  /// crashes on input.  It attempts to prune down the testcase to something
+  /// reasonable, and figure out exactly which pass is crashing.
+  ///
+  Error debugOptimizerCrash(const std::string &ID = "passes");
+
+  /// debugCodeGeneratorCrash - This method is called when the code generator
+  /// crashes on an input.  It attempts to reduce the input as much as possible
+  /// while still causing the code generator to crash.
+  Error debugCodeGeneratorCrash();
+
+  /// debugMiscompilation - This method is used when the passes selected are not
+  /// crashing, but the generated output is semantically different from the
+  /// input.
+  Error debugMiscompilation();
+
+  /// debugPassMiscompilation - This method is called when the specified pass
+  /// miscompiles Program as input.  It tries to reduce the testcase to
+  /// something that smaller that still miscompiles the program.
+  /// ReferenceOutput contains the filename of the file containing the output we
+  /// are to match.
+  ///
+  bool debugPassMiscompilation(const PassInfo *ThePass,
+                               const std::string &ReferenceOutput);
+
+  /// compileSharedObject - This method creates a SharedObject from a given
+  /// BitcodeFile for debugging a code generator.
+  ///
+  Expected<std::string> compileSharedObject(const std::string &BitcodeFile);
+
+  /// debugCodeGenerator - This method narrows down a module to a function or
+  /// set of functions, using the CBE as a ``safe'' code generator for other
+  /// functions that are not under consideration.
+  Error debugCodeGenerator();
+
+  /// isExecutingJIT - Returns true if bugpoint is currently testing the JIT
+  ///
+  bool isExecutingJIT();
+
+  Module &getProgram() const { return *Program; }
+
+  /// Set the current module to the specified module, returning the old one.
+  std::unique_ptr<Module> swapProgramIn(std::unique_ptr<Module> M);
+
+  AbstractInterpreter *switchToSafeInterpreter() {
+    AbstractInterpreter *Old = Interpreter;
+    Interpreter = (AbstractInterpreter *)SafeInterpreter;
+    return Old;
+  }
+
+  void switchToInterpreter(AbstractInterpreter *AI) { Interpreter = AI; }
+
+  /// If we reduce or update the program somehow, call this method to update
+  /// bugdriver with it.  This deletes the old module and sets the specified one
+  /// as the current program.
+  void setNewProgram(std::unique_ptr<Module> M);
+
+  /// Try to compile the specified module. This is used for code generation
+  /// crash testing.
+  Error compileProgram(Module &M) const;
+
+  /// This method runs "Program", capturing the output of the program to a file.
+  /// A recommended filename may be optionally specified.
+  Expected<std::string> executeProgram(const Module &Program,
+                                       std::string OutputFilename,
+                                       std::string Bitcode,
+                                       const std::string &SharedObjects,
+                                       AbstractInterpreter *AI) const;
+
+  /// Used to create reference output with the "safe" backend, if reference
+  /// output is not provided.  If there is a problem with the code generator
+  /// (e.g., llc crashes), this will return false and set Error.
+  Expected<std::string>
+  executeProgramSafely(const Module &Program,
+                       const std::string &OutputFile) const;
+
+  /// Calls compileProgram and then records the output into ReferenceOutputFile.
+  /// Returns true if reference file created, false otherwise. Note:
+  /// initializeExecutionEnvironment should be called BEFORE this function.
+  Error createReferenceFile(Module &M, const std::string &Filename =
+                                           "bugpoint.reference.out-%%%%%%%");
+
+  /// This method executes the specified module and diffs the output against the
+  /// file specified by ReferenceOutputFile.  If the output is different, 1 is
+  /// returned.  If there is a problem with the code generator (e.g., llc
+  /// crashes), this will return -1 and set Error.
+  Expected<bool> diffProgram(const Module &Program,
+                             const std::string &BitcodeFile = "",
+                             const std::string &SharedObj = "",
+                             bool RemoveBitcode = false) const;
+
+  /// This function is used to output M to a file named "bugpoint-ID.bc".
+  void EmitProgressBitcode(const Module &M, const std::string &ID,
+                           bool NoFlyer = false) const;
+
+  /// This method clones the current Program and deletes the specified
+  /// instruction from the cloned module.  It then runs a series of cleanup
+  /// passes (ADCE and SimplifyCFG) to eliminate any code which depends on the
+  /// value. The modified module is then returned.
+  ///
+  std::unique_ptr<Module> deleteInstructionFromProgram(const Instruction *I,
+                                                       unsigned Simp);
+
+  /// This method clones the current Program and performs a series of cleanups
+  /// intended to get rid of extra cruft on the module. If the
+  /// MayModifySemantics argument is true, then the cleanups is allowed to
+  /// modify how the code behaves.
+  ///
+  std::unique_ptr<Module> performFinalCleanups(std::unique_ptr<Module> M,
+                                               bool MayModifySemantics = false);
+
+  /// Given a module, extract up to one loop from it into a new function. This
+  /// returns null if there are no extractable loops in the program or if the
+  /// loop extractor crashes.
+  std::unique_ptr<Module> extractLoop(Module *M);
+
+  /// Extract all but the specified basic blocks into their own functions. The
+  /// only detail is that M is actually a module cloned from the one the BBs are
+  /// in, so some mapping needs to be performed. If this operation fails for
+  /// some reason (ie the implementation is buggy), this function should return
+  /// null, otherwise it returns a new Module.
+  std::unique_ptr<Module>
+  extractMappedBlocksFromModule(const std::vector<BasicBlock *> &BBs,
+                                Module *M);
+
+  /// Carefully run the specified set of pass on the specified/ module,
+  /// returning the transformed module on success, or a null pointer on failure.
+  std::unique_ptr<Module> runPassesOn(Module *M,
+                                      const std::vector<std::string> &Passes,
+                                      ArrayRef<std::string> ExtraArgs = {});
+
+  /// runPasses - Run the specified passes on Program, outputting a bitcode
+  /// file and writting the filename into OutputFile if successful.  If the
+  /// optimizations fail for some reason (optimizer crashes), return true,
+  /// otherwise return false.  If DeleteOutput is set to true, the bitcode is
+  /// deleted on success, and the filename string is undefined.  This prints to
+  /// outs() a single line message indicating whether compilation was successful
+  /// or failed, unless Quiet is set.  ExtraArgs specifies additional arguments
+  /// to pass to the child bugpoint instance.
+  ///
+  bool runPasses(Module &Program, const std::vector<std::string> &PassesToRun,
+                 std::string &OutputFilename, bool DeleteOutput = false,
+                 bool Quiet = false,
+                 ArrayRef<std::string> ExtraArgs = {}) const;
+
+  /// runPasses - Just like the method above, but this just returns true or
+  /// false indicating whether or not the optimizer crashed on the specified
+  /// input (true = crashed).  Does not produce any output.
+  ///
+  bool runPasses(Module &M, const std::vector<std::string> &PassesToRun) const {
+    std::string Filename;
+    return runPasses(M, PassesToRun, Filename, true);
+  }
+
+  /// Take the specified pass list and create different combinations of passes
+  /// to compile the program with. Compile the program with each set and mark
+  /// test to see if it compiled correctly. If the passes compiled correctly
+  /// output nothing and rearrange the passes into a new order. If the passes
+  /// did not compile correctly, output the command required to recreate the
+  /// failure.
+  Error runManyPasses(const std::vector<std::string> &AllPasses);
+
+  /// This writes the current "Program" to the named bitcode file.  If an error
+  /// occurs, true is returned.
+  bool writeProgramToFile(const std::string &Filename, const Module &M) const;
+  bool writeProgramToFile(const std::string &Filename, int FD,
+                          const Module &M) const;
+  bool writeProgramToFile(int FD, const Module &M) const;
+
+private:
+  /// initializeExecutionEnvironment - This method is used to set up the
+  /// environment for executing LLVM programs.
+  ///
+  Error initializeExecutionEnvironment();
+};
+
+struct DiscardTemp {
+  sys::fs::TempFile &File;
+  ~DiscardTemp();
+};
+
+///  Given a bitcode or assembly input filename, parse and return it, or return
+///  null if not possible.
+///
+std::unique_ptr<Module> parseInputFile(StringRef InputFilename,
+                                       LLVMContext &ctxt);
+
+/// getPassesString - Turn a list of passes into a string which indicates the
+/// command line options that must be passed to add the passes.
+///
+std::string getPassesString(const std::vector<std::string> &Passes);
+
+/// PrintFunctionList - prints out list of problematic functions
+///
+void PrintFunctionList(const std::vector<Function *> &Funcs);
+
+/// PrintGlobalVariableList - prints out list of problematic global variables
+///
+void PrintGlobalVariableList(const std::vector<GlobalVariable *> &GVs);
+
+// DeleteGlobalInitializer - "Remove" the global variable by deleting its
+// initializer, making it external.
+//
+void DeleteGlobalInitializer(GlobalVariable *GV);
+
+// DeleteFunctionBody - "Remove" the function by deleting all of it's basic
+// blocks, making it external.
+//
+void DeleteFunctionBody(Function *F);
+
+/// Given a module and a list of functions in the module, split the functions
+/// OUT of the specified module, and place them in the new module.
+std::unique_ptr<Module>
+SplitFunctionsOutOfModule(Module *M, const std::vector<Function *> &F,
+                          ValueToValueMapTy &VMap);
+
+} // End llvm namespace
+
+#endif
diff --git a/contrib/libs/llvm12/tools/bugpoint/CrashDebugger.cpp b/contrib/libs/llvm12/tools/bugpoint/CrashDebugger.cpp
new file mode 100644
index 0000000000..d06bca9a12
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/CrashDebugger.cpp
@@ -0,0 +1,1432 @@
+//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
+//
+// 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 defines the bugpoint internals that narrow down compilation crashes
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ListReducer.h"
+#include "ToolRunner.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/ValueSymbolTable.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include <set>
+using namespace llvm;
+
+namespace {
+cl::opt<bool> KeepMain("keep-main",
+                       cl::desc("Force function reduction to keep main"),
+                       cl::init(false));
+cl::opt<bool> NoGlobalRM("disable-global-remove",
+                         cl::desc("Do not remove global variables"),
+                         cl::init(false));
+
+cl::opt<bool> NoAttributeRM("disable-attribute-remove",
+                         cl::desc("Do not remove function attributes"),
+                         cl::init(false));
+
+cl::opt<bool> ReplaceFuncsWithNull(
+    "replace-funcs-with-null",
+    cl::desc("When stubbing functions, replace all uses will null"),
+    cl::init(false));
+cl::opt<bool> DontReducePassList("disable-pass-list-reduction",
+                                 cl::desc("Skip pass list reduction steps"),
+                                 cl::init(false));
+
+cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
+                          cl::desc("Do not remove global named metadata"),
+                          cl::init(false));
+cl::opt<bool> NoStripDebugInfo("disable-strip-debuginfo",
+                               cl::desc("Do not strip debug info metadata"),
+                               cl::init(false));
+cl::opt<bool> NoStripDebugTypeInfo("disable-strip-debug-types",
+                               cl::desc("Do not strip debug type info metadata"),
+                               cl::init(false));
+cl::opt<bool> VerboseErrors("verbose-errors",
+                            cl::desc("Print the output of crashing program"),
+                            cl::init(false));
+}
+
+namespace llvm {
+class ReducePassList : public ListReducer<std::string> {
+  BugDriver &BD;
+
+public:
+  ReducePassList(BugDriver &bd) : BD(bd) {}
+
+  // Return true iff running the "removed" passes succeeds, and running the
+  // "Kept" passes fail when run on the output of the "removed" passes.  If we
+  // return true, we update the current module of bugpoint.
+  Expected<TestResult> doTest(std::vector<std::string> &Removed,
+                              std::vector<std::string> &Kept) override;
+};
+}
+
+Expected<ReducePassList::TestResult>
+ReducePassList::doTest(std::vector<std::string> &Prefix,
+                       std::vector<std::string> &Suffix) {
+  std::string PrefixOutput;
+  std::unique_ptr<Module> OrigProgram;
+  if (!Prefix.empty()) {
+    outs() << "Checking to see if these passes crash: "
+           << getPassesString(Prefix) << ": ";
+    if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
+      return KeepPrefix;
+
+    OrigProgram = std::move(BD.Program);
+
+    BD.Program = parseInputFile(PrefixOutput, BD.getContext());
+    if (BD.Program == nullptr) {
+      errs() << BD.getToolName() << ": Error reading bitcode file '"
+             << PrefixOutput << "'!\n";
+      exit(1);
+    }
+    sys::fs::remove(PrefixOutput);
+  }
+
+  outs() << "Checking to see if these passes crash: " << getPassesString(Suffix)
+         << ": ";
+
+  if (BD.runPasses(BD.getProgram(), Suffix))
+    return KeepSuffix; // The suffix crashes alone...
+
+  // Nothing failed, restore state...
+  if (OrigProgram)
+    BD.Program = std::move(OrigProgram);
+  return NoFailure;
+}
+
+using BugTester = bool (*)(const BugDriver &, Module *);
+
+namespace {
+/// ReduceCrashingGlobalInitializers - This works by removing global variable
+/// initializers and seeing if the program still crashes. If it does, then we
+/// keep that program and try again.
+class ReduceCrashingGlobalInitializers : public ListReducer<GlobalVariable *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingGlobalInitializers(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<GlobalVariable *> &Prefix,
+                              std::vector<GlobalVariable *> &Kept) override {
+    if (!Kept.empty() && TestGlobalVariables(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestGlobalVariables(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestGlobalVariables(std::vector<GlobalVariable *> &GVs);
+};
+}
+
+bool ReduceCrashingGlobalInitializers::TestGlobalVariables(
+    std::vector<GlobalVariable *> &GVs) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  std::set<GlobalVariable *> GVSet;
+
+  for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
+    GlobalVariable *CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
+    assert(CMGV && "Global Variable not in module?!");
+    GVSet.insert(CMGV);
+  }
+
+  outs() << "Checking for crash with only these global variables: ";
+  PrintGlobalVariableList(GVs);
+  outs() << ": ";
+
+  // Loop over and delete any global variables which we aren't supposed to be
+  // playing with...
+  for (GlobalVariable &I : M->globals())
+    if (I.hasInitializer() && !GVSet.count(&I)) {
+      DeleteGlobalInitializer(&I);
+      I.setLinkage(GlobalValue::ExternalLinkage);
+      I.setComdat(nullptr);
+    }
+
+  // Try running the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use global variable pointers that point into the now-current
+    // module.
+    GVs.assign(GVSet.begin(), GVSet.end());
+    return true;
+  }
+
+  return false;
+}
+
+namespace {
+/// ReduceCrashingFunctions reducer - This works by removing functions and
+/// seeing if the program still crashes. If it does, then keep the newer,
+/// smaller program.
+///
+class ReduceCrashingFunctions : public ListReducer<Function *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingFunctions(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<Function *> &Prefix,
+                              std::vector<Function *> &Kept) override {
+    if (!Kept.empty() && TestFuncs(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestFuncs(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestFuncs(std::vector<Function *> &Prefix);
+};
+}
+
+static void RemoveFunctionReferences(Module *M, const char *Name) {
+  auto *UsedVar = M->getGlobalVariable(Name, true);
+  if (!UsedVar || !UsedVar->hasInitializer())
+    return;
+  if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
+    assert(UsedVar->use_empty());
+    UsedVar->eraseFromParent();
+    return;
+  }
+  auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
+  std::vector<Constant *> Used;
+  for (Value *V : OldUsedVal->operand_values()) {
+    Constant *Op = cast<Constant>(V->stripPointerCasts());
+    if (!Op->isNullValue()) {
+      Used.push_back(cast<Constant>(V));
+    }
+  }
+  auto *NewValElemTy = OldUsedVal->getType()->getElementType();
+  auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
+  auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
+  UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
+  UsedVar->setInitializer(NewUsedVal);
+}
+
+bool ReduceCrashingFunctions::TestFuncs(std::vector<Function *> &Funcs) {
+  // If main isn't present, claim there is no problem.
+  if (KeepMain && !is_contained(Funcs, BD.getProgram().getFunction("main")))
+    return false;
+
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  std::set<Function *> Functions;
+  for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
+    Function *CMF = cast<Function>(VMap[Funcs[i]]);
+    assert(CMF && "Function not in module?!");
+    assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty");
+    assert(CMF->getName() == Funcs[i]->getName() && "wrong name");
+    Functions.insert(CMF);
+  }
+
+  outs() << "Checking for crash with only these functions: ";
+  PrintFunctionList(Funcs);
+  outs() << ": ";
+  if (!ReplaceFuncsWithNull) {
+    // Loop over and delete any functions which we aren't supposed to be playing
+    // with...
+    for (Function &I : *M)
+      if (!I.isDeclaration() && !Functions.count(&I))
+        DeleteFunctionBody(&I);
+  } else {
+    std::vector<GlobalValue *> ToRemove;
+    // First, remove aliases to functions we're about to purge.
+    for (GlobalAlias &Alias : M->aliases()) {
+      GlobalObject *Root = Alias.getBaseObject();
+      Function *F = dyn_cast_or_null<Function>(Root);
+      if (F) {
+        if (Functions.count(F))
+          // We're keeping this function.
+          continue;
+      } else if (Root->isNullValue()) {
+        // This referenced a globalalias that we've already replaced,
+        // so we still need to replace this alias.
+      } else if (!F) {
+        // Not a function, therefore not something we mess with.
+        continue;
+      }
+
+      PointerType *Ty = cast<PointerType>(Alias.getType());
+      Constant *Replacement = ConstantPointerNull::get(Ty);
+      Alias.replaceAllUsesWith(Replacement);
+      ToRemove.push_back(&Alias);
+    }
+
+    for (Function &I : *M) {
+      if (!I.isDeclaration() && !Functions.count(&I)) {
+        PointerType *Ty = cast<PointerType>(I.getType());
+        Constant *Replacement = ConstantPointerNull::get(Ty);
+        I.replaceAllUsesWith(Replacement);
+        ToRemove.push_back(&I);
+      }
+    }
+
+    for (auto *F : ToRemove) {
+      F->eraseFromParent();
+    }
+
+    // Finally, remove any null members from any global intrinsic.
+    RemoveFunctionReferences(M.get(), "llvm.used");
+    RemoveFunctionReferences(M.get(), "llvm.compiler.used");
+  }
+  // Try running the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use function pointers that point into the now-current
+    // module.
+    Funcs.assign(Functions.begin(), Functions.end());
+    return true;
+  }
+  return false;
+}
+
+namespace {
+/// ReduceCrashingFunctionAttributes reducer - This works by removing
+/// attributes on a particular function and seeing if the program still crashes.
+/// If it does, then keep the newer, smaller program.
+///
+class ReduceCrashingFunctionAttributes : public ListReducer<Attribute> {
+  BugDriver &BD;
+  std::string FnName;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
+                                   BugTester testFn)
+      : BD(bd), FnName(FnName), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
+                              std::vector<Attribute> &Kept) override {
+    if (!Kept.empty() && TestFuncAttrs(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestFuncAttrs(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestFuncAttrs(std::vector<Attribute> &Attrs);
+};
+}
+
+bool ReduceCrashingFunctionAttributes::TestFuncAttrs(
+    std::vector<Attribute> &Attrs) {
+  // Clone the program to try hacking it apart...
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram());
+  Function *F = M->getFunction(FnName);
+
+  // Build up an AttributeList from the attributes we've been given by the
+  // reducer.
+  AttrBuilder AB;
+  for (auto A : Attrs)
+    AB.addAttribute(A);
+  AttributeList NewAttrs;
+  NewAttrs =
+      NewAttrs.addAttributes(BD.getContext(), AttributeList::FunctionIndex, AB);
+
+  // Set this new list of attributes on the function.
+  F->setAttributes(NewAttrs);
+
+  // If the attribute list includes "optnone" we need to make sure it also
+  // includes "noinline" otherwise we will get a verifier failure.
+  if (F->hasFnAttribute(Attribute::OptimizeNone))
+    F->addFnAttr(Attribute::NoInline);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Pass along the set of attributes that caused the crash.
+    Attrs.clear();
+    for (Attribute A : NewAttrs.getFnAttributes()) {
+      Attrs.push_back(A);
+    }
+    return true;
+  }
+  return false;
+}
+
+namespace {
+/// Simplify the CFG without completely destroying it.
+/// This is not well defined, but basically comes down to "try to eliminate
+/// unreachable blocks and constant fold terminators without deciding that
+/// certain undefined behavior cuts off the program at the legs".
+void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
+  if (F.empty())
+    return;
+
+  for (auto *BB : BBs) {
+    ConstantFoldTerminator(BB);
+    MergeBlockIntoPredecessor(BB);
+  }
+
+  // Remove unreachable blocks
+  // removeUnreachableBlocks can't be used here, it will turn various
+  // undefined behavior into unreachables, but bugpoint was the thing that
+  // generated the undefined behavior, and we don't want it to kill the entire
+  // program.
+  SmallPtrSet<BasicBlock *, 16> Visited;
+  for (auto *BB : depth_first(&F.getEntryBlock()))
+    Visited.insert(BB);
+
+  SmallVector<BasicBlock *, 16> Unreachable;
+  for (auto &BB : F)
+    if (!Visited.count(&BB))
+      Unreachable.push_back(&BB);
+
+  // The dead BB's may be in a dead cycle or otherwise have references to each
+  // other.  Because of this, we have to drop all references first, then delete
+  // them all at once.
+  for (auto *BB : Unreachable) {
+    for (BasicBlock *Successor : successors(&*BB))
+      if (Visited.count(Successor))
+        Successor->removePredecessor(&*BB);
+    BB->dropAllReferences();
+  }
+  for (auto *BB : Unreachable)
+    BB->eraseFromParent();
+}
+/// ReduceCrashingBlocks reducer - This works by setting the terminators of
+/// all terminators except the specified basic blocks to a 'ret' instruction,
+/// then running the simplify-cfg pass.  This has the effect of chopping up
+/// the CFG really fast which can reduce large functions quickly.
+///
+class ReduceCrashingBlocks : public ListReducer<const BasicBlock *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingBlocks(BugDriver &BD, BugTester testFn)
+      : BD(BD), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
+                              std::vector<const BasicBlock *> &Kept) override {
+    if (!Kept.empty() && TestBlocks(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestBlocks(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
+};
+}
+
+bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock *> &BBs) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<BasicBlock *, 8> Blocks;
+  for (unsigned i = 0, e = BBs.size(); i != e; ++i)
+    Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
+
+  outs() << "Checking for crash with only these blocks:";
+  unsigned NumPrint = Blocks.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << BBs[i]->getName();
+  if (NumPrint < Blocks.size())
+    outs() << "... <" << Blocks.size() << " total>";
+  outs() << ": ";
+
+  // Loop over and delete any hack up any blocks that are not listed...
+  for (Function &F : M->functions()) {
+    for (BasicBlock &BB : F) {
+      if (!Blocks.count(&BB) && BB.getTerminator()->getNumSuccessors()) {
+        // Loop over all of the successors of this block, deleting any PHI nodes
+        // that might include it.
+        for (BasicBlock *Succ : successors(&BB))
+          Succ->removePredecessor(&BB);
+
+        Instruction *BBTerm = BB.getTerminator();
+        if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy())
+          continue;
+        if (!BBTerm->getType()->isVoidTy())
+          BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
+
+        // Replace the old terminator instruction.
+        BB.getInstList().pop_back();
+        new UnreachableInst(BB.getContext(), &BB);
+      }
+    }
+  }
+
+  // The CFG Simplifier pass may delete one of the basic blocks we are
+  // interested in.  If it does we need to take the block out of the list.  Make
+  // a "persistent mapping" by turning basic blocks into <function, name> pairs.
+  // This won't work well if blocks are unnamed, but that is just the risk we
+  // have to take. FIXME: Can we just name the blocks?
+  std::vector<std::pair<std::string, std::string>> BlockInfo;
+
+  for (BasicBlock *BB : Blocks)
+    BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
+                           std::string(BB->getName()));
+
+  SmallVector<BasicBlock *, 16> ToProcess;
+  for (auto &F : *M) {
+    for (auto &BB : F)
+      if (!Blocks.count(&BB))
+        ToProcess.push_back(&BB);
+    simpleSimplifyCfg(F, ToProcess);
+    ToProcess.clear();
+  }
+  // Verify we didn't break anything
+  std::vector<std::string> Passes;
+  Passes.push_back("verify");
+  std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
+  if (!New) {
+    errs() << "verify failed!\n";
+    exit(1);
+  }
+  M = std::move(New);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use basic block pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    BBs.clear();
+    const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
+    for (const auto &BI : BlockInfo) {
+      Function *F = cast<Function>(GST.lookup(BI.first));
+      Value *V = F->getValueSymbolTable()->lookup(BI.second);
+      if (V && V->getType() == Type::getLabelTy(V->getContext()))
+        BBs.push_back(cast<BasicBlock>(V));
+    }
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+/// ReduceCrashingConditionals reducer - This works by changing
+/// conditional branches to unconditional ones, then simplifying the CFG
+/// This has the effect of chopping up the CFG really fast which can reduce
+/// large functions quickly.
+///
+class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
+  BugDriver &BD;
+  BugTester TestFn;
+  bool Direction;
+
+public:
+  ReduceCrashingConditionals(BugDriver &bd, BugTester testFn, bool Direction)
+      : BD(bd), TestFn(testFn), Direction(Direction) {}
+
+  Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
+                              std::vector<const BasicBlock *> &Kept) override {
+    if (!Kept.empty() && TestBlocks(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestBlocks(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
+};
+}
+
+bool ReduceCrashingConditionals::TestBlocks(
+    std::vector<const BasicBlock *> &BBs) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const BasicBlock *, 8> Blocks;
+  for (const auto *BB : BBs)
+    Blocks.insert(cast<BasicBlock>(VMap[BB]));
+
+  outs() << "Checking for crash with changing conditionals to always jump to "
+         << (Direction ? "true" : "false") << ":";
+  unsigned NumPrint = Blocks.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << BBs[i]->getName();
+  if (NumPrint < Blocks.size())
+    outs() << "... <" << Blocks.size() << " total>";
+  outs() << ": ";
+
+  // Loop over and delete any hack up any blocks that are not listed...
+  for (auto &F : *M)
+    for (auto &BB : F)
+      if (!Blocks.count(&BB)) {
+        auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
+        if (!BR || !BR->isConditional())
+          continue;
+        if (Direction)
+          BR->setCondition(ConstantInt::getTrue(BR->getContext()));
+        else
+          BR->setCondition(ConstantInt::getFalse(BR->getContext()));
+      }
+
+  // The following may destroy some blocks, so we save them first
+  std::vector<std::pair<std::string, std::string>> BlockInfo;
+
+  for (const BasicBlock *BB : Blocks)
+    BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
+                           std::string(BB->getName()));
+
+  SmallVector<BasicBlock *, 16> ToProcess;
+  for (auto &F : *M) {
+    for (auto &BB : F)
+      if (!Blocks.count(&BB))
+        ToProcess.push_back(&BB);
+    simpleSimplifyCfg(F, ToProcess);
+    ToProcess.clear();
+  }
+  // Verify we didn't break anything
+  std::vector<std::string> Passes;
+  Passes.push_back("verify");
+  std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
+  if (!New) {
+    errs() << "verify failed!\n";
+    exit(1);
+  }
+  M = std::move(New);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use basic block pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    BBs.clear();
+    const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
+    for (auto &BI : BlockInfo) {
+      auto *F = cast<Function>(GST.lookup(BI.first));
+      Value *V = F->getValueSymbolTable()->lookup(BI.second);
+      if (V && V->getType() == Type::getLabelTy(V->getContext()))
+        BBs.push_back(cast<BasicBlock>(V));
+    }
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+/// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
+/// in the program.
+
+class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
+  BugDriver &BD;
+  BugTester TestFn;
+  TargetTransformInfo TTI;
+
+public:
+  ReduceSimplifyCFG(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn), TTI(bd.getProgram().getDataLayout()) {}
+
+  Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
+                              std::vector<const BasicBlock *> &Kept) override {
+    if (!Kept.empty() && TestBlocks(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestBlocks(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
+};
+}
+
+bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const BasicBlock *, 8> Blocks;
+  for (const auto *BB : BBs)
+    Blocks.insert(cast<BasicBlock>(VMap[BB]));
+
+  outs() << "Checking for crash with CFG simplifying:";
+  unsigned NumPrint = Blocks.size();
+  if (NumPrint > 10)
+    NumPrint = 10;
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << BBs[i]->getName();
+  if (NumPrint < Blocks.size())
+    outs() << "... <" << Blocks.size() << " total>";
+  outs() << ": ";
+
+  // The following may destroy some blocks, so we save them first
+  std::vector<std::pair<std::string, std::string>> BlockInfo;
+
+  for (const BasicBlock *BB : Blocks)
+    BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
+                           std::string(BB->getName()));
+
+  // Loop over and delete any hack up any blocks that are not listed...
+  for (auto &F : *M)
+    // Loop over all of the basic blocks and remove them if they are unneeded.
+    for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
+      if (!Blocks.count(&*BBIt)) {
+        ++BBIt;
+        continue;
+      }
+      simplifyCFG(&*BBIt++, TTI);
+    }
+  // Verify we didn't break anything
+  std::vector<std::string> Passes;
+  Passes.push_back("verify");
+  std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
+  if (!New) {
+    errs() << "verify failed!\n";
+    exit(1);
+  }
+  M = std::move(New);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use basic block pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    BBs.clear();
+    const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
+    for (auto &BI : BlockInfo) {
+      auto *F = cast<Function>(GST.lookup(BI.first));
+      Value *V = F->getValueSymbolTable()->lookup(BI.second);
+      if (V && V->getType() == Type::getLabelTy(V->getContext()))
+        BBs.push_back(cast<BasicBlock>(V));
+    }
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+/// ReduceCrashingInstructions reducer - This works by removing the specified
+/// non-terminator instructions and replacing them with undef.
+///
+class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingInstructions(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
+                              std::vector<const Instruction *> &Kept) override {
+    if (!Kept.empty() && TestInsts(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestInsts(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestInsts(std::vector<const Instruction *> &Prefix);
+};
+}
+
+bool ReduceCrashingInstructions::TestInsts(
+    std::vector<const Instruction *> &Insts) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<Instruction *, 32> Instructions;
+  for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
+    assert(!Insts[i]->isTerminator());
+    Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
+  }
+
+  outs() << "Checking for crash with only " << Instructions.size();
+  if (Instructions.size() == 1)
+    outs() << " instruction: ";
+  else
+    outs() << " instructions: ";
+
+  for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
+    for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
+      for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
+        Instruction *Inst = &*I++;
+        if (!Instructions.count(Inst) && !Inst->isTerminator() &&
+            !Inst->isEHPad() && !Inst->getType()->isTokenTy() &&
+            !Inst->isSwiftError()) {
+          if (!Inst->getType()->isVoidTy())
+            Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
+          Inst->eraseFromParent();
+        }
+      }
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass(/*FatalErrors=*/false));
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use instruction pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    Insts.clear();
+    for (Instruction *Inst : Instructions)
+      Insts.push_back(Inst);
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+/// ReduceCrashingMetadata reducer - This works by removing all metadata from
+/// the specified instructions.
+///
+class ReduceCrashingMetadata : public ListReducer<Instruction *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingMetadata(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<Instruction *> &Prefix,
+                              std::vector<Instruction *> &Kept) override {
+    if (!Kept.empty() && TestInsts(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestInsts(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestInsts(std::vector<Instruction *> &Prefix);
+};
+} // namespace
+
+bool ReduceCrashingMetadata::TestInsts(std::vector<Instruction *> &Insts) {
+  // Clone the program to try hacking it apart...
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // Convert list to set for fast lookup...
+  SmallPtrSet<Instruction *, 32> Instructions;
+  for (Instruction *I : Insts)
+    Instructions.insert(cast<Instruction>(VMap[I]));
+
+  outs() << "Checking for crash with metadata retained from "
+         << Instructions.size();
+  if (Instructions.size() == 1)
+    outs() << " instruction: ";
+  else
+    outs() << " instructions: ";
+
+  // Try to drop instruction metadata from all instructions, except the ones
+  // selected in Instructions.
+  for (Function &F : *M)
+    for (Instruction &Inst : instructions(F)) {
+      if (!Instructions.count(&Inst)) {
+        Inst.dropUnknownNonDebugMetadata();
+        Inst.setDebugLoc({});
+      }
+    }
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass(/*FatalErrors=*/false));
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+
+    // Make sure to use instruction pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    Insts.clear();
+    for (Instruction *I : Instructions)
+      Insts.push_back(I);
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+// Reduce the list of Named Metadata nodes. We keep this as a list of
+// names to avoid having to convert back and forth every time.
+class ReduceCrashingNamedMD : public ListReducer<std::string> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingNamedMD(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<std::string> &Prefix,
+                              std::vector<std::string> &Kept) override {
+    if (!Kept.empty() && TestNamedMDs(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestNamedMDs(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestNamedMDs(std::vector<std::string> &NamedMDs);
+};
+}
+
+bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
+
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  outs() << "Checking for crash with only these named metadata nodes:";
+  unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << NamedMDs[i];
+  if (NumPrint < NamedMDs.size())
+    outs() << "... <" << NamedMDs.size() << " total>";
+  outs() << ": ";
+
+  // Make a StringMap for faster lookup
+  StringSet<> Names;
+  for (const std::string &Name : NamedMDs)
+    Names.insert(Name);
+
+  // First collect all the metadata to delete in a vector, then
+  // delete them all at once to avoid invalidating the iterator
+  std::vector<NamedMDNode *> ToDelete;
+  ToDelete.reserve(M->named_metadata_size() - Names.size());
+  for (auto &NamedMD : M->named_metadata())
+    // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
+    if (!Names.count(NamedMD.getName()) &&
+        (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
+      ToDelete.push_back(&NamedMD);
+
+  for (auto *NamedMD : ToDelete)
+    NamedMD->eraseFromParent();
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass(/*FatalErrors=*/false));
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+    return true;
+  }
+  return false;
+}
+
+namespace {
+// Reduce the list of operands to named metadata nodes
+class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
+  BugDriver &BD;
+  BugTester TestFn;
+
+public:
+  ReduceCrashingNamedMDOps(BugDriver &bd, BugTester testFn)
+      : BD(bd), TestFn(testFn) {}
+
+  Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
+                              std::vector<const MDNode *> &Kept) override {
+    if (!Kept.empty() && TestNamedMDOps(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestNamedMDOps(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
+};
+}
+
+bool ReduceCrashingNamedMDOps::TestNamedMDOps(
+    std::vector<const MDNode *> &NamedMDOps) {
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
+  for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
+    OldMDNodeOps.insert(NamedMDOps[i]);
+  }
+
+  outs() << "Checking for crash with only " << OldMDNodeOps.size();
+  if (OldMDNodeOps.size() == 1)
+    outs() << " named metadata operand: ";
+  else
+    outs() << " named metadata operands: ";
+
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
+
+  // This is a little wasteful. In the future it might be good if we could have
+  // these dropped during cloning.
+  for (auto &NamedMD : BD.getProgram().named_metadata()) {
+    // Drop the old one and create a new one
+    M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
+    NamedMDNode *NewNamedMDNode =
+        M->getOrInsertNamedMetadata(NamedMD.getName());
+    for (MDNode *op : NamedMD.operands())
+      if (OldMDNodeOps.count(op))
+        NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
+  }
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass(/*FatalErrors=*/false));
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    // Make sure to use instruction pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    NamedMDOps.clear();
+    for (const MDNode *Node : OldMDNodeOps)
+      NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
+
+    BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
+    return true;
+  }
+  // It didn't crash, try something else.
+  return false;
+}
+
+/// Attempt to eliminate as many global initializers as possible.
+static Error ReduceGlobalInitializers(BugDriver &BD, BugTester TestFn) {
+  Module &OrigM = BD.getProgram();
+  if (OrigM.global_empty())
+    return Error::success();
+
+  // Now try to reduce the number of global variable initializers in the
+  // module to something small.
+  std::unique_ptr<Module> M = CloneModule(OrigM);
+  bool DeletedInit = false;
+
+  for (GlobalVariable &GV : M->globals()) {
+    if (GV.hasInitializer()) {
+      DeleteGlobalInitializer(&GV);
+      GV.setLinkage(GlobalValue::ExternalLinkage);
+      GV.setComdat(nullptr);
+      DeletedInit = true;
+    }
+  }
+
+  if (!DeletedInit)
+    return Error::success();
+
+  // See if the program still causes a crash...
+  outs() << "\nChecking to see if we can delete global inits: ";
+
+  if (TestFn(BD, M.get())) { // Still crashes?
+    BD.setNewProgram(std::move(M));
+    outs() << "\n*** Able to remove all global initializers!\n";
+    return Error::success();
+  }
+
+  // No longer crashes.
+  outs() << "  - Removing all global inits hides problem!\n";
+
+  std::vector<GlobalVariable *> GVs;
+  for (GlobalVariable &GV : OrigM.globals())
+    if (GV.hasInitializer())
+      GVs.push_back(&GV);
+
+  if (GVs.size() > 1 && !BugpointIsInterrupted) {
+    outs() << "\n*** Attempting to reduce the number of global initializers "
+           << "in the testcase\n";
+
+    unsigned OldSize = GVs.size();
+    Expected<bool> Result =
+        ReduceCrashingGlobalInitializers(BD, TestFn).reduceList(GVs);
+    if (Error E = Result.takeError())
+      return E;
+
+    if (GVs.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
+  }
+  return Error::success();
+}
+
+static Error ReduceInsts(BugDriver &BD, BugTester TestFn) {
+  // Attempt to delete instructions using bisection. This should help out nasty
+  // cases with large basic blocks where the problem is at one end.
+  if (!BugpointIsInterrupted) {
+    std::vector<const Instruction *> Insts;
+    for (const Function &F : BD.getProgram())
+      for (const BasicBlock &BB : F)
+        for (const Instruction &I : BB)
+          if (!I.isTerminator())
+            Insts.push_back(&I);
+
+    Expected<bool> Result =
+        ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
+    if (Error E = Result.takeError())
+      return E;
+  }
+
+  unsigned Simplification = 2;
+  do {
+    if (BugpointIsInterrupted)
+      // TODO: Should we distinguish this with an "interrupted error"?
+      return Error::success();
+    --Simplification;
+    outs() << "\n*** Attempting to reduce testcase by deleting instruc"
+           << "tions: Simplification Level #" << Simplification << '\n';
+
+    // Now that we have deleted the functions that are unnecessary for the
+    // program, try to remove instructions that are not necessary to cause the
+    // crash.  To do this, we loop through all of the instructions in the
+    // remaining functions, deleting them (replacing any values produced with
+    // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
+    // still triggers failure, keep deleting until we cannot trigger failure
+    // anymore.
+    //
+    unsigned InstructionsToSkipBeforeDeleting = 0;
+  TryAgain:
+
+    // Loop over all of the (non-terminator) instructions remaining in the
+    // function, attempting to delete them.
+    unsigned CurInstructionNum = 0;
+    for (Module::const_iterator FI = BD.getProgram().begin(),
+                                E = BD.getProgram().end();
+         FI != E; ++FI)
+      if (!FI->isDeclaration())
+        for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
+             ++BI)
+          for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
+               I != E; ++I, ++CurInstructionNum) {
+            if (InstructionsToSkipBeforeDeleting) {
+              --InstructionsToSkipBeforeDeleting;
+            } else {
+              if (BugpointIsInterrupted)
+                // TODO: Should this be some kind of interrupted error?
+                return Error::success();
+
+              if (I->isEHPad() || I->getType()->isTokenTy() ||
+                  I->isSwiftError())
+                continue;
+
+              outs() << "Checking instruction: " << *I;
+              std::unique_ptr<Module> M =
+                  BD.deleteInstructionFromProgram(&*I, Simplification);
+
+              // Find out if the pass still crashes on this pass...
+              if (TestFn(BD, M.get())) {
+                // Yup, it does, we delete the old module, and continue trying
+                // to reduce the testcase...
+                BD.setNewProgram(std::move(M));
+                InstructionsToSkipBeforeDeleting = CurInstructionNum;
+                goto TryAgain; // I wish I had a multi-level break here!
+              }
+            }
+          }
+
+    if (InstructionsToSkipBeforeDeleting) {
+      InstructionsToSkipBeforeDeleting = 0;
+      goto TryAgain;
+    }
+
+  } while (Simplification);
+
+  // Attempt to drop metadata from instructions that does not contribute to the
+  // crash.
+  if (!BugpointIsInterrupted) {
+    std::vector<Instruction *> Insts;
+    for (Function &F : BD.getProgram())
+      for (Instruction &I : instructions(F))
+        Insts.push_back(&I);
+
+    Expected<bool> Result =
+        ReduceCrashingMetadata(BD, TestFn).reduceList(Insts);
+    if (Error E = Result.takeError())
+      return E;
+  }
+
+  BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
+  return Error::success();
+}
+
+/// DebugACrash - Given a predicate that determines whether a component crashes
+/// on a program, try to destructively reduce the program while still keeping
+/// the predicate true.
+static Error DebugACrash(BugDriver &BD, BugTester TestFn) {
+  // See if we can get away with nuking some of the global variable initializers
+  // in the program...
+  if (!NoGlobalRM)
+    if (Error E = ReduceGlobalInitializers(BD, TestFn))
+      return E;
+
+  // Now try to reduce the number of functions in the module to something small.
+  std::vector<Function *> Functions;
+  for (Function &F : BD.getProgram())
+    if (!F.isDeclaration())
+      Functions.push_back(&F);
+
+  if (Functions.size() > 1 && !BugpointIsInterrupted) {
+    outs() << "\n*** Attempting to reduce the number of functions "
+              "in the testcase\n";
+
+    unsigned OldSize = Functions.size();
+    Expected<bool> Result =
+        ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
+    if (Error E = Result.takeError())
+      return E;
+
+    if (Functions.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
+  }
+
+  if (!NoAttributeRM) {
+    // For each remaining function, try to reduce that function's attributes.
+    std::vector<std::string> FunctionNames;
+    for (Function &F : BD.getProgram())
+      FunctionNames.push_back(std::string(F.getName()));
+
+    if (!FunctionNames.empty() && !BugpointIsInterrupted) {
+      outs() << "\n*** Attempting to reduce the number of function attributes"
+                " in the testcase\n";
+
+      unsigned OldSize = 0;
+      unsigned NewSize = 0;
+      for (std::string &Name : FunctionNames) {
+        Function *Fn = BD.getProgram().getFunction(Name);
+        assert(Fn && "Could not find function?");
+
+        std::vector<Attribute> Attrs;
+        for (Attribute A : Fn->getAttributes().getFnAttributes())
+          Attrs.push_back(A);
+
+        OldSize += Attrs.size();
+        Expected<bool> Result =
+          ReduceCrashingFunctionAttributes(BD, Name, TestFn).reduceList(Attrs);
+        if (Error E = Result.takeError())
+          return E;
+
+        NewSize += Attrs.size();
+      }
+
+      if (OldSize < NewSize)
+        BD.EmitProgressBitcode(BD.getProgram(), "reduced-function-attributes");
+    }
+  }
+
+  // Attempt to change conditional branches into unconditional branches to
+  // eliminate blocks.
+  if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
+    std::vector<const BasicBlock *> Blocks;
+    for (Function &F : BD.getProgram())
+      for (BasicBlock &BB : F)
+        Blocks.push_back(&BB);
+    unsigned OldSize = Blocks.size();
+    Expected<bool> Result =
+        ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
+    if (Error E = Result.takeError())
+      return E;
+    Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
+    if (Error E = Result.takeError())
+      return E;
+    if (Blocks.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
+  }
+
+  // Attempt to delete entire basic blocks at a time to speed up
+  // convergence... this actually works by setting the terminator of the blocks
+  // to a return instruction then running simplifycfg, which can potentially
+  // shrinks the code dramatically quickly
+  //
+  if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
+    std::vector<const BasicBlock *> Blocks;
+    for (Function &F : BD.getProgram())
+      for (BasicBlock &BB : F)
+        Blocks.push_back(&BB);
+    unsigned OldSize = Blocks.size();
+    Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
+    if (Error E = Result.takeError())
+      return E;
+    if (Blocks.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
+  }
+
+  if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
+    std::vector<const BasicBlock *> Blocks;
+    for (Function &F : BD.getProgram())
+      for (BasicBlock &BB : F)
+        Blocks.push_back(&BB);
+    unsigned OldSize = Blocks.size();
+    Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
+    if (Error E = Result.takeError())
+      return E;
+    if (Blocks.size() < OldSize)
+      BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
+  }
+
+  // Attempt to delete instructions using bisection. This should help out nasty
+  // cases with large basic blocks where the problem is at one end.
+  if (!BugpointIsInterrupted)
+    if (Error E = ReduceInsts(BD, TestFn))
+      return E;
+
+  // Attempt to strip debug info metadata.
+  auto stripMetadata = [&](std::function<bool(Module &)> strip) {
+    std::unique_ptr<Module> M = CloneModule(BD.getProgram());
+    strip(*M);
+    if (TestFn(BD, M.get()))
+      BD.setNewProgram(std::move(M));
+  };
+  if (!NoStripDebugInfo && !BugpointIsInterrupted) {
+    outs() << "\n*** Attempting to strip the debug info: ";
+    stripMetadata(StripDebugInfo);
+  }
+  if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
+    outs() << "\n*** Attempting to strip the debug type info: ";
+    stripMetadata(stripNonLineTableDebugInfo);
+  }
+
+  if (!NoNamedMDRM) {
+    if (!BugpointIsInterrupted) {
+      // Try to reduce the amount of global metadata (particularly debug info),
+      // by dropping global named metadata that anchors them
+      outs() << "\n*** Attempting to remove named metadata: ";
+      std::vector<std::string> NamedMDNames;
+      for (auto &NamedMD : BD.getProgram().named_metadata())
+        NamedMDNames.push_back(NamedMD.getName().str());
+      Expected<bool> Result =
+          ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
+      if (Error E = Result.takeError())
+        return E;
+    }
+
+    if (!BugpointIsInterrupted) {
+      // Now that we quickly dropped all the named metadata that doesn't
+      // contribute to the crash, bisect the operands of the remaining ones
+      std::vector<const MDNode *> NamedMDOps;
+      for (auto &NamedMD : BD.getProgram().named_metadata())
+        for (auto op : NamedMD.operands())
+          NamedMDOps.push_back(op);
+      Expected<bool> Result =
+          ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
+      if (Error E = Result.takeError())
+        return E;
+    }
+    BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
+  }
+
+  // Try to clean up the testcase by running funcresolve and globaldce...
+  if (!BugpointIsInterrupted) {
+    outs() << "\n*** Attempting to perform final cleanups: ";
+    std::unique_ptr<Module> M = CloneModule(BD.getProgram());
+    M = BD.performFinalCleanups(std::move(M), true);
+
+    // Find out if the pass still crashes on the cleaned up program...
+    if (M && TestFn(BD, M.get()))
+      BD.setNewProgram(
+          std::move(M)); // Yup, it does, keep the reduced version...
+  }
+
+  BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
+
+  return Error::success();
+}
+
+static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
+  return BD.runPasses(*M, BD.getPassesToRun());
+}
+
+/// debugOptimizerCrash - This method is called when some pass crashes on input.
+/// It attempts to prune down the testcase to something reasonable, and figure
+/// out exactly which pass is crashing.
+///
+Error BugDriver::debugOptimizerCrash(const std::string &ID) {
+  outs() << "\n*** Debugging optimizer crash!\n";
+
+  // Reduce the list of passes which causes the optimizer to crash...
+  if (!BugpointIsInterrupted && !DontReducePassList) {
+    Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
+    if (Error E = Result.takeError())
+      return E;
+  }
+
+  outs() << "\n*** Found crashing pass"
+         << (PassesToRun.size() == 1 ? ": " : "es: ")
+         << getPassesString(PassesToRun) << '\n';
+
+  EmitProgressBitcode(*Program, ID);
+
+  auto Res = DebugACrash(*this, TestForOptimizerCrash);
+  if (Res || DontReducePassList)
+    return Res;
+  // Try to reduce the pass list again. This covers additional cases
+  // we failed to reduce earlier, because of more complex pass dependencies
+  // triggering the crash.
+  auto SecondRes = ReducePassList(*this).reduceList(PassesToRun);
+  if (Error E = SecondRes.takeError())
+    return E;
+  outs() << "\n*** Found crashing pass"
+         << (PassesToRun.size() == 1 ? ": " : "es: ")
+         << getPassesString(PassesToRun) << '\n';
+
+  EmitProgressBitcode(getProgram(), "reduced-simplified");
+  return Res;
+}
+
+static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
+  if (Error E = BD.compileProgram(*M)) {
+    if (VerboseErrors)
+      errs() << toString(std::move(E)) << "\n";
+    else {
+      consumeError(std::move(E));
+      errs() << "<crash>\n";
+    }
+    return true; // Tool is still crashing.
+  }
+  errs() << '\n';
+  return false;
+}
+
+/// debugCodeGeneratorCrash - This method is called when the code generator
+/// crashes on an input.  It attempts to reduce the input as much as possible
+/// while still causing the code generator to crash.
+Error BugDriver::debugCodeGeneratorCrash() {
+  errs() << "*** Debugging code generator crash!\n";
+
+  return DebugACrash(*this, TestForCodeGenCrash);
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/ExecutionDriver.cpp b/contrib/libs/llvm12/tools/bugpoint/ExecutionDriver.cpp
new file mode 100644
index 0000000000..f06f378962
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/ExecutionDriver.cpp
@@ -0,0 +1,457 @@
+//===- ExecutionDriver.cpp - Allow execution of LLVM program --------------===//
+//
+// 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 code used to execute the program utilizing one of the
+// various ways of running LLVM bitcode.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ToolRunner.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/SystemUtils.h"
+#include "llvm/Support/raw_ostream.h"
+#include <fstream>
+
+using namespace llvm;
+
+namespace {
+// OutputType - Allow the user to specify the way code should be run, to test
+// for miscompilation.
+//
+enum OutputType {
+  AutoPick,
+  RunLLI,
+  RunJIT,
+  RunLLC,
+  RunLLCIA,
+  CompileCustom,
+  Custom
+};
+
+cl::opt<double> AbsTolerance("abs-tolerance",
+                             cl::desc("Absolute error tolerated"),
+                             cl::init(0.0));
+cl::opt<double> RelTolerance("rel-tolerance",
+                             cl::desc("Relative error tolerated"),
+                             cl::init(0.0));
+
+cl::opt<OutputType> InterpreterSel(
+    cl::desc("Specify the \"test\" i.e. suspect back-end:"),
+    cl::values(clEnumValN(AutoPick, "auto", "Use best guess"),
+               clEnumValN(RunLLI, "run-int", "Execute with the interpreter"),
+               clEnumValN(RunJIT, "run-jit", "Execute with JIT"),
+               clEnumValN(RunLLC, "run-llc", "Compile with LLC"),
+               clEnumValN(RunLLCIA, "run-llc-ia",
+                          "Compile with LLC with integrated assembler"),
+               clEnumValN(CompileCustom, "compile-custom",
+                          "Use -compile-command to define a command to "
+                          "compile the bitcode. Useful to avoid linking."),
+               clEnumValN(Custom, "run-custom",
+                          "Use -exec-command to define a command to execute "
+                          "the bitcode. Useful for cross-compilation.")),
+    cl::init(AutoPick));
+
+cl::opt<OutputType> SafeInterpreterSel(
+    cl::desc("Specify \"safe\" i.e. known-good backend:"),
+    cl::values(clEnumValN(AutoPick, "safe-auto", "Use best guess"),
+               clEnumValN(RunLLC, "safe-run-llc", "Compile with LLC"),
+               clEnumValN(Custom, "safe-run-custom",
+                          "Use -exec-command to define a command to execute "
+                          "the bitcode. Useful for cross-compilation.")),
+    cl::init(AutoPick));
+
+cl::opt<std::string> SafeInterpreterPath(
+    "safe-path", cl::desc("Specify the path to the \"safe\" backend program"),
+    cl::init(""));
+
+cl::opt<bool> AppendProgramExitCode(
+    "append-exit-code",
+    cl::desc("Append the exit code to the output so it gets diff'd too"),
+    cl::init(false));
+
+cl::opt<std::string>
+    InputFile("input", cl::init("/dev/null"),
+              cl::desc("Filename to pipe in as stdin (default: /dev/null)"));
+
+cl::list<std::string>
+    AdditionalSOs("additional-so", cl::desc("Additional shared objects to load "
+                                            "into executing programs"));
+
+cl::list<std::string> AdditionalLinkerArgs(
+    "Xlinker", cl::desc("Additional arguments to pass to the linker"));
+
+cl::opt<std::string> CustomCompileCommand(
+    "compile-command", cl::init("llc"),
+    cl::desc("Command to compile the bitcode (use with -compile-custom) "
+             "(default: llc)"));
+
+cl::opt<std::string> CustomExecCommand(
+    "exec-command", cl::init("simulate"),
+    cl::desc("Command to execute the bitcode (use with -run-custom) "
+             "(default: simulate)"));
+}
+
+namespace llvm {
+// Anything specified after the --args option are taken as arguments to the
+// program being debugged.
+cl::list<std::string> InputArgv("args", cl::Positional,
+                                cl::desc("<program arguments>..."),
+                                cl::ZeroOrMore, cl::PositionalEatsArgs);
+
+cl::opt<std::string>
+    OutputPrefix("output-prefix", cl::init("bugpoint"),
+                 cl::desc("Prefix to use for outputs (default: 'bugpoint')"));
+}
+
+namespace {
+cl::list<std::string> ToolArgv("tool-args", cl::Positional,
+                               cl::desc("<tool arguments>..."), cl::ZeroOrMore,
+                               cl::PositionalEatsArgs);
+
+cl::list<std::string> SafeToolArgv("safe-tool-args", cl::Positional,
+                                   cl::desc("<safe-tool arguments>..."),
+                                   cl::ZeroOrMore, cl::PositionalEatsArgs);
+
+cl::opt<std::string> CCBinary("gcc", cl::init(""),
+                              cl::desc("The gcc binary to use."));
+
+cl::list<std::string> CCToolArgv("gcc-tool-args", cl::Positional,
+                                 cl::desc("<gcc-tool arguments>..."),
+                                 cl::ZeroOrMore, cl::PositionalEatsArgs);
+}
+
+//===----------------------------------------------------------------------===//
+// BugDriver method implementation
+//
+
+/// initializeExecutionEnvironment - This method is used to set up the
+/// environment for executing LLVM programs.
+///
+Error BugDriver::initializeExecutionEnvironment() {
+  outs() << "Initializing execution environment: ";
+
+  // Create an instance of the AbstractInterpreter interface as specified on
+  // the command line
+  SafeInterpreter = nullptr;
+  std::string Message;
+
+  if (CCBinary.empty()) {
+    if (ErrorOr<std::string> ClangPath =
+            FindProgramByName("clang", getToolName(), &AbsTolerance))
+      CCBinary = *ClangPath;
+    else
+      CCBinary = "gcc";
+  }
+
+  switch (InterpreterSel) {
+  case AutoPick:
+    if (!Interpreter) {
+      InterpreterSel = RunJIT;
+      Interpreter =
+          AbstractInterpreter::createJIT(getToolName(), Message, &ToolArgv);
+    }
+    if (!Interpreter) {
+      InterpreterSel = RunLLC;
+      Interpreter = AbstractInterpreter::createLLC(
+          getToolName(), Message, CCBinary, &ToolArgv, &CCToolArgv);
+    }
+    if (!Interpreter) {
+      InterpreterSel = RunLLI;
+      Interpreter =
+          AbstractInterpreter::createLLI(getToolName(), Message, &ToolArgv);
+    }
+    if (!Interpreter) {
+      InterpreterSel = AutoPick;
+      Message = "Sorry, I can't automatically select an interpreter!\n";
+    }
+    break;
+  case RunLLI:
+    Interpreter =
+        AbstractInterpreter::createLLI(getToolName(), Message, &ToolArgv);
+    break;
+  case RunLLC:
+  case RunLLCIA:
+    Interpreter = AbstractInterpreter::createLLC(
+        getToolName(), Message, CCBinary, &ToolArgv, &CCToolArgv,
+        InterpreterSel == RunLLCIA);
+    break;
+  case RunJIT:
+    Interpreter =
+        AbstractInterpreter::createJIT(getToolName(), Message, &ToolArgv);
+    break;
+  case CompileCustom:
+    Interpreter = AbstractInterpreter::createCustomCompiler(
+        getToolName(), Message, CustomCompileCommand);
+    break;
+  case Custom:
+    Interpreter = AbstractInterpreter::createCustomExecutor(
+        getToolName(), Message, CustomExecCommand);
+    break;
+  }
+  if (!Interpreter)
+    errs() << Message;
+  else // Display informational messages on stdout instead of stderr
+    outs() << Message;
+
+  std::string Path = SafeInterpreterPath;
+  if (Path.empty())
+    Path = getToolName();
+  std::vector<std::string> SafeToolArgs = SafeToolArgv;
+  switch (SafeInterpreterSel) {
+  case AutoPick:
+    // In "llc-safe" mode, default to using LLC as the "safe" backend.
+    if (InterpreterSel == RunLLC) {
+      SafeInterpreterSel = RunLLC;
+      SafeToolArgs.push_back("--relocation-model=pic");
+      SafeInterpreter = AbstractInterpreter::createLLC(
+          Path.c_str(), Message, CCBinary, &SafeToolArgs, &CCToolArgv);
+    } else if (InterpreterSel != CompileCustom) {
+      SafeInterpreterSel = AutoPick;
+      Message = "Sorry, I can't automatically select a safe interpreter!\n";
+    }
+    break;
+  case RunLLC:
+  case RunLLCIA:
+    SafeToolArgs.push_back("--relocation-model=pic");
+    SafeInterpreter = AbstractInterpreter::createLLC(
+        Path.c_str(), Message, CCBinary, &SafeToolArgs, &CCToolArgv,
+        SafeInterpreterSel == RunLLCIA);
+    break;
+  case Custom:
+    SafeInterpreter = AbstractInterpreter::createCustomExecutor(
+        getToolName(), Message, CustomExecCommand);
+    break;
+  default:
+    Message = "Sorry, this back-end is not supported by bugpoint as the "
+              "\"safe\" backend right now!\n";
+    break;
+  }
+  if (!SafeInterpreter && InterpreterSel != CompileCustom) {
+    outs() << Message << "\nExiting.\n";
+    exit(1);
+  }
+
+  cc = CC::create(getToolName(), Message, CCBinary, &CCToolArgv);
+  if (!cc) {
+    outs() << Message << "\nExiting.\n";
+    exit(1);
+  }
+
+  // If there was an error creating the selected interpreter, quit with error.
+  if (Interpreter == nullptr)
+    return make_error<StringError>("Failed to init execution environment",
+                                   inconvertibleErrorCode());
+  return Error::success();
+}
+
+/// Try to compile the specified module, returning false and setting Error if an
+/// error occurs.  This is used for code generation crash testing.
+Error BugDriver::compileProgram(Module &M) const {
+  // Emit the program to a bitcode file...
+  auto Temp =
+      sys::fs::TempFile::create(OutputPrefix + "-test-program-%%%%%%%.bc");
+  if (!Temp) {
+    errs() << ToolName
+           << ": Error making unique filename: " << toString(Temp.takeError())
+           << "\n";
+    exit(1);
+  }
+  DiscardTemp Discard{*Temp};
+  if (writeProgramToFile(Temp->FD, M)) {
+    errs() << ToolName << ": Error emitting bitcode to file '" << Temp->TmpName
+           << "'!\n";
+    exit(1);
+  }
+
+  // Actually compile the program!
+  return Interpreter->compileProgram(Temp->TmpName, Timeout, MemoryLimit);
+}
+
+/// This method runs "Program", capturing the output of the program to a file,
+/// returning the filename of the file.  A recommended filename may be
+/// optionally specified.
+Expected<std::string> BugDriver::executeProgram(const Module &Program,
+                                                std::string OutputFile,
+                                                std::string BitcodeFile,
+                                                const std::string &SharedObj,
+                                                AbstractInterpreter *AI) const {
+  if (!AI)
+    AI = Interpreter;
+  assert(AI && "Interpreter should have been created already!");
+  bool CreatedBitcode = false;
+  if (BitcodeFile.empty()) {
+    // Emit the program to a bitcode file...
+    SmallString<128> UniqueFilename;
+    int UniqueFD;
+    std::error_code EC = sys::fs::createUniqueFile(
+        OutputPrefix + "-test-program-%%%%%%%.bc", UniqueFD, UniqueFilename);
+    if (EC) {
+      errs() << ToolName << ": Error making unique filename: " << EC.message()
+             << "!\n";
+      exit(1);
+    }
+    BitcodeFile = std::string(UniqueFilename.str());
+
+    if (writeProgramToFile(BitcodeFile, UniqueFD, Program)) {
+      errs() << ToolName << ": Error emitting bitcode to file '" << BitcodeFile
+             << "'!\n";
+      exit(1);
+    }
+    CreatedBitcode = true;
+  }
+
+  // Remove the temporary bitcode file when we are done.
+  std::string BitcodePath(BitcodeFile);
+  FileRemover BitcodeFileRemover(BitcodePath, CreatedBitcode && !SaveTemps);
+
+  if (OutputFile.empty())
+    OutputFile = OutputPrefix + "-execution-output-%%%%%%%";
+
+  // Check to see if this is a valid output filename...
+  SmallString<128> UniqueFile;
+  std::error_code EC = sys::fs::createUniqueFile(OutputFile, UniqueFile);
+  if (EC) {
+    errs() << ToolName << ": Error making unique filename: " << EC.message()
+           << "\n";
+    exit(1);
+  }
+  OutputFile = std::string(UniqueFile.str());
+
+  // Figure out which shared objects to run, if any.
+  std::vector<std::string> SharedObjs(AdditionalSOs);
+  if (!SharedObj.empty())
+    SharedObjs.push_back(SharedObj);
+
+  Expected<int> RetVal = AI->ExecuteProgram(BitcodeFile, InputArgv, InputFile,
+                                            OutputFile, AdditionalLinkerArgs,
+                                            SharedObjs, Timeout, MemoryLimit);
+  if (Error E = RetVal.takeError())
+    return std::move(E);
+
+  if (*RetVal == -1) {
+    errs() << "<timeout>";
+    static bool FirstTimeout = true;
+    if (FirstTimeout) {
+      outs()
+          << "\n"
+             "*** Program execution timed out!  This mechanism is designed to "
+             "handle\n"
+             "    programs stuck in infinite loops gracefully.  The -timeout "
+             "option\n"
+             "    can be used to change the timeout threshold or disable it "
+             "completely\n"
+             "    (with -timeout=0).  This message is only displayed once.\n";
+      FirstTimeout = false;
+    }
+  }
+
+  if (AppendProgramExitCode) {
+    std::ofstream outFile(OutputFile.c_str(), std::ios_base::app);
+    outFile << "exit " << *RetVal << '\n';
+    outFile.close();
+  }
+
+  // Return the filename we captured the output to.
+  return OutputFile;
+}
+
+/// Used to create reference output with the "safe" backend, if reference output
+/// is not provided.
+Expected<std::string>
+BugDriver::executeProgramSafely(const Module &Program,
+                                const std::string &OutputFile) const {
+  return executeProgram(Program, OutputFile, "", "", SafeInterpreter);
+}
+
+Expected<std::string>
+BugDriver::compileSharedObject(const std::string &BitcodeFile) {
+  assert(Interpreter && "Interpreter should have been created already!");
+  std::string OutputFile;
+
+  // Using the known-good backend.
+  Expected<CC::FileType> FT =
+      SafeInterpreter->OutputCode(BitcodeFile, OutputFile);
+  if (Error E = FT.takeError())
+    return std::move(E);
+
+  std::string SharedObjectFile;
+  if (Error E = cc->MakeSharedObject(OutputFile, *FT, SharedObjectFile,
+                                     AdditionalLinkerArgs))
+    return std::move(E);
+
+  // Remove the intermediate C file
+  sys::fs::remove(OutputFile);
+
+  return SharedObjectFile;
+}
+
+/// Calls compileProgram and then records the output into ReferenceOutputFile.
+/// Returns true if reference file created, false otherwise. Note:
+/// initializeExecutionEnvironment should be called BEFORE this function.
+Error BugDriver::createReferenceFile(Module &M, const std::string &Filename) {
+  if (Error E = compileProgram(*Program))
+    return E;
+
+  Expected<std::string> Result = executeProgramSafely(*Program, Filename);
+  if (Error E = Result.takeError()) {
+    if (Interpreter != SafeInterpreter) {
+      E = joinErrors(
+              std::move(E),
+              make_error<StringError>(
+                  "*** There is a bug running the \"safe\" backend.  Either"
+                  " debug it (for example with the -run-jit bugpoint option,"
+                  " if JIT is being used as the \"safe\" backend), or fix the"
+                  " error some other way.\n",
+                  inconvertibleErrorCode()));
+    }
+    return E;
+  }
+  ReferenceOutputFile = *Result;
+  outs() << "\nReference output is: " << ReferenceOutputFile << "\n\n";
+  return Error::success();
+}
+
+/// This method executes the specified module and diffs the output against the
+/// file specified by ReferenceOutputFile.  If the output is different, 1 is
+/// returned.  If there is a problem with the code generator (e.g., llc
+/// crashes), this will set ErrMsg.
+Expected<bool> BugDriver::diffProgram(const Module &Program,
+                                      const std::string &BitcodeFile,
+                                      const std::string &SharedObject,
+                                      bool RemoveBitcode) const {
+  // Execute the program, generating an output file...
+  Expected<std::string> Output =
+      executeProgram(Program, "", BitcodeFile, SharedObject, nullptr);
+  if (Error E = Output.takeError())
+    return std::move(E);
+
+  std::string Error;
+  bool FilesDifferent = false;
+  if (int Diff = DiffFilesWithTolerance(ReferenceOutputFile, *Output,
+                                        AbsTolerance, RelTolerance, &Error)) {
+    if (Diff == 2) {
+      errs() << "While diffing output: " << Error << '\n';
+      exit(1);
+    }
+    FilesDifferent = true;
+  } else {
+    // Remove the generated output if there are no differences.
+    sys::fs::remove(*Output);
+  }
+
+  // Remove the bitcode file if we are supposed to.
+  if (RemoveBitcode)
+    sys::fs::remove(BitcodeFile);
+  return FilesDifferent;
+}
+
+bool BugDriver::isExecutingJIT() { return InterpreterSel == RunJIT; }
diff --git a/contrib/libs/llvm12/tools/bugpoint/ExtractFunction.cpp b/contrib/libs/llvm12/tools/bugpoint/ExtractFunction.cpp
new file mode 100644
index 0000000000..7a75cb90ed
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/ExtractFunction.cpp
@@ -0,0 +1,420 @@
+//===- ExtractFunction.cpp - Extract a function from Program --------------===//
+//
+// 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 several methods that are used to extract functions,
+// loops, or portions of a module from the rest of the module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/CodeExtractor.h"
+#include <set>
+using namespace llvm;
+
+#define DEBUG_TYPE "bugpoint"
+
+namespace llvm {
+bool DisableSimplifyCFG = false;
+extern cl::opt<std::string> OutputPrefix;
+} // End llvm namespace
+
+namespace {
+cl::opt<bool> NoDCE("disable-dce",
+                    cl::desc("Do not use the -dce pass to reduce testcases"));
+cl::opt<bool, true>
+    NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG),
+           cl::desc("Do not use the -simplifycfg pass to reduce testcases"));
+
+Function *globalInitUsesExternalBA(GlobalVariable *GV) {
+  if (!GV->hasInitializer())
+    return nullptr;
+
+  Constant *I = GV->getInitializer();
+
+  // walk the values used by the initializer
+  // (and recurse into things like ConstantExpr)
+  std::vector<Constant *> Todo;
+  std::set<Constant *> Done;
+  Todo.push_back(I);
+
+  while (!Todo.empty()) {
+    Constant *V = Todo.back();
+    Todo.pop_back();
+    Done.insert(V);
+
+    if (BlockAddress *BA = dyn_cast<BlockAddress>(V)) {
+      Function *F = BA->getFunction();
+      if (F->isDeclaration())
+        return F;
+    }
+
+    for (User::op_iterator i = V->op_begin(), e = V->op_end(); i != e; ++i) {
+      Constant *C = dyn_cast<Constant>(*i);
+      if (C && !isa<GlobalValue>(C) && !Done.count(C))
+        Todo.push_back(C);
+    }
+  }
+  return nullptr;
+}
+} // end anonymous namespace
+
+std::unique_ptr<Module>
+BugDriver::deleteInstructionFromProgram(const Instruction *I,
+                                        unsigned Simplification) {
+  // FIXME, use vmap?
+  std::unique_ptr<Module> Clone = CloneModule(*Program);
+
+  const BasicBlock *PBB = I->getParent();
+  const Function *PF = PBB->getParent();
+
+  Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn
+  std::advance(
+      RFI, std::distance(PF->getParent()->begin(), Module::const_iterator(PF)));
+
+  Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB
+  std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB)));
+
+  BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst
+  std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I)));
+  Instruction *TheInst = &*RI; // Got the corresponding instruction!
+
+  // If this instruction produces a value, replace any users with null values
+  if (!TheInst->getType()->isVoidTy())
+    TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType()));
+
+  // Remove the instruction from the program.
+  TheInst->getParent()->getInstList().erase(TheInst);
+
+  // Spiff up the output a little bit.
+  std::vector<std::string> Passes;
+
+  /// Can we get rid of the -disable-* options?
+  if (Simplification > 1 && !NoDCE)
+    Passes.push_back("dce");
+  if (Simplification && !DisableSimplifyCFG)
+    Passes.push_back("simplifycfg"); // Delete dead control flow
+
+  Passes.push_back("verify");
+  std::unique_ptr<Module> New = runPassesOn(Clone.get(), Passes);
+  if (!New) {
+    errs() << "Instruction removal failed.  Sorry. :(  Please report a bug!\n";
+    exit(1);
+  }
+  return New;
+}
+
+std::unique_ptr<Module>
+BugDriver::performFinalCleanups(std::unique_ptr<Module> M,
+                                bool MayModifySemantics) {
+  // Make all functions external, so GlobalDCE doesn't delete them...
+  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
+    I->setLinkage(GlobalValue::ExternalLinkage);
+
+  std::vector<std::string> CleanupPasses;
+  CleanupPasses.push_back("globaldce");
+
+  if (MayModifySemantics)
+    CleanupPasses.push_back("deadarghaX0r");
+  else
+    CleanupPasses.push_back("deadargelim");
+
+  std::unique_ptr<Module> New = runPassesOn(M.get(), CleanupPasses);
+  if (!New) {
+    errs() << "Final cleanups failed.  Sorry. :(  Please report a bug!\n";
+    return nullptr;
+  }
+  return New;
+}
+
+std::unique_ptr<Module> BugDriver::extractLoop(Module *M) {
+  std::vector<std::string> LoopExtractPasses;
+  LoopExtractPasses.push_back("loop-extract-single");
+
+  std::unique_ptr<Module> NewM = runPassesOn(M, LoopExtractPasses);
+  if (!NewM) {
+    outs() << "*** Loop extraction failed: ";
+    EmitProgressBitcode(*M, "loopextraction", true);
+    outs() << "*** Sorry. :(  Please report a bug!\n";
+    return nullptr;
+  }
+
+  // Check to see if we created any new functions.  If not, no loops were
+  // extracted and we should return null.  Limit the number of loops we extract
+  // to avoid taking forever.
+  static unsigned NumExtracted = 32;
+  if (M->size() == NewM->size() || --NumExtracted == 0) {
+    return nullptr;
+  } else {
+    assert(M->size() < NewM->size() && "Loop extract removed functions?");
+    Module::iterator MI = NewM->begin();
+    for (unsigned i = 0, e = M->size(); i != e; ++i)
+      ++MI;
+  }
+
+  return NewM;
+}
+
+static void eliminateAliases(GlobalValue *GV) {
+  // First, check whether a GlobalAlias references this definition.
+  // GlobalAlias MAY NOT reference declarations.
+  for (;;) {
+    // 1. Find aliases
+    SmallVector<GlobalAlias *, 1> aliases;
+    Module *M = GV->getParent();
+    for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end();
+         I != E; ++I)
+      if (I->getAliasee()->stripPointerCasts() == GV)
+        aliases.push_back(&*I);
+    if (aliases.empty())
+      break;
+    // 2. Resolve aliases
+    for (unsigned i = 0, e = aliases.size(); i < e; ++i) {
+      aliases[i]->replaceAllUsesWith(aliases[i]->getAliasee());
+      aliases[i]->eraseFromParent();
+    }
+    // 3. Repeat until no more aliases found; there might
+    // be an alias to an alias...
+  }
+}
+
+//
+// DeleteGlobalInitializer - "Remove" the global variable by deleting its
+// initializer,
+// making it external.
+//
+void llvm::DeleteGlobalInitializer(GlobalVariable *GV) {
+  eliminateAliases(GV);
+  GV->setInitializer(nullptr);
+  GV->setComdat(nullptr);
+}
+
+// DeleteFunctionBody - "Remove" the function by deleting all of its basic
+// blocks, making it external.
+//
+void llvm::DeleteFunctionBody(Function *F) {
+  eliminateAliases(F);
+  // Function declarations can't have comdats.
+  F->setComdat(nullptr);
+
+  // delete the body of the function...
+  F->deleteBody();
+  assert(F->isDeclaration() && "This didn't make the function external!");
+}
+
+/// GetTorInit - Given a list of entries for static ctors/dtors, return them
+/// as a constant array.
+static Constant *GetTorInit(std::vector<std::pair<Function *, int>> &TorList) {
+  assert(!TorList.empty() && "Don't create empty tor list!");
+  std::vector<Constant *> ArrayElts;
+  Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext());
+
+  StructType *STy = StructType::get(Int32Ty, TorList[0].first->getType());
+  for (unsigned i = 0, e = TorList.size(); i != e; ++i) {
+    Constant *Elts[] = {ConstantInt::get(Int32Ty, TorList[i].second),
+                        TorList[i].first};
+    ArrayElts.push_back(ConstantStruct::get(STy, Elts));
+  }
+  return ConstantArray::get(
+      ArrayType::get(ArrayElts[0]->getType(), ArrayElts.size()), ArrayElts);
+}
+
+/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and
+/// M1 has all of the global variables.  If M2 contains any functions that are
+/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and
+/// prune appropriate entries out of M1s list.
+static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2,
+                                ValueToValueMapTy &VMap) {
+  GlobalVariable *GV = M1->getNamedGlobal(GlobalName);
+  if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || !GV->use_empty())
+    return;
+
+  std::vector<std::pair<Function *, int>> M1Tors, M2Tors;
+  ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer());
+  if (!InitList)
+    return;
+
+  for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) {
+    if (ConstantStruct *CS =
+            dyn_cast<ConstantStruct>(InitList->getOperand(i))) {
+      if (CS->getNumOperands() != 2)
+        return; // Not array of 2-element structs.
+
+      if (CS->getOperand(1)->isNullValue())
+        break; // Found a null terminator, stop here.
+
+      ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0));
+      int Priority = CI ? CI->getSExtValue() : 0;
+
+      Constant *FP = CS->getOperand(1);
+      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP))
+        if (CE->isCast())
+          FP = CE->getOperand(0);
+      if (Function *F = dyn_cast<Function>(FP)) {
+        if (!F->isDeclaration())
+          M1Tors.push_back(std::make_pair(F, Priority));
+        else {
+          // Map to M2's version of the function.
+          F = cast<Function>(VMap[F]);
+          M2Tors.push_back(std::make_pair(F, Priority));
+        }
+      }
+    }
+  }
+
+  GV->eraseFromParent();
+  if (!M1Tors.empty()) {
+    Constant *M1Init = GetTorInit(M1Tors);
+    new GlobalVariable(*M1, M1Init->getType(), false,
+                       GlobalValue::AppendingLinkage, M1Init, GlobalName);
+  }
+
+  GV = M2->getNamedGlobal(GlobalName);
+  assert(GV && "Not a clone of M1?");
+  assert(GV->use_empty() && "llvm.ctors shouldn't have uses!");
+
+  GV->eraseFromParent();
+  if (!M2Tors.empty()) {
+    Constant *M2Init = GetTorInit(M2Tors);
+    new GlobalVariable(*M2, M2Init->getType(), false,
+                       GlobalValue::AppendingLinkage, M2Init, GlobalName);
+  }
+}
+
+std::unique_ptr<Module>
+llvm::SplitFunctionsOutOfModule(Module *M, const std::vector<Function *> &F,
+                                ValueToValueMapTy &VMap) {
+  // Make sure functions & globals are all external so that linkage
+  // between the two modules will work.
+  for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
+    I->setLinkage(GlobalValue::ExternalLinkage);
+  for (Module::global_iterator I = M->global_begin(), E = M->global_end();
+       I != E; ++I) {
+    if (I->hasName() && I->getName()[0] == '\01')
+      I->setName(I->getName().substr(1));
+    I->setLinkage(GlobalValue::ExternalLinkage);
+  }
+
+  ValueToValueMapTy NewVMap;
+  std::unique_ptr<Module> New = CloneModule(*M, NewVMap);
+
+  // Remove the Test functions from the Safe module
+  std::set<Function *> TestFunctions;
+  for (unsigned i = 0, e = F.size(); i != e; ++i) {
+    Function *TNOF = cast<Function>(VMap[F[i]]);
+    LLVM_DEBUG(errs() << "Removing function ");
+    LLVM_DEBUG(TNOF->printAsOperand(errs(), false));
+    LLVM_DEBUG(errs() << "\n");
+    TestFunctions.insert(cast<Function>(NewVMap[TNOF]));
+    DeleteFunctionBody(TNOF); // Function is now external in this module!
+  }
+
+  // Remove the Safe functions from the Test module
+  for (Function &I : *New)
+    if (!TestFunctions.count(&I))
+      DeleteFunctionBody(&I);
+
+  // Try to split the global initializers evenly
+  for (GlobalVariable &I : M->globals()) {
+    GlobalVariable *GV = cast<GlobalVariable>(NewVMap[&I]);
+    if (Function *TestFn = globalInitUsesExternalBA(&I)) {
+      if (Function *SafeFn = globalInitUsesExternalBA(GV)) {
+        errs() << "*** Error: when reducing functions, encountered "
+                  "the global '";
+        GV->printAsOperand(errs(), false);
+        errs() << "' with an initializer that references blockaddresses "
+                  "from safe function '"
+               << SafeFn->getName() << "' and from test function '"
+               << TestFn->getName() << "'.\n";
+        exit(1);
+      }
+      DeleteGlobalInitializer(&I); // Delete the initializer to make it external
+    } else {
+      // If we keep it in the safe module, then delete it in the test module
+      DeleteGlobalInitializer(GV);
+    }
+  }
+
+  // Make sure that there is a global ctor/dtor array in both halves of the
+  // module if they both have static ctor/dtor functions.
+  SplitStaticCtorDtor("llvm.global_ctors", M, New.get(), NewVMap);
+  SplitStaticCtorDtor("llvm.global_dtors", M, New.get(), NewVMap);
+
+  return New;
+}
+
+//===----------------------------------------------------------------------===//
+// Basic Block Extraction Code
+//===----------------------------------------------------------------------===//
+
+std::unique_ptr<Module>
+BugDriver::extractMappedBlocksFromModule(const std::vector<BasicBlock *> &BBs,
+                                         Module *M) {
+  auto Temp = sys::fs::TempFile::create(OutputPrefix + "-extractblocks%%%%%%%");
+  if (!Temp) {
+    outs() << "*** Basic Block extraction failed!\n";
+    errs() << "Error creating temporary file: " << toString(Temp.takeError())
+           << "\n";
+    EmitProgressBitcode(*M, "basicblockextractfail", true);
+    return nullptr;
+  }
+  DiscardTemp Discard{*Temp};
+
+  // Extract all of the blocks except the ones in BBs.
+  SmallVector<BasicBlock *, 32> BlocksToExtract;
+  for (Function &F : *M)
+    for (BasicBlock &BB : F)
+      // Check if this block is going to be extracted.
+      if (!llvm::is_contained(BBs, &BB))
+        BlocksToExtract.push_back(&BB);
+
+  raw_fd_ostream OS(Temp->FD, /*shouldClose*/ false);
+  for (BasicBlock *BB : BBs) {
+    // If the BB doesn't have a name, give it one so we have something to key
+    // off of.
+    if (!BB->hasName())
+      BB->setName("tmpbb");
+    OS << BB->getParent()->getName() << " " << BB->getName() << "\n";
+  }
+  OS.flush();
+  if (OS.has_error()) {
+    errs() << "Error writing list of blocks to not extract\n";
+    EmitProgressBitcode(*M, "basicblockextractfail", true);
+    OS.clear_error();
+    return nullptr;
+  }
+
+  std::string uniqueFN = "--extract-blocks-file=";
+  uniqueFN += Temp->TmpName;
+
+  std::vector<std::string> PI;
+  PI.push_back("extract-blocks");
+  std::unique_ptr<Module> Ret = runPassesOn(M, PI, {uniqueFN});
+
+  if (!Ret) {
+    outs() << "*** Basic Block extraction failed, please report a bug!\n";
+    EmitProgressBitcode(*M, "basicblockextractfail", true);
+  }
+  return Ret;
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/FindBugs.cpp b/contrib/libs/llvm12/tools/bugpoint/FindBugs.cpp
new file mode 100644
index 0000000000..2b1146da96
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/FindBugs.cpp
@@ -0,0 +1,99 @@
+//===-- FindBugs.cpp - Run Many Different Optimizations -------------------===//
+//
+// 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 defines an interface that allows bugpoint to choose different
+// combinations of optimizations to run on the selected input. Bugpoint will
+// run these optimizations and record the success/failure of each. This way
+// we can hopefully spot bugs in the optimizations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+#include <random>
+using namespace llvm;
+
+Error
+BugDriver::runManyPasses(const std::vector<std::string> &AllPasses) {
+  setPassesToRun(AllPasses);
+  outs() << "Starting bug finding procedure...\n\n";
+
+  // Creating a reference output if necessary
+  if (Error E = initializeExecutionEnvironment())
+    return E;
+
+  outs() << "\n";
+  if (ReferenceOutputFile.empty()) {
+    outs() << "Generating reference output from raw program: \n";
+    if (Error E = createReferenceFile(*Program))
+      return E;
+  }
+
+  std::mt19937 randomness(std::random_device{}());
+  unsigned num = 1;
+  while (1) {
+    //
+    // Step 1: Randomize the order of the optimizer passes.
+    //
+    std::shuffle(PassesToRun.begin(), PassesToRun.end(), randomness);
+
+    //
+    // Step 2: Run optimizer passes on the program and check for success.
+    //
+    outs() << "Running selected passes on program to test for crash: ";
+    for (int i = 0, e = PassesToRun.size(); i != e; i++) {
+      outs() << "-" << PassesToRun[i] << " ";
+    }
+
+    std::string Filename;
+    if (runPasses(*Program, PassesToRun, Filename, false)) {
+      outs() << "\n";
+      outs() << "Optimizer passes caused failure!\n\n";
+      return debugOptimizerCrash();
+    } else {
+      outs() << "Combination " << num << " optimized successfully!\n";
+    }
+
+    //
+    // Step 3: Compile the optimized code.
+    //
+    outs() << "Running the code generator to test for a crash: ";
+    if (Error E = compileProgram(*Program)) {
+      outs() << "\n*** compileProgram threw an exception: ";
+      outs() << toString(std::move(E));
+      return debugCodeGeneratorCrash();
+    }
+    outs() << '\n';
+
+    //
+    // Step 4: Run the program and compare its output to the reference
+    // output (created above).
+    //
+    outs() << "*** Checking if passes caused miscompliation:\n";
+    Expected<bool> Diff = diffProgram(*Program, Filename, "", false);
+    if (Error E = Diff.takeError()) {
+      errs() << toString(std::move(E));
+      return debugCodeGeneratorCrash();
+    }
+    if (*Diff) {
+      outs() << "\n*** diffProgram returned true!\n";
+      Error E = debugMiscompilation();
+      if (!E)
+        return Error::success();
+    }
+    outs() << "\n*** diff'd output matches!\n";
+
+    sys::fs::remove(Filename);
+
+    outs() << "\n\n";
+    num++;
+  } // end while
+
+  // Unreachable.
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/ListReducer.h b/contrib/libs/llvm12/tools/bugpoint/ListReducer.h
new file mode 100644
index 0000000000..04f2207a31
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/ListReducer.h
@@ -0,0 +1,208 @@
+//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This class is to be used as a base class for operations that want to zero in
+// on a subset of the input which still causes the bug we are tracking.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
+#define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
+
+#include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cstdlib>
+#include <random>
+#include <vector>
+
+namespace llvm {
+
+extern bool BugpointIsInterrupted;
+
+template <typename ElTy> struct ListReducer {
+  enum TestResult {
+    NoFailure,  // No failure of the predicate was detected
+    KeepSuffix, // The suffix alone satisfies the predicate
+    KeepPrefix  // The prefix alone satisfies the predicate
+  };
+
+  virtual ~ListReducer() {}
+
+  /// This virtual function should be overriden by subclasses to implement the
+  /// test desired.  The testcase is only required to test to see if the Kept
+  /// list still satisfies the property, but if it is going to check the prefix
+  /// anyway, it can.
+  virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix,
+                                      std::vector<ElTy> &Kept) = 0;
+
+  /// This function attempts to reduce the length of the specified list while
+  /// still maintaining the "test" property.  This is the core of the "work"
+  /// that bugpoint does.
+  Expected<bool> reduceList(std::vector<ElTy> &TheList) {
+    std::vector<ElTy> empty;
+    std::mt19937 randomness(0x6e5ea738);  // Seed the random number generator
+    Expected<TestResult> Result = doTest(TheList, empty);
+    if (Error E = Result.takeError())
+      return std::move(E);
+    switch (*Result) {
+    case KeepPrefix:
+      if (TheList.size() == 1) // we are done, it's the base case and it fails
+        return true;
+      else
+        break; // there's definitely an error, but we need to narrow it down
+
+    case KeepSuffix:
+      // cannot be reached!
+      llvm_unreachable("bugpoint ListReducer internal error: "
+                       "selected empty set.");
+
+    case NoFailure:
+      return false; // there is no failure with the full set of passes/funcs!
+    }
+
+    // Maximal number of allowed splitting iterations,
+    // before the elements are randomly shuffled.
+    const unsigned MaxIterationsWithoutProgress = 3;
+
+    // Maximal number of allowed single-element trim iterations. We add a
+    // threshold here as single-element reductions may otherwise take a
+    // very long time to complete.
+    const unsigned MaxTrimIterationsWithoutBackJump = 3;
+    bool ShufflingEnabled = true;
+
+  Backjump:
+    unsigned MidTop = TheList.size();
+    unsigned MaxIterations = MaxIterationsWithoutProgress;
+    unsigned NumOfIterationsWithoutProgress = 0;
+    while (MidTop > 1) { // Binary split reduction loop
+      // Halt if the user presses ctrl-c.
+      if (BugpointIsInterrupted) {
+        errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
+        return true;
+      }
+
+      // If the loop doesn't make satisfying progress, try shuffling.
+      // The purpose of shuffling is to avoid the heavy tails of the
+      // distribution (improving the speed of convergence).
+      if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
+        std::vector<ElTy> ShuffledList(TheList);
+        std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
+        errs() << "\n\n*** Testing shuffled set...\n\n";
+        // Check that random shuffle doesn't lose the bug
+        Expected<TestResult> Result = doTest(ShuffledList, empty);
+        // TODO: Previously, this error was ignored and we treated it as if
+        // shuffling hid the bug. This should really either be consumeError if
+        // that behaviour was sensible, or we should propagate the error.
+        assert(!Result.takeError() && "Shuffling caused internal error?");
+
+        if (*Result == KeepPrefix) {
+          // If the bug is still here, use the shuffled list.
+          TheList.swap(ShuffledList);
+          MidTop = TheList.size();
+          // Must increase the shuffling treshold to avoid the small
+          // probability of infinite looping without making progress.
+          MaxIterations += 2;
+          errs() << "\n\n*** Shuffling does not hide the bug...\n\n";
+        } else {
+          ShufflingEnabled = false; // Disable shuffling further on
+          errs() << "\n\n*** Shuffling hides the bug...\n\n";
+        }
+        NumOfIterationsWithoutProgress = 0;
+      }
+
+      unsigned Mid = MidTop / 2;
+      std::vector<ElTy> Prefix(TheList.begin(), TheList.begin() + Mid);
+      std::vector<ElTy> Suffix(TheList.begin() + Mid, TheList.end());
+
+      Expected<TestResult> Result = doTest(Prefix, Suffix);
+      if (Error E = Result.takeError())
+        return std::move(E);
+      switch (*Result) {
+      case KeepSuffix:
+        // The property still holds.  We can just drop the prefix elements, and
+        // shorten the list to the "kept" elements.
+        TheList.swap(Suffix);
+        MidTop = TheList.size();
+        // Reset progress treshold and progress counter
+        MaxIterations = MaxIterationsWithoutProgress;
+        NumOfIterationsWithoutProgress = 0;
+        break;
+      case KeepPrefix:
+        // The predicate still holds, shorten the list to the prefix elements.
+        TheList.swap(Prefix);
+        MidTop = TheList.size();
+        // Reset progress treshold and progress counter
+        MaxIterations = MaxIterationsWithoutProgress;
+        NumOfIterationsWithoutProgress = 0;
+        break;
+      case NoFailure:
+        // Otherwise the property doesn't hold.  Some of the elements we removed
+        // must be necessary to maintain the property.
+        MidTop = Mid;
+        NumOfIterationsWithoutProgress++;
+        break;
+      }
+    }
+
+    // Probability of backjumping from the trimming loop back to the binary
+    // split reduction loop.
+    const int BackjumpProbability = 10;
+
+    // Okay, we trimmed as much off the top and the bottom of the list as we
+    // could.  If there is more than two elements in the list, try deleting
+    // interior elements and testing that.
+    //
+    if (TheList.size() > 2) {
+      bool Changed = true;
+      std::vector<ElTy> EmptyList;
+      unsigned TrimIterations = 0;
+      while (Changed) { // Trimming loop.
+        Changed = false;
+
+        // If the binary split reduction loop made an unfortunate sequence of
+        // splits, the trimming loop might be left off with a huge number of
+        // remaining elements (large search space). Backjumping out of that
+        // search space and attempting a different split can significantly
+        // improve the convergence speed.
+        if (std::rand() % 100 < BackjumpProbability)
+          goto Backjump;
+
+        for (unsigned i = 1; i < TheList.size() - 1; ++i) {
+          // Check interior elts
+          if (BugpointIsInterrupted) {
+            errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
+            return true;
+          }
+
+          std::vector<ElTy> TestList(TheList);
+          TestList.erase(TestList.begin() + i);
+
+          Expected<TestResult> Result = doTest(EmptyList, TestList);
+          if (Error E = Result.takeError())
+            return std::move(E);
+          if (*Result == KeepSuffix) {
+            // We can trim down the list!
+            TheList.swap(TestList);
+            --i; // Don't skip an element of the list
+            Changed = true;
+          }
+        }
+        if (TrimIterations >= MaxTrimIterationsWithoutBackJump)
+          break;
+        TrimIterations++;
+      }
+    }
+
+    return true; // there are some failure and we've narrowed them down
+  }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/contrib/libs/llvm12/tools/bugpoint/Miscompilation.cpp b/contrib/libs/llvm12/tools/bugpoint/Miscompilation.cpp
new file mode 100644
index 0000000000..e69fe9ff6c
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/Miscompilation.cpp
@@ -0,0 +1,1104 @@
+//===- Miscompilation.cpp - Debug program miscompilations -----------------===//
+//
+// 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 optimizer and code generation miscompilation debugging
+// support.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ListReducer.h"
+#include "ToolRunner.h"
+#include "llvm/Config/config.h" // for HAVE_LINK_R
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Linker/Linker.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+using namespace llvm;
+
+namespace llvm {
+extern cl::opt<std::string> OutputPrefix;
+extern cl::list<std::string> InputArgv;
+} // end namespace llvm
+
+namespace {
+static llvm::cl::opt<bool> DisableLoopExtraction(
+    "disable-loop-extraction",
+    cl::desc("Don't extract loops when searching for miscompilations"),
+    cl::init(false));
+static llvm::cl::opt<bool> DisableBlockExtraction(
+    "disable-block-extraction",
+    cl::desc("Don't extract blocks when searching for miscompilations"),
+    cl::init(false));
+
+class ReduceMiscompilingPasses : public ListReducer<std::string> {
+  BugDriver &BD;
+
+public:
+  ReduceMiscompilingPasses(BugDriver &bd) : BD(bd) {}
+
+  Expected<TestResult> doTest(std::vector<std::string> &Prefix,
+                              std::vector<std::string> &Suffix) override;
+};
+} // end anonymous namespace
+
+/// TestResult - After passes have been split into a test group and a control
+/// group, see if they still break the program.
+///
+Expected<ReduceMiscompilingPasses::TestResult>
+ReduceMiscompilingPasses::doTest(std::vector<std::string> &Prefix,
+                                 std::vector<std::string> &Suffix) {
+  // First, run the program with just the Suffix passes.  If it is still broken
+  // with JUST the kept passes, discard the prefix passes.
+  outs() << "Checking to see if '" << getPassesString(Suffix)
+         << "' compiles correctly: ";
+
+  std::string BitcodeResult;
+  if (BD.runPasses(BD.getProgram(), Suffix, BitcodeResult, false /*delete*/,
+                   true /*quiet*/)) {
+    errs() << " Error running this sequence of passes"
+           << " on the input program!\n";
+    BD.setPassesToRun(Suffix);
+    BD.EmitProgressBitcode(BD.getProgram(), "pass-error", false);
+    // TODO: This should propagate the error instead of exiting.
+    if (Error E = BD.debugOptimizerCrash())
+      exit(1);
+    exit(0);
+  }
+
+  // Check to see if the finished program matches the reference output...
+  Expected<bool> Diff = BD.diffProgram(BD.getProgram(), BitcodeResult, "",
+                                       true /*delete bitcode*/);
+  if (Error E = Diff.takeError())
+    return std::move(E);
+  if (*Diff) {
+    outs() << " nope.\n";
+    if (Suffix.empty()) {
+      errs() << BD.getToolName() << ": I'm confused: the test fails when "
+             << "no passes are run, nondeterministic program?\n";
+      exit(1);
+    }
+    return KeepSuffix; // Miscompilation detected!
+  }
+  outs() << " yup.\n"; // No miscompilation!
+
+  if (Prefix.empty())
+    return NoFailure;
+
+  // Next, see if the program is broken if we run the "prefix" passes first,
+  // then separately run the "kept" passes.
+  outs() << "Checking to see if '" << getPassesString(Prefix)
+         << "' compiles correctly: ";
+
+  // If it is not broken with the kept passes, it's possible that the prefix
+  // passes must be run before the kept passes to break it.  If the program
+  // WORKS after the prefix passes, but then fails if running the prefix AND
+  // kept passes, we can update our bitcode file to include the result of the
+  // prefix passes, then discard the prefix passes.
+  //
+  if (BD.runPasses(BD.getProgram(), Prefix, BitcodeResult, false /*delete*/,
+                   true /*quiet*/)) {
+    errs() << " Error running this sequence of passes"
+           << " on the input program!\n";
+    BD.setPassesToRun(Prefix);
+    BD.EmitProgressBitcode(BD.getProgram(), "pass-error", false);
+    // TODO: This should propagate the error instead of exiting.
+    if (Error E = BD.debugOptimizerCrash())
+      exit(1);
+    exit(0);
+  }
+
+  // If the prefix maintains the predicate by itself, only keep the prefix!
+  Diff = BD.diffProgram(BD.getProgram(), BitcodeResult, "", false);
+  if (Error E = Diff.takeError())
+    return std::move(E);
+  if (*Diff) {
+    outs() << " nope.\n";
+    sys::fs::remove(BitcodeResult);
+    return KeepPrefix;
+  }
+  outs() << " yup.\n"; // No miscompilation!
+
+  // Ok, so now we know that the prefix passes work, try running the suffix
+  // passes on the result of the prefix passes.
+  //
+  std::unique_ptr<Module> PrefixOutput =
+      parseInputFile(BitcodeResult, BD.getContext());
+  if (!PrefixOutput) {
+    errs() << BD.getToolName() << ": Error reading bitcode file '"
+           << BitcodeResult << "'!\n";
+    exit(1);
+  }
+  sys::fs::remove(BitcodeResult);
+
+  // Don't check if there are no passes in the suffix.
+  if (Suffix.empty())
+    return NoFailure;
+
+  outs() << "Checking to see if '" << getPassesString(Suffix)
+         << "' passes compile correctly after the '" << getPassesString(Prefix)
+         << "' passes: ";
+
+  std::unique_ptr<Module> OriginalInput =
+      BD.swapProgramIn(std::move(PrefixOutput));
+  if (BD.runPasses(BD.getProgram(), Suffix, BitcodeResult, false /*delete*/,
+                   true /*quiet*/)) {
+    errs() << " Error running this sequence of passes"
+           << " on the input program!\n";
+    BD.setPassesToRun(Suffix);
+    BD.EmitProgressBitcode(BD.getProgram(), "pass-error", false);
+    // TODO: This should propagate the error instead of exiting.
+    if (Error E = BD.debugOptimizerCrash())
+      exit(1);
+    exit(0);
+  }
+
+  // Run the result...
+  Diff = BD.diffProgram(BD.getProgram(), BitcodeResult, "",
+                        true /*delete bitcode*/);
+  if (Error E = Diff.takeError())
+    return std::move(E);
+  if (*Diff) {
+    outs() << " nope.\n";
+    return KeepSuffix;
+  }
+
+  // Otherwise, we must not be running the bad pass anymore.
+  outs() << " yup.\n"; // No miscompilation!
+  // Restore orig program & free test.
+  BD.setNewProgram(std::move(OriginalInput));
+  return NoFailure;
+}
+
+namespace {
+class ReduceMiscompilingFunctions : public ListReducer<Function *> {
+  BugDriver &BD;
+  Expected<bool> (*TestFn)(BugDriver &, std::unique_ptr<Module>,
+                           std::unique_ptr<Module>);
+
+public:
+  ReduceMiscompilingFunctions(BugDriver &bd,
+                              Expected<bool> (*F)(BugDriver &,
+                                                  std::unique_ptr<Module>,
+                                                  std::unique_ptr<Module>))
+      : BD(bd), TestFn(F) {}
+
+  Expected<TestResult> doTest(std::vector<Function *> &Prefix,
+                              std::vector<Function *> &Suffix) override {
+    if (!Suffix.empty()) {
+      Expected<bool> Ret = TestFuncs(Suffix);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+      if (*Ret)
+        return KeepSuffix;
+    }
+    if (!Prefix.empty()) {
+      Expected<bool> Ret = TestFuncs(Prefix);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+      if (*Ret)
+        return KeepPrefix;
+    }
+    return NoFailure;
+  }
+
+  Expected<bool> TestFuncs(const std::vector<Function *> &Prefix);
+};
+} // end anonymous namespace
+
+/// Given two modules, link them together and run the program, checking to see
+/// if the program matches the diff. If there is an error, return NULL. If not,
+/// return the merged module. The Broken argument will be set to true if the
+/// output is different. If the DeleteInputs argument is set to true then this
+/// function deletes both input modules before it returns.
+///
+static Expected<std::unique_ptr<Module>> testMergedProgram(const BugDriver &BD,
+                                                           const Module &M1,
+                                                           const Module &M2,
+                                                           bool &Broken) {
+  // Resulting merge of M1 and M2.
+  auto Merged = CloneModule(M1);
+  if (Linker::linkModules(*Merged, CloneModule(M2)))
+    // TODO: Shouldn't we thread the error up instead of exiting?
+    exit(1);
+
+  // Execute the program.
+  Expected<bool> Diff = BD.diffProgram(*Merged, "", "", false);
+  if (Error E = Diff.takeError())
+    return std::move(E);
+  Broken = *Diff;
+  return std::move(Merged);
+}
+
+/// split functions in a Module into two groups: those that are under
+/// consideration for miscompilation vs. those that are not, and test
+/// accordingly. Each group of functions becomes a separate Module.
+Expected<bool>
+ReduceMiscompilingFunctions::TestFuncs(const std::vector<Function *> &Funcs) {
+  // Test to see if the function is misoptimized if we ONLY run it on the
+  // functions listed in Funcs.
+  outs() << "Checking to see if the program is misoptimized when "
+         << (Funcs.size() == 1 ? "this function is" : "these functions are")
+         << " run through the pass"
+         << (BD.getPassesToRun().size() == 1 ? "" : "es") << ":";
+  PrintFunctionList(Funcs);
+  outs() << '\n';
+
+  // Create a clone for two reasons:
+  // * If the optimization passes delete any function, the deleted function
+  //   will be in the clone and Funcs will still point to valid memory
+  // * If the optimization passes use interprocedural information to break
+  //   a function, we want to continue with the original function. Otherwise
+  //   we can conclude that a function triggers the bug when in fact one
+  //   needs a larger set of original functions to do so.
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> Clone = CloneModule(BD.getProgram(), VMap);
+  std::unique_ptr<Module> Orig = BD.swapProgramIn(std::move(Clone));
+
+  std::vector<Function *> FuncsOnClone;
+  for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
+    Function *F = cast<Function>(VMap[Funcs[i]]);
+    FuncsOnClone.push_back(F);
+  }
+
+  // Split the module into the two halves of the program we want.
+  VMap.clear();
+  std::unique_ptr<Module> ToNotOptimize = CloneModule(BD.getProgram(), VMap);
+  std::unique_ptr<Module> ToOptimize =
+      SplitFunctionsOutOfModule(ToNotOptimize.get(), FuncsOnClone, VMap);
+
+  Expected<bool> Broken =
+      TestFn(BD, std::move(ToOptimize), std::move(ToNotOptimize));
+
+  BD.setNewProgram(std::move(Orig));
+
+  return Broken;
+}
+
+/// Give anonymous global values names.
+static void DisambiguateGlobalSymbols(Module &M) {
+  for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E;
+       ++I)
+    if (!I->hasName())
+      I->setName("anon_global");
+  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+    if (!I->hasName())
+      I->setName("anon_fn");
+}
+
+/// Given a reduced list of functions that still exposed the bug, check to see
+/// if we can extract the loops in the region without obscuring the bug.  If so,
+/// it reduces the amount of code identified.
+///
+static Expected<bool>
+ExtractLoops(BugDriver &BD,
+             Expected<bool> (*TestFn)(BugDriver &, std::unique_ptr<Module>,
+                                      std::unique_ptr<Module>),
+             std::vector<Function *> &MiscompiledFunctions) {
+  bool MadeChange = false;
+  while (1) {
+    if (BugpointIsInterrupted)
+      return MadeChange;
+
+    ValueToValueMapTy VMap;
+    std::unique_ptr<Module> ToNotOptimize = CloneModule(BD.getProgram(), VMap);
+    std::unique_ptr<Module> ToOptimize = SplitFunctionsOutOfModule(
+        ToNotOptimize.get(), MiscompiledFunctions, VMap);
+    std::unique_ptr<Module> ToOptimizeLoopExtracted =
+        BD.extractLoop(ToOptimize.get());
+    if (!ToOptimizeLoopExtracted)
+      // If the loop extractor crashed or if there were no extractible loops,
+      // then this chapter of our odyssey is over with.
+      return MadeChange;
+
+    errs() << "Extracted a loop from the breaking portion of the program.\n";
+
+    // Bugpoint is intentionally not very trusting of LLVM transformations.  In
+    // particular, we're not going to assume that the loop extractor works, so
+    // we're going to test the newly loop extracted program to make sure nothing
+    // has broken.  If something broke, then we'll inform the user and stop
+    // extraction.
+    AbstractInterpreter *AI = BD.switchToSafeInterpreter();
+    bool Failure;
+    Expected<std::unique_ptr<Module>> New = testMergedProgram(
+        BD, *ToOptimizeLoopExtracted, *ToNotOptimize, Failure);
+    if (Error E = New.takeError())
+      return std::move(E);
+    if (!*New)
+      return false;
+
+    // Delete the original and set the new program.
+    std::unique_ptr<Module> Old = BD.swapProgramIn(std::move(*New));
+    for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
+      MiscompiledFunctions[i] = cast<Function>(VMap[MiscompiledFunctions[i]]);
+
+    if (Failure) {
+      BD.switchToInterpreter(AI);
+
+      // Merged program doesn't work anymore!
+      errs() << "  *** ERROR: Loop extraction broke the program. :("
+             << " Please report a bug!\n";
+      errs() << "      Continuing on with un-loop-extracted version.\n";
+
+      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-tno.bc",
+                            *ToNotOptimize);
+      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-to.bc",
+                            *ToOptimize);
+      BD.writeProgramToFile(OutputPrefix + "-loop-extract-fail-to-le.bc",
+                            *ToOptimizeLoopExtracted);
+
+      errs() << "Please submit the " << OutputPrefix
+             << "-loop-extract-fail-*.bc files.\n";
+      return MadeChange;
+    }
+    BD.switchToInterpreter(AI);
+
+    outs() << "  Testing after loop extraction:\n";
+    // Clone modules, the tester function will free them.
+    std::unique_ptr<Module> TOLEBackup =
+        CloneModule(*ToOptimizeLoopExtracted, VMap);
+    std::unique_ptr<Module> TNOBackup = CloneModule(*ToNotOptimize, VMap);
+
+    for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
+      MiscompiledFunctions[i] = cast<Function>(VMap[MiscompiledFunctions[i]]);
+
+    Expected<bool> Result = TestFn(BD, std::move(ToOptimizeLoopExtracted),
+                                   std::move(ToNotOptimize));
+    if (Error E = Result.takeError())
+      return std::move(E);
+
+    ToOptimizeLoopExtracted = std::move(TOLEBackup);
+    ToNotOptimize = std::move(TNOBackup);
+
+    if (!*Result) {
+      outs() << "*** Loop extraction masked the problem.  Undoing.\n";
+      // If the program is not still broken, then loop extraction did something
+      // that masked the error.  Stop loop extraction now.
+
+      std::vector<std::pair<std::string, FunctionType *>> MisCompFunctions;
+      for (Function *F : MiscompiledFunctions) {
+        MisCompFunctions.emplace_back(std::string(F->getName()),
+                                      F->getFunctionType());
+      }
+
+      if (Linker::linkModules(*ToNotOptimize,
+                              std::move(ToOptimizeLoopExtracted)))
+        exit(1);
+
+      MiscompiledFunctions.clear();
+      for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
+        Function *NewF = ToNotOptimize->getFunction(MisCompFunctions[i].first);
+
+        assert(NewF && "Function not found??");
+        MiscompiledFunctions.push_back(NewF);
+      }
+
+      BD.setNewProgram(std::move(ToNotOptimize));
+      return MadeChange;
+    }
+
+    outs() << "*** Loop extraction successful!\n";
+
+    std::vector<std::pair<std::string, FunctionType *>> MisCompFunctions;
+    for (Module::iterator I = ToOptimizeLoopExtracted->begin(),
+                          E = ToOptimizeLoopExtracted->end();
+         I != E; ++I)
+      if (!I->isDeclaration())
+        MisCompFunctions.emplace_back(std::string(I->getName()),
+                                      I->getFunctionType());
+
+    // Okay, great!  Now we know that we extracted a loop and that loop
+    // extraction both didn't break the program, and didn't mask the problem.
+    // Replace the current program with the loop extracted version, and try to
+    // extract another loop.
+    if (Linker::linkModules(*ToNotOptimize, std::move(ToOptimizeLoopExtracted)))
+      exit(1);
+
+    // All of the Function*'s in the MiscompiledFunctions list are in the old
+    // module.  Update this list to include all of the functions in the
+    // optimized and loop extracted module.
+    MiscompiledFunctions.clear();
+    for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
+      Function *NewF = ToNotOptimize->getFunction(MisCompFunctions[i].first);
+
+      assert(NewF && "Function not found??");
+      MiscompiledFunctions.push_back(NewF);
+    }
+
+    BD.setNewProgram(std::move(ToNotOptimize));
+    MadeChange = true;
+  }
+}
+
+namespace {
+class ReduceMiscompiledBlocks : public ListReducer<BasicBlock *> {
+  BugDriver &BD;
+  Expected<bool> (*TestFn)(BugDriver &, std::unique_ptr<Module>,
+                           std::unique_ptr<Module>);
+  std::vector<Function *> FunctionsBeingTested;
+
+public:
+  ReduceMiscompiledBlocks(BugDriver &bd,
+                          Expected<bool> (*F)(BugDriver &,
+                                              std::unique_ptr<Module>,
+                                              std::unique_ptr<Module>),
+                          const std::vector<Function *> &Fns)
+      : BD(bd), TestFn(F), FunctionsBeingTested(Fns) {}
+
+  Expected<TestResult> doTest(std::vector<BasicBlock *> &Prefix,
+                              std::vector<BasicBlock *> &Suffix) override {
+    if (!Suffix.empty()) {
+      Expected<bool> Ret = TestFuncs(Suffix);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+      if (*Ret)
+        return KeepSuffix;
+    }
+    if (!Prefix.empty()) {
+      Expected<bool> Ret = TestFuncs(Prefix);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+      if (*Ret)
+        return KeepPrefix;
+    }
+    return NoFailure;
+  }
+
+  Expected<bool> TestFuncs(const std::vector<BasicBlock *> &BBs);
+};
+} // end anonymous namespace
+
+/// TestFuncs - Extract all blocks for the miscompiled functions except for the
+/// specified blocks.  If the problem still exists, return true.
+///
+Expected<bool>
+ReduceMiscompiledBlocks::TestFuncs(const std::vector<BasicBlock *> &BBs) {
+  // Test to see if the function is misoptimized if we ONLY run it on the
+  // functions listed in Funcs.
+  outs() << "Checking to see if the program is misoptimized when all ";
+  if (!BBs.empty()) {
+    outs() << "but these " << BBs.size() << " blocks are extracted: ";
+    for (unsigned i = 0, e = BBs.size() < 10 ? BBs.size() : 10; i != e; ++i)
+      outs() << BBs[i]->getName() << " ";
+    if (BBs.size() > 10)
+      outs() << "...";
+  } else {
+    outs() << "blocks are extracted.";
+  }
+  outs() << '\n';
+
+  // Split the module into the two halves of the program we want.
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> Clone = CloneModule(BD.getProgram(), VMap);
+  std::unique_ptr<Module> Orig = BD.swapProgramIn(std::move(Clone));
+  std::vector<Function *> FuncsOnClone;
+  std::vector<BasicBlock *> BBsOnClone;
+  for (unsigned i = 0, e = FunctionsBeingTested.size(); i != e; ++i) {
+    Function *F = cast<Function>(VMap[FunctionsBeingTested[i]]);
+    FuncsOnClone.push_back(F);
+  }
+  for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
+    BasicBlock *BB = cast<BasicBlock>(VMap[BBs[i]]);
+    BBsOnClone.push_back(BB);
+  }
+  VMap.clear();
+
+  std::unique_ptr<Module> ToNotOptimize = CloneModule(BD.getProgram(), VMap);
+  std::unique_ptr<Module> ToOptimize =
+      SplitFunctionsOutOfModule(ToNotOptimize.get(), FuncsOnClone, VMap);
+
+  // Try the extraction.  If it doesn't work, then the block extractor crashed
+  // or something, in which case bugpoint can't chase down this possibility.
+  if (std::unique_ptr<Module> New =
+          BD.extractMappedBlocksFromModule(BBsOnClone, ToOptimize.get())) {
+    Expected<bool> Ret = TestFn(BD, std::move(New), std::move(ToNotOptimize));
+    BD.setNewProgram(std::move(Orig));
+    return Ret;
+  }
+  BD.setNewProgram(std::move(Orig));
+  return false;
+}
+
+/// Given a reduced list of functions that still expose the bug, extract as many
+/// basic blocks from the region as possible without obscuring the bug.
+///
+static Expected<bool>
+ExtractBlocks(BugDriver &BD,
+              Expected<bool> (*TestFn)(BugDriver &, std::unique_ptr<Module>,
+                                       std::unique_ptr<Module>),
+              std::vector<Function *> &MiscompiledFunctions) {
+  if (BugpointIsInterrupted)
+    return false;
+
+  std::vector<BasicBlock *> Blocks;
+  for (unsigned i = 0, e = MiscompiledFunctions.size(); i != e; ++i)
+    for (BasicBlock &BB : *MiscompiledFunctions[i])
+      Blocks.push_back(&BB);
+
+  // Use the list reducer to identify blocks that can be extracted without
+  // obscuring the bug.  The Blocks list will end up containing blocks that must
+  // be retained from the original program.
+  unsigned OldSize = Blocks.size();
+
+  // Check to see if all blocks are extractible first.
+  Expected<bool> Ret = ReduceMiscompiledBlocks(BD, TestFn, MiscompiledFunctions)
+                           .TestFuncs(std::vector<BasicBlock *>());
+  if (Error E = Ret.takeError())
+    return std::move(E);
+  if (*Ret) {
+    Blocks.clear();
+  } else {
+    Expected<bool> Ret =
+        ReduceMiscompiledBlocks(BD, TestFn, MiscompiledFunctions)
+            .reduceList(Blocks);
+    if (Error E = Ret.takeError())
+      return std::move(E);
+    if (Blocks.size() == OldSize)
+      return false;
+  }
+
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> ProgClone = CloneModule(BD.getProgram(), VMap);
+  std::unique_ptr<Module> ToExtract =
+      SplitFunctionsOutOfModule(ProgClone.get(), MiscompiledFunctions, VMap);
+  std::unique_ptr<Module> Extracted =
+      BD.extractMappedBlocksFromModule(Blocks, ToExtract.get());
+  if (!Extracted) {
+    // Weird, extraction should have worked.
+    errs() << "Nondeterministic problem extracting blocks??\n";
+    return false;
+  }
+
+  // Otherwise, block extraction succeeded.  Link the two program fragments back
+  // together.
+
+  std::vector<std::pair<std::string, FunctionType *>> MisCompFunctions;
+  for (Module::iterator I = Extracted->begin(), E = Extracted->end(); I != E;
+       ++I)
+    if (!I->isDeclaration())
+      MisCompFunctions.emplace_back(std::string(I->getName()),
+                                    I->getFunctionType());
+
+  if (Linker::linkModules(*ProgClone, std::move(Extracted)))
+    exit(1);
+
+  // Update the list of miscompiled functions.
+  MiscompiledFunctions.clear();
+
+  for (unsigned i = 0, e = MisCompFunctions.size(); i != e; ++i) {
+    Function *NewF = ProgClone->getFunction(MisCompFunctions[i].first);
+    assert(NewF && "Function not found??");
+    MiscompiledFunctions.push_back(NewF);
+  }
+
+  // Set the new program and delete the old one.
+  BD.setNewProgram(std::move(ProgClone));
+
+  return true;
+}
+
+/// This is a generic driver to narrow down miscompilations, either in an
+/// optimization or a code generator.
+///
+static Expected<std::vector<Function *>> DebugAMiscompilation(
+    BugDriver &BD,
+    Expected<bool> (*TestFn)(BugDriver &, std::unique_ptr<Module>,
+                             std::unique_ptr<Module>)) {
+  // Okay, now that we have reduced the list of passes which are causing the
+  // failure, see if we can pin down which functions are being
+  // miscompiled... first build a list of all of the non-external functions in
+  // the program.
+  std::vector<Function *> MiscompiledFunctions;
+  Module &Prog = BD.getProgram();
+  for (Function &F : Prog)
+    if (!F.isDeclaration())
+      MiscompiledFunctions.push_back(&F);
+
+  // Do the reduction...
+  if (!BugpointIsInterrupted) {
+    Expected<bool> Ret = ReduceMiscompilingFunctions(BD, TestFn)
+                             .reduceList(MiscompiledFunctions);
+    if (Error E = Ret.takeError()) {
+      errs() << "\n***Cannot reduce functions: ";
+      return std::move(E);
+    }
+  }
+  outs() << "\n*** The following function"
+         << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+         << " being miscompiled: ";
+  PrintFunctionList(MiscompiledFunctions);
+  outs() << '\n';
+
+  // See if we can rip any loops out of the miscompiled functions and still
+  // trigger the problem.
+
+  if (!BugpointIsInterrupted && !DisableLoopExtraction) {
+    Expected<bool> Ret = ExtractLoops(BD, TestFn, MiscompiledFunctions);
+    if (Error E = Ret.takeError())
+      return std::move(E);
+    if (*Ret) {
+      // Okay, we extracted some loops and the problem still appears.  See if
+      // we can eliminate some of the created functions from being candidates.
+      DisambiguateGlobalSymbols(BD.getProgram());
+
+      // Do the reduction...
+      if (!BugpointIsInterrupted)
+        Ret = ReduceMiscompilingFunctions(BD, TestFn)
+                  .reduceList(MiscompiledFunctions);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+
+      outs() << "\n*** The following function"
+             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+             << " being miscompiled: ";
+      PrintFunctionList(MiscompiledFunctions);
+      outs() << '\n';
+    }
+  }
+
+  if (!BugpointIsInterrupted && !DisableBlockExtraction) {
+    Expected<bool> Ret = ExtractBlocks(BD, TestFn, MiscompiledFunctions);
+    if (Error E = Ret.takeError())
+      return std::move(E);
+    if (*Ret) {
+      // Okay, we extracted some blocks and the problem still appears.  See if
+      // we can eliminate some of the created functions from being candidates.
+      DisambiguateGlobalSymbols(BD.getProgram());
+
+      // Do the reduction...
+      Ret = ReduceMiscompilingFunctions(BD, TestFn)
+                .reduceList(MiscompiledFunctions);
+      if (Error E = Ret.takeError())
+        return std::move(E);
+
+      outs() << "\n*** The following function"
+             << (MiscompiledFunctions.size() == 1 ? " is" : "s are")
+             << " being miscompiled: ";
+      PrintFunctionList(MiscompiledFunctions);
+      outs() << '\n';
+    }
+  }
+
+  return MiscompiledFunctions;
+}
+
+/// This is the predicate function used to check to see if the "Test" portion of
+/// the program is misoptimized.  If so, return true.  In any case, both module
+/// arguments are deleted.
+///
+static Expected<bool> TestOptimizer(BugDriver &BD, std::unique_ptr<Module> Test,
+                                    std::unique_ptr<Module> Safe) {
+  // Run the optimization passes on ToOptimize, producing a transformed version
+  // of the functions being tested.
+  outs() << "  Optimizing functions being tested: ";
+  std::unique_ptr<Module> Optimized =
+      BD.runPassesOn(Test.get(), BD.getPassesToRun());
+  if (!Optimized) {
+    errs() << " Error running this sequence of passes"
+           << " on the input program!\n";
+    BD.EmitProgressBitcode(*Test, "pass-error", false);
+    BD.setNewProgram(std::move(Test));
+    if (Error E = BD.debugOptimizerCrash())
+      return std::move(E);
+    return false;
+  }
+  outs() << "done.\n";
+
+  outs() << "  Checking to see if the merged program executes correctly: ";
+  bool Broken;
+  auto Result = testMergedProgram(BD, *Optimized, *Safe, Broken);
+  if (Error E = Result.takeError())
+    return std::move(E);
+  if (auto New = std::move(*Result)) {
+    outs() << (Broken ? " nope.\n" : " yup.\n");
+    // Delete the original and set the new program.
+    BD.setNewProgram(std::move(New));
+  }
+  return Broken;
+}
+
+/// debugMiscompilation - This method is used when the passes selected are not
+/// crashing, but the generated output is semantically different from the
+/// input.
+///
+Error BugDriver::debugMiscompilation() {
+  // Make sure something was miscompiled...
+  if (!BugpointIsInterrupted) {
+    Expected<bool> Result =
+        ReduceMiscompilingPasses(*this).reduceList(PassesToRun);
+    if (Error E = Result.takeError())
+      return E;
+    if (!*Result)
+      return make_error<StringError>(
+          "*** Optimized program matches reference output!  No problem"
+          " detected...\nbugpoint can't help you with your problem!\n",
+          inconvertibleErrorCode());
+  }
+
+  outs() << "\n*** Found miscompiling pass"
+         << (getPassesToRun().size() == 1 ? "" : "es") << ": "
+         << getPassesString(getPassesToRun()) << '\n';
+  EmitProgressBitcode(*Program, "passinput");
+
+  Expected<std::vector<Function *>> MiscompiledFunctions =
+      DebugAMiscompilation(*this, TestOptimizer);
+  if (Error E = MiscompiledFunctions.takeError())
+    return E;
+
+  // Output a bunch of bitcode files for the user...
+  outs() << "Outputting reduced bitcode files which expose the problem:\n";
+  ValueToValueMapTy VMap;
+  Module *ToNotOptimize = CloneModule(getProgram(), VMap).release();
+  Module *ToOptimize =
+      SplitFunctionsOutOfModule(ToNotOptimize, *MiscompiledFunctions, VMap)
+          .release();
+
+  outs() << "  Non-optimized portion: ";
+  EmitProgressBitcode(*ToNotOptimize, "tonotoptimize", true);
+  delete ToNotOptimize; // Delete hacked module.
+
+  outs() << "  Portion that is input to optimizer: ";
+  EmitProgressBitcode(*ToOptimize, "tooptimize");
+  delete ToOptimize; // Delete hacked module.
+
+  return Error::success();
+}
+
+/// Get the specified modules ready for code generator testing.
+///
+static std::unique_ptr<Module>
+CleanupAndPrepareModules(BugDriver &BD, std::unique_ptr<Module> Test,
+                         Module *Safe) {
+  // Clean up the modules, removing extra cruft that we don't need anymore...
+  Test = BD.performFinalCleanups(std::move(Test));
+
+  // If we are executing the JIT, we have several nasty issues to take care of.
+  if (!BD.isExecutingJIT())
+    return Test;
+
+  // First, if the main function is in the Safe module, we must add a stub to
+  // the Test module to call into it.  Thus, we create a new function `main'
+  // which just calls the old one.
+  if (Function *oldMain = Safe->getFunction("main"))
+    if (!oldMain->isDeclaration()) {
+      // Rename it
+      oldMain->setName("llvm_bugpoint_old_main");
+      // Create a NEW `main' function with same type in the test module.
+      Function *newMain =
+          Function::Create(oldMain->getFunctionType(),
+                           GlobalValue::ExternalLinkage, "main", Test.get());
+      // Create an `oldmain' prototype in the test module, which will
+      // corresponds to the real main function in the same module.
+      Function *oldMainProto = Function::Create(oldMain->getFunctionType(),
+                                                GlobalValue::ExternalLinkage,
+                                                oldMain->getName(), Test.get());
+      // Set up and remember the argument list for the main function.
+      std::vector<Value *> args;
+      for (Function::arg_iterator I = newMain->arg_begin(),
+                                  E = newMain->arg_end(),
+                                  OI = oldMain->arg_begin();
+           I != E; ++I, ++OI) {
+        I->setName(OI->getName()); // Copy argument names from oldMain
+        args.push_back(&*I);
+      }
+
+      // Call the old main function and return its result
+      BasicBlock *BB = BasicBlock::Create(Safe->getContext(), "entry", newMain);
+      CallInst *call = CallInst::Create(oldMainProto, args, "", BB);
+
+      // If the type of old function wasn't void, return value of call
+      ReturnInst::Create(Safe->getContext(), call, BB);
+    }
+
+  // The second nasty issue we must deal with in the JIT is that the Safe
+  // module cannot directly reference any functions defined in the test
+  // module.  Instead, we use a JIT API call to dynamically resolve the
+  // symbol.
+
+  // Add the resolver to the Safe module.
+  // Prototype: void *getPointerToNamedFunction(const char* Name)
+  FunctionCallee resolverFunc = Safe->getOrInsertFunction(
+      "getPointerToNamedFunction", Type::getInt8PtrTy(Safe->getContext()),
+      Type::getInt8PtrTy(Safe->getContext()));
+
+  // Use the function we just added to get addresses of functions we need.
+  for (Module::iterator F = Safe->begin(), E = Safe->end(); F != E; ++F) {
+    if (F->isDeclaration() && !F->use_empty() &&
+        &*F != resolverFunc.getCallee() &&
+        !F->isIntrinsic() /* ignore intrinsics */) {
+      Function *TestFn = Test->getFunction(F->getName());
+
+      // Don't forward functions which are external in the test module too.
+      if (TestFn && !TestFn->isDeclaration()) {
+        // 1. Add a string constant with its name to the global file
+        Constant *InitArray =
+            ConstantDataArray::getString(F->getContext(), F->getName());
+        GlobalVariable *funcName = new GlobalVariable(
+            *Safe, InitArray->getType(), true /*isConstant*/,
+            GlobalValue::InternalLinkage, InitArray, F->getName() + "_name");
+
+        // 2. Use `GetElementPtr *funcName, 0, 0' to convert the string to an
+        // sbyte* so it matches the signature of the resolver function.
+
+        // GetElementPtr *funcName, ulong 0, ulong 0
+        std::vector<Constant *> GEPargs(
+            2, Constant::getNullValue(Type::getInt32Ty(F->getContext())));
+        Value *GEP = ConstantExpr::getGetElementPtr(InitArray->getType(),
+                                                    funcName, GEPargs);
+        std::vector<Value *> ResolverArgs;
+        ResolverArgs.push_back(GEP);
+
+        // Rewrite uses of F in global initializers, etc. to uses of a wrapper
+        // function that dynamically resolves the calls to F via our JIT API
+        if (!F->use_empty()) {
+          // Create a new global to hold the cached function pointer.
+          Constant *NullPtr = ConstantPointerNull::get(F->getType());
+          GlobalVariable *Cache = new GlobalVariable(
+              *F->getParent(), F->getType(), false,
+              GlobalValue::InternalLinkage, NullPtr, F->getName() + ".fpcache");
+
+          // Construct a new stub function that will re-route calls to F
+          FunctionType *FuncTy = F->getFunctionType();
+          Function *FuncWrapper =
+              Function::Create(FuncTy, GlobalValue::InternalLinkage,
+                               F->getName() + "_wrapper", F->getParent());
+          BasicBlock *EntryBB =
+              BasicBlock::Create(F->getContext(), "entry", FuncWrapper);
+          BasicBlock *DoCallBB =
+              BasicBlock::Create(F->getContext(), "usecache", FuncWrapper);
+          BasicBlock *LookupBB =
+              BasicBlock::Create(F->getContext(), "lookupfp", FuncWrapper);
+
+          // Check to see if we already looked up the value.
+          Value *CachedVal =
+              new LoadInst(F->getType(), Cache, "fpcache", EntryBB);
+          Value *IsNull = new ICmpInst(*EntryBB, ICmpInst::ICMP_EQ, CachedVal,
+                                       NullPtr, "isNull");
+          BranchInst::Create(LookupBB, DoCallBB, IsNull, EntryBB);
+
+          // Resolve the call to function F via the JIT API:
+          //
+          // call resolver(GetElementPtr...)
+          CallInst *Resolver = CallInst::Create(resolverFunc, ResolverArgs,
+                                                "resolver", LookupBB);
+
+          // Cast the result from the resolver to correctly-typed function.
+          CastInst *CastedResolver = new BitCastInst(
+              Resolver, PointerType::getUnqual(F->getFunctionType()),
+              "resolverCast", LookupBB);
+
+          // Save the value in our cache.
+          new StoreInst(CastedResolver, Cache, LookupBB);
+          BranchInst::Create(DoCallBB, LookupBB);
+
+          PHINode *FuncPtr =
+              PHINode::Create(NullPtr->getType(), 2, "fp", DoCallBB);
+          FuncPtr->addIncoming(CastedResolver, LookupBB);
+          FuncPtr->addIncoming(CachedVal, EntryBB);
+
+          // Save the argument list.
+          std::vector<Value *> Args;
+          for (Argument &A : FuncWrapper->args())
+            Args.push_back(&A);
+
+          // Pass on the arguments to the real function, return its result
+          if (F->getReturnType()->isVoidTy()) {
+            CallInst::Create(FuncTy, FuncPtr, Args, "", DoCallBB);
+            ReturnInst::Create(F->getContext(), DoCallBB);
+          } else {
+            CallInst *Call =
+                CallInst::Create(FuncTy, FuncPtr, Args, "retval", DoCallBB);
+            ReturnInst::Create(F->getContext(), Call, DoCallBB);
+          }
+
+          // Use the wrapper function instead of the old function
+          F->replaceAllUsesWith(FuncWrapper);
+        }
+      }
+    }
+  }
+
+  if (verifyModule(*Test) || verifyModule(*Safe)) {
+    errs() << "Bugpoint has a bug, which corrupted a module!!\n";
+    abort();
+  }
+
+  return Test;
+}
+
+/// This is the predicate function used to check to see if the "Test" portion of
+/// the program is miscompiled by the code generator under test.  If so, return
+/// true.  In any case, both module arguments are deleted.
+///
+static Expected<bool> TestCodeGenerator(BugDriver &BD,
+                                        std::unique_ptr<Module> Test,
+                                        std::unique_ptr<Module> Safe) {
+  Test = CleanupAndPrepareModules(BD, std::move(Test), Safe.get());
+
+  SmallString<128> TestModuleBC;
+  int TestModuleFD;
+  std::error_code EC = sys::fs::createTemporaryFile("bugpoint.test", "bc",
+                                                    TestModuleFD, TestModuleBC);
+  if (EC) {
+    errs() << BD.getToolName()
+           << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+  if (BD.writeProgramToFile(std::string(TestModuleBC.str()), TestModuleFD,
+                            *Test)) {
+    errs() << "Error writing bitcode to `" << TestModuleBC.str()
+           << "'\nExiting.";
+    exit(1);
+  }
+
+  FileRemover TestModuleBCRemover(TestModuleBC.str(), !SaveTemps);
+
+  // Make the shared library
+  SmallString<128> SafeModuleBC;
+  int SafeModuleFD;
+  EC = sys::fs::createTemporaryFile("bugpoint.safe", "bc", SafeModuleFD,
+                                    SafeModuleBC);
+  if (EC) {
+    errs() << BD.getToolName()
+           << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+
+  if (BD.writeProgramToFile(std::string(SafeModuleBC.str()), SafeModuleFD,
+                            *Safe)) {
+    errs() << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting.";
+    exit(1);
+  }
+
+  FileRemover SafeModuleBCRemover(SafeModuleBC.str(), !SaveTemps);
+
+  Expected<std::string> SharedObject =
+      BD.compileSharedObject(std::string(SafeModuleBC.str()));
+  if (Error E = SharedObject.takeError())
+    return std::move(E);
+
+  FileRemover SharedObjectRemover(*SharedObject, !SaveTemps);
+
+  // Run the code generator on the `Test' code, loading the shared library.
+  // The function returns whether or not the new output differs from reference.
+  Expected<bool> Result = BD.diffProgram(
+      BD.getProgram(), std::string(TestModuleBC.str()), *SharedObject, false);
+  if (Error E = Result.takeError())
+    return std::move(E);
+
+  if (*Result)
+    errs() << ": still failing!\n";
+  else
+    errs() << ": didn't fail.\n";
+
+  return Result;
+}
+
+/// debugCodeGenerator - debug errors in LLC, LLI, or CBE.
+///
+Error BugDriver::debugCodeGenerator() {
+  if ((void *)SafeInterpreter == (void *)Interpreter) {
+    Expected<std::string> Result =
+        executeProgramSafely(*Program, "bugpoint.safe.out");
+    if (Result) {
+      outs() << "\n*** The \"safe\" i.e. 'known good' backend cannot match "
+             << "the reference diff.  This may be due to a\n    front-end "
+             << "bug or a bug in the original program, but this can also "
+             << "happen if bugpoint isn't running the program with the "
+             << "right flags or input.\n    I left the result of executing "
+             << "the program with the \"safe\" backend in this file for "
+             << "you: '" << *Result << "'.\n";
+    }
+    return Error::success();
+  }
+
+  DisambiguateGlobalSymbols(*Program);
+
+  Expected<std::vector<Function *>> Funcs =
+      DebugAMiscompilation(*this, TestCodeGenerator);
+  if (Error E = Funcs.takeError())
+    return E;
+
+  // Split the module into the two halves of the program we want.
+  ValueToValueMapTy VMap;
+  std::unique_ptr<Module> ToNotCodeGen = CloneModule(getProgram(), VMap);
+  std::unique_ptr<Module> ToCodeGen =
+      SplitFunctionsOutOfModule(ToNotCodeGen.get(), *Funcs, VMap);
+
+  // Condition the modules
+  ToCodeGen =
+      CleanupAndPrepareModules(*this, std::move(ToCodeGen), ToNotCodeGen.get());
+
+  SmallString<128> TestModuleBC;
+  int TestModuleFD;
+  std::error_code EC = sys::fs::createTemporaryFile("bugpoint.test", "bc",
+                                                    TestModuleFD, TestModuleBC);
+  if (EC) {
+    errs() << getToolName() << "Error making unique filename: " << EC.message()
+           << "\n";
+    exit(1);
+  }
+
+  if (writeProgramToFile(std::string(TestModuleBC.str()), TestModuleFD,
+                         *ToCodeGen)) {
+    errs() << "Error writing bitcode to `" << TestModuleBC << "'\nExiting.";
+    exit(1);
+  }
+
+  // Make the shared library
+  SmallString<128> SafeModuleBC;
+  int SafeModuleFD;
+  EC = sys::fs::createTemporaryFile("bugpoint.safe", "bc", SafeModuleFD,
+                                    SafeModuleBC);
+  if (EC) {
+    errs() << getToolName() << "Error making unique filename: " << EC.message()
+           << "\n";
+    exit(1);
+  }
+
+  if (writeProgramToFile(std::string(SafeModuleBC.str()), SafeModuleFD,
+                         *ToNotCodeGen)) {
+    errs() << "Error writing bitcode to `" << SafeModuleBC << "'\nExiting.";
+    exit(1);
+  }
+  Expected<std::string> SharedObject =
+      compileSharedObject(std::string(SafeModuleBC.str()));
+  if (Error E = SharedObject.takeError())
+    return E;
+
+  outs() << "You can reproduce the problem with the command line: \n";
+  if (isExecutingJIT()) {
+    outs() << "  lli -load " << *SharedObject << " " << TestModuleBC;
+  } else {
+    outs() << "  llc " << TestModuleBC << " -o " << TestModuleBC << ".s\n";
+    outs() << "  cc " << *SharedObject << " " << TestModuleBC.str() << ".s -o "
+           << TestModuleBC << ".exe\n";
+    outs() << "  ./" << TestModuleBC << ".exe";
+  }
+  for (unsigned i = 0, e = InputArgv.size(); i != e; ++i)
+    outs() << " " << InputArgv[i];
+  outs() << '\n';
+  outs() << "The shared object was created with:\n  llc -march=c "
+         << SafeModuleBC.str() << " -o temporary.c\n"
+         << "  cc -xc temporary.c -O2 -o " << *SharedObject;
+  if (TargetTriple.getArch() == Triple::sparc)
+    outs() << " -G"; // Compile a shared library, `-G' for Sparc
+  else
+    outs() << " -fPIC -shared"; // `-shared' for Linux/X86, maybe others
+
+  outs() << " -fno-strict-aliasing\n";
+
+  return Error::success();
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/OptimizerDriver.cpp b/contrib/libs/llvm12/tools/bugpoint/OptimizerDriver.cpp
new file mode 100644
index 0000000000..ca78735202
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/OptimizerDriver.cpp
@@ -0,0 +1,287 @@
+//===- OptimizerDriver.cpp - Allow BugPoint to run passes safely ----------===//
+//
+// 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 defines an interface that allows bugpoint to run various passes
+// without the threat of a buggy pass corrupting bugpoint (of course, bugpoint
+// may have its own bugs, but that's another story...).  It achieves this by
+// forking a copy of itself and having the child process do the optimizations.
+// If this client dies, we can always fork a new one.  :)
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ToolRunner.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/ToolOutputFile.h"
+
+#define DONT_GET_PLUGIN_LOADER_OPTION
+#include "llvm/Support/PluginLoader.h"
+
+
+using namespace llvm;
+
+#define DEBUG_TYPE "bugpoint"
+
+namespace llvm {
+extern cl::opt<std::string> OutputPrefix;
+}
+
+static cl::opt<bool> PreserveBitcodeUseListOrder(
+    "preserve-bc-uselistorder",
+    cl::desc("Preserve use-list order when writing LLVM bitcode."),
+    cl::init(true), cl::Hidden);
+
+static cl::opt<std::string>
+    OptCmd("opt-command", cl::init(""),
+           cl::desc("Path to opt. (default: search path "
+                    "for 'opt'.)"));
+
+/// This writes the current "Program" to the named bitcode file.  If an error
+/// occurs, true is returned.
+static bool writeProgramToFileAux(ToolOutputFile &Out, const Module &M) {
+  WriteBitcodeToFile(M, Out.os(), PreserveBitcodeUseListOrder);
+  Out.os().close();
+  if (!Out.os().has_error()) {
+    Out.keep();
+    return false;
+  }
+  return true;
+}
+
+bool BugDriver::writeProgramToFile(const std::string &Filename, int FD,
+                                   const Module &M) const {
+  ToolOutputFile Out(Filename, FD);
+  return writeProgramToFileAux(Out, M);
+}
+
+bool BugDriver::writeProgramToFile(int FD, const Module &M) const {
+  raw_fd_ostream OS(FD, /*shouldClose*/ false);
+  WriteBitcodeToFile(M, OS, PreserveBitcodeUseListOrder);
+  OS.flush();
+  if (!OS.has_error())
+    return false;
+  OS.clear_error();
+  return true;
+}
+
+bool BugDriver::writeProgramToFile(const std::string &Filename,
+                                   const Module &M) const {
+  std::error_code EC;
+  ToolOutputFile Out(Filename, EC, sys::fs::OF_None);
+  if (!EC)
+    return writeProgramToFileAux(Out, M);
+  return true;
+}
+
+/// This function is used to output the current Program to a file named
+/// "bugpoint-ID.bc".
+void BugDriver::EmitProgressBitcode(const Module &M, const std::string &ID,
+                                    bool NoFlyer) const {
+  // Output the input to the current pass to a bitcode file, emit a message
+  // telling the user how to reproduce it: opt -foo blah.bc
+  //
+  std::string Filename = OutputPrefix + "-" + ID + ".bc";
+  if (writeProgramToFile(Filename, M)) {
+    errs() << "Error opening file '" << Filename << "' for writing!\n";
+    return;
+  }
+
+  outs() << "Emitted bitcode to '" << Filename << "'\n";
+  if (NoFlyer || PassesToRun.empty())
+    return;
+  outs() << "\n*** You can reproduce the problem with: ";
+  if (UseValgrind)
+    outs() << "valgrind ";
+  outs() << "opt " << Filename;
+  for (unsigned i = 0, e = PluginLoader::getNumPlugins(); i != e; ++i) {
+    outs() << " -load " << PluginLoader::getPlugin(i);
+  }
+  outs() << " " << getPassesString(PassesToRun) << "\n";
+}
+
+cl::opt<bool> SilencePasses(
+    "silence-passes",
+    cl::desc("Suppress output of running passes (both stdout and stderr)"));
+
+static cl::list<std::string> OptArgs("opt-args", cl::Positional,
+                                     cl::desc("<opt arguments>..."),
+                                     cl::ZeroOrMore, cl::PositionalEatsArgs);
+
+/// runPasses - Run the specified passes on Program, outputting a bitcode file
+/// and writing the filename into OutputFile if successful.  If the
+/// optimizations fail for some reason (optimizer crashes), return true,
+/// otherwise return false.  If DeleteOutput is set to true, the bitcode is
+/// deleted on success, and the filename string is undefined.  This prints to
+/// outs() a single line message indicating whether compilation was successful
+/// or failed.
+///
+bool BugDriver::runPasses(Module &Program,
+                          const std::vector<std::string> &Passes,
+                          std::string &OutputFilename, bool DeleteOutput,
+                          bool Quiet, ArrayRef<std::string> ExtraArgs) const {
+  // setup the output file name
+  outs().flush();
+  SmallString<128> UniqueFilename;
+  std::error_code EC = sys::fs::createUniqueFile(
+      OutputPrefix + "-output-%%%%%%%.bc", UniqueFilename);
+  if (EC) {
+    errs() << getToolName()
+           << ": Error making unique filename: " << EC.message() << "\n";
+    return 1;
+  }
+  OutputFilename = std::string(UniqueFilename.str());
+
+  // set up the input file name
+  Expected<sys::fs::TempFile> Temp =
+      sys::fs::TempFile::create(OutputPrefix + "-input-%%%%%%%.bc");
+  if (!Temp) {
+    errs() << getToolName()
+           << ": Error making unique filename: " << toString(Temp.takeError())
+           << "\n";
+    return 1;
+  }
+  DiscardTemp Discard{*Temp};
+  raw_fd_ostream OS(Temp->FD, /*shouldClose*/ false);
+
+  WriteBitcodeToFile(Program, OS, PreserveBitcodeUseListOrder);
+  OS.flush();
+  if (OS.has_error()) {
+    errs() << "Error writing bitcode file: " << Temp->TmpName << "\n";
+    OS.clear_error();
+    return 1;
+  }
+
+  std::string tool = OptCmd;
+  if (OptCmd.empty()) {
+    if (ErrorOr<std::string> Path =
+            FindProgramByName("opt", getToolName(), &OutputPrefix))
+      tool = *Path;
+    else
+      errs() << Path.getError().message() << "\n";
+  }
+  if (tool.empty()) {
+    errs() << "Cannot find `opt' in PATH!\n";
+    return 1;
+  }
+  if (!sys::fs::exists(tool)) {
+    errs() << "Specified `opt' binary does not exist: " << tool << "\n";
+    return 1;
+  }
+
+  std::string Prog;
+  if (UseValgrind) {
+    if (ErrorOr<std::string> Path = sys::findProgramByName("valgrind"))
+      Prog = *Path;
+    else
+      errs() << Path.getError().message() << "\n";
+  } else
+    Prog = tool;
+  if (Prog.empty()) {
+    errs() << "Cannot find `valgrind' in PATH!\n";
+    return 1;
+  }
+
+  // setup the child process' arguments
+  SmallVector<StringRef, 8> Args;
+  if (UseValgrind) {
+    Args.push_back("valgrind");
+    Args.push_back("--error-exitcode=1");
+    Args.push_back("-q");
+    Args.push_back(tool);
+  } else
+    Args.push_back(tool);
+
+  for (unsigned i = 0, e = OptArgs.size(); i != e; ++i)
+    Args.push_back(OptArgs[i]);
+  // Pin to legacy PM since bugpoint has lots of infra and hacks revolving
+  // around the legacy PM.
+  Args.push_back("-enable-new-pm=0");
+  Args.push_back("-disable-symbolication");
+  Args.push_back("-o");
+  Args.push_back(OutputFilename);
+  std::vector<std::string> pass_args;
+  for (unsigned i = 0, e = PluginLoader::getNumPlugins(); i != e; ++i) {
+    pass_args.push_back(std::string("-load"));
+    pass_args.push_back(PluginLoader::getPlugin(i));
+  }
+  for (std::vector<std::string>::const_iterator I = Passes.begin(),
+                                                E = Passes.end();
+       I != E; ++I)
+    pass_args.push_back(std::string("-") + (*I));
+  for (std::vector<std::string>::const_iterator I = pass_args.begin(),
+                                                E = pass_args.end();
+       I != E; ++I)
+    Args.push_back(I->c_str());
+  Args.push_back(Temp->TmpName.c_str());
+  Args.append(ExtraArgs.begin(), ExtraArgs.end());
+
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = Args.size() - 1; i != e; ++i) errs()
+             << " " << Args[i];
+             errs() << "\n";);
+
+  Optional<StringRef> Redirects[3] = {None, None, None};
+  // Redirect stdout and stderr to nowhere if SilencePasses is given.
+  if (SilencePasses) {
+    Redirects[1] = "";
+    Redirects[2] = "";
+  }
+
+  std::string ErrMsg;
+  int result = sys::ExecuteAndWait(Prog, Args, None, Redirects, Timeout,
+                                   MemoryLimit, &ErrMsg);
+
+  // If we are supposed to delete the bitcode file or if the passes crashed,
+  // remove it now.  This may fail if the file was never created, but that's ok.
+  if (DeleteOutput || result != 0)
+    sys::fs::remove(OutputFilename);
+
+  if (!Quiet) {
+    if (result == 0)
+      outs() << "Success!\n";
+    else if (result > 0)
+      outs() << "Exited with error code '" << result << "'\n";
+    else if (result < 0) {
+      if (result == -1)
+        outs() << "Execute failed: " << ErrMsg << "\n";
+      else
+        outs() << "Crashed: " << ErrMsg << "\n";
+    }
+    if (result & 0x01000000)
+      outs() << "Dumped core\n";
+  }
+
+  // Was the child successful?
+  return result != 0;
+}
+
+std::unique_ptr<Module>
+BugDriver::runPassesOn(Module *M, const std::vector<std::string> &Passes,
+                       ArrayRef<std::string> ExtraArgs) {
+  std::string BitcodeResult;
+  if (runPasses(*M, Passes, BitcodeResult, false /*delete*/, true /*quiet*/,
+                ExtraArgs)) {
+    return nullptr;
+  }
+
+  std::unique_ptr<Module> Ret = parseInputFile(BitcodeResult, Context);
+  if (!Ret) {
+    errs() << getToolName() << ": Error reading bitcode file '" << BitcodeResult
+           << "'!\n";
+    exit(1);
+  }
+  sys::fs::remove(BitcodeResult);
+  return Ret;
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/ToolRunner.cpp b/contrib/libs/llvm12/tools/bugpoint/ToolRunner.cpp
new file mode 100644
index 0000000000..c4ea1dad12
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/ToolRunner.cpp
@@ -0,0 +1,865 @@
+//===-- ToolRunner.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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the interfaces described in the ToolRunner.h file.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ToolRunner.h"
+#include "llvm/Config/config.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/raw_ostream.h"
+#include <fstream>
+#include <sstream>
+#include <utility>
+using namespace llvm;
+
+#define DEBUG_TYPE "toolrunner"
+
+namespace llvm {
+cl::opt<bool> SaveTemps("save-temps", cl::init(false),
+                        cl::desc("Save temporary files"));
+}
+
+namespace {
+cl::opt<std::string>
+    RemoteClient("remote-client",
+                 cl::desc("Remote execution client (rsh/ssh)"));
+
+cl::opt<std::string> RemoteHost("remote-host",
+                                cl::desc("Remote execution (rsh/ssh) host"));
+
+cl::opt<std::string> RemotePort("remote-port",
+                                cl::desc("Remote execution (rsh/ssh) port"));
+
+cl::opt<std::string> RemoteUser("remote-user",
+                                cl::desc("Remote execution (rsh/ssh) user id"));
+
+cl::opt<std::string>
+    RemoteExtra("remote-extra-options",
+                cl::desc("Remote execution (rsh/ssh) extra options"));
+}
+
+/// RunProgramWithTimeout - This function provides an alternate interface
+/// to the sys::Program::ExecuteAndWait interface.
+/// @see sys::Program::ExecuteAndWait
+static int RunProgramWithTimeout(StringRef ProgramPath,
+                                 ArrayRef<StringRef> Args, StringRef StdInFile,
+                                 StringRef StdOutFile, StringRef StdErrFile,
+                                 unsigned NumSeconds = 0,
+                                 unsigned MemoryLimit = 0,
+                                 std::string *ErrMsg = nullptr) {
+  Optional<StringRef> Redirects[3] = {StdInFile, StdOutFile, StdErrFile};
+  return sys::ExecuteAndWait(ProgramPath, Args, None, Redirects, NumSeconds,
+                             MemoryLimit, ErrMsg);
+}
+
+/// RunProgramRemotelyWithTimeout - This function runs the given program
+/// remotely using the given remote client and the sys::Program::ExecuteAndWait.
+/// Returns the remote program exit code or reports a remote client error if it
+/// fails. Remote client is required to return 255 if it failed or program exit
+/// code otherwise.
+/// @see sys::Program::ExecuteAndWait
+static int RunProgramRemotelyWithTimeout(
+    StringRef RemoteClientPath, ArrayRef<StringRef> Args, StringRef StdInFile,
+    StringRef StdOutFile, StringRef StdErrFile, unsigned NumSeconds = 0,
+    unsigned MemoryLimit = 0) {
+  Optional<StringRef> Redirects[3] = {StdInFile, StdOutFile, StdErrFile};
+
+  // Run the program remotely with the remote client
+  int ReturnCode = sys::ExecuteAndWait(RemoteClientPath, Args, None, Redirects,
+                                       NumSeconds, MemoryLimit);
+
+  // Has the remote client fail?
+  if (255 == ReturnCode) {
+    std::ostringstream OS;
+    OS << "\nError running remote client:\n ";
+    for (StringRef Arg : Args)
+      OS << " " << Arg.str();
+    OS << "\n";
+
+    // The error message is in the output file, let's print it out from there.
+    std::string StdOutFileName = StdOutFile.str();
+    std::ifstream ErrorFile(StdOutFileName.c_str());
+    if (ErrorFile) {
+      std::copy(std::istreambuf_iterator<char>(ErrorFile),
+                std::istreambuf_iterator<char>(),
+                std::ostreambuf_iterator<char>(OS));
+      ErrorFile.close();
+    }
+
+    errs() << OS.str();
+  }
+
+  return ReturnCode;
+}
+
+static Error ProcessFailure(StringRef ProgPath, ArrayRef<StringRef> Args,
+                            unsigned Timeout = 0, unsigned MemoryLimit = 0) {
+  std::ostringstream OS;
+  OS << "\nError running tool:\n ";
+  for (StringRef Arg : Args)
+    OS << " " << Arg.str();
+  OS << "\n";
+
+  // Rerun the compiler, capturing any error messages to print them.
+  SmallString<128> ErrorFilename;
+  std::error_code EC = sys::fs::createTemporaryFile(
+      "bugpoint.program_error_messages", "", ErrorFilename);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+
+  RunProgramWithTimeout(ProgPath, Args, "", ErrorFilename.str(),
+                        ErrorFilename.str(), Timeout, MemoryLimit);
+  // FIXME: check return code ?
+
+  // Print out the error messages generated by CC if possible...
+  std::ifstream ErrorFile(ErrorFilename.c_str());
+  if (ErrorFile) {
+    std::copy(std::istreambuf_iterator<char>(ErrorFile),
+              std::istreambuf_iterator<char>(),
+              std::ostreambuf_iterator<char>(OS));
+    ErrorFile.close();
+  }
+
+  sys::fs::remove(ErrorFilename.c_str());
+  return make_error<StringError>(OS.str(), inconvertibleErrorCode());
+}
+
+//===---------------------------------------------------------------------===//
+// LLI Implementation of AbstractIntepreter interface
+//
+namespace {
+class LLI : public AbstractInterpreter {
+  std::string LLIPath;               // The path to the LLI executable
+  std::vector<std::string> ToolArgs; // Args to pass to LLI
+public:
+  LLI(const std::string &Path, const std::vector<std::string> *Args)
+      : LLIPath(Path) {
+    ToolArgs.clear();
+    if (Args) {
+      ToolArgs = *Args;
+    }
+  }
+
+  Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs,
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) override;
+};
+}
+
+Expected<int> LLI::ExecuteProgram(const std::string &Bitcode,
+                                  const std::vector<std::string> &Args,
+                                  const std::string &InputFile,
+                                  const std::string &OutputFile,
+                                  const std::vector<std::string> &CCArgs,
+                                  const std::vector<std::string> &SharedLibs,
+                                  unsigned Timeout, unsigned MemoryLimit) {
+  std::vector<StringRef> LLIArgs;
+  LLIArgs.push_back(LLIPath);
+  LLIArgs.push_back("-force-interpreter=true");
+
+  for (std::vector<std::string>::const_iterator i = SharedLibs.begin(),
+                                                e = SharedLibs.end();
+       i != e; ++i) {
+    LLIArgs.push_back("-load");
+    LLIArgs.push_back(*i);
+  }
+
+  // Add any extra LLI args.
+  for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i)
+    LLIArgs.push_back(ToolArgs[i]);
+
+  LLIArgs.push_back(Bitcode);
+  // Add optional parameters to the running program from Argv
+  for (unsigned i = 0, e = Args.size(); i != e; ++i)
+    LLIArgs.push_back(Args[i]);
+
+  outs() << "<lli>";
+  outs().flush();
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = LLIArgs.size() - 1; i != e; ++i) errs()
+             << " " << LLIArgs[i];
+             errs() << "\n";);
+  return RunProgramWithTimeout(LLIPath, LLIArgs, InputFile, OutputFile,
+                               OutputFile, Timeout, MemoryLimit);
+}
+
+void AbstractInterpreter::anchor() {}
+
+ErrorOr<std::string> llvm::FindProgramByName(const std::string &ExeName,
+                                             const char *Argv0,
+                                             void *MainAddr) {
+  // Check the directory that the calling program is in.  We can do
+  // this if ProgramPath contains at least one / character, indicating that it
+  // is a relative path to the executable itself.
+  std::string Main = sys::fs::getMainExecutable(Argv0, MainAddr);
+  StringRef Result = sys::path::parent_path(Main);
+  if (ErrorOr<std::string> Path = sys::findProgramByName(ExeName, Result))
+    return *Path;
+
+  // Check the user PATH.
+  return sys::findProgramByName(ExeName);
+}
+
+// LLI create method - Try to find the LLI executable
+AbstractInterpreter *
+AbstractInterpreter::createLLI(const char *Argv0, std::string &Message,
+                               const std::vector<std::string> *ToolArgs) {
+  if (ErrorOr<std::string> LLIPath =
+      FindProgramByName("lli", Argv0, (void *)(intptr_t)&createLLI)) {
+    Message = "Found lli: " + *LLIPath + "\n";
+    return new LLI(*LLIPath, ToolArgs);
+  } else {
+    Message = LLIPath.getError().message() + "\n";
+    return nullptr;
+  }
+}
+
+//===---------------------------------------------------------------------===//
+// Custom compiler command implementation of AbstractIntepreter interface
+//
+// Allows using a custom command for compiling the bitcode, thus allows, for
+// example, to compile a bitcode fragment without linking or executing, then
+// using a custom wrapper script to check for compiler errors.
+namespace {
+class CustomCompiler : public AbstractInterpreter {
+  std::string CompilerCommand;
+  std::vector<std::string> CompilerArgs;
+
+public:
+  CustomCompiler(const std::string &CompilerCmd,
+                 std::vector<std::string> CompArgs)
+      : CompilerCommand(CompilerCmd), CompilerArgs(std::move(CompArgs)) {}
+
+  Error compileProgram(const std::string &Bitcode, unsigned Timeout = 0,
+                       unsigned MemoryLimit = 0) override;
+
+  Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs = std::vector<std::string>(),
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) override {
+    return make_error<StringError>(
+        "Execution not supported with -compile-custom",
+        inconvertibleErrorCode());
+  }
+};
+}
+
+Error CustomCompiler::compileProgram(const std::string &Bitcode,
+                                     unsigned Timeout, unsigned MemoryLimit) {
+
+  std::vector<StringRef> ProgramArgs;
+  ProgramArgs.push_back(CompilerCommand);
+
+  for (const auto &Arg : CompilerArgs)
+    ProgramArgs.push_back(Arg);
+  ProgramArgs.push_back(Bitcode);
+
+  // Add optional parameters to the running program from Argv
+  for (const auto &Arg : CompilerArgs)
+    ProgramArgs.push_back(Arg);
+
+  if (RunProgramWithTimeout(CompilerCommand, ProgramArgs, "", "", "", Timeout,
+                            MemoryLimit))
+    return ProcessFailure(CompilerCommand, ProgramArgs, Timeout, MemoryLimit);
+  return Error::success();
+}
+
+//===---------------------------------------------------------------------===//
+// Custom execution command implementation of AbstractIntepreter interface
+//
+// Allows using a custom command for executing the bitcode, thus allows,
+// for example, to invoke a cross compiler for code generation followed by
+// a simulator that executes the generated binary.
+namespace {
+class CustomExecutor : public AbstractInterpreter {
+  std::string ExecutionCommand;
+  std::vector<std::string> ExecutorArgs;
+
+public:
+  CustomExecutor(const std::string &ExecutionCmd,
+                 std::vector<std::string> ExecArgs)
+      : ExecutionCommand(ExecutionCmd), ExecutorArgs(std::move(ExecArgs)) {}
+
+  Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs,
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) override;
+};
+}
+
+Expected<int> CustomExecutor::ExecuteProgram(
+    const std::string &Bitcode, const std::vector<std::string> &Args,
+    const std::string &InputFile, const std::string &OutputFile,
+    const std::vector<std::string> &CCArgs,
+    const std::vector<std::string> &SharedLibs, unsigned Timeout,
+    unsigned MemoryLimit) {
+
+  std::vector<StringRef> ProgramArgs;
+  ProgramArgs.push_back(ExecutionCommand);
+
+  for (std::size_t i = 0; i < ExecutorArgs.size(); ++i)
+    ProgramArgs.push_back(ExecutorArgs[i]);
+  ProgramArgs.push_back(Bitcode);
+
+  // Add optional parameters to the running program from Argv
+  for (unsigned i = 0, e = Args.size(); i != e; ++i)
+    ProgramArgs.push_back(Args[i]);
+
+  return RunProgramWithTimeout(ExecutionCommand, ProgramArgs, InputFile,
+                               OutputFile, OutputFile, Timeout, MemoryLimit);
+}
+
+// Tokenize the CommandLine to the command and the args to allow
+// defining a full command line as the command instead of just the
+// executed program. We cannot just pass the whole string after the command
+// as a single argument because then the program sees only a single
+// command line argument (with spaces in it: "foo bar" instead
+// of "foo" and "bar").
+//
+// Spaces are used as a delimiter; however repeated, leading, and trailing
+// whitespace are ignored. Simple escaping is allowed via the '\'
+// character, as seen below:
+//
+// Two consecutive '\' evaluate to a single '\'.
+// A space after a '\' evaluates to a space that is not interpreted as a
+// delimiter.
+// Any other instances of the '\' character are removed.
+//
+// Example:
+// '\\' -> '\'
+// '\ ' -> ' '
+// 'exa\mple' -> 'example'
+//
+static void lexCommand(const char *Argv0, std::string &Message,
+                       const std::string &CommandLine, std::string &CmdPath,
+                       std::vector<std::string> &Args) {
+
+  std::string Token;
+  std::string Command;
+  bool FoundPath = false;
+
+  // first argument is the PATH.
+  // Skip repeated whitespace, leading whitespace and trailing whitespace.
+  for (std::size_t Pos = 0u; Pos <= CommandLine.size(); ++Pos) {
+    if ('\\' == CommandLine[Pos]) {
+      if (Pos + 1 < CommandLine.size())
+        Token.push_back(CommandLine[++Pos]);
+
+      continue;
+    }
+    if (' ' == CommandLine[Pos] || CommandLine.size() == Pos) {
+      if (Token.empty())
+        continue;
+
+      if (!FoundPath) {
+        Command = Token;
+        FoundPath = true;
+        Token.clear();
+        continue;
+      }
+
+      Args.push_back(Token);
+      Token.clear();
+      continue;
+    }
+    Token.push_back(CommandLine[Pos]);
+  }
+
+  auto Path = FindProgramByName(Command, Argv0, (void *)(intptr_t)&lexCommand);
+  if (!Path) {
+    Message = std::string("Cannot find '") + Command +
+              "' in PATH: " + Path.getError().message() + "\n";
+    return;
+  }
+  CmdPath = *Path;
+
+  Message = "Found command in: " + CmdPath + "\n";
+}
+
+// Custom execution environment create method, takes the execution command
+// as arguments
+AbstractInterpreter *AbstractInterpreter::createCustomCompiler(
+    const char *Argv0, std::string &Message,
+    const std::string &CompileCommandLine) {
+
+  std::string CmdPath;
+  std::vector<std::string> Args;
+  lexCommand(Argv0, Message, CompileCommandLine, CmdPath, Args);
+  if (CmdPath.empty())
+    return nullptr;
+
+  return new CustomCompiler(CmdPath, Args);
+}
+
+// Custom execution environment create method, takes the execution command
+// as arguments
+AbstractInterpreter *
+AbstractInterpreter::createCustomExecutor(const char *Argv0,
+                                          std::string &Message,
+                                          const std::string &ExecCommandLine) {
+
+  std::string CmdPath;
+  std::vector<std::string> Args;
+  lexCommand(Argv0, Message, ExecCommandLine, CmdPath, Args);
+  if (CmdPath.empty())
+    return nullptr;
+
+  return new CustomExecutor(CmdPath, Args);
+}
+
+//===----------------------------------------------------------------------===//
+// LLC Implementation of AbstractIntepreter interface
+//
+Expected<CC::FileType> LLC::OutputCode(const std::string &Bitcode,
+                                       std::string &OutputAsmFile,
+                                       unsigned Timeout, unsigned MemoryLimit) {
+  const char *Suffix = (UseIntegratedAssembler ? ".llc.o" : ".llc.s");
+
+  SmallString<128> UniqueFile;
+  std::error_code EC =
+      sys::fs::createUniqueFile(Bitcode + "-%%%%%%%" + Suffix, UniqueFile);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+  OutputAsmFile = std::string(UniqueFile.str());
+  std::vector<StringRef> LLCArgs;
+  LLCArgs.push_back(LLCPath);
+
+  // Add any extra LLC args.
+  for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i)
+    LLCArgs.push_back(ToolArgs[i]);
+
+  LLCArgs.push_back("-o");
+  LLCArgs.push_back(OutputAsmFile); // Output to the Asm file
+  LLCArgs.push_back(Bitcode);       // This is the input bitcode
+
+  if (UseIntegratedAssembler)
+    LLCArgs.push_back("-filetype=obj");
+
+  outs() << (UseIntegratedAssembler ? "<llc-ia>" : "<llc>");
+  outs().flush();
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = LLCArgs.size() - 1; i != e; ++i) errs()
+             << " " << LLCArgs[i];
+             errs() << "\n";);
+  if (RunProgramWithTimeout(LLCPath, LLCArgs, "", "", "", Timeout, MemoryLimit))
+    return ProcessFailure(LLCPath, LLCArgs, Timeout, MemoryLimit);
+  return UseIntegratedAssembler ? CC::ObjectFile : CC::AsmFile;
+}
+
+Error LLC::compileProgram(const std::string &Bitcode, unsigned Timeout,
+                          unsigned MemoryLimit) {
+  std::string OutputAsmFile;
+  Expected<CC::FileType> Result =
+      OutputCode(Bitcode, OutputAsmFile, Timeout, MemoryLimit);
+  sys::fs::remove(OutputAsmFile);
+  if (Error E = Result.takeError())
+    return E;
+  return Error::success();
+}
+
+Expected<int> LLC::ExecuteProgram(const std::string &Bitcode,
+                                  const std::vector<std::string> &Args,
+                                  const std::string &InputFile,
+                                  const std::string &OutputFile,
+                                  const std::vector<std::string> &ArgsForCC,
+                                  const std::vector<std::string> &SharedLibs,
+                                  unsigned Timeout, unsigned MemoryLimit) {
+
+  std::string OutputAsmFile;
+  Expected<CC::FileType> FileKind =
+      OutputCode(Bitcode, OutputAsmFile, Timeout, MemoryLimit);
+  FileRemover OutFileRemover(OutputAsmFile, !SaveTemps);
+  if (Error E = FileKind.takeError())
+    return std::move(E);
+
+  std::vector<std::string> CCArgs(ArgsForCC);
+  llvm::append_range(CCArgs, SharedLibs);
+
+  // Assuming LLC worked, compile the result with CC and run it.
+  return cc->ExecuteProgram(OutputAsmFile, Args, *FileKind, InputFile,
+                            OutputFile, CCArgs, Timeout, MemoryLimit);
+}
+
+/// createLLC - Try to find the LLC executable
+///
+LLC *AbstractInterpreter::createLLC(const char *Argv0, std::string &Message,
+                                    const std::string &CCBinary,
+                                    const std::vector<std::string> *Args,
+                                    const std::vector<std::string> *CCArgs,
+                                    bool UseIntegratedAssembler) {
+  ErrorOr<std::string> LLCPath =
+      FindProgramByName("llc", Argv0, (void *)(intptr_t)&createLLC);
+  if (!LLCPath) {
+    Message = LLCPath.getError().message() + "\n";
+    return nullptr;
+  }
+
+  CC *cc = CC::create(Argv0, Message, CCBinary, CCArgs);
+  if (!cc) {
+    errs() << Message << "\n";
+    exit(1);
+  }
+  Message = "Found llc: " + *LLCPath + "\n";
+  return new LLC(*LLCPath, cc, Args, UseIntegratedAssembler);
+}
+
+//===---------------------------------------------------------------------===//
+// JIT Implementation of AbstractIntepreter interface
+//
+namespace {
+class JIT : public AbstractInterpreter {
+  std::string LLIPath;               // The path to the LLI executable
+  std::vector<std::string> ToolArgs; // Args to pass to LLI
+public:
+  JIT(const std::string &Path, const std::vector<std::string> *Args)
+      : LLIPath(Path) {
+    ToolArgs.clear();
+    if (Args) {
+      ToolArgs = *Args;
+    }
+  }
+
+  Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs = std::vector<std::string>(),
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) override;
+};
+}
+
+Expected<int> JIT::ExecuteProgram(const std::string &Bitcode,
+                                  const std::vector<std::string> &Args,
+                                  const std::string &InputFile,
+                                  const std::string &OutputFile,
+                                  const std::vector<std::string> &CCArgs,
+                                  const std::vector<std::string> &SharedLibs,
+                                  unsigned Timeout, unsigned MemoryLimit) {
+  // Construct a vector of parameters, incorporating those from the command-line
+  std::vector<StringRef> JITArgs;
+  JITArgs.push_back(LLIPath);
+  JITArgs.push_back("-force-interpreter=false");
+
+  // Add any extra LLI args.
+  for (unsigned i = 0, e = ToolArgs.size(); i != e; ++i)
+    JITArgs.push_back(ToolArgs[i]);
+
+  for (unsigned i = 0, e = SharedLibs.size(); i != e; ++i) {
+    JITArgs.push_back("-load");
+    JITArgs.push_back(SharedLibs[i]);
+  }
+  JITArgs.push_back(Bitcode);
+  // Add optional parameters to the running program from Argv
+  for (unsigned i = 0, e = Args.size(); i != e; ++i)
+    JITArgs.push_back(Args[i]);
+
+  outs() << "<jit>";
+  outs().flush();
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = JITArgs.size() - 1; i != e; ++i) errs()
+             << " " << JITArgs[i];
+             errs() << "\n";);
+  LLVM_DEBUG(errs() << "\nSending output to " << OutputFile << "\n");
+  return RunProgramWithTimeout(LLIPath, JITArgs, InputFile, OutputFile,
+                               OutputFile, Timeout, MemoryLimit);
+}
+
+/// createJIT - Try to find the LLI executable
+///
+AbstractInterpreter *
+AbstractInterpreter::createJIT(const char *Argv0, std::string &Message,
+                               const std::vector<std::string> *Args) {
+  if (ErrorOr<std::string> LLIPath =
+          FindProgramByName("lli", Argv0, (void *)(intptr_t)&createJIT)) {
+    Message = "Found lli: " + *LLIPath + "\n";
+    return new JIT(*LLIPath, Args);
+  } else {
+    Message = LLIPath.getError().message() + "\n";
+    return nullptr;
+  }
+}
+
+//===---------------------------------------------------------------------===//
+// CC abstraction
+//
+
+static bool IsARMArchitecture(std::vector<StringRef> Args) {
+  for (size_t I = 0; I < Args.size(); ++I) {
+    if (!Args[I].equals_lower("-arch"))
+      continue;
+    ++I;
+    if (I == Args.size())
+      break;
+    if (Args[I].startswith_lower("arm"))
+      return true;
+  }
+
+  return false;
+}
+
+Expected<int> CC::ExecuteProgram(const std::string &ProgramFile,
+                                 const std::vector<std::string> &Args,
+                                 FileType fileType,
+                                 const std::string &InputFile,
+                                 const std::string &OutputFile,
+                                 const std::vector<std::string> &ArgsForCC,
+                                 unsigned Timeout, unsigned MemoryLimit) {
+  std::vector<StringRef> CCArgs;
+
+  CCArgs.push_back(CCPath);
+
+  if (TargetTriple.getArch() == Triple::x86)
+    CCArgs.push_back("-m32");
+
+  for (std::vector<std::string>::const_iterator I = ccArgs.begin(),
+                                                E = ccArgs.end();
+       I != E; ++I)
+    CCArgs.push_back(*I);
+
+  // Specify -x explicitly in case the extension is wonky
+  if (fileType != ObjectFile) {
+    CCArgs.push_back("-x");
+    if (fileType == CFile) {
+      CCArgs.push_back("c");
+      CCArgs.push_back("-fno-strict-aliasing");
+    } else {
+      CCArgs.push_back("assembler");
+
+      // For ARM architectures we don't want this flag. bugpoint isn't
+      // explicitly told what architecture it is working on, so we get
+      // it from cc flags
+      if (TargetTriple.isOSDarwin() && !IsARMArchitecture(CCArgs))
+        CCArgs.push_back("-force_cpusubtype_ALL");
+    }
+  }
+
+  CCArgs.push_back(ProgramFile); // Specify the input filename.
+
+  CCArgs.push_back("-x");
+  CCArgs.push_back("none");
+  CCArgs.push_back("-o");
+
+  SmallString<128> OutputBinary;
+  std::error_code EC =
+      sys::fs::createUniqueFile(ProgramFile + "-%%%%%%%.cc.exe", OutputBinary);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+  CCArgs.push_back(OutputBinary); // Output to the right file...
+
+  // Add any arguments intended for CC. We locate them here because this is
+  // most likely -L and -l options that need to come before other libraries but
+  // after the source. Other options won't be sensitive to placement on the
+  // command line, so this should be safe.
+  for (unsigned i = 0, e = ArgsForCC.size(); i != e; ++i)
+    CCArgs.push_back(ArgsForCC[i]);
+
+  CCArgs.push_back("-lm"); // Hard-code the math library...
+  CCArgs.push_back("-O2"); // Optimize the program a bit...
+  if (TargetTriple.getArch() == Triple::sparc)
+    CCArgs.push_back("-mcpu=v9");
+
+  outs() << "<CC>";
+  outs().flush();
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = CCArgs.size() - 1; i != e; ++i) errs()
+             << " " << CCArgs[i];
+             errs() << "\n";);
+  if (RunProgramWithTimeout(CCPath, CCArgs, "", "", ""))
+    return ProcessFailure(CCPath, CCArgs);
+
+  std::vector<StringRef> ProgramArgs;
+
+  // Declared here so that the destructor only runs after
+  // ProgramArgs is used.
+  std::string Exec;
+
+  if (RemoteClientPath.empty())
+    ProgramArgs.push_back(OutputBinary);
+  else {
+    ProgramArgs.push_back(RemoteClientPath);
+    ProgramArgs.push_back(RemoteHost);
+    if (!RemoteUser.empty()) {
+      ProgramArgs.push_back("-l");
+      ProgramArgs.push_back(RemoteUser);
+    }
+    if (!RemotePort.empty()) {
+      ProgramArgs.push_back("-p");
+      ProgramArgs.push_back(RemotePort);
+    }
+    if (!RemoteExtra.empty()) {
+      ProgramArgs.push_back(RemoteExtra);
+    }
+
+    // Full path to the binary. We need to cd to the exec directory because
+    // there is a dylib there that the exec expects to find in the CWD
+    char *env_pwd = getenv("PWD");
+    Exec = "cd ";
+    Exec += env_pwd;
+    Exec += "; ./";
+    Exec += OutputBinary.c_str();
+    ProgramArgs.push_back(Exec);
+  }
+
+  // Add optional parameters to the running program from Argv
+  for (unsigned i = 0, e = Args.size(); i != e; ++i)
+    ProgramArgs.push_back(Args[i]);
+
+  // Now that we have a binary, run it!
+  outs() << "<program>";
+  outs().flush();
+  LLVM_DEBUG(
+      errs() << "\nAbout to run:\t";
+      for (unsigned i = 0, e = ProgramArgs.size() - 1; i != e; ++i) errs()
+      << " " << ProgramArgs[i];
+      errs() << "\n";);
+
+  FileRemover OutputBinaryRemover(OutputBinary.str(), !SaveTemps);
+
+  if (RemoteClientPath.empty()) {
+    LLVM_DEBUG(errs() << "<run locally>");
+    std::string Error;
+    int ExitCode = RunProgramWithTimeout(OutputBinary.str(), ProgramArgs,
+                                         InputFile, OutputFile, OutputFile,
+                                         Timeout, MemoryLimit, &Error);
+    // Treat a signal (usually SIGSEGV) or timeout as part of the program output
+    // so that crash-causing miscompilation is handled seamlessly.
+    if (ExitCode < -1) {
+      std::ofstream outFile(OutputFile.c_str(), std::ios_base::app);
+      outFile << Error << '\n';
+      outFile.close();
+    }
+    return ExitCode;
+  } else {
+    outs() << "<run remotely>";
+    outs().flush();
+    return RunProgramRemotelyWithTimeout(RemoteClientPath, ProgramArgs,
+                                         InputFile, OutputFile, OutputFile,
+                                         Timeout, MemoryLimit);
+  }
+}
+
+Error CC::MakeSharedObject(const std::string &InputFile, FileType fileType,
+                           std::string &OutputFile,
+                           const std::vector<std::string> &ArgsForCC) {
+  SmallString<128> UniqueFilename;
+  std::error_code EC = sys::fs::createUniqueFile(
+      InputFile + "-%%%%%%%" + LTDL_SHLIB_EXT, UniqueFilename);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "\n";
+    exit(1);
+  }
+  OutputFile = std::string(UniqueFilename.str());
+
+  std::vector<StringRef> CCArgs;
+
+  CCArgs.push_back(CCPath);
+
+  if (TargetTriple.getArch() == Triple::x86)
+    CCArgs.push_back("-m32");
+
+  for (std::vector<std::string>::const_iterator I = ccArgs.begin(),
+                                                E = ccArgs.end();
+       I != E; ++I)
+    CCArgs.push_back(*I);
+
+  // Compile the C/asm file into a shared object
+  if (fileType != ObjectFile) {
+    CCArgs.push_back("-x");
+    CCArgs.push_back(fileType == AsmFile ? "assembler" : "c");
+  }
+  CCArgs.push_back("-fno-strict-aliasing");
+  CCArgs.push_back(InputFile); // Specify the input filename.
+  CCArgs.push_back("-x");
+  CCArgs.push_back("none");
+  if (TargetTriple.getArch() == Triple::sparc)
+    CCArgs.push_back("-G"); // Compile a shared library, `-G' for Sparc
+  else if (TargetTriple.isOSDarwin()) {
+    // link all source files into a single module in data segment, rather than
+    // generating blocks. dynamic_lookup requires that you set
+    // MACOSX_DEPLOYMENT_TARGET=10.3 in your env.  FIXME: it would be better for
+    // bugpoint to just pass that in the environment of CC.
+    CCArgs.push_back("-single_module");
+    CCArgs.push_back("-dynamiclib"); // `-dynamiclib' for MacOS X/PowerPC
+    CCArgs.push_back("-undefined");
+    CCArgs.push_back("dynamic_lookup");
+  } else
+    CCArgs.push_back("-shared"); // `-shared' for Linux/X86, maybe others
+
+  if (TargetTriple.getArch() == Triple::x86_64)
+    CCArgs.push_back("-fPIC"); // Requires shared objs to contain PIC
+
+  if (TargetTriple.getArch() == Triple::sparc)
+    CCArgs.push_back("-mcpu=v9");
+
+  CCArgs.push_back("-o");
+  CCArgs.push_back(OutputFile);         // Output to the right filename.
+  CCArgs.push_back("-O2");              // Optimize the program a bit.
+
+  // Add any arguments intended for CC. We locate them here because this is
+  // most likely -L and -l options that need to come before other libraries but
+  // after the source. Other options won't be sensitive to placement on the
+  // command line, so this should be safe.
+  for (unsigned i = 0, e = ArgsForCC.size(); i != e; ++i)
+    CCArgs.push_back(ArgsForCC[i]);
+
+  outs() << "<CC>";
+  outs().flush();
+  LLVM_DEBUG(errs() << "\nAbout to run:\t";
+             for (unsigned i = 0, e = CCArgs.size() - 1; i != e; ++i) errs()
+             << " " << CCArgs[i];
+             errs() << "\n";);
+  if (RunProgramWithTimeout(CCPath, CCArgs, "", "", ""))
+    return ProcessFailure(CCPath, CCArgs);
+  return Error::success();
+}
+
+/// create - Try to find the CC executable
+///
+CC *CC::create(const char *Argv0, std::string &Message,
+               const std::string &CCBinary,
+               const std::vector<std::string> *Args) {
+  auto CCPath = FindProgramByName(CCBinary, Argv0, (void *)(intptr_t)&create);
+  if (!CCPath) {
+    Message = "Cannot find `" + CCBinary + "' in PATH: " +
+              CCPath.getError().message() + "\n";
+    return nullptr;
+  }
+
+  std::string RemoteClientPath;
+  if (!RemoteClient.empty()) {
+    auto Path = sys::findProgramByName(RemoteClient);
+    if (!Path) {
+      Message = "Cannot find `" + RemoteClient + "' in PATH: " +
+                Path.getError().message() + "\n";
+      return nullptr;
+    }
+    RemoteClientPath = *Path;
+  }
+
+  Message = "Found CC: " + *CCPath + "\n";
+  return new CC(*CCPath, RemoteClientPath, Args);
+}
diff --git a/contrib/libs/llvm12/tools/bugpoint/ToolRunner.h b/contrib/libs/llvm12/tools/bugpoint/ToolRunner.h
new file mode 100644
index 0000000000..f6b5f26c7a
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/ToolRunner.h
@@ -0,0 +1,190 @@
+//===-- tools/bugpoint/ToolRunner.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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file exposes an abstraction around a platform C compiler, used to
+// compile C and assembly code.  It also exposes an "AbstractIntepreter"
+// interface, which is used to execute code using one of the LLVM execution
+// engines.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_BUGPOINT_TOOLRUNNER_H
+#define LLVM_TOOLS_BUGPOINT_TOOLRUNNER_H
+
+#include "llvm/ADT/Triple.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/SystemUtils.h"
+#include <exception>
+#include <vector>
+
+namespace llvm {
+
+extern cl::opt<bool> SaveTemps;
+extern Triple TargetTriple;
+
+class LLC;
+
+//===---------------------------------------------------------------------===//
+// CC abstraction
+//
+class CC {
+  std::string CCPath;              // The path to the cc executable.
+  std::string RemoteClientPath;    // The path to the rsh / ssh executable.
+  std::vector<std::string> ccArgs; // CC-specific arguments.
+  CC(StringRef ccPath, StringRef RemotePath,
+     const std::vector<std::string> *CCArgs)
+      : CCPath(std::string(ccPath)), RemoteClientPath(std::string(RemotePath)) {
+    if (CCArgs)
+      ccArgs = *CCArgs;
+  }
+
+public:
+  enum FileType { AsmFile, ObjectFile, CFile };
+
+  static CC *create(const char *Argv0, std::string &Message,
+                    const std::string &CCBinary,
+                    const std::vector<std::string> *Args);
+
+  /// ExecuteProgram - Execute the program specified by "ProgramFile" (which is
+  /// either a .s file, or a .c file, specified by FileType), with the specified
+  /// arguments.  Standard input is specified with InputFile, and standard
+  /// Output is captured to the specified OutputFile location.  The SharedLibs
+  /// option specifies optional native shared objects that can be loaded into
+  /// the program for execution.
+  ///
+  Expected<int> ExecuteProgram(
+      const std::string &ProgramFile, const std::vector<std::string> &Args,
+      FileType fileType, const std::string &InputFile,
+      const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0);
+
+  /// MakeSharedObject - This compiles the specified file (which is either a .c
+  /// file or a .s file) into a shared object.
+  ///
+  Error MakeSharedObject(const std::string &InputFile, FileType fileType,
+                         std::string &OutputFile,
+                         const std::vector<std::string> &ArgsForCC);
+};
+
+//===---------------------------------------------------------------------===//
+/// AbstractInterpreter Class - Subclasses of this class are used to execute
+/// LLVM bitcode in a variety of ways.  This abstract interface hides this
+/// complexity behind a simple interface.
+///
+class AbstractInterpreter {
+  virtual void anchor();
+
+public:
+  static LLC *createLLC(const char *Argv0, std::string &Message,
+                        const std::string &CCBinary,
+                        const std::vector<std::string> *Args = nullptr,
+                        const std::vector<std::string> *CCArgs = nullptr,
+                        bool UseIntegratedAssembler = false);
+
+  static AbstractInterpreter *
+  createLLI(const char *Argv0, std::string &Message,
+            const std::vector<std::string> *Args = nullptr);
+
+  static AbstractInterpreter *
+  createJIT(const char *Argv0, std::string &Message,
+            const std::vector<std::string> *Args = nullptr);
+
+  static AbstractInterpreter *
+  createCustomCompiler(const char *Argv0, std::string &Message,
+                       const std::string &CompileCommandLine);
+
+  static AbstractInterpreter *
+  createCustomExecutor(const char *Argv0, std::string &Message,
+                       const std::string &ExecCommandLine);
+
+  virtual ~AbstractInterpreter() {}
+
+  /// compileProgram - Compile the specified program from bitcode to executable
+  /// code.  This does not produce any output, it is only used when debugging
+  /// the code generator.  It returns false if the code generator fails.
+  virtual Error compileProgram(const std::string &Bitcode, unsigned Timeout = 0,
+                               unsigned MemoryLimit = 0) {
+    return Error::success();
+  }
+
+  /// Compile the specified program from bitcode to code understood by the CC
+  /// driver (either C or asm).  Returns an error if the code generator fails,,
+  /// otherwise, the type of code emitted.
+  virtual Expected<CC::FileType> OutputCode(const std::string &Bitcode,
+                                            std::string &OutFile,
+                                            unsigned Timeout = 0,
+                                            unsigned MemoryLimit = 0) {
+    return make_error<StringError>(
+        "OutputCode not supported by this AbstractInterpreter!",
+        inconvertibleErrorCode());
+  }
+
+  /// ExecuteProgram - Run the specified bitcode file, emitting output to the
+  /// specified filename.  This sets RetVal to the exit code of the program or
+  /// returns an Error if a problem was encountered that prevented execution of
+  /// the program.
+  ///
+  virtual Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs = std::vector<std::string>(),
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) = 0;
+};
+
+//===---------------------------------------------------------------------===//
+// LLC Implementation of AbstractIntepreter interface
+//
+class LLC : public AbstractInterpreter {
+  std::string LLCPath;               // The path to the LLC executable.
+  std::vector<std::string> ToolArgs; // Extra args to pass to LLC.
+  CC *cc;
+  bool UseIntegratedAssembler;
+
+public:
+  LLC(const std::string &llcPath, CC *cc, const std::vector<std::string> *Args,
+      bool useIntegratedAssembler)
+      : LLCPath(llcPath), cc(cc),
+        UseIntegratedAssembler(useIntegratedAssembler) {
+    ToolArgs.clear();
+    if (Args)
+      ToolArgs = *Args;
+  }
+  ~LLC() override { delete cc; }
+
+  /// compileProgram - Compile the specified program from bitcode to executable
+  /// code.  This does not produce any output, it is only used when debugging
+  /// the code generator.  Returns false if the code generator fails.
+  Error compileProgram(const std::string &Bitcode, unsigned Timeout = 0,
+                       unsigned MemoryLimit = 0) override;
+
+  Expected<int> ExecuteProgram(
+      const std::string &Bitcode, const std::vector<std::string> &Args,
+      const std::string &InputFile, const std::string &OutputFile,
+      const std::vector<std::string> &CCArgs = std::vector<std::string>(),
+      const std::vector<std::string> &SharedLibs = std::vector<std::string>(),
+      unsigned Timeout = 0, unsigned MemoryLimit = 0) override;
+
+  Expected<CC::FileType> OutputCode(const std::string &Bitcode,
+                                    std::string &OutFile, unsigned Timeout = 0,
+                                    unsigned MemoryLimit = 0) override;
+};
+
+/// Find the first executable file \ExeName, either in the user's PATH or,
+/// failing that, in the same directory as argv[0]. This allows us to find
+/// another LLVM tool if it is built in the same directory. If no executable is
+/// found, an error is returned.
+ErrorOr<std::string> FindProgramByName(const std::string &ExeName,
+                                       const char *Argv0, void *MainAddr);
+
+} // End llvm namespace
+
+#endif
diff --git a/contrib/libs/llvm12/tools/bugpoint/bugpoint.cpp b/contrib/libs/llvm12/tools/bugpoint/bugpoint.cpp
new file mode 100644
index 0000000000..937ec23231
--- /dev/null
+++ b/contrib/libs/llvm12/tools/bugpoint/bugpoint.cpp
@@ -0,0 +1,244 @@
+//===- bugpoint.cpp - The LLVM Bugpoint 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 is an automated compiler debugger tool.  It is used to narrow
+// down miscompilations and crash problems to a specific pass in the compiler,
+// and the specific Module or Function input that is causing the problem.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BugDriver.h"
+#include "ToolRunner.h"
+#include "llvm/Config/llvm-config.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/LegacyPassNameParser.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/LinkAllIR.h"
+#include "llvm/LinkAllPasses.h"
+#include "llvm/Passes/PassPlugin.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/PluginLoader.h"
+#include "llvm/Support/PrettyStackTrace.h"
+#include "llvm/Support/Process.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/Valgrind.h"
+#include "llvm/Transforms/IPO/AlwaysInliner.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+
+// Enable this macro to debug bugpoint itself.
+//#define DEBUG_BUGPOINT 1
+
+using namespace llvm;
+
+static cl::opt<bool>
+    FindBugs("find-bugs", cl::desc("Run many different optimization sequences "
+                                   "on program to find bugs"),
+             cl::init(false));
+
+static cl::list<std::string>
+    InputFilenames(cl::Positional, cl::OneOrMore,
+                   cl::desc("<input llvm ll/bc files>"));
+
+static cl::opt<unsigned> TimeoutValue(
+    "timeout", cl::init(300), cl::value_desc("seconds"),
+    cl::desc("Number of seconds program is allowed to run before it "
+             "is killed (default is 300s), 0 disables timeout"));
+
+static cl::opt<int> MemoryLimit(
+    "mlimit", cl::init(-1), cl::value_desc("MBytes"),
+    cl::desc("Maximum amount of memory to use. 0 disables check. Defaults to "
+             "400MB (800MB under valgrind, 0 with sanitizers)."));
+
+static cl::opt<bool>
+    UseValgrind("enable-valgrind",
+                cl::desc("Run optimizations through valgrind"));
+
+// The AnalysesList is automatically populated with registered Passes by the
+// PassNameParser.
+//
+static cl::list<const PassInfo *, bool, PassNameParser>
+    PassList(cl::desc("Passes available:"), cl::ZeroOrMore);
+
+static cl::opt<bool>
+    StandardLinkOpts("std-link-opts",
+                     cl::desc("Include the standard link time optimizations"));
+
+static cl::opt<bool>
+    OptLevelO1("O1", cl::desc("Optimization level 1. Identical to 'opt -O1'"));
+
+static cl::opt<bool>
+    OptLevelO2("O2", cl::desc("Optimization level 2. Identical to 'opt -O2'"));
+
+static cl::opt<bool> OptLevelOs(
+    "Os",
+    cl::desc(
+        "Like -O2 with extra optimizations for size. Similar to clang -Os"));
+
+static cl::opt<bool>
+OptLevelOz("Oz",
+           cl::desc("Like -Os but reduces code size further. Similar to clang -Oz"));
+
+static cl::opt<bool>
+    OptLevelO3("O3", cl::desc("Optimization level 3. Identical to 'opt -O3'"));
+
+static cl::opt<std::string>
+    OverrideTriple("mtriple", cl::desc("Override target triple for module"));
+
+/// BugpointIsInterrupted - Set to true when the user presses ctrl-c.
+bool llvm::BugpointIsInterrupted = false;
+
+#ifndef DEBUG_BUGPOINT
+static void BugpointInterruptFunction() { BugpointIsInterrupted = true; }
+#endif
+
+// Hack to capture a pass list.
+namespace {
+class AddToDriver : public legacy::FunctionPassManager {
+  BugDriver &D;
+
+public:
+  AddToDriver(BugDriver &_D) : FunctionPassManager(nullptr), D(_D) {}
+
+  void add(Pass *P) override {
+    const void *ID = P->getPassID();
+    const PassInfo *PI = PassRegistry::getPassRegistry()->getPassInfo(ID);
+    D.addPass(std::string(PI->getPassArgument()));
+  }
+};
+}
+
+// This routine adds optimization passes based on selected optimization level,
+// OptLevel.
+//
+// OptLevel - Optimization Level
+static void AddOptimizationPasses(legacy::FunctionPassManager &FPM,
+                                  unsigned OptLevel,
+                                  unsigned SizeLevel) {
+  PassManagerBuilder Builder;
+  Builder.OptLevel = OptLevel;
+  Builder.SizeLevel = SizeLevel;
+
+  if (OptLevel > 1)
+    Builder.Inliner = createFunctionInliningPass(OptLevel, SizeLevel, false);
+  else
+    Builder.Inliner = createAlwaysInlinerLegacyPass();
+
+  Builder.populateFunctionPassManager(FPM);
+  Builder.populateModulePassManager(FPM);
+}
+
+#define HANDLE_EXTENSION(Ext)                                                  \
+  llvm::PassPluginLibraryInfo get##Ext##PluginInfo();
+#include "llvm/Support/Extension.def"
+
+int main(int argc, char **argv) {
+#ifndef DEBUG_BUGPOINT
+  InitLLVM X(argc, argv);
+#endif
+
+  // Initialize passes
+  PassRegistry &Registry = *PassRegistry::getPassRegistry();
+  initializeCore(Registry);
+  initializeScalarOpts(Registry);
+  initializeObjCARCOpts(Registry);
+  initializeVectorization(Registry);
+  initializeIPO(Registry);
+  initializeAnalysis(Registry);
+  initializeTransformUtils(Registry);
+  initializeInstCombine(Registry);
+  initializeAggressiveInstCombine(Registry);
+  initializeInstrumentation(Registry);
+  initializeTarget(Registry);
+
+  if (std::getenv("bar") == (char*) -1) {
+    InitializeAllTargets();
+    InitializeAllTargetMCs();
+    InitializeAllAsmPrinters();
+    InitializeAllAsmParsers();
+  }
+
+  cl::ParseCommandLineOptions(argc, argv,
+                              "LLVM automatic testcase reducer. See\nhttp://"
+                              "llvm.org/cmds/bugpoint.html"
+                              " for more information.\n");
+#ifndef DEBUG_BUGPOINT
+  sys::SetInterruptFunction(BugpointInterruptFunction);
+#endif
+
+  LLVMContext Context;
+  // If we have an override, set it and then track the triple we want Modules
+  // to use.
+  if (!OverrideTriple.empty()) {
+    TargetTriple.setTriple(Triple::normalize(OverrideTriple));
+    outs() << "Override triple set to '" << TargetTriple.getTriple() << "'\n";
+  }
+
+  if (MemoryLimit < 0) {
+    // Set the default MemoryLimit.  Be sure to update the flag's description if
+    // you change this.
+    if (sys::RunningOnValgrind() || UseValgrind)
+      MemoryLimit = 800;
+    else
+      MemoryLimit = 400;
+#if (LLVM_ADDRESS_SANITIZER_BUILD || LLVM_MEMORY_SANITIZER_BUILD ||            \
+     LLVM_THREAD_SANITIZER_BUILD)
+    // Starting from kernel 4.9 memory allocated with mmap is counted against
+    // RLIMIT_DATA. Sanitizers need to allocate tens of terabytes for shadow.
+    MemoryLimit = 0;
+#endif
+  }
+
+  BugDriver D(argv[0], FindBugs, TimeoutValue, MemoryLimit, UseValgrind,
+              Context);
+  if (D.addSources(InputFilenames))
+    return 1;
+
+  AddToDriver PM(D);
+
+  if (StandardLinkOpts) {
+    PassManagerBuilder Builder;
+    Builder.Inliner = createFunctionInliningPass();
+    Builder.populateLTOPassManager(PM);
+  }
+
+  if (OptLevelO1)
+    AddOptimizationPasses(PM, 1, 0);
+  else if (OptLevelO2)
+    AddOptimizationPasses(PM, 2, 0);
+  else if (OptLevelO3)
+    AddOptimizationPasses(PM, 3, 0);
+  else if (OptLevelOs)
+    AddOptimizationPasses(PM, 2, 1);
+  else if (OptLevelOz)
+    AddOptimizationPasses(PM, 2, 2);
+
+  for (const PassInfo *PI : PassList)
+    D.addPass(std::string(PI->getPassArgument()));
+
+// Bugpoint has the ability of generating a plethora of core files, so to
+// avoid filling up the disk, we prevent it
+#ifndef DEBUG_BUGPOINT
+  sys::Process::PreventCoreFiles();
+#endif
+
+// Needed to pull in symbols from statically linked extensions, including static
+// registration. It is unused otherwise because bugpoint has no support for
+// NewPM.
+#define HANDLE_EXTENSION(Ext)                                                  \
+  (void)get##Ext##PluginInfo();
+#include "llvm/Support/Extension.def"
+
+  if (Error E = D.run()) {
+    errs() << toString(std::move(E));
+    return 1;
+  }
+  return 0;
+}