Alternative code generation backend

[quasilyte]

Proposal: use Emacs Lisp as main output format (instead of lapcode).

Known advantages:

• simpler to debug
• easier to edit by hand (if you do not have Go sources)

Known disadvantages:

• resulting bytecode is sub-optimal due to many reasons
• some features (like goto) are harder to implement on Lisp Level.

Potential solution to those disadvantages: Write alternative Emacs Lisp compiler or complement existing compiler in the way that makes possible to produce efficient code out of the lisp.

The extended Emacs Lisp is a language that is understood by the new compiler. Extended Emacs Lisp adds some special forms that are required for efficient Go mapping. Special form return must translate directly to return opcode.

Because IR is about to be re-written anyway (#47), maybe it is about right time to think about this one seriously.

[quasilyte]

At this stage, minimal proof of concept implementation is needed.

[quasilyte]

To simplify code generation layer, coupling between ir/compiler and sexpconv has been increased in the past. AST mappers know about backend and its instruction set.

Such coupling makes it harder to add a new compilation target.

[quasilyte]

I think I have it.

1) Teach byte-compile-form new forms:

(defadvice byte-compile-form (around plugin activate)
  (setq ad-return-value
        (pcase form
          (`(%return ,v)
           (byte-compile-form v)
           (byte-compile-out 'byte-return 0))
          (`(%label ,name)
           (push (xbyte-tag-ref name)
                 byte-compile-output))
          (`(%goto ,name)
           (push (cons 'byte-goto (xbyte-tag-ref name))
                 byte-compile-output))
          (_
           ad-do-it))))

2) As seen above, xbyte-tag-ref function is needed:

(defvar xbyte-tags (make-hash-table :test #'eq))
(defun xbyte-tag-ref (name)
  (or (gethash name xbyte-tags)
      (puthash name (byte-compile-make-tag) xbyte-tags)))

3) xbyte-tags needs to be cleared between byte-compile calls. To avoid another defadvice, simple wrapper can be used:

(defun xbyte-compile (form)
  (clrhash xbyte-tags)
  (byte-compile form))

Now we are ready to roll!

(let ((byte-optimize nil)
      (lexical-binding t))
  (disassemble
   (xbyte-compile
    (lambda (x)
      (%goto foo)
      (setq x 10)
      (%label foo)))))
=>
;;0       goto      1
;;3       constant  10
;;4       stack-set 1
;;6:1     return    

(let ((byte-optimize nil)
      (lexical-binding t))
  (disassemble
   (xbyte-compile
    (lambda (x)
      (when (= x 0)
        (%return "zero!"))
      x))))
=>
;;0       dup       
;;1       constant  0
;;2       eqlsign   
;;3       goto-if-nil 1
;;6       constant  "zero!"
;;7       return    
;;8:1     dup       
;;9       return    

Yup, goto and procedure-style return inside Emacs Lisp.

%return, %label and %goto are not real functions, more like some kind of intrinsics understood by patched Emacs Lisp compiler.

With these new intrinsics, it is possible to achieve good performance while using S-expressions format as an output.

[quasilyte]

goto must emit discardN where N depends on the jump target. This is needed to avoid execution stack corruption.

79

[quasilyte]

Multiple backends (and their mid-ends) are far easier to achieve thanks to big refactoring. 1aa43965c71abce28cec467c9b3cab0838d38332 has working IR-based (lapcode) backend. Next step is to make backend selection via translate_package tool possible.

[quasilyte]

The code above with defalias is awful. More reliable way is described here: Writing Emacs Lisp compiler intrinsics.