1;;; byte-opt.el --- the optimization passes of the emacs-lisp byte compiler 2 3;; Copyright (C) 1991, 1994, 2000, 2001, 2002, 2003, 2004, 4;; 2005, 2006, 2007 Free Software Foundation, Inc. 5 6;; Author: Jamie Zawinski <jwz@lucid.com> 7;; Hallvard Furuseth <hbf@ulrik.uio.no> 8;; Maintainer: FSF 9;; Keywords: internal 10 11;; This file is part of GNU Emacs. 12 13;; GNU Emacs is free software; you can redistribute it and/or modify 14;; it under the terms of the GNU General Public License as published by 15;; the Free Software Foundation; either version 2, or (at your option) 16;; any later version. 17 18;; GNU Emacs is distributed in the hope that it will be useful, 19;; but WITHOUT ANY WARRANTY; without even the implied warranty of 20;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21;; GNU General Public License for more details. 22 23;; You should have received a copy of the GNU General Public License 24;; along with GNU Emacs; see the file COPYING. If not, write to the 25;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 26;; Boston, MA 02110-1301, USA. 27 28;;; Commentary: 29 30;; ======================================================================== 31;; "No matter how hard you try, you can't make a racehorse out of a pig. 32;; You can, however, make a faster pig." 33;; 34;; Or, to put it another way, the emacs byte compiler is a VW Bug. This code 35;; makes it be a VW Bug with fuel injection and a turbocharger... You're 36;; still not going to make it go faster than 70 mph, but it might be easier 37;; to get it there. 38;; 39 40;; TO DO: 41;; 42;; (apply (lambda (x &rest y) ...) 1 (foo)) 43;; 44;; maintain a list of functions known not to access any global variables 45;; (actually, give them a 'dynamically-safe property) and then 46;; (let ( v1 v2 ... vM vN ) <...dynamically-safe...> ) ==> 47;; (let ( v1 v2 ... vM ) vN <...dynamically-safe...> ) 48;; by recursing on this, we might be able to eliminate the entire let. 49;; However certain variables should never have their bindings optimized 50;; away, because they affect everything. 51;; (put 'debug-on-error 'binding-is-magic t) 52;; (put 'debug-on-abort 'binding-is-magic t) 53;; (put 'debug-on-next-call 'binding-is-magic t) 54;; (put 'inhibit-quit 'binding-is-magic t) 55;; (put 'quit-flag 'binding-is-magic t) 56;; (put 't 'binding-is-magic t) 57;; (put 'nil 'binding-is-magic t) 58;; possibly also 59;; (put 'gc-cons-threshold 'binding-is-magic t) 60;; (put 'track-mouse 'binding-is-magic t) 61;; others? 62;; 63;; Simple defsubsts often produce forms like 64;; (let ((v1 (f1)) (v2 (f2)) ...) 65;; (FN v1 v2 ...)) 66;; It would be nice if we could optimize this to 67;; (FN (f1) (f2) ...) 68;; but we can't unless FN is dynamically-safe (it might be dynamically 69;; referring to the bindings that the lambda arglist established.) 70;; One of the uncountable lossages introduced by dynamic scope... 71;; 72;; Maybe there should be a control-structure that says "turn on 73;; fast-and-loose type-assumptive optimizations here." Then when 74;; we see a form like (car foo) we can from then on assume that 75;; the variable foo is of type cons, and optimize based on that. 76;; But, this won't win much because of (you guessed it) dynamic 77;; scope. Anything down the stack could change the value. 78;; (Another reason it doesn't work is that it is perfectly valid 79;; to call car with a null argument.) A better approach might 80;; be to allow type-specification of the form 81;; (put 'foo 'arg-types '(float (list integer) dynamic)) 82;; (put 'foo 'result-type 'bool) 83;; It should be possible to have these types checked to a certain 84;; degree. 85;; 86;; collapse common subexpressions 87;; 88;; It would be nice if redundant sequences could be factored out as well, 89;; when they are known to have no side-effects: 90;; (list (+ a b c) (+ a b c)) --> a b add c add dup list-2 91;; but beware of traps like 92;; (cons (list x y) (list x y)) 93;; 94;; Tail-recursion elimination is not really possible in Emacs Lisp. 95;; Tail-recursion elimination is almost always impossible when all variables 96;; have dynamic scope, but given that the "return" byteop requires the 97;; binding stack to be empty (rather than emptying it itself), there can be 98;; no truly tail-recursive Emacs Lisp functions that take any arguments or 99;; make any bindings. 100;; 101;; Here is an example of an Emacs Lisp function which could safely be 102;; byte-compiled tail-recursively: 103;; 104;; (defun tail-map (fn list) 105;; (cond (list 106;; (funcall fn (car list)) 107;; (tail-map fn (cdr list))))) 108;; 109;; However, if there was even a single let-binding around the COND, 110;; it could not be byte-compiled, because there would be an "unbind" 111;; byte-op between the final "call" and "return." Adding a 112;; Bunbind_all byteop would fix this. 113;; 114;; (defun foo (x y z) ... (foo a b c)) 115;; ... (const foo) (varref a) (varref b) (varref c) (call 3) END: (return) 116;; ... (varref a) (varbind x) (varref b) (varbind y) (varref c) (varbind z) (goto 0) END: (unbind-all) (return) 117;; ... (varref a) (varset x) (varref b) (varset y) (varref c) (varset z) (goto 0) END: (return) 118;; 119;; this also can be considered tail recursion: 120;; 121;; ... (const foo) (varref a) (call 1) (goto X) ... X: (return) 122;; could generalize this by doing the optimization 123;; (goto X) ... X: (return) --> (return) 124;; 125;; But this doesn't solve all of the problems: although by doing tail- 126;; recursion elimination in this way, the call-stack does not grow, the 127;; binding-stack would grow with each recursive step, and would eventually 128;; overflow. I don't believe there is any way around this without lexical 129;; scope. 130;; 131;; Wouldn't it be nice if Emacs Lisp had lexical scope. 132;; 133;; Idea: the form (lexical-scope) in a file means that the file may be 134;; compiled lexically. This proclamation is file-local. Then, within 135;; that file, "let" would establish lexical bindings, and "let-dynamic" 136;; would do things the old way. (Or we could use CL "declare" forms.) 137;; We'd have to notice defvars and defconsts, since those variables should 138;; always be dynamic, and attempting to do a lexical binding of them 139;; should simply do a dynamic binding instead. 140;; But! We need to know about variables that were not necessarily defvarred 141;; in the file being compiled (doing a boundp check isn't good enough.) 142;; Fdefvar() would have to be modified to add something to the plist. 143;; 144;; A major disadvantage of this scheme is that the interpreter and compiler 145;; would have different semantics for files compiled with (dynamic-scope). 146;; Since this would be a file-local optimization, there would be no way to 147;; modify the interpreter to obey this (unless the loader was hacked 148;; in some grody way, but that's a really bad idea.) 149 150;; Other things to consider: 151 152;; ;; Associative math should recognize subcalls to identical function: 153;; (disassemble (lambda (x) (+ (+ (foo) 1) (+ (bar) 2)))) 154;; ;; This should generate the same as (1+ x) and (1- x) 155 156;; (disassemble (lambda (x) (cons (+ x 1) (- x 1)))) 157;; ;; An awful lot of functions always return a non-nil value. If they're 158;; ;; error free also they may act as true-constants. 159 160;; (disassemble (lambda (x) (and (point) (foo)))) 161;; ;; When 162;; ;; - all but one arguments to a function are constant 163;; ;; - the non-constant argument is an if-expression (cond-expression?) 164;; ;; then the outer function can be distributed. If the guarding 165;; ;; condition is side-effect-free [assignment-free] then the other 166;; ;; arguments may be any expressions. Since, however, the code size 167;; ;; can increase this way they should be "simple". Compare: 168 169;; (disassemble (lambda (x) (eq (if (point) 'a 'b) 'c))) 170;; (disassemble (lambda (x) (if (point) (eq 'a 'c) (eq 'b 'c)))) 171 172;; ;; (car (cons A B)) -> (prog1 A B) 173;; (disassemble (lambda (x) (car (cons (foo) 42)))) 174 175;; ;; (cdr (cons A B)) -> (progn A B) 176;; (disassemble (lambda (x) (cdr (cons 42 (foo))))) 177 178;; ;; (car (list A B ...)) -> (prog1 A B ...) 179;; (disassemble (lambda (x) (car (list (foo) 42 (bar))))) 180 181;; ;; (cdr (list A B ...)) -> (progn A (list B ...)) 182;; (disassemble (lambda (x) (cdr (list 42 (foo) (bar))))) 183 184 185;;; Code: 186 187(require 'bytecomp) 188 189(defun byte-compile-log-lap-1 (format &rest args) 190 (if (aref byte-code-vector 0) 191 (error "The old version of the disassembler is loaded. Reload new-bytecomp as well")) 192 (byte-compile-log-1 193 (apply 'format format 194 (let (c a) 195 (mapcar (lambda (arg) 196 (if (not (consp arg)) 197 (if (and (symbolp arg) 198 (string-match "^byte-" (symbol-name arg))) 199 (intern (substring (symbol-name arg) 5)) 200 arg) 201 (if (integerp (setq c (car arg))) 202 (error "non-symbolic byte-op %s" c)) 203 (if (eq c 'TAG) 204 (setq c arg) 205 (setq a (cond ((memq c byte-goto-ops) 206 (car (cdr (cdr arg)))) 207 ((memq c byte-constref-ops) 208 (car (cdr arg))) 209 (t (cdr arg)))) 210 (setq c (symbol-name c)) 211 (if (string-match "^byte-." c) 212 (setq c (intern (substring c 5))))) 213 (if (eq c 'constant) (setq c 'const)) 214 (if (and (eq (cdr arg) 0) 215 (not (memq c '(unbind call const)))) 216 c 217 (format "(%s %s)" c a)))) 218 args))))) 219 220(defmacro byte-compile-log-lap (format-string &rest args) 221 `(and (memq byte-optimize-log '(t byte)) 222 (byte-compile-log-lap-1 ,format-string ,@args))) 223 224 225;;; byte-compile optimizers to support inlining 226 227(put 'inline 'byte-optimizer 'byte-optimize-inline-handler) 228 229(defun byte-optimize-inline-handler (form) 230 "byte-optimize-handler for the `inline' special-form." 231 (cons 'progn 232 (mapcar 233 (lambda (sexp) 234 (let ((f (car-safe sexp))) 235 (if (and (symbolp f) 236 (or (cdr (assq f byte-compile-function-environment)) 237 (not (or (not (fboundp f)) 238 (cdr (assq f byte-compile-macro-environment)) 239 (and (consp (setq f (symbol-function f))) 240 (eq (car f) 'macro)) 241 (subrp f))))) 242 (byte-compile-inline-expand sexp) 243 sexp))) 244 (cdr form)))) 245 246 247;; Splice the given lap code into the current instruction stream. 248;; If it has any labels in it, you're responsible for making sure there 249;; are no collisions, and that byte-compile-tag-number is reasonable 250;; after this is spliced in. The provided list is destroyed. 251(defun byte-inline-lapcode (lap) 252 (setq byte-compile-output (nconc (nreverse lap) byte-compile-output))) 253 254(defun byte-compile-inline-expand (form) 255 (let* ((name (car form)) 256 (fn (or (cdr (assq name byte-compile-function-environment)) 257 (and (fboundp name) (symbol-function name))))) 258 (if (null fn) 259 (progn 260 (byte-compile-warn "attempt to inline `%s' before it was defined" 261 name) 262 form) 263 ;; else 264 (when (and (consp fn) (eq (car fn) 'autoload)) 265 (load (nth 1 fn)) 266 (setq fn (or (and (fboundp name) (symbol-function name)) 267 (cdr (assq name byte-compile-function-environment))))) 268 (if (and (consp fn) (eq (car fn) 'autoload)) 269 (error "File `%s' didn't define `%s'" (nth 1 fn) name)) 270 (if (and (symbolp fn) (not (eq fn t))) 271 (byte-compile-inline-expand (cons fn (cdr form))) 272 (if (byte-code-function-p fn) 273 (let (string) 274 (fetch-bytecode fn) 275 (setq string (aref fn 1)) 276 ;; Isn't it an error for `string' not to be unibyte?? --stef 277 (if (fboundp 'string-as-unibyte) 278 (setq string (string-as-unibyte string))) 279 (cons `(lambda ,(aref fn 0) 280 (byte-code ,string ,(aref fn 2) ,(aref fn 3))) 281 (cdr form))) 282 (if (eq (car-safe fn) 'lambda) 283 (cons fn (cdr form)) 284 ;; Give up on inlining. 285 form)))))) 286 287;; ((lambda ...) ...) 288(defun byte-compile-unfold-lambda (form &optional name) 289 (or name (setq name "anonymous lambda")) 290 (let ((lambda (car form)) 291 (values (cdr form))) 292 (if (byte-code-function-p lambda) 293 (setq lambda (list 'lambda (aref lambda 0) 294 (list 'byte-code (aref lambda 1) 295 (aref lambda 2) (aref lambda 3))))) 296 (let ((arglist (nth 1 lambda)) 297 (body (cdr (cdr lambda))) 298 optionalp restp 299 bindings) 300 (if (and (stringp (car body)) (cdr body)) 301 (setq body (cdr body))) 302 (if (and (consp (car body)) (eq 'interactive (car (car body)))) 303 (setq body (cdr body))) 304 (while arglist 305 (cond ((eq (car arglist) '&optional) 306 ;; ok, I'll let this slide because funcall_lambda() does... 307 ;; (if optionalp (error "multiple &optional keywords in %s" name)) 308 (if restp (error "&optional found after &rest in %s" name)) 309 (if (null (cdr arglist)) 310 (error "nothing after &optional in %s" name)) 311 (setq optionalp t)) 312 ((eq (car arglist) '&rest) 313 ;; ...but it is by no stretch of the imagination a reasonable 314 ;; thing that funcall_lambda() allows (&rest x y) and 315 ;; (&rest x &optional y) in arglists. 316 (if (null (cdr arglist)) 317 (error "nothing after &rest in %s" name)) 318 (if (cdr (cdr arglist)) 319 (error "multiple vars after &rest in %s" name)) 320 (setq restp t)) 321 (restp 322 (setq bindings (cons (list (car arglist) 323 (and values (cons 'list values))) 324 bindings) 325 values nil)) 326 ((and (not optionalp) (null values)) 327 (byte-compile-warn "attempt to open-code `%s' with too few arguments" name) 328 (setq arglist nil values 'too-few)) 329 (t 330 (setq bindings (cons (list (car arglist) (car values)) 331 bindings) 332 values (cdr values)))) 333 (setq arglist (cdr arglist))) 334 (if values 335 (progn 336 (or (eq values 'too-few) 337 (byte-compile-warn 338 "attempt to open-code `%s' with too many arguments" name)) 339 form) 340 341 ;; The following leads to infinite recursion when loading a 342 ;; file containing `(defsubst f () (f))', and then trying to 343 ;; byte-compile that file. 344 ;(setq body (mapcar 'byte-optimize-form body))) 345 346 (let ((newform 347 (if bindings 348 (cons 'let (cons (nreverse bindings) body)) 349 (cons 'progn body)))) 350 (byte-compile-log " %s\t==>\t%s" form newform) 351 newform))))) 352 353 354;;; implementing source-level optimizers 355 356(defun byte-optimize-form-code-walker (form for-effect) 357 ;; 358 ;; For normal function calls, We can just mapcar the optimizer the cdr. But 359 ;; we need to have special knowledge of the syntax of the special forms 360 ;; like let and defun (that's why they're special forms :-). (Actually, 361 ;; the important aspect is that they are subrs that don't evaluate all of 362 ;; their args.) 363 ;; 364 (let ((fn (car-safe form)) 365 tmp) 366 (cond ((not (consp form)) 367 (if (not (and for-effect 368 (or byte-compile-delete-errors 369 (not (symbolp form)) 370 (eq form t)))) 371 form)) 372 ((eq fn 'quote) 373 (if (cdr (cdr form)) 374 (byte-compile-warn "malformed quote form: `%s'" 375 (prin1-to-string form))) 376 ;; map (quote nil) to nil to simplify optimizer logic. 377 ;; map quoted constants to nil if for-effect (just because). 378 (and (nth 1 form) 379 (not for-effect) 380 form)) 381 ((or (byte-code-function-p fn) 382 (eq 'lambda (car-safe fn))) 383 (byte-compile-unfold-lambda form)) 384 ((memq fn '(let let*)) 385 ;; recursively enter the optimizer for the bindings and body 386 ;; of a let or let*. This for depth-firstness: forms that 387 ;; are more deeply nested are optimized first. 388 (cons fn 389 (cons 390 (mapcar (lambda (binding) 391 (if (symbolp binding) 392 binding 393 (if (cdr (cdr binding)) 394 (byte-compile-warn "malformed let binding: `%s'" 395 (prin1-to-string binding))) 396 (list (car binding) 397 (byte-optimize-form (nth 1 binding) nil)))) 398 (nth 1 form)) 399 (byte-optimize-body (cdr (cdr form)) for-effect)))) 400 ((eq fn 'cond) 401 (cons fn 402 (mapcar (lambda (clause) 403 (if (consp clause) 404 (cons 405 (byte-optimize-form (car clause) nil) 406 (byte-optimize-body (cdr clause) for-effect)) 407 (byte-compile-warn "malformed cond form: `%s'" 408 (prin1-to-string clause)) 409 clause)) 410 (cdr form)))) 411 ((eq fn 'progn) 412 ;; as an extra added bonus, this simplifies (progn <x>) --> <x> 413 (if (cdr (cdr form)) 414 (progn 415 (setq tmp (byte-optimize-body (cdr form) for-effect)) 416 (if (cdr tmp) (cons 'progn tmp) (car tmp))) 417 (byte-optimize-form (nth 1 form) for-effect))) 418 ((eq fn 'prog1) 419 (if (cdr (cdr form)) 420 (cons 'prog1 421 (cons (byte-optimize-form (nth 1 form) for-effect) 422 (byte-optimize-body (cdr (cdr form)) t))) 423 (byte-optimize-form (nth 1 form) for-effect))) 424 ((eq fn 'prog2) 425 (cons 'prog2 426 (cons (byte-optimize-form (nth 1 form) t) 427 (cons (byte-optimize-form (nth 2 form) for-effect) 428 (byte-optimize-body (cdr (cdr (cdr form))) t))))) 429 430 ((memq fn '(save-excursion save-restriction save-current-buffer)) 431 ;; those subrs which have an implicit progn; it's not quite good 432 ;; enough to treat these like normal function calls. 433 ;; This can turn (save-excursion ...) into (save-excursion) which 434 ;; will be optimized away in the lap-optimize pass. 435 (cons fn (byte-optimize-body (cdr form) for-effect))) 436 437 ((eq fn 'with-output-to-temp-buffer) 438 ;; this is just like the above, except for the first argument. 439 (cons fn 440 (cons 441 (byte-optimize-form (nth 1 form) nil) 442 (byte-optimize-body (cdr (cdr form)) for-effect)))) 443 444 ((eq fn 'if) 445 (when (< (length form) 3) 446 (byte-compile-warn "too few arguments for `if'")) 447 (cons fn 448 (cons (byte-optimize-form (nth 1 form) nil) 449 (cons 450 (byte-optimize-form (nth 2 form) for-effect) 451 (byte-optimize-body (nthcdr 3 form) for-effect))))) 452 453 ((memq fn '(and or)) ; remember, and/or are control structures. 454 ;; take forms off the back until we can't any more. 455 ;; In the future it could conceivably be a problem that the 456 ;; subexpressions of these forms are optimized in the reverse 457 ;; order, but it's ok for now. 458 (if for-effect 459 (let ((backwards (reverse (cdr form)))) 460 (while (and backwards 461 (null (setcar backwards 462 (byte-optimize-form (car backwards) 463 for-effect)))) 464 (setq backwards (cdr backwards))) 465 (if (and (cdr form) (null backwards)) 466 (byte-compile-log 467 " all subforms of %s called for effect; deleted" form)) 468 (and backwards 469 (cons fn (nreverse (mapcar 'byte-optimize-form backwards))))) 470 (cons fn (mapcar 'byte-optimize-form (cdr form))))) 471 472 ((eq fn 'interactive) 473 (byte-compile-warn "misplaced interactive spec: `%s'" 474 (prin1-to-string form)) 475 nil) 476 477 ((memq fn '(defun defmacro function 478 condition-case save-window-excursion)) 479 ;; These forms are compiled as constants or by breaking out 480 ;; all the subexpressions and compiling them separately. 481 form) 482 483 ((eq fn 'unwind-protect) 484 ;; the "protected" part of an unwind-protect is compiled (and thus 485 ;; optimized) as a top-level form, so don't do it here. But the 486 ;; non-protected part has the same for-effect status as the 487 ;; unwind-protect itself. (The protected part is always for effect, 488 ;; but that isn't handled properly yet.) 489 (cons fn 490 (cons (byte-optimize-form (nth 1 form) for-effect) 491 (cdr (cdr form))))) 492 493 ((eq fn 'catch) 494 ;; the body of a catch is compiled (and thus optimized) as a 495 ;; top-level form, so don't do it here. The tag is never 496 ;; for-effect. The body should have the same for-effect status 497 ;; as the catch form itself, but that isn't handled properly yet. 498 (cons fn 499 (cons (byte-optimize-form (nth 1 form) nil) 500 (cdr (cdr form))))) 501 502 ((eq fn 'ignore) 503 ;; Don't treat the args to `ignore' as being 504 ;; computed for effect. We want to avoid the warnings 505 ;; that might occur if they were treated that way. 506 ;; However, don't actually bother calling `ignore'. 507 `(prog1 nil . ,(mapcar 'byte-optimize-form (cdr form)))) 508 509 ;; If optimization is on, this is the only place that macros are 510 ;; expanded. If optimization is off, then macroexpansion happens 511 ;; in byte-compile-form. Otherwise, the macros are already expanded 512 ;; by the time that is reached. 513 ((not (eq form 514 (setq form (macroexpand form 515 byte-compile-macro-environment)))) 516 (byte-optimize-form form for-effect)) 517 518 ;; Support compiler macros as in cl.el. 519 ((and (fboundp 'compiler-macroexpand) 520 (symbolp (car-safe form)) 521 (get (car-safe form) 'cl-compiler-macro) 522 (not (eq form 523 (with-no-warnings 524 (setq form (compiler-macroexpand form)))))) 525 (byte-optimize-form form for-effect)) 526 527 ((not (symbolp fn)) 528 (byte-compile-warn "`%s' is a malformed function" 529 (prin1-to-string fn)) 530 form) 531 532 ((and for-effect (setq tmp (get fn 'side-effect-free)) 533 (or byte-compile-delete-errors 534 (eq tmp 'error-free) 535 ;; Detect the expansion of (pop foo). 536 ;; There is no need to compile the call to `car' there. 537 (and (eq fn 'car) 538 (eq (car-safe (cadr form)) 'prog1) 539 (let ((var (cadr (cadr form))) 540 (last (nth 2 (cadr form)))) 541 (and (symbolp var) 542 (null (nthcdr 3 (cadr form))) 543 (eq (car-safe last) 'setq) 544 (eq (cadr last) var) 545 (eq (car-safe (nth 2 last)) 'cdr) 546 (eq (cadr (nth 2 last)) var)))) 547 (progn 548 (byte-compile-warn "value returned from %s is unused" 549 (prin1-to-string form)) 550 nil))) 551 (byte-compile-log " %s called for effect; deleted" fn) 552 ;; appending a nil here might not be necessary, but it can't hurt. 553 (byte-optimize-form 554 (cons 'progn (append (cdr form) '(nil))) t)) 555 556 (t 557 ;; Otherwise, no args can be considered to be for-effect, 558 ;; even if the called function is for-effect, because we 559 ;; don't know anything about that function. 560 (let ((args (mapcar #'byte-optimize-form (cdr form)))) 561 (if (and (get fn 'pure) 562 (byte-optimize-all-constp args)) 563 (list 'quote (apply fn (mapcar #'eval args))) 564 (cons fn args))))))) 565 566(defun byte-optimize-all-constp (list) 567 "Non-nil iff all elements of LIST satisfy `byte-compile-constp'." 568 (let ((constant t)) 569 (while (and list constant) 570 (unless (byte-compile-constp (car list)) 571 (setq constant nil)) 572 (setq list (cdr list))) 573 constant)) 574 575(defun byte-optimize-form (form &optional for-effect) 576 "The source-level pass of the optimizer." 577 ;; 578 ;; First, optimize all sub-forms of this one. 579 (setq form (byte-optimize-form-code-walker form for-effect)) 580 ;; 581 ;; after optimizing all subforms, optimize this form until it doesn't 582 ;; optimize any further. This means that some forms will be passed through 583 ;; the optimizer many times, but that's necessary to make the for-effect 584 ;; processing do as much as possible. 585 ;; 586 (let (opt new) 587 (if (and (consp form) 588 (symbolp (car form)) 589 (or (and for-effect 590 ;; we don't have any of these yet, but we might. 591 (setq opt (get (car form) 'byte-for-effect-optimizer))) 592 (setq opt (get (car form) 'byte-optimizer))) 593 (not (eq form (setq new (funcall opt form))))) 594 (progn 595;; (if (equal form new) (error "bogus optimizer -- %s" opt)) 596 (byte-compile-log " %s\t==>\t%s" form new) 597 (setq new (byte-optimize-form new for-effect)) 598 new) 599 form))) 600 601 602(defun byte-optimize-body (forms all-for-effect) 603 ;; optimize the cdr of a progn or implicit progn; all forms is a list of 604 ;; forms, all but the last of which are optimized with the assumption that 605 ;; they are being called for effect. the last is for-effect as well if 606 ;; all-for-effect is true. returns a new list of forms. 607 (let ((rest forms) 608 (result nil) 609 fe new) 610 (while rest 611 (setq fe (or all-for-effect (cdr rest))) 612 (setq new (and (car rest) (byte-optimize-form (car rest) fe))) 613 (if (or new (not fe)) 614 (setq result (cons new result))) 615 (setq rest (cdr rest))) 616 (nreverse result))) 617 618 619;; some source-level optimizers 620;; 621;; when writing optimizers, be VERY careful that the optimizer returns 622;; something not EQ to its argument if and ONLY if it has made a change. 623;; This implies that you cannot simply destructively modify the list; 624;; you must return something not EQ to it if you make an optimization. 625;; 626;; It is now safe to optimize code such that it introduces new bindings. 627 628;; I'd like this to be a defsubst, but let's not be self-referential... 629(defmacro byte-compile-trueconstp (form) 630 ;; Returns non-nil if FORM is a non-nil constant. 631 `(cond ((consp ,form) (eq (car ,form) 'quote)) 632 ((not (symbolp ,form))) 633 ((eq ,form t)) 634 ((keywordp ,form)))) 635 636;; If the function is being called with constant numeric args, 637;; evaluate as much as possible at compile-time. This optimizer 638;; assumes that the function is associative, like + or *. 639(defun byte-optimize-associative-math (form) 640 (let ((args nil) 641 (constants nil) 642 (rest (cdr form))) 643 (while rest 644 (if (numberp (car rest)) 645 (setq constants (cons (car rest) constants)) 646 (setq args (cons (car rest) args))) 647 (setq rest (cdr rest))) 648 (if (cdr constants) 649 (if args 650 (list (car form) 651 (apply (car form) constants) 652 (if (cdr args) 653 (cons (car form) (nreverse args)) 654 (car args))) 655 (apply (car form) constants)) 656 form))) 657 658;; If the function is being called with constant numeric args, 659;; evaluate as much as possible at compile-time. This optimizer 660;; assumes that the function satisfies 661;; (op x1 x2 ... xn) == (op ...(op (op x1 x2) x3) ...xn) 662;; like - and /. 663(defun byte-optimize-nonassociative-math (form) 664 (if (or (not (numberp (car (cdr form)))) 665 (not (numberp (car (cdr (cdr form)))))) 666 form 667 (let ((constant (car (cdr form))) 668 (rest (cdr (cdr form)))) 669 (while (numberp (car rest)) 670 (setq constant (funcall (car form) constant (car rest)) 671 rest (cdr rest))) 672 (if rest 673 (cons (car form) (cons constant rest)) 674 constant)))) 675 676;;(defun byte-optimize-associative-two-args-math (form) 677;; (setq form (byte-optimize-associative-math form)) 678;; (if (consp form) 679;; (byte-optimize-two-args-left form) 680;; form)) 681 682;;(defun byte-optimize-nonassociative-two-args-math (form) 683;; (setq form (byte-optimize-nonassociative-math form)) 684;; (if (consp form) 685;; (byte-optimize-two-args-right form) 686;; form)) 687 688(defun byte-optimize-approx-equal (x y) 689 (<= (* (abs (- x y)) 100) (abs (+ x y)))) 690 691;; Collect all the constants from FORM, after the STARTth arg, 692;; and apply FUN to them to make one argument at the end. 693;; For functions that can handle floats, that optimization 694;; can be incorrect because reordering can cause an overflow 695;; that would otherwise be avoided by encountering an arg that is a float. 696;; We avoid this problem by (1) not moving float constants and 697;; (2) not moving anything if it would cause an overflow. 698(defun byte-optimize-delay-constants-math (form start fun) 699 ;; Merge all FORM's constants from number START, call FUN on them 700 ;; and put the result at the end. 701 (let ((rest (nthcdr (1- start) form)) 702 (orig form) 703 ;; t means we must check for overflow. 704 (overflow (memq fun '(+ *)))) 705 (while (cdr (setq rest (cdr rest))) 706 (if (integerp (car rest)) 707 (let (constants) 708 (setq form (copy-sequence form) 709 rest (nthcdr (1- start) form)) 710 (while (setq rest (cdr rest)) 711 (cond ((integerp (car rest)) 712 (setq constants (cons (car rest) constants)) 713 (setcar rest nil)))) 714 ;; If necessary, check now for overflow 715 ;; that might be caused by reordering. 716 (if (and overflow 717 ;; We have overflow if the result of doing the arithmetic 718 ;; on floats is not even close to the result 719 ;; of doing it on integers. 720 (not (byte-optimize-approx-equal 721 (apply fun (mapcar 'float constants)) 722 (float (apply fun constants))))) 723 (setq form orig) 724 (setq form (nconc (delq nil form) 725 (list (apply fun (nreverse constants))))))))) 726 form)) 727 728(defun byte-optimize-plus (form) 729 (setq form (byte-optimize-delay-constants-math form 1 '+)) 730 (if (memq 0 form) (setq form (delq 0 (copy-sequence form)))) 731 ;;(setq form (byte-optimize-associative-two-args-math form)) 732 (cond ((null (cdr form)) 733 (condition-case () 734 (eval form) 735 (error form))) 736;;; It is not safe to delete the function entirely 737;;; (actually, it would be safe if we know the sole arg 738;;; is not a marker). 739;;; ((null (cdr (cdr form))) (nth 1 form)) 740 ((null (cddr form)) 741 (if (numberp (nth 1 form)) 742 (nth 1 form) 743 form)) 744 ((and (null (nthcdr 3 form)) 745 (or (memq (nth 1 form) '(1 -1)) 746 (memq (nth 2 form) '(1 -1)))) 747 ;; Optimize (+ x 1) into (1+ x) and (+ x -1) into (1- x). 748 (let ((integer 749 (if (memq (nth 1 form) '(1 -1)) 750 (nth 1 form) 751 (nth 2 form))) 752 (other 753 (if (memq (nth 1 form) '(1 -1)) 754 (nth 2 form) 755 (nth 1 form)))) 756 (list (if (eq integer 1) '1+ '1-) 757 other))) 758 (t form))) 759 760(defun byte-optimize-minus (form) 761 ;; Put constants at the end, except the last constant. 762 (setq form (byte-optimize-delay-constants-math form 2 '+)) 763 ;; Now only first and last element can be a number. 764 (let ((last (car (reverse (nthcdr 3 form))))) 765 (cond ((eq 0 last) 766 ;; (- x y ... 0) --> (- x y ...) 767 (setq form (copy-sequence form)) 768 (setcdr (cdr (cdr form)) (delq 0 (nthcdr 3 form)))) 769 ((equal (nthcdr 2 form) '(1)) 770 (setq form (list '1- (nth 1 form)))) 771 ((equal (nthcdr 2 form) '(-1)) 772 (setq form (list '1+ (nth 1 form)))) 773 ;; If form is (- CONST foo... CONST), merge first and last. 774 ((and (numberp (nth 1 form)) 775 (numberp last)) 776 (setq form (nconc (list '- (- (nth 1 form) last) (nth 2 form)) 777 (delq last (copy-sequence (nthcdr 3 form)))))))) 778;;; It is not safe to delete the function entirely 779;;; (actually, it would be safe if we know the sole arg 780;;; is not a marker). 781;;; (if (eq (nth 2 form) 0) 782;;; (nth 1 form) ; (- x 0) --> x 783 (byte-optimize-predicate 784 (if (and (null (cdr (cdr (cdr form)))) 785 (eq (nth 1 form) 0)) ; (- 0 x) --> (- x) 786 (cons (car form) (cdr (cdr form))) 787 form)) 788;;; ) 789 ) 790 791(defun byte-optimize-multiply (form) 792 (setq form (byte-optimize-delay-constants-math form 1 '*)) 793 ;; If there is a constant in FORM, it is now the last element. 794 (cond ((null (cdr form)) 1) 795;;; It is not safe to delete the function entirely 796;;; (actually, it would be safe if we know the sole arg 797;;; is not a marker or if it appears in other arithmetic). 798;;; ((null (cdr (cdr form))) (nth 1 form)) 799 ((let ((last (car (reverse form)))) 800 (cond ((eq 0 last) (cons 'progn (cdr form))) 801 ((eq 1 last) (delq 1 (copy-sequence form))) 802 ((eq -1 last) (list '- (delq -1 (copy-sequence form)))) 803 ((and (eq 2 last) 804 (memq t (mapcar 'symbolp (cdr form)))) 805 (prog1 (setq form (delq 2 (copy-sequence form))) 806 (while (not (symbolp (car (setq form (cdr form)))))) 807 (setcar form (list '+ (car form) (car form))))) 808 (form)))))) 809 810(defsubst byte-compile-butlast (form) 811 (nreverse (cdr (reverse form)))) 812 813(defun byte-optimize-divide (form) 814 (setq form (byte-optimize-delay-constants-math form 2 '*)) 815 (let ((last (car (reverse (cdr (cdr form)))))) 816 (if (numberp last) 817 (cond ((= (length form) 3) 818 (if (and (numberp (nth 1 form)) 819 (not (zerop last)) 820 (condition-case nil 821 (/ (nth 1 form) last) 822 (error nil))) 823 (setq form (list 'progn (/ (nth 1 form) last))))) 824 ((= last 1) 825 (setq form (byte-compile-butlast form))) 826 ((numberp (nth 1 form)) 827 (setq form (cons (car form) 828 (cons (/ (nth 1 form) last) 829 (byte-compile-butlast (cdr (cdr form))))) 830 last nil)))) 831 (cond 832;;; ((null (cdr (cdr form))) 833;;; (nth 1 form)) 834 ((eq (nth 1 form) 0) 835 (append '(progn) (cdr (cdr form)) '(0))) 836 ((eq last -1) 837 (list '- (if (nthcdr 3 form) 838 (byte-compile-butlast form) 839 (nth 1 form)))) 840 (form)))) 841 842(defun byte-optimize-logmumble (form) 843 (setq form (byte-optimize-delay-constants-math form 1 (car form))) 844 (byte-optimize-predicate 845 (cond ((memq 0 form) 846 (setq form (if (eq (car form) 'logand) 847 (cons 'progn (cdr form)) 848 (delq 0 (copy-sequence form))))) 849 ((and (eq (car-safe form) 'logior) 850 (memq -1 form)) 851 (cons 'progn (cdr form))) 852 (form)))) 853 854 855(defun byte-optimize-binary-predicate (form) 856 (if (byte-compile-constp (nth 1 form)) 857 (if (byte-compile-constp (nth 2 form)) 858 (condition-case () 859 (list 'quote (eval form)) 860 (error form)) 861 ;; This can enable some lapcode optimizations. 862 (list (car form) (nth 2 form) (nth 1 form))) 863 form)) 864 865(defun byte-optimize-predicate (form) 866 (let ((ok t) 867 (rest (cdr form))) 868 (while (and rest ok) 869 (setq ok (byte-compile-constp (car rest)) 870 rest (cdr rest))) 871 (if ok 872 (condition-case () 873 (list 'quote (eval form)) 874 (error form)) 875 form))) 876 877(defun byte-optimize-identity (form) 878 (if (and (cdr form) (null (cdr (cdr form)))) 879 (nth 1 form) 880 (byte-compile-warn "identity called with %d arg%s, but requires 1" 881 (length (cdr form)) 882 (if (= 1 (length (cdr form))) "" "s")) 883 form)) 884 885(put 'identity 'byte-optimizer 'byte-optimize-identity) 886 887(put '+ 'byte-optimizer 'byte-optimize-plus) 888(put '* 'byte-optimizer 'byte-optimize-multiply) 889(put '- 'byte-optimizer 'byte-optimize-minus) 890(put '/ 'byte-optimizer 'byte-optimize-divide) 891(put 'max 'byte-optimizer 'byte-optimize-associative-math) 892(put 'min 'byte-optimizer 'byte-optimize-associative-math) 893 894(put '= 'byte-optimizer 'byte-optimize-binary-predicate) 895(put 'eq 'byte-optimizer 'byte-optimize-binary-predicate) 896(put 'equal 'byte-optimizer 'byte-optimize-binary-predicate) 897(put 'string= 'byte-optimizer 'byte-optimize-binary-predicate) 898(put 'string-equal 'byte-optimizer 'byte-optimize-binary-predicate) 899 900(put '< 'byte-optimizer 'byte-optimize-predicate) 901(put '> 'byte-optimizer 'byte-optimize-predicate) 902(put '<= 'byte-optimizer 'byte-optimize-predicate) 903(put '>= 'byte-optimizer 'byte-optimize-predicate) 904(put '1+ 'byte-optimizer 'byte-optimize-predicate) 905(put '1- 'byte-optimizer 'byte-optimize-predicate) 906(put 'not 'byte-optimizer 'byte-optimize-predicate) 907(put 'null 'byte-optimizer 'byte-optimize-predicate) 908(put 'memq 'byte-optimizer 'byte-optimize-predicate) 909(put 'consp 'byte-optimizer 'byte-optimize-predicate) 910(put 'listp 'byte-optimizer 'byte-optimize-predicate) 911(put 'symbolp 'byte-optimizer 'byte-optimize-predicate) 912(put 'stringp 'byte-optimizer 'byte-optimize-predicate) 913(put 'string< 'byte-optimizer 'byte-optimize-predicate) 914(put 'string-lessp 'byte-optimizer 'byte-optimize-predicate) 915 916(put 'logand 'byte-optimizer 'byte-optimize-logmumble) 917(put 'logior 'byte-optimizer 'byte-optimize-logmumble) 918(put 'logxor 'byte-optimizer 'byte-optimize-logmumble) 919(put 'lognot 'byte-optimizer 'byte-optimize-predicate) 920 921(put 'car 'byte-optimizer 'byte-optimize-predicate) 922(put 'cdr 'byte-optimizer 'byte-optimize-predicate) 923(put 'car-safe 'byte-optimizer 'byte-optimize-predicate) 924(put 'cdr-safe 'byte-optimizer 'byte-optimize-predicate) 925 926 927;; I'm not convinced that this is necessary. Doesn't the optimizer loop 928;; take care of this? - Jamie 929;; I think this may some times be necessary to reduce ie (quote 5) to 5, 930;; so arithmetic optimizers recognize the numeric constant. - Hallvard 931(put 'quote 'byte-optimizer 'byte-optimize-quote) 932(defun byte-optimize-quote (form) 933 (if (or (consp (nth 1 form)) 934 (and (symbolp (nth 1 form)) 935 (not (byte-compile-const-symbol-p form)))) 936 form 937 (nth 1 form))) 938 939(defun byte-optimize-zerop (form) 940 (cond ((numberp (nth 1 form)) 941 (eval form)) 942 (byte-compile-delete-errors 943 (list '= (nth 1 form) 0)) 944 (form))) 945 946(put 'zerop 'byte-optimizer 'byte-optimize-zerop) 947 948(defun byte-optimize-and (form) 949 ;; Simplify if less than 2 args. 950 ;; if there is a literal nil in the args to `and', throw it and following 951 ;; forms away, and surround the `and' with (progn ... nil). 952 (cond ((null (cdr form))) 953 ((memq nil form) 954 (list 'progn 955 (byte-optimize-and 956 (prog1 (setq form (copy-sequence form)) 957 (while (nth 1 form) 958 (setq form (cdr form))) 959 (setcdr form nil))) 960 nil)) 961 ((null (cdr (cdr form))) 962 (nth 1 form)) 963 ((byte-optimize-predicate form)))) 964 965(defun byte-optimize-or (form) 966 ;; Throw away nil's, and simplify if less than 2 args. 967 ;; If there is a literal non-nil constant in the args to `or', throw away all 968 ;; following forms. 969 (if (memq nil form) 970 (setq form (delq nil (copy-sequence form)))) 971 (let ((rest form)) 972 (while (cdr (setq rest (cdr rest))) 973 (if (byte-compile-trueconstp (car rest)) 974 (setq form (copy-sequence form) 975 rest (setcdr (memq (car rest) form) nil)))) 976 (if (cdr (cdr form)) 977 (byte-optimize-predicate form) 978 (nth 1 form)))) 979 980(defun byte-optimize-cond (form) 981 ;; if any clauses have a literal nil as their test, throw them away. 982 ;; if any clause has a literal non-nil constant as its test, throw 983 ;; away all following clauses. 984 (let (rest) 985 ;; This must be first, to reduce (cond (t ...) (nil)) to (progn t ...) 986 (while (setq rest (assq nil (cdr form))) 987 (setq form (delq rest (copy-sequence form)))) 988 (if (memq nil (cdr form)) 989 (setq form (delq nil (copy-sequence form)))) 990 (setq rest form) 991 (while (setq rest (cdr rest)) 992 (cond ((byte-compile-trueconstp (car-safe (car rest))) 993 (cond ((eq rest (cdr form)) 994 (setq form 995 (if (cdr (car rest)) 996 (if (cdr (cdr (car rest))) 997 (cons 'progn (cdr (car rest))) 998 (nth 1 (car rest))) 999 (car (car rest))))) 1000 ((cdr rest) 1001 (setq form (copy-sequence form)) 1002 (setcdr (memq (car rest) form) nil))) 1003 (setq rest nil))))) 1004 ;; 1005 ;; Turn (cond (( <x> )) ... ) into (or <x> (cond ... )) 1006 (if (eq 'cond (car-safe form)) 1007 (let ((clauses (cdr form))) 1008 (if (and (consp (car clauses)) 1009 (null (cdr (car clauses)))) 1010 (list 'or (car (car clauses)) 1011 (byte-optimize-cond 1012 (cons (car form) (cdr (cdr form))))) 1013 form)) 1014 form)) 1015 1016(defun byte-optimize-if (form) 1017 ;; (if <true-constant> <then> <else...>) ==> <then> 1018 ;; (if <false-constant> <then> <else...>) ==> (progn <else...>) 1019 ;; (if <test> nil <else...>) ==> (if (not <test>) (progn <else...>)) 1020 ;; (if <test> <then> nil) ==> (if <test> <then>) 1021 (let ((clause (nth 1 form))) 1022 (cond ((byte-compile-trueconstp clause) 1023 (nth 2 form)) 1024 ((null clause) 1025 (if (nthcdr 4 form) 1026 (cons 'progn (nthcdr 3 form)) 1027 (nth 3 form))) 1028 ((nth 2 form) 1029 (if (equal '(nil) (nthcdr 3 form)) 1030 (list 'if clause (nth 2 form)) 1031 form)) 1032 ((or (nth 3 form) (nthcdr 4 form)) 1033 (list 'if 1034 ;; Don't make a double negative; 1035 ;; instead, take away the one that is there. 1036 (if (and (consp clause) (memq (car clause) '(not null)) 1037 (= (length clause) 2)) ; (not xxxx) or (not (xxxx)) 1038 (nth 1 clause) 1039 (list 'not clause)) 1040 (if (nthcdr 4 form) 1041 (cons 'progn (nthcdr 3 form)) 1042 (nth 3 form)))) 1043 (t 1044 (list 'progn clause nil))))) 1045 1046(defun byte-optimize-while (form) 1047 (when (< (length form) 2) 1048 (byte-compile-warn "too few arguments for `while'")) 1049 (if (nth 1 form) 1050 form)) 1051 1052(put 'and 'byte-optimizer 'byte-optimize-and) 1053(put 'or 'byte-optimizer 'byte-optimize-or) 1054(put 'cond 'byte-optimizer 'byte-optimize-cond) 1055(put 'if 'byte-optimizer 'byte-optimize-if) 1056(put 'while 'byte-optimizer 'byte-optimize-while) 1057 1058;; byte-compile-negation-optimizer lives in bytecomp.el 1059(put '/= 'byte-optimizer 'byte-compile-negation-optimizer) 1060(put 'atom 'byte-optimizer 'byte-compile-negation-optimizer) 1061(put 'nlistp 'byte-optimizer 'byte-compile-negation-optimizer) 1062 1063 1064(defun byte-optimize-funcall (form) 1065 ;; (funcall (lambda ...) ...) ==> ((lambda ...) ...) 1066 ;; (funcall foo ...) ==> (foo ...) 1067 (let ((fn (nth 1 form))) 1068 (if (memq (car-safe fn) '(quote function)) 1069 (cons (nth 1 fn) (cdr (cdr form))) 1070 form))) 1071 1072(defun byte-optimize-apply (form) 1073 ;; If the last arg is a literal constant, turn this into a funcall. 1074 ;; The funcall optimizer can then transform (funcall 'foo ...) -> (foo ...). 1075 (let ((fn (nth 1 form)) 1076 (last (nth (1- (length form)) form))) ; I think this really is fastest 1077 (or (if (or (null last) 1078 (eq (car-safe last) 'quote)) 1079 (if (listp (nth 1 last)) 1080 (let ((butlast (nreverse (cdr (reverse (cdr (cdr form))))))) 1081 (nconc (list 'funcall fn) butlast 1082 (mapcar (lambda (x) (list 'quote x)) (nth 1 last)))) 1083 (byte-compile-warn 1084 "last arg to apply can't be a literal atom: `%s'" 1085 (prin1-to-string last)) 1086 nil)) 1087 form))) 1088 1089(put 'funcall 'byte-optimizer 'byte-optimize-funcall) 1090(put 'apply 'byte-optimizer 'byte-optimize-apply) 1091 1092 1093(put 'let 'byte-optimizer 'byte-optimize-letX) 1094(put 'let* 'byte-optimizer 'byte-optimize-letX) 1095(defun byte-optimize-letX (form) 1096 (cond ((null (nth 1 form)) 1097 ;; No bindings 1098 (cons 'progn (cdr (cdr form)))) 1099 ((or (nth 2 form) (nthcdr 3 form)) 1100 form) 1101 ;; The body is nil 1102 ((eq (car form) 'let) 1103 (append '(progn) (mapcar 'car-safe (mapcar 'cdr-safe (nth 1 form))) 1104 '(nil))) 1105 (t 1106 (let ((binds (reverse (nth 1 form)))) 1107 (list 'let* (reverse (cdr binds)) (nth 1 (car binds)) nil))))) 1108 1109 1110(put 'nth 'byte-optimizer 'byte-optimize-nth) 1111(defun byte-optimize-nth (form) 1112 (if (= (safe-length form) 3) 1113 (if (memq (nth 1 form) '(0 1)) 1114 (list 'car (if (zerop (nth 1 form)) 1115 (nth 2 form) 1116 (list 'cdr (nth 2 form)))) 1117 (byte-optimize-predicate form)) 1118 form)) 1119 1120(put 'nthcdr 'byte-optimizer 'byte-optimize-nthcdr) 1121(defun byte-optimize-nthcdr (form) 1122 (if (= (safe-length form) 3) 1123 (if (memq (nth 1 form) '(0 1 2)) 1124 (let ((count (nth 1 form))) 1125 (setq form (nth 2 form)) 1126 (while (>= (setq count (1- count)) 0) 1127 (setq form (list 'cdr form))) 1128 form) 1129 (byte-optimize-predicate form)) 1130 form)) 1131 1132;; Fixme: delete-char -> delete-region (byte-coded) 1133;; optimize string-as-unibyte, string-as-multibyte, string-make-unibyte, 1134;; string-make-multibyte for constant args. 1135 1136(put 'featurep 'byte-optimizer 'byte-optimize-featurep) 1137(defun byte-optimize-featurep (form) 1138 ;; Emacs-21's byte-code doesn't run under XEmacs anyway, so we can 1139 ;; safely optimize away this test. 1140 (if (equal '((quote xemacs)) (cdr-safe form)) 1141 nil 1142 form)) 1143 1144(put 'set 'byte-optimizer 'byte-optimize-set) 1145(defun byte-optimize-set (form) 1146 (let ((var (car-safe (cdr-safe form)))) 1147 (cond 1148 ((and (eq (car-safe var) 'quote) (consp (cdr var))) 1149 `(setq ,(cadr var) ,@(cddr form))) 1150 ((and (eq (car-safe var) 'make-local-variable) 1151 (eq (car-safe (setq var (car-safe (cdr var)))) 'quote) 1152 (consp (cdr var))) 1153 `(progn ,(cadr form) (setq ,(cadr var) ,@(cddr form)))) 1154 (t form)))) 1155 1156;; enumerating those functions which need not be called if the returned 1157;; value is not used. That is, something like 1158;; (progn (list (something-with-side-effects) (yow)) 1159;; (foo)) 1160;; may safely be turned into 1161;; (progn (progn (something-with-side-effects) (yow)) 1162;; (foo)) 1163;; Further optimizations will turn (progn (list 1 2 3) 'foo) into 'foo. 1164 1165;; Some of these functions have the side effect of allocating memory 1166;; and it would be incorrect to replace two calls with one. 1167;; But we don't try to do those kinds of optimizations, 1168;; so it is safe to list such functions here. 1169;; Some of these functions return values that depend on environment 1170;; state, so that constant folding them would be wrong, 1171;; but we don't do constant folding based on this list. 1172 1173;; However, at present the only optimization we normally do 1174;; is delete calls that need not occur, and we only do that 1175;; with the error-free functions. 1176 1177;; I wonder if I missed any :-\) 1178(let ((side-effect-free-fns 1179 '(% * + - / /= 1+ 1- < <= = > >= abs acos append aref ash asin atan 1180 assoc assq 1181 boundp buffer-file-name buffer-local-variables buffer-modified-p 1182 buffer-substring byte-code-function-p 1183 capitalize car-less-than-car car cdr ceiling char-after char-before 1184 char-equal char-to-string char-width 1185 compare-strings concat coordinates-in-window-p 1186 copy-alist copy-sequence copy-marker cos count-lines 1187 decode-time default-boundp default-value documentation downcase 1188 elt exp expt encode-time error-message-string 1189 fboundp fceiling featurep ffloor 1190 file-directory-p file-exists-p file-locked-p file-name-absolute-p 1191 file-newer-than-file-p file-readable-p file-symlink-p file-writable-p 1192 float float-time floor format format-time-string frame-visible-p 1193 fround ftruncate 1194 get gethash get-buffer get-buffer-window getenv get-file-buffer 1195 hash-table-count 1196 int-to-string intern-soft 1197 keymap-parent 1198 length local-variable-if-set-p local-variable-p log log10 logand 1199 logb logior lognot logxor lsh 1200 make-list make-string make-symbol 1201 marker-buffer max member memq min mod multibyte-char-to-unibyte 1202 next-window nth nthcdr number-to-string 1203 parse-colon-path plist-get plist-member 1204 prefix-numeric-value previous-window prin1-to-string propertize 1205 radians-to-degrees rassq rassoc read-from-string regexp-quote 1206 region-beginning region-end reverse round 1207 sin sqrt string string< string= string-equal string-lessp string-to-char 1208 string-to-int string-to-number substring sxhash symbol-function 1209 symbol-name symbol-plist symbol-value string-make-unibyte 1210 string-make-multibyte string-as-multibyte string-as-unibyte 1211 tan truncate 1212 unibyte-char-to-multibyte upcase user-full-name 1213 user-login-name user-original-login-name user-variable-p 1214 vconcat 1215 window-buffer window-dedicated-p window-edges window-height 1216 window-hscroll window-minibuffer-p window-width 1217 zerop)) 1218 (side-effect-and-error-free-fns 1219 '(arrayp atom 1220 bobp bolp bool-vector-p 1221 buffer-end buffer-list buffer-size buffer-string bufferp 1222 car-safe case-table-p cdr-safe char-or-string-p commandp cons consp 1223 current-buffer current-global-map current-indentation 1224 current-local-map current-minor-mode-maps current-time 1225 current-time-string current-time-zone 1226 eobp eolp eq equal eventp 1227 floatp following-char framep 1228 get-largest-window get-lru-window 1229 hash-table-p 1230 identity ignore integerp integer-or-marker-p interactive-p 1231 invocation-directory invocation-name 1232 keymapp 1233 line-beginning-position line-end-position list listp 1234 make-marker mark mark-marker markerp memory-limit minibuffer-window 1235 mouse-movement-p 1236 natnump nlistp not null number-or-marker-p numberp 1237 one-window-p overlayp 1238 point point-marker point-min point-max preceding-char processp 1239 recent-keys recursion-depth 1240 safe-length selected-frame selected-window sequencep 1241 standard-case-table standard-syntax-table stringp subrp symbolp 1242 syntax-table syntax-table-p 1243 this-command-keys this-command-keys-vector this-single-command-keys 1244 this-single-command-raw-keys 1245 user-real-login-name user-real-uid user-uid 1246 vector vectorp visible-frame-list 1247 wholenump window-configuration-p window-live-p windowp))) 1248 (while side-effect-free-fns 1249 (put (car side-effect-free-fns) 'side-effect-free t) 1250 (setq side-effect-free-fns (cdr side-effect-free-fns))) 1251 (while side-effect-and-error-free-fns 1252 (put (car side-effect-and-error-free-fns) 'side-effect-free 'error-free) 1253 (setq side-effect-and-error-free-fns (cdr side-effect-and-error-free-fns))) 1254 nil) 1255 1256 1257;; pure functions are side-effect free functions whose values depend 1258;; only on their arguments. For these functions, calls with constant 1259;; arguments can be evaluated at compile time. This may shift run time 1260;; errors to compile time. 1261 1262(let ((pure-fns 1263 '(concat symbol-name regexp-opt regexp-quote string-to-syntax))) 1264 (while pure-fns 1265 (put (car pure-fns) 'pure t) 1266 (setq pure-fns (cdr pure-fns))) 1267 nil) 1268 1269(defun byte-compile-splice-in-already-compiled-code (form) 1270 ;; form is (byte-code "..." [...] n) 1271 (if (not (memq byte-optimize '(t lap))) 1272 (byte-compile-normal-call form) 1273 (byte-inline-lapcode 1274 (byte-decompile-bytecode-1 (nth 1 form) (nth 2 form) t)) 1275 (setq byte-compile-maxdepth (max (+ byte-compile-depth (nth 3 form)) 1276 byte-compile-maxdepth)) 1277 (setq byte-compile-depth (1+ byte-compile-depth)))) 1278 1279(put 'byte-code 'byte-compile 'byte-compile-splice-in-already-compiled-code) 1280 1281 1282(defconst byte-constref-ops 1283 '(byte-constant byte-constant2 byte-varref byte-varset byte-varbind)) 1284 1285;; This function extracts the bitfields from variable-length opcodes. 1286;; Originally defined in disass.el (which no longer uses it.) 1287 1288(defun disassemble-offset () 1289 "Don't call this!" 1290 ;; fetch and return the offset for the current opcode. 1291 ;; return nil if this opcode has no offset 1292 ;; OP, PTR and BYTES are used and set dynamically 1293 (defvar op) 1294 (defvar ptr) 1295 (defvar bytes) 1296 (cond ((< op byte-nth) 1297 (let ((tem (logand op 7))) 1298 (setq op (logand op 248)) 1299 (cond ((eq tem 6) 1300 (setq ptr (1+ ptr)) ;offset in next byte 1301 (aref bytes ptr)) 1302 ((eq tem 7) 1303 (setq ptr (1+ ptr)) ;offset in next 2 bytes 1304 (+ (aref bytes ptr) 1305 (progn (setq ptr (1+ ptr)) 1306 (lsh (aref bytes ptr) 8)))) 1307 (t tem)))) ;offset was in opcode 1308 ((>= op byte-constant) 1309 (prog1 (- op byte-constant) ;offset in opcode 1310 (setq op byte-constant))) 1311 ((and (>= op byte-constant2) 1312 (<= op byte-goto-if-not-nil-else-pop)) 1313 (setq ptr (1+ ptr)) ;offset in next 2 bytes 1314 (+ (aref bytes ptr) 1315 (progn (setq ptr (1+ ptr)) 1316 (lsh (aref bytes ptr) 8)))) 1317 ((and (>= op byte-listN) 1318 (<= op byte-insertN)) 1319 (setq ptr (1+ ptr)) ;offset in next byte 1320 (aref bytes ptr)))) 1321 1322 1323;; This de-compiler is used for inline expansion of compiled functions, 1324;; and by the disassembler. 1325;; 1326;; This list contains numbers, which are pc values, 1327;; before each instruction. 1328(defun byte-decompile-bytecode (bytes constvec) 1329 "Turns BYTECODE into lapcode, referring to CONSTVEC." 1330 (let ((byte-compile-constants nil) 1331 (byte-compile-variables nil) 1332 (byte-compile-tag-number 0)) 1333 (byte-decompile-bytecode-1 bytes constvec))) 1334 1335;; As byte-decompile-bytecode, but updates 1336;; byte-compile-{constants, variables, tag-number}. 1337;; If MAKE-SPLICEABLE is true, then `return' opcodes are replaced 1338;; with `goto's destined for the end of the code. 1339;; That is for use by the compiler. 1340;; If MAKE-SPLICEABLE is nil, we are being called for the disassembler. 1341;; In that case, we put a pc value into the list 1342;; before each insn (or its label). 1343(defun byte-decompile-bytecode-1 (bytes constvec &optional make-spliceable) 1344 (let ((length (length bytes)) 1345 (ptr 0) optr tags op offset 1346 lap tmp 1347 endtag) 1348 (while (not (= ptr length)) 1349 (or make-spliceable 1350 (setq lap (cons ptr lap))) 1351 (setq op (aref bytes ptr) 1352 optr ptr 1353 offset (disassemble-offset)) ; this does dynamic-scope magic 1354 (setq op (aref byte-code-vector op)) 1355 (cond ((memq op byte-goto-ops) 1356 ;; it's a pc 1357 (setq offset 1358 (cdr (or (assq offset tags) 1359 (car (setq tags 1360 (cons (cons offset 1361 (byte-compile-make-tag)) 1362 tags))))))) 1363 ((cond ((eq op 'byte-constant2) (setq op 'byte-constant) t) 1364 ((memq op byte-constref-ops))) 1365 (setq tmp (if (>= offset (length constvec)) 1366 (list 'out-of-range offset) 1367 (aref constvec offset)) 1368 offset (if (eq op 'byte-constant) 1369 (byte-compile-get-constant tmp) 1370 (or (assq tmp byte-compile-variables) 1371 (car (setq byte-compile-variables 1372 (cons (list tmp) 1373 byte-compile-variables))))))) 1374 ((and make-spliceable 1375 (eq op 'byte-return)) 1376 (if (= ptr (1- length)) 1377 (setq op nil) 1378 (setq offset (or endtag (setq endtag (byte-compile-make-tag))) 1379 op 'byte-goto)))) 1380 ;; lap = ( [ (pc . (op . arg)) ]* ) 1381 (setq lap (cons (cons optr (cons op (or offset 0))) 1382 lap)) 1383 (setq ptr (1+ ptr))) 1384 ;; take off the dummy nil op that we replaced a trailing "return" with. 1385 (let ((rest lap)) 1386 (while rest 1387 (cond ((numberp (car rest))) 1388 ((setq tmp (assq (car (car rest)) tags)) 1389 ;; this addr is jumped to 1390 (setcdr rest (cons (cons nil (cdr tmp)) 1391 (cdr rest))) 1392 (setq tags (delq tmp tags)) 1393 (setq rest (cdr rest)))) 1394 (setq rest (cdr rest)))) 1395 (if tags (error "optimizer error: missed tags %s" tags)) 1396 (if (null (car (cdr (car lap)))) 1397 (setq lap (cdr lap))) 1398 (if endtag 1399 (setq lap (cons (cons nil endtag) lap))) 1400 ;; remove addrs, lap = ( [ (op . arg) | (TAG tagno) ]* ) 1401 (mapcar (function (lambda (elt) 1402 (if (numberp elt) 1403 elt 1404 (cdr elt)))) 1405 (nreverse lap)))) 1406 1407 1408;;; peephole optimizer 1409 1410(defconst byte-tagref-ops (cons 'TAG byte-goto-ops)) 1411 1412(defconst byte-conditional-ops 1413 '(byte-goto-if-nil byte-goto-if-not-nil byte-goto-if-nil-else-pop 1414 byte-goto-if-not-nil-else-pop)) 1415 1416(defconst byte-after-unbind-ops 1417 '(byte-constant byte-dup 1418 byte-symbolp byte-consp byte-stringp byte-listp byte-numberp byte-integerp 1419 byte-eq byte-not 1420 byte-cons byte-list1 byte-list2 ; byte-list3 byte-list4 1421 byte-interactive-p) 1422 ;; How about other side-effect-free-ops? Is it safe to move an 1423 ;; error invocation (such as from nth) out of an unwind-protect? 1424 ;; No, it is not, because the unwind-protect forms can alter 1425 ;; the inside of the object to which nth would apply. 1426 ;; For the same reason, byte-equal was deleted from this list. 1427 "Byte-codes that can be moved past an unbind.") 1428 1429(defconst byte-compile-side-effect-and-error-free-ops 1430 '(byte-constant byte-dup byte-symbolp byte-consp byte-stringp byte-listp 1431 byte-integerp byte-numberp byte-eq byte-equal byte-not byte-car-safe 1432 byte-cdr-safe byte-cons byte-list1 byte-list2 byte-point byte-point-max 1433 byte-point-min byte-following-char byte-preceding-char 1434 byte-current-column byte-eolp byte-eobp byte-bolp byte-bobp 1435 byte-current-buffer byte-interactive-p)) 1436 1437(defconst byte-compile-side-effect-free-ops 1438 (nconc 1439 '(byte-varref byte-nth byte-memq byte-car byte-cdr byte-length byte-aref 1440 byte-symbol-value byte-get byte-concat2 byte-concat3 byte-sub1 byte-add1 1441 byte-eqlsign byte-gtr byte-lss byte-leq byte-geq byte-diff byte-negate 1442 byte-plus byte-max byte-min byte-mult byte-char-after byte-char-syntax 1443 byte-buffer-substring byte-string= byte-string< byte-nthcdr byte-elt 1444 byte-member byte-assq byte-quo byte-rem) 1445 byte-compile-side-effect-and-error-free-ops)) 1446 1447;; This crock is because of the way DEFVAR_BOOL variables work. 1448;; Consider the code 1449;; 1450;; (defun foo (flag) 1451;; (let ((old-pop-ups pop-up-windows) 1452;; (pop-up-windows flag)) 1453;; (cond ((not (eq pop-up-windows old-pop-ups)) 1454;; (setq old-pop-ups pop-up-windows) 1455;; ...)))) 1456;; 1457;; Uncompiled, old-pop-ups will always be set to nil or t, even if FLAG is 1458;; something else. But if we optimize 1459;; 1460;; varref flag 1461;; varbind pop-up-windows 1462;; varref pop-up-windows 1463;; not 1464;; to 1465;; varref flag 1466;; dup 1467;; varbind pop-up-windows 1468;; not 1469;; 1470;; we break the program, because it will appear that pop-up-windows and 1471;; old-pop-ups are not EQ when really they are. So we have to know what 1472;; the BOOL variables are, and not perform this optimization on them. 1473 1474;; The variable `byte-boolean-vars' is now primitive and updated 1475;; automatically by DEFVAR_BOOL. 1476 1477(defun byte-optimize-lapcode (lap &optional for-effect) 1478 "Simple peephole optimizer. LAP is both modified and returned. 1479If FOR-EFFECT is non-nil, the return value is assumed to be of no importance." 1480 (let (lap0 1481 lap1 1482 lap2 1483 (keep-going 'first-time) 1484 (add-depth 0) 1485 rest tmp tmp2 tmp3 1486 (side-effect-free (if byte-compile-delete-errors 1487 byte-compile-side-effect-free-ops 1488 byte-compile-side-effect-and-error-free-ops))) 1489 (while keep-going 1490 (or (eq keep-going 'first-time) 1491 (byte-compile-log-lap " ---- next pass")) 1492 (setq rest lap 1493 keep-going nil) 1494 (while rest 1495 (setq lap0 (car rest) 1496 lap1 (nth 1 rest) 1497 lap2 (nth 2 rest)) 1498 1499 ;; You may notice that sequences like "dup varset discard" are 1500 ;; optimized but sequences like "dup varset TAG1: discard" are not. 1501 ;; You may be tempted to change this; resist that temptation. 1502 (cond ;; 1503 ;; <side-effect-free> pop --> <deleted> 1504 ;; ...including: 1505 ;; const-X pop --> <deleted> 1506 ;; varref-X pop --> <deleted> 1507 ;; dup pop --> <deleted> 1508 ;; 1509 ((and (eq 'byte-discard (car lap1)) 1510 (memq (car lap0) side-effect-free)) 1511 (setq keep-going t) 1512 (setq tmp (aref byte-stack+-info (symbol-value (car lap0)))) 1513 (setq rest (cdr rest)) 1514 (cond ((= tmp 1) 1515 (byte-compile-log-lap 1516 " %s discard\t-->\t<deleted>" lap0) 1517 (setq lap (delq lap0 (delq lap1 lap)))) 1518 ((= tmp 0) 1519 (byte-compile-log-lap 1520 " %s discard\t-->\t<deleted> discard" lap0) 1521 (setq lap (delq lap0 lap))) 1522 ((= tmp -1) 1523 (byte-compile-log-lap 1524 " %s discard\t-->\tdiscard discard" lap0) 1525 (setcar lap0 'byte-discard) 1526 (setcdr lap0 0)) 1527 ((error "Optimizer error: too much on the stack")))) 1528 ;; 1529 ;; goto*-X X: --> X: 1530 ;; 1531 ((and (memq (car lap0) byte-goto-ops) 1532 (eq (cdr lap0) lap1)) 1533 (cond ((eq (car lap0) 'byte-goto) 1534 (setq lap (delq lap0 lap)) 1535 (setq tmp "<deleted>")) 1536 ((memq (car lap0) byte-goto-always-pop-ops) 1537 (setcar lap0 (setq tmp 'byte-discard)) 1538 (setcdr lap0 0)) 1539 ((error "Depth conflict at tag %d" (nth 2 lap0)))) 1540 (and (memq byte-optimize-log '(t byte)) 1541 (byte-compile-log " (goto %s) %s:\t-->\t%s %s:" 1542 (nth 1 lap1) (nth 1 lap1) 1543 tmp (nth 1 lap1))) 1544 (setq keep-going t)) 1545 ;; 1546 ;; varset-X varref-X --> dup varset-X 1547 ;; varbind-X varref-X --> dup varbind-X 1548 ;; const/dup varset-X varref-X --> const/dup varset-X const/dup 1549 ;; const/dup varbind-X varref-X --> const/dup varbind-X const/dup 1550 ;; The latter two can enable other optimizations. 1551 ;; 1552 ((and (eq 'byte-varref (car lap2)) 1553 (eq (cdr lap1) (cdr lap2)) 1554 (memq (car lap1) '(byte-varset byte-varbind))) 1555 (if (and (setq tmp (memq (car (cdr lap2)) byte-boolean-vars)) 1556 (not (eq (car lap0) 'byte-constant))) 1557 nil 1558 (setq keep-going t) 1559 (if (memq (car lap0) '(byte-constant byte-dup)) 1560 (progn 1561 (setq tmp (if (or (not tmp) 1562 (byte-compile-const-symbol-p 1563 (car (cdr lap0)))) 1564 (cdr lap0) 1565 (byte-compile-get-constant t))) 1566 (byte-compile-log-lap " %s %s %s\t-->\t%s %s %s" 1567 lap0 lap1 lap2 lap0 lap1 1568 (cons (car lap0) tmp)) 1569 (setcar lap2 (car lap0)) 1570 (setcdr lap2 tmp)) 1571 (byte-compile-log-lap " %s %s\t-->\tdup %s" lap1 lap2 lap1) 1572 (setcar lap2 (car lap1)) 1573 (setcar lap1 'byte-dup) 1574 (setcdr lap1 0) 1575 ;; The stack depth gets locally increased, so we will 1576 ;; increase maxdepth in case depth = maxdepth here. 1577 ;; This can cause the third argument to byte-code to 1578 ;; be larger than necessary. 1579 (setq add-depth 1)))) 1580 ;; 1581 ;; dup varset-X discard --> varset-X 1582 ;; dup varbind-X discard --> varbind-X 1583 ;; (the varbind variant can emerge from other optimizations) 1584 ;; 1585 ((and (eq 'byte-dup (car lap0)) 1586 (eq 'byte-discard (car lap2)) 1587 (memq (car lap1) '(byte-varset byte-varbind))) 1588 (byte-compile-log-lap " dup %s discard\t-->\t%s" lap1 lap1) 1589 (setq keep-going t 1590 rest (cdr rest)) 1591 (setq lap (delq lap0 (delq lap2 lap)))) 1592 ;; 1593 ;; not goto-X-if-nil --> goto-X-if-non-nil 1594 ;; not goto-X-if-non-nil --> goto-X-if-nil 1595 ;; 1596 ;; it is wrong to do the same thing for the -else-pop variants. 1597 ;; 1598 ((and (eq 'byte-not (car lap0)) 1599 (or (eq 'byte-goto-if-nil (car lap1)) 1600 (eq 'byte-goto-if-not-nil (car lap1)))) 1601 (byte-compile-log-lap " not %s\t-->\t%s" 1602 lap1 1603 (cons 1604 (if (eq (car lap1) 'byte-goto-if-nil) 1605 'byte-goto-if-not-nil 1606 'byte-goto-if-nil) 1607 (cdr lap1))) 1608 (setcar lap1 (if (eq (car lap1) 'byte-goto-if-nil) 1609 'byte-goto-if-not-nil 1610 'byte-goto-if-nil)) 1611 (setq lap (delq lap0 lap)) 1612 (setq keep-going t)) 1613 ;; 1614 ;; goto-X-if-nil goto-Y X: --> goto-Y-if-non-nil X: 1615 ;; goto-X-if-non-nil goto-Y X: --> goto-Y-if-nil X: 1616 ;; 1617 ;; it is wrong to do the same thing for the -else-pop variants. 1618 ;; 1619 ((and (or (eq 'byte-goto-if-nil (car lap0)) 1620 (eq 'byte-goto-if-not-nil (car lap0))) ; gotoX 1621 (eq 'byte-goto (car lap1)) ; gotoY 1622 (eq (cdr lap0) lap2)) ; TAG X 1623 (let ((inverse (if (eq 'byte-goto-if-nil (car lap0)) 1624 'byte-goto-if-not-nil 'byte-goto-if-nil))) 1625 (byte-compile-log-lap " %s %s %s:\t-->\t%s %s:" 1626 lap0 lap1 lap2 1627 (cons inverse (cdr lap1)) lap2) 1628 (setq lap (delq lap0 lap)) 1629 (setcar lap1 inverse) 1630 (setq keep-going t))) 1631 ;; 1632 ;; const goto-if-* --> whatever 1633 ;; 1634 ((and (eq 'byte-constant (car lap0)) 1635 (memq (car lap1) byte-conditional-ops)) 1636 (cond ((if (or (eq (car lap1) 'byte-goto-if-nil) 1637 (eq (car lap1) 'byte-goto-if-nil-else-pop)) 1638 (car (cdr lap0)) 1639 (not (car (cdr lap0)))) 1640 (byte-compile-log-lap " %s %s\t-->\t<deleted>" 1641 lap0 lap1) 1642 (setq rest (cdr rest) 1643 lap (delq lap0 (delq lap1 lap)))) 1644 (t 1645 (if (memq (car lap1) byte-goto-always-pop-ops) 1646 (progn 1647 (byte-compile-log-lap " %s %s\t-->\t%s" 1648 lap0 lap1 (cons 'byte-goto (cdr lap1))) 1649 (setq lap (delq lap0 lap))) 1650 (byte-compile-log-lap " %s %s\t-->\t%s" lap0 lap1 1651 (cons 'byte-goto (cdr lap1)))) 1652 (setcar lap1 'byte-goto))) 1653 (setq keep-going t)) 1654 ;; 1655 ;; varref-X varref-X --> varref-X dup 1656 ;; varref-X [dup ...] varref-X --> varref-X [dup ...] dup 1657 ;; We don't optimize the const-X variations on this here, 1658 ;; because that would inhibit some goto optimizations; we 1659 ;; optimize the const-X case after all other optimizations. 1660 ;; 1661 ((and (eq 'byte-varref (car lap0)) 1662 (progn 1663 (setq tmp (cdr rest)) 1664 (while (eq (car (car tmp)) 'byte-dup) 1665 (setq tmp (cdr tmp))) 1666 t) 1667 (eq (cdr lap0) (cdr (car tmp))) 1668 (eq 'byte-varref (car (car tmp)))) 1669 (if (memq byte-optimize-log '(t byte)) 1670 (let ((str "")) 1671 (setq tmp2 (cdr rest)) 1672 (while (not (eq tmp tmp2)) 1673 (setq tmp2 (cdr tmp2) 1674 str (concat str " dup"))) 1675 (byte-compile-log-lap " %s%s %s\t-->\t%s%s dup" 1676 lap0 str lap0 lap0 str))) 1677 (setq keep-going t) 1678 (setcar (car tmp) 'byte-dup) 1679 (setcdr (car tmp) 0) 1680 (setq rest tmp)) 1681 ;; 1682 ;; TAG1: TAG2: --> TAG1: <deleted> 1683 ;; (and other references to TAG2 are replaced with TAG1) 1684 ;; 1685 ((and (eq (car lap0) 'TAG) 1686 (eq (car lap1) 'TAG)) 1687 (and (memq byte-optimize-log '(t byte)) 1688 (byte-compile-log " adjacent tags %d and %d merged" 1689 (nth 1 lap1) (nth 1 lap0))) 1690 (setq tmp3 lap) 1691 (while (setq tmp2 (rassq lap0 tmp3)) 1692 (setcdr tmp2 lap1) 1693 (setq tmp3 (cdr (memq tmp2 tmp3)))) 1694 (setq lap (delq lap0 lap) 1695 keep-going t)) 1696 ;; 1697 ;; unused-TAG: --> <deleted> 1698 ;; 1699 ((and (eq 'TAG (car lap0)) 1700 (not (rassq lap0 lap))) 1701 (and (memq byte-optimize-log '(t byte)) 1702 (byte-compile-log " unused tag %d removed" (nth 1 lap0))) 1703 (setq lap (delq lap0 lap) 1704 keep-going t)) 1705 ;; 1706 ;; goto ... --> goto <delete until TAG or end> 1707 ;; return ... --> return <delete until TAG or end> 1708 ;; 1709 ((and (memq (car lap0) '(byte-goto byte-return)) 1710 (not (memq (car lap1) '(TAG nil)))) 1711 (setq tmp rest) 1712 (let ((i 0) 1713 (opt-p (memq byte-optimize-log '(t lap))) 1714 str deleted) 1715 (while (and (setq tmp (cdr tmp)) 1716 (not (eq 'TAG (car (car tmp))))) 1717 (if opt-p (setq deleted (cons (car tmp) deleted) 1718 str (concat str " %s") 1719 i (1+ i)))) 1720 (if opt-p 1721 (let ((tagstr 1722 (if (eq 'TAG (car (car tmp))) 1723 (format "%d:" (car (cdr (car tmp)))) 1724 (or (car tmp) "")))) 1725 (if (< i 6) 1726 (apply 'byte-compile-log-lap-1 1727 (concat " %s" str 1728 " %s\t-->\t%s <deleted> %s") 1729 lap0 1730 (nconc (nreverse deleted) 1731 (list tagstr lap0 tagstr))) 1732 (byte-compile-log-lap 1733 " %s <%d unreachable op%s> %s\t-->\t%s <deleted> %s" 1734 lap0 i (if (= i 1) "" "s") 1735 tagstr lap0 tagstr)))) 1736 (rplacd rest tmp)) 1737 (setq keep-going t)) 1738 ;; 1739 ;; <safe-op> unbind --> unbind <safe-op> 1740 ;; (this may enable other optimizations.) 1741 ;; 1742 ((and (eq 'byte-unbind (car lap1)) 1743 (memq (car lap0) byte-after-unbind-ops)) 1744 (byte-compile-log-lap " %s %s\t-->\t%s %s" lap0 lap1 lap1 lap0) 1745 (setcar rest lap1) 1746 (setcar (cdr rest) lap0) 1747 (setq keep-going t)) 1748 ;; 1749 ;; varbind-X unbind-N --> discard unbind-(N-1) 1750 ;; save-excursion unbind-N --> unbind-(N-1) 1751 ;; save-restriction unbind-N --> unbind-(N-1) 1752 ;; 1753 ((and (eq 'byte-unbind (car lap1)) 1754 (memq (car lap0) '(byte-varbind byte-save-excursion 1755 byte-save-restriction)) 1756 (< 0 (cdr lap1))) 1757 (if (zerop (setcdr lap1 (1- (cdr lap1)))) 1758 (delq lap1 rest)) 1759 (if (eq (car lap0) 'byte-varbind) 1760 (setcar rest (cons 'byte-discard 0)) 1761 (setq lap (delq lap0 lap))) 1762 (byte-compile-log-lap " %s %s\t-->\t%s %s" 1763 lap0 (cons (car lap1) (1+ (cdr lap1))) 1764 (if (eq (car lap0) 'byte-varbind) 1765 (car rest) 1766 (car (cdr rest))) 1767 (if (and (/= 0 (cdr lap1)) 1768 (eq (car lap0) 'byte-varbind)) 1769 (car (cdr rest)) 1770 "")) 1771 (setq keep-going t)) 1772 ;; 1773 ;; goto*-X ... X: goto-Y --> goto*-Y 1774 ;; goto-X ... X: return --> return 1775 ;; 1776 ((and (memq (car lap0) byte-goto-ops) 1777 (memq (car (setq tmp (nth 1 (memq (cdr lap0) lap)))) 1778 '(byte-goto byte-return))) 1779 (cond ((and (not (eq tmp lap0)) 1780 (or (eq (car lap0) 'byte-goto) 1781 (eq (car tmp) 'byte-goto))) 1782 (byte-compile-log-lap " %s [%s]\t-->\t%s" 1783 (car lap0) tmp tmp) 1784 (if (eq (car tmp) 'byte-return) 1785 (setcar lap0 'byte-return)) 1786 (setcdr lap0 (cdr tmp)) 1787 (setq keep-going t)))) 1788 ;; 1789 ;; goto-*-else-pop X ... X: goto-if-* --> whatever 1790 ;; goto-*-else-pop X ... X: discard --> whatever 1791 ;; 1792 ((and (memq (car lap0) '(byte-goto-if-nil-else-pop 1793 byte-goto-if-not-nil-else-pop)) 1794 (memq (car (car (setq tmp (cdr (memq (cdr lap0) lap))))) 1795 (eval-when-compile 1796 (cons 'byte-discard byte-conditional-ops))) 1797 (not (eq lap0 (car tmp)))) 1798 (setq tmp2 (car tmp)) 1799 (setq tmp3 (assq (car lap0) '((byte-goto-if-nil-else-pop 1800 byte-goto-if-nil) 1801 (byte-goto-if-not-nil-else-pop 1802 byte-goto-if-not-nil)))) 1803 (if (memq (car tmp2) tmp3) 1804 (progn (setcar lap0 (car tmp2)) 1805 (setcdr lap0 (cdr tmp2)) 1806 (byte-compile-log-lap " %s-else-pop [%s]\t-->\t%s" 1807 (car lap0) tmp2 lap0)) 1808 ;; Get rid of the -else-pop's and jump one step further. 1809 (or (eq 'TAG (car (nth 1 tmp))) 1810 (setcdr tmp (cons (byte-compile-make-tag) 1811 (cdr tmp)))) 1812 (byte-compile-log-lap " %s [%s]\t-->\t%s <skip>" 1813 (car lap0) tmp2 (nth 1 tmp3)) 1814 (setcar lap0 (nth 1 tmp3)) 1815 (setcdr lap0 (nth 1 tmp))) 1816 (setq keep-going t)) 1817 ;; 1818 ;; const goto-X ... X: goto-if-* --> whatever 1819 ;; const goto-X ... X: discard --> whatever 1820 ;; 1821 ((and (eq (car lap0) 'byte-constant) 1822 (eq (car lap1) 'byte-goto) 1823 (memq (car (car (setq tmp (cdr (memq (cdr lap1) lap))))) 1824 (eval-when-compile 1825 (cons 'byte-discard byte-conditional-ops))) 1826 (not (eq lap1 (car tmp)))) 1827 (setq tmp2 (car tmp)) 1828 (cond ((memq (car tmp2) 1829 (if (null (car (cdr lap0))) 1830 '(byte-goto-if-nil byte-goto-if-nil-else-pop) 1831 '(byte-goto-if-not-nil 1832 byte-goto-if-not-nil-else-pop))) 1833 (byte-compile-log-lap " %s goto [%s]\t-->\t%s %s" 1834 lap0 tmp2 lap0 tmp2) 1835 (setcar lap1 (car tmp2)) 1836 (setcdr lap1 (cdr tmp2)) 1837 ;; Let next step fix the (const,goto-if*) sequence. 1838 (setq rest (cons nil rest))) 1839 (t 1840 ;; Jump one step further 1841 (byte-compile-log-lap 1842 " %s goto [%s]\t-->\t<deleted> goto <skip>" 1843 lap0 tmp2) 1844 (or (eq 'TAG (car (nth 1 tmp))) 1845 (setcdr tmp (cons (byte-compile-make-tag) 1846 (cdr tmp)))) 1847 (setcdr lap1 (car (cdr tmp))) 1848 (setq lap (delq lap0 lap)))) 1849 (setq keep-going t)) 1850 ;; 1851 ;; X: varref-Y ... varset-Y goto-X --> 1852 ;; X: varref-Y Z: ... dup varset-Y goto-Z 1853 ;; (varset-X goto-BACK, BACK: varref-X --> copy the varref down.) 1854 ;; (This is so usual for while loops that it is worth handling). 1855 ;; 1856 ((and (eq (car lap1) 'byte-varset) 1857 (eq (car lap2) 'byte-goto) 1858 (not (memq (cdr lap2) rest)) ;Backwards jump 1859 (eq (car (car (setq tmp (cdr (memq (cdr lap2) lap))))) 1860 'byte-varref) 1861 (eq (cdr (car tmp)) (cdr lap1)) 1862 (not (memq (car (cdr lap1)) byte-boolean-vars))) 1863 ;;(byte-compile-log-lap " Pulled %s to end of loop" (car tmp)) 1864 (let ((newtag (byte-compile-make-tag))) 1865 (byte-compile-log-lap 1866 " %s: %s ... %s %s\t-->\t%s: %s %s: ... %s %s %s" 1867 (nth 1 (cdr lap2)) (car tmp) 1868 lap1 lap2 1869 (nth 1 (cdr lap2)) (car tmp) 1870 (nth 1 newtag) 'byte-dup lap1 1871 (cons 'byte-goto newtag) 1872 ) 1873 (setcdr rest (cons (cons 'byte-dup 0) (cdr rest))) 1874 (setcdr tmp (cons (setcdr lap2 newtag) (cdr tmp)))) 1875 (setq add-depth 1) 1876 (setq keep-going t)) 1877 ;; 1878 ;; goto-X Y: ... X: goto-if*-Y --> goto-if-not-*-X+1 Y: 1879 ;; (This can pull the loop test to the end of the loop) 1880 ;; 1881 ((and (eq (car lap0) 'byte-goto) 1882 (eq (car lap1) 'TAG) 1883 (eq lap1 1884 (cdr (car (setq tmp (cdr (memq (cdr lap0) lap)))))) 1885 (memq (car (car tmp)) 1886 '(byte-goto byte-goto-if-nil byte-goto-if-not-nil 1887 byte-goto-if-nil-else-pop))) 1888;; (byte-compile-log-lap " %s %s, %s %s --> moved conditional" 1889;; lap0 lap1 (cdr lap0) (car tmp)) 1890 (let ((newtag (byte-compile-make-tag))) 1891 (byte-compile-log-lap 1892 "%s %s: ... %s: %s\t-->\t%s ... %s:" 1893 lap0 (nth 1 lap1) (nth 1 (cdr lap0)) (car tmp) 1894 (cons (cdr (assq (car (car tmp)) 1895 '((byte-goto-if-nil . byte-goto-if-not-nil) 1896 (byte-goto-if-not-nil . byte-goto-if-nil) 1897 (byte-goto-if-nil-else-pop . 1898 byte-goto-if-not-nil-else-pop) 1899 (byte-goto-if-not-nil-else-pop . 1900 byte-goto-if-nil-else-pop)))) 1901 newtag) 1902 1903 (nth 1 newtag) 1904 ) 1905 (setcdr tmp (cons (setcdr lap0 newtag) (cdr tmp))) 1906 (if (eq (car (car tmp)) 'byte-goto-if-nil-else-pop) 1907 ;; We can handle this case but not the -if-not-nil case, 1908 ;; because we won't know which non-nil constant to push. 1909 (setcdr rest (cons (cons 'byte-constant 1910 (byte-compile-get-constant nil)) 1911 (cdr rest)))) 1912 (setcar lap0 (nth 1 (memq (car (car tmp)) 1913 '(byte-goto-if-nil-else-pop 1914 byte-goto-if-not-nil 1915 byte-goto-if-nil 1916 byte-goto-if-not-nil 1917 byte-goto byte-goto)))) 1918 ) 1919 (setq keep-going t)) 1920 ) 1921 (setq rest (cdr rest))) 1922 ) 1923 ;; Cleanup stage: 1924 ;; Rebuild byte-compile-constants / byte-compile-variables. 1925 ;; Simple optimizations that would inhibit other optimizations if they 1926 ;; were done in the optimizing loop, and optimizations which there is no 1927 ;; need to do more than once. 1928 (setq byte-compile-constants nil 1929 byte-compile-variables nil) 1930 (setq rest lap) 1931 (while rest 1932 (setq lap0 (car rest) 1933 lap1 (nth 1 rest)) 1934 (if (memq (car lap0) byte-constref-ops) 1935 (if (or (eq (car lap0) 'byte-constant) 1936 (eq (car lap0) 'byte-constant2)) 1937 (unless (memq (cdr lap0) byte-compile-constants) 1938 (setq byte-compile-constants (cons (cdr lap0) 1939 byte-compile-constants))) 1940 (unless (memq (cdr lap0) byte-compile-variables) 1941 (setq byte-compile-variables (cons (cdr lap0) 1942 byte-compile-variables))))) 1943 (cond (;; 1944 ;; const-C varset-X const-C --> const-C dup varset-X 1945 ;; const-C varbind-X const-C --> const-C dup varbind-X 1946 ;; 1947 (and (eq (car lap0) 'byte-constant) 1948 (eq (car (nth 2 rest)) 'byte-constant) 1949 (eq (cdr lap0) (cdr (nth 2 rest))) 1950 (memq (car lap1) '(byte-varbind byte-varset))) 1951 (byte-compile-log-lap " %s %s %s\t-->\t%s dup %s" 1952 lap0 lap1 lap0 lap0 lap1) 1953 (setcar (cdr (cdr rest)) (cons (car lap1) (cdr lap1))) 1954 (setcar (cdr rest) (cons 'byte-dup 0)) 1955 (setq add-depth 1)) 1956 ;; 1957 ;; const-X [dup/const-X ...] --> const-X [dup ...] dup 1958 ;; varref-X [dup/varref-X ...] --> varref-X [dup ...] dup 1959 ;; 1960 ((memq (car lap0) '(byte-constant byte-varref)) 1961 (setq tmp rest 1962 tmp2 nil) 1963 (while (progn 1964 (while (eq 'byte-dup (car (car (setq tmp (cdr tmp)))))) 1965 (and (eq (cdr lap0) (cdr (car tmp))) 1966 (eq (car lap0) (car (car tmp))))) 1967 (setcar tmp (cons 'byte-dup 0)) 1968 (setq tmp2 t)) 1969 (if tmp2 1970 (byte-compile-log-lap 1971 " %s [dup/%s]...\t-->\t%s dup..." lap0 lap0 lap0))) 1972 ;; 1973 ;; unbind-N unbind-M --> unbind-(N+M) 1974 ;; 1975 ((and (eq 'byte-unbind (car lap0)) 1976 (eq 'byte-unbind (car lap1))) 1977 (byte-compile-log-lap " %s %s\t-->\t%s" lap0 lap1 1978 (cons 'byte-unbind 1979 (+ (cdr lap0) (cdr lap1)))) 1980 (setq keep-going t) 1981 (setq lap (delq lap0 lap)) 1982 (setcdr lap1 (+ (cdr lap1) (cdr lap0)))) 1983 ) 1984 (setq rest (cdr rest))) 1985 (setq byte-compile-maxdepth (+ byte-compile-maxdepth add-depth))) 1986 lap) 1987 1988(provide 'byte-opt) 1989 1990 1991;; To avoid "lisp nesting exceeds max-lisp-eval-depth" when this file compiles 1992;; itself, compile some of its most used recursive functions (at load time). 1993;; 1994(eval-when-compile 1995 (or (byte-code-function-p (symbol-function 'byte-optimize-form)) 1996 (assq 'byte-code (symbol-function 'byte-optimize-form)) 1997 (let ((byte-optimize nil) 1998 (byte-compile-warnings nil)) 1999 (mapcar (lambda (x) 2000 (or noninteractive (message "compiling %s..." x)) 2001 (byte-compile x) 2002 (or noninteractive (message "compiling %s...done" x))) 2003 '(byte-optimize-form 2004 byte-optimize-body 2005 byte-optimize-predicate 2006 byte-optimize-binary-predicate 2007 ;; Inserted some more than necessary, to speed it up. 2008 byte-optimize-form-code-walker 2009 byte-optimize-lapcode)))) 2010 nil) 2011 2012;; arch-tag: 0f14076b-737e-4bef-aae6-908826ec1ff1 2013;;; byte-opt.el ends here 2014