| 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)))))) |