OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library dominator_tree; | 5 library dominator_tree; |
6 | 6 |
7 // Flowgraph dominators in O(m log n) time. Implements the algorithm from | 7 // Flowgraph dominators in O(m log n) time. Implements the algorithm from |
8 // [Lengauer & Tarjan 1979] | 8 // [Lengauer & Tarjan 1979] |
9 // T. Lengauer and R.E. Tarjan, | 9 // T. Lengauer and R.E. Tarjan, |
10 // "A fast algorithm for finding dominators in a flowgraph", | 10 // "A fast algorithm for finding dominators in a flowgraph", |
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
78 return v; | 78 return v; |
79 } else { | 79 } else { |
80 _compress(v); | 80 _compress(v); |
81 return v.label; | 81 return v.label; |
82 } | 82 } |
83 } | 83 } |
84 | 84 |
85 void _link(_Vertex v, _Vertex w) { | 85 void _link(_Vertex v, _Vertex w) { |
86 w.ancestor = v; | 86 w.ancestor = v; |
87 } | 87 } |
88 | 88 |
89 void computeDominatorTree(Object root) { | 89 void computeDominatorTree(Object root) { |
90 _Vertex r = _asVertex(root); | 90 _Vertex r = _asVertex(root); |
91 int n = _idToVertex.length; | 91 int n = _idToVertex.length; |
92 _dfs(r); | 92 _dfs(r); |
93 if (_vertex.length != n) { | 93 if (_vertex.length != n) { |
94 throw new StateError("Not a flowgraph: " | 94 throw new StateError("Not a flowgraph: " |
95 "only ${_vertex.length} of $n vertices reachable"); | 95 "only ${_vertex.length} of $n vertices reachable"); |
96 } | 96 } |
97 for (int i = n - 1; i >= 1; --i) { | 97 for (int i = n - 1; i >= 1; --i) { |
98 _Vertex w = _vertex[i]; | 98 _Vertex w = _vertex[i]; |
(...skipping 13 matching lines...) Expand all Loading... |
112 } | 112 } |
113 for (int i = 1; i < n; ++i) { | 113 for (int i = 1; i < n; ++i) { |
114 _Vertex w = _vertex[i]; | 114 _Vertex w = _vertex[i]; |
115 if (w.dom != _vertex[w.semi]) { | 115 if (w.dom != _vertex[w.semi]) { |
116 w.dom = w.dom.dom; | 116 w.dom = w.dom.dom; |
117 } | 117 } |
118 } | 118 } |
119 r.dom = null; | 119 r.dom = null; |
120 } | 120 } |
121 } | 121 } |
OLD | NEW |