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

7

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

8–10

No need to repeat the function names.

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

llvm/tools/llvm-reduce/TestRunner.h

9–13

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

34–35

What does the return value mean?

45

Typically best to pass std::unique_ptr by value.

48

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

26–29

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

125

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.

130

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

22–23

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

20–24

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

26–27

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

34

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

58

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

84–86

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

8–10

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

llvm/tools/llvm-reduce/TestRunner.h

48

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

22–23

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

34–35

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

34

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

130

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

8

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

58

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

34

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

34

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

5

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

5

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

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

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

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

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

168–169

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/docs/BugpointRedesign.md

+# Bugpoint Redesign
+Author: Diego Treviño ([e-mail])
+
+Date: 2019-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:
+
+
+* 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/test/CMakeLists.txt

set(LLVM_TEST_DEPENDS
           llvm-opt-fuzzer
           llvm-opt-report
           llvm-pdbutil
           llvm-profdata
           llvm-ranlib
           llvm-rc
           llvm-readobj
           llvm-readelf
+          llvm-reduce
           llvm-rtdyld
           llvm-size
           llvm-split
           llvm-strings
           llvm-strip
           llvm-symbolizer
           llvm-tblgen
           llvm-undname

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

+#!/usr/bin/env python
+
+import sys
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "@interesting" in line:
+    sys.exit(0)
+
+sys.exit(1) # IR isn't interesting

llvm/test/Reduce/remove-funcs.ll

+; Test that llvm-reduce can remove uninteresting functions as well as
+; their InstCalls.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-funcs.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins, shell
+
+; CHECK-NOT: uninteresting1()
+define i32 @uninteresting1() {
+entry:
+  ret i32 0
+}
+
+; CHECK: interesting()
+define i32 @interesting() {
+entry:
+  ; CHECK: call i32 @interesting()
+  %call2 = call i32 @interesting()
+  ; CHECK-NOT: call i32 @uninteresting1()
+  %call = call i32 @uninteresting1()
+  ret i32 5
+}
+
+; CHECK-NOT: uninteresting2()
+define i32 @uninteresting2() {
+entry:
+  ret i32 0
+}
+
+; CHECK-NOT: uninteresting3()
+define i32 @uninteresting3() {
+entry:
+  ret i32 10
+}

llvm/tools/LLVMBuild.txt

  llvm-modextract
  llvm-mt
  llvm-nm
  llvm-objcopy
  llvm-objdump
  llvm-pdbutil
  llvm-profdata
  llvm-rc
+ llvm-reduce
  llvm-rtdyld
  llvm-size
  llvm-split
  llvm-undname
  opt
  verify-uselistorder
 
 [component_0]
 type = Group
 name = Tools
 parent = $ROOT

llvm/tools/llvm-reduce/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmParsers
+  AllTargetsCodeGens
+  AllTargetsDescs
+  AllTargetsInfos
+  IRReader
+  Support
+  Target
+  TransformUtils
+  )
+
+# Support plugins.
+set(LLVM_NO_DEAD_STRIP 1)
+
+add_llvm_tool(llvm-reduce
+  llvm-reduce.cpp
+  TestRunner.cpp
+  deltas/Delta.cpp
+  deltas/ReduceFunctions.cpp
+
+  DEPENDS
+  intrinsics_gen
+  )
+export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

+//===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===//
+//
+// 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 calls each specialized Delta pass in order to reduce the input IR
+// file.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+#include "deltas/Delta.h"
+#include "deltas/ReduceFunctions.h"
+
+namespace llvm {
+
+inline void runDeltaPasses(TestRunner &Tester) {
+  reduceFunctionsDeltaPass(Tester);
+  // TODO: Implement the remaining Delta Passes
+}
+
+} // namespace llvm

llvm/tools/llvm-reduce/LLVMBuild.txt

-;===- ./tools/LLVMBuild.txt ------------------------------------*- Conf -*--===;
+;===- ./tools/llvm-reduce/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 = llvm-reduce
+parent = Tools
+required_libraries =
+ BitReader
+ IRReader
+ all-targets

llvm/tools/llvm-reduce/TestRunner.h

+//===-- tools/llvm-reduce/TestRunner.h ---------------------------*- C++ -*-===/
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
+#define LLVM_TOOLS_LLVMREDUCE_TESTRUNNER_H
+
+#include "llvm/ADT/SmallString.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Program.h"
+#include <vector>
+
+namespace llvm {
+
+// This class contains all the info necessary for running the provided
+// interesting-ness test, as well as the most reduced module and its
+// respective filename.
+class TestRunner {
+public:
+  TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
+             StringRef ReducedFilepath);
+
+  /// Runs the interesting-ness test for the specified file
+  /// @returns 0 if test was successful, 1 if otherwise
+  int run(StringRef Filename);
+
+  /// Filename to the most reduced testcase
+  StringRef getReducedFilepath() const { return ReducedFilepath; }
+  /// Directory where tmp files are created
+  StringRef getTmpDir() const { return TmpDirectory; }
+  /// Returns the most reduced version of the original testcase
+  Module *getProgram() const { return Program.get(); }
+
+  void setReducedFilepath(SmallString<128> F) {
+    ReducedFilepath = std::move(F);
+  }
+  void setProgram(std::unique_ptr<Module> P) { Program = std::move(P); }
+
+private:
+  SmallString<128> TestName;
+  std::vector<std::string> TestArgs;
+  SmallString<128> ReducedFilepath;
+  SmallString<128> TmpDirectory;
+  std::unique_ptr<Module> Program;
+};
+
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/TestRunner.cpp

+//===-- TestRunner.cpp ----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+
+using namespace llvm;
+
+/// Gets Current Working Directory and tries to create a Tmp Directory
+static SmallString<128> initializeTmpDirectory() {
+  SmallString<128> CWD;
+  if (std::error_code EC = sys::fs::current_path(CWD)) {
+    errs() << "Error getting current directory: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  SmallString<128> TmpDirectory;
+  sys::path::append(TmpDirectory, CWD, "tmp");
+  if (std::error_code EC = sys::fs::create_directory(TmpDirectory))
+    errs() << "Error creating tmp directory: " << EC.message() << "!\n";
+
+  return TmpDirectory;
+}
+
+TestRunner::TestRunner(StringRef TestName, std::vector<std::string> TestArgs,
+                       StringRef ReducedFilepath)
+    : TestName(TestName), TestArgs(std::move(TestArgs)),
+      ReducedFilepath(ReducedFilepath) {
+  TmpDirectory = initializeTmpDirectory();
+}
+
+/// Runs the interestingness test, passes file to be tested as first argument
+/// and other specified test arguments after that.
+int TestRunner::run(StringRef Filename) {
+  std::vector<StringRef> ProgramArgs;
+  ProgramArgs.push_back(TestName);
+  ProgramArgs.push_back(Filename);
+
+  for (auto Arg : TestArgs)
+    ProgramArgs.push_back(Arg.c_str());
+
+  StringRef SR = "";
+  Optional<StringRef> Redirects[3] = {SR, SR, SR}; // STDIN, STDOUT, STDERR
+  int Result = sys::ExecuteAndWait(TestName, ProgramArgs, None, Redirects);
+
+  if (Result < 0) {
+    Error E = make_error<StringError>("Error running interesting-ness test\n",
+                                      inconvertibleErrorCode());
+    outs() << toString(std::move(E));
+    exit(1);
+  }
+
+  return !Result;
+}

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

+//===- Delta.h - 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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
+#define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
+
+#include "../TestRunner.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include <fstream>
+#include <set>
+#include <vector>
+
+using namespace llvm;
+
+struct Chunk {
+  unsigned begin;
+  unsigned end;
+
+  /// Helper function to verify if a given Target-index is inside the Chunk
+  bool contains(unsigned Index) const { return Index >= begin && Index <= end; }
+
+  void print() const {
+    outs() << "[" << begin;
+    if (end - begin != 0)
+      outs() << "," << end;
+    outs() << "]";
+  }
+
+  /// Operator when populating CurrentChunks in Generic Delta Pass
+  friend bool operator!=(const Chunk &C1, const Chunk &C2) {
+    return C1.begin != C2.begin || C1.end != C2.end;
+  }
+
+  /// Operator used for sets
+  friend bool operator<(const Chunk &C1, const Chunk &C2) {
+    return std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end);
+  }
+};
+
+namespace llvm {
+
+/// This function implements the Delta Debugging algorithm, it receives a
+/// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
+/// splits them in half; these chunks of targets are then tested while ignoring
+/// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
+/// it is removed from consideration. The algorithm will attempt to split the
+/// Chunks in half and start the process again until it can't split chunks
+/// anymore.
+///
+/// This function is intended to be called by each specialized delta pass (e.g.
+/// RemoveFunctions) and receives three key parameters:
+/// * Test: The main TestRunner instance which is used to run the provided
+/// interesting-ness test, as well as to store and access the reduced Program.
+/// * Targets: The amount of Targets that are going to be reduced by the
+/// algorithm, for example, the RemoveGlobalVars pass would send the amount of
+/// initialized GVs.
+/// * ExtractChunksFromModule: A function used to tailor the main program so it
+/// only contains Targets that are inside Chunks of the given iteration.
+/// Note: This function is implemented by each specialized Delta pass
+///
+/// Other implementations of the Delta Debugging algorithm can also be found in
+/// the CReduce, Delta, and Lithium projects.
+void runDeltaPass(TestRunner &Test, unsigned Targets,
+                  std::function<void(const std::vector<Chunk> &, Module *)>
+                      ExtractChunksFromModule);
+} // namespace llvm
+
+#endif

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

+//===- 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"
+
+/// Writes IR code to the given Filepath
+static bool writeProgramToFile(StringRef Filepath, int FD, const Module &M) {
+  ToolOutputFile Out(Filepath, FD);
+  M.print(Out.os(), /*AnnotationWriter=*/nullptr);
+  Out.os().close();
+
+  if (!Out.os().has_error()) {
+    Out.keep();
+    return false;
+  }
+  return true;
+}
+
+/// Creates a temporary (and unique) file inside the tmp folder and writes
+/// the given module IR.
+static SmallString<128> createTmpFile(Module *M, StringRef TmpDir) {
+  SmallString<128> UniqueFilepath;
+  int UniqueFD;
+
+  SmallString<128> TmpFilepath;
+  sys::path::append(TmpFilepath, TmpDir, "tmp-%%%.ll");
+  std::error_code EC =
+      sys::fs::createUniqueFile(TmpFilepath, UniqueFD, UniqueFilepath);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  if (writeProgramToFile(UniqueFilepath, UniqueFD, *M)) {
+    errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n";
+    exit(1);
+  }
+  return UniqueFilepath;
+}
+
+/// Prints the Chunk Indexes with the following format: [start, end], if
+/// chunk is at minimum size (1), then it just displays [start].
+static void printChunks(std::vector<Chunk> Chunks, bool Oneline = false) {
+  if (Chunks.empty()) {
+    outs() << "No Chunks";
+    return;
+  }
+
+  for (auto C : Chunks) {
+    if (!Oneline)
+      outs() << '\t';
+    C.print();
+    if (!Oneline)
+      outs() << '\n';
+  }
+}
+
+/// Counts the amount of lines for a given file
+static unsigned getLines(StringRef Filepath) {
+  unsigned Lines = 0;
+  std::string CurrLine;
+  std::ifstream FileStream(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) {
+  outs() << "Increasing granularity...";
+  std::vector<Chunk> NewChunks;
+  bool SplitOne = false;
+
+  for (auto &C : Chunks) {
+    if (C.end - C.begin == 0)
+      NewChunks.push_back(C);
+    else {
+      unsigned 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;
+    outs() << "Success! New Chunks:\n";
+    printChunks(Chunks);
+  }
+  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, unsigned Targets,
+    std::function<void(const std::vector<Chunk> &, Module *)>
+        ExtractChunksFromModule) {
+  if (!Targets) {
+    outs() << "\nNothing to reduce\n";
+    return;
+  }
+
+  std::vector<Chunk> Chunks = {{1, Targets}};
+  std::set<Chunk> UninterestingChunks;
+  std::unique_ptr<Module> ReducedProgram;
+
+  if (!Test.run(Test.getReducedFilepath())) {
+    outs() << "\nInput isn't interesting! Verify interesting-ness test\n";
+    return;
+  }
+
+  if (!increaseGranularity(Chunks)) {
+    outs() << "\nAlready at minimum size. Cannot reduce anymore.\n";
+    return;
+  }
+
+  do {
+    UninterestingChunks = {};
+    for (int I = Chunks.size() - 1; I >= 0; --I) {
+      std::vector<Chunk> CurrentChunks;
+
+      for (auto C : Chunks)
+        if (!UninterestingChunks.count(C) && C != Chunks[I])
+          CurrentChunks.push_back(C);
+
+      if (CurrentChunks.empty())
+        continue;
+
+      // 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());
+      // Write Module to tmp file
+      SmallString<128> CurrentFilepath =
+          createTmpFile(Clone.get(), Test.getTmpDir());
+
+      outs() << "Testing with: ";
+      printChunks(CurrentChunks, /*Oneline=*/true);
+      outs() << " | " << sys::path::filename(CurrentFilepath);
+
+      // Current Chunks aren't interesting
+      if (!Test.run(CurrentFilepath)) {
+        outs() << "\n";
+        continue;
+      }
+
+      UninterestingChunks.insert(Chunks[I]);
+      Test.setReducedFilepath(CurrentFilepath);
+      ReducedProgram = std::move(Clone);
+      outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
+    }
+    // Delete uninteresting chunks
+    auto UnwantedChunks = Chunks.end();
+    UnwantedChunks = std::remove_if(Chunks.begin(), Chunks.end(),
+                                    [UninterestingChunks](const Chunk &C) {
+                                      return UninterestingChunks.count(C);
+                                    });
+    Chunks.erase(UnwantedChunks, Chunks.end());
+
+  } while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
+
+  // If we reduced the testcase replace it
+  if (ReducedProgram)
+    Test.setProgram(std::move(ReducedProgram));
+  outs() << "Couldn't increase anymore.\n";
+}
 No newline at end of file

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

+//===- ReduceFunctions.h - Specialized Delta Pass -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce functions (and any instruction that calls it) in the provided
+// Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Delta.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+namespace llvm {
+void reduceFunctionsDeltaPass(TestRunner &Test);
+} // namespace llvm

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

+//===- ReduceFunctions.cpp - Specialized Delta Pass -----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce functions (and any instruction that calls it) in the provided
+// Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceFunctions.h"
+
+/// Removes all the Defined Functions (as well as their calls)
+/// that aren't inside any of the desired Chunks.
+/// @returns the Module stripped of out-of-chunk functions
+static void extractFunctionsFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                       Module *Program) {
+  // Get functions inside desired chunks
+  std::set<Function *> FuncsToKeep;
+  unsigned I = 0, FunctionCount = 0;
+  for (auto &F : *Program)
+    if (!F.isDeclaration() && I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(++FunctionCount))
+        FuncsToKeep.insert(&F);
+      if (FunctionCount == ChunksToKeep[I].end)
+        ++I;
+    }
+
+  // Delete out-of-chunk functions, and replace their calls with undef
+  std::vector<Function *> FuncsToRemove;
+  for (auto &F : *Program)
+    if (!F.isDeclaration() && !FuncsToKeep.count(&F)) {
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      FuncsToRemove.push_back(&F);
+    }
+
+  for (auto *F : FuncsToRemove)
+    F->eraseFromParent();
+
+  // Delete instructions with undef calls
+  std::vector<Instruction *> InstToRemove;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &I : BB)
+        if (auto *Call = dyn_cast<CallInst>(&I))
+          if (!Call->getCalledFunction()) {
+            // Instruction might be stored / used somewhere else
+            I.replaceAllUsesWith(UndefValue::get(I.getType()));
+            InstToRemove.push_back(&I);
+          }
+
+  for (auto *I : InstToRemove)
+    I->eraseFromParent();
+}
+
+/// Counts the amount of non-declaration functions and prints their
+/// respective name & index
+static unsigned countDefinedFunctions(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "Function Index Reference:\n";
+  unsigned FunctionCount = 0;
+  for (auto &F : *Program)
+    if (!F.isDeclaration())
+      outs() << "\t" << ++FunctionCount << ": " << F.getName() << "\n";
+
+  outs() << "----------------------------\n";
+  return FunctionCount;
+}
+
+void llvm::reduceFunctionsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Functions...\n";
+  unsigned Functions = countDefinedFunctions(Test.getProgram());
+  runDeltaPass(Test, Functions, extractFunctionsFromModule);
+  outs() << "----------------------------\n";
+}
 No newline at end of file

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

+//===- llvm-reduce.cpp - The LLVM Delta Reduction 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 tries to reduce an IR test case for a given interesting-ness
+// test. It runs multiple delta debugging passes in order to minimize the input
+// file. It's worth noting that this is a part of the bugpoint redesign
+// proposal, and thus a *temporary* tool that will eventually be integrated
+// into the bugpoint tool itself.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DeltaManager.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/raw_ostream.h"
+#include <system_error>
+#include <vector>
+
+using namespace llvm;
+
+static cl::opt<bool> Help("h", cl::desc("Alias for -help"), cl::Hidden);
+static cl::opt<bool> Version("v", cl::desc("Alias for -version"), cl::Hidden);
+
+static cl::opt<std::string> InputFilename(cl::Positional, cl::Required,
+                                          cl::desc("<input llvm ll/bc file>"));
+
+static cl::opt<std::string>
+    TestFilename("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"));
+
+static cl::opt<std::string>
+    OutputFilename("output",
+                   cl::desc("Specify the output file. default: reduced.ll"));
+static cl::alias OutputFileAlias("o", cl::desc("Alias for -output"),
+                                 cl::aliasopt(OutputFilename));
+
+static cl::opt<bool>
+    ReplaceInput("in-place",
+                 cl::desc("WARNING: This option will replace your input file"
+                          "with the reduced version!"));
+
+// Parses IR into a Module and verifies it
+static std::unique_ptr<Module> parseInputFile(StringRef Filename,
+                                              LLVMContext &Ctxt) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Result = parseIRFile(Filename, Err, Ctxt);
+  if (!Result) {
+    Err.print("llvm-reduce", errs());
+    return Result;
+  }
+
+  if (verifyModule(*Result, &errs())) {
+    errs() << "Error: " << Filename << " - 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.\n");
+
+  LLVMContext Context;
+  std::unique_ptr<Module> OriginalProgram =
+      parseInputFile(InputFilename, Context);
+
+  // Initialize test environment
+  TestRunner Tester(TestFilename, TestArguments, InputFilename);
+  Tester.setProgram(std::move(OriginalProgram));
+
+  // Try to reduce code
+  runDeltaPasses(Tester);
+  StringRef ReducedFilename = sys::path::filename(Tester.getReducedFilepath());
+
+  if (ReducedFilename == sys::path::filename(InputFilename)) {
+    outs() << "\nCouldnt reduce input :/\n";
+  } else {
+    if (ReplaceInput) // In-place
+      OutputFilename = InputFilename.c_str();
+    else if (OutputFilename.empty())
+      OutputFilename = "reduced.ll";
+    else
+      OutputFilename += ".ll";
+
+    sys::fs::copy_file(Tester.getReducedFilepath(), OutputFilename);
+    outs() << "\nDone reducing! Reduced IR to file: " << OutputFilename << "\n";
+  }
+
+  return 0;
+}