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: Sat, 13 May 2023 03:20:18 -0000 (UTC) Organization: A noiseless patient Spider Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-05-004@comp.compilers> References: <23-05-003@comp.compilers> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="5361"; mail-complaints-to="abuse@iecc.com" Keywords: tools, debug Posted-Date: 13 May 2023 11:14:32 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:3460 On 2023-05-12, Russ Cox 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