Floating-point constant folding in Emacs byte compiler

Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 1085 bytes --]

While preparing and installing the attached patch to Emacs master, I 
noticed that the byte optimizer assumes that floating-point arithmetic 
behaves the same at compile-time that it does at runtime. For example, 
on my x86-64 platform the byte compiler optimizes (/ 0 0.0) to -NaN, (- 
1 1.0000000000000001) to 0.0, and (< 1 1.0000000000000001) to nil, even 
though these expressions will evaluate to different values on (say) an 
IBM mainframe that uses IBM floating point, and the first expression 
yields +NaN on some IEEE platforms (e.g., ARM).

These discrepancies mean that .elc files containing floating-point 
constants might not be platform-independent, in that byte-compiling a 
file on one machine X and running it on another machine Y can yield 
different results than byte-compiling and running the same file on Y. Is 
this sort of discrepancy intended? If so, should it be documented in the 
Emacs Lisp manual? On the one hand, I doubt whether this sort of 
optimization buys us much performance; on the other, I doubt whether 
many users care about the discrepancies.


[-- Attachment #2: 0001-Fix-byte-opt-lists-of-pure-functions-etc.txt --]
[-- Type: text/plain, Size: 5339 bytes --]

From 3b1024ac8162a66cc6baf6f7f339d9f73bcb6b90 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Thu, 22 Mar 2018 11:25:42 -0700
Subject: [PATCH] Fix byte-opt lists of pure functions etc.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This fixes a bug where a byte-compiler running on 64-bit Emacs
optimized (lsh -1 -1) to #x1fffffffffffffff, an optimization
that is incorrect for .elc files intended for either 32- or
64-bit Emacs.  While I was in the neighborhood, I noticed other
glitches in the lists of pure and side-effect-free functions, and
fixed the errors that I found.
* lisp/emacs-lisp/byte-opt.el (side-effect-free-fns):
Move some functions here from side-effect-and-error-free-fns,
since they can now signal errors.  The affected functions are
current-time-string, current-time-zone,
line-beginning-position, line-end-position.  Rename langinfo
to locale-info.  Add logcount.  Remove string-to-int.
(side-effect-and-error-free-fns): Remove minibuffer-window, a
function that can signal errors, and that is already in
side-effect-free-fns.
(pure-fns): Remove ash, lsh, and logb, since they are
platform-dependent and .elc files should be
platform-independent.  Add %, logand, logcount.  Sort.
Clarify what is meant by “pure”.
---
 lisp/emacs-lisp/byte-opt.el | 37 +++++++++++++++++++++++--------------
 1 file changed, 23 insertions(+), 14 deletions(-)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index a316364761..55343e1e3a 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -1186,6 +1186,7 @@ byte-optimize-set
 	 char-equal char-to-string char-width compare-strings
 	 compare-window-configurations concat coordinates-in-window-p
 	 copy-alist copy-sequence copy-marker cos count-lines
+	 current-time-string current-time-zone
 	 decode-char
 	 decode-time default-boundp default-value documentation downcase
 	 elt encode-char exp expt encode-time error-message-string
@@ -1199,8 +1200,9 @@ byte-optimize-set
 	 hash-table-count
 	 int-to-string intern-soft
 	 keymap-parent
-	 length local-variable-if-set-p local-variable-p log log10 logand
-	 logb logior lognot logxor lsh langinfo
+	 length line-beginning-position line-end-position
+	 local-variable-if-set-p local-variable-p locale-info
+	 log log10 logand logb logcount logior lognot logxor lsh
 	 make-list make-string make-symbol marker-buffer max member memq min
 	 minibuffer-selected-window minibuffer-window
 	 mod multibyte-char-to-unibyte next-window nth nthcdr number-to-string
@@ -1210,7 +1212,7 @@ byte-optimize-set
 	 radians-to-degrees rassq rassoc read-from-string regexp-quote
 	 region-beginning region-end reverse round
 	 sin sqrt string string< string= string-equal string-lessp string-to-char
-	 string-to-int string-to-number substring
+	 string-to-number substring
 	 sxhash sxhash-equal sxhash-eq sxhash-eql
 	 symbol-function symbol-name symbol-plist symbol-value string-make-unibyte
 	 string-make-multibyte string-as-multibyte string-as-unibyte
@@ -1240,7 +1242,6 @@ byte-optimize-set
 	 charsetp commandp cons consp
 	 current-buffer current-global-map current-indentation
 	 current-local-map current-minor-mode-maps current-time
-	 current-time-string current-time-zone
 	 eobp eolp eq equal eventp
 	 floatp following-char framep
 	 get-largest-window get-lru-window
@@ -1248,9 +1249,9 @@ byte-optimize-set
 	 identity ignore integerp integer-or-marker-p interactive-p
 	 invocation-directory invocation-name
 	 keymapp keywordp
-	 line-beginning-position line-end-position list listp
+	 list listp
 	 make-marker mark mark-marker markerp max-char
-	 memory-limit minibuffer-window
+	 memory-limit
 	 mouse-movement-p
 	 natnump nlistp not null number-or-marker-p numberp
 	 one-window-p overlayp
@@ -1275,16 +1276,24 @@ byte-optimize-set
   nil)
 
 \f
-;; pure functions are side-effect free functions whose values depend
-;; only on their arguments. For these functions, calls with constant
-;; arguments can be evaluated at compile time. This may shift run time
-;; errors to compile time.
+;; Pure functions are side-effect free functions whose values depend
+;; only on their arguments, not on the platform.  For these functions,
+;; calls with constant arguments can be evaluated at compile time.
+;; This may shift runtime errors to compile time.  For example, logand
+;; is pure since its results are machine-independent, whereas ash is
+;; not pure because (ash 1 29)'s value depends on machine word size.
+;;
+;; When deciding whether a function is pure, do not worry about
+;; mutable strings or markers, as they are so unlikely in real code
+;; that they are not worth worrying about.  Thus string-to-char is
+;; pure even though it might return different values if a string is
+;; changed, and logand is pure even though it might return different
+;; values if a marker is moved.
 
 (let ((pure-fns
-       '(concat symbol-name regexp-opt regexp-quote string-to-syntax
-         string-to-char
-         ash lsh logb lognot logior logxor
-         ceiling floor)))
+       '(% concat logand logcount logior lognot logxor
+	 regexp-opt regexp-quote
+	 string-to-char string-to-syntax symbol-name)))
   (while pure-fns
     (put (car pure-fns) 'pure t)
     (setq pure-fns (cdr pure-fns)))
-- 
2.14.3

Re: Floating-point constant folding in Emacs byte compiler

[Stefan Monnier]

> These discrepancies mean that .elc files containing floating-point constants
> might not be platform-independent, in that byte-compiling a file on one
> machine X and running it on another machine Y can yield different results
> than byte-compiling and running the same file on Y. Is this sort of
> discrepancy intended?

I'm pretty sure those runtime differences are not on-purpose, so whether
they show up at run-time or compile-time doesn't matter.
IOW we can keep optimizing those.


        Stefan

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

Stefan Monnier wrote:
> I'm pretty sure those runtime differences are not on-purpose

Although that's most likely true for the examples I gave, it's a problematic 
assumption for code that intentionally inspects runtime behavior.

I mention this because my recently-installed byte-opt patch fixed a problem of 
this sort with lsh. byte-opt was evaluating (lsh -1 -1) at compile-time, whereas 
the intent of the (lsh -1 -1) was to calculate most-positive-fixnum at run-time. 
It's not hard to imagine similar sorts of code to inspect properties of the 
machine's floating-point behavior, code that would yield the wrong value if 
compiled on a machine with different floating-point properties.

Nowadays Emacs hosts almost invariably use IEEE floating point, and I suppose we 
could hardwire that assumption into Emacs. Even so, IEEE floating-point is not 
bit-for-bit identical on all platforms, so if we're constant-folding 
floating-point expressions surely we should at least document that we're doing 
so, so that programmers know that they can't rely on constant expressions 
yielding a different value than what run-time evaluation would deliver.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Thu, 22 Mar 2018 21:26:00 -0400
> 
> > These discrepancies mean that .elc files containing floating-point constants
> > might not be platform-independent, in that byte-compiling a file on one
> > machine X and running it on another machine Y can yield different results
> > than byte-compiling and running the same file on Y. Is this sort of
> > discrepancy intended?
> 
> I'm pretty sure those runtime differences are not on-purpose, so whether
> they show up at run-time or compile-time doesn't matter.
> IOW we can keep optimizing those.

I don't understand your conclusion: if this is unintended, then IMO we
should stop optimizing these, so that byte code is more portable.  Or
am I missing something?

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Thu, 22 Mar 2018 22:22:25 -0700
> 
> Nowadays Emacs hosts almost invariably use IEEE floating point, and I suppose we 
> could hardwire that assumption into Emacs. Even so, IEEE floating-point is not 
> bit-for-bit identical on all platforms, so if we're constant-folding 
> floating-point expressions surely we should at least document that we're doing 
> so, so that programmers know that they can't rely on constant expressions 
> yielding a different value than what run-time evaluation would deliver.

I think we should strive to leave the byte code platform-independent.
If nothing else, it will make sure the *.elc files in a release
tarball can be used on all supported platforms with identical
results.  Otherwise, we will need to byte-compile files at build time,
something that will make the build much longer than it should be.

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 889 bytes --]

On 03/23/2018 01:24 AM, Eli Zaretskii wrote:
> I think we should strive to leave the byte code platform-independent.

That's my thought as well. The byte-compiler was taking the Fortran 
attitude that if an optimization would be allowed on an 
infinite-precision machine, then do it even if it results in different 
answers on real machines due to rounding error or overflow. This loses 
predictability and means that .elc files are not machine-independent. 
Althopugh performance trumps predictability for Fortran, predictability 
is more important for Emacs, as its users will not notice any 
performance loss but they might be affected by the differing answers.

I took a quick look through the byte optimizer and removed the 
Fortran-style floating-point optimizations that I found, by installing 
the attached. This doesn't seem to affect performance significantly on 
Emacs itself.


[-- Attachment #2: 0001-Avoid-Fortran-style-floating-point-optimization.patch --]
[-- Type: text/x-patch, Size: 11689 bytes --]

From 34a2afa85daf513631512309f01aea55f77f6fec Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Fri, 23 Mar 2018 12:57:39 -0700
Subject: [PATCH] Avoid Fortran-style floating-point optimization

When optimizing arithmetic operations, avoid optimizations that
are valid for mathematical numbers but invalid for floating-point.
For example, do not optimize (+ 1 v 0.5) to (+ v 1.5), as they may
not be the same due to rounding errors.  In general,
floating-point numbers cannot be constant-folded, since that would
make .elc files platform-dependent.
* lisp/emacs-lisp/byte-opt.el (byte-optimize-associative-math):
Do not optimize floats.
(byte-optimize-nonassociative-math, byte-optimize-approx-equal)
(byte-optimize-delay-constants-math, byte-compile-butlast)
(byte-optimize-logmumble):
Remove; no longer used.
(byte-optimize-minus): Do not optimize (- 0 x) to (- x).
(byte-optimize-multiply): Do not optimize (* -1 x) to (- x).
(byte-optimize-divide): Do not optimize (/ x -1) to (- x).
(logand, logior, logxor): Optimize with byte-optimize-predicate
instead of with byte-optimize-logmumble.
* test/lisp/emacs-lisp/bytecomp-tests.el:
(byte-opt-testsuite-arith-data): Add a couple of test cases.
---
 lisp/emacs-lisp/byte-opt.el            | 168 ++++-----------------------------
 test/lisp/emacs-lisp/bytecomp-tests.el |   6 +-
 2 files changed, 24 insertions(+), 150 deletions(-)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 55343e1e3a..a5e0e21964 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -656,15 +656,15 @@ byte-compile-nilconstp
         ((not (symbolp form)) nil)
         ((null form))))
 
-;; If the function is being called with constant numeric args,
+;; If the function is being called with constant integer args,
 ;; evaluate as much as possible at compile-time.  This optimizer
-;; assumes that the function is associative, like + or *.
+;; assumes that the function is associative, like min or max.
 (defun byte-optimize-associative-math (form)
   (let ((args nil)
 	(constants nil)
 	(rest (cdr form)))
     (while rest
-      (if (numberp (car rest))
+      (if (integerp (car rest))
 	  (setq constants (cons (car rest) constants))
 	  (setq args (cons (car rest) args)))
       (setq rest (cdr rest)))
@@ -678,82 +678,7 @@ byte-optimize-associative-math
 	    (apply (car form) constants))
 	form)))
 
-;; If the function is being called with constant numeric args,
-;; evaluate as much as possible at compile-time.  This optimizer
-;; assumes that the function satisfies
-;;   (op x1 x2 ... xn) == (op ...(op (op x1 x2) x3) ...xn)
-;; like - and /.
-(defun byte-optimize-nonassociative-math (form)
-  (if (or (not (numberp (car (cdr form))))
-	  (not (numberp (car (cdr (cdr form))))))
-      form
-    (let ((constant (car (cdr form)))
-	  (rest (cdr (cdr form))))
-      (while (numberp (car rest))
-	(setq constant (funcall (car form) constant (car rest))
-	      rest (cdr rest)))
-      (if rest
-	  (cons (car form) (cons constant rest))
-	  constant))))
-
-;;(defun byte-optimize-associative-two-args-math (form)
-;;  (setq form (byte-optimize-associative-math form))
-;;  (if (consp form)
-;;      (byte-optimize-two-args-left form)
-;;      form))
-
-;;(defun byte-optimize-nonassociative-two-args-math (form)
-;;  (setq form (byte-optimize-nonassociative-math form))
-;;  (if (consp form)
-;;      (byte-optimize-two-args-right form)
-;;      form))
-
-(defun byte-optimize-approx-equal (x y)
-  (<= (* (abs (- x y)) 100) (abs (+ x y))))
-
-;; Collect all the constants from FORM, after the STARTth arg,
-;; and apply FUN to them to make one argument at the end.
-;; For functions that can handle floats, that optimization
-;; can be incorrect because reordering can cause an overflow
-;; that would otherwise be avoided by encountering an arg that is a float.
-;; We avoid this problem by (1) not moving float constants and
-;; (2) not moving anything if it would cause an overflow.
-(defun byte-optimize-delay-constants-math (form start fun)
-  ;; Merge all FORM's constants from number START, call FUN on them
-  ;; and put the result at the end.
-  (let ((rest (nthcdr (1- start) form))
-	(orig form)
-	;; t means we must check for overflow.
-	(overflow (memq fun '(+ *))))
-    (while (cdr (setq rest (cdr rest)))
-      (if (integerp (car rest))
-	  (let (constants)
-	    (setq form (copy-sequence form)
-		  rest (nthcdr (1- start) form))
-	    (while (setq rest (cdr rest))
-	      (cond ((integerp (car rest))
-		     (setq constants (cons (car rest) constants))
-		     (setcar rest nil))))
-	    ;; If necessary, check now for overflow
-	    ;; that might be caused by reordering.
-	    (if (and overflow
-		     ;; We have overflow if the result of doing the arithmetic
-		     ;; on floats is not even close to the result
-		     ;; of doing it on integers.
-		     (not (byte-optimize-approx-equal
-			    (apply fun (mapcar 'float constants))
-			    (float (apply fun constants)))))
-		(setq form orig)
-	      (setq form (nconc (delq nil form)
-				(list (apply fun (nreverse constants)))))))))
-    form))
-
-(defsubst byte-compile-butlast (form)
-  (nreverse (cdr (reverse form))))
-
 (defun byte-optimize-plus (form)
-  ;; Don't call `byte-optimize-delay-constants-math' (bug#1334).
-  ;;(setq form (byte-optimize-delay-constants-math form 1 '+))
   (if (memq 0 form) (setq form (delq 0 (copy-sequence form))))
   ;; For (+ constants...), byte-optimize-predicate does the work.
   (when (memq nil (mapcar 'numberp (cdr form)))
@@ -767,26 +692,19 @@ byte-optimize-plus
 	    (setq integer (nth 1 form) other (nth 2 form))
 	  (setq integer (nth 2 form) other (nth 1 form)))
 	(setq form
-	      (list (if (eq integer 1) '1+ '1-) other))))
-     ;; Here, we could also do
-     ;;  (+ x y ... 1) --> (1+ (+ x y ...))
-     ;;  (+ x y ... -1) --> (1- (+ x y ...))
-     ;; The resulting bytecode is smaller, but is it faster? -- cyd
-     ))
+	      (list (if (eq integer 1) '1+ '1-) other))))))
   (byte-optimize-predicate form))
 
 (defun byte-optimize-minus (form)
-  ;; Don't call `byte-optimize-delay-constants-math' (bug#1334).
-  ;;(setq form (byte-optimize-delay-constants-math form 2 '+))
   ;; Remove zeros.
   (when (and (nthcdr 3 form)
 	     (memq 0 (cddr form)))
     (setq form (nconc (list (car form) (cadr form))
 		      (delq 0 (copy-sequence (cddr form)))))
-    ;; After the above, we must turn (- x) back into (- x 0)
+    ;; After the above, we must turn (- x) back into (- x 0).
     (or (cddr form)
 	(setq form (nconc form (list 0)))))
-  ;; For (- constants..), byte-optimize-predicate does the work.
+  ;; For (- constants...), byte-optimize-predicate does the work.
   (when (memq nil (mapcar 'numberp (cdr form)))
     (cond
      ;; (- x 1) --> (1- x)
@@ -794,71 +712,25 @@ byte-optimize-minus
       (setq form (list '1- (nth 1 form))))
      ;; (- x -1) --> (1+ x)
      ((equal (nthcdr 2 form) '(-1))
-      (setq form (list '1+ (nth 1 form))))
-     ;; (- 0 x) --> (- x)
-     ((and (eq (nth 1 form) 0)
-	   (= (length form) 3))
-      (setq form (list '- (nth 2 form))))
-     ;; Here, we could also do
-     ;;  (- x y ... 1) --> (1- (- x y ...))
-     ;;  (- x y ... -1) --> (1+ (- x y ...))
-     ;; The resulting bytecode is smaller, but is it faster? -- cyd
-     ))
+      (setq form (list '1+ (nth 1 form))))))
   (byte-optimize-predicate form))
 
 (defun byte-optimize-multiply (form)
-  (setq form (byte-optimize-delay-constants-math form 1 '*))
-  ;; For (* constants..), byte-optimize-predicate does the work.
-  (when (memq nil (mapcar 'numberp (cdr form)))
-    ;; After `byte-optimize-predicate', if there is a INTEGER constant
-    ;; in FORM, it is in the last element.
-    (let ((last (car (reverse (cdr form)))))
-      (cond
-       ;; Would handling (* ... 0) here cause floating point errors?
-       ;; See bug#1334.
-       ((eq 1 last) (setq form (byte-compile-butlast form)))
-       ((eq -1 last)
-	(setq form (list '- (if (nthcdr 3 form)
-				(byte-compile-butlast form)
-			      (nth 1 form))))))))
+  (if (memq 1 form) (setq form (delq 1 (copy-sequence form))))
+  ;; For (* integers..), byte-optimize-predicate does the work.
   (byte-optimize-predicate form))
 
 (defun byte-optimize-divide (form)
-  (setq form (byte-optimize-delay-constants-math form 2 '*))
-  ;; After `byte-optimize-predicate', if there is a INTEGER constant
-  ;; in FORM, it is in the last element.
-  (let ((last (car (reverse (cdr (cdr form))))))
-    (cond
-     ;; Runtime error (leave it intact).
-     ((or (null last)
-	  (eq last 0)
-	  (memql 0.0 (cddr form))))
-     ;; No constants in expression
-     ((not (numberp last)))
-     ;; For (* constants..), byte-optimize-predicate does the work.
-     ((null (memq nil (mapcar 'numberp (cdr form)))))
-     ;; (/ x y.. 1) --> (/ x y..)
-     ((and (eq last 1) (nthcdr 3 form))
-      (setq form (byte-compile-butlast form)))
-     ;; (/ x -1), (/ x .. -1)  --> (- x), (- (/ x ..))
-     ((eq last -1)
-      (setq form (list '- (if (nthcdr 3 form)
-			      (byte-compile-butlast form)
-			    (nth 1 form)))))))
+  ;; Remove 1s.
+  (when (and (nthcdr 3 form)
+	     (memq 1 (cddr form)))
+    (setq form (nconc (list (car form) (cadr form))
+		      (delq 1 (copy-sequence (cddr form)))))
+    ;; After the above, we must turn (/ x) back into (/ x 1).
+    (or (cddr form)
+	(setq form (nconc form (list 1)))))
   (byte-optimize-predicate form))
 
-(defun byte-optimize-logmumble (form)
-  (setq form (byte-optimize-delay-constants-math form 1 (car form)))
-  (byte-optimize-predicate
-   (cond ((memq 0 form)
-	  (setq form (if (eq (car form) 'logand)
-			 (cons 'progn (cdr form))
-		       (delq 0 (copy-sequence form)))))
-	 ((and (eq (car-safe form) 'logior)
-	       (memq -1 form))
-	  (cons 'progn (cdr form)))
-	 (form))))
-
 
 (defun byte-optimize-binary-predicate (form)
   (cond
@@ -923,9 +795,9 @@ byte-optimize-identity
 (put 'string< 'byte-optimizer 'byte-optimize-predicate)
 (put 'string-lessp 'byte-optimizer 'byte-optimize-predicate)
 
-(put 'logand 'byte-optimizer 'byte-optimize-logmumble)
-(put 'logior 'byte-optimizer 'byte-optimize-logmumble)
-(put 'logxor 'byte-optimizer 'byte-optimize-logmumble)
+(put 'logand 'byte-optimizer 'byte-optimize-predicate)
+(put 'logior 'byte-optimizer 'byte-optimize-predicate)
+(put 'logxor 'byte-optimizer 'byte-optimize-predicate)
 (put 'lognot 'byte-optimizer 'byte-optimize-predicate)
 
 (put 'car 'byte-optimizer 'byte-optimize-predicate)
diff --git a/test/lisp/emacs-lisp/bytecomp-tests.el b/test/lisp/emacs-lisp/bytecomp-tests.el
index 6ae7cdb9f9..7330c67614 100644
--- a/test/lisp/emacs-lisp/bytecomp-tests.el
+++ b/test/lisp/emacs-lisp/bytecomp-tests.el
@@ -38,8 +38,7 @@ byte-opt-testsuite-arith-data
     (let ((a 3) (b 2) (c 1.0))                     (/ a b c))
     (let ((a (+ 1 (expt 2 -64))) (b (expt 2 -65))) (+ a -1 b))
     (let ((a (+ 1 (expt 2 -64))) (b (expt 2 -65))) (- a 1 (- b)))
-    ;; This fails.  Should it be a bug?
-    ;; (let ((a (expt 2 -1074)) (b 0.125))		   (* a 8 b))
+    (let ((a (expt 2 -1074)) (b 0.125))		   (* a 8 b))
     (let ((a 1.0))				   (* a 0))
     (let ((a 1.0))				   (* a 2.0 0))
     (let ((a 1.0))				   (/ 0 a))
@@ -244,6 +243,9 @@ byte-opt-testsuite-arith-data
     (let ((a 3) (b 2) (c 1.0)) (/ a b c 0))
     (let ((a 3) (b 2) (c 1.0)) (/ a b c 1))
     (let ((a 3) (b 2) (c 1.0)) (/ a b c -1))
+
+    (let ((a t)) (logand 0 a))
+
     ;; Test switch bytecode
     (let ((a 3)) (cond ((eq a 1) 'one) ((eq a 2) 'two) ((eq a 3) 'three) (t t)))
     (let ((a 'three)) (cond ((eq a 'one) 1) ((eq a 2) 'two) ((eq a 'three) 3)
-- 
2.14.3

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

Is this really specific to floating-point expressions, though?

(byte-compile (lambda (x) (* #x10000 #x10000 #x10000 #x10000)))
#[(x) "À\207" [0] 1]

(at least on this somewhat oudated version of Emacs). Note the 0 in
the constant vector, which hardcodes the <65-bit-ness of fixnums.

I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
(* #x10000 #x10000))) similarly produces a constant-zero function,
which will produce the wrong result when fixnums are actually 62 bits
long.

(This is tangential, but I think that it might make sense, at some
point in the future, to switch to JavaScript-like
everything-is-a-float-but-there's-just-one-NaN "numbers"; that would
be quite a bit of work already, since several functions do different
things for integer and float arguments (I feel they should be fixed
anyway), and it would be nice to be able to point to the current
byte-opt situation as evidence that if you're relying on unusual
number behavior, you're already doing something wrong)

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Fri, 23 Mar 2018 20:52:52 +0000
> Cc: Emacs development discussions <emacs-devel@gnu.org>
> 
> Is this really specific to floating-point expressions, though?
> 
> (byte-compile (lambda (x) (* #x10000 #x10000 #x10000 #x10000)))
> #[(x) "À\207" [0] 1]
> 
> (at least on this somewhat oudated version of Emacs). Note the 0 in
> the constant vector, which hardcodes the <65-bit-ness of fixnums.
> 
> I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
> (* #x10000 #x10000))) similarly produces a constant-zero function,

The result depends on whether Emacs was build --with-wide-int.  If it
was, the result is #[(x) "\300\207" [4294967296] 1], if it wasn't, I
get #[(x) "\300\207" [0] 1].

Re: Floating-point constant folding in Emacs byte compiler

[Robert Pluim]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Pip Cet <pipcet@gmail.com>
>> Date: Fri, 23 Mar 2018 20:52:52 +0000
>> Cc: Emacs development discussions <emacs-devel@gnu.org>
>> 
>> Is this really specific to floating-point expressions, though?
>> 
>> (byte-compile (lambda (x) (* #x10000 #x10000 #x10000 #x10000)))
>> #[(x) "À\207" [0] 1]
>> 
>> (at least on this somewhat oudated version of Emacs). Note the 0 in
>> the constant vector, which hardcodes the <65-bit-ness of fixnums.
>> 
>> I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
>> (* #x10000 #x10000))) similarly produces a constant-zero function,
>
> The result depends on whether Emacs was build --with-wide-int.  If it
> was, the result is #[(x) "\300\207" [4294967296] 1], if it wasn't, I
> get #[(x) "\300\207" [0] 1].

Hmm, would it be worthwhile to have Emacs signal overflow in such a
situation (perhaps controlled by a configuration variable) so we could
fix such issues?

Robert

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> X-Spam-Status: No, score=-0.5 required=5.0 tests=BAYES_05,FREEMAIL_FROM,
> 	T_DKIM_INVALID autolearn=disabled version=3.3.2
> From: Robert Pluim <rpluim@gmail.com>
> Cc: Pip Cet <pipcet@gmail.com>,  eggert@cs.ucla.edu,  emacs-devel@gnu.org
> Gmane-Reply-To-List: yes
> Date: Mon, 26 Mar 2018 11:39:25 +0200
> 
> >> I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
> >> (* #x10000 #x10000))) similarly produces a constant-zero function,
> >
> > The result depends on whether Emacs was build --with-wide-int.  If it
> > was, the result is #[(x) "\300\207" [4294967296] 1], if it wasn't, I
> > get #[(x) "\300\207" [0] 1].
> 
> Hmm, would it be worthwhile to have Emacs signal overflow in such a
> situation (perhaps controlled by a configuration variable) so we could
> fix such issues?

In which of these two cases do you see overflow?

I also don't think I understand the utility of signaling an overflow
error from the byte compiler that happened because it did constant
folding.  What else except bug reports could this yield?

Re: Floating-point constant folding in Emacs byte compiler

[Robert Pluim]

Eli Zaretskii <eliz@gnu.org> writes:

>> X-Spam-Status: No, score=-0.5 required=5.0 tests=BAYES_05,FREEMAIL_FROM,
>> 	T_DKIM_INVALID autolearn=disabled version=3.3.2
>> From: Robert Pluim <rpluim@gmail.com>
>> Cc: Pip Cet <pipcet@gmail.com>,  eggert@cs.ucla.edu,  emacs-devel@gnu.org
>> Gmane-Reply-To-List: yes
>> Date: Mon, 26 Mar 2018 11:39:25 +0200
>> 
>> >> I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
>> >> (* #x10000 #x10000))) similarly produces a constant-zero function,
>> >
>> > The result depends on whether Emacs was build --with-wide-int.  If it
>> > was, the result is #[(x) "\300\207" [4294967296] 1], if it wasn't, I
>> > get #[(x) "\300\207" [0] 1].
>> 
>> Hmm, would it be worthwhile to have Emacs signal overflow in such a
>> situation (perhaps controlled by a configuration variable) so we could
>> fix such issues?
>
> In which of these two cases do you see overflow?
>

Does (* #x10000 #x10000) not overflow on 32-bit? Or have I missed a
bit somewhere?

> I also don't think I understand the utility of signaling an overflow
> error from the byte compiler that happened because it did constant
> folding.  What else except bug reports could this yield?

I was proposing it as a debug option, not a generally enabled one. Of
course if there's no overflow, it would be kind of useless :-)

Robert

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Robert Pluim <rpluim@gmail.com>
> Cc: emacs-devel@gnu.org
> Date: Mon, 26 Mar 2018 17:57:01 +0200
> 
> >> >> I imagine that on a 32-bit version of emacs, (byte-compile (lambda (x)
> >> >> (* #x10000 #x10000))) similarly produces a constant-zero function,
> >> >
> >> > The result depends on whether Emacs was build --with-wide-int.  If it
> >> > was, the result is #[(x) "\300\207" [4294967296] 1], if it wasn't, I
> >> > get #[(x) "\300\207" [0] 1].
> >> 
> >> Hmm, would it be worthwhile to have Emacs signal overflow in such a
> >> situation (perhaps controlled by a configuration variable) so we could
> >> fix such issues?
> >
> > In which of these two cases do you see overflow?
> >
> 
> Does (* #x10000 #x10000) not overflow on 32-bit?

Only if Emacs was not built --with-wide-int.

> > I also don't think I understand the utility of signaling an overflow
> > error from the byte compiler that happened because it did constant
> > folding.  What else except bug reports could this yield?
> 
> I was proposing it as a debug option, not a generally enabled one. Of
> course if there's no overflow, it would be kind of useless :-)

If we want the byte code to be portable, the results of compiling
cannot depend on the machine on which the code was byte-compiled.

Re: Floating-point constant folding in Emacs byte compiler

[Stefan Monnier]

>> Hmm, would it be worthwhile to have Emacs signal overflow in such a
>> situation (perhaps controlled by a configuration variable) so we could
>> fix such issues?

I think TRT is for the byte-compiler to refrain from performing this
optimization when the result doesn't fit within 30bits.


        Stefan

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

Well, right now the byte code (or at least the constant vector) does
depend on the machine on which the code was byte-compiled, but it's
also read differently: if I understand things correctly, large
integers in decimal notation are automatically converted to floats,
while large hex constants signal an overflow error. I believe the
former case applies to the read syntax for byte-compiled functions.

But is this really a problem for any actual code? Good code shouldn't
depend on more than the 30 bits Emacs guarantees, and IMHO it
shouldn't distinguish between integers and their floating-point
representations. In other words, I think we should specify less
behavior for our numbers, not more, and keep the byte compiler simple.
If code is broken for any of 30-bit integers, 62-bit integers, 32-bit
integers, 48-bit integers, integers-as-IEEE-doubles, or bignums, or
any combination of two of those for compilation and reading/running
bytecode, that's a bug which makes it harder to play around with Emacs
internals.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Mon, 26 Mar 2018 18:23:15 +0000
> Cc: Robert Pluim <rpluim@gmail.com>, emacs-devel@gnu.org
> 
> But is this really a problem for any actual code? Good code shouldn't
> depend on more than the 30 bits Emacs guarantees

IMO, it is no longer reasonable nowadays to require "good code" to be
limited to 30 bits.  Most people use 64-bit platforms, and those who
don't should be able to run the code with some run-time penalty, but
without overflows, errors, and any similar calamities.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Mon, 26 Mar 2018 13:52:33 -0400
> 
> >> Hmm, would it be worthwhile to have Emacs signal overflow in such a
> >> situation (perhaps controlled by a configuration variable) so we could
> >> fix such issues?
> 
> I think TRT is for the byte-compiler to refrain from performing this
> optimization when the result doesn't fit within 30bits.

I agree.

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 378 bytes --]

On 03/26/2018 10:52 AM, Stefan Monnier wrote:
> I think TRT is for the byte-compiler to refrain from performing this
> optimization when the result doesn't fit within 30bits.

Yes, this seems like the right way to go for Emacs, since we value 
reproducibility and safety over performance for numeric computation. I 
installed the attached patch into master, to try to do that.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-constant-folding-of-overflows.patch --]
[-- Type: text/x-patch; name="0001-Fix-constant-folding-of-overflows.patch", Size: 10156 bytes --]

From e3b742dcc3d2f1946969d87839e3b72b0f52c513 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 26 Mar 2018 17:03:54 -0700
Subject: [PATCH] Fix constant folding of overflows

This suppresses some byte-code optimizations that were invalid in
the presence of integer overflows, because they meant that .elc
files assumed the runtime behavior of the compiling platform, as
opposed to the runtime platform.  Problem reported by Pip Cet in:
https://lists.gnu.org/r/emacs-devel/2018-03/msg00753.html
* lisp/emacs-lisp/byte-opt.el (byte-opt--portable-max)
(byte-opt--portable-min): New constants.
(byte-opt--portable-numberp, byte-opt--arith-reduce)
(byte-optimize-1+, byte-optimize-1-): New functions.
(byte-optimize-plus, byte-optimize-minus, byte-optimize-multiply)
(byte-optimize-divide):	Avoid invalid optimizations.
(1+, 1-): Use new optimizers.
(byte-optimize-or, byte-optimize-cond): Simplify by using
remq instead of delq and copy-sequence.
---
 lisp/emacs-lisp/byte-opt.el | 175 +++++++++++++++++++++++++++++++-------------
 1 file changed, 124 insertions(+), 51 deletions(-)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 004f58cc12..3bc4c438d6 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -678,59 +678,134 @@ byte-optimize-associative-math
 	    (apply (car form) constants))
 	form)))
 
+;; Portable Emacs integers fall in this range.
+(defconst byte-opt--portable-max #x1fffffff)
+(defconst byte-opt--portable-min (- -1 byte-opt--portable-max))
+
+;; True if N is a number that works the same on all Emacs platforms.
+;; Portable Emacs fixnums are exactly representable as floats on all
+;; Emacs platforms, and (except for -0.0) any floating-point number
+;; that equals one of these integers must be the same on all
+;; platforms.  Although other floating-point numbers such as 0.5 are
+;; also portable, it can be tricky to characterize them portably so
+;; they are not optimized.
+(defun byte-opt--portable-numberp (n)
+  (and (numberp n)
+       (<= byte-opt--portable-min n byte-opt--portable-max)
+       (= n (floor n))
+       (not (and (floatp n) (zerop n)
+                 (condition-case () (< (/ n) 0) (error))))))
+
+;; Use OP to reduce any leading prefix of portable numbers in the list
+;; (cons ACCUM ARGS) down to a single portable number, and return the
+;; resulting list A of arguments.  The idea is that applying OP to A
+;; is equivalent to (but likely more efficient than) applying OP to
+;; (cons ACCUM ARGS), on any Emacs platform.  Do not make any special
+;; provision for (- X) or (/ X); for example, it is the caller’s
+;; responsibility that (- 1 0) should not be "optimized" to (- 1).
+(defun byte-opt--arith-reduce (op accum args)
+  (when (byte-opt--portable-numberp accum)
+    (let (accum1)
+      (while (and (byte-opt--portable-numberp (car args))
+                  (byte-opt--portable-numberp
+                   (setq accum1 (condition-case ()
+                                    (funcall op accum (car args))
+                                  (error))))
+                  (= accum1 (funcall op (float accum) (car args))))
+        (setq accum accum1)
+        (setq args (cdr args)))))
+  (cons accum args))
+
 (defun byte-optimize-plus (form)
-  (if (memq 0 form) (setq form (delq 0 (copy-sequence form))))
-  ;; For (+ constants...), byte-optimize-predicate does the work.
-  (when (memq nil (mapcar 'numberp (cdr form)))
+  (let ((args (remq 0 (byte-opt--arith-reduce #'+ 0 (cdr form)))))
     (cond
+     ;; (+) -> 0
+     ((null args) 0)
+     ;; (+ n) -> n, where n is a number
+     ((and (null (cdr args)) (numberp (car args))) (car args))
      ;; (+ x 1) --> (1+ x) and (+ x -1) --> (1- x).
-     ((and (= (length form) 3)
-	   (or (memq (nth 1 form) '(1 -1))
-	       (memq (nth 2 form) '(1 -1))))
-      (let (integer other)
-	(if (memq (nth 1 form) '(1 -1))
-	    (setq integer (nth 1 form) other (nth 2 form))
-	  (setq integer (nth 2 form) other (nth 1 form)))
-	(setq form
-	      (list (if (eq integer 1) '1+ '1-) other))))))
-  (byte-optimize-predicate form))
+     ((and (null (cddr args)) (or (memq 1 args) (memq -1 args)))
+      (let* ((arg1 (car args)) (arg2 (cadr args))
+             (integer-is-first (memq arg1 '(1 -1)))
+             (integer (if integer-is-first arg1 arg2))
+             (other (if integer-is-first arg2 arg1)))
+        (list (if (eq integer 1) '1+ '1-) other)))
+     ;; not further optimized
+     ((equal args (cdr form)) form)
+     (t (cons '+ args)))))
 
 (defun byte-optimize-minus (form)
-  ;; Remove zeros.
-  (when (and (nthcdr 3 form)
-	     (memq 0 (cddr form)))
-    (setq form (nconc (list (car form) (cadr form))
-		      (delq 0 (copy-sequence (cddr form)))))
-    ;; After the above, we must turn (- x) back into (- x 0).
-    (or (cddr form)
-	(setq form (nconc form (list 0)))))
-  ;; For (- constants...), byte-optimize-predicate does the work.
-  (when (memq nil (mapcar 'numberp (cdr form)))
-    (cond
-     ;; (- x 1) --> (1- x)
-     ((equal (nthcdr 2 form) '(1))
-      (setq form (list '1- (nth 1 form))))
-     ;; (- x -1) --> (1+ x)
-     ((equal (nthcdr 2 form) '(-1))
-      (setq form (list '1+ (nth 1 form))))))
-  (byte-optimize-predicate form))
+  (let ((args (cdr form)))
+    (if (and (cdr args)
+             (null (cdr (setq args (byte-opt--arith-reduce
+                                    #'- (car args) (cdr args)))))
+             (numberp (car args)))
+        ;; The entire argument list reduced to a constant; return it.
+        (car args)
+      ;; Remove non-leading zeros, except for (- x 0).
+      (when (memq 0 (cdr args))
+        (setq args (cons (car args) (or (remq 0 (cdr args)) (list 0)))))
+      (cond
+       ;; (- x 1) --> (1- x)
+       ((equal (cdr args) '(1))
+        (list '1- (car args)))
+       ;; (- x -1) --> (1+ x)
+       ((equal (cdr args) '(-1))
+        (list '1+ (car args)))
+       ;; (- n) -> -n, where n and -n are portable numbers.
+       ;; This must be done separately since byte-opt--arith-reduce
+       ;; is not applied to (- n).
+       ((and (null (cdr args))
+             (byte-opt--portable-numberp (car args))
+             (byte-opt--portable-numberp (- (car args))))
+        (- (car args)))
+       ;; not further optimized
+       ((equal args (cdr form)) form)
+       (t (cons '- args))))))
+
+(defun byte-optimize-1+ (form)
+  (let ((args (cdr form)))
+    (when (null (cdr args))
+      (let ((n (car args)))
+        (when (and (byte-opt--portable-numberp n)
+                   (byte-opt--portable-numberp (1+ n)))
+          (setq form (1+ n))))))
+  form)
+
+(defun byte-optimize-1- (form)
+  (let ((args (cdr form)))
+    (when (null (cdr args))
+      (let ((n (car args)))
+        (when (and (byte-opt--portable-numberp n)
+                   (byte-opt--portable-numberp (1- n)))
+          (setq form (1- n))))))
+  form)
 
 (defun byte-optimize-multiply (form)
-  (if (memq 1 form) (setq form (delq 1 (copy-sequence form))))
-  ;; For (* integers..), byte-optimize-predicate does the work.
-  (byte-optimize-predicate form))
+  (let* ((args (remq 1 (byte-opt--arith-reduce #'* 1 (cdr form)))))
+    (cond
+     ;; (*) -> 1
+     ((null args) 1)
+     ;; (* n) -> n, where n is a number
+     ((and (null (cdr args)) (numberp (car args))) (car args))
+     ;; not further optimized
+     ((equal args (cdr form)) form)
+     (t (cons '* args)))))
 
 (defun byte-optimize-divide (form)
-  ;; Remove 1s.
-  (when (and (nthcdr 3 form)
-	     (memq 1 (cddr form)))
-    (setq form (nconc (list (car form) (cadr form))
-		      (delq 1 (copy-sequence (cddr form)))))
-    ;; After the above, we must turn (/ x) back into (/ x 1).
-    (or (cddr form)
-	(setq form (nconc form (list 1)))))
-  (byte-optimize-predicate form))
-
+  (let ((args (cdr form)))
+    (if (and (cdr args)
+             (null (cdr (setq args (byte-opt--arith-reduce
+                                    #'/ (car args) (cdr args)))))
+             (numberp (car args)))
+        ;; The entire argument list reduced to a constant; return it.
+        (car args)
+      ;; Remove non-leading 1s, except for (/ x 1).
+      (when (memq 1 (cdr args))
+        (setq args (cons (car args) (or (remq 1 (cdr args)) (list 1)))))
+      (if (equal args (cdr form))
+          form
+        (cons '/ args)))))
 
 (defun byte-optimize-binary-predicate (form)
   (cond
@@ -800,8 +875,8 @@ byte-optimize-memq
 (put '>   'byte-optimizer 'byte-optimize-predicate)
 (put '<=  'byte-optimizer 'byte-optimize-predicate)
 (put '>=  'byte-optimizer 'byte-optimize-predicate)
-(put '1+  'byte-optimizer 'byte-optimize-predicate)
-(put '1-  'byte-optimizer 'byte-optimize-predicate)
+(put '1+  'byte-optimizer 'byte-optimize-1+)
+(put '1-  'byte-optimizer 'byte-optimize-1-)
 (put 'not 'byte-optimizer 'byte-optimize-predicate)
 (put 'null  'byte-optimizer 'byte-optimize-predicate)
 (put 'consp 'byte-optimizer 'byte-optimize-predicate)
@@ -854,8 +929,7 @@ byte-optimize-or
   ;; Throw away nil's, and simplify if less than 2 args.
   ;; If there is a literal non-nil constant in the args to `or', throw away all
   ;; following forms.
-  (if (memq nil form)
-      (setq form (delq nil (copy-sequence form))))
+  (setq form (remq nil form))
   (let ((rest form))
     (while (cdr (setq rest (cdr rest)))
       (if (byte-compile-trueconstp (car rest))
@@ -872,9 +946,8 @@ byte-optimize-cond
   (let (rest)
     ;; This must be first, to reduce (cond (t ...) (nil)) to (progn t ...)
     (while (setq rest (assq nil (cdr form)))
-      (setq form (delq rest (copy-sequence form))))
-    (if (memq nil (cdr form))
-	(setq form (delq nil (copy-sequence form))))
+      (setq form (remq rest form)))
+    (setq form (remq nil form))
     (setq rest form)
     (while (setq rest (cdr rest))
       (cond ((byte-compile-trueconstp (car-safe (car rest)))
-- 
2.14.3

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

On 03/26/2018 11:23 AM, Pip Cet wrote:
> if I understand things correctly, large integers in decimal notation 
> are automatically converted to floats, while large hex constants 
> signal an overflow error. I believe the former case applies to the 
> read syntax for byte-compiled functions.

Yes, that's right. This thread got started, though, partly because I'm 
thinking of changing the behavior for plain integers to be more like 
that of other radixes, because the automatic-float conversion causes too 
many problems in practice. This is still work in progress. For a recent 
discussion please see:

https://debbugs.gnu.org/30408

> is this really a problem for any actual code? Good code shouldn't 
> depend on more than the 30 bits Emacs guarantees,

It is a real issue, I'm afraid.(I suppose this means the code isn't 
good....) See these recent fixes in the master branch:

https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=f92c6dd6cd09991c2ab4c0612574064ca061d927
https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=011186279c1041e790b81af72981547d623d9b29
https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=cae9e0fa0358d6323b57a288b5661dc72d36356d

Better treatment of large integers at compile-time will help catch these 
gotchas.

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

On 03/26/2018 05:28 PM, Paul Eggert wrote:
> Better treatment of large integers at compile-time will help catch 
> these gotchas. 

I proposed a patch along these lines here:

https://debbugs.gnu.org/30408#43

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

Here's another interesting case of machine-dependent byte compliation:

(defun f (x) (* (+ x 1024.0) (- x 1024.0)))

(byte-compile 'f)

The resulting constvec is [x 1024.0 1024.0] on this machine, but using
NaN-boxed-doubles-as-Lisp-Objects, it's [x 1024.0]. It's easy enough
to see why (identical float values aren't eq on standard Emacs), but
it results in bytecode that's not only machine-dependent, but depends
on details that aren't visible in the form's read syntax:

(setq v 1024.0)
(setq form1 '(lambda (x) (* (+ x 1024.0) (- x 1024.0))))
(setq form2 `(lambda (x) (* (+ x ,v) (- x ,v))))
(message "%S %S" form1 (byte-compile form1))
(message "%S %S" form2 (byte-compile form2))

produces:

(lambda (x) (* (+ x 1024.0) (- x 1024.0))) #[(x) " \301\\ \302Z_\207"
[x 1024.0 1024.0] 3]
(lambda (x) (* (+ x 1024.0) (- x 1024.0))) #[(x) " \301\\ \301Z_\207"
[x 1024.0] 3]

It's easy to fix this by merging the constvec based on eql rather than
eq, but that makes the byte compiler inconsistent: with optimization,
(lambda () (eq 1024.0 1024.0)) will still be false, but without
optimization, it will turn into bytecode that always returns true.

This is biting me because I want bytecode to be exactly the same as on
standard Emacs.

Re: Floating-point constant folding in Emacs byte compiler

[Noam Postavsky]

On 30 March 2018 at 12:26, Pip Cet <pipcet@gmail.com> wrote:

> It's easy to fix this by merging the constvec based on eql rather than
> eq, but that makes the byte compiler inconsistent: with optimization,
> (lambda () (eq 1024.0 1024.0)) will still be false, but without
> optimization, it will turn into bytecode that always returns true.

I don't think there should be an expectation that `eq' on floats is consistent.

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

On 03/30/2018 09:26 AM, Pip Cet wrote:
> with optimization,
> (lambda () (eq 1024.0 1024.0)) will still be false, but without
> optimization, it will turn into bytecode that always returns true

This problem is endemic to Lisp implementations and I wouldn't worry 
about it too much. In Scheme, for example, it is unspecifed whether (eq? 
2.0 2.0) returns true or false, and Emacs Lisp could do the same. We'll 
have similar problems with bignums if we ever get around to implementing 
them.

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

I believe the currently-documented behavior is that it's undefined;
however, merely leaving it undefined doesn't make bytecode compilation
reproducible. To do that, right now, I redefine EQ to be true for
same-value floats. I'd prefer the byte compiler to be fixed
(unfortunately, flet-binding eq around the invocation of the byte
compiler isn't an option since byte-compiled code won't let you
redefine eq), but there appear to be several places where the
assumption is built into it, and I haven't found them all. The
half-fixed compiler generates obviously-suboptimal bytecode sequences
like "const X; const X;".

I think it makes sense to say that bytecode should be portable but not
necessarily identical between implementations, provided there's also a
way to canonicalize bytecode generation so the result is actually
target-independent (in the sense that if there are still bytecode
differences between targets, that's a bug in the Lisp code); I hope
redefining EQ is sufficient for that.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Mon, 2 Apr 2018 10:56:25 +0000
> Cc: Robert Pluim <rpluim@gmail.com>, emacs-devel@gnu.org
> 
> I believe the currently-documented behavior is that it's undefined;
> however, merely leaving it undefined doesn't make bytecode compilation
> reproducible. To do that, right now, I redefine EQ to be true for
> same-value floats. I'd prefer the byte compiler to be fixed
> (unfortunately, flet-binding eq around the invocation of the byte
> compiler isn't an option since byte-compiled code won't let you
> redefine eq), but there appear to be several places where the
> assumption is built into it, and I haven't found them all. The
> half-fixed compiler generates obviously-suboptimal bytecode sequences
> like "const X; const X;".
> 
> I think it makes sense to say that bytecode should be portable but not
> necessarily identical between implementations, provided there's also a
> way to canonicalize bytecode generation so the result is actually
> target-independent (in the sense that if there are still bytecode
> differences between targets, that's a bug in the Lisp code); I hope
> redefining EQ is sufficient for that.

Can you make a step back and explain what is it that you are trying to
achieve, and why?  Making potentially backward-incompatible changes
without a very good reason is not something we should be enthusiastic
about, IMO.  E.g., the fact that two floats are never EQ is burned
into too many muscle memories, and I expect subtle problems with at
least C code that uses EQ.

Thanks.

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

I'm trying to make bytecode reproducible for my code, which uses
SpiderMonkey's JS::Value type, and in which two same-value floats are
always equal (because their bit representations are), and standard
Emacs on a standard GNU/Linux machine, where, as I've just learned,
two same-value floats are never eq (I'd previously thought that was
undefined, and actually unpredictable in practice).

Finding subtle problems in C code that assumes floats are never EQ
would be one reason why I'm doing this, to understand and hopefully
one day find bugs in the Emacs code base.

Again, this is the first time I hear that "two floats are never EQ" is
actually intentional behavior that some code might rely on, rather
than a mere accident of the current float implementation. Do you
happen to have any examples at hand for code that relies on this?

In the case of byte code, what I've seen so far is that the code
generated is actually suboptimal, and runs fine without duplicated
float constants in the constants vector.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Mon, 2 Apr 2018 11:42:59 +0000
> Cc: eggert@cs.ucla.edu, rpluim@gmail.com, emacs-devel@gnu.org
> 
> I'm trying to make bytecode reproducible for my code, which uses
> SpiderMonkey's JS::Value type, and in which two same-value floats are
> always equal (because their bit representations are), and standard
> Emacs on a standard GNU/Linux machine, where, as I've just learned,
> two same-value floats are never eq (I'd previously thought that was
> undefined, and actually unpredictable in practice).

Well, maybe what I said could be misinterpreted: they _can_ be EQ iff
they reference the same Lisp_Float object.  If they reference
different objects, they aren't EQ.  When these floats come from Lisp,
it's extremely unlikely for them to reference the same object, though.

> Again, this is the first time I hear that "two floats are never EQ" is
> actually intentional behavior that some code might rely on, rather
> than a mere accident of the current float implementation. Do you
> happen to have any examples at hand for code that relies on this?

Not off the top of my head, no.  But IME such implementation details
tend to leak into the code, and I would be surprised if we didn't have
something like that in Emacs.

> In the case of byte code, what I've seen so far is that the code
> generated is actually suboptimal, and runs fine without duplicated
> float constants in the constants vector.

Comparing FP values for equivalence on the C level is tricky at best,
due to extended precision, guard bits, etc.  What is your plan for
overcoming these obstacles in a predictable and reliable manner?  Did
you consider solving the problem the other way around, i.e. teaching
JS::Value about this issue?  (Caveat: I know nothing about JS.)

Re: Floating-point constant folding in Emacs byte compiler

[Noam Postavsky]

On 30 March 2018 at 12:26, Pip Cet <pipcet@gmail.com> wrote:

> It's easy to fix this by merging the constvec based on eql rather than
> eq, but that makes the byte compiler inconsistent: with optimization,
> (lambda () (eq 1024.0 1024.0)) will still be false, but without
> optimization, it will turn into bytecode that always returns true.

The byte-compiler is already inconsistent in this way for string literals:

(funcall (byte-compile (lambda ()
                         (let ((s "one") (s2 "one"))
                           (eq s s2)))))
;=> t

(funcall (lambda ()
           (let ((s "one") (s2 "one"))
             (eq s s2))))

;=> nil

Although surprisingly:

(funcall (byte-compile (lambda ()
                         (eq "one" "one"))))
;=> nil

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Noam Postavsky <npostavs@gmail.com>
> Date: Mon, 2 Apr 2018 08:57:30 -0400
> Cc: Robert Pluim <rpluim@gmail.com>, Paul Eggert <eggert@cs.ucla.edu>,
> 	Emacs developers <emacs-devel@gnu.org>
> 
> On 30 March 2018 at 12:26, Pip Cet <pipcet@gmail.com> wrote:
> 
> > It's easy to fix this by merging the constvec based on eql rather than
> > eq, but that makes the byte compiler inconsistent: with optimization,
> > (lambda () (eq 1024.0 1024.0)) will still be false, but without
> > optimization, it will turn into bytecode that always returns true.
> 
> The byte-compiler is already inconsistent in this way for string literals:

Yes, because strings share the same EQ issue with floats.  And because
we sometimes try to "optimize" that.  For example, in make_pure_string.

RE: Floating-point constant folding in Emacs byte compiler

[Drew Adams]

(Apologies for not following this thread.)

Would it be possible for a user or Lisp code to be
able to specify that it does not want the byte compiler
to perform such floating-point optimization, in order
to provide more platform-independence?

Many uses of Emacs Lisp and C code don't really need
such optimization, I would think.  Couldn't the byte
compiler be made to respect a user (or Lisp-code)
choice here?

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> Date: Mon, 2 Apr 2018 06:37:40 -0700 (PDT)
> From: Drew Adams <drew.adams@oracle.com>
> Cc: rpluim@gmail.com, eggert@cs.ucla.edu, pipcet@gmail.com, emacs-devel@gnu.org
> 
> Would it be possible for a user or Lisp code to be
> able to specify that it does not want the byte compiler
> to perform such floating-point optimization, in order
> to provide more platform-independence?

We didn't yet decide to make any changes in the byte compiler, so I
see no need to discuss such fire escapes.  The current trend is to
disable optimizations when they harm portability or cause undefined
or unspecified behavior.

Re: Floating-point constant folding in Emacs byte compiler

[Stefan Monnier]

> Yes, because strings share the same EQ issue with floats.  And because
> we sometimes try to "optimize" that.  For example, in make_pure_string.

It's actually subtly different: with floats, EQ (and functions that
use it) is the *only* way to distinguish two equal floats.
With strings it's not the case because you can modify the object in
place (e.g. by changing its text-properties).

So for strings, the semantics is much less undefined: we're not free to
merge two strings just because they're `equal`, whereas for floats
we are.


        Stefan

Re: Floating-point constant folding in Emacs byte compiler

[Stefan Monnier]

> reproducible.  To do that, right now, I redefine EQ to be true for
> same-value floats.

So you redefine EQ to mean EQL?  That should work.


        Stefan

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

On Mon, Apr 2, 2018 at 1:37 PM, Drew Adams <drew.adams@oracle.com> wrote:
> Would it be possible for a user or Lisp code to be
> able to specify that it does not want the byte compiler
> to perform such floating-point optimization, in order
> to provide more platform-independence?

I think it's slightly different: I think it should be possible to
instruct the compiler, in special cases (when building byte code that
is to be run on several different machines/Emacs implementations), to
perform the optimizations, which result in code that is very slightly
more efficient and less platform-dependent (but might break certain
long-standing assumptions about independently constructed floats never
being eq). It's the unoptimized code that makes it easy to rely on
platform-dependent features, and that depends on implementation
details in ways that the optimized code does not.

> Many uses of Emacs Lisp and C code don't really need
> such optimization, I would think.  Couldn't the byte
> compiler be made to respect a user (or Lisp-code)
> choice here?

If I understand Eli correctly, there's no way to enable the new option
by default, because old code might break in subtle ways; that also
makes it questionable whether it's worth it to include the new option
at all.

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

On Mon, Apr 2, 2018 at 2:50 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> reproducible.  To do that, right now, I redefine EQ to be true for
>> same-value floats.
>
> So you redefine EQ to mean EQL?  That should work.

It does! I can now produce the same lisp/ directory as standard Emacs
+ EQ=EQL + CANNOT_DUMP=yes (however, even vanilla Emacs will produce
different lisp/ directories with and without CANNOT_DUMP=yes. One
instance is cus-load.el, which includes entries for preloaded files
when CANNOT_DUMP=yes, which is arguably a feature; I'm looking at the
other differences).

I redefined the C EQ macro, not (just) Feq.

RE: Floating-point constant folding in Emacs byte compiler

[Drew Adams]

> > Would it be possible for a user or Lisp code to be
> > able to specify that it does not want the byte compiler
> > to perform such floating-point optimization, in order
> > to provide more platform-independence?
> 
> I think it's slightly different: I think it should be possible to
> instruct the compiler, in special cases (when building byte code that
> is to be run on several different machines/Emacs implementations), to
> perform the optimizations, which result in code that is very slightly
> more efficient and less platform-dependent (but might break certain
> long-standing assumptions about independently constructed floats never
> being eq). It's the unoptimized code that makes it easy to rely on
> platform-dependent features, and that depends on implementation
> details in ways that the optimized code does not.
> 
> > Many uses of Emacs Lisp and C code don't really need
> > such optimization, I would think.  Couldn't the byte
> > compiler be made to respect a user (or Lisp-code)
> > choice here?
> 
> If I understand Eli correctly, there's no way to enable the new option
> by default, because old code might break in subtle ways; that also
> makes it questionable whether it's worth it to include the new option
> at all.

My concern is to not have platform-independence suffer more,
or at least be able to optionally prevent that as much as
possible.

Re: Floating-point constant folding in Emacs byte compiler

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 502 bytes --]

On 04/02/2018 07:48 AM, Stefan Monnier wrote:
> we're not free to
> merge two strings just because they're `equal`, whereas for floats
> we are.
Yes, that's the key point here. I see that the Elisp documentation does 
not specify how eq behaves on floats with the same values, so I took a 
crack at specifying this the same way that Common Lisp and Scheme do by 
installing the attached into master. I doubt whether Common Lisp/Scheme 
semantics here will break real Elisp code in any significant way.

[-- Attachment #2: 0001-Clarify-eq-on-floats.patch --]
[-- Type: text/x-patch, Size: 1333 bytes --]

From b89189f686a599817d8cdcc81038b62a38a7baa7 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 2 Apr 2018 12:19:00 -0700
Subject: [PATCH] Clarify eq on floats

* doc/lispref/objects.texi (Equality Predicates):
Say that two floats with the same values might or might not be eq.
---
 doc/lispref/objects.texi | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi
index af740625ad..78a7dccc88 100644
--- a/doc/lispref/objects.texi
+++ b/doc/lispref/objects.texi
@@ -2083,6 +2083,10 @@ Equality Predicates
 necessarily @code{eq} to each other: they are @code{eq} only if they
 are the same object, meaning that a change in the contents of one will
 be reflected by the same change in the contents of the other.
+For other types of objects whose contents cannot be changed (e.g.,
+floats), two arguments with the same contents might or might not be
+the same object, and @code{eq} returns @code{t} or @code{nil}
+depending on whether the Lisp interpreter created one object or two.
 
 @example
 @group
@@ -2095,6 +2099,12 @@ Equality Predicates
      @result{} t
 @end group
 
+@group
+(eq 3.0 3.0)
+     @result{} t @r{or} nil
+;; @r{The result is implementation-dependent.}
+@end group
+
 @group
 (eq "asdf" "asdf")
      @result{} nil
-- 
2.14.3

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

Actually, there's this bit in the documentation for eql:

Floating-point numbers of equal value are ‘eql’, but they may not be ‘eq’.

I think that matches what I want (which is to be free to merge all
floats of equal value right away), and it matches your change, but not
what Eli suggested was legitimate.

Re: Floating-point constant folding in Emacs byte compiler

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Mon, 2 Apr 2018 19:39:13 +0000
> Cc: emacs-devel@gnu.org
> 
> Floating-point numbers of equal value are ‘eql’, but they may not be ‘eq’.
> 
> I think that matches what I want (which is to be free to merge all
> floats of equal value right away), and it matches your change, but not
> what Eli suggested was legitimate.

We could be mis-communicating: you said "EQ", not 'eq', so I thought
you wanted to supplant the EQ macro on the C level to return non-zero
for two float objects whose values compare equal.  Now it sounds like
you were talking about something entirely different, something that
only matters on the Lisp level.

Re: Floating-point constant folding in Emacs byte compiler

[Pip Cet]

> We could be mis-communicating: you said "EQ", not 'eq', so I thought
> you wanted to supplant the EQ macro on the C level to return non-zero
> for two float objects whose values compare equal.  Now it sounds like
> you were talking about something entirely different, something that
> only matters on the Lisp level.

Sorry for the confusion. You're right, I was talking about replacing
EQ, and I was ignoring the difference between eq and EQ. TBH, I'm not
too worried about the C code and EQ, though I would be worried about
making EQ and eq mean different things.