diff options
Diffstat (limited to 'contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp')
-rw-r--r-- | contrib/libs/llvm12/tools/llvm-reduce/deltas/Delta.cpp | 180 |
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"; +} |