Added Delta IR Reduction Tool

[diegotf]

Summary

This tool is part of the bugpoint redesign proposal, once finished it will be merged into bugpoint itself, although no specifics have been defined (i.e. could be integrated into the crash debugger or as a sub-tool).

The tool accepts 2 arguments: an interesting-ness test and an IR file to reduce. Once it parses and verifies the input file, it runs multiple Passes to minimize the IR which in turn call the Delta Debugging implementation (Note: an overview of this algorithm can be found in Delta.h).

Each pass must implement a helper function (extractChunksFromModule) which the Delta implementation will run on each iteration. For example, in the ReduceFunctions pass it will modify the module so it only contains chunk-functions, e.g. if the algorithm wants to test if the first 5 functions and the last 2 are interesting, this helper will modify the module so it only contains said functions.

You can also follow the projects progress through the llvm-dev mailing list (the most recent thread can be found here)

[diegotf]

Reduced Program is now saved after each delta pass instead of after each reduction (which caused some issues since chunks are structured based on Indexes).

Fixed bug where test arguments where being passed incorrectly to TestRunner.

Added more doxygen comments.

[diegotf]

Added Checks to remove-funcs.ll test & added inline option to output reduced IR to input file

[diegotf]

Added Checks to remove-funcs.ll to verify that uninteresting function calls are deleted as well

[diegotf]

Renamed inline option to in-place.

Moved IR file-writing to Generic Delta Pass, to simplify specialized passes

[diegotf]

Re-ran clang-format on project files

[chandlerc]

I'd suggest enhancing the main description to include an overview of the code structure and organization to help reviewers follow the implementation design here. Think of it like a mini design doc for the *implementation* itself.

llvm/test/Reduce/inputs/remove-funcs.sh

1 ↗

(On Diff #207098)

The directory is typically capitalized as Inputs in LLVM.

llvm/test/Reduce/remove-funcs.ll

6 ↗

(On Diff #207098)

You'll also want to say that this requires a shell. While the test itself doesn't it requires one on the system to run the "test" script.

llvm/tools/llvm-reduce/TestRunner.cpp

7–9 ↗

(On Diff #207098)

No need to repeat the function names.

But more importantly -- what kind of alternative? What's the difference?

llvm/tools/llvm-reduce/TestRunner.h

8–12 ↗

(On Diff #207098)

I'd move this to be a doxygen comment on the class. You can skip the file comment if its just one class.

33–34 ↗

(On Diff #207098)

What does the return value mean?

44 ↗

(On Diff #207098)

Typically best to pass std::unique_ptr by value.

47 ↗

(On Diff #207098)

Any particular reason to use SmallString instead of std::string?

[chandlerc]

(Also, really sorry, I mashed send button too soon, I'm still going through the code. Feel free to start on anything i posted, but sorry for the very random subset of comments)

[chandlerc]

Ok, now I've made a full pass through this. Mostly I think the first thing to do is tighten up the design around the core run function template and how reducers work with it. Documenting that design in detail will be really helpful I think.

llvm/tools/llvm-reduce/TestRunner.cpp

25–28 ↗

(On Diff #207098)

looks like some stale formatting...

llvm/tools/llvm-reduce/deltas/Chunk.h

18–31 ↗

(On Diff #207098)

I'm not sure this is really helped by being split out into its own file. I'd keep it maybe as a nested type inside the delta class?

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

124 ↗

(On Diff #207098)

This really needs more documentation to explain how it is intended to be used.

This would also be a good place to give readers background that they may need to read teh rest of the code. For example, they may not be familiar w/ the write ups of the delta debugging algorithm, so maybe give an overview here. Also will serve as a good place to capture anything that you end up changing from the standard one.

129 ↗

(On Diff #207098)

This is a class with a single static function.... Why is it a class? should it just be a function?

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

27–30 ↗

(On Diff #207098)

I feel like this could use a better name.

Maybe, extractChunksFromModule?

[dblaikie]

Did the broader design discussion about bugpoint lead to this design (a separate llvm-reduce tool)? I didn't quite follow that thread far enough to see the conclusion that lead to this direction (rather than improving/modifying bugpoint) - might be worth writing a bit more in the commit description about the conversation (link to the thread if that's helpful) and design choices - and long-term plan (to merge behavior, share things, remove one or the other - or should these two tools exist indefinitely with different goals/uses?)

llvm/tools/llvm-reduce/DeltaManager.h

21–22 ↗

(On Diff #207098)

Might as well make it a struct if all its members are public? Or a namespace (if it's meant as a grouping of stateless functions. Or no namespace at all and just a free (Possibly inline) function in the llvm namespace.

llvm/tools/llvm-reduce/TestRunner.cpp

19–23 ↗

(On Diff #207098)

There's probably some utility in LLVM to do this in a platform-independent way ('/' isn't the only path separator, etc)

25–26 ↗

(On Diff #207098)

these two std::strings shouldn't be passed by value if they aren't going to be moved into member std::strings - so either pass by const-ref (or more likely StringRef) or pass SmallStrings by value (or make the members std::strings, and move into them)

llvm/tools/llvm-reduce/deltas/Chunk.h

27–30 ↗

(On Diff #207098)

Is this comparison sufficient for std::set (strict weak ordering - specifically I'd be worried about !({1, 4} < {3, 6}) && !({3, 6} < {1, 4}) - so perhaps this comparison should have an assertion that the two ranges are non-overlapping?)

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

33 ↗

(On Diff #207098)

This seems like a fairly general function name to have in the llvm namespace in a header - yeah, all these functions look like they aren't part of the API here, but helper functions for the template below. So hiding them in some way would be nice. We don't have many cases of "impl"/"detail" namespaces in LLVM - maybe a trivial base class? (I'm not a huge fan of using classes to group functions, so this doesn't sound super satisfying to me - I'm open to ideas/suggestions)

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

23–24 ↗

(On Diff #207098)

Looks like another class used as a way to group utility functions

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

57 ↗

(On Diff #207098)

Probably should be 'static' (as well as other utility functions in this (& any other .cpp) files) if this isn't used outside this file?

83–85 ↗

(On Diff #207098)

Probably skip the {} on single line statements like this (that tends to be the common style in the LLVM codebase)

[diegotf]

Added in-depth description of Delta Algorithm, added shell requirement to test, and general code formatting.

[diegotf]

llvm/tools/llvm-reduce/TestRunner.cpp

7–9 ↗

(On Diff #207098)

True, I just grabbed that function directly from bugpoint, I hadn't noticed it's actually redundant

llvm/tools/llvm-reduce/TestRunner.h

47 ↗

(On Diff #207098)

Just trying to use ADT where possible (as per @lebedev.ri's suggestion), and since said variables are going to be Paths they will generally be under 128 chars.

llvm/tools/llvm-reduce/deltas/Chunk.h

27–30 ↗

(On Diff #207098)

I actually thought about that case but since I'm just using sets for lookup (and dont really care about the order) I left the comparison as is, would you still recommend I add the assertion?

[diegotf]

Moved bugpoint redesign proposal to llvm/docs folder.

Made runDeltaPasses an inline function in the llvm namespace and removed the DeltaManager class.

Moved Delta.h helper functions out of llvm-namespace

Filepath manipulation now use standarized sys::path methods (instead of appending strings directly)

[dblaikie]

llvm/tools/llvm-reduce/deltas/Chunk.h

27–30 ↗

(On Diff #207098)

The issue would be that if the ordering requirement is violated, it could break even a lookup - in the example I gave above, those two objects would be considered "equivalent", for instance.

If the Chunks are necessarily non-overlapping, perhaps it'd be simpler/accurate to only compare begin to begin (rather than begin to end)? (I'd do that and/or add the assertion)

[diegotf]

Fixed Chunk operator< overload

llvm/tools/llvm-reduce/DeltaManager.h

21–22 ↗

(On Diff #207098)

I think inline function is the way to go, it really doesn't make sense having it as a class when it's the only member

llvm/tools/llvm-reduce/TestRunner.h

33–34 ↗

(On Diff #207098)

I've added a comment to clarify that :)

llvm/tools/llvm-reduce/deltas/Chunk.h

27–30 ↗

(On Diff #207098)

That is a very keen observation, I'll change the comparison to begin-begin (since they can't overlap).

[diegotf]

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

33 ↗

(On Diff #207098)

Agreed, I will just move them out of the llvm namespace for the moment, since I'm still on the fence about this class' design

129 ↗

(On Diff #207098)

The main reason I chose this design was to streamline how Specialized Delta passes are implemented. So they only have to implement the getTargetCount and extractChunksFromModule methods. As well as make their invocations easier (Delta<SpecializedPass>::run(); vs SpecializedPass p; p.run();).

But I'm reconsidering it, since it's a bit too convoluted, and a simple switch statement can do the trick without jumping through so many "hoops".

I am welcome to suggestions

[diegotf]

In D63672#1565680, @dblaikie wrote:

Did the broader design discussion about bugpoint lead to this design (a separate llvm-reduce tool)? I didn't quite follow that thread far enough to see the conclusion that lead to this direction (rather than improving/modifying bugpoint) - might be worth writing a bit more in the commit description about the conversation (link to the thread if that's helpful) and design choices - and long-term plan (to merge behavior, share things, remove one or the other - or should these two tools exist indefinitely with different goals/uses?)

Thanks for the comment, I've clarified it in the description. As well as a brief description of how the tool is structured.

[dblaikie]

llvm/tools/llvm-reduce/TestRunner.cpp

7 ↗

(On Diff #207649)

I'd encourage naming the parameters (both in the ctor definition here, but also in the ctor declaration) the same as the members to avoid confusion. ("do these things represent the same concept? Are they massaged/modified in some way in the ctor implementation to get to the member values?)

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

57 ↗

(On Diff #207098)

Technically the LLVM style guide advocates for using "static" rather than anonymous namespaces (except for classes, where "static" isn't supported by the language): https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

[dblaikie]

In D63672#1567614, @diegotf wrote:

In D63672#1565680, @dblaikie wrote:

Did the broader design discussion about bugpoint lead to this design (a separate llvm-reduce tool)? I didn't quite follow that thread far enough to see the conclusion that lead to this direction (rather than improving/modifying bugpoint) - might be worth writing a bit more in the commit description about the conversation (link to the thread if that's helpful) and design choices - and long-term plan (to merge behavior, share things, remove one or the other - or should these two tools exist indefinitely with different goals/uses?)

Thanks for the comment, I've clarified it in the description. As well as a brief description of how the tool is structured.

The intent is to build this separately, then fold it into bugpoint? What's the tradeoff/motivation for that compared to building this into bugpoint to begin with? (seems like it presents a risk that that unification doesn't happen & we're left with a fractured solution ('one more competing standard' sort of situation)) Is the desire to get this reviewed/committed sooner while pursuing some bugpoint refactoring necessary before unification, without delaying implementation of this tool until after that refactoring?

[diegotf]

In D63672#1568616, @dblaikie wrote:

In D63672#1567614, @diegotf wrote:

In D63672#1565680, @dblaikie wrote:

Did the broader design discussion about bugpoint lead to this design (a separate llvm-reduce tool)? I didn't quite follow that thread far enough to see the conclusion that lead to this direction (rather than improving/modifying bugpoint) - might be worth writing a bit more in the commit description about the conversation (link to the thread if that's helpful) and design choices - and long-term plan (to merge behavior, share things, remove one or the other - or should these two tools exist indefinitely with different goals/uses?)

Thanks for the comment, I've clarified it in the description. As well as a brief description of how the tool is structured.

The intent is to build this separately, then fold it into bugpoint? What's the tradeoff/motivation for that compared to building this into bugpoint to begin with? (seems like it presents a risk that that unification doesn't happen & we're left with a fractured solution ('one more competing standard' sort of situation)) Is the desire to get this reviewed/committed sooner while pursuing some bugpoint refactoring necessary before unification, without delaying implementation of this tool until after that refactoring?

The main reason I chose this route was to not interfere with bugpoint's current users, especially because there's low test coverage, these changes might end up doing more harm than good. Additionally, some community members also voiced their concerns about how the redesign might affect their current workflow.

I also agree the risks you mentioned are very real indeed, and I'm not still 100% sure this might be the best approach so other routes might be worth exploring.

[diegotf]

llvm-reduce.cpp functions are now explicitly typed as static, as per LLVM Guidelines

Renamed TestRunner ctor parameters to match its respective members

[dblaikie]

In D63672#1568862, @diegotf wrote:

In D63672#1568616, @dblaikie wrote:

In D63672#1567614, @diegotf wrote:

In D63672#1565680, @dblaikie wrote:

Did the broader design discussion about bugpoint lead to this design (a separate llvm-reduce tool)? I didn't quite follow that thread far enough to see the conclusion that lead to this direction (rather than improving/modifying bugpoint) - might be worth writing a bit more in the commit description about the conversation (link to the thread if that's helpful) and design choices - and long-term plan (to merge behavior, share things, remove one or the other - or should these two tools exist indefinitely with different goals/uses?)

Thanks for the comment, I've clarified it in the description. As well as a brief description of how the tool is structured.

The intent is to build this separately, then fold it into bugpoint? What's the tradeoff/motivation for that compared to building this into bugpoint to begin with? (seems like it presents a risk that that unification doesn't happen & we're left with a fractured solution ('one more competing standard' sort of situation)) Is the desire to get this reviewed/committed sooner while pursuing some bugpoint refactoring necessary before unification, without delaying implementation of this tool until after that refactoring?

The main reason I chose this route was to not interfere with bugpoint's current users, especially because there's low test coverage, these changes might end up doing more harm than good. Additionally, some community members also voiced their concerns about how the redesign might affect their current workflow.

I also agree the risks you mentioned are very real indeed, and I'm not still 100% sure this might be the best approach so other routes might be worth exploring.

Fair enough - good to have it written down (perhaps in the commit message, probably also in a comment in the files, etc) - I personally would consider creating a whole separate tool with the intent that it later be removed a bit heavy, but I'm happy enough with it if @chandlerc is.

[diegotf]

Added disclaimer in main file that the tool is temporary.

Re-worded Delta class comment

[diegotf]

Re-added behavior to delete direct uses opf GVs (accidentally deleted)

[diegotf]

Removed accidental change from diff

[diegotf]

Cleanup from accidental change

[lebedev.ri]

Did the review finish here?

[gribozavr]

Sorry, this change broke the buildbots (http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/16018) and I reverted it in r368073.

[diegotf]

In D63672#1617487, @lebedev.ri wrote:

Did the review finish here?

Yes, and continued here D64176

In D63672#1617579, @gribozavr wrote:

Sorry, this change broke the buildbots (http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/16018) and I reverted it in r368073.

Thanks for the heads up and the revert.

[diegotf]

Added a more targeted test to fix broken buildbot & added bugfix from D64176

[hctim]

rL368112 Still broken on sanitizer-x86_64-linux-bootstrap-msan:

FAIL: LLVM :: Reduce/remove-funcs.ll (25362 of 32940)
******************** TEST 'LLVM :: Reduce/remove-funcs.ll' FAILED ********************
Script:
--
: 'RUN: at line 4';   llvm-reduce --test /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm/test/Reduce/Inputs/remove-funcs.sh /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm/test/Reduce/remove-funcs.ll
: 'RUN: at line 5';   cat reduced.ll | /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/bin/FileCheck /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm/test/Reduce/remove-funcs.ll
--
Exit Code: 127

Command Output (stderr):
--
/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/test/Reduce/Output/remove-funcs.ll.script: line 1: llvm-reduce: command not found

--

[nridge]

This change is breaking shared library builds with linker errors like:

llvm-reduce.cpp:function main: error: undefined reference to 'llvm::LLVMContext::LLVMContext()'

[phosek]

We see a different test failure:

******************** TEST 'LLVM :: Reduce/remove-funcs.ll' FAILED ********************
Script:
--
: 'RUN: at line 4';   llvm-reduce --test /b/s/w/ir/k/llvm-project/llvm/test/Reduce/Inputs/remove-funcs.sh /b/s/w/ir/k/llvm-project/llvm/test/Reduce/remove-funcs.ll
: 'RUN: at line 5';   cat reduced.ll | /b/s/w/ir/k/recipe_cleanup/clangzMsUXi/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Reduce/remove-funcs.ll
--
Exit Code: 1

Command Output (stdout):
--
Reducing functions...
----------------------------
Chunk Index Reference:
	1: uninteresting1
	2: interesting
	3: uninteresting2
	4: uninteresting3
----------------------------
Error: input file isnt interesting

--

[phosek]

Reverted in rL368122.

[dblaikie]

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

33 ↗

(On Diff #207098)

I'm still a bit concerned the != is inconsistent with op< (eg: there could be two items for which !(A < B) and !(B < A) (ie: the items are equivalent, as far as the < ordering is concerned) but A != B).

Is the inequality needed/does it need to be narrowly defined as it is? If so, I'd suggest a proper ordering of op<, then.

Maybe it's simple enough that you could define op< as "std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end)"

llvm/trunk/docs/BugpointRedesign.md

72 ↗

(On Diff #213678)

Which way are we talking about the test - is "failing" the test the same as reproducing the scenario the user is searching for? Or is "failing" the test failing to reproduce the intended scenario?

Either way I think this phrase might be a bit off - you want to discard those things that don't impact the pass/fail of the test (no matter which direction you think of the test as being). (as is mentioned on the next bullet point - maybe you could skip this first one? Not sure)

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

7 ↗

(On Diff #213678)

std::move(TestArgs) (& TmpDirectory) probably?

17–18 ↗

(On Diff #213678)

Could/should this be a range-based for loop over TestArgs?

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

39 ↗

(On Diff #213678)

std::move(F) probably?

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

63 ↗

(On Diff #213678)

I think there are some portable helper APIs for forming combined paths (rather than using string concatenation and hardcoded path separator you have here) - might want to use one of those? (fs::path/join/something like that)

106 ↗

(On Diff #213678)

Functions and classes outside any namespace are probably not ideal (too easy to collide with other things) - I guess these should go in the llvm namespace?

(& maybe these functions are long enough they could be out of line in a .cpp file?)

150 ↗

(On Diff #213678)

Would this be worth unit testing with a stub/mock that would demonstrate the delta reduction algorithm directly?

156 ↗

(On Diff #213678)

Would it be more appropriate for getTargetCount to return some handle to the actual entities, rather than only a count - that way extractChunksFromModule wouldn't need to rediscover them (& so it wouldn't have to make sure it computed the same number of targets, for instance - it'd be given the targets directly)

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

22 ↗

(On Diff #213678)

Given that this function doesn't mutate ChunksToKeep, perhaps it should pass by const ref?

27 ↗

(On Diff #213678)

DenseSet maybe?

73–83 ↗

(On Diff #213678)

Printing this out during a call that sounds non-mutable might not be an ideal design - perhaps there should be some other more explicit call to print the reference?

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

19–26 ↗

(On Diff #213678)

class used for function grouping - this has come up a few times, and I see it's used as a trait of sorts, which might be justified (though the previouse xamples of this were changed, right? So is this one more justified/different from the previous ones?)

Even if it's going to be a class used to group functions/describe a trait-of-sorts, it should probably be a struct rather than a class with all public members.

llvm/trunk/tools/llvm-reduce/llvm-reduce.cpp

100 ↗

(On Diff #213678)

Perhaps call 'initializeTmpDirectory' in the ctor call for Tester - rather than having a separate named local variable? (since it's only used in that one place & would be more efficient to move it into the TestRunner, etc)

[diegotf]

llvm/trunk/docs/BugpointRedesign.md

72 ↗

(On Diff #213678)

Yeah, I worded the bullet point poorly, and now that you mention it, the bullet doesn't seem to add anything; I'll just remove it

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

150 ↗

(On Diff #213678)

That is a very good idea actually, I'll add a test

156 ↗

(On Diff #213678)

The thing is, since extractChunksFromModule clones the original module each time, there's no way of comparing the targets from the original Module & the Cloned one (I know the compare function would work for Functions, but there's no alternative for other targets like Arguments or MDNodes)

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

19–26 ↗

(On Diff #213678)

This design is bit stale actually, I forgot to update this diff. Let me update it with the format used in the other passes

llvm/trunk/tools/llvm-reduce/llvm-reduce.cpp

100 ↗

(On Diff #213678)

Good idea!

[dblaikie]

Also, I'm not able to run these locally - because I think I'm not using the system shell. Do you know anytihng about how I tell lit not to use its own shell, but to use the system one so it'll run these tests? (I can remove the REQUIRES line from the test and they run OK I think - but would be best to reproduce it more accurately) & have you been able to reproduce the failures various folks were reporting when this was previously committed?

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

156 ↗

(On Diff #213678)

Ah, I see. So this assumes that removing targets is independent of other targets - if you remove N targets, then there will be M-N targets remaining, etc.

Fair enough then.

[diegotf]

In D63672#1619572, @dblaikie wrote:

Also, I'm not able to run these locally - because I think I'm not using the system shell. Do you know anytihng about how I tell lit not to use its own shell, but to use the system one so it'll run these tests? (I can remove the REQUIRES line from the test and they run OK I think - but would be best to reproduce it more accurately) &

That's weird, the test should work with lit's shell just fine. And as far as I know the workaround that you mentioned is the only solution I know.

have you been able to reproduce the failures various folks were reporting when this was previously committed?

Locally, no. So I'm going to add a bit more logging to see why it broke the buildbots

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

33 ↗

(On Diff #207098)

Yesterday I was debugging a problem caused precisely by this inconsistency.

I didn't know std::tie even existed, I'll change op< to your suggestion :)

[diegotf]

Updated Delta Debugging implementation, Chunk op< now uses std::tie

[dblaikie]

Hey Diego, generally patches should not be committed without explicit approval (once a patch is sent for review, it's assumed it needs some kind of completion/sign-off/approval before committing). This patch has now been submitted 3 times without approval being given, I think?

Also when recommitting a reverted patch, it's important to include information about how the reason for a revert has been addressed. Committing with no fix to the bug is not usually acceptable except in fairly narrow circumstances (where all other avenues to reproduce the failure have been exhausted - including asking other developers who reported the failure to help reproduce the issue (they might be able to give hints about particular architectures and other environmental issues, etc - and they can do so on their own timeline rather than being forced to dig the issue out because they sync'd up and hit your patch again)).

[diegotf]

In D63672#1619933, @dblaikie wrote:

Hey Diego, generally patches should not be committed without explicit approval (once a patch is sent for review, it's assumed it needs some kind of completion/sign-off/approval before committing). This patch has now been submitted 3 times without approval being given, I think?

Also when recommitting a reverted patch, it's important to include information about how the reason for a revert has been addressed. Committing with no fix to the bug is not usually acceptable except in fairly narrow circumstances (where all other avenues to reproduce the failure have been exhausted - including asking other developers who reported the failure to help reproduce the issue (they might be able to give hints about particular architectures and other environmental issues, etc - and they can do so on their own timeline rather than being forced to dig the issue out because they sync'd up and hit your patch again)).

I'm so sorry, I will be more thorough before committing Diffs; I will ask around to see if I can find the cause of the broken builds

[dblaikie]

In D63672#1619957, @diegotf wrote:

In D63672#1619933, @dblaikie wrote:

Hey Diego, generally patches should not be committed without explicit approval (once a patch is sent for review, it's assumed it needs some kind of completion/sign-off/approval before committing). This patch has now been submitted 3 times without approval being given, I think?

Also when recommitting a reverted patch, it's important to include information about how the reason for a revert has been addressed. Committing with no fix to the bug is not usually acceptable except in fairly narrow circumstances (where all other avenues to reproduce the failure have been exhausted - including asking other developers who reported the failure to help reproduce the issue (they might be able to give hints about particular architectures and other environmental issues, etc - and they can do so on their own timeline rather than being forced to dig the issue out because they sync'd up and hit your patch again)).

I'm so sorry, I will be more thorough before committing Diffs; I will ask around to see if I can find the cause of the broken builds

No worries (:

I'm /guessing/ it might have something to do with running the interestingness test script - I doubt there's anything else quite like that in-tree, so probably a fair few reasons it might not work, I'd guess?

[diegotf]

In D63672#1620056, @dblaikie wrote:

In D63672#1619957, @diegotf wrote:

In D63672#1619933, @dblaikie wrote:

Hey Diego, generally patches should not be committed without explicit approval (once a patch is sent for review, it's assumed it needs some kind of completion/sign-off/approval before committing). This patch has now been submitted 3 times without approval being given, I think?

Also when recommitting a reverted patch, it's important to include information about how the reason for a revert has been addressed. Committing with no fix to the bug is not usually acceptable except in fairly narrow circumstances (where all other avenues to reproduce the failure have been exhausted - including asking other developers who reported the failure to help reproduce the issue (they might be able to give hints about particular architectures and other environmental issues, etc - and they can do so on their own timeline rather than being forced to dig the issue out because they sync'd up and hit your patch again)).

I'm so sorry, I will be more thorough before committing Diffs; I will ask around to see if I can find the cause of the broken builds

No worries (:

I'm /guessing/ it might have something to do with running the interestingness test script - I doubt there's anything else quite like that in-tree, so probably a fair few reasons it might not work, I'd guess?

Yeah I've been asking around and the issue seems to be that I'm using bash extensions on it ([[).

And to avoid all the shell hassle I'm just going to move the interesting-ness test over to python

[phosek]

In D63672#1620056, @dblaikie wrote:

In D63672#1619957, @diegotf wrote:

In D63672#1619933, @dblaikie wrote:

Hey Diego, generally patches should not be committed without explicit approval (once a patch is sent for review, it's assumed it needs some kind of completion/sign-off/approval before committing). This patch has now been submitted 3 times without approval being given, I think?

Also when recommitting a reverted patch, it's important to include information about how the reason for a revert has been addressed. Committing with no fix to the bug is not usually acceptable except in fairly narrow circumstances (where all other avenues to reproduce the failure have been exhausted - including asking other developers who reported the failure to help reproduce the issue (they might be able to give hints about particular architectures and other environmental issues, etc - and they can do so on their own timeline rather than being forced to dig the issue out because they sync'd up and hit your patch again)).

I'm so sorry, I will be more thorough before committing Diffs; I will ask around to see if I can find the cause of the broken builds

No worries (:

I'm /guessing/ it might have something to do with running the interestingness test script - I doubt there's anything else quite like that in-tree, so probably a fair few reasons it might not work, I'd guess?

I spoke with @diegotf offline but I'll leave it here for completeness: one thing I noticed while looking at the remove-funcs.sh script is that it uses #!/bin/sh. On some systems like Ubuntu that would mean bash but on other systems that might be different, e.g. on our bots we use Debian and /bin/sh is dash. The script uses bash extensions like [[ so it's going to fail with other shells. So either it needs to explicitly request bash by using /usr/bin/env bash or we need to make sure that the script doesn't use any bash extensions.

[diegotf]

Moved interesting-ness test to python & changed createTmpFile so it uses sys::path::append instead of hardcoded separators (/)

[lebedev.ri]

llvm/test/BP2/remove-funcs-test.sh

1 ↗

(On Diff #206108)

I'll be more specific - you can not use shell at all, regardless of whether it's bash/sh/zsh/...
It should be python-based.

llvm/test/Reduce/remove-funcs.ll

4 ↗

(On Diff #214032)

I think i'm failing to see the purpose of that script.
Why is it needed? FileCheck will fail just as good if it doesn't match.

[diegotf]

llvm/test/BP2/remove-funcs-test.sh

1 ↗

(On Diff #206108)

Thanks for the clarification! I think it might be worthwhile writing that down somewhere (for future reference)

llvm/test/Reduce/remove-funcs.ll

4 ↗

(On Diff #214032)

It is used internally by the tool in order to reduce IR. And to clarify that I moved the script into an Inputs folder.

[diegotf]

Formatting changes & added llvm-reduce as test dependency

[dblaikie]

llvm/tools/llvm-reduce/TestRunner.cpp

46–47 ↗

(On Diff #214201)

Do you need to initialize these elements? I suspect just this:

Optional<StringRef> Redirects[3];

should suffice (since they're "Optional" - it'd be weird to have to make them "non-None but empty strings").

llvm/tools/llvm-reduce/deltas/Delta.cpp

168–169 ↗

(On Diff #214201)

Looks like an unnecessary initialization? Coeuld be written as:

auto UnwantedChunks = std::remove_if....

Though some people would actually wrap up erase and remove together:

Chunks.erase(llvm::remove_if(Chunks, [&](const Chunk &C) {
  return UninterestingChunks.count(C);
}, Chunks.end());

Oh, there we go, we have an llvm::erase_if:

erase_if(Chunks, [&](const Chunk &C) {
  ...
});

Nice & easy :)

[diegotf]

Remove unnecessary initialization & refactored erasure of uninteresting chunks in Delta.cpp

llvm/tools/llvm-reduce/TestRunner.cpp

46–47 ↗

(On Diff #214201)

Yeah I'm actually not sure why I initialized them 🤔

llvm/tools/llvm-reduce/deltas/Delta.cpp

168–169 ↗

(On Diff #214201)

Wow, love the solution. I didn't know llvm::erase_if existed, I really need to read up more on some parts of the LLVM API.

Thanks for the cleaner solution!

[dblaikie]

Looks plausible enough to try committing this again & see if it sticks, thanks!

[sbc100]

I think they may have broken the -DBUILD_SHARED_LIBS=ON build: Proposed fix: https://reviews.llvm.org/D65982

[JDevlieghere]

This also broke the documentation bot: http://lab.llvm.org:8011/builders/llvm-sphinx-docs

[diegotf]

In D63672#1623225, @JDevlieghere wrote:

This also broke the documentation bot: http://lab.llvm.org:8011/builders/llvm-sphinx-docs

Fix here: D66022

[mgorny]

This broke NetBSD buildbots:
http://lab.llvm.org:8011/builders/netbsd-amd64/builds/22010/steps/run%20unit%20tests/logs/FAIL%3A%20LLVM%3A%3Aremove-funcs.ll
http://lab.llvm.org:8011/builders/netbsd-amd64/builds/22010/steps/run%20unit%20tests/logs/FAIL%3A%20LLVM%3A%3Aremove-global-vars.ll

llvm/trunk/test/Reduce/Inputs/remove-funcs.py

1 ↗

(On Diff #214246)

This is broken on systems with non-standard Python executable name. You ought to use lit's %python substitution to invoke Python. However, I don't really know how to combine that with llvm-reduce.

[mgorny]

Ok, I have an idea of using --test-arg but it would require the args to be passed before the filename. I'll post a patch.

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

44 ↗

(On Diff #214246)

Wouldn't it be better to pass arguments *before* the filename?

[mgorny]

In D63672#1657183, @mgorny wrote:

Ok, I have an idea of using --test-arg but it would require the args to be passed before the filename. I'll post a patch.

Actually, I won't because I'm hitting some memory corruption in TestArgs and I don't really have time or motivation to fight it. Please fix your code.

[dblaikie]

In D63672#1657198, @mgorny wrote:

In D63672#1657183, @mgorny wrote:

Ok, I have an idea of using --test-arg but it would require the args to be passed before the filename. I'll post a patch.

Actually, I won't because I'm hitting some memory corruption in TestArgs and I don't really have time or motivation to fight it. Please fix your code.

Could you be more specific? I've tried running both tests under valgrind and haven't encountered any reported errors there.

[dblaikie]

llvm/trunk/test/Reduce/Inputs/remove-funcs.py

1 ↗

(On Diff #214246)

I've provided what I believe to be a fix for this in r371143

[mgorny]

In D63672#1659973, @dblaikie wrote:

In D63672#1657198, @mgorny wrote:

In D63672#1657183, @mgorny wrote:

Ok, I have an idea of using --test-arg but it would require the args to be passed before the filename. I'll post a patch.

Actually, I won't because I'm hitting some memory corruption in TestArgs and I don't really have time or motivation to fight it. Please fix your code.

Could you be more specific? I've tried running both tests under valgrind and haven't encountered any reported errors there.

In my case, passing --test-arg to the program caused TestArgs inside TestRunner to contain junk before the actual parameter strings.

llvm/trunk/test/Reduce/Inputs/remove-funcs.py

1 ↗

(On Diff #214246)

Heh, that's a hack I wouldn't think of. Thanks.

[dblaikie]

In D63672#1660282, @mgorny wrote:

In D63672#1659973, @dblaikie wrote:

In D63672#1657198, @mgorny wrote:

In D63672#1657183, @mgorny wrote:

Ok, I have an idea of using --test-arg but it would require the args to be passed before the filename. I'll post a patch.

Actually, I won't because I'm hitting some memory corruption in TestArgs and I don't really have time or motivation to fight it. Please fix your code.

Could you be more specific? I've tried running both tests under valgrind and haven't encountered any reported errors there.

In my case, passing --test-arg to the program caused TestArgs inside TestRunner to contain junk before the actual parameter strings.

Ah - so was this not while running one of the existing tests, but running some other commands? Could you provide reproduction steps, then? (exactly what inputs, commands, etc)

llvm/tools/LLVMBuild.txt

 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [common]
 subdirectories =
  bugpoint
+ bp2
  dsymutil
  llc
  lli
  llvm-ar
  llvm-as
  llvm-bcanalyzer
  llvm-cat
  llvm-cfi-verify

llvm/tools/bp2/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmParsers
+  AllTargetsCodeGens
+  AllTargetsDescs
+  AllTargetsInfos
+  Analysis
+  BitWriter
+  CodeGen
+  Core
+  IPO
+  IRReader
+  AggressiveInstCombine
+  InstCombine
+  Instrumentation
+  Linker
+  ObjCARCOpts
+  ScalarOpts
+  Support
+  Target
+  TransformUtils
+  Vectorize
+  )
+
+# Support plugins.
+set(LLVM_NO_DEAD_STRIP 1)
+
+add_llvm_tool(bp2
+  bp2.cpp
+  TestRunner.cpp
+  DeltaManager.cpp
+  deltas/RemoveFunctions.cpp
+
+  DEPENDS
+  intrinsics_gen
+  )
+export_executable_symbols(bp2)

llvm/tools/bp2/DeltaManager.h

+#include "deltas/RemoveFunctions.h"
+#include "deltas/Delta.h"
+#include "TestRunner.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+
+
+namespace llvm {
+
+class DeltaManager {
+  public:
+    DeltaManager(Module* P, TestRunner T);
+    void runDeltaPasses();
+  
+  private:
+    Module* Program;
+    TestRunner Tester;
+};
+
+}
 No newline at end of file

llvm/tools/bp2/DeltaManager.cpp

+#include "DeltaManager.h"
+
+using namespace llvm;
+
+DeltaManager::DeltaManager(Module* P, TestRunner T)
+    : Program(P), Tester(T) {}
+
+void DeltaManager::runDeltaPasses() {
+  outs() << "Reducing functions...\n";
+  Delta<RemoveFunctions>::run(Program, Tester);
+  // TODO: Implement the remaining deltas..
+}

llvm/tools/bp2/LLVMBuild.txt

-;===- ./tools/LLVMBuild.txt ------------------------------------*- Conf -*--===;
+;===- ./tools/bugpoint/LLVMBuild.txt ---------------------------*- Conf -*--===;
 ;
 ; 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 is an LLVMBuild description file for the components in this subdirectory.
 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
-[common]
-subdirectories =
- bugpoint
- dsymutil
- llc
- lli
- llvm-ar
- llvm-as
- llvm-bcanalyzer
- llvm-cat
- llvm-cfi-verify
- llvm-cov
- llvm-cvtres
- llvm-diff
- llvm-dis
- llvm-dwarfdump
- llvm-dwp
- llvm-elfabi
- llvm-exegesis
- llvm-extract
- llvm-jitlistener
- llvm-jitlink
- llvm-link
- llvm-lto
- llvm-mc
- llvm-mca
- llvm-modextract
- llvm-mt
- llvm-nm
- llvm-objcopy
- llvm-objdump
- llvm-pdbutil
- llvm-profdata
- llvm-rc
- llvm-rtdyld
- llvm-size
- llvm-split
- llvm-undname
- opt
- verify-uselistorder
-
 [component_0]
-type = Group
-name = Tools
-parent = $ROOT
+type = Tool
+name = bp2
+parent = Tools
+required_libraries =
+ AsmParser
+ BitReader
+ BitWriter
+ CodeGen
+ IRReader
+ IPO
+ Instrumentation
+ Linker
+ ObjCARC
+ Scalar
+ all-targets

llvm/tools/bp2/TestRunner.h

+#ifndef LLVM_TOOLS_BP2_TESTRUNNER_H
+#define LLVM_TOOLS_BP2_TESTRUNNER_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Error.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Program.h"
+
+namespace llvm {
+
+class TestRunner {
+  public:
+    TestRunner(std::string OriginalF, std::string TestN, 
+               std::vector<std::string> TArgs);
+    // Runs the interestingness test for the given filename
+    // @returns 1 if the Filename is interesting, 0 if otherwise.
+    int run(std::string Filename);
+    std::string getOriginalFilename() { return OriginalFilename; }
+
+  private:
+    std::string OriginalFilename;
+    std::string TestName;
+    std::vector<std::string> TestArgs;
+};
+
+}
+
+#endif
 No newline at end of file

llvm/tools/bp2/TestRunner.cpp

+#include "TestRunner.h"
+
+using namespace llvm;
+
+/// RunProgramWithTimeout - This function provides an alternate interface
+/// to the sys::Program::ExecuteAndWait interface.
+/// @see sys::Program::ExecuteAndWait
+int runProgramWithTimeout(StringRef ProgramPath, ArrayRef<StringRef> Args,
+                          unsigned NumSeconds = 0, unsigned MemoryLimit = 0,
+                          std::string *ErrMsg = nullptr) {
+  StringRef SR = "";
+  Optional<StringRef> Redirects[3] = {SR, SR, SR};
+  return sys::ExecuteAndWait(ProgramPath, Args, None, Redirects, NumSeconds,
+                             MemoryLimit, ErrMsg);
+}
+
+TestRunner::TestRunner(std::string OriginalF, std::string TestN, 
+                           std::vector<std::string> TArgs)
+    : OriginalFilename(OriginalF), TestName(TestN), TestArgs(TArgs) {}
+
+
+int TestRunner::run(std::string Filename) {
+  std::vector<StringRef> ProgramArgs;
+  ProgramArgs.push_back(TestName.c_str());
+  ProgramArgs.push_back(Filename.c_str());
+
+  for (auto Arg : TestArgs)
+    ProgramArgs.push_back(Arg.c_str());
+
+  int Result = runProgramWithTimeout(TestName, ProgramArgs);
+
+  if (Result < 0) {
+    Error E = make_error<StringError>("Error running interesting-ness test\n",
+                                   inconvertibleErrorCode());
+    outs() << toString(std::move(E));
+    exit(1);
+  }
+
+  return !Result;
+}
 No newline at end of file

llvm/tools/bp2/bp2.cpp

+//===- 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 "DeltaManager.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/SourceMgr.h"
+#include <vector>
+
+using namespace llvm;
+
+static cl::opt<std::string> InputFilename(cl::Positional, cl::Required,
+                                          cl::desc("<input llvm ll/bc file>"));
+
+static cl::opt<std::string>
+    TestName("test", cl::Required,
+                   cl::desc("Name of the interesting-ness test to be run"));
+
+static cl::list<std::string>
+    TestArguments("test-arg", cl::ZeroOrMore,
+                   cl::desc("Arguments passed onto the interesting-ness test"));
+
+// Parses IR into a Module and verifies it
+std::unique_ptr<Module> parseInputFile(StringRef Filename, LLVMContext &Ctxt) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
+  if (!Result) {
+    Err.print("bp2", errs());
+    return Result;
+  }
+
+  if (verifyModule(*Result, &errs())) {
+    errs() << "bp2: " << Filename << ": error: input module is broken!\n";
+    return std::unique_ptr<Module>();
+  }
+
+  return Result;
+}
+
+int main(int argc, char **argv) {
+  InitLLVM X(argc, argv);
+
+  cl::ParseCommandLineOptions(argc, argv,
+                              "LLVM automatic testcase reducer. See\nhttp://"
+                              "llvm.org/cmds/bugpoint.html"
+                              " for more information.\n");
+
+  LLVMContext Context;
+  std::unique_ptr<Module> P = parseInputFile(InputFilename, Context);
+
+  std::vector<std::string> TestArgs(std::move(TestArguments));
+  TestRunner Tester(InputFilename, TestName, TestArgs);
+
+  DeltaManager DeltaMgr(P.get(), Tester);
+  DeltaMgr.runDeltaPasses();
+  
+  return 0;
+}

llvm/tools/bp2/bugpoint.md

+# Bugpoint Redesign
+Author: Diego Treviño ([e-mail])
+
+Date: 2016-06-05
+
+Status: Draft
+
+
+## Introduction
+As use of bugpoint has grown several areas of improvement have been identified through years of use: confusing to use, slow, it doesn’t always produce high quality test cases, etc. This document proposes a new approach with a narrower focus: minimization of IR test cases.
+
+
+## Proposed New Design
+
+
+### Narrow focus: test-case reduction
+The main focus will be a code reduction strategy to obtain much smaller test cases that still have the same property as the original one. This will be done via classic delta debugging and by adding some IR-specific reductions (e.g. replacing globals, removing unused instructions, etc), similar to what already exists, but with more in-depth minimization.
+
+
+Granted, if the community differs on this proposal, the legacy code could still be present in the tool, but with the caveat of still being documented and designed towards delta reduction.
+
+
+### Command-Line Options
+We are proposing to reduce the plethora of bugpoint’s options to just two: an interesting-ness test and the arguments for said test, similar to other delta reduction tools such as CReduce, Delta, and Lithium; the tool should feel less cluttered, and there should also be no uncertainty about how to operate it.
+
+
+The interesting-ness test that’s going to be run to reduce the code is given by name:
+        `--test=<test_name>`
+If a `--test`  option is not given, the program exits; this option is similar to bugpoint’s current `-compile-custom` option, which lets the user run a custom script.
+
+
+The interesting-ness test would be defined as a script that returns 0 when the IR achieves a user-defined behaviour (e.g. failure to compile on clang) and a nonzero value when otherwise. Leaving the user the freedom to determine what is and isn’t interesting to the tool, and thus, streamlining the process of reducing a test-case.
+
+
+If the test accepts any arguments (excluding the input ll/bc file), they are given via the following flag:
+        `--test_args=<test_arguments>`
+If unspecified, the test is run as given. It’s worth noting that the input file would be passed as a parameter to the test, similar how `-compile-custom` currently operates.
+
+
+### Implementation
+The tool would behave similar to CReduce’s functionality in that it would have a list of passes that try to minimize the given test-case. We should be able to modularize the tool’s behavior, as well as making it easier to maintain and expand. 
+
+
+The first version of this redesign would try to:
+
+
+* Split the code into chunks and discard those that fail the given test
+* Discard functions, instructions and metadata that don’t influence the interesting-ness test
+* Remove unused parameters from functions
+* Eliminate unvisited conditional paths
+* Rename variables to more regular ones (such as “a”, “b”, “c”, etc.)
+
+
+Once these passes are implemented, more meaningful reductions (such as type reduction) would be added to the tool, to even further reduce IR.
+
+
+## Background on historical bugpoint issues
+
+
+### Root Cause Analysis
+Presently, bugpoint takes a long time to find the source problem in a given IR file, mainly due to the fact that it tries to debug the input by running various strategies to classify the bug, which in turn run multiple optimizer and compilation passes over the input, taking up a lot of time. Furthermore, when the IR crashes, it tries to reduce it by performing some sub-optimal passes (e.g. a lot of unreachable blocks), and sometimes even fails to minimize at all.
+
+
+### "Quirky" Interface
+Bugpoint’s current interface overwhelms and confuses the user, the help screen alone ends up confusing rather providing guidance, as seen below:
+
+![Bugpoint's help option showcase](https://lh6.googleusercontent.com/sbpaSVHzpVVZKKAgHL9gvfzTWdgh3ju0KiDYql6WmWZfDYrdauOJMcuo9PP_V1dq8JQfMHOSKTv3lJcSpVytUyU8r5tJ2KTlGB0b2ve7jsZ3nVX8K8ItAbsA0JWkFKw67VJnq99m)
+
+And, not only are there numerous features and options, but some of them also work in unexpected ways and most of the time the user ends up using a custom script. Pruning and simplifying the interface will be worth considering in order to make the tool more useful in the general case and easier to maintain.
+
+
+

llvm/tools/bp2/deltas/Chunk.h

+#ifndef LLVM_TOOLS_BP2_DELTAS_CHUNK_H
+#define LLVM_TOOLS_BP2_DELTAS_CHUNK_H
+
+struct Chunk {
+  int begin;
+  int end;
+
+  friend bool operator!=(const Chunk &C1, const Chunk &C2) {
+    return C1.begin != C2.begin && C1.end != C2.end;
+  }
+  friend bool operator<(const Chunk& C1, const Chunk &C2) {
+    return C1.end < C2.begin;
+  }
+};
+
+#endif
 No newline at end of file

llvm/tools/bp2/deltas/Delta.h

+#include "Chunk.h"
+#include "TestRunner.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/IR/Module.h"
+#include <fstream>
+#include <string>
+#include <vector>
+#include <set>
+
+namespace llvm {
+
+inline void printChunks(std::vector<Chunk> Chunks, bool Oneline = false) {
+  for(auto C : Chunks) {
+    if (!Oneline) outs() << '\t';
+    outs() << "[" << C.begin;
+    if (C.end - C.begin != 0)
+      outs() << "," << C.end;
+    outs() << "]";
+    if (!Oneline) outs() << '\n';
+  }
+}
+
+// Counts the amount of lines for a given file
+inline unsigned getLines(std::string Filename) {
+  unsigned Lines = 0;
+  std::string CurrLine;
+  std::ifstream FileStream(Filename);
+
+  while (std::getline(FileStream, CurrLine))
+    ++Lines;
+
+  return Lines;
+}
+
+inline bool increaseGranularity(std::vector<Chunk> &Chunks) {
+  outs() << "Increasing granularity...\n";
+  std::vector<Chunk> NewChunks;
+  bool SplitOne = false;
+
+  for(auto C : Chunks) {
+    int Half = (C.begin + C.end) / 2;
+    if (C.end - C.begin == 0)
+      NewChunks.push_back(C);
+    else {
+      NewChunks.push_back({ C.begin, Half });
+      NewChunks.push_back({ Half + 1, C.end });
+      SplitOne = true;
+    }
+  }
+  if (SplitOne) {
+    Chunks = NewChunks;
+    outs() << "Success! New Chunks:\n";
+    printChunks(Chunks);
+  }
+  return SplitOne;
+}
+
+template<class D> class Delta {
+  public:
+    // Default Delta Debugging Algorithm
+    static void run(Module* Program, TestRunner Test) {
+      int TargetCount = D::getTargetCount(Program);
+      std::vector<Chunk> Chunks = {{ 1, TargetCount }};
+      std::vector<Chunk> CurrentChunks;
+      std::set<Chunk> UninterestingChunks;
+
+      std::string SmallestFilename = Test.getOriginalFilename();
+      // Maybe also save the smallest Module?
+
+      // TODO: Run initial pass to verify input is interesting
+      increaseGranularity(Chunks);
+
+      do {
+        UninterestingChunks = {};
+        for (int I = Chunks.size() - 1; I >= 0; --I) {
+          CurrentChunks = {};
+
+          for(auto C : Chunks)
+            if (!UninterestingChunks.count(C) && C != Chunks[I])
+              CurrentChunks.push_back(C);
+
+          outs() << "Testing with: ";
+          printChunks(CurrentChunks, /*Oneline*/ true);
+
+          std::string CurrentFilename = D::prepareIR(Program, CurrentChunks);
+          outs() << " | " << CurrentFilename;
+
+          if (Test.run(CurrentFilename) && 
+              getLines(CurrentFilename) < getLines(SmallestFilename)) {
+            SmallestFilename = CurrentFilename;
+            outs() << " **** SUCCESS | lines: " << getLines(SmallestFilename);
+          }
+          outs() << "\n";
+        }
+        // Delete proven Uninteresting chunks 
+        auto It = Chunks.begin(), E = Chunks.end();
+        while(It != E) {
+          if (UninterestingChunks.count(*It))
+            It = Chunks.erase(It);
+          else
+            ++It;
+        }
+      } while(!UninterestingChunks.empty() || increaseGranularity(Chunks));
+      outs() << "Couldn't increase granularity anymore.\n";
+    }
+};
+
+}

llvm/tools/bp2/deltas/RemoveFunctions.h

+#include "Chunk.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/FunctionComparator.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <memory>
+#include <vector>
+#include <set>
+
+namespace llvm {
+
+class RemoveFunctions {
+  public:
+    static int getTargetCount(Module* Program);
+    static std::string prepareIR(Module* Program, std::vector<Chunk> Chunks);
+};
+
+}
 No newline at end of file

llvm/tools/bp2/deltas/RemoveFunctions.cpp

+#include "RemoveFunctions.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Use.h"
+#include "llvm/Support/Casting.h"
+#include <set>
+#include <vector>
+
+using namespace llvm;
+
+bool writeProgramToFile(const std::string &Filename, int FD,
+                                   const Module &M) {
+  ToolOutputFile Out(Filename, FD);
+  WriteBitcodeToFile(M, Out.os());
+  Out.os().close();
+
+  if (!Out.os().has_error()) {
+    Out.keep();
+    return false;
+  }
+  return true;
+}
+
+// Clones original program, and deletes Functions that aren't in desired chunks
+std::string RemoveFunctions::prepareIR(Module *Program,
+                                       std::vector<Chunk> ChunksToKeep) {
+  std::string NewBitcode;
+  std::unique_ptr<Module> Clone = CloneModule(*Program);
+  std::set<Function*> ToKeep;
+
+  // Get all functions inside desired chunks 
+  int I = 0, FunctionCount = 1;
+  for(auto &F : *Clone) {
+    if (!F.isDeclaration()) {
+      if (FunctionCount >= ChunksToKeep[I].begin &&
+          FunctionCount <= ChunksToKeep[I].end) {
+        ToKeep.insert(&F);
+      }
+      else if (FunctionCount > ChunksToKeep[I].end)
+        ++I;
+    ++FunctionCount;
+    }
+  }
+
+  std::vector<Function*> ToRemove;
+
+  // Delete out-of-chunk functions, and replace their calls with null
+  for (Function &F : *Clone) {
+    if (!F.isDeclaration() && !ToKeep.count(&F)) {
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      ToRemove.push_back(&F);
+    }
+  }
+
+  for (auto *F : ToRemove) {
+    F->eraseFromParent();
+  }
+
+   std::vector<Instruction*> ToRemoveI;
+
+  // Clean up null calls
+  for(auto &F : *Clone)
+    for(auto &BB : F)
+      for(auto &I : BB)
+        if (CallInst *callInst = dyn_cast<CallInst>(&I))
+          if (!callInst->getCalledFunction()) {
+            I.replaceAllUsesWith(UndefValue::get(I.getType()));
+            ToRemoveI.push_back(&I);
+          }
+
+  for (auto *I : ToRemoveI) {
+    I->eraseFromParent();
+  }
+
+
+  // Write new module to file
+  SmallString<128> UniqueFilename;
+  int UniqueFD;
+  std::error_code EC = sys::fs::createUniqueFile("tmp-%%%.bc", UniqueFD, 
+                                                 UniqueFilename);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "!\n";
+    exit(1);
+  }
+  NewBitcode = UniqueFilename.str();
+
+  if (writeProgramToFile(NewBitcode, UniqueFD, *Clone)) {
+    errs() << "Error emitting bitcode to file '" << NewBitcode
+            << "'!\n";
+    exit(1);
+  }
+
+  return NewBitcode;
+}
+
+int RemoveFunctions::getTargetCount(Module* M) {
+  outs() << "----------------------------\n";
+  outs() << "Chunk Index Reference:\n";
+  int FunctionCount = 0;
+  for (auto &F : *M)
+    if (!F.isDeclaration()) {
+      ++FunctionCount;
+      outs() << "\t" << FunctionCount << ": " << F.getName() << "\n";
+    }
+  outs() << "----------------------------\n";
+  return FunctionCount;
+}
 No newline at end of file