New Paper on Test-Case Reduction

For about the last four years my group has struggled with the problem of taking a large program that makes a compiler do something bad (crash, run forever, generate incorrect code) and turning it into a minimum-sized program that elicits the same bad behavior. Delta is a great tool but it does not entirely solve the problem. Anyway, the short version of the story is that we spent a ton of time on this problem and only made good headway during the last year or so.

Our various approaches and their results are written up in a paper that I’ll present at PLDI 2012 in Beijing in June. I’m pretty happy with it. The audience is narrow but one of the new tools, C-Reduce (we’ll announce a release here shortly), really nails the problem and produces output far smaller than any tool anyone else has produced.

It had been a long time (eight years, perhaps) since I took both the technical lead and writing lead on a paper and let me tell you, it was awful. I’m not saying I did all the work or anything, but I did a lot of it and it about killed me. Anyway, I have a fresh appreciation for implementation effort that students put into a systems paper. C-Reduce is a simple tool that has basically one internal interface, and somehow it took at least a dozen iterations before I arrived at a version of this interface that I’m happy with.


5 responses to “New Paper on Test-Case Reduction”

  1. Nice paper.
    I’ve been using c_reduce in the last couple of weeks on a few gcc bug testcases and it’s really nice and effective.

    A few problems came up during testing:
    – Sometimes c_reduce will apparently loop endlessly. (The inline run blows up the testcase again and again)
    – clang_delta constantly crashes when its build with the latest clang trunk version (started ~2 weeks ago)
    But c_reduce is even useful without a working clang_delta…

  2. Could you please clarify the licence of this tool? There are several different BSD-like licences in various files in the git repo, and many files are not obviously covered by any of them.

  3. Hi Mans, everything is intended to be under our usual BSD-style license. We’ll get that cleaned up as we move towards making a release.

    Octoploid, I don’t think we’ve seen a test case with the inlining problem you describe. If it’s a file you can share, we’d love to have a real case that blows up. Tuning inliners is never easy.

    Could you try the latest clang_delta? It has generally been working well for me lately. If the current revision crashes please let us know and we’ll fix it ASAP. Please give us platform info as well; all of our development is on x64 Linux.

  4. regehr:

    IIRC I was using a testcase for a still unfixed gcc lto bug:
    It’s a bit unusual because the bug depends on the size of the input. (so maybe looping cannot be avoided)

    The crashes were fixed by not building
    a “buggy” compiler with a “buggy” compiler. (I’ve build clang trunk with clang 3.0 today and everything seems to be OK).
    I still see occasional crashes in some passes. (If I find the time I will report them to the new mailinglist)

  5. Octoploid, great. For a variety of reasons I generally just build Clang and clang_delta using g++ and this always seems to work.

    We would definitely appreciate bug reports for passes, and I may hack C-Reduce a bit so that when clang_delta dies it produces a nice little bug report. Actually the right thing to do is obvious: fork off a new C-Reduce instance, this time looking for a small testcase triggering the clang_delta bug.

    So far, happily, I have avoided using C-Reduce to debug C-Reduce.