runtime/observatory/lib/dominator_tree.dart

// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

library dominator_tree;

// Flowgraph dominators in O(m log n) time. Implements the algorithm from
// [Lengauer & Tarjan 1979]
// T. Lengauer and R.E. Tarjan,
// "A fast algorithm for finding dominators in a flowgraph",
// ACM Transactions on Programming Language and Systems, 1(1):121-141, 1979.

// Internal vertex information used inside 'Dominator'.
// Field names mostly follow naming in [Lengauer & Tarjan 1979].
class _Vertex {
  final Object id;
  _Vertex dom;
  _Vertex parent;
  _Vertex ancestor;
  _Vertex label;
  int semi;
  final List<_Vertex> pred = new List<_Vertex>();
  final List<_Vertex> bucket = new List<_Vertex>();
  // TODO(koda): Avoid duplication by having an interface for 'id' with
  // access to outgoing edges, and/or clearing 'succ' after constructing
  // inverse graph in 'pred'.
  final List<_Vertex> succ = new List<_Vertex>();
  _Vertex(this.id) { label = this; }
}

// Utility to compute immediate dominators. Usage:
// 1. Build the flowgraph using 'addEdges'.
// 2. Call 'computeDominatorTree' once.
// 3. Use 'dominator' to access result.
// The instance can only be used once.
class Dominator {
  final Map<Object, _Vertex> _idToVertex = new Map<Object, _Vertex>();
  final List<_Vertex> _vertex = new List<_Vertex>();
  
  void addEdges(Object u, Iterable<Object> vs) {
    _asVertex(u).succ.addAll(vs.map(_asVertex));
  }
  
  // Returns the immediate dominator of 'v', or null if 'v' is the root.
  Object dominator(Object v) {
    _Vertex dom = _asVertex(v).dom;
    return dom == null ? null : dom.id;
  }
  
  _Vertex _asVertex(Object u) {
    return _idToVertex.putIfAbsent(u, () => new _Vertex(u));
  }
  
  void _dfs(_Vertex v) {
    v.semi = _vertex.length;
    _vertex.add(v);
    for (_Vertex w in v.succ) {
      if (w.semi == null) {
        w.parent = v;
        _dfs(w);
      }
      w.pred.add(v);
    }
  }

  void _compress(_Vertex v) {
    if (v.ancestor.ancestor != null) {
      _compress(v.ancestor);
      if (v.ancestor.label.semi < v.label.semi) {
        v.label = v.ancestor.label;
      }
      v.ancestor = v.ancestor.ancestor;
    }
  }

  _Vertex _eval(_Vertex v) {
    if (v.ancestor == null) {
      return v;
    } else {
      _compress(v);
      return v.label;
    }
  }

  void _link(_Vertex v, _Vertex w) {
    w.ancestor = v;
  }
  
  void computeDominatorTree(Object root) {
    _Vertex r = _asVertex(root);
    int n = _idToVertex.length;
    _dfs(r);
    if (_vertex.length != n) {
      throw new StateError("Not a flowgraph: "
          "only ${_vertex.length} of $n vertices reachable");
    }
    for (int i = n - 1; i >= 1; --i) {
      _Vertex w = _vertex[i];
      for (_Vertex v in w.pred) {
        _Vertex u = _eval(v);
        if (u.semi < w.semi) {
          w.semi = u.semi;
        }
      }
      _vertex[w.semi].bucket.add(w);
      _link(w.parent, w);
      for (_Vertex v in w.parent.bucket) {
        _Vertex u = _eval(v);
        v.dom = u.semi < v.semi ? u : w.parent;
      }
      w.parent.bucket.clear();
    }
    for (int i = 1; i < n; ++i) {
      _Vertex w = _vertex[i];
      if (w.dom != _vertex[w.semi]) {
        w.dom = w.dom.dom;
      }
    }
    r.dom = null;
  }
}