* Small LAP peephole optimization
@ 2007-05-09 10:19 Dmitry Antipov
2007-05-09 16:54 ` Ken Raeburn
2007-05-09 21:34 ` Richard Stallman
0 siblings, 2 replies; 5+ messages in thread
From: Dmitry Antipov @ 2007-05-09 10:19 UTC (permalink / raw)
To: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 733 bytes --]
Hello again,
this is a minor LAP peephole optimization intended to remove redundant
'(byte-constant 0) (byte-plus . 0)' byte code insns. As an obvious
example, for
(disassemble (byte-compile '(lambda (x y) (+ x (* 2 y)))))
it will produce
0 varref x
1 varref y
2 dup
3 plus
4 plus
5 return
instead of current
0 varref x
1 varref y
2 dup
3 plus
4 constant 0
5 plus
6 plus
7 return
During full bootstrap, this small optimization is performed for more
than 100 LAPs, thus removing ~400 byte code insns. It was also tested by
byte-force-recompile of all lisp, and hopefully it works.
There are also a few cosmetic cleanups.
Dmitry
[-- Attachment #2: byte_opt_const_0_plus.patch --]
[-- Type: text/plain, Size: 2785 bytes --]
Index: lisp/emacs-lisp/byte-opt.el
===================================================================
RCS file: /sources/emacs/emacs/lisp/emacs-lisp/byte-opt.el,v
retrieving revision 1.94
diff -u -r1.94 byte-opt.el
--- lisp/emacs-lisp/byte-opt.el 11 Apr 2007 17:10:42 -0000 1.94
+++ lisp/emacs-lisp/byte-opt.el 9 May 2007 06:43:58 -0000
@@ -1526,6 +1526,21 @@
(setcdr lap0 0))
((error "Optimizer error: too much on the stack"))))
;;
+ ;; constant 0 plus --> <deleted>
+ ;;
+ ((and (eq (car lap0) 'byte-constant)
+ (numberp (cadr lap0))
+ (zerop (cadr lap0))
+ (eq (car lap1) 'byte-plus))
+ (let ((tmp lap) (head nil))
+ (while (not (eq lap0 (car tmp)))
+ (setq head (append head (list (car tmp)))
+ tmp (cdr tmp)))
+ (byte-compile-log-lap " %s %s\t-->\t<deleted>" lap0 lap1)
+ (setq rest (cddr rest)
+ lap (nconc head rest)
+ keep-going t)))
+ ;;
;; goto*-X X: --> X:
;;
((and (memq (car lap0) byte-goto-ops)
@@ -1537,10 +1552,9 @@
(setcar lap0 (setq tmp 'byte-discard))
(setcdr lap0 0))
((error "Depth conflict at tag %d" (nth 2 lap0))))
- (and (memq byte-optimize-log '(t byte))
- (byte-compile-log " (goto %s) %s:\t-->\t%s %s:"
- (nth 1 lap1) (nth 1 lap1)
- tmp (nth 1 lap1)))
+ (byte-compile-log-lap " (goto %s) %s:\t-->\t%s %s:"
+ (nth 1 lap1) (nth 1 lap1)
+ tmp (nth 1 lap1))
(setq keep-going t))
;;
;; varset-X varref-X --> dup varset-X
@@ -1672,8 +1686,8 @@
(while (not (eq tmp tmp2))
(setq tmp2 (cdr tmp2)
str (concat str " dup")))
- (byte-compile-log-lap " %s%s %s\t-->\t%s%s dup"
- lap0 str lap0 lap0 str)))
+ (byte-compile-log-lap-1 " %s%s %s\t-->\t%s%s dup"
+ lap0 str lap0 lap0 str)))
(setq keep-going t)
(setcar (car tmp) 'byte-dup)
(setcdr (car tmp) 0)
@@ -1684,9 +1698,8 @@
;;
((and (eq (car lap0) 'TAG)
(eq (car lap1) 'TAG))
- (and (memq byte-optimize-log '(t byte))
- (byte-compile-log " adjacent tags %d and %d merged"
- (nth 1 lap1) (nth 1 lap0)))
+ (byte-compile-log-lap " adjacent tags %d and %d merged"
+ (nth 1 lap1) (nth 1 lap0))
(setq tmp3 lap)
(while (setq tmp2 (rassq lap0 tmp3))
(setcdr tmp2 lap1)
@@ -1698,8 +1711,7 @@
;;
((and (eq 'TAG (car lap0))
(not (rassq lap0 lap)))
- (and (memq byte-optimize-log '(t byte))
- (byte-compile-log " unused tag %d removed" (nth 1 lap0)))
+ (byte-compile-log-lap " unused tag %d removed" (nth 1 lap0))
(setq lap (delq lap0 lap)
keep-going t))
;;
[-- Attachment #3: Type: text/plain, Size: 142 bytes --]
_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/emacs-devel
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Small LAP peephole optimization
2007-05-09 10:19 Small LAP peephole optimization Dmitry Antipov
@ 2007-05-09 16:54 ` Ken Raeburn
2007-05-10 14:21 ` Dmitry Antipov
2007-05-09 21:34 ` Richard Stallman
1 sibling, 1 reply; 5+ messages in thread
From: Ken Raeburn @ 2007-05-09 16:54 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: emacs-devel
On May 9, 2007, at 06:19, Dmitry Antipov wrote:
> Hello again,
>
> this is a minor LAP peephole optimization intended to remove redundant
> '(byte-constant 0) (byte-plus . 0)' byte code insns. As an obvious
> example, for
>
> (disassemble (byte-compile '(lambda (x y) (+ x (* 2 y)))))
>
> it will produce
>
> 0 varref x
> 1 varref y
> 2 dup
> 3 plus
> 4 plus
> 5 return
>
> instead of current
>
> 0 varref x
> 1 varref y
> 2 dup
> 3 plus
> 4 constant 0
> 5 plus
> 6 plus
> 7 return
This looks like a nice little optimization, yes. But consider that
+0 is not always a no-op. If the other value is not numeric, an
error will be thrown, and in fact you could use the one-argument form
of + as a cheap way to test for a numeric value. So, in a less
obvious example:
(defun foo (x y) (+ (quux 2 y)))
becomes:
byte code for foo:
args: (x y)
0 constant quux
1 constant 2
2 varref y
3 call 2
4 constant 0
5 plus
6 return
Now if the author of "foo" isn't sure that "quux" is going to return
a numeric value, removing the addition changes the semantics of "foo".
> During full bootstrap, this small optimization is performed for more
> than 100 LAPs, thus removing ~400 byte code insns. It was also
> tested by
> byte-force-recompile of all lisp, and hopefully it works.
I would guess that in most of these cases it's a safe optimization,
but you should really check. If the previous operation is guaranteed
to leave a numeric value at the top of the stack, as in your example,
and no other code can branch to the +0 sequence, then you can do the
optimization; otherwise, you probably shouldn't. (An opcode like
plus that generates a numeric value if it doesn't throw an error is
easy. Harder is figuring out after popping values off the stack
whether the next value left at the top is numeric, especially in the
face of branches.)
Ken
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Small LAP peephole optimization
2007-05-09 16:54 ` Ken Raeburn
@ 2007-05-10 14:21 ` Dmitry Antipov
2007-05-10 20:10 ` Ken Raeburn
0 siblings, 1 reply; 5+ messages in thread
From: Dmitry Antipov @ 2007-05-10 14:21 UTC (permalink / raw)
To: Ken Raeburn; +Cc: emacs-devel
Ken Raeburn wrote:
> Now if the author of "foo" isn't sure that "quux" is going to return a
> numeric value, removing the addition changes the semantics of "foo".
Yes. I understand this myself after a short meditation around the comment
above 'byte-compile-associative' :-).
> I would guess that in most of these cases it's a safe optimization, but
> you should really check.
What do you think about such 'unsafe' optimizations in general ? As I know,
some CL systems (such as from Franz) allows byte compiler to be very aggressive
at the cost of safety.
> If the previous operation is guaranteed to leave a numeric value at the top
> of the stack, as in your example, and no other code can branch to the +0 sequence,
> then you can do the optimization; otherwise, you probably shouldn't.
As I understand, branching to +0 is impossible if there is no TAG between
previous byteop an (byte-constant 0), so we might safely optimize the
sequences like
<numeric-on-top-op> (byte-constant 0) (byte-plus . 0) -> <numeric-on-top-op>
Less obvious cases are also interesting, but I'm not sure that saving 2 ops
might push someone to implement substantially more complex logic.
Dmitry
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Small LAP peephole optimization
2007-05-10 14:21 ` Dmitry Antipov
@ 2007-05-10 20:10 ` Ken Raeburn
0 siblings, 0 replies; 5+ messages in thread
From: Ken Raeburn @ 2007-05-10 20:10 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: emacs-devel
On May 10, 2007, at 10:21, Dmitry Antipov wrote:
> What do you think about such 'unsafe' optimizations in general ? As
> I know,
> some CL systems (such as from Franz) allows byte compiler to be
> very aggressive
> at the cost of safety.
Generally, in the absence of either a directive from the code author
saying such assumptions are valid, or some language spec (or other
documentation readily available to the code authors) that says that
such assumptions may be made in compilation, I don't think such
optimizations to valid code are a good idea.
> As I understand, branching to +0 is impossible if there is no TAG
> between
> previous byteop an (byte-constant 0), so we might safely optimize the
> sequences like
>
> <numeric-on-top-op> (byte-constant 0) (byte-plus . 0) -> <numeric-
> on-top-op>
I'm not familiar with the representation of byte code in the
compiler, but if labels are explicit in the sequence so that you can
see that there isn't one there, then yes, that looks correct.
> Less obvious cases are also interesting, but I'm not sure that
> saving 2 ops
> might push someone to implement substantially more complex logic.
Right, probably not worthwhile, at least right now.
Ken
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Small LAP peephole optimization
2007-05-09 10:19 Small LAP peephole optimization Dmitry Antipov
2007-05-09 16:54 ` Ken Raeburn
@ 2007-05-09 21:34 ` Richard Stallman
1 sibling, 0 replies; 5+ messages in thread
From: Richard Stallman @ 2007-05-09 21:34 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: emacs-devel
400 instructions is a small saving, but I am not against this if
others want to install it. However, it is big enough that we would
need legal papers to install it.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2007-05-10 20:10 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-05-09 10:19 Small LAP peephole optimization Dmitry Antipov
2007-05-09 16:54 ` Ken Raeburn
2007-05-10 14:21 ` Dmitry Antipov
2007-05-10 20:10 ` Ken Raeburn
2007-05-09 21:34 ` Richard Stallman
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).