File: byte-opt.el.html

========================================================================
"No matter how hard you try, you can't make a racehorse out of a pig.
You can, however, make a faster pig."

Or, to put it another way, the Emacs byte compiler is a VW Bug. This code makes it be a VW Bug with fuel injection and a turbocharger... You're still not going to make it go faster than 70 mph, but it might be easier to get it there.

TO DO:

(apply (lambda (x &rest y) ...) 1 (foo))

maintain a list of functions known not to access any global variables
(actually, give them a 'dynamically-safe property) and then
  (let ( v1 v2 ... vM vN ) <...dynamically-safe...> ) ==>
  (let ( v1 v2 ... vM ) vN <...dynamically-safe...> )
by recursing on this, we might be able to eliminate the entire let. However certain variables should never have their bindings optimized away, because they affect everything.
  (put 'debug-on-error 'binding-is-magic t)
  (put 'debug-on-abort 'binding-is-magic t)
  (put 'debug-on-next-call 'binding-is-magic t)
  (put 'inhibit-quit 'binding-is-magic t)
  (put 'quit-flag 'binding-is-magic t)
  (put 't 'binding-is-magic t)
  (put 'nil 'binding-is-magic t)
possibly also
  (put 'gc-cons-threshold 'binding-is-magic t)
  (put 'track-mouse 'binding-is-magic t)
others?

Simple defsubsts often produce forms like
   (let ((v1 (f1)) (v2 (f2)) ...)
      (FN v1 v2 ...))
It would be nice if we could optimize this to
   (FN (f1) (f2) ...)
but we can't unless FN is dynamically-safe (it might be dynamically referring to the bindings that the lambda arglist established.) One of the uncountable lossages introduced by dynamic scope...

Maybe there should be a control-structure that says "turn on
fast-and-loose type-assumptive optimizations here." Then when
we see a form like (car foo) we can from then on assume that the variable foo is of type cons, and optimize based on that. But, this won't win much because of (you guessed it) dynamic scope. Anything down the stack could change the value.
(Another reason it doesn't work is that it is perfectly valid
to call car with a null argument.) A better approach might
be to allow type-specification of the form
  (put 'foo 'arg-types '(float (list integer) dynamic))
  (put 'foo 'result-type 'bool)
It should be possible to have these types checked to a certain degree.

collapse common subexpressions

It would be nice if redundant sequences could be factored out as well, when they are known to have no side-effects:
  (list (+ a b c) (+ a b c)) --> a b add c add dup list-2
but beware of traps like
  (cons (list x y) (list x y))

Tail-recursion elimination is not really possible in Emacs Lisp. Tail-recursion elimination is almost always impossible when all variables have dynamic scope, but given that the "return" byteop requires the binding stack to be empty (rather than emptying it itself), there can be no truly tail-recursive Emacs Lisp functions that take any arguments or make any bindings.

Here is an example of an Emacs Lisp function which could safely be byte-compiled tail-recursively:

 (defun tail-map (fn list)
   (cond (list
          (funcall fn (car list))
          (tail-map fn (cdr list)))))

However, if there was even a single let-binding around the COND, it could not be byte-compiled, because there would be an "unbind"
byte-op between the final "call" and "return." Adding a
Bunbind_all byteop would fix this.

  (defun foo (x y z) ... (foo a b c))
  ... (const foo) (varref a) (varref b) (varref c) (call 3) END: (return)
  ... (varref a) (varbind x) (varref b) (varbind y) (varref c) (varbind z) (goto 0) END: (unbind-all) (return)
  ... (varref a) (varset x) (varref b) (varset y) (varref c) (varset z) (goto 0) END: (return)

this also can be considered tail recursion:

  ... (const foo) (varref a) (call 1) (goto X) ... X: (return)
could generalize this by doing the optimization
  (goto X) ... X: (return) --> (return)

But this doesn't solve all of the problems: although by doing tail- recursion elimination in this way, the call-stack does not grow, the binding-stack would grow with each recursive step, and would eventually overflow. I don't believe there is any way around this without lexical scope.

Wouldn't it be nice if Emacs Lisp had lexical scope.

Idea: the form (lexical-scope) in a file means that the file may be compiled lexically. This proclamation is file-local. Then, within that file, "let" would establish lexical bindings, and "let-dynamic" would do things the old way. (Or we could use CL "declare" forms.) We'd have to notice defvars and defconsts, since those variables should always be dynamic, and attempting to do a lexical binding of them should simply do a dynamic binding instead.
But! We need to know about variables that were not necessarily defvared
in the file being compiled (doing a boundp check isn't good enough.) Fdefvar() would have to be modified to add something to the plist.

A major disadvantage of this scheme is that the interpreter and compiler would have different semantics for files compiled with (dynamic-scope). Since this would be a file-local optimization, there would be no way to modify the interpreter to obey this (unless the loader was hacked in some grody way, but that's a really bad idea.)

Other things to consider:

;; Associative math should recognize subcalls to identical function:
(disassemble (lambda (x) (+ (+ (foo) 1) (+ (bar) 2))))
;; This should generate the same as (1+ x) and (1- x)

(disassemble (lambda (x) (cons (+ x 1) (- x 1))))
;; An awful lot of functions always return a non-nil value. If they're
;; error free also they may act as true-constants.

(disassemble (lambda (x) (and (point) (foo))))
;; When
;; - all but one arguments to a function are constant
;; - the non-constant argument is an if-expression (cond-expression?)
;; then the outer function can be distributed. If the guarding
;; condition is side-effect-free [assignment-free] then the other
;; arguments may be any expressions. Since, however, the code size
;; can increase this way they should be "simple". Compare:

(disassemble (lambda (x) (eq (if (point) 'a 'b) 'c)))
(disassemble (lambda (x) (if (point) (eq 'a 'c) (eq 'b 'c))))

;; (car (cons A B)) -> (prog1 A B)
(disassemble (lambda (x) (car (cons (foo) 42))))

;; (cdr (cons A B)) -> (progn A B)
(disassemble (lambda (x) (cdr (cons 42 (foo)))))

;; (car (list A B ...)) -> (prog1 A B ...)
(disassemble (lambda (x) (car (list (foo) 42 (bar)))))

;; (cdr (list A B ...)) -> (progn A (list B ...))
(disassemble (lambda (x) (cdr (list 42 (foo) (bar)))))

Defined variables (6)

Defined functions (51)

Defined faces (0)