[gambit-list] Guile's new compiler

Marc Feeley feeley at iro.umontreal.ca
Fri Nov 6 17:30:29 EST 2015


A good source of information is this page:

https://wingolog.org/archives/2011/10/11/partial-evaluation-in-guile

It seems that Guile’s partial evaluator uses an “effort counter” that is decremented when inlining happens, and when it reaches 0 no more inlining occurs.

From guile/module/language/tree-il/peval.scm:

;; Counters are data structures used to limit the effort that peval
;; spends on particular inlining attempts.  Each call site in the source
;; program is allocated some amount of effort.  If peval exceeds the
;; effort counter while attempting to inline a call site, it aborts the
;; inlining attempt and residualizes a call instead.
;;
;; As there is a fixed number of call sites, that makes `peval' O(N) in
;; the number of call sites in the source program.
;;
;; Counters should limit the size of the residual program as well, but
;; currently this is not implemented.
;;
;; At the top level, before seeing any peval call, there is no counter,
;; because inlining will terminate as there is no recursion.  When peval
;; sees a call at the top level, it will make a new counter, allocating
;; it some amount of effort and size.
;;
;; This top-level effort counter effectively "prints money".  Within a
;; toplevel counter, no more effort is printed ex nihilo; for a nested
;; inlining attempt to proceed, effort must be transferred from the
;; toplevel counter to the nested counter.
;;
;; Via `data' and `prev', counters form a linked list, terminating in a
;; toplevel counter.  In practice `data' will be the a pointer to the
;; source expression of the procedure being inlined.
;;
;; In this way peval can detect a recursive inlining attempt, by walking
;; back on the `prev' links looking for matching `data'.  Recursive
;; counters receive a more limited effort allocation, as we don't want
;; to spend all of the effort for a toplevel inlining site on loops.
;; Also, recursive counters don't need a prompt at each inlining site:
;; either the call chain folds entirely, or it will be residualized at
;; its original call.

(define* (peval exp #:optional (cenv (current-module)) (env vlist-null)
                #:key
                (operator-size-limit 40)
                (operand-size-limit 20)
                (value-size-limit 10)
                (effort-limit 500)
                (recursive-effort-limit 100))
…)

Gambit currently uses the size of the call site to determine how much code can be inlined.  I’ll have to look into the effort counters that Guile’s partial evaluator uses to see if something similar could be used in Gambit.

I note however that the effort limit used in Guile is an arbitrary constant that isn’t modifiable by the programmer.  I’m affraid it could lead to lots of inlining in some cases and not much in other cases.  For example:

(letrec ((f (lambda (s)
              (define char-at
                (lambda (n) (string-ref s n)))
              (define len
                (lambda () (string-length s)))
              (let loop ((i 0))
                (if (< i (len))
                    (cons (char-at i)
                          (loop (+ 1 i)))
                    '())))))
  (f "123"))

is expanded to

(let f ((s "123"))
  (let loop ((i 0))
    (if (< i (string-length s))
      (cons (string-ref s i) (loop (#{1+}# i)))
      '())))

but replacing the string "123" by "12" gives: (list #\1 #\2)

In the case of

(letrec ((f1 (lambda (x) (list x x x x x x x x)))
         (f2 (lambda (x) (f1 (f1 x))))
         (f3 (lambda (x) (f2 (f2 x))))
         (f4 (lambda (x) (f3 (f3 x))))
         (f5 (lambda (x) (f4 x)))
         (f6 (lambda (x) (f5 x)))
         (f7 (lambda (x) (f6 x)))
         (f8 (lambda (x) (f7 x)))
         (f9 (lambda (x) (f8 x))))
  (f9 0))

Guile expands this to

(let ()
  (define (f9 x) (f8 x))
  (define (f8 x) (f7 x))
  (define (f7 x) (f6 x))
  (define (f6 x) (f5 x))
  (define (f5 x) (f4 x))
  (define (f4 x)
    (f3 (let* ((x (let ((x (list x x x x x x x x)))
                    (list x x x x x x x x)))
               (x (list x x x x x x x x)))
          (list x x x x x x x x))))
  (define (f3 x)
    (let* ((x (let ((x (list x x x x x x x x)))
                (list x x x x x x x x)))
           (x (list x x x x x x x x)))
      (list x x x x x x x x)))
  (f9 0))

Note that this code doesn’t create a list of 0’s at the leaves, and it does not do some inlining because the “effort limit” is reached (function f3 is only inlined once, and also f4 to f9 aren’t inlined even though they are called at a single call site).  There remains 7 function calls.

Gambit treats those call sites separately, so the residual code has 4 function calls in all with the default inlining limit of 300 and has 0 function calls with an inlining limit of 1000.  Functions f5 to f9 are always eliminated whatever the inlining limit.

So I don’t think one approach is superior to the other.  They are different inlining heuristics.  There’s clearly room for experimentation and benchmarking…

I suggest you dive into gsc/_ptree2.scm to try out different strategies and see what works best!

Marc


> On Nov 6, 2015, at 3:22 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> On 11/06/2015 03:16 PM, Marc Feeley wrote:
>> The lambda can’t be removed because loop is referred to at 2 call sites, in the call (loop 0) and the call (loop (+ 1 i)).
> 
> OK, that's what I meant by "If that idea isn't precisely correct then maybe it's something one could start with to get something that works."
> 
> Maybe we should just ask Andy what he does.
> 
> Brad




More information about the Gambit-list mailing list