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