Skip to content

Commit 099e5c5

Browse files
author
Diego Trevino Ferrer
committedAug 7, 2019
Added Delta IR Reduction Tool
Summary: Tool parses input IR file, and runs the delta debugging algorithm to reduce the functions inside the input file. Reviewers: alexshap, chandlerc Subscribers: mgorny, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63672 > llvm-svn: 368071 llvm-svn: 368112
·
llvmorg-21-initllvmorg-10.0.0-rc1
1 parent feef101 commit 099e5c5

13 files changed

+763
-0
lines changed
 

‎llvm/docs/BugpointRedesign.md

+106
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
# Bugpoint Redesign
2+
Author: Diego Treviño (diegotf@google.com)
3+
4+
Date: 2019-06-05
5+
6+
Status: Draft
7+
8+
9+
## Introduction
10+
As use of bugpoint has grown several areas of improvement have been identified
11+
through years of use: confusing to use, slow, it doesn’t always produce high
12+
quality test cases, etc. This document proposes a new approach with a narrower
13+
focus: minimization of IR test cases.
14+
15+
16+
## Proposed New Design
17+
18+
19+
### Narrow focus: test-case reduction
20+
The main focus will be a code reduction strategy to obtain much smaller test
21+
cases that still have the same property as the original one. This will be done
22+
via classic delta debugging and by adding some IR-specific reductions (e.g.
23+
replacing globals, removing unused instructions, etc), similar to what
24+
already exists, but with more in-depth minimization.
25+
26+
27+
Granted, if the community differs on this proposal, the legacy code could still
28+
be present in the tool, but with the caveat of still being documented and
29+
designed towards delta reduction.
30+
31+
32+
### Command-Line Options
33+
We are proposing to reduce the plethora of bugpoint’s options to just two: an
34+
interesting-ness test and the arguments for said test, similar to other delta
35+
reduction tools such as CReduce, Delta, and Lithium; the tool should feel less
36+
cluttered, and there should also be no uncertainty about how to operate it.
37+
38+
39+
The interesting-ness test that’s going to be run to reduce the code is given
40+
by name:
41+
`--test=<test_name>`
42+
If a `--test` option is not given, the program exits; this option is similar
43+
to bugpoint’s current `-compile-custom` option, which lets the user run a
44+
custom script.
45+
46+
47+
The interesting-ness test would be defined as a script that returns 0 when the
48+
IR achieves a user-defined behaviour (e.g. failure to compile on clang) and a
49+
nonzero value when otherwise. Leaving the user the freedom to determine what is
50+
and isn’t interesting to the tool, and thus, streamlining the process of
51+
reducing a test-case.
52+
53+
54+
If the test accepts any arguments (excluding the input ll/bc file), they are
55+
given via the following flag:
56+
`--test_args=<test_arguments>`
57+
If unspecified, the test is run as given. It’s worth noting that the input file
58+
would be passed as a parameter to the test, similar how `-compile-custom`
59+
currently operates.
60+
61+
62+
### Implementation
63+
The tool would behave similar to CReduce’s functionality in that it would have a
64+
list of passes that try to minimize the given test-case. We should be able to
65+
modularize the tool’s behavior, as well as making it easier to maintain and
66+
expand.
67+
68+
69+
The first version of this redesign would try to:
70+
71+
72+
* Split the code into chunks and discard those that fail the given test
73+
* Discard functions, instructions and metadata that don’t influence the
74+
interesting-ness test
75+
* Remove unused parameters from functions
76+
* Eliminate unvisited conditional paths
77+
* Rename variables to more regular ones (such as “a”, “b”, “c”, etc.)
78+
79+
80+
Once these passes are implemented, more meaningful reductions (such as type
81+
reduction) would be added to the tool, to even further reduce IR.
82+
83+
84+
## Background on historical bugpoint issues
85+
86+
87+
### Root Cause Analysis
88+
Presently, bugpoint takes a long time to find the source problem in a given IR
89+
file, mainly due to the fact that it tries to debug the input by running
90+
various strategies to classify the bug, which in turn run multiple optimizer
91+
and compilation passes over the input, taking up a lot of time. Furthermore,
92+
when the IR crashes, it tries to reduce it by performing some sub-optimal
93+
passes (e.g. a lot of unreachable blocks), and sometimes even fails to minimize
94+
at all.
95+
96+
97+
### "Quirky" Interface
98+
Bugpoint’s current interface overwhelms and confuses the user, the help screen
99+
alone ends up confusing rather providing guidance, as seen below:
100+
101+
![Bugpoint's help option showcase](https://lh6.googleusercontent.com/sbpaSVHzpVVZKKAgHL9gvfzTWdgh3ju0KiDYql6WmWZfDYrdauOJMcuo9PP_V1dq8JQfMHOSKTv3lJcSpVytUyU8r5tJ2KTlGB0b2ve7jsZ3nVX8K8ItAbsA0JWkFKw67VJnq99m)
102+
103+
And, not only are there numerous features and options, but some of them also
104+
work in unexpected ways and most of the time the user ends up using a custom
105+
script. Pruning and simplifying the interface will be worth considering in
106+
order to make the tool more useful in the general case and easier to maintain.

‎llvm/test/Reduce/Inputs/remove-funcs.sh

+9
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
#!/bin/sh
2+
3+
matches=$(cat $1 | grep "@interesting" | wc -l)
4+
5+
if [[ $matches > 0 ]]; then
6+
exit 0
7+
else
8+
exit 1
9+
fi

‎llvm/test/Reduce/remove-funcs.ll

+34
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
; Test that llvm-reduce can remove uninteresting functions as well as
2+
; their InstCalls.
3+
;
4+
; RUN: llvm-reduce --test %p/Inputs/remove-funcs.sh %s
5+
; RUN: cat reduced.ll | FileCheck %s
6+
; REQUIRES: plugins, shell
7+
8+
; CHECK-NOT: uninteresting1()
9+
define i32 @uninteresting1() {
10+
entry:
11+
ret i32 0
12+
}
13+
14+
; CHECK: interesting()
15+
define i32 @interesting() {
16+
entry:
17+
; CHECK: call i32 @interesting()
18+
%call2 = call i32 @interesting()
19+
; CHECK-NOT: call i32 @uninteresting1()
20+
%call = call i32 @uninteresting1()
21+
ret i32 5
22+
}
23+
24+
; CHECK-NOT: uninteresting2()
25+
define i32 @uninteresting2() {
26+
entry:
27+
ret i32 0
28+
}
29+
30+
; CHECK-NOT: uninteresting3()
31+
define i32 @uninteresting3() {
32+
entry:
33+
ret i32 10
34+
}

‎llvm/tools/LLVMBuild.txt

+1
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ subdirectories =
4848
llvm-pdbutil
4949
llvm-profdata
5050
llvm-rc
51+
llvm-reduce
5152
llvm-rtdyld
5253
llvm-size
5354
llvm-split

‎llvm/tools/llvm-reduce/CMakeLists.txt

+23
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
set(LLVM_LINK_COMPONENTS
2+
AllTargetsAsmParsers
3+
AllTargetsCodeGens
4+
AllTargetsDescs
5+
AllTargetsInfos
6+
IRReader
7+
Support
8+
Target
9+
TransformUtils
10+
)
11+
12+
# Support plugins.
13+
set(LLVM_NO_DEAD_STRIP 1)
14+
15+
add_llvm_tool(llvm-reduce
16+
llvm-reduce.cpp
17+
TestRunner.cpp
18+
deltas/RemoveFunctions.cpp
19+
20+
DEPENDS
21+
intrinsics_gen
22+
)
23+
export_executable_symbols(llvm-reduce)

‎llvm/tools/llvm-reduce/DeltaManager.h

+26
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This class calls each specialized Delta pass by passing it as a template to
10+
// the generic Delta Pass.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "TestRunner.h"
15+
#include "deltas/Delta.h"
16+
#include "deltas/RemoveFunctions.h"
17+
18+
namespace llvm {
19+
20+
inline void runDeltaPasses(TestRunner &Tester) {
21+
outs() << "Reducing functions...\n";
22+
Delta<RemoveFunctions>::run(Tester);
23+
// TODO: Implement the rest of the Delta Passes
24+
}
25+
26+
} // namespace llvm

‎llvm/tools/llvm-reduce/LLVMBuild.txt

+24
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
;===- ./tools/llvm-reduce/LLVMBuild.txt ------------------------*- Conf -*--===;
2+
;
3+
; Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
; See https://llvm.org/LICENSE.txt for license information.
5+
; SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
;
7+
;===------------------------------------------------------------------------===;
8+
;
9+
; This is an LLVMBuild description file for the components in this subdirectory.
10+
;
11+
; For more information on the LLVMBuild system, please see:
12+
;
13+
; http://llvm.org/docs/LLVMBuild.html
14+
;
15+
;===------------------------------------------------------------------------===;
16+
17+
[component_0]
18+
type = Tool
19+
name = llvm-reduce
20+
parent = Tools
21+
required_libraries =
22+
BitReader
23+
IRReader
24+
all-targets

‎llvm/tools/llvm-reduce/TestRunner.cpp

+32
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#include "TestRunner.h"
2+
3+
using namespace llvm;
4+
5+
TestRunner::TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
6+
StringRef ReducedFilepath, SmallString<128> TmpDirectory)
7+
: TestName(TestName), TestArgs(TestArgs), ReducedFilepath(ReducedFilepath),
8+
TmpDirectory(TmpDirectory) {}
9+
10+
/// Runs the interestingness test, passes file to be tested as first argument
11+
/// and other specified test arguments after that.
12+
int TestRunner::run(StringRef Filename) {
13+
std::vector<StringRef> ProgramArgs;
14+
ProgramArgs.push_back(TestName);
15+
ProgramArgs.push_back(Filename);
16+
17+
for (unsigned I = 0, E = TestArgs.size(); I != E; ++I)
18+
ProgramArgs.push_back(TestArgs[I].c_str());
19+
20+
StringRef SR = "";
21+
Optional<StringRef> Redirects[3] = {SR, SR, SR}; // STDIN, STDOUT, STDERR
22+
int Result = sys::ExecuteAndWait(TestName, ProgramArgs, None, Redirects);
23+
24+
if (Result < 0) {
25+
Error E = make_error<StringError>("Error running interesting-ness test\n",
26+
inconvertibleErrorCode());
27+
outs() << toString(std::move(E));
28+
exit(1);
29+
}
30+
31+
return !Result;
32+
}

‎llvm/tools/llvm-reduce/TestRunner.h

+52
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
9+
#ifndef LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
10+
#define LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
11+
12+
#include "llvm/ADT/SmallString.h"
13+
#include "llvm/IR/Module.h"
14+
#include "llvm/Support/Error.h"
15+
#include "llvm/Support/Program.h"
16+
#include <vector>
17+
18+
namespace llvm {
19+
20+
// This class contains all the info necessary for running the provided
21+
// interesting-ness test, as well as the most reduced module and its
22+
// respective filename.
23+
class TestRunner {
24+
public:
25+
TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
26+
StringRef ReducedFilepath, SmallString<128> TmpDirectory);
27+
28+
/// Runs the interesting-ness test for the specified file
29+
/// @returns 0 if test was successful, 1 if otherwise
30+
int run(StringRef Filename);
31+
32+
/// Filename to the most reduced testcase
33+
StringRef getReducedFilepath() const { return ReducedFilepath; }
34+
/// Directory where tmp files are created
35+
StringRef getTmpDir() const { return TmpDirectory; }
36+
/// Returns the most reduced version of the original testcase
37+
Module *getProgram() const { return Program.get(); }
38+
39+
void setReducedFilepath(SmallString<128> F) { ReducedFilepath = F; }
40+
void setProgram(std::unique_ptr<Module> P) { Program = std::move(P); }
41+
42+
private:
43+
SmallString<128> TestName;
44+
std::vector<std::string> TestArgs;
45+
SmallString<128> ReducedFilepath;
46+
SmallString<128> TmpDirectory;
47+
std::unique_ptr<Module> Program;
48+
};
49+
50+
} // namespace llvm
51+
52+
#endif

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

+222
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,222 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This file contains the implementation for the Delta Debugging Algorithm:
10+
// it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
11+
// into chunks and tries to reduce the number chunks that are interesting.
12+
//
13+
//===----------------------------------------------------------------------===//
14+
15+
#ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
16+
#define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
17+
18+
#include "../TestRunner.h"
19+
#include "llvm/IR/Verifier.h"
20+
#include "llvm/Support/FileSystem.h"
21+
#include "llvm/Support/Path.h"
22+
#include "llvm/Support/ScopedPrinter.h"
23+
#include "llvm/Support/ToolOutputFile.h"
24+
#include <fstream>
25+
#include <set>
26+
#include <vector>
27+
28+
using namespace llvm;
29+
30+
struct Chunk {
31+
int begin;
32+
int end;
33+
34+
/// Operator when populating CurrentChunks in Generic Delta Pass
35+
friend bool operator!=(const Chunk &C1, const Chunk &C2) {
36+
return C1.begin != C2.begin && C1.end != C2.end;
37+
}
38+
39+
/// Operator used for sets
40+
friend bool operator<(const Chunk &C1, const Chunk &C2) {
41+
return C1.begin < C2.begin;
42+
}
43+
};
44+
45+
/// Writes IR code to the given Filepath
46+
inline bool writeProgramToFile(StringRef Filepath, int FD, const Module &M) {
47+
ToolOutputFile Out(Filepath, FD);
48+
M.print(Out.os(), /*AnnotationWriter=*/nullptr);
49+
Out.os().close();
50+
51+
if (!Out.os().has_error()) {
52+
Out.keep();
53+
return false;
54+
}
55+
return true;
56+
}
57+
58+
/// Creates a temporary (and unique) file inside the tmp folder and outputs
59+
/// the module inside it.
60+
inline SmallString<128> createTmpFile(Module *M, StringRef TmpDir) {
61+
SmallString<128> UniqueFilepath;
62+
int UniqueFD;
63+
64+
std::error_code EC = sys::fs::createUniqueFile(TmpDir + "/tmp-%%%.ll",
65+
UniqueFD, UniqueFilepath);
66+
if (EC) {
67+
errs() << "Error making unique filename: " << EC.message() << "!\n";
68+
exit(1);
69+
}
70+
71+
if (writeProgramToFile(UniqueFilepath, UniqueFD, *M)) {
72+
errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n";
73+
exit(1);
74+
}
75+
return UniqueFilepath;
76+
}
77+
78+
/// Prints the Chunk Indexes with the following format: [start, end], if
79+
/// chunk is at minimum size (1), then it just displays [start].
80+
inline void printChunks(std::vector<Chunk> Chunks, bool Oneline = false) {
81+
for (auto C : Chunks) {
82+
if (!Oneline)
83+
outs() << '\t';
84+
outs() << "[" << C.begin;
85+
if (C.end - C.begin != 0)
86+
outs() << "," << C.end;
87+
outs() << "]";
88+
if (!Oneline)
89+
outs() << '\n';
90+
}
91+
}
92+
93+
/// Counts the amount of lines for a given file
94+
inline unsigned getLines(StringRef Filepath) {
95+
unsigned Lines = 0;
96+
std::string CurrLine;
97+
std::ifstream FileStream(Filepath);
98+
99+
while (std::getline(FileStream, CurrLine))
100+
++Lines;
101+
102+
return Lines;
103+
}
104+
105+
/// Splits Chunks in half and prints them.
106+
/// If unable to split (when chunk size is 1) returns false.
107+
inline bool increaseGranularity(std::vector<Chunk> &Chunks) {
108+
outs() << "Increasing granularity...";
109+
std::vector<Chunk> NewChunks;
110+
bool SplitOne = false;
111+
112+
for (auto &C : Chunks) {
113+
if (C.end - C.begin == 0)
114+
NewChunks.push_back(C);
115+
else {
116+
int Half = (C.begin + C.end) / 2;
117+
NewChunks.push_back({C.begin, Half});
118+
NewChunks.push_back({Half + 1, C.end});
119+
SplitOne = true;
120+
}
121+
}
122+
if (SplitOne) {
123+
Chunks = NewChunks;
124+
outs() << "Success! New Chunks:\n";
125+
printChunks(Chunks);
126+
}
127+
return SplitOne;
128+
}
129+
130+
namespace llvm {
131+
132+
/// This class implements the Delta Debugging algorithm, it receives a set of
133+
/// Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and splits them
134+
/// in half; these chunks of targets are then tested while ignoring one chunk,
135+
/// if a chunk is proven to be uninteresting (i.e. fails the test) it is
136+
/// removed from consideration. Otherwise, the algorithm will attempt to split
137+
/// the Chunks in half and start the process again, until it can't split chunks
138+
/// anymore.
139+
///
140+
/// The class is intended to be called statically by the DeltaManager class
141+
/// alongside a specialized delta pass (e.g. RemoveFunctions) passed as a
142+
/// template.
143+
/// This specialized pass implements two functions:
144+
/// * getTargetCount, which returns the amount of targets (e.g. Functions)
145+
/// there are in the Module.
146+
/// * extractChunksFromModule, which clones the given Module and modifies it
147+
/// so it only contains Chunk Targets.
148+
///
149+
/// Other implementations of the Delta Debugging algorithm can be found in the
150+
/// CReduce, Delta, and Lithium projects.
151+
template <class P> class Delta {
152+
public:
153+
/// Runs the Delta Debugging algorithm, splits the code into chunks and
154+
/// reduces the amount of chunks that are considered interesting by the
155+
/// given test.
156+
static void run(TestRunner &Test) {
157+
int TargetCount = P::getTargetCount(Test.getProgram());
158+
std::vector<Chunk> Chunks = {{1, TargetCount}};
159+
std::set<Chunk> UninterestingChunks;
160+
std::unique_ptr<Module> ReducedProgram;
161+
162+
if (Test.run(Test.getReducedFilepath()))
163+
increaseGranularity(Chunks);
164+
else {
165+
outs() << "Error: input file isnt interesting\n";
166+
exit(1);
167+
}
168+
169+
do {
170+
UninterestingChunks = {};
171+
for (int I = Chunks.size() - 1; I >= 0; --I) {
172+
std::vector<Chunk> CurrentChunks;
173+
174+
for (auto C : Chunks)
175+
if (!UninterestingChunks.count(C) && C != Chunks[I])
176+
CurrentChunks.push_back(C);
177+
178+
// Generate Module with only Targets inside Current Chunks
179+
std::unique_ptr<Module> CurrentProgram =
180+
P::extractChunksFromModule(CurrentChunks, Test.getProgram());
181+
// Write Module to tmp file
182+
SmallString<128> CurrentFilepath =
183+
createTmpFile(CurrentProgram.get(), Test.getTmpDir());
184+
185+
outs() << "Testing with: ";
186+
printChunks(CurrentChunks, /*Oneline=*/true);
187+
outs() << " | " << sys::path::filename(CurrentFilepath);
188+
189+
// Current Chunks aren't interesting
190+
if (!Test.run(CurrentFilepath)) {
191+
outs() << "\n";
192+
continue;
193+
}
194+
195+
// We only care about interesting chunks if they reduce the testcase
196+
if (getLines(CurrentFilepath) < getLines(Test.getReducedFilepath())) {
197+
UninterestingChunks.insert(Chunks[I]);
198+
Test.setReducedFilepath(CurrentFilepath);
199+
ReducedProgram = std::move(CurrentProgram);
200+
outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath);
201+
}
202+
outs() << "\n";
203+
}
204+
// Delete uninteresting chunks
205+
auto UnwantedChunks = Chunks.end();
206+
UnwantedChunks = std::remove_if(Chunks.begin(), Chunks.end(),
207+
[UninterestingChunks](const Chunk &C) {
208+
return UninterestingChunks.count(C);
209+
});
210+
Chunks.erase(UnwantedChunks, Chunks.end());
211+
} while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
212+
213+
// If we reduced the testcase replace it
214+
if (ReducedProgram)
215+
Test.setProgram(std::move(ReducedProgram));
216+
outs() << "Couldn't increase anymore.\n";
217+
}
218+
};
219+
220+
} // namespace llvm
221+
222+
#endif

‎llvm/tools/llvm-reduce/deltas/RemoveFunctions.cpp

+84
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This file is a Specialized Delta Pass, which removes the functions that are
10+
// not in the provided function-chunks.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "RemoveFunctions.h"
15+
16+
using namespace llvm;
17+
18+
/// Removes all the Defined Functions (as well as their calls)
19+
/// that aren't inside any of the desired Chunks.
20+
/// @returns the Module stripped of out-of-chunk functions
21+
std::unique_ptr<Module>
22+
RemoveFunctions::extractChunksFromModule(std::vector<Chunk> ChunksToKeep,
23+
Module *Program) {
24+
std::unique_ptr<Module> Clone = CloneModule(*Program);
25+
26+
// Get functions inside desired chunks
27+
std::set<Function *> FuncsToKeep;
28+
int I = 0, FunctionCount = 1;
29+
for (auto &F : *Clone) {
30+
if (!F.isDeclaration()) {
31+
if (FunctionCount >= ChunksToKeep[I].begin &&
32+
FunctionCount <= ChunksToKeep[I].end) {
33+
FuncsToKeep.insert(&F);
34+
}
35+
if (FunctionCount >= ChunksToKeep[I].end)
36+
++I;
37+
++FunctionCount;
38+
}
39+
}
40+
41+
// Delete out-of-chunk functions, and replace their calls with undef
42+
std::vector<Function *> FuncsToRemove;
43+
for (auto &F : *Clone) {
44+
if (!F.isDeclaration() && !FuncsToKeep.count(&F)) {
45+
F.replaceAllUsesWith(UndefValue::get(F.getType()));
46+
FuncsToRemove.push_back(&F);
47+
}
48+
}
49+
for (auto *F : FuncsToRemove)
50+
F->eraseFromParent();
51+
52+
// Delete instructions with undef calls
53+
std::vector<Instruction *> InstToRemove;
54+
for (auto &F : *Clone)
55+
for (auto &BB : F)
56+
for (auto &I : BB)
57+
if (auto *Call = dyn_cast<CallInst>(&I))
58+
if (!Call->getCalledFunction()) {
59+
// Instruction might be stored / used somewhere else
60+
I.replaceAllUsesWith(UndefValue::get(I.getType()));
61+
InstToRemove.push_back(&I);
62+
}
63+
64+
for (auto *I : InstToRemove)
65+
I->eraseFromParent();
66+
67+
return Clone;
68+
}
69+
70+
/// Counts the amount of non-declaration functions and prints their
71+
/// respective index & name
72+
int RemoveFunctions::getTargetCount(Module *Program) {
73+
// TODO: Silence index with --quiet flag
74+
outs() << "----------------------------\n";
75+
outs() << "Chunk Index Reference:\n";
76+
int FunctionCount = 0;
77+
for (auto &F : *Program)
78+
if (!F.isDeclaration()) {
79+
++FunctionCount;
80+
outs() << "\t" << FunctionCount << ": " << F.getName() << "\n";
81+
}
82+
outs() << "----------------------------\n";
83+
return FunctionCount;
84+
}

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

+28
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This file is a Specialized Delta Pass, which removes the functions that are
10+
// not in the provided function-chunks.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "Delta.h"
15+
#include "llvm/Transforms/Utils/Cloning.h"
16+
17+
namespace llvm {
18+
19+
class RemoveFunctions {
20+
public:
21+
/// Outputs the number of Functions in the given Module
22+
static int getTargetCount(Module *Program);
23+
/// Clones module and returns it with chunk functions only
24+
static std::unique_ptr<Module>
25+
extractChunksFromModule(std::vector<Chunk> ChunksToKeep, Module *Program);
26+
};
27+
28+
} // namespace llvm

‎llvm/tools/llvm-reduce/llvm-reduce.cpp

+122
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
//===- llvm-reduce.cpp - The LLVM Delta Reduction utility -----------------===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This program tries to reduce an IR test case for a given interesting-ness
10+
// test. It runs multiple delta debugging passes in order to minimize the input
11+
// file. It's worth noting that this is a *temporary* tool that will eventually
12+
// be integrated into the bugpoint tool itself.
13+
//
14+
//===----------------------------------------------------------------------===//
15+
16+
#include "DeltaManager.h"
17+
#include "llvm/ADT/SmallString.h"
18+
#include "llvm/IR/LLVMContext.h"
19+
#include "llvm/IR/Verifier.h"
20+
#include "llvm/IRReader/IRReader.h"
21+
#include "llvm/Support/CommandLine.h"
22+
#include "llvm/Support/InitLLVM.h"
23+
#include "llvm/Support/SourceMgr.h"
24+
#include "llvm/Support/raw_ostream.h"
25+
#include <system_error>
26+
#include <vector>
27+
28+
using namespace llvm;
29+
30+
static cl::opt<bool> Help("h", cl::desc("Alias for -help"), cl::Hidden);
31+
static cl::opt<bool> Version("v", cl::desc("Alias for -version"), cl::Hidden);
32+
33+
static cl::opt<std::string> InputFilename(cl::Positional, cl::Required,
34+
cl::desc("<input llvm ll/bc file>"));
35+
36+
static cl::opt<std::string>
37+
TestFilename("test", cl::Required,
38+
cl::desc("Name of the interesting-ness test to be run"));
39+
40+
static cl::list<std::string>
41+
TestArguments("test-arg", cl::ZeroOrMore,
42+
cl::desc("Arguments passed onto the interesting-ness test"));
43+
44+
static cl::opt<std::string>
45+
OutputFilename("output",
46+
cl::desc("Specify the output file. default: reduced.ll"));
47+
static cl::alias OutputFileAlias("o", cl::desc("Alias for -output"),
48+
cl::aliasopt(OutputFilename));
49+
50+
static cl::opt<bool>
51+
ReplaceInput("in-place",
52+
cl::desc("WARNING: This option will replace your input file"
53+
"with the reduced version!"));
54+
55+
// Parses IR into a Module and verifies it
56+
static std::unique_ptr<Module> parseInputFile(StringRef Filename,
57+
LLVMContext &Ctxt) {
58+
SMDiagnostic Err;
59+
std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
60+
if (!Result) {
61+
Err.print("llvm-reduce", errs());
62+
return Result;
63+
}
64+
65+
if (verifyModule(*Result, &errs())) {
66+
errs() << "Error: " << Filename << " - input module is broken!\n";
67+
return std::unique_ptr<Module>();
68+
}
69+
70+
return Result;
71+
}
72+
73+
/// Gets Current Working Directory and tries to create a Tmp Directory
74+
static SmallString<128> initializeTmpDirectory() {
75+
SmallString<128> CWD;
76+
if (std::error_code EC = sys::fs::current_path(CWD)) {
77+
errs() << "Error getting current directory: " << EC.message() << "!\n";
78+
exit(1);
79+
}
80+
81+
SmallString<128> TmpDirectory;
82+
sys::path::append(TmpDirectory, CWD, "tmp");
83+
if (std::error_code EC = sys::fs::create_directory(TmpDirectory))
84+
errs() << "Error creating tmp directory: " << EC.message() << "!\n";
85+
86+
return TmpDirectory;
87+
}
88+
89+
int main(int argc, char **argv) {
90+
InitLLVM X(argc, argv);
91+
92+
cl::ParseCommandLineOptions(argc, argv, "LLVM automatic testcase reducer.\n");
93+
94+
LLVMContext Context;
95+
std::unique_ptr<Module> OriginalProgram =
96+
parseInputFile(InputFilename, Context);
97+
98+
// Initialize test environment
99+
SmallString<128> TmpDirectory = initializeTmpDirectory();
100+
TestRunner Tester(TestFilename, TestArguments, InputFilename, TmpDirectory);
101+
Tester.setProgram(std::move(OriginalProgram));
102+
103+
// Try to reduce code
104+
runDeltaPasses(Tester);
105+
StringRef ReducedFilename = sys::path::filename(Tester.getReducedFilepath());
106+
107+
if (ReducedFilename == InputFilename) {
108+
outs() << "\nCouldnt reduce input :/\n";
109+
} else {
110+
if (ReplaceInput) // In-place
111+
OutputFilename = InputFilename.c_str();
112+
else if (OutputFilename.empty())
113+
OutputFilename = "reduced.ll";
114+
else
115+
OutputFilename += ".ll";
116+
117+
sys::fs::copy_file(Tester.getReducedFilepath(), OutputFilename);
118+
outs() << "\nDone reducing! Reduced IR to file: " << OutputFilename << "\n";
119+
}
120+
121+
return 0;
122+
}

0 commit comments

Comments
 (0)
Please sign in to comment.