Hi.
Thanks to a suggestion by Marc on the Chicken mailing list, I am experimenting with using the output of 'gsc -report' to remove non-reachable defines. I assume each defined identifier reported with D and one of A or R or C as reachable, all others as non-reachable. The found set of non-reachable identifiers is incomplete, but it can be improved by repeating the analysis on the reduced source:
scms r-matcher.scm
cond-expand-command: ... alexpand-command: ... reachable-command: (gsc -:h3700000 -report r-matcher.alexp > r-matcher.alexp.gsc) reduce-command: (cfa-reduce -k r-matcher.alexp r-matcher.reach > r-matcher.rea1) defines: #removed: 718 (24.73%) #kept: 2185 iter 1 size: 3822249 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea1 > r-matcher.rea1.gsc) reduce-command: (cfa-reduce -k r-matcher.rea1 r-matcher.reach > r-matcher.rea2) defines: #removed: 252 (11.53%) #kept: 1933 iter 2 size: 3519136 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea2 > r-matcher.rea2.gsc) reduce-command: (cfa-reduce -k r-matcher.rea2 r-matcher.reach > r-matcher.rea3) defines: #removed: 150 (7.76%) #kept: 1783 iter 3 size: 3277324 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea3 > r-matcher.rea3.gsc) reduce-command: (cfa-reduce -k r-matcher.rea3 r-matcher.reach > r-matcher.rea4) defines: #removed: 93 (5.22%) #kept: 1690 iter 4 size: 3154753 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea4 > r-matcher.rea4.gsc) reduce-command: (cfa-reduce -k r-matcher.rea4 r-matcher.reach > r-matcher.rea5) defines: #removed: 42 (2.49%) #kept: 1648 iter 5 size: 3000686 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea5 > r-matcher.rea5.gsc) reduce-command: (cfa-reduce -k r-matcher.rea5 r-matcher.reach > r-matcher.rea6) defines: #removed: 60 (3.64%) #kept: 1588 iter 6 size: 2924187 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea6 > r-matcher.rea6.gsc) reduce-command: (cfa-reduce -k r-matcher.rea6 r-matcher.reach > r-matcher.rea7) defines: #removed: 26 (1.64%) #kept: 1562 iter 7 size: 2600067 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea7 > r-matcher.rea7.gsc) reduce-command: (cfa-reduce -k r-matcher.rea7 r-matcher.reach > r-matcher.rea8) defines: #removed: 16 (1.02%) #kept: 1546 iter 8 size: 2586789 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea8 > r-matcher.rea8.gsc) reduce-command: (cfa-reduce -k r-matcher.rea8 r-matcher.reach > r-matcher.rea9) defines: #removed: 12 (0.78%) #kept: 1534 iter 9 size: 2584936 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea9 > r-matcher.rea9.gsc) reduce-command: (cfa-reduce -k r-matcher.rea9 r-matcher.reach > r-matcher.rea10) defines: #removed: 6 (0.39%) #kept: 1528 iter 10 size: 2580332 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea10 > r-matcher.rea10.gsc) reduce-command: (cfa-reduce -k r-matcher.rea10 r-matcher.reach > r-matcher.rea11) defines: #removed: 1 (0.07%) #kept: 1527 iter 11 size: 2579734 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea11 > r-matcher.rea11.gsc) reduce-command: (cfa-reduce -k r-matcher.rea11 r-matcher.reach > r-matcher.rea12) defines: #removed: 0 (0.00%) #kept: 1527 iter 12 size: 2579734 bytes
The loop is terminated if no change of the source file is achieved (fixed point). Here are some questions:
1. There are still non-reachable functions in the final source file, e.g. if two functions call each other but are never called from a third function.
2. Can the analysis by 'gsc -report' be made more aggressive or can it be hinted by providing some identifiers that are known to be non-reachable?
3. Is there a way to stop gsc when the report is ready? Without such a feature, the above 12-step analysis takes 20 minutes because it also generates .o files in each iteration.
Greetings Sven
Afficher les réponses par date
A better way to determine which definitions are live is to use the tree shaker. Use (declare (optimize-dead-definitions)) and “gsc -dg” to create a dependency graph file “foo.dg” and then look at all the names in the foo.dg file (which can also be visualized with the “dot” program). You probably also want to disable inlining with (declare (not inline)) if you want to disregard the fact that definitions can become dead if they are inlined at all the call sites.
For example:
bash$ gsc -c -dg foo.scm;echo not defined:;fgrep '" [label =' foo.dg | sed -e 's/^ //g' -e 's/" [label =.*$/"/g' | sort | uniq;echo live including not defined:;fgrep ' -> ' foo.dg | sed -e 's/^ //g' -e 's/;$//g' -e $'s/ -> /\\n/g' | sort | uniq not defined: "*" "+" "println" live including not defined: "*" "+" "c" "d" "e" "main" "println" "| foo|" bash$ cat foo.scm (declare (optimize-dead-definitions) (block) (not inline) )
(define (a x) (if (< x 100) (a (b x)) x))
(define (b x) (* x 2))
(define (c x) (d (e x)))
(define (d x) (* x x))
(define (e x) (+ x 1))
(define (main) (println (c 10)))
(main) bash$ cat foo.dg digraph "/Users/feeley/foo" { graph [splines = true overlap = false rankdir = "TD"]; node [fontname = "Courier New" shape = "none"]; "println" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> println </font></td></tr></table>>]; "+" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> + </font></td></tr></table>>]; "*" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> * </font></td></tr></table>>]; "main" -> "println"; "main" -> "c"; "e" -> "+"; "d" -> "*"; "c" -> "e"; "c" -> "d"; "| foo|" -> "main"; }
The output of “dot -O -Tpdf foo.dg” is:
The black nodes indicate global variables that are not defined in the source file. The node | foo| represents the file’s toplevel expressions. Arrows represent dependencies.
Marc
On Aug 24, 2017, at 6:12 AM, Sven Hartrumpf hartrumpf@gmx.net wrote:
Hi.
Thanks to a suggestion by Marc on the Chicken mailing list, I am experimenting with using the output of 'gsc -report' to remove non-reachable defines. I assume each defined identifier reported with D and one of A or R or C as reachable, all others as non-reachable. The found set of non-reachable identifiers is incomplete, but it can be improved by repeating the analysis on the reduced source:
scms r-matcher.scm
cond-expand-command: ... alexpand-command: ... reachable-command: (gsc -:h3700000 -report r-matcher.alexp > r-matcher.alexp.gsc) reduce-command: (cfa-reduce -k r-matcher.alexp r-matcher.reach > r-matcher.rea1) defines: #removed: 718 (24.73%) #kept: 2185 iter 1 size: 3822249 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea1 > r-matcher.rea1.gsc) reduce-command: (cfa-reduce -k r-matcher.rea1 r-matcher.reach > r-matcher.rea2) defines: #removed: 252 (11.53%) #kept: 1933 iter 2 size: 3519136 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea2 > r-matcher.rea2.gsc) reduce-command: (cfa-reduce -k r-matcher.rea2 r-matcher.reach > r-matcher.rea3) defines: #removed: 150 (7.76%) #kept: 1783 iter 3 size: 3277324 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea3 > r-matcher.rea3.gsc) reduce-command: (cfa-reduce -k r-matcher.rea3 r-matcher.reach > r-matcher.rea4) defines: #removed: 93 (5.22%) #kept: 1690 iter 4 size: 3154753 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea4 > r-matcher.rea4.gsc) reduce-command: (cfa-reduce -k r-matcher.rea4 r-matcher.reach > r-matcher.rea5) defines: #removed: 42 (2.49%) #kept: 1648 iter 5 size: 3000686 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea5 > r-matcher.rea5.gsc) reduce-command: (cfa-reduce -k r-matcher.rea5 r-matcher.reach > r-matcher.rea6) defines: #removed: 60 (3.64%) #kept: 1588 iter 6 size: 2924187 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea6 > r-matcher.rea6.gsc) reduce-command: (cfa-reduce -k r-matcher.rea6 r-matcher.reach > r-matcher.rea7) defines: #removed: 26 (1.64%) #kept: 1562 iter 7 size: 2600067 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea7 > r-matcher.rea7.gsc) reduce-command: (cfa-reduce -k r-matcher.rea7 r-matcher.reach > r-matcher.rea8) defines: #removed: 16 (1.02%) #kept: 1546 iter 8 size: 2586789 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea8 > r-matcher.rea8.gsc) reduce-command: (cfa-reduce -k r-matcher.rea8 r-matcher.reach > r-matcher.rea9) defines: #removed: 12 (0.78%) #kept: 1534 iter 9 size: 2584936 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea9 > r-matcher.rea9.gsc) reduce-command: (cfa-reduce -k r-matcher.rea9 r-matcher.reach > r-matcher.rea10) defines: #removed: 6 (0.39%) #kept: 1528 iter 10 size: 2580332 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea10 > r-matcher.rea10.gsc) reduce-command: (cfa-reduce -k r-matcher.rea10 r-matcher.reach > r-matcher.rea11) defines: #removed: 1 (0.07%) #kept: 1527 iter 11 size: 2579734 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea11 > r-matcher.rea11.gsc) reduce-command: (cfa-reduce -k r-matcher.rea11 r-matcher.reach > r-matcher.rea12) defines: #removed: 0 (0.00%) #kept: 1527 iter 12 size: 2579734 bytes
The loop is terminated if no change of the source file is achieved (fixed point). Here are some questions:
- There are still non-reachable functions in the final source file, e.g.
if two functions call each other but are never called from a third function.
- Can the analysis by 'gsc -report' be made more aggressive or can it be hinted
by providing some identifiers that are known to be non-reachable?
- Is there a way to stop gsc when the report is ready? Without such a feature,
the above 12-step analysis takes 20 minutes because it also generates .o files in each iteration.
Greetings Sven _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
By the way, without the optimize-dead-definitions declaration you would get this dependency graph:
Which shows that nothing is dependent on “a” (nothing points to it) and also shows what “a” depends on.
A “gsc -report” (with or without the optimize-dead-definitions) will show that a, b, c, d, e and main are defined and called. The dependency graph is more precise because it is computed using a reachability analysis (similar to a garbage collector) on the GVM code that is generated by the compiler, so you can observe the result of various optimizations (inlining, dead definition removal, constant folding, etc).
Marc
On Aug 24, 2017, at 8:00 AM, Marc Feeley feeley@iro.umontreal.ca wrote:
A better way to determine which definitions are live is to use the tree shaker. Use (declare (optimize-dead-definitions)) and “gsc -dg” to create a dependency graph file “foo.dg” and then look at all the names in the foo.dg file (which can also be visualized with the “dot” program). You probably also want to disable inlining with (declare (not inline)) if you want to disregard the fact that definitions can become dead if they are inlined at all the call sites.
For example:
bash$ gsc -c -dg foo.scm;echo not defined:;fgrep '" [label =' foo.dg | sed -e 's/^ //g' -e 's/" [label =.*$/"/g' | sort | uniq;echo live including not defined:;fgrep ' -> ' foo.dg | sed -e 's/^ //g' -e 's/;$//g' -e $'s/ -> /\\n/g' | sort | uniq not defined: "*" "+" "println" live including not defined: "*" "+" "c" "d" "e" "main" "println" "| foo|" bash$ cat foo.scm (declare (optimize-dead-definitions) (block) (not inline) )
(define (a x) (if (< x 100) (a (b x)) x))
(define (b x) (* x 2))
(define (c x) (d (e x)))
(define (d x) (* x x))
(define (e x) (+ x 1))
(define (main) (println (c 10)))
(main) bash$ cat foo.dg digraph "/Users/feeley/foo" { graph [splines = true overlap = false rankdir = "TD"]; node [fontname = "Courier New" shape = "none"]; "println" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> println </font></td></tr></table>>]; "+" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> + </font></td></tr></table>>]; "*" [label = <<table border="0" cellborder="0" cellspacing="0" cellpadding="0" bgcolor="black"><tr><td><font face="Courier Bold" color="white"> * </font></td></tr></table>>]; "main" -> "println"; "main" -> "c"; "e" -> "+"; "d" -> "*"; "c" -> "e"; "c" -> "d"; "| foo|" -> "main"; }
The output of “dot -O -Tpdf foo.dg” is:
<foo.dg.pdf>
The black nodes indicate global variables that are not defined in the source file. The node | foo| represents the file’s toplevel expressions. Arrows represent dependencies.
Marc
On Aug 24, 2017, at 6:12 AM, Sven Hartrumpf hartrumpf@gmx.net wrote:
Hi.
Thanks to a suggestion by Marc on the Chicken mailing list, I am experimenting with using the output of 'gsc -report' to remove non-reachable defines. I assume each defined identifier reported with D and one of A or R or C as reachable, all others as non-reachable. The found set of non-reachable identifiers is incomplete, but it can be improved by repeating the analysis on the reduced source:
scms r-matcher.scm
cond-expand-command: ... alexpand-command: ... reachable-command: (gsc -:h3700000 -report r-matcher.alexp > r-matcher.alexp.gsc) reduce-command: (cfa-reduce -k r-matcher.alexp r-matcher.reach > r-matcher.rea1) defines: #removed: 718 (24.73%) #kept: 2185 iter 1 size: 3822249 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea1 > r-matcher.rea1.gsc) reduce-command: (cfa-reduce -k r-matcher.rea1 r-matcher.reach > r-matcher.rea2) defines: #removed: 252 (11.53%) #kept: 1933 iter 2 size: 3519136 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea2 > r-matcher.rea2.gsc) reduce-command: (cfa-reduce -k r-matcher.rea2 r-matcher.reach > r-matcher.rea3) defines: #removed: 150 (7.76%) #kept: 1783 iter 3 size: 3277324 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea3 > r-matcher.rea3.gsc) reduce-command: (cfa-reduce -k r-matcher.rea3 r-matcher.reach > r-matcher.rea4) defines: #removed: 93 (5.22%) #kept: 1690 iter 4 size: 3154753 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea4 > r-matcher.rea4.gsc) reduce-command: (cfa-reduce -k r-matcher.rea4 r-matcher.reach > r-matcher.rea5) defines: #removed: 42 (2.49%) #kept: 1648 iter 5 size: 3000686 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea5 > r-matcher.rea5.gsc) reduce-command: (cfa-reduce -k r-matcher.rea5 r-matcher.reach > r-matcher.rea6) defines: #removed: 60 (3.64%) #kept: 1588 iter 6 size: 2924187 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea6 > r-matcher.rea6.gsc) reduce-command: (cfa-reduce -k r-matcher.rea6 r-matcher.reach > r-matcher.rea7) defines: #removed: 26 (1.64%) #kept: 1562 iter 7 size: 2600067 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea7 > r-matcher.rea7.gsc) reduce-command: (cfa-reduce -k r-matcher.rea7 r-matcher.reach > r-matcher.rea8) defines: #removed: 16 (1.02%) #kept: 1546 iter 8 size: 2586789 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea8 > r-matcher.rea8.gsc) reduce-command: (cfa-reduce -k r-matcher.rea8 r-matcher.reach > r-matcher.rea9) defines: #removed: 12 (0.78%) #kept: 1534 iter 9 size: 2584936 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea9 > r-matcher.rea9.gsc) reduce-command: (cfa-reduce -k r-matcher.rea9 r-matcher.reach > r-matcher.rea10) defines: #removed: 6 (0.39%) #kept: 1528 iter 10 size: 2580332 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea10 > r-matcher.rea10.gsc) reduce-command: (cfa-reduce -k r-matcher.rea10 r-matcher.reach > r-matcher.rea11) defines: #removed: 1 (0.07%) #kept: 1527 iter 11 size: 2579734 bytes reachable-command: (gsc -:h3700000 -report r-matcher.rea11 > r-matcher.rea11.gsc) reduce-command: (cfa-reduce -k r-matcher.rea11 r-matcher.reach > r-matcher.rea12) defines: #removed: 0 (0.00%) #kept: 1527 iter 12 size: 2579734 bytes
The loop is terminated if no change of the source file is achieved (fixed point). Here are some questions:
- There are still non-reachable functions in the final source file, e.g.
if two functions call each other but are never called from a third function.
- Can the analysis by 'gsc -report' be made more aggressive or can it be hinted
by providing some identifiers that are known to be non-reachable?
- Is there a way to stop gsc when the report is ready? Without such a feature,
the above 12-step analysis takes 20 minutes because it also generates .o files in each iteration.
Greetings Sven _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
MF, 2017-08-24 08:00:
A better way to determine which definitions are live is to use the tree shaker. Use (declare (optimize-dead-definitions)) and “gsc -dg” to create a dependency graph file “foo.dg” and then look at all the names in the foo.dg file (which can also be visualized with the “dot” program). You probably also want to disable inlining with (declare (not inline)) if you want to disregard the fact that definitions can become dead if they are inlined at all the call sites.
Yas. That works better than -report. Which option should I use to _avoid_ that defined constant values (like (define *opt #t)) that are never changed are optimized away and hence will not appear in .dg? At the moment, I use the following options: (declare (r5rs-scheme) (block) (not constant-fold) (not inline) (optimize-dead-definitions) (standard-bindings) (extended-bindings))
Greetings Sven
Just remove the block declaration. Not sure why I put it there in the first place…
Marc
On Aug 24, 2017, at 4:20 PM, Sven Hartrumpf hartrumpf@gmx.net wrote:
MF, 2017-08-24 08:00:
A better way to determine which definitions are live is to use the tree shaker. Use (declare (optimize-dead-definitions)) and “gsc -dg” to create a dependency graph file “foo.dg” and then look at all the names in the foo.dg file (which can also be visualized with the “dot” program). You probably also want to disable inlining with (declare (not inline)) if you want to disregard the fact that definitions can become dead if they are inlined at all the call sites.
Yas. That works better than -report. Which option should I use to _avoid_ that defined constant values (like (define *opt #t)) that are never changed are optimized away and hence will not appear in .dg? At the moment, I use the following options: (declare (r5rs-scheme) (block) (not constant-fold) (not inline) (optimize-dead-definitions) (standard-bindings) (extended-bindings))
Greetings Sven _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
-
Marc Feeley -
Sven Hartrumpf