Re: binary search debugging of compilers

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

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