diff options
author | Andy Wingo <wingo@pobox.com> | 2025-01-22 16:50:52 +0100 |
---|---|---|
committer | Andy Wingo <wingo@pobox.com> | 2025-01-22 16:50:52 +0100 |
commit | 47dce42edb3d158d6a71eb4da8421287b88c9ef1 (patch) | |
tree | ab624927a5217ca53749ae360892bb9491347dd0 /module/language | |
parent | 60c1e5cc422d8b5d0c7158c8cbcb17a741b7a7f3 (diff) | |
download | guile-47dce42edb3d158d6a71eb4da8421287b88c9ef1.tar.gz |
Use transient intset/intmap optimizations when computing SCCs
* module/language/cps/graphs.scm (compute-sorted-strongly-connected-components):
Use more transient data structures.
Diffstat (limited to 'module/language')
-rw-r--r-- | module/language/cps/graphs.scm | 30 |
1 files changed, 16 insertions, 14 deletions
diff --git a/module/language/cps/graphs.scm b/module/language/cps/graphs.scm index a518afc55..78e4ef070 100644 --- a/module/language/cps/graphs.scm +++ b/module/language/cps/graphs.scm @@ -1,6 +1,6 @@ ;;; Continuation-passing style (CPS) intermediate language (IL) -;; Copyright (C) 2013-2015, 2017-2021 Free Software Foundation, Inc. +;; Copyright (C) 2013-2015, 2017-2021, 2025 Free Software Foundation, Inc. ;;;; This library is free software; you can redistribute it and/or ;;;; modify it under the terms of the GNU Lesser General Public @@ -227,23 +227,25 @@ connected components in sorted order." start) start)) (define node-components - (intmap-fold (lambda (id nodes out) - (intset-fold (lambda (node out) (intmap-add out node id)) - nodes out)) - components - empty-intmap)) + (persistent-intmap + (intmap-fold (lambda (id nodes out) + (intset-fold (lambda (node out) (intmap-add! out node id)) + nodes out)) + components + empty-intmap))) (define (node-component node) (intmap-ref node-components node)) (define (component-successors id nodes) (intset-remove - (intset-fold (lambda (node out) - (intset-fold - (lambda (successor out) - (intset-add out (node-component successor))) - (intmap-ref edges node) - out)) - nodes - empty-intset) + (persistent-intset + (intset-fold (lambda (node out) + (intset-fold + (lambda (successor out) + (intset-add! out (node-component successor))) + (intmap-ref edges node) + out)) + nodes + empty-intset)) id)) (define component-edges (intmap-map component-successors components)) |