Debian Codegraph @

lib/util/dominator.scm

raw
1 ;;;
2 ;;; dominator.scm - Calculate dominators of control graph nodes
3 ;;;
4 ;;; Copyright (c) 2015-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module util.dominator
35 (use srfi.42)
36 (export calculate-dominators))
37 (select-module util.dominator)
38
39 ;; Based on
40 ;; Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy:
41 ;; A Simple, Fast Dominance Algorithm,
42 ;; Software Practice and Experience, Vol.4 pp.1-10, 2001.
43
44 ;; A graph is represented in (start, upstreams, downstreams, node-comparator)
45 ;; where
46 ;; start :: Node
47 ;; upstreams :: Node -> [Node]
48 ;; downstreams :: Node -> [Node]
49 ;; node-comparator :: comparator (with hash function)
50 ;;
51 ;; Returns
52 ;; [(node, immediate-dominator-node)]
53
54 (define (calculate-dominators start upstreams downstreams node-comparator)
55 (define t:id->node (make-hash-table 'eqv?))
56 (define t:upstream-ids (make-hash-table 'eqv?)) ; id -> [id]
57 (define t:downstream-ids (make-hash-table 'eqv?)) ; id -> [id]
58 (define t:node->id (make-hash-table node-comparator))
59 (define (id->node id) (hash-table-get t:id->node id #f))
60 (define (node->id node) (hash-table-get t:node->id node #f))
61 (define (id->upstream-ids id) (hash-table-get t:upstream-ids id '()))
62 (define (id->downstream-ids id) (hash-table-get t:downstream-ids id '()))
63
64 (define (postorder node next-id) ; returns next id
65 (if (node->id node)
66 next-id
67 (begin
68 (hash-table-put! t:node->id node #t) ; mark visited
69 (let1 next-id (fold postorder next-id (downstreams node))
70 (hash-table-put! t:id->node next-id node)
71 (hash-table-put! t:node->id node next-id)
72 (+ next-id 1)))))
73
74 (define (setup! node)
75 (let1 id (node->id node)
76 (unless (hash-table-exists? t:upstream-ids id)
77 (hash-table-put! t:upstream-ids id
78 (filter-map node->id (upstreams node)))
79 (hash-table-put! t:downstream-ids id
80 (filter-map node->id (downstreams node)))
81 (for-each setup! (downstreams node)))))
82
83 (define (update doms nid changed?)
84 (let1 b0 (any (^n (and (vector-ref doms n) n)) (id->upstream-ids nid))
85 (unless b0
86 (error "calculate-dominators: something wrong with input graph"))
87 (let1 new-idom (fold (^[n new-idom]
88 (if-let1 m (and (not (eq? n b0))
89 (vector-ref doms n))
90 (intersect doms m new-idom)
91 new-idom))
92 b0 (id->upstream-ids nid))
93 (if (eqv? (vector-ref doms nid) new-idom)
94 changed?
95 (begin (vector-set! doms nid new-idom) #t)))))
96
97 (define (iterate! doms max-nid)
98 (when (fold (^[nid changed?] (update doms nid changed?))
99 #f (iota max-nid (- max-nid 1) -1))
100 (iterate! doms max-nid)))
101
102 (define (intersect doms b1 b2)
103 (let loop ([finger1 b1]
104 [finger2 b2])
105 (cond [(= finger1 finger2) finger1]
106 [(< finger1 finger2) (loop (vector-ref doms finger1) finger2)]
107 [else (loop finger1 (vector-ref doms finger2))])))
108
109 (let* ([nnodes (postorder start 0)]
110 [doms (make-vector nnodes #f)])
111 (vector-set! doms (- nnodes 1) (- nnodes 1))
112 (setup! start)
113 (iterate! doms (- nnodes 1))
114 (list-ec (: i (- nnodes 1))
115 (list (id->node i) (id->node (vector-ref doms i))))))