Path: csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Kaz Kylheku <643-408-1753@kylheku.com>
Newsgroups: comp.compilers
Subject: Nice application of that hash bisection debugging approach.
Date: Fri, 04 Jul 2025 08:27:04 -0000
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <25-07-002@comp.compilers>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="81734"; mail-complaints-to="abuse@iecc.com"
Keywords: debug
Posted-Date: 04 Jul 2025 13:21:39 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:3669

I'm doing compiler work at the moment and have one of those bugs
where an optimization miscompiles something in the compiler which
then shows up as a breakage elsewhere.

Because this is Lisp, it took literally two or three minutes to whip up the
hash bisection technique.

In the Lisp compiler, the basic unit of file compilation is the
top-level form.

I defined three dynamically scoped variables in the compiler,
which are shown with the final values:

(defvar *cmask* #b1111111)
(defvar *cval*  #b0101100)
(defvar *chash*)

*chash* is bound to the equal hash calculated over the top-level form
being compiled.

E.g. if the form were (+ 2 2), the hash would be calculated
as:

  2> (hash-equal '(+ 2 2))
  192681593

and that would be the value of *chash*.

Then whenever the expression

  (eql (logand *chash* *cmask*) *cval*)

is true, the optimization is enabled. Also, when that same expression
is true, a portion of top-level form is printed: enough to identify it.

I quickly arrived at the above values. One form is printed,
and that's the one mistranslated:

$ make
TXR stdlib/optimize.tl -> stdlib/optimize.tlo
TXR stdlib/compiler.tl -> stdlib/compiler.tlo
(defun compile-file-conditionally
  (in-path out-path
   test-fn))
TXR stdlib/asm.tl -> stdlib/asm.tlo
./txr: unhandled exception of type error:
./txr: slot: #<struct-type assembler> has no slot named asm
make: failing command:
./txr --in-package=sys --compile=stdlib/asm.tl:stdlib/asm.tlo.tmp
Makefile:195: recipe for target 'stdlib/asm.tlo' failed
make: *** [stdlib/asm.tlo] Error 1

So the function compile-file-condtionally is the mistranslated one.

When we flip the top masked bit in *cval* from 0 to 1:

(defvar *cmask* #b1111111)
(defvar *cval*  #b1101100)
(defvar *chash*)

then a different top-level form is identified and targeted for
the optimization, a function called rewrite in the optimizer, and the
compilation succeeds:

$ make
TXR stdlib/optimize.tl -> stdlib/optimize.tlo
(defun rewrite
  (fun list out))
TXR stdlib/compiler.tl -> stdlib/compiler.tlo
TXR stdlib/asm.tl -> stdlib/asm.tlo

It's so easy to do it's not worth keeping the changes; next time I need
the technique, I will whip it up from scratch again.

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