Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <864-117-4973@kylheku.com> Newsgroups: comp.compilers Subject: Re: binary search debugging of compilers Date: Sun, 14 May 2023 02:49:15 -0000 (UTC) Organization: A noiseless patient Spider Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-05-006@comp.compilers> References: <23-05-003@comp.compilers> <23-05-005@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="19376"; mail-complaints-to="abuse@iecc.com" Keywords: tools, debug Posted-Date: 14 May 2023 12:20:49 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3462 On 2023-05-13, Fernando wrote: > Hi Russ, that's very interesting. You should consider submitting a report of > the technique to CGO! The next deadline is on the 19th, but then there will be > another deadline on September 1st. We can summarize it briefly. Background: Suppose we have some data processing technique which transforms N entities. A new version of the technique changes how all the entities are transformed. One or more of them are transformed erroneously, resulting in a system regression (one which doesn't readily identify the bad element). Because all elements are transformed with the new technique, there are big differences in all of them compared to the old technique: comparing old and new is futile. Setup: We can (somehow) enumerate the N entities with integers, which we express using a pure binary enumeration. Then, we can discover the number of an erroneously processed element, one bit at a time. Procedure: First we treat all elements numbered ..XXXXXX0 using the new technique technique, and all others using the the old technique. If the system fails, we know that it's the ..XXXXX0 set which has one or more badly processed elements. Otherwise it's the other set, whose enumerations end in a 1. Either way, we have discovered the identity of the last bit. Suppose that discovered bit is 1. We then proceed with the next bit: we process ..XXXXXX01 entities with the new technique and all others with the old technique. If the problem reproduces, we have narrowed to the ...XXXXX01 set, otherwise to the .XXXXX11 set. In this manner we discover every bit, at which point we have a useful piece of information: the identity of a misprocessed element. We can then focus the investigation on how it is misprocessed. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca