[gambit-list] gsc -report for finding non-reachable defines

Marc Feeley feeley at iro.umontreal.ca
Thu Aug 24 08:00:12 EDT 2017


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:

-------------- next part --------------
A non-text attachment was scrubbed...
Name: foo.dg.pdf
Type: application/pdf
Size: 16181 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20170824/dac6cf24/attachment.pdf>
-------------- next part --------------


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 at 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:
> 
> 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
> _______________________________________________
> Gambit-list mailing list
> Gambit-list at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list



More information about the Gambit-list mailing list