Page MenuHomePhabricator

Added Delta IR Reduction Tool
ClosedPublic

Authored by diegotf on Jun 21 2019, 2:09 PM.

Details

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)

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Did the review finish here?

Yes, and continued here D64176

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 updated this revision to Diff 213751.Aug 6 2019, 4:52 PM

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

This revision was not accepted when it landed; it landed in state Needs Review.Aug 6 2019, 5:02 PM
Closed by commit rL368112: Added Delta IR Reduction Tool (authored by diegotf30, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.
hctim added a subscriber: hctim.Aug 6 2019, 5:49 PM

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 added a subscriber: nridge.Aug 6 2019, 7:32 PM

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

llvm-reduce.cpp:function main: error: undefined reference to 'llvm::LLVMContext::LLVMContext()'
phosek added a subscriber: phosek.Aug 6 2019, 7:48 PM

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

--
dblaikie added inline comments.Aug 7 2019, 10:40 AM
llvm/tools/llvm-reduce/deltas/Delta.h
33 ↗(On Diff #207098)

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

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

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

llvm/trunk/docs/BugpointRedesign.md
73

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
8

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

18–19

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

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

std::move(F) probably?

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

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)

107

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?)

151

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

157

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
101

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 marked 11 inline comments as done.Aug 7 2019, 12:04 PM
diegotf added inline comments.
llvm/trunk/docs/BugpointRedesign.md
73

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
151

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

157

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
101

Good idea!

diegotf reopened this revision.Aug 7 2019, 12:04 PM
diegotf marked 2 inline comments as done.

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
157

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 marked 2 inline comments as done.Aug 7 2019, 1:00 PM

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

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

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

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

llvm/tools/llvm-reduce/deltas/Delta.h
33 ↗(On Diff #207098)

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

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

diegotf updated this revision to Diff 213974.Aug 7 2019, 1:01 PM
diegotf marked an inline comment as done.

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

nridge removed a subscriber: nridge.Aug 7 2019, 1:07 PM
This revision was not accepted when it landed; it landed in state Needs Review.Aug 7 2019, 2:38 PM
Closed by commit rL368214: Added Delta IR Reduction Tool (authored by diegotf30, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.

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)).

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

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 reopened this revision.Aug 7 2019, 4:21 PM

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 added a comment.Aug 7 2019, 4:26 PM

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 updated this revision to Diff 214032.EditedAug 7 2019, 4:27 PM

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

lebedev.ri added inline comments.Aug 7 2019, 11:08 PM
llvm/test/BP2/remove-funcs-test.sh
1 ↗(On Diff #206108)

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

llvm/test/Reduce/remove-funcs.ll
4 ↗(On Diff #214032)

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

diegotf marked 4 inline comments as done.Aug 8 2019, 11:08 AM
diegotf added inline comments.
llvm/test/BP2/remove-funcs-test.sh
1 ↗(On Diff #206108)

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

llvm/test/Reduce/remove-funcs.ll
4 ↗(On Diff #214032)

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

diegotf updated this revision to Diff 214201.Aug 8 2019, 11:41 AM
diegotf marked an inline comment as done.

Formatting changes & added llvm-reduce as test dependency

dblaikie added inline comments.Aug 8 2019, 2:25 PM
llvm/tools/llvm-reduce/TestRunner.cpp
46–47 ↗(On Diff #214201)

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

Optional<StringRef> Redirects[3];

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

llvm/tools/llvm-reduce/deltas/Delta.cpp
168–169 ↗(On Diff #214201)

Looks like an unnecessary initialization? Coeuld be written as:

auto UnwantedChunks = std::remove_if....

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

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

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

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

Nice & easy :)

diegotf edited the summary of this revision. (Show Details)Aug 8 2019, 2:39 PM
diegotf updated this revision to Diff 214243.Aug 8 2019, 2:59 PM
diegotf marked 4 inline comments as done.

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

llvm/tools/llvm-reduce/TestRunner.cpp
46–47 ↗(On Diff #214201)

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

llvm/tools/llvm-reduce/deltas/Delta.cpp
168–169 ↗(On Diff #214201)

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

Thanks for the cleaner solution!

dblaikie accepted this revision.Aug 8 2019, 3:07 PM

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

This revision is now accepted and ready to land.Aug 8 2019, 3:07 PM
Closed by commit rL368358: Added Delta IR Reduction Tool (authored by diegotf30, committed by ). · Explain WhyAug 8 2019, 3:16 PM
This revision was automatically updated to reflect the committed changes.
sbc100 added a subscriber: sbc100.Aug 8 2019, 3:54 PM

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

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

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 added a comment.Wed, Sep 4, 4:11 AM

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

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

mgorny added a comment.Wed, Sep 4, 4:27 AM

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.

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 added inline comments.Thu, Sep 5, 4:33 PM
llvm/trunk/test/Reduce/Inputs/remove-funcs.py
1

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

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

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

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)