Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.compilers > #3460

Re: binary search debugging of compilers

Show all headers | View raw

On 2023-05-12, Russ Cox <rsc@swtch.com> wrote:
> In 2015, Keith Randall was working on a new SSA backend for the Go
> compiler. The old and new backends coexisted, and we could use either
> for any given function in the compilation. Keith introduced an
> environment variable GOSSAHASH that specifies the last few binary
> digits of the hash of function names that should use the new backend.
> So GOSSAHASH=0110 means compile only those functions whose names hash
> to a value with last four bits 0110. When a test is failing with the
> new backend, you try GOSSAHASH=0 and GOSSAHASH=1, and then use binary
> search to progressively refine the pattern, narrowing the failure down
> until only a single function is being compiled with the new backend.
> This was invaluable for approaching failures in large real-world tests
> (tests for libraries or production code, not for the compiler) that we
> had not written and did not understand. ...

> It seems like the idea of binary search to narrow down a buggy
> software change is so natural that there must have been many earlier
> uses for debugging before 1999, especially in compilers.

I have used binary searching to find bugs in the TXR Lisp compiler.

Say for the sake of simplicity that I already have a pretty reliable
idea in which file the miscompiled function resides.

Because the compiler executes the top-level forms that it compiles,
I can go to 50% of that file (literally by typing 50% in Vim).
Then stick a (setf *opt-level* 0) at that line. The bottom half
of the file is then compiled without optimizations. If the bug goes
away, then something is being mis-optimized in the second half.
And so it goes.

Another trick I have used is to suppress the compilation of
specific forms according to this pattern:

  (defun fun (...) ...)   --> (eval '(defun fun () ...))

I.e. take the form, and eval its quoted version:

   form -> (eval 'form)

So the compiler now is compiling nothing more than an eval call which
takes a canned code literal as its argument. When the resulting compiled
file is loaded, fun will be an interpreted function, not a compiled
fucntion: the compiled version of the eval call executes, interpreting
the defun form, resulting in an interpreted function being defined.  If
the bug goes away, that function was being miscompiled.

(This works in Lisp dialects that have a pure interpreter behind eval;
dialects whose eval is actually a compiler may not support this
technique well.)

The hash technique seems nice. If we have no idea where in the
code base the miscompilation is happening, it seems like it could help;
it seems easier than some of the following techniques.

I often have a good idea where in the code base the problem is because
during the rebuild of TXR, files are compiled one by one. As each file
in the stdlib/ is compiled, the next compile job now uses that file (if
it is implied for loading).  So more ofen than not, as soon as we
miscompile some file that used during compilation, the compilation of
the next file will misbehave. Or possibly the same file. The compiler
evaluates what it compiles (unless told not to).  If the compiler is
compiling some code that it's also itself using, it may misbehave soon
after miscompiling some of it, before that file is done compiling.

A useful technique used sometimes is to substitute known-good compiled
files. If the problem goes away if we substitute a known-good
compiled file (touching the timestamps so that it's not clobbered
with a recompile), we can suspect that the file is being miscompiled.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

binary search debugging of compilers Russ Cox <rsc@swtch.com> - 2023-05-12 13:59 -0400
  Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-13 03:20 +0000
  Re: binary search debugging of compilers Fernando <pronesto@gmail.com> - 2023-05-13 04:47 -0700
    Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-14 02:49 +0000
      Re: binary search debugging of compilers gah4 <gah4@u.washington.edu> - 2023-05-14 13:38 -0700
        Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-15 21:52 +0000
          Re: binary search debugging of compilers gah4 <gah4@u.washington.edu> - 2023-05-16 23:52 -0700
            Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-17 18:28 +0000
              Re: binary search debugging of compilers gah4 <gah4@u.washington.edu> - 2023-05-17 15:23 -0700
                Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-19 03:21 +0000
                Re: binary search debugging of compilers Thomas Koenig <tkoenig@netcologne.de> - 2023-05-19 21:59 +0000
                Re: binary search debugging of compilers gah4 <gah4@u.washington.edu> - 2023-05-20 20:20 -0700
                Re: Old C compilers, binary search debugging of compilers Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2023-05-22 09:05 +0200
              binary search debugging of compilers Max B <tekk.nolagi@gmail.com> - 2023-05-19 16:31 -0500
  Re: binary search debugging of compilers Thomas Koenig <tkoenig@netcologne.de> - 2023-05-14 19:59 +0000
    Re: binary search debugging of compilers Cameron McInally <cameron.mcinally@nyu.edu> - 2023-05-14 23:28 -0400
    Re: binary search debugging of compilers Kaz Kylheku <864-117-4973@kylheku.com> - 2023-05-15 21:35 +0000

csiph-web