Guile’s 2.1.1 announcement includes the following paragraph:
======================================================================
** Better optimizations via compiler rewrite
Guile's compiler now uses a Continuation-Passing Style (CPS) intermediate language, allowing it to reason easily about temporary values and control flow. Examples of optimizations that this permits are optimal contification, optimal common subexpression elimination, dead code elimination, loop-invariant code motion, loop peeling, loop inversion, parallel moves with at most one temporary, allocation of stack slots using precise liveness information, and closure optimization. For more, see "Continuation-Passing Style" in the manual.
======================================================================
Are some of these missing from Gambit’s compiler? Could they be “easily” added (for some value of “easily”)?
Brad
(Sorry for the third try sending this to the mail list. El capitan (Mac OS X 10.11) mail is “different”.)
Afficher les réponses par date
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.
Marc
On Nov 4, 2015, at 10:08 PM, lucier@math.purdue.edu wrote:
Guile’s 2.1.1 announcement includes the following paragraph:
======================================================================
** Better optimizations via compiler rewrite
Guile's compiler now uses a Continuation-Passing Style (CPS) intermediate language, allowing it to reason easily about temporary values and control flow. Examples of optimizations that this permits are optimal contification, optimal common subexpression elimination, dead code elimination, loop-invariant code motion, loop peeling, loop inversion, parallel moves with at most one temporary, allocation of stack slots using precise liveness information, and closure optimization. For more, see "Continuation-Passing Style" in the manual.
======================================================================
Are some of these missing from Gambit’s compiler? Could they be “easily” added (for some value of “easily”)?
Brad
(Sorry for the third try sending this to the mail list. El capitan (Mac OS X 10.11) mail is “different”.) _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Nov 4, 2015, at 10:26 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
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.
Marc
OK.
What about this example:
[Media-Mac-mini-3:~] lucier% cat crap.scm (define (a x y) (map + x y))
[Media-Mac-mini-3:~] lucier% gsc -c -expansion crap Expansion:
(define a (lambda (x y) (let ((temp.0 +)) (if (and ('#<procedure #2 ##eq?> map '#<procedure #3 map>) ('#<procedure #4 ##procedure?> temp.0)) (letrec ((loop1.3 (lambda (x y temp.0 temp.4 temp.5) (if (and ('#<procedure #5 ##pair?> temp.4) ('#<procedure #5 ##pair?> temp.5)) (loop1.3 x y temp.0 ('#<procedure #6 ##cdr> temp.4) ('#<procedure #6 ##cdr> temp.5)) (if (and ('#<procedure #7 ##null?> temp.4) ('#<procedure #7 ##null?> temp.5)) (letrec ((loop2.6 (lambda (temp.0 temp.7 temp.8) (if (and ('#<procedure #5 ##pair?> temp.7) ('#<procedure #5 ##pair?> temp.8)) (let ((x.9 (temp.0 ('#<procedure #8 ##car> temp.7) ('#<procedure #8 ##car> temp.8)))) ('#<procedure #9 ##cons> x.9 (loop2.6 temp.0 ('#<procedure #6 ##cdr> temp.7) ('#<procedure #6 ##cdr> temp.8)))) '())))) (loop2.6 temp.0 x y)) (map temp.0 x y)))))) (loop1.3 x y temp.0 x y)) (map temp.0 x y)))))
The gambit compiler doesn’t specialize +.
Or even
[Media-Mac-mini-3:~] lucier% cat crap.scm (define (a x y) (map f64+ x y)) [Media-Mac-mini-3:~] lucier% gsc -c -expansion crap Expansion:
(define a (lambda (x y) (let ((temp.0 f64+)) (if (and ('#<procedure #2 ##eq?> map '#<procedure #3 map>) ('#<procedure #4 ##procedure?> temp.0)) (letrec ((loop1.3 (lambda (x y temp.0 temp.4 temp.5) (if (and ('#<procedure #5 ##pair?> temp.4) ('#<procedure #5 ##pair?> temp.5)) (loop1.3 x y temp.0 ('#<procedure #6 ##cdr> temp.4) ('#<procedure #6 ##cdr> temp.5)) (if (and ('#<procedure #7 ##null?> temp.4) ('#<procedure #7 ##null?> temp.5)) (letrec ((loop2.6 (lambda (temp.0 temp.7 temp.8) (if (and ('#<procedure #5 ##pair?> temp.7) ('#<procedure #5 ##pair?> temp.8)) (let ((x.9 (temp.0 ('#<procedure #8 ##car> temp.7) ('#<procedure #8 ##car> temp.8)))) ('#<procedure #9 ##cons> x.9 (loop2.6 temp.0 ('#<procedure #6 ##cdr> temp.7) ('#<procedure #6 ##cdr> temp.8)))) '())))) (loop2.6 temp.0 x y)) (map temp.0 x y)))))) (loop1.3 x y temp.0 x y)) (map temp.0 x y)))))
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?
Marc
On Nov 5, 2015, at 12:38 AM, Bradley Lucier lucier@math.purdue.edu wrote:
On Nov 4, 2015, at 10:26 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
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.
Marc
OK.
What about this example:
[Media-Mac-mini-3:~] lucier% cat crap.scm (define (a x y) (map + x y))
[Media-Mac-mini-3:~] lucier% gsc -c -expansion crap Expansion:
(define a (lambda (x y) (let ((temp.0 +)) (if (and ('#<procedure #2 ##eq?> map '#<procedure #3 map>) ('#<procedure #4 ##procedure?> temp.0)) (letrec ((loop1.3 (lambda (x y temp.0 temp.4 temp.5) (if (and ('#<procedure #5 ##pair?> temp.4) ('#<procedure #5 ##pair?> temp.5)) (loop1.3 x y temp.0 ('#<procedure #6 ##cdr> temp.4) ('#<procedure #6 ##cdr> temp.5)) (if (and ('#<procedure #7 ##null?> temp.4) ('#<procedure #7 ##null?> temp.5)) (letrec ((loop2.6 (lambda (temp.0 temp.7 temp.8) (if (and ('#<procedure #5 ##pair?> temp.7) ('#<procedure #5 ##pair?> temp.8)) (let ((x.9 (temp.0 ('#<procedure #8 ##car> temp.7) ('#<procedure #8 ##car> temp.8)))) ('#<procedure #9 ##cons> x.9 (loop2.6 temp.0 ('#<procedure #6 ##cdr> temp.7) ('#<procedure #6 ##cdr> temp.8)))) '())))) (loop2.6 temp.0 x y)) (map temp.0 x y)))))) (loop1.3 x y temp.0 x y)) (map temp.0 x y)))))
The gambit compiler doesn’t specialize +.
Or even
[Media-Mac-mini-3:~] lucier% cat crap.scm (define (a x y) (map f64+ x y)) [Media-Mac-mini-3:~] lucier% gsc -c -expansion crap Expansion:
(define a (lambda (x y) (let ((temp.0 f64+)) (if (and ('#<procedure #2 ##eq?> map '#<procedure #3 map>) ('#<procedure #4 ##procedure?> temp.0)) (letrec ((loop1.3 (lambda (x y temp.0 temp.4 temp.5) (if (and ('#<procedure #5 ##pair?> temp.4) ('#<procedure #5 ##pair?> temp.5)) (loop1.3 x y temp.0 ('#<procedure #6 ##cdr> temp.4) ('#<procedure #6 ##cdr> temp.5)) (if (and ('#<procedure #7 ##null?> temp.4) ('#<procedure #7 ##null?> temp.5)) (letrec ((loop2.6 (lambda (temp.0 temp.7 temp.8) (if (and ('#<procedure #5 ##pair?> temp.7) ('#<procedure #5 ##pair?> temp.8)) (let ((x.9 (temp.0 ('#<procedure #8 ##car> temp.7) ('#<procedure #8 ##car> temp.8)))) ('#<procedure #9 ##cons> x.9 (loop2.6 temp.0 ('#<procedure #6 ##cdr> temp.7) ('#<procedure #6 ##cdr> temp.8)))) '())))) (loop2.6 temp.0 x y)) (map temp.0 x y)))))) (loop1.3 x y temp.0 x y)) (map temp.0 x y)))))
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.
On Nov 5, 2015, at 5:21 PM, Bradley Lucier lucier@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
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@math.purdue.edu wrote:
On Nov 5, 2015, at 5:21 PM, Bradley Lucier lucier@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
One issue with your example is that ##string-length (and many other ## primitives) were not being constant folded. That is now fixed.
Another issue is that for the (let loop ((i 0)) …) there is no loop peeling occurring. Note that the let loop expands to a (letrec ((loop (lambda (i) …))) (loop 0)) . I noticed that the beta-reducer was not constant propagating the value of i in (let ((i 0)) …) after the first inlining of the function. So I added a beta-reduction of the let.
But there is another issue… The inliner will limit the expansion of the code to some factor of the size of the call site. Here the call site which starts the loop is (loop 0), a tiny call of size 3 (the size is the number of parse-tree nodes). Increasing the inlining-limit at the top of the file does not help because the body of the loop function is expanded before the call site is considered for inlining, so the body of the loop function is bigger and doesn’t get inlined. So a workaround is to rewrite the loop so that it is a separate function, and then attach a high inlining limit to the call. An alternative is to have a high inlining limit for the (let loop …) and a low inlining limit for the loop body. For example:
(declare (standard-bindings) (fixnum) (not safe))
(let ((s "yo")) (define char-at (lambda (n) (string-ref s n))) (define len (lambda () (string-length s))) (declare (inlining-limit 2000)) (let loop ((i 0)) (declare (inlining-limit 100)) (if (< i (len)) (cons (char-at i) (loop (+ 1 i))) '())))
With that source code, gsc now expands it to:
('#<procedure #2 ##cons> #\y ('#<procedure #2 ##cons> #\o '()))
Which can’t be improved without violating eq?-ness of the resulting list.
It isn’t clear how to fix this to avoid the need for the programmer to change the inlining limit. The simple approach of not beta-reducing the body of the function before it is inlined doesn’t work well when the body is actually made smaller by the beta-reduction.
Marc
On Nov 6, 2015, at 1:44 AM, Bradley Lucier lucier@math.purdue.edu wrote:
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
Hallo,
On 11/06/2015 05:54 PM, Marc Feeley wrote:
It isn’t clear how to fix this to avoid the need for the programmer to change the inlining limit. The simple approach of not beta-reducing the body of the function before it is inlined doesn’t work well when the body is actually made smaller by the beta-reduction.
But when the lambda is inside a letrec, does not escape and is called only once the beta reduction will never increase code size (provided that you do not emit the lambda). I have done something similar in my toy compiler:
https://github.com/asandroq/sly/blob/cps/src/compiler.scm#L758
Cheers, -alex
Hi,
Never mind, obviously the lambda will be called from inside itself, when it's a loop.
Von meinem iPhone gesendet
Am 06 Nov 2015 um 18:19 schrieb Alex Silva asandroq@gmail.com:
Hallo,
On 11/06/2015 05:54 PM, Marc Feeley wrote:
It isn’t clear how to fix this to avoid the need for the programmer to change the inlining limit. The simple approach of not beta-reducing the body of the function before it is inlined doesn’t work well when the body is actually made smaller by the beta-reduction.
But when the lambda is inside a letrec, does not escape and is called only once the beta reduction will never increase code size (provided that you do not emit the lambda). I have done something similar in my toy compiler:
https://github.com/asandroq/sly/blob/cps/src/compiler.scm#L758
Cheers, -alex
On 11/06/2015 11:54 AM, Marc Feeley wrote:
One issue with your example is that ##string-length (and many other ## primitives) were not being constant folded. That is now fixed.
Another issue is that for the (let loop ((i 0)) …) there is no loop peeling occurring. Note that the let loop expands to a (letrec ((loop (lambda (i) …))) (loop 0)) . I noticed that the beta-reducer was not constant propagating the value of i in (let ((i 0)) …) after the first inlining of the function. So I added a beta-reduction of the let.
But there is another issue… The inliner will limit the expansion of the code to some factor of the size of the call site. Here the call site which starts the loop is (loop 0), a tiny call of size 3 (the size is the number of parse-tree nodes). Increasing the inlining-limit at the top of the file does not help because the body of the loop function is expanded before the call site is considered for inlining, so the body of the loop function is bigger and doesn’t get inlined. So a workaround is to rewrite the loop so that it is a separate function, and then attach a high inlining limit to the call. An alternative is to have a high inlining limit for the (let loop …) and a low inlining limit for the loop body. For example:
Wow, what progress in such a short time!
Here's an idea:
In the example, if the body of lambda is expanded into the call (loop 0), then the original lambda can be removed! So this doesn't increase the total size of the code at all. Maybe you can have logic that says: If a the inlinining limit is k * 100, and a lambda has no more than k possible call sites, then expand that lambda into the call sites and eliminate the code for the original lambda.
If that idea isn't precisely correct then maybe it's something one could start with to get something that works.
Brad
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)).
Marc
On Nov 6, 2015, at 2:51 PM, Bradley Lucier lucier@math.purdue.edu wrote:
On 11/06/2015 11:54 AM, Marc Feeley wrote:
One issue with your example is that ##string-length (and many other ## primitives) were not being constant folded. That is now fixed.
Another issue is that for the (let loop ((i 0)) …) there is no loop peeling occurring. Note that the let loop expands to a (letrec ((loop (lambda (i) …))) (loop 0)) . I noticed that the beta-reducer was not constant propagating the value of i in (let ((i 0)) …) after the first inlining of the function. So I added a beta-reduction of the let.
But there is another issue… The inliner will limit the expansion of the code to some factor of the size of the call site. Here the call site which starts the loop is (loop 0), a tiny call of size 3 (the size is the number of parse-tree nodes). Increasing the inlining-limit at the top of the file does not help because the body of the loop function is expanded before the call site is considered for inlining, so the body of the loop function is bigger and doesn’t get inlined. So a workaround is to rewrite the loop so that it is a separate function, and then attach a high inlining limit to the call. An alternative is to have a high inlining limit for the (let loop …) and a low inlining limit for the loop body. For example:
Wow, what progress in such a short time!
Here's an idea:
In the example, if the body of lambda is expanded into the call (loop 0), then the original lambda can be removed! So this doesn't increase the total size of the code at all. Maybe you can have logic that says: If a the inlinining limit is k * 100, and a lambda has no more than k possible call sites, then expand that lambda into the call sites and eliminate the code for the original lambda.
If that idea isn't precisely correct then maybe it's something one could start with to get something that works.
Brad
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
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@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
Speaking of benchmarking ...
I just ran the tests in misc/bench.tgz on 4.8.1 and with your latest changes. The results are all over the place. Perhaps I'm doing something wrong. Perhaps you might check it yourself.
The times for dderiv, lattice, conform, nd scheme roughly doubled with the new compiler; takl, tfib, graphs, matrix, maze, mazefun, peval, pi ray are up 50%.
Other things have improved, too, of course.
I'll attach the summaries.
Brad
On 11/07/2015 06:53 PM, Bradley Lucier wrote:
On 11/07/2015 06:41 PM, Bradley Lucier wrote:
Speaking of benchmarking ...
I just ran the tests in misc/bench.tgz on 4.8.1 and with your latest changes. The results are all over the place. Perhaps I'm doing something wrong.
Looks like this is the case, I'll get back to you.
Brad
Here's a new summary of the new results (don't ask).
There are many small differences, but with modern machines it's difficult to understand where those differences arise.
Anyway, looks like nothing broke, and nothing got improved tremendously, either.
Brad
I just rebuilt Gambit with
firefly:~/programs/gambit/gambit-v4_8_1-devel/bench> ./configure 'CC=gcc -march=native -Wdisabled-optimization -Wall -W --param max-gcse-memory=1000000000' '--enable-single-host' '--enable-multiple-versions' '--enable-shared' --enable-c-opt
and got the results at the bottom, which are uniformly better than the old results.
The -Wdisabled-optimization line showed me that GCSE wasn't being done, and after looking at gcse.c in the gcc sources I saw that I needed to increase the max-gcse-memory from 50 MB (found in gcc/params.def) to something bigger. I'm working a machine with 32GB, so I just decided to make it roughly 1GB.
Pretty good.
Brad
./bench -r 3 -s r6rs-fixflo-unsafe gambit all ./summarize results.Gambit-C-r6rs-fixflo-unsafe (succeed 0 0) (fail ) (crash ) (browse 892 894) (cpstak 264 266) (ctak 344 344) (dderiv 308 311) (deriv 272 274) (destruc 292 293) (diviter 292 293) (divrec 388 390) (puzzle 144 147) (takl 140 141) (trav1 180 183) (trav2 688 689) (triangl 308 312) (fft 76 79) (fib 212 214) (fibfp 168 169) (mbrot 152 153) (nucleic 64 67) (pnpoly 60 61) (sum 88 89) (sumfp 684 684) (tak 220 220) (tfib 444 444) (ack 160 160) (array1 64 64) (cat 360 361) (string 292 292) (sum1 376 376) (sumloop 1560 1563) (tail 292 294) (wc 168 171) (conform 240 240) (dynamic 228 230) (earley 244 243) (fibc 264 263) (graphs 292 295) (lattice 516 518) (matrix 372 371) (maze 172 169) (mazefun 276 280) (nqueens 288 289) (paraffins 752 756) (peval 280 279) (pi 472 471) (primes 492 492) (ray 100 101) (scheme 332 333) (simplex 112 114) (slatex 164 165) (perm9 300 302) (nboyer 340 339) (sboyer 232 233) (gcbench 752 752)
I have a hard time interpreting the results. Can you give the performance as a ratio compared to the build without max-gcse-memory?
Also, were all of the other options the same? Including —enable-c-opt?
I assume this has nothing to do with inlining or does it?
Marc
On Nov 7, 2015, at 10:50 PM, Bradley Lucier lucier@math.purdue.edu wrote:
I just rebuilt Gambit with
firefly:~/programs/gambit/gambit-v4_8_1-devel/bench> ./configure 'CC=gcc -march=native -Wdisabled-optimization -Wall -W --param max-gcse-memory=1000000000' '--enable-single-host' '--enable-multiple-versions' '--enable-shared' --enable-c-opt
and got the results at the bottom, which are uniformly better than the old results.
The -Wdisabled-optimization line showed me that GCSE wasn't being done, and after looking at gcse.c in the gcc sources I saw that I needed to increase the max-gcse-memory from 50 MB (found in gcc/params.def) to something bigger. I'm working a machine with 32GB, so I just decided to make it roughly 1GB.
Pretty good.
Brad
./bench -r 3 -s r6rs-fixflo-unsafe gambit all ./summarize results.Gambit-C-r6rs-fixflo-unsafe (succeed 0 0) (fail ) (crash ) (browse 892 894) (cpstak 264 266) (ctak 344 344) (dderiv 308 311) (deriv 272 274) (destruc 292 293) (diviter 292 293) (divrec 388 390) (puzzle 144 147) (takl 140 141) (trav1 180 183) (trav2 688 689) (triangl 308 312) (fft 76 79) (fib 212 214) (fibfp 168 169) (mbrot 152 153) (nucleic 64 67) (pnpoly 60 61) (sum 88 89) (sumfp 684 684) (tak 220 220) (tfib 444 444) (ack 160 160) (array1 64 64) (cat 360 361) (string 292 292) (sum1 376 376) (sumloop 1560 1563) (tail 292 294) (wc 168 171) (conform 240 240) (dynamic 228 230) (earley 244 243) (fibc 264 263) (graphs 292 295) (lattice 516 518) (matrix 372 371) (maze 172 169) (mazefun 276 280) (nqueens 288 289) (paraffins 752 756) (peval 280 279) (pi 472 471) (primes 492 492) (ray 100 101) (scheme 332 333) (simplex 112 114) (slatex 164 165) (perm9 300 302) (nboyer 340 339) (sboyer 232 233) (gcbench 752 752)
See these results, which indicate also the time to build gambit with each set of options.
There are many optimizations in gcc that are turned off for "large" functions, where "large" could mean any number of things. In 2000 I introduced into gcc the -Wdisabled-optimization warning that could allow one to know when an optimization is disabled, and for what reason, but it is implemented internally only in global common subexpression elimination and in constant propagation.
So using --enable-single-host, which generates a single C routine from a Scheme source file, quietly disables many optimizations even when --enable-c-opt is enabled and -Wdisabled-optimization is specified.
These results seem to indicate that applying the -O2 gcc optimizations on code without --enable-single-host is often faster than code with --enable-single-host, even with --enable-c-opt.
Brad
Really nice!
Could you also compute the geometric means? That way we could have a single measure of the performance. This would be helpful to determine what the best options are for various scenarios (fast build vs. slow build).
Marc
On Nov 9, 2015, at 4:27 PM, Bradley Lucier lucier@math.purdue.edu wrote:
See these results, which indicate also the time to build gambit with each set of options.
There are many optimizations in gcc that are turned off for "large" functions, where "large" could mean any number of things. In 2000 I introduced into gcc the -Wdisabled-optimization warning that could allow one to know when an optimization is disabled, and for what reason, but it is implemented internally only in global common subexpression elimination and in constant propagation.
So using --enable-single-host, which generates a single C routine from a Scheme source file, quietly disables many optimizations even when --enable-c-opt is enabled and -Wdisabled-optimization is specified.
These results seem to indicate that applying the -O2 gcc optimizations on code without --enable-single-host is often faster than code with --enable-single-host, even with --enable-c-opt.
Brad
<bench-hacked.html>
Hi,
On Nov 9, 2015, at 4:27 PM, Bradley Lucier lucier@math.purdue.edu
wrote:
So using --enable-single-host, which generates a single C routine from a Scheme source file, quietly disables many optimizations even when --enable-c-opt is enabled and -Wdisabled-optimization is specified.
Probably the reason why it builds so much faster than clang with `--enable-single-host`.
-alex
On 11/11/2015 11:52 AM, Alex Silva wrote:
Hi,
On Nov 9, 2015, at 4:27 PM, Bradley Lucier lucier@math.purdue.edu
wrote:
So using --enable-single-host, which generates a single C routine from a Scheme source file, quietly disables many optimizations even when --enable-c-opt is enabled and -Wdisabled-optimization is specified.
Probably the reason why it builds so much faster than clang with `--enable-single-host`.
I don't know of any optimizations that are skipped with the default Gambit configuration (without --enable-c-opt).
So, no, this is not why gcc is faster than clang.
Brad
Hi,
On 12 November 2015 at 05:34, Bradley Lucier lucier@math.purdue.edu wrote:
Probably the reason why it builds so much faster than clang with `--enable-single-host`.
I don't know of any optimizations that are skipped with the default Gambit configuration (without --enable-c-opt).
So, no, this is not why gcc is faster than clang.
Of course I was talking about my experience, and I always use `--enable-c-opt`.
Cheers,
On 11/11/2015 11:47 AM, Marc Feeley wrote:
Really nice!
Could you also compute the geometric means? That way we could have a single measure of the performance. This would be helpful to determine what the best options are for various scenarios (fast build vs. slow build).
I'm in the middle of some other things for a few days.
Here are the file, go to town.
Brad
Is this a measurement of the impact of elevation of max-gcse-memory from 50MB to 1GB on the execution speed of compiled code?
What do the first and second columns describe, etotal execution time for the 50MB and 1MB cases?
2015-11-08 11:50 GMT+08:00 Bradley Lucier lucier@math.purdue.edu:
I just rebuilt Gambit with
firefly:~/programs/gambit/gambit-v4_8_1-devel/bench> ./configure 'CC=gcc -march=native -Wdisabled-optimization -Wall -W --param max-gcse-memory=1000000000' '--enable-single-host' '--enable-multiple-versions' '--enable-shared' --enable-c-opt
and got the results at the bottom, which are uniformly better than the old results.
The -Wdisabled-optimization line showed me that GCSE wasn't being done, and after looking at gcse.c in the gcc sources I saw that I needed to increase the max-gcse-memory from 50 MB (found in gcc/params.def) to something bigger. I'm working a machine with 32GB, so I just decided to make it roughly 1GB.
Pretty good.
Brad
./bench -r 3 -s r6rs-fixflo-unsafe gambit all ./summarize results.Gambit-C-r6rs-fixflo-unsafe (succeed 0 0) (fail ) (crash ) (browse 892 894) (cpstak 264 266) (ctak 344 344) (dderiv 308 311) (deriv 272 274) (destruc 292 293) (diviter 292 293) (divrec 388 390) (puzzle 144 147) (takl 140 141) (trav1 180 183) (trav2 688 689) (triangl 308 312) (fft 76 79) (fib 212 214) (fibfp 168 169) (mbrot 152 153) (nucleic 64 67) (pnpoly 60 61) (sum 88 89) (sumfp 684 684) (tak 220 220) (tfib 444 444) (ack 160 160) (array1 64 64) (cat 360 361) (string 292 292) (sum1 376 376) (sumloop 1560 1563) (tail 292 294) (wc 168 171) (conform 240 240) (dynamic 228 230) (earley 244 243) (fibc 264 263) (graphs 292 295) (lattice 516 518) (matrix 372 371) (maze 172 169) (mazefun 276 280) (nqueens 288 289) (paraffins 752 756) (peval 280 279) (pi 472 471) (primes 492 492) (ray 100 101) (scheme 332 333) (simplex 112 114) (slatex 164 165) (perm9 300 302) (nboyer 340 339) (sboyer 232 233) (gcbench 752 752)
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Great results Brad!
Could you also include the time to build Gambit in your results. For me, build time is an important factor in any decision to use an optimization.
Thanks, Guillaume
On Sun, Nov 8, 2015 at 7:28 AM, Adam adam.mlmb@gmail.com wrote:
Is this a measurement of the impact of elevation of max-gcse-memory from 50MB to 1GB on the execution speed of compiled code?
What do the first and second columns describe, etotal execution time for the 50MB and 1MB cases?
2015-11-08 11:50 GMT+08:00 Bradley Lucier lucier@math.purdue.edu:
I just rebuilt Gambit with
firefly:~/programs/gambit/gambit-v4_8_1-devel/bench> ./configure 'CC=gcc -march=native -Wdisabled-optimization -Wall -W --param max-gcse-memory=1000000000' '--enable-single-host' '--enable-multiple-versions' '--enable-shared' --enable-c-opt
and got the results at the bottom, which are uniformly better than the old results.
The -Wdisabled-optimization line showed me that GCSE wasn't being done, and after looking at gcse.c in the gcc sources I saw that I needed to increase the max-gcse-memory from 50 MB (found in gcc/params.def) to something bigger. I'm working a machine with 32GB, so I just decided to make it roughly 1GB.
Pretty good.
Brad
./bench -r 3 -s r6rs-fixflo-unsafe gambit all ./summarize results.Gambit-C-r6rs-fixflo-unsafe (succeed 0 0) (fail ) (crash ) (browse 892 894) (cpstak 264 266) (ctak 344 344) (dderiv 308 311) (deriv 272 274) (destruc 292 293) (diviter 292 293) (divrec 388 390) (puzzle 144 147) (takl 140 141) (trav1 180 183) (trav2 688 689) (triangl 308 312) (fft 76 79) (fib 212 214) (fibfp 168 169) (mbrot 152 153) (nucleic 64 67) (pnpoly 60 61) (sum 88 89) (sumfp 684 684) (tak 220 220) (tfib 444 444) (ack 160 160) (array1 64 64) (cat 360 361) (string 292 292) (sum1 376 376) (sumloop 1560 1563) (tail 292 294) (wc 168 171) (conform 240 240) (dynamic 228 230) (earley 244 243) (fibc 264 263) (graphs 292 295) (lattice 516 518) (matrix 372 371) (maze 172 169) (mazefun 276 280) (nqueens 288 289) (paraffins 752 756) (peval 280 279) (pi 472 471) (primes 492 492) (ray 100 101) (scheme 332 333) (simplex 112 114) (slatex 164 165) (perm9 300 302) (nboyer 340 339) (sboyer 232 233) (gcbench 752 752)
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 11/05/2015 07:29 AM, Marc Feeley wrote:
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.
How do you run the compiler through the interpreter so that we can trace the routines in _ptree2.scm and see the input and output in a reasonable way?
Brad
% cd gsc % ./igsc.scm loading "~~/gsc/_host.scm" loading "~~/gsc/_utils.scm" loading "~~/gsc/_source.scm" loading "~~/gsc/_parms.scm" loading "~~/gsc/_env.scm" loading "~~/gsc/_ptree1.scm" loading "~~/gsc/_ptree2.scm" loading "~~/gsc/_gvm.scm" loading "~~/gsc/_back.scm" loading "~~/gsc/_front.scm" loading "~~/gsc/_prims.scm" loading "~~/gsc/_assert.scm" loading "~~/gsc/_asm.scm" loading "~~/gsc/_x86.scm" loading "~~/gsc/_codegen.scm" loading "~~/gsc/_t-univ.scm" loading "~~/gsc/_t-c-1.scm" loading "~~/gsc/_t-c-3.scm" loading "~~/gsc/_t-c-2.scm" loading "~~/gsc/_gsclib.scm" loading "~~/gsc/_gsc.scm" loading "~~/gsc/_gscdebug.scm" Gambit v4.8.1
(trace c#br) (compile-file-to-target "crap.scm")
| > (c#br '(PTREE: 10) '() 'need #f) | (PTREE: 10) | > (c#br '(PTREE: (pp (let ((temp.0 n) (temp.1 n)) (if (and ('#<procedure #2... | | > (c#br '(PTREE: pp) '() 'need #f) | | (PTREE: pp) | | > (c#br '(PTREE: (let ((temp.0 n) (temp.1 n)) (if (and ('#<procedure #2 #... | | | > (c#br '(PTREE: n) '((#((var-tag) temp.1 (PTREE: (lambda (temp.0 temp.... | | | (PTREE: 10) | | | > (c#br '(PTREE: n) '((#((var-tag) temp.1 (PTREE: (lambda (temp.0 temp.... | | | (PTREE: 10) | | | > (c#br '(PTREE: (if (and ('#<procedure #2 ##fixnum?> temp.1) ('#<proce... | | | | > (c#br '(PTREE: (and ('#<procedure #2 ##fixnum?> temp.1) ('#<procedu... | | | | | > (c#br '(PTREE: ('#<procedure #2 ##fixnum?> temp.1)) '((#((var-tag... | | | | | | > (c#br '(PTREE: '#<procedure #2 ##fixnum?>) '((#((var-tag) temp.... | | | | | | (PTREE: '#<procedure #2 ##fixnum?>) | | | | | | > (c#br '(PTREE: temp.1) '((#((var-tag) temp.1 (PTREE: (lambda (t... | | | | | | (PTREE: 10) | | | | | (PTREE: #t) | | | | > (c#br '(PTREE: ('#<procedure #2 ##fixnum?> temp.0)) '((#((var-tag) ... | | | | | > (c#br '(PTREE: '#<procedure #2 ##fixnum?>) '((#((var-tag) temp.1 ... | | | | | (PTREE: '#<procedure #2 ##fixnum?>) | | | | | > (c#br '(PTREE: temp.0) '((#((var-tag) temp.1 (PTREE: (lambda (tem... | | | | | (PTREE: 10) | | | | (PTREE: #t) | | | > (c#br '(PTREE: (if ('#<procedure #3 ##eqv?> temp.1 0) 0 (let ((temp.2... | | | | > (c#br '(PTREE: ('#<procedure #3 ##eqv?> temp.1 0)) '((#((var-tag) t... | | | | | > (c#br '(PTREE: '#<procedure #3 ##eqv?>) '((#((var-tag) temp.1 (PT... | | | | | (PTREE: '#<procedure #3 ##eqv?>) | | | | | > (c#br '(PTREE: temp.1) '((#((var-tag) temp.1 (PTREE: (lambda (tem... | | | | | (PTREE: 10) | | | | | > (c#br '(PTREE: 0) '((#((var-tag) temp.1 (PTREE: (lambda (temp.0 t... | | | | | (PTREE: 0) | | | | (PTREE: #f) | | | > (c#br '(PTREE: (let ((temp.2 (if ('#<procedure #3 ##eqv?> temp.1 -1) ... | | | | > (c#br '(PTREE: (if ('#<procedure #3 ##eqv?> temp.1 -1) ('#<procedur... | | | | | > (c#br '(PTREE: ('#<procedure #3 ##eqv?> temp.1 -1)) '((#((var-tag... | | | | | | > (c#br '(PTREE: '#<procedure #3 ##eqv?>) '((#((var-tag) temp.1 (... | | | | | | (PTREE: '#<procedure #3 ##eqv?>) | | | | | | > (c#br '(PTREE: temp.1) '((#((var-tag) temp.1 (PTREE: (lambda (t... | | | | | | (PTREE: 10) | | | | | | > (c#br '(PTREE: -1) '((#((var-tag) temp.1 (PTREE: (lambda (temp.... | | | | | | (PTREE: -1) | | | | | (PTREE: #f) | | | | > (c#br '(PTREE: ('#<procedure #5 ##fx*?> temp.0 temp.1)) '((#((var-t... | | | | | > (c#br '(PTREE: '#<procedure #5 ##fx*?>) '((#((var-tag) temp.1 (PT... | | | | | (PTREE: '#<procedure #5 ##fx*?>) | | | | | > (c#br '(PTREE: temp.0) '((#((var-tag) temp.1 (PTREE: (lambda (tem... | | | | | (PTREE: 10) | | | | | > (c#br '(PTREE: temp.1) '((#((var-tag) temp.1 (PTREE: (lambda (tem... | | | | | (PTREE: 10) | | | | (PTREE: 100) | | | | > (c#br '(PTREE: (if temp.2 temp.2 ('#<procedure #6 *> temp.0 temp.1)... | | | | | > (c#br '(PTREE: temp.2) '((#((var-tag) temp.2 (PTREE: (lambda (tem... | | | | | (PTREE: 100) | | | | > (c#br '(PTREE: temp.2) '((#((var-tag) temp.2 (PTREE: (lambda (temp.... | | | | (PTREE: 100) | | | (PTREE: 100) | | (PTREE: 100) | (PTREE: (pp 100)) "/Users/feeley/gambit/work/gsc/crap.c"
Marc
P.S. I had to fix a small problem in igsc.scm, so you’ll have to pull my last commit.
On Nov 6, 2015, at 1:32 AM, Bradley Lucier lucier@math.purdue.edu wrote:
On 11/05/2015 07:29 AM, Marc Feeley wrote:
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.
How do you run the compiler through the interpreter so that we can trace the routines in _ptree2.scm and see the input and output in a reasonable way?
Brad