Fail to optimize tail recursion when tail call occurs in FINALLY clause of LOOP without RETURN

Bug #1810257 reported by Hugo Ishimaru on 2019-01-02
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Undecided
Unassigned

Bug Description

The following code produces the CONTROL-STACK-EXHAUSTED error (if thread_control_stack_size is small):
(defun test-tailrec (table begin-idx)
  (declare (optimize (speed 3) (safety 0))
           ((simple-array fixnum (*)) table)
           (fixnum begin-idx))
  (when (< begin-idx (length table))
    (loop with base = (aref table begin-idx)
          for end-idx from begin-idx below (length table)
          while (= base (aref table end-idx))
          finally ; here occur some side effects in practice
             (test-tailrec table end-idx))))

(defparameter *table* (make-array 1000000 :element-type 'fixnum))
(dotimes (idx (length *table*))
  (setf (aref *table* idx) (random most-positive-fixnum)))
(test-tailrec *table* 0)

By disassembling we can confirm the TCO didn't occur. A workaround is enclosing the last form with an (unnecessary) RETURN as follows:

(defun test-tailrec2 (table begin-idx)
  (declare (optimize (speed 3) (safety 0))
           ((simple-array fixnum (*)) table)
           (fixnum begin-idx))
  (when (< begin-idx (length table))
    (loop with base = (aref table begin-idx)
          for end-idx from begin-idx below (length table)
          while (= base (aref table end-idx))
          finally (return (test-tailrec2 table end-idx)))))

Environment: SBCL 1.4.14 (Windows, x64)

summary: - fail to optimize tail recursion when tail call occurs in FINALLY clause
+ Fail to optimize tail recursion when tail call occurs in FINALLY clause
of LOOP without RETURN
Stas Boukarev (stassats) wrote :

Without RETURN it will return NIL, and not the values returned by the function. Tail call optimization can only return the values from the called function.

Changed in sbcl:
status: New → Invalid
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers