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

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

19–32

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

28–31

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

28–31

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

24–25

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

28–31

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

28–31

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

28–31

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

2

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

2

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

47–48

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

47–48

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/test/BP2/remove-funcs-test.sh

+#!/bin/bash
+
+ret=$(lli $1)
+
+if [[ $ret -eq 10 ]]; then
+  exit 0
+else
+  exit 1
+fi

llvm/test/BP2/remove-functions.ll

+; Test that bp2 can remove uninteresting functions (and its respective calls)
+;
+; RUN: bp2 --test=remove-funcs-test.sh remove-functions.ll
+; RUN: llvm-dis reduced.bc -o - | FileCheck %s
+; RUN: bash remove-funcs-test.sh reduced.bc
+; REQUIRES: plugins
+@.str = private unnamed_addr constant [4 x i8] c"%i\0A\00", align 1
+
+define i32 @uninteresting1() {
+entry:
+  ret i32 25
+}
+
+; CHECK: interesting()
+define i32 @interesting() {
+entry:
+  ret i32 10
+}
+
+; CHECK-NOT: uninteresting2()
+define i32 @uninteresting2() {
+entry:
+  ret i32 2000
+}
+
+; CHECK: main()
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  %number = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  store i32 0, i32* %number, align 4
+  %call = call i32 @uninteresting1()
+  %call1 = call i32 @interesting()
+  store i32 %call1, i32* %number, align 4
+  %0 = load i32, i32* %number, align 4
+  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %0)
+  %call3 = call i32 @uninteresting1()
+  %call4 = call i32 @uninteresting2()
+  ret i32 0
+}
+
+declare i32 @printf(i8*, ...)

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
+  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(llvm-reduce
+  llvm-reduce.cpp
+  TestRunner.cpp
+  deltas/RemoveFunctions.cpp
+
+  DEPENDS
+  intrinsics_gen
+  )
+export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

+//===- 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 class calls each specialized Delta pass as a class template given to
+// the generic Delta Pass
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+#include "deltas/Delta.h"
+#include "deltas/RemoveFunctions.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+
+
+namespace llvm {
+
+class DeltaManager {
+public:
+  static void runDeltaPasses(TestRunner &Tester) {
+    outs() << "Reducing functions...\n";
+    Delta<RemoveFunctions>::run(Tester);
+    // TODO: Implement the rest of the 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 =
+ AsmParser
+ BitReader
+ BitWriter
+ CodeGen
+ IRReader
+ IPO
+ Instrumentation
+ Linker
+ ObjCARC
+ Scalar
+ all-targets

llvm/tools/llvm-reduce/TestRunner.h

+//===- 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 file contains all the info necessary for running the provided
+// interesting-ness test, as well as the most reduced module and its
+// respective filename.
+//
+//===----------------------------------------------------------------------===//
+
+#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/Program.h"
+#include "llvm/ADT/ArrayRef.h"
+#include <vector>
+
+namespace llvm {
+
+class TestRunner {
+public:
+  TestRunner(std::string TestFilename, std::vector<std::string> TArgs,
+             std::string InputFilename, SmallString<128> CWD);
+
+  /// Runs the interestingness test for the given filename
+  /// @returns 1 if the Filename is interesting, 0 if otherwise.
+  int run(SmallString<128> Filename);
+
+  /// Filename to the most reduced testcase
+  SmallString<128> getReducedFilename() { return ReducedFilename; }
+  /// Directory where tmp files are created
+  SmallString<128> getTmpDir() { return TmpDirectory; }
+  /// Returns the most reduced version of the original testcase
+  Module* getProgram() { return Program.get(); }
+  
+  void setReducedFilename(SmallString<128> F) { ReducedFilename = F; }
+  void setProgram(std::unique_ptr<Module> &P) { Program = std::move(P); }
+
+private:
+  SmallString<128> TestName;
+  std::vector<std::string> TestArgs;
+  SmallString<128> ReducedFilename;
+  SmallString<128> TmpDirectory;
+  std::unique_ptr<Module> Program;
+};
+
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/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);
+}
+
+SmallString<128> append(SmallString<128> Path, std::string Filename) {
+  SmallString<128> Filepath = Path;
+  Filepath += "/" + Filename;
+  return Filepath;
+}
+
+TestRunner::TestRunner(std::string TestFilename, std::vector<std::string> TArgs,
+                       std::string InputFilename, SmallString<128> CWD)
+    : TestName(append(CWD, TestFilename)), TestArgs(TArgs),
+      ReducedFilename(append(CWD, InputFilename)),
+      TmpDirectory(append(CWD, "tmp")) {}
+
+
+/// Runs the interesting-ness test with the given arguments
+int TestRunner::run(SmallString<128> 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;
+}

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

+//===- 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 Data type is used in the Delta Reduction Algorithm, contains the
+// start and end index for the given chunk of Targets (i.e. Functions, Basic
+// Blocks, GVs, etc.)
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_CHUNK_H
+#define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_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

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

+//===- 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 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 tests if a certain chunk is un-interesting (until chunk
+// size cannot be reduced).
+//
+//===----------------------------------------------------------------------===//
+
+#include "../TestRunner.h"
+#include "Chunk.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
+#include <fstream>
+#include <memory>
+#include <set>
+#include <string>
+#include <vector>
+
+namespace llvm {
+
+/// Prints the Chunk Indexes with the following format: [start, end].
+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(SmallString<128> Filepath) {
+  unsigned Lines = 0;
+  std::string CurrLine;
+  std::ifstream FileStream(to_string(Filepath));
+
+  while (std::getline(FileStream, CurrLine))
+    ++Lines;
+
+  return Lines;
+}
+
+/// Splits Chunks in half, if unable to split returns false.
+inline bool increaseGranularity(std::vector<Chunk> &Chunks) {
+  outs() << "Increasing granularity...";
+  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;
+}
+
+/// Returns the Filename (with extension) or a given path
+inline std::string getFilename(SmallString<128> Filepath) {
+  return Filepath.substr(Filepath.rfind('/') + 1);
+}
+
+template <class D> class Delta {
+public:
+  /// Runs the Delta Debugging algorithm, splits the code into chunks and 
+  /// reduces the amount of chunks that are considered interesting by the
+  /// given test.
+  static void run(TestRunner &Test) {
+    // Get the amount of Fuctions, GVs, Basic Blocks, etc.
+    int TargetCount = D::getTargetCount(Test.getProgram());
+    std::vector<Chunk> Chunks = {{1, TargetCount}};
+    std::vector<Chunk> CurrentChunks;
+    std::set<Chunk> UninterestingChunks;
+
+    if (Test.run(Test.getReducedFilename()))
+      increaseGranularity(Chunks);
+    else {
+      outs() << "Error: input file isnt interesting\n";
+      exit(1);
+    }
+
+    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);
+
+        // Call Delta Pass to Make Module with only Chunk Targets
+        SmallString<128> CurrentFilepath;
+        std::unique_ptr<Module> CurrentProgram =
+            D::prepareIR(CurrentChunks, Test, CurrentFilepath);
+        outs() << " | " << getFilename(CurrentFilepath);
+        // Current Chunks aren't interesting
+        if (!Test.run(CurrentFilepath)) {
+          outs() << "\n";
+          continue;
+        }
+        // We only care about interesting chunks if they reduce the testcase
+        if (getLines(CurrentFilepath) < getLines(Test.getReducedFilename())) {
+          UninterestingChunks.insert(Chunks[I]);
+          Test.setReducedFilename(CurrentFilepath);
+          Test.setProgram(CurrentProgram);
+          outs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath);
+        }
+        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 anymore.\n";
+  }
+};
+
+} // namespace llvm

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

+//===- 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 file is a Specialized Delta Pass, which removes the functions that are
+// not in the provided function-chunks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../TestRunner.h"
+#include "Chunk.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/FunctionComparator.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <memory>
+#include <set>
+#include <vector>
+
+namespace llvm {
+
+class RemoveFunctions {
+public:
+  /// Outputs the number of Functions in the given Module
+  static int getTargetCount(Module* P);
+  /// Deletes non-chunk Functions from module and writes the modified module
+  /// to a tmp file.
+  static std::unique_ptr<Module> prepareIR(std::vector<Chunk> ChunksToKeep, 
+                                           TestRunner &Test,
+                                           SmallString<128> &CurrentFilepath);
+};
+
+} // namespace llvm
+

llvm/tools/llvm-reduce/deltas/RemoveFunctions.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 file is a Specialized Delta Pass, which removes the functions that are
+// not in the provided function-chunks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RemoveFunctions.h"
+#include "llvm/ADT/SmallString.h"
+#include <memory>
+
+using namespace llvm;
+
+/// Writes Bitcode to a unique file inside the "tmp" folder
+bool writeProgramToFile(SmallString<128> Filename, int FD,
+                                   const Module &M) {
+  ToolOutputFile Out(Filename, FD);
+  M.print(Out.os(), /*AnnotationWriter=*/ nullptr,
+          /*ShouldPreserveUseListOrder=*/ true);
+  Out.os().close();
+
+  if (!Out.os().has_error()) {
+    Out.keep();
+    return false;
+  }
+  return true;
+}
+
+/// Goes over the Function Chunks, and removes all the Defined Functions that 
+/// aren't inside any given Chunk. Once stripped, it is written to an
+/// IR file (which is tested by the generic Delta pass).
+std::unique_ptr<Module> RemoveFunctions::prepareIR(
+    std::vector<Chunk> ChunksToKeep,
+    TestRunner &Test,
+    SmallString<128> &CurrentFilepath) {
+  std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram());
+
+  // Get all functions inside desired chunks 
+  std::set<Function*> FuncsToKeep;
+  int I = 0, FunctionCount = 1;
+  for(auto &F : *Clone) {
+    if (!F.isDeclaration()) {
+      if (FunctionCount >= ChunksToKeep[I].begin &&
+          FunctionCount <= ChunksToKeep[I].end) {
+        FuncsToKeep.insert(&F);
+      }
+      if (FunctionCount >= ChunksToKeep[I].end)
+        ++I;
+    ++FunctionCount;
+    }
+  }
+
+  // Delete out-of-chunk functions, and replace their calls with null
+  std::vector<Function*> FuncsToRemove;
+  for (Function &F : *Clone) {
+    if (!F.isDeclaration() && !FuncsToKeep.count(&F)) {
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      FuncsToRemove.push_back(&F);
+    }
+  }
+
+  for (auto *F : FuncsToRemove) {
+    F->eraseFromParent();
+  }
+
+  // Clean up null calls
+  std::vector<Instruction*> InstToRemove;
+  for(auto &F : *Clone)
+    for(auto &BB : F)
+      for(auto &I : BB)
+        if (auto *Call = dyn_cast<CallInst>(&I))
+          if (!Call->getCalledFunction()) {
+            I.replaceAllUsesWith(UndefValue::get(I.getType()));
+            InstToRemove.push_back(&I);
+          }
+
+  for (auto *I : InstToRemove) {
+    I->eraseFromParent();
+  }
+
+  // Write modified module to file
+  SmallString<128> UniqueFilepath;
+  SmallString<128> TmpDirectory = Test.getTmpDir();
+  int UniqueFD;
+  std::error_code EC = sys::fs::createUniqueFile(TmpDirectory + "/tmp-%%%.ll", 
+                                                 UniqueFD, UniqueFilepath);
+  if (EC) {
+    errs() << "Error making unique filename: " << EC.message() << "!\n";
+    exit(1);
+  }
+
+  if (writeProgramToFile(UniqueFilepath, UniqueFD, *Clone)) {
+    errs() << "Error emitting bitcode to file '" << UniqueFilepath << "'!\n";
+    exit(1);
+  }
+  CurrentFilepath = UniqueFilepath;
+
+  return Clone;
+}
+
+/// Counts the amount of non-declaration functions and displays their 
+/// respective index & name 
+int RemoveFunctions::getTargetCount(Module* P) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "Chunk Index Reference:\n";
+  int FunctionCount = 0;
+  for (auto &F : *P)
+    if (!F.isDeclaration()) {
+      ++FunctionCount;
+      outs() << "\t" << FunctionCount << ": " << F.getName() << "\n";
+    }
+  outs() << "----------------------------\n";
+  return FunctionCount;
+}

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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DeltaManager.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/Program.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/raw_ostream.h"
+#include <system_error>
+#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>
+    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("Filename of reduced file, if unset it's outputted" 
+                            "to STDOUT"));
+
+// 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("llvm-reduce", errs());
+    return Result;
+  }
+
+  if (verifyModule(*Result, &errs())) {
+    errs() << "Error: " << Filename << " - input module is broken!\n";
+    return std::unique_ptr<Module>();
+  }
+
+  return Result;
+}
+
+void 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 = CWD;
+  TmpDirectory.append("/tmp");
+  if(std::error_code EC = sys::fs::create_directory(TmpDirectory)) {
+    errs() << "Error creating tmp directory: " << EC.message() << "!\n";
+  }
+}
+
+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> OriginalProgram =
+      parseInputFile(InputFilename, Context);
+
+  SmallString<128> CWD;
+  initializeTmpDirectory(CWD);
+
+  std::vector<std::string> TestArgs(std::move(TestArguments));
+  TestRunner Tester(TestFilename, TestArgs, InputFilename, CWD);
+  Tester.setProgram(OriginalProgram);
+
+  DeltaManager::runDeltaPasses(Tester);
+
+  if(OutputFilename != "") {
+    sys::fs::rename(Tester.getReducedFilename(),
+                    CWD + "/" + OutputFilename + ".ll");
+  }
+  else {
+    // TODO: Output to STDOUT
+  }
+
+  return 0;
+}