[gambit-list] Guile's new compiler

Marc Feeley feeley at iro.umontreal.ca
Fri Nov 6 08:22:43 EST 2015


My guess is that the Gambit code transformations are applied sequentially, once, and your code would require the transformations to be done repeatedly, in some kind of loop.  The problem with looping over the transformations is preventing code bloat and also guaranteeing termination.  If you have an idea how to do this, let me know.

Marc

> On Nov 6, 2015, at 1:44 AM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> 
>> On Nov 5, 2015, at 5:21 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
>> 
>> On 11/05/2015 07:29 AM, Marc Feeley wrote:
>>> You haven’t given the compiler much information to help it optimize…
>>> 
>>> Try:
>>> 
>>> (declare (standard-bindings))
>>> 
>>> (define (a x y)
>>>  (map (lambda (c d) (+ c d)) x y))
>>> 
>>> It gives better inlining than (map + x y) .  I haven’t looked into the details of why, but it is the transformations in gsc/_ptree2.scm that are involved in the inlining.  Perhaps you could trace the code to see where the inlining is cut short.
>>> 
>>> Did you try this with Guile also to compare?
>> 
>> Well, the guile compiler takes this
>> 
>> (let ((string->chars
>>      (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)))
>>              '())))))
>> (string->chars "yo"))
>> 
>> and turns it into
>> (compile-file "crap.scm" #:to 'assembly)
>> $2 = "/home/lucier/.cache/guile/ccache/2.0-LE-8-2.0/home/lucier/Desktop/crap.scm.go"
>> 
>> which is
>> 
>> (load-program ((:LCASE341 . 2)) 16 (load-program () 66 #f (make-eol) (load-symbol "filename") (load-string "crap.scm") (cons) (make-int8:0) (make-int8 8) (make-int8:0) (cons) (cons) (make-int8 4) (make-int8 11) (make-int8 23) (cons) (cons) (make-int8 9) (make-int8 18) (make-int8 15) (cons) (cons) (list 0 4) (make-int8 2) (make-int8 10) (make-int8:0) (list 0 3) (list 0 1) (list 0 3) (return)) (assert-nargs-ee/locals 0) (make-char8 121) (make-char8 111) (list 0 2) (return) (nop) (nop) (nop) (nop) (nop) (nop))
>> 
>> (which is just constructing the list of characters '(#\y #\o))
>> 
>> Even after adding
>> 
>> (declare (standard-bindings)
>> 	 (fixnum)
>> 	 (not safe)
>> 	 (inlining-limit 1000))
>> 
>> Gambit does
>> 
>> firefly:~/Desktop> gsc -c -expansion crap
>> Expansion:
>> 
>> (let ((s "yo"))
>> (letrec ((loop (lambda (s i)
>>                  (if ('#<procedure #2 ##fx<> i ('#<procedure #3 ##string-length> s))
>>                      ('#<procedure #4 ##cons>
>>                       ('#<procedure #5 ##string-ref> s i)
>>                       (let ((i ('#<procedure #6 ##fx+> 1 i)))
>>                         (if ('#<procedure #2 ##fx<>
>>                              i
>>                              ('#<procedure #3 ##string-length> s))
>>                             ('#<procedure #4 ##cons>
>>                              ('#<procedure #5 ##string-ref> s i)
>>                              (let ((i ('#<procedure #6 ##fx+> 1 i)))
>>                                (if ('#<procedure #2 ##fx<>
>>                                     i
>>                                     ('#<procedure #3 ##string-length> s))
>>                                    ('#<procedure #4 ##cons>
>>                                     ('#<procedure #5 ##string-ref> s i)
>>                                     (let ((i ('#<procedure #6 ##fx+> 1 i)))
>>                                       (if ('#<procedure #2 ##fx<>
>>                                            i
>>                                            ('#<procedure #3 ##string-length> s))
>>                                           ('#<procedure #4 ##cons>
>>                                            ('#<procedure #5 ##string-ref> s i)
>>                                            (loop s ('#<procedure #6 ##fx+> 1 i)))
>>                                           '())))
>>                                    '())))
>>                             '())))
>>                      '()))))
>>   (loop s 0)))
>> 
>> I.e., it never pulls that argument into the closure.
> 
> Ah, but if you start with
> 
> ((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)))
>               '())))
> "yo")
> 
> The Gambit compiler gives
> 
> (letrec ((loop (lambda (i)
>                 (if ('#<procedure #7 ##fx<> i (let () ('#<procedure #8 ##string-length> "yo")))
>                     ('#<procedure #5 ##cons>
>                      (let ((n i)) ('#<procedure #9 ##string-ref> "yo" n))
>                      (let ((i ('#<procedure #10 ##fx+> 1 i)))
>                        (if ('#<procedure #7 ##fx<> i (let () ('#<procedure #8 ##string-length> "yo")))
>                            ('#<procedure #5 ##cons>
>                             (let ((n i)) ('#<procedure #9 ##string-ref> "yo" n))
>                             (let ((i ('#<procedure #10 ##fx+> 1 i)))
>                               (if ('#<procedure #7 ##fx<> i (let () ('#<procedure #8 ##string-length> "yo")))
>                                   ('#<procedure #5 ##cons>
>                                    (let ((n i)) ('#<procedure #9 ##string-ref> "yo" n))
>                                    (let ((i ('#<procedure #10 ##fx+> 1 i)))
>                                      (if ('#<procedure #7 ##fx<> i (let () ('#<procedure #8 ##string-length> "yo")))
>                                          ('#<procedure #5 ##cons> (let ((n i)) ('#<procedure #9 ##string-ref> "yo" n)) (loop ('#<procedure #10 ##fx+> 1 i)))
>                                          '())))
>                                   '())))
>                            '())))
>                     '()))))
>  (loop 0))
> 
> so now the problem is that it doesn’t do compile-time evaluation of ('#<procedure #8 ##string-length> "yo”).
> 
> Re your previous message:
> 
>> As far as I can tell, all of those optimizations are currently done by the Gambit compiler except for loop-invariant code motion and loop inversion.  I’m not sure how much those optimizations are useful however.
> 
> doesn’t loop inversion strip off the first few iterations of the loop with known values (i.e., start with i=0 in loop, compare it with ('#<procedure #8 ##string-length> "yo”), see that it truly is <, do the cons whose first argument is ('#<procedure #9 ##string-ref> "yo" 0), etc.) before defining a general loop body for later use?  (Am I being at all clear?)
> 
> Brad




More information about the Gambit-list mailing list