* lisp/emacs-lisp/cl-macs.el: Optimize self-calls in tail position

Implement a limited form of tail-call optimization for the special
case of recursive functions defined with `cl-labels`.  Only self-recursion
is optimized, no attempt is made to handle more complex cases such a mutual
recursion.

The main benefit is to reduce the use of the stack, tho in my limited
tests, this can also improve performance (about half of the way to
a hand-written `while` loop).

(cl--self-tco): New function.
(cl-labels): Use it.

* lisp/subr.el (letrec): Optimize single-binding corner case.

* test/lisp/emacs-lisp/cl-macs-tests.el (cl-macs--labels): Add tests
to check that TCO is working.

1 files changed, 16 insertions, 1 deletions

diff --git a/test/lisp/emacs-lisp/cl-macs-tests.el b/test/lisp/emacs-lisp/cl-macs-tests.el
index 7774ed3145b..bcd63f73a3c 100644
--- a/test/lisp/emacs-lisp/cl-macs-tests.el
+++ b/test/lisp/emacs-lisp/cl-macs-tests.el
@@ -616,6 +616,21 @@ collection clause."
   ;; Simple recursive function.
   (cl-labels ((len (xs) (if xs (1+ (len (cdr xs))) 0)))
     (should (equal (len (make-list 42 t)) 42)))
-  )
+
+  ;; Simple tail-recursive function.
+  (cl-labels ((len (xs n) (if xs (len (cdr xs) (1+ n)) n)))
+    (should (equal (len (make-list 42 t) 0) 42))
+    ;; Should not bump into stack depth limits.
+    (should (equal (len (make-list 42000 t) 0) 42000)))
+
+  ;; Check that non-recursive functions are handled more efficiently.
+  (should (pcase (macroexpand '(cl-labels ((f (x) (+ x 1))) (f 5)))
+            (`(let* ,_ (funcall ,_ 5)) t)))
+
+  ;; Case of "tail-recursive lambdas".
+  (should (pcase (macroexpand
+                  '(cl-labels ((len (xs n) (if xs (len (cdr xs) (1+ n)) n)))
+                     #'len))
+            (`(function (lambda (,_ ,_) . ,_)) t))))
 
 ;;; cl-macs-tests.el ends here