Path: csiph.com!xmission!usenet.csail.mit.edu!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Cameron McInally Newsgroups: comp.compilers Subject: Re: binary search debugging of compilers Date: Sun, 14 May 2023 23:28:11 -0400 Organization: Compilers Central Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-05-009@comp.compilers> References: <23-05-003@comp.compilers> <23-05-007@comp.compilers> Reply-To: cameron.mcinally@nyu.edu MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="6269"; mail-complaints-to="abuse@iecc.com" Keywords: tools, debug Posted-Date: 15 May 2023 12:15:42 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <23-05-007@comp.compilers> X-Orig-IP: 209.85.217.70 Xref: csiph.com comp.compilers:3465 On Sun, May 14, 2023 at 22:42 Thomas Koenig wrote: > Russ Cox schrieb: > > > As I mentioned at the top, I am interested to hear about earlier uses > > of approaches like this, or any other ideas for situations where the > > approach might be applicable. Clearly the general problem has overlaps > > with group testing [1], and in particular Hwang's binary search-based > > approach (1972) [2]. > > For GCC regression-hunting, two techniques are routinely used. > > One of them is the use of "gcc bisect", described at > https://git-scm.com/docs/git-bisect > . If there is a failing test > case, this can (at the cost of some CPU time) usually pinpoint > offending commit. Ah, this is close to my heart. The story I heard was that automated regression bisection originated in the Cray compiler group around the mid 1990s. I didn't join that team until the aughts, but can attest to the quality of Cray's system, which is still in use today AFAIK. https://ieeexplore.ieee.org/document/625082 For the general case of reducing runtime errors, the Wolf Fencing algorithm would be a good thread to pull for uncovering the history. https://dl.acm.org/doi/abs/10.1145/358690.358695 Hope that helps, Cam