Dependeny graphs for reachable bindings: Gambit 4.9.3 vs 4.9.4
Hello. For a long time, I have been using gsc to determine all reachable bindings (functions and global variables) of a Scheme program with gsc -c -dg foo.scm This dependeny graph analysis is fast and was the most accurate one I found in the Scheme world. When stepping from 4.9.3 to 4.9.4(git), the analysis misses many reachable bindings (i.e. many false negatives, no false positives). For a large example program, the number drops from 7178 to 6248. Is this expected? Do I need to adjust my gsc options above? Greetings Sven
Afficher les réponses par date
The dependency graph is computed after program transformations and (some) optimizations are performed. It could be the case that v4.9.4 is doing a better job at optimizing the code than v4.9.3 so that a procedure that was kept in the code by v4.9.3 has been eliminated by v4.9.4. It is hard to tell in your particular case which optimization is causing the issue. Here’s a simple example: $ cat dg.scm (declare (optimize-dead-definitions)) (declare (standard-bindings) (block) (inlining-limit 500)) (define (f x) (list x x)) (define (g x) (if x (f (list 1 x)) 42)) (define (h x) (list (f x) (g x))) (pp (g #f)) $ gsc -c -expansion dg.scm Expansion: (pp 42) With v4.9.3 the expansion will include the definition of f, g and h even though none of those definitions are required by the code (due to procedure inlining). Perhaps you could look at the difference in dependency graphs generated by v4.9.3 and v4.9.4 to find what is now considered dead that wasn’t in v4.9.3? This might point to an optimization you need to turn off to get the same result as v4.9.3 . The drop from 7178 to 6248 “reachable” procedures may simply be better inlining by the v4.9.4 compiler. Turning off inlining with a (declare (not inline)) may be all that is needed. Marc
On Jan 4, 2022, at 5:02 AM, Sven Hartrumpf <hartrumpf@gmx.net> wrote:
Hello.
For a long time, I have been using gsc to determine all reachable bindings (functions and global variables) of a Scheme program with
gsc -c -dg foo.scm
This dependeny graph analysis is fast and was the most accurate one I found in the Scheme world. When stepping from 4.9.3 to 4.9.4(git), the analysis misses many reachable bindings (i.e. many false negatives, no false positives). For a large example program, the number drops from 7178 to 6248. Is this expected? Do I need to adjust my gsc options above?
Greetings Sven
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://mailman.iro.umontreal.ca/cgi-bin/mailman/listinfo/gambit-list
Thanks for the answer, Marc. You wrote, 2022-01-04 09:14:
The dependency graph is computed after program transformations and (some) optimizations are performed. It could be the case that v4.9.4 is doing a better job at optimizing the code than v4.9.3 so that a procedure that was kept in the code by v4.9.3 has been eliminated by v4.9.4. It is hard to tell in your particular case which optimization is causing the issue.
Here’s a simple example:
$ cat dg.scm (declare (optimize-dead-definitions)) (declare (standard-bindings) (block) (inlining-limit 500))
(define (f x) (list x x))
(define (g x) (if x (f (list 1 x)) 42))
(define (h x) (list (f x) (g x)))
(pp (g #f)) $ gsc -c -expansion dg.scm Expansion:
(pp 42)
Impressive.
With v4.9.3 the expansion will include the definition of f, g and h even though none of those definitions are required by the code (due to procedure inlining).
Perhaps you could look at the difference in dependency graphs generated by v4.9.3 and v4.9.4 to find what is now considered dead that wasn’t in v4.9.3?
Too large, will try that with a smaller program.
This might point to an optimization you need to turn off to get the same result as v4.9.3 . The drop from 7178 to 6248 “reachable” procedures may simply be better inlining by the v4.9.4 compiler. Turning off inlining with a (declare (not inline)) may be all that is needed.
I am already using: (declare (r5rs-scheme) (not constant-fold) (not inline) (optimize-dead-definitions) (standard-bindings) (extended-bindings)) Ciao Sven
On Jan 4, 2022, at 9:31 AM, Sven Hartrumpf <hartrumpf@gmx.net> wrote:
Too large, will try that with a smaller program.
This might point to an optimization you need to turn off to get the same result as v4.9.3 . The drop from 7178 to 6248 “reachable” procedures may simply be better inlining by the v4.9.4 compiler. Turning off inlining with a (declare (not inline)) may be all that is needed.
Just reading through the list of 930 definitions (7178-6248) may give you a clue if they have common characteristic (small? or from the same “module”?) or unusual properties (defined more than once?). It could be the case that there is a single definition that is causing 929 others to be considered dead by v4.9.4 . For example your code may be calling a “print-report” procedure, and the implementation of print-report uses 929 procedures that are not used elsewhere than the implementation of print-report. If the v4.9.4 optimizer is smart enough to figure out that print-report is not actually needed, then that causes a difference of 930 dead procedures. Marc
Investigating the original .dg files showed that the format was extended so that my (not too clever) postprocessor missed some pieces of information. For example, some dependency arcs are now annotated with "[style = dotted]". After fixing this in my postprocessor, the reachability analyses are identical when using Gambit 4.9.3 and 4.9.4. Ciao Sven
Indeed v4.9.4 adds dotted lines in the dependency graph. The meaning of the lines is: - solid line from A to B: procedure A contains a call to procedure B - dotted line from A to B: procedure A contains a read or write of variable B Sometimes there will be both a solid and dotted line from A to B. This happens often when speculative inlining is done (to respect R5RS semantics). For example: (define (f x) (sin x)) will be compiled as: (define f (lambda (x) (if (and ('#<procedure #2 ##eq?> sin '#<procedure #3 sin>) ('#<procedure #4 ##flonum?> x)) ('#<procedure #5 ##flsin> x) (sin x)))) Procedure f contains a call to sin and a variable reference of sin, so there will be a solid and dotted line between f and sin in the dependency graph: Moreover, sin is in black to indicate that the file does not contain a definition of sin. It can help identify undefined procedures/variables, or procedures that should be imported from other modules. Marc
On Jan 4, 2022, at 10:15 AM, Sven Hartrumpf <hartrumpf@gmx.net> wrote:
Investigating the original .dg files showed that the format was extended so that my (not too clever) postprocessor missed some pieces of information. For example, some dependency arcs are now annotated with "[style = dotted]".
After fixing this in my postprocessor, the reachability analyses are identical when using Gambit 4.9.3 and 4.9.4.
Ciao Sven
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://mailman.iro.umontreal.ca/cgi-bin/mailman/listinfo/gambit-list
participants (2)
-
Marc Feeley -
Sven Hartrumpf