bug#42147: 28.0.50; pure vs side-effect-free, missing optimizations?

[Andrea Corallo via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>]

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

Mattias Engdegård <mattiase@acm.org> writes:

> 3 juli 2020 kl. 21.05 skrev Andrea Corallo <andrea_corallo@yahoo.it>:
>
>> attached the updated version of the patch updating the pure function
>> classification.
>
> Thanks Andrea! Philipp Stephani raised the interesting question of (essentially) whether 'car' is pure. For the purposes of the current constant folding in the byte compiler the answer is yes, but perhaps you have wider ambitions in your work?
>
> Clearly, (car X) cannot be moved past some operations with side-effects if X is aliased:
>
> (let* ((x (list 'a))
>        (y (car x)))
>   (f x)
>   y)
>
> Here, (car x) cannot be sunk past the call to f despite x remaining unchanged (assuming lexical binding).
> It would be useful to know more exactly what notion of purity you require.

Thanks for the observation, today I was studying the situation.

I think the notion of purity has to be the same one we use in the byte
compiler.  The trickiness is in if the considered object is immutable or
not.  The optimizer must stay in the boundary of what is allowed in this
regard.

To put in elisp what I think ATM:

(defun aaa ()
  (let ((x (list 1 2)))
    (1+ (car x)) ; <= legally optimizable
    ))

(defun bbb ()
  (let ((x (list 1 2)))
    (f x)        ; f is not pure
    (1+ (car x)) ; <= cannot optimize
    ))

(defun ccc ()
  (let ((x '(1 2)))
    (f x)        ; f is not pure
    (1+ (car x)) ; <= legally optimizable because immutable
    ))

(defun ddd ()
  (let ((x (list 1 2)))
    (f x)        ; f is pure
    (1+ (car x)) ; <= legally optimizable
    ))

Now given we are not constant folding `cons' we are not materializing
conses, as a consequence of these three example we would optimize only
`ccc' if we include `car' as pure.  AFAIU this is correct given
modifying an immutable object in `f' would be undefined.

So yes for me `car' is pure and I think we should add it to the list.

BTW reading the code of the native compiler I realized I am already
extrapolating for use a very similar list of optimizable functions to the one
proposed.  I still think would quite cleaner to classify these in
byte-opt.el.

Attached the updated patch where I'm adding car, car-safe, cdr,
cdr-safe, max, min.

Feedback welcome

Thanks

  Andrea

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-a-number-of-functions-to-pure-fns-bug-42147.patch --]
[-- Type: text/x-patch, Size: 1928 bytes --]

From 15a7dc91a3ef278e1beaa834fdf961844f7b80c8 Mon Sep 17 00:00:00 2001
From: Andrea Corallo <akrl@sdf.org>
Date: Wed, 1 Jul 2020 10:07:57 +0200
Subject: [PATCH] * Add a number of functions to pure-fns (bug#42147)

	* lisp/emacs-lisp/byte-opt.el (pure-fns): Add: /=, <, <=, =,
	>, >=, abs, arrayp, ash, assoc, assq, bool-vector-p car,
	car-safe, cdr, cdr-safe, char-or-string-p, characterp, consp,
	eq, eql, equal, expt, floatp, hash-table-p, identity,
	integer-or-marker-p, integerp, keywordp, length, listp, max,
	member, memq, memql, min, mod, natnump, nlistp, not, null,
	number-or-marker-p, numberp, proper-list-p, rassq,
	safe-length, sequencep, string-equal, string-lessp, string<,
	string=, stringp, symbolp, vectorp.
---
 lisp/emacs-lisp/byte-opt.el | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 12bde8faf3..6ad8f11cd7 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -1307,9 +1307,14 @@ byte-optimize-set
 ;; values if a marker is moved.
 
 (let ((pure-fns
-       '(% concat logand logcount logior lognot logxor
-	 regexp-opt regexp-quote
-	 string-to-char string-to-syntax symbol-name)))
+       '(% /= < <= = > >= abs arrayp ash assoc assq bool-vector-p car car-safe
+         cdr cdr-safe char-or-string-p characterp concat consp eq eql equal
+         expt floatp hash-table-p identity integer-or-marker-p integerp
+         keywordp length listp logand logcount logior lognot logxor max member
+         memq memql min mod natnump nlistp not null number-or-marker-p, numberp
+         proper-list-p rassq regexp-opt regexp-quote safe-length sequencep
+         string-equal string-lessp string-to-char string-to-syntax string<
+         string= stringp symbol-name symbolp vectorp)))
   (while pure-fns
     (put (car pure-fns) 'pure t)
     (setq pure-fns (cdr pure-fns)))
-- 
2.17.1