Metadebugging (i.e. founding metabugs) methodology.

Hello All

(I hope this forum is the appropriate place to ask)

I'm working within GCC on a Lisp translator (from some Lisp dialect, called MELT, to C) to be used for GCC middle end analysis; the motivation is to be able to code GCC middle end analyzers & passes in my Lisp dialect.

The code is updated several times a day on the GCC SVN. See MELT for details (or ask me).

The lisp dialect is not really documented yet. The major difference is that MELT has both boxed and unboxed values. Also, most primitives are not called as in Lisp (but most control operators are the same, let is somehow a let*, ...). Primitives are described by giving their expansion to C. MELT files have a *.bysl extension (because MELT was called Basilys at first).

The MELT dialect is a lisp like dialect (a Lisp1 in C.Queinnec terminology), with dynamic types and lexical scoping (a la Scheme).

Here is the familiar 2nd order function to map a function into a list.

(defun list_map (lis f)
  (if (is_list lis)
      (if (is_closure f)
	  (let ( (reslis (make_list discr_list)) 
		 (curpair (list_first lis)) )
	    (forever lisloop
		     (if (not (is_pair curpair)) 
			 (return reslis))
		     (let ( (curelem (pair_head curpair)) )
		       (list_append reslis (f curelem)))
		     (setq curpair (pair_tail curpair)))

In the code above, defun if let forever return setq are "keywords" ie have a special significance to the compiler. is_list is_closure make_list list_first not is_pair pair_head list_append pair_tail are primitives (expanded to some C code). lis f lisploop reslis curpair curelem are locally bound names and the function list_map is globally defined by the defun

Here is the not (boolean not, on unboxed longs) and is_list (on values) primitive:

(defprimitive not (:long i) :long "(!(" i "))")

(defprimitive is_list (li) :long
  "(basilys_magic_discr((" li ")) == OBMAG_LIST)")

The first :long occurrence in not before i tells that formal i is an unboxed long, and the second :long occurrence tells that the result of not primitive is an unboxed long.

The is_list primitive definition tells that the result of is_list is an unboxed long, and how to expand it into C. The quoted strings are actually C code fragments appearing in the generated code.

Lists in MELT are not just pairs. A List is actually a structure keeping the first & the last pair of a linked list of pairs.

First, some fact about my implementation (available on GCC SubVersion repository in the MELT branch).

I'm working within GCC, closely following the trunk (future 4.4)

I have a runtime, which means a garbage collector & various primitives coded in C. See files gcc/basilys.c & gcc/basilys.h - it is debugged well enough to be able to run many minutes. (BTW debugging a garbage collector is a nightmare). MELT garbage collector is built above the existing GGC collector in GCC.

I have a cold translator, coded in Common Lisp (CLISP actually). File contrib/cold-basilys.lisp. It is able to translate some MELT code *.bysl into *.c ; I do know it is buggy, but I want to maintain it as little as possible. Conceptually the only purpose of this cold translator is to be able to handle warm-basilys.bysl below

The real stuff is the warm translator, in file gcc/melt/warm-basilys.bysl it is translated by CLISP running cold-basilys.lisp to coldbuilt-warm-basilys.c & (a plugin dynamically loaded by my cc1 - the C compiler proper of gcc).

my cc1 with the above generated is able to translate (except bugs) any *.bysl file into *.c (so it does the same work as cold-basilys.lisp, but in principle better, and coded in MELT). in particular it is able to translate itself, ie warm-basilys.bysl into warm-basilys-1.c etc..

my cc1 with is able to generate warm-basilys-2.c from the same warm-basilys.bysl. Sadly, warm-basilys-2.c is not the same as warm-basilys-1.c (it should)

my cc1 with produces warm-basilys-3.c from warm-basilys.bysl. warm-basilys-2.c & warm-basilys-3.c are identical (but buggy).

The buggy bootstrap (with warm-basilys-2 & warm-basilys-3 identical but buggy) actually happenned in svn rev135845

I am chasing a meta-bug, in the following sense.. The function pairlist_to_multiple in warm-basilys.bysl near line 2183 is incorrectly translated by warm-basilys.bysl (actually by - founding that one of the badly translated function is this one is non trivial. It behaves differently in (works ok there) and in (incorrectly returns nil).

I am experimenting that chasing metabug is challenging, and quite difficult.

Do you have horror stories, hints, insights, theoretical papers, personal experiences, about these?

How do you find such metabugs? (it is meta in the sense that the generated code behave wrongly).


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Code generation woes

Whenever I do code generation I try to follow a example driven approach. I create a set of generated files manually, write the source that generates them and keep forcing the compiler to reproduce the expected files in a byte exactly form. I use these as functional tests for the compiler, but I keep this kind of thing too when I find bugs as regression tests (i.e. I get the incorrect generated code, manually correct it and use as a unit test). Another thing to keep track too is having static analysis of the AST, so even if the language don't support full static checking we can check many interesting properties in a simple fashion, usually invariants that the compiler should follow. It's a good exercise to find the invariants that certain optimizations should ensure and keep track of them using assertions in the compiler, usually the cost (in time) of checking them is small enough to not matter. Finally I try to exercise the generated code with unit testing, keeping found bugs as regression tests.

bug solved.

Thanks to the help, the bug was solved.

Bug solved.

Thnaks to the help the bug was solved.