diff options
Diffstat (limited to 'lisp/emacs-lisp/bytecomp.el')
| -rw-r--r-- | lisp/emacs-lisp/bytecomp.el | 265 |
1 files changed, 226 insertions, 39 deletions
diff --git a/lisp/emacs-lisp/bytecomp.el b/lisp/emacs-lisp/bytecomp.el index 09ea7206d6e..75e6b904aa6 100644 --- a/lisp/emacs-lisp/bytecomp.el +++ b/lisp/emacs-lisp/bytecomp.el @@ -223,6 +223,11 @@ This includes variable references and calls to functions such as `car'." :group 'bytecomp :type 'boolean) +(defcustom byte-compile-cond-use-jump-table t + "Compile `cond' clauses to a jump table implementation (using a hash-table)." + :group 'bytecomp + :type 'boolean) + (defvar byte-compile-dynamic nil "If non-nil, compile function bodies so they load lazily. They are hidden in comments in the compiled file, @@ -412,6 +417,8 @@ specify different fields to sort on." (const calls+callers) (const nil))) (defvar byte-compile-debug nil) +(defvar byte-compile-jump-tables nil + "List of all jump tables used during compilation of this form.") (defvar byte-compile-constants nil "List of all constants encountered during compilation of this form.") (defvar byte-compile-variables nil @@ -747,6 +754,10 @@ otherwise pop it") ;; `byte-compile-lapcode'). (defconst byte-discardN-preserve-tos byte-discardN) +(byte-defop 183 -2 byte-switch + "to take a hash table and a value from the stack, and jump to the address +the value maps to, if any.") + ;; unused: 182-191 (byte-defop 192 1 byte-constant "for reference to a constant") @@ -823,7 +834,7 @@ CONST2 may be evaluated multiple times." op off ; Operation & offset opcode ; numeric value of OP (bytes '()) ; Put the output bytes here - (patchlist nil)) ; List of gotos to patch + (patchlist nil)) ; List of gotos to patch (dolist (lap-entry lap) (setq op (car lap-entry) off (cdr lap-entry)) @@ -905,6 +916,12 @@ CONST2 may be evaluated multiple times." ;; FIXME: Replace this by some workaround. (if (> (car bytes-tail) 255) (error "Bytecode overflow"))) + (dolist (hash-table byte-compile-jump-tables) + (maphash #'(lambda (value tag) + (setq pc (cadr tag)) + (puthash value (+ (logand pc 255) (lsh (lsh pc -8) 8)) + hash-table)) + hash-table)) (apply 'unibyte-string (nreverse bytes)))) @@ -1954,7 +1971,8 @@ With argument ARG, insert value in current buffer after the form." ;; (edebug-all-defs nil) ;; (edebug-all-forms nil) ;; Simulate entry to byte-compile-top-level - (byte-compile-constants nil) + (byte-compile-jump-tables nil) + (byte-compile-constants nil) (byte-compile-variables nil) (byte-compile-tag-number 0) (byte-compile-depth 0) @@ -2250,7 +2268,8 @@ list that represents a doc string reference. byte-compile-variables nil byte-compile-depth 0 byte-compile-maxdepth 0 - byte-compile-output nil)))) + byte-compile-output nil + byte-compile-jump-tables nil)))) (defvar byte-compile-force-lexical-warnings nil) @@ -2862,7 +2881,8 @@ for symbols generated by the byte compiler itself." (byte-compile-maxdepth 0) (byte-compile--lexical-environment lexenv) (byte-compile-reserved-constants (or reserved-csts 0)) - (byte-compile-output nil)) + (byte-compile-output nil) + (byte-compile-jump-tables nil)) (if (memq byte-optimize '(t source)) (setq form (byte-optimize-form form byte-compile--for-effect))) (while (and (eq (car-safe form) 'progn) (null (cdr (cdr form)))) @@ -3114,15 +3134,57 @@ for symbols generated by the byte compiler itself." ;; happens to be true for byte-code generated by bytecomp.el without ;; lexical-binding, but it's not true in general, and it's not true for ;; code output by bytecomp.el with lexical-binding. - (let ((endtag (byte-compile-make-tag))) + ;; We also restore the value of `byte-compile-depth' and remove TAG depths + ;; accordingly when inlining lapcode containing lap-code, exactly as + ;; documented in `byte-compile-cond-jump-table'. + (let ((endtag (byte-compile-make-tag)) + last-jump-tag ;; last TAG we have jumped to + last-depth ;; last value of `byte-compile-depth' + last-constant ;; value of the last constant encountered + last-switch ;; whether the last op encountered was byte-switch + switch-tags ;; a list of tags that byte-switch could jump to + ;; a list of tags byte-switch will jump to, if the value doesn't + ;; match any entry in the hash table + switch-default-tags) (dolist (op lap) (cond - ((eq (car op) 'TAG) (byte-compile-out-tag op)) - ((memq (car op) byte-goto-ops) (byte-compile-goto (car op) (cdr op))) + ((eq (car op) 'TAG) + (when (or (member op switch-tags) (member op switch-default-tags)) + ;; This TAG is used in a jump table, this means the last goto + ;; was to a done/default TAG, and thus it's cddr should be set to nil. + (when last-jump-tag + (setcdr (cdr last-jump-tag) nil)) + ;; Also, restore the value of `byte-compile-depth' to what it was + ;; before the last goto. + (setq byte-compile-depth last-depth + last-jump-tag nil)) + (byte-compile-out-tag op)) + ((memq (car op) byte-goto-ops) + (setq last-depth byte-compile-depth + last-jump-tag (cdr op)) + (byte-compile-goto (car op) (cdr op)) + (when last-switch + ;; The last op was byte-switch, this goto jumps to a "default" TAG + ;; (when no value in the jump table is satisfied). + (push (cdr op) switch-default-tags) + (setcdr (cdr (cdr op)) nil) + (setq byte-compile-depth last-depth + last-switch nil))) ((eq (car op) 'byte-return) (byte-compile-discard (- byte-compile-depth end-depth) t) (byte-compile-goto 'byte-goto endtag)) - (t (byte-compile-out (car op) (cdr op))))) + (t + (when (eq (car op) 'byte-switch) + ;; The last constant is a jump table. + (push last-constant byte-compile-jump-tables) + (setq last-switch t) + ;; Push all TAGs in the jump to switch-tags. + (maphash #'(lambda (_k tag) + (push tag switch-tags)) + last-constant)) + (setq last-constant (and (eq (car op) 'byte-constant) (cadr op))) + (setq last-depth byte-compile-depth) + (byte-compile-out (car op) (cdr op))))) (byte-compile-out-tag endtag))) (defun byte-compile-unfold-bcf (form) @@ -3951,37 +4013,162 @@ that suppresses all warnings during execution of BODY." (byte-compile-out-tag donetag)))) (setq byte-compile--for-effect nil)) +(defun byte-compile-cond-vars (obj1 obj2) + ;; We make sure that of OBJ1 and OBJ2, one of them is a symbol, + ;; and the other is a constant expression whose value can be + ;; compared with `eq' (with `macroexp-const-p'). + (or + (and (symbolp obj1) (macroexp-const-p obj2) (cons obj1 obj2)) + (and (symbolp obj2) (macroexp-const-p obj1) (cons obj2 obj1)))) + +(defun byte-compile-cond-jump-table-info (clauses) + "If CLAUSES is a `cond' form where: +The condition for each clause is of the form (TEST VAR VALUE). +VAR is a variable. +TEST and VAR are the same throughout all conditions. +VALUE satisfies `macroexp-const-p'. + +Return a list of the form ((TEST . VAR) ((VALUE BODY) ...))" + (let ((cases '()) + (ok t) + prev-var prev-test) + (and (catch 'break + (dolist (clause (cdr clauses) ok) + (let* ((condition (car clause)) + (test (car-safe condition)) + (vars (when (consp condition) + (byte-compile-cond-vars (cadr condition) (cl-caddr condition)))) + (obj1 (car-safe vars)) + (obj2 (cdr-safe vars)) + (body (cdr-safe clause))) + (unless prev-var + (setq prev-var obj1)) + (unless prev-test + (setq prev-test test)) + (if (and obj1 (memq test '(eq eql equal)) + (consp condition) + (eq test prev-test) + (eq obj1 prev-var) + ;; discard duplicate clauses + (not (assq obj2 cases))) + (push (list (if (consp obj2) (eval obj2) obj2) body) cases) + (if (eq condition t) + (progn (push (list 'default body) cases) + (throw 'break t)) + (setq ok nil) + (throw 'break nil)))))) + (list (cons prev-test prev-var) (nreverse cases))))) + +(defun byte-compile-cond-jump-table (clauses) + (let* ((table-info (byte-compile-cond-jump-table-info clauses)) + (test (caar table-info)) + (var (cdar table-info)) + (cases (cadr table-info)) + jump-table test-obj body tag donetag default-tag default-case) + (when (and cases (not (= (length cases) 1))) + ;; TODO: Once :linear-search is implemented for `make-hash-table' + ;; set it to `t' for cond forms with a small number of cases. + (setq jump-table (make-hash-table :test test + :purecopy t + :size (if (assq 'default cases) + (1- (length cases)) + (length cases))) + default-tag (byte-compile-make-tag) + donetag (byte-compile-make-tag)) + ;; The structure of byte-switch code: + ;; + ;; varref var + ;; constant #s(hash-table purecopy t data (val1 (TAG1) val2 (TAG2))) + ;; switch + ;; goto DEFAUT-TAG + ;; TAG1 + ;; <clause body> + ;; goto DONETAG + ;; TAG2 + ;; <clause body> + ;; goto DONETAG + ;; DEFAULT-TAG + ;; <body for `t' clause, if any (else `constant nil')> + ;; DONETAG + + (byte-compile-variable-ref var) + (byte-compile-push-constant jump-table) + (byte-compile-out 'byte-switch) + + ;; When the opcode argument is `byte-goto', `byte-compile-goto' sets + ;; `byte-compile-depth' to `nil'. However, we need `byte-compile-depth' + ;; to be non-nil for generating tags for all cases. Since + ;; `byte-compile-depth' will increase by atmost 1 after compiling + ;; all of the clause (which is further enforced by cl-assert below) + ;; it should be safe to preserve it's value. + (let ((byte-compile-depth byte-compile-depth)) + (byte-compile-goto 'byte-goto default-tag)) + + (when (assq 'default cases) + (setq default-case (cadr (assq 'default cases)) + cases (butlast cases 1))) + + (dolist (case cases) + (setq tag (byte-compile-make-tag) + test-obj (nth 0 case) + body (nth 1 case)) + (byte-compile-out-tag tag) + (puthash test-obj tag jump-table) + + (let ((byte-compile-depth byte-compile-depth) + (init-depth byte-compile-depth)) + ;; Since `byte-compile-body' might increase `byte-compile-depth' + ;; by 1, not preserving it's value will cause it to potentially + ;; increase by one for every clause body compiled, causing + ;; depth/tag conflicts or violating asserts down the road. + ;; To make sure `byte-compile-body' itself doesn't violate this, + ;; we use `cl-assert'. + (byte-compile-body body byte-compile--for-effect) + (cl-assert (or (= byte-compile-depth init-depth) + (= byte-compile-depth (1+ init-depth)))) + (byte-compile-goto 'byte-goto donetag) + (setcdr (cdr donetag) nil))) + + (byte-compile-out-tag default-tag) + (if default-case + (byte-compile-body-do-effect default-case) + (byte-compile-constant nil)) + (byte-compile-out-tag donetag) + (push jump-table byte-compile-jump-tables)))) + (defun byte-compile-cond (clauses) - (let ((donetag (byte-compile-make-tag)) - nexttag clause) - (while (setq clauses (cdr clauses)) - (setq clause (car clauses)) - (cond ((or (eq (car clause) t) - (and (eq (car-safe (car clause)) 'quote) - (car-safe (cdr-safe (car clause))))) - ;; Unconditional clause - (setq clause (cons t clause) - clauses nil)) - ((cdr clauses) - (byte-compile-form (car clause)) - (if (null (cdr clause)) - ;; First clause is a singleton. - (byte-compile-goto-if t byte-compile--for-effect donetag) - (setq nexttag (byte-compile-make-tag)) - (byte-compile-goto 'byte-goto-if-nil nexttag) - (byte-compile-maybe-guarded (car clause) - (byte-compile-body (cdr clause) byte-compile--for-effect)) - (byte-compile-goto 'byte-goto donetag) - (byte-compile-out-tag nexttag))))) - ;; Last clause - (let ((guard (car clause))) - (and (cdr clause) (not (eq guard t)) - (progn (byte-compile-form guard) - (byte-compile-goto-if nil byte-compile--for-effect donetag) - (setq clause (cdr clause)))) - (byte-compile-maybe-guarded guard - (byte-compile-body-do-effect clause))) - (byte-compile-out-tag donetag))) + (or (and byte-compile-cond-use-jump-table + (byte-compile-cond-jump-table clauses)) + (let ((donetag (byte-compile-make-tag)) + nexttag clause) + (while (setq clauses (cdr clauses)) + (setq clause (car clauses)) + (cond ((or (eq (car clause) t) + (and (eq (car-safe (car clause)) 'quote) + (car-safe (cdr-safe (car clause))))) + ;; Unconditional clause + (setq clause (cons t clause) + clauses nil)) + ((cdr clauses) + (byte-compile-form (car clause)) + (if (null (cdr clause)) + ;; First clause is a singleton. + (byte-compile-goto-if t byte-compile--for-effect donetag) + (setq nexttag (byte-compile-make-tag)) + (byte-compile-goto 'byte-goto-if-nil nexttag) + (byte-compile-maybe-guarded (car clause) + (byte-compile-body (cdr clause) byte-compile--for-effect)) + (byte-compile-goto 'byte-goto donetag) + (byte-compile-out-tag nexttag))))) + ;; Last clause + (let ((guard (car clause))) + (and (cdr clause) (not (eq guard t)) + (progn (byte-compile-form guard) + (byte-compile-goto-if nil byte-compile--for-effect donetag) + (setq clause (cdr clause)))) + (byte-compile-maybe-guarded guard + (byte-compile-body-do-effect clause))) + (byte-compile-out-tag donetag)))) (defun byte-compile-and (form) (let ((failtag (byte-compile-make-tag)) @@ -4528,7 +4715,7 @@ binding slots have been popped." (and byte-compile-depth (not (= (cdr (cdr tag)) byte-compile-depth)) (error "Compiler bug: depth conflict at tag %d" (car (cdr tag)))) - (setq byte-compile-depth (cdr (cdr tag)))) + (setq byte-compile-depth (cdr (cdr tag)))) (setcdr (cdr tag) byte-compile-depth))) (defun byte-compile-goto (opcode tag) |