Test-case reduction means taking a large input to a computer program (for compiler debugging, the input is itself a program) and turning it into a much smaller input that still triggers the bug. It is a very important part of the debugging process.
Delta, an excellent open-source implementation of the delta debugging algorithm ddmin, has been the test-case reduction tool of choice for compiler developers. We’ve just released C-Reduce: a test case reducer that often gives output 25 times smaller than Delta’s. The contribution of C-Reduce is adding a lot of domain specificity. For example, it knows how to resolve a typedef, flatten a namespace, inline a function call, remove a dead argument from a function, and rename a variable. These (and dozens of other transformations) use Clang as a source-to-source transformation engine. Although domain specificity is displeasing in a reduction tool, C/C++ programs cannot be fully reduced without it. This earlier blog post contains many examples of C-Reduce’s output.
Resources:
- Download source from the C-Reduce home page.
- Learn how to use C-Reduce and see some examples here.
- See our PLDI 2012 paper for a more thorough explanation and evaluation of C-Reduce.
We’d be happy to hear feedback.
11 responses to “Announcing C-Reduce: A Better Test-Case Reducer for C/C++ Compiler Debugging”
Looking forward to running it on programs generated by CSmith that expose bugs in our compilers – manual reduction is quite hard and automatic reduction would likely eliminate most of the cost of attending to the average detected bug.
Many, many thanks for writing and releasing these!
Congratulations!
This is such a wonderful and useful tool, that I personally don’t use Delta anymore.
(Although I cannot understand why you’ve deleted the first pass_lines runs with 1,2 and 10 (topformflat) in the release. They are essential with large C++ testcases IMHO.)
BTW the mailing-list is also available on Gmane:
http://news.gmane.org/gmane.comp.programming.creduce.devel
Hi Octoploid, for the test cases that I reduce (mostly Csmith output) those passes were just wasting time trying to delete things that had already been tried.
I guess we have a tuning problem, but I’m not sure what to do about it.
One answer would be to tune for the worst case, which is probably large C++. I’ll think about this. In the meantime it should be easy for you to turn on these passes yourself, of course.
One simple heuristic would be to look at the size of the test-case. If it is bigger than say 200kB then use the additional pass_lines runs.
Hi Octoploid, I’m traveling and not getting any hacking done. But when I get home I’ll add the change you suggest.
What would it take to get c-reduce working on Windows? From the llvm site, it looks like clang can be built on Windows, but it cannot parse the C++ standard library included with Visual Studio, etc. What are the components of llvm/clang that c-reduce needs? How much engineering would be needed to replace llvm/clang by another supporting compiler?
Hi WP, the easy thing to do is use C-Reduce in a degraded mode where the Clang-based passes don’t run. It will still be a lot more effective than the Delta tool. You can do this pretty easily and I’ll also try it out when I get a chance.
Clang is used as a library for source to source transformation. Re-implementing that functionality in a different tool would be a large amount of work, and I’m not even sure what tool might be used. Does MS have any libraries supporting src-to-src transformation of C/C++ code? My guess is the best thing to do is wait for Clang so support the MS C++ code.
WP, if you have some Windows programs that trigger compiler bugs that you’d like reduced, please pass them along (with instructions for reproducing the crash or other bug) and we’ll see what can be done.
> What are the components of llvm/clang that c-reduce needs?
The clang_delta tool (part of the C-Reduce package) links against the LLVM “engine” libraries and numerous Clang libraries. The list of libraries is found in this file:
https://github.com/csmith-project/creduce/blob/master/clang_delta/Makefile.am
I’m not sure that this “precise” answer is very useful :-), but I offer it anyway.
Re: running C-Reduce without the Clang-based passes
I’ll mention that we have thought some about making it easier to configure/run C-Reduce without clang_delta (and thus without LLVM/Clang installed).
Even without LLVM/Clang, there are other external dependencies, described in the INSTALL instructions:
https://github.com/csmith-project/creduce/blob/master/INSTALL
We are very interested in people’s use cases: how they do and want to use C-Reduce. Full discussion of this is probably a topic for the C-Reduce development mailing list:
http://www.flux.utah.edu/mailman/listinfo/creduce-dev
Firstly I should say, thanks for c-reduce!
& Thanks for all the insights about building it on Windows.
I think this blog is tres’ cool