blob: 81309d3e258f1f3048b601a81d531ff8fe819012 [file] [log] [blame]
 // Copyright (c) 2020, 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. class Vertex> { // Input: vertices directly reachable from this vertex. final List successors = []; // Output: the nearest vertex that all paths from the root must go through to // reach this vertex. T? dominator; bool isDominatedBy(T other) { Vertex? d = this; while (d != null) { if (d == other) { return true; } d = d.dominator; } return false; } // Temporaries. See Lengauer and Tarjan. final List _predecessors = []; int _semi = 0; T? _label; T? _ancestor; T? _parent; List? _bucket; } // T. Lengauer and R. E. Tarjan. "A Fast Algorithm for Finding Dominators // in a Flowgraph." computeDominators>(T root) { // Lengauer and Tarjan Step 1. final vertex = []; vertex.add(null); var n = 0; dfs(T v) { n++; vertex.add(v); v._semi = n; v._label = v; v._ancestor = null; for (final w in v.successors) { if (w._semi == 0) { w._parent = v; dfs(w); } w._predecessors.add(v); } } dfs(root); forestCompress(T v) { T ancestor = v._ancestor!; if (ancestor._ancestor != null) { forestCompress(ancestor); ancestor = v._ancestor!; if (ancestor._label!._semi < v._label!._semi) { v._label = ancestor._label; } v._ancestor = ancestor._ancestor; } } T forestEval(T v) { if (v._ancestor == null) { return v; } else { forestCompress(v); return v._label!; } } forestLink(T? v, T w) { w._ancestor = v; } for (var i = vertex.length - 1; i > 1; i--) { final T w = vertex[i]!; // Lengauer and Tarjan Step 2. for (T v in w._predecessors) { if (v._semi == 0) continue; // Unreachable final u = forestEval(v); if (u._semi < w._semi) { w._semi = u._semi; } } Vertex z = vertex[w._semi]!; var b = z._bucket; if (b == null) { z._bucket = b = []; } b.add(w); forestLink(w._parent, w); // Lengauer and Tarjan Step 3. z = w._parent!; b = z._bucket; z._bucket = null; if (b != null) { for (final v in b) { final u = forestEval(v); v.dominator = u._semi < v._semi ? u : w._parent; } } } // Lengauer and Tarjan Step 4. for (var i = 2; i < vertex.length; i++) { final T w = vertex[i]!; if (w.dominator != vertex[w._semi]) { w.dominator = w.dominator!.dominator; } } }