inlining a recursive function causes compiler to stack overflow

[John Fremlin]

I made a naive recursive function to calculate a Google codejam problem. Declaim inlining it is probably not a good idea. However, it would be nice if the compiler didn't crash to ldb (git head and 1.0.29).

$ sbcl --eval '(compile-file "C.lisp")'
This is SBCL 1.0.34.10, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
; loading system definition from
; /home/john/Build/sbcl/contrib/sb-grovel/sb-grovel.asd into #<PACKAGE "ASDF1">
; registering #<SYSTEM SB-GROVEL {100404EBA1}> as SB-GROVEL
STYLE-WARNING: redefining ALTERNATIVE-ROOT-PATH-TO-FASL-PATH in DEFUN

; compiling file "/tmp/C.lisp" (written 01 FEB 2010 05:38:21 PM):
; compiling (DECLAIM (OPTIMIZE DEBUG ...))
; compiling (DECLAIM (INLINE COUNT-FILL-IN-GRID))
; compiling (DEFUN COUNT-FILL-IN-GRID ...)INFO: Control stack guard page unprotected
Control stack guard page temporarily disabled: proceed with caution

fatal error encountered in SBCL pid 17001(tid 140737353901808):
Control stack exhausted

Welcome to LDB, a low-level debugger for the Lisp runtime environment.
ldb>

Here is the function inlne (also attached)
(declaim (optimize debug safety))

(declaim (inline count-fill-in-grid))
(defun count-fill-in-grid (grid rows cols &optional (c-start 0) (r-start 0))
  (declare (type fixnum rows cols c-start r-start) (optimize speed))
  (macrolet ((a (c r)
        `(aref grid ,c ,r)))
    (loop for c from c-start below cols
   do (loop
     for r from r-start below rows
     for v = (a c r)
     do
     (unless v
       (let ((min 0) (max 25))
         (flet ((maybe-min (val)
    (when val
      (setf min (max min val)))))
    (unless (zerop r)
      (maybe-min (a c (1- r))))
    (unless (zerop c)
      (maybe-min (a (1- c) r))))
         (flet ((maybe-max (val)
    (when val
      (setf max (min max val)))))
    (unless (= r (1- rows))
      (maybe-max (a c (1+ r))))
    (unless (= c (1- cols))
      (maybe-max (a (1+ c) r))))
         (when (> min max)
    (return-from count-fill-in-grid 0))
         (let ((count 0))
    (loop for v from min upto max do
          (setf (a c r) v)
          (let ((recur (count-fill-in-grid grid rows cols c r)))
     (when (zerop recur) (return))
     (setf count (mod (+ count recur) 10007))))
    (setf (a c r) nil)
    (return-from count-fill-in-grid count)))))
   (setf r-start 0)))
  1)

SBCL 1.0.34.10

[Nikodemus Siivola (nikodemus)]

Marked as "high" because of the fall into LDB.

[Nikodemus Siivola (nikodemus)]

As a quick workaround:

 (setf sb-ext:*inline-expansion-limit* 12)

allows the code to compile.

[Roman Marynchak (roman-marynchak)]

The simple fix idea is to prevent the inline expansion of the recursive functions when they are called within their own bodies. Are there any drawbacks in such approach?

[Roman Marynchak (roman-marynchak)]

I have attached the patch, which implements the above idea. It shows the right place for the recursive call detection (ir1opt.lisp, recognize-known-call), but the recursion detection predicate is a sketch at this time (improvements are very welcome!). This patch works only after chill.lisp and patched ir1opt.lisp are loaded, but it aborts the cross-compilation. So, use it only to design the right version of the predicate.

[John Fremlin (john-fremlin)]

I think that it is wrong in general to ban the inlining of recursive
functions which is a very useful optimization.

Take the (defun fib (n) (if (zerop n) 1 (+ (fib (- n 2)) (fin (1- n)))))
classic stupid example. Inlining a few rounds of this would actually be
quite sensible (supposing the compiler were incapable of transforming it
completely).

Consider the relatively common idiom of a function sometimes fixing up
its inputs and then calling itself with the fixed inputs rather than
setf'ing them. Inlining is sensible again.

The problem is that you have to stop inlining before the compiler blows
up, not that you shouldn't do it at all.

[...]

[Roman Marynchak (roman-marynchak)]

I do agree with you about the useful nature of the inlining of recursive functions. But the compiler could do a different number of the inlining passes, depending on the function's body size. So, it is quite hard (maybe I should say 'impossible' ?) to guess the last pass number - which will eventually crash the compiler.

In this situation, at least two solutions are possible:

1. Close this issue, and use *inline-expansion-limit* to deal with the complex cases.
2. Ban the recursive functions inlining into themselves, despite of any useful outcomes. What is interesting, one legacy comment in ir1util.lisp supports this too:

" ;; FIXME: If the objective is to stop the recursive
           ;; expansion of inline functions, wouldn't it be more
           ;; correct to look back through surrounding expansions
           ;; (which are, I think, stored in the *CURRENT-PATH*, and
           ;; possibly stored elsewhere too) and suppress expansion
           ;; and print this warning when the function being proposed
           ;; for inline expansion is found there? (I don't like the
           ;; arbitrary numerical limit in principle, and I think
           ;; it'll be a nuisance in practice if we ever want the
           ;; compiler to be able to use WITH-COMPILATION-UNIT on
           ;; arbitrarily huge blocks of code. -- WHN)
"

I would prefer the first variant - to close the issue, and to describe *inline-expansion-limit* somewhere in the manual, so the users will know about the problems with the recursive inlining. Previously, I was going to implement the second variant, but your decent examples about the inlining usefulness have changed my opinion. As usual, I will be glad to hear what other developers think about this.

Roman

[Nikodemus Siivola (nikodemus)]

Banning recursive functions from self-inlining is not good.

Documenting *inline-expansion-limit* is good, but it is not a classy fix for this bug.

I think both in here and potentially elsewhere what one may want to do is to sniff the stack before deciding to continue: that is, inline if the limit is not reached, and there is at least X amount of stack-space left.

[Stas Boukarev (stassats)]

It doesn't overflow with the new lower (50) limit, but it gets stuck in constraint propagation because the resulting function is very large. But any large nested function can exhaust the compiler stack, you have to be mindful of that.