How we use binary search to find compiler bugs • Hacker News Board

Re: How we use binary search to find compiler bugs

#11

Post by hedora » Sat, Oct 22, 2022, 4:19 AM UTC

Check out the Delta Debugging paper. There has been a ton of follow-on work (1000+ direct citations), and lots of tools exist.

Here's the citation, abstract and link to a PDF copy:

Simplifying and isolating failure-inducing input Andreas Zeller, Ralf Hildebrandt IEEE Transactions on Software Engineering 28 (2), 183-200, 2002

Given some test case, a program fails. Which circumstances of the test case are responsible for the particular failure? The delta debugging algorithm generalizes and simplifies the failing test case to a minimal test case that still produces the failure. It also isolates the difference between a passing and a failing test case. In a case study, the Mozilla Web browser crashed after 95 user actions. Our prototype implementation automatically simplified the input to three relevant user actions. Likewise, it simplified 896 lines of HTML to the single line that caused the failure. The case study required 139 automated test runs or 35 minutes on a 500 MHz PC.

http://cs.purdue.edu/homes/xyzhang/fall07/Papers/delta-debug...

Edit: adjusted tone

Re: How we use binary search to find compiler bugs

#12

Post by FeepingCreature » Sat, Oct 22, 2022, 6:09 AM UTC

D also has Dustmite (https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...), same idea.

Re: How we use binary search to find compiler bugs

#13

Post by drdrey » Sat, Oct 22, 2022, 6:29 AM UTC

bugpoint is the equivalent for llvm: https://www.llvm.org/docs/CommandGuide/bugpoint.html

Re: How we use binary search to find compiler bugs

#14

Post by lozenge » Sat, Oct 22, 2022, 10:05 AM UTC

tantalor wrote: post #8

I have wondered how to extend this to combinations of elements. What if the bad outcome only happens when two or more elements are enabled? Is there a generalization of binary search for powersets? Can this be done efficiently?

You might want to look at Hypothesis, a testing library that can also randomly generate test cases and reduce examples to a more minimal case. It supports many data types and "strategies".

Re: How we use binary search to find compiler bugs

#15

Post by Genghis_9000 » Sat, Oct 22, 2022, 12:58 PM UTC

> You may have heard of bisecting from geometry or from git bisect1. Those are the two places I heard about it

I heard of it from when I first started programming and I cut the code in half (maybe 3rds or other units, close enough) until I found which part was breaking the program.

Re: How we use binary search to find compiler bugs

#16

Post by kevinventullo » Sat, Oct 22, 2022, 1:15 PM UTC

tantalor wrote: post #8

I have wondered how to extend this to combinations of elements. What if the bad outcome only happens when two or more elements are enabled? Is there a generalization of binary search for powersets? Can this be done efficiently?

If I understand your problem correctly, you could iterate through the elements disabling one at a time and checking whether the bad outcome still occurs.

Assuming this works, it should be optimal: if you’re only getting a binary outcome at each step, you’ll never do better than lg(2^n) = n.

Re: How we use binary search to find compiler bugs

#17

Post by tekknolagi » Sat, Oct 22, 2022, 5:56 PM UTC

tantalor wrote: post #8

I have wondered how to extend this to combinations of elements. What if the bad outcome only happens when two or more elements are enabled? Is there a generalization of binary search for powersets? Can this be done efficiently?

This does work for combinations -- often I get JIT lists with two functions on it and the issue has to do with something in the call path itself.