Re: binary search debugging of compilers

Kaz Kylheku <864-117-4973@kylheku.com>
Sun, 14 May 2023 02:49:15 -0000 (UTC)

          From comp.compilers

Related articles
binary search debugging of compilers rsc@swtch.com (Russ Cox) (2023-05-12)
Re: binary search debugging of compilers 864-117-4973@kylheku.com (Kaz Kylheku) (2023-05-13)
Re: binary search debugging of compilers pronesto@gmail.com (Fernando) (2023-05-13)
Re: binary search debugging of compilers 864-117-4973@kylheku.com (Kaz Kylheku) (2023-05-14)
Re: binary search debugging of compilers tkoenig@netcologne.de (Thomas Koenig) (2023-05-14)
Re: binary search debugging of compilers gah4@u.washington.edu (gah4) (2023-05-14)
Re: binary search debugging of compilers cameron.mcinally@nyu.edu (Cameron McInally) (2023-05-14)
Re: binary search debugging of compilers 864-117-4973@kylheku.com (Kaz Kylheku) (2023-05-15)
Re: binary search debugging of compilers 864-117-4973@kylheku.com (Kaz Kylheku) (2023-05-15)
Re: binary search debugging of compilers gah4@u.washington.edu (gah4) (2023-05-16)
[15 later articles]
| List of all articles for this month |

From: Kaz Kylheku <864-117-4973@kylheku.com>
Newsgroups: comp.compilers
Date: Sun, 14 May 2023 02:49:15 -0000 (UTC)
Organization: A noiseless patient Spider
References: 23-05-003 23-05-005
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

On 2023-05-13, Fernando <pronesto@gmail.com> 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


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.