summaryrefslogtreecommitdiff
path: root/module
diff options
context:
space:
mode:
authorAndy Wingo <wingo@pobox.com>2025-01-22 16:50:52 +0100
committerAndy Wingo <wingo@pobox.com>2025-01-22 16:50:52 +0100
commit47dce42edb3d158d6a71eb4da8421287b88c9ef1 (patch)
treeab624927a5217ca53749ae360892bb9491347dd0 /module
parent60c1e5cc422d8b5d0c7158c8cbcb17a741b7a7f3 (diff)
downloadguile-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')
-rw-r--r--module/language/cps/graphs.scm30
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))