aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp')
-rw-r--r--contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp180
1 files changed, 180 insertions, 0 deletions
diff --git a/contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp b/contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp
new file mode 100644
index 0000000000..9b0969e936
--- /dev/null
+++ b/contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp
@@ -0,0 +1,180 @@
+//===- Delta.cpp - Delta Debugging Algorithm Implementation ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the implementation for the Delta Debugging Algorithm:
+// it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
+// into chunks and tries to reduce the number chunks that are interesting.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include <fstream>
+#include <set>
+
+using namespace llvm;
+
+void writeOutput(llvm::Module *M, llvm::StringRef Message);
+
+bool IsReduced(Module &M, TestRunner &Test, SmallString<128> &CurrentFilepath) {
+ // Write Module to tmp file
+ int FD;
+ std::error_code EC =
+ sys::fs::createTemporaryFile("llvm-reduce", "ll", FD, CurrentFilepath);
+ if (EC) {
+ errs() << "Error making unique filename: " << EC.message() << "!\n";
+ exit(1);
+ }
+
+ ToolOutputFile Out(CurrentFilepath, FD);
+ M.print(Out.os(), /*AnnotationWriter=*/nullptr);
+ Out.os().close();
+ if (Out.os().has_error()) {
+ errs() << "Error emitting bitcode to file '" << CurrentFilepath << "'!\n";
+ exit(1);
+ }
+
+ // Current Chunks aren't interesting
+ return Test.run(CurrentFilepath);
+}
+
+/// Counts the amount of lines for a given file
+static int getLines(StringRef Filepath) {
+ int Lines = 0;
+ std::string CurrLine;
+ std::ifstream FileStream{std::string(Filepath)};
+
+ while (std::getline(FileStream, CurrLine))
+ ++Lines;
+
+ return Lines;
+}
+
+/// Splits Chunks in half and prints them.
+/// If unable to split (when chunk size is 1) returns false.
+static bool increaseGranularity(std::vector<Chunk> &Chunks) {
+ errs() << "Increasing granularity...";
+ std::vector<Chunk> NewChunks;
+ bool SplitOne = false;
+
+ for (auto &C : Chunks) {
+ if (C.end - C.begin == 0)
+ NewChunks.push_back(C);
+ else {
+ int Half = (C.begin + C.end) / 2;
+ NewChunks.push_back({C.begin, Half});
+ NewChunks.push_back({Half + 1, C.end});
+ SplitOne = true;
+ }
+ }
+ if (SplitOne) {
+ Chunks = NewChunks;
+ errs() << "Success! New Chunks:\n";
+ for (auto C : Chunks) {
+ errs() << '\t';
+ C.print();
+ errs() << '\n';
+ }
+ }
+ return SplitOne;
+}
+
+/// Runs the Delta Debugging algorithm, splits the code into chunks and
+/// reduces the amount of chunks that are considered interesting by the
+/// given test.
+void llvm::runDeltaPass(
+ TestRunner &Test, int Targets,
+ std::function<void(const std::vector<Chunk> &, Module *)>
+ ExtractChunksFromModule) {
+ assert(Targets >= 0);
+ if (!Targets) {
+ errs() << "\nNothing to reduce\n";
+ return;
+ }
+
+ if (Module *Program = Test.getProgram()) {
+ SmallString<128> CurrentFilepath;
+ if (!IsReduced(*Program, Test, CurrentFilepath)) {
+ errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
+ exit(1);
+ }
+
+ assert(!verifyModule(*Program, &errs()) &&
+ "input module is broken before making changes");
+ }
+
+ std::vector<Chunk> ChunksStillConsideredInteresting = {{1, Targets}};
+ std::unique_ptr<Module> ReducedProgram;
+
+ bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity;
+ do {
+ FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false;
+
+ std::set<Chunk> UninterestingChunks;
+ for (Chunk &ChunkToCheckForUninterestingness :
+ reverse(ChunksStillConsideredInteresting)) {
+ // Take all of ChunksStillConsideredInteresting chunks, except those we've
+ // already deemed uninteresting (UninterestingChunks) but didn't remove
+ // from ChunksStillConsideredInteresting yet, and additionally ignore
+ // ChunkToCheckForUninterestingness chunk.
+ std::vector<Chunk> CurrentChunks;
+ CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -
+ UninterestingChunks.size() - 1);
+ copy_if(ChunksStillConsideredInteresting,
+ std::back_inserter(CurrentChunks), [&](const Chunk &C) {
+ return !UninterestingChunks.count(C) &&
+ C != ChunkToCheckForUninterestingness;
+ });
+
+ // Clone module before hacking it up..
+ std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram());
+ // Generate Module with only Targets inside Current Chunks
+ ExtractChunksFromModule(CurrentChunks, Clone.get());
+
+ // Some reductions may result in invalid IR. Skip such reductions.
+ if (verifyModule(*Clone.get(), &errs())) {
+ errs() << " **** WARNING | reduction resulted in invalid module, "
+ "skipping\n";
+ continue;
+ }
+
+ errs() << "Ignoring: ";
+ ChunkToCheckForUninterestingness.print();
+ for (const Chunk &C : UninterestingChunks)
+ C.print();
+
+ SmallString<128> CurrentFilepath;
+ if (!IsReduced(*Clone, Test, CurrentFilepath)) {
+ // Program became non-reduced, so this chunk appears to be interesting.
+ errs() << "\n";
+ continue;
+ }
+
+ FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;
+ UninterestingChunks.insert(ChunkToCheckForUninterestingness);
+ ReducedProgram = std::move(Clone);
+ errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
+ writeOutput(ReducedProgram.get(), "Saved new best reduction to ");
+ }
+ // Delete uninteresting chunks
+ erase_if(ChunksStillConsideredInteresting,
+ [&UninterestingChunks](const Chunk &C) {
+ return UninterestingChunks.count(C);
+ });
+ } while (!ChunksStillConsideredInteresting.empty() &&
+ (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity ||
+ increaseGranularity(ChunksStillConsideredInteresting)));
+
+ // If we reduced the testcase replace it
+ if (ReducedProgram)
+ Test.setProgram(std::move(ReducedProgram));
+ errs() << "Couldn't increase anymore.\n";
+}