1 files changed, 28 insertions, 0 deletions
diff --git a/Source/VCGeneration/GraphAlgorithms.cs b/Source/VCGeneration/GraphAlgorithms.cs
index 1a8ab9b1..006a923f 100644
--- a/Source/VCGeneration/GraphAlgorithms.cs
+++ b/Source/VCGeneration/GraphAlgorithms.cs
@@ -93,6 +93,34 @@ public static class GraphAlgorithms {
 
     return sortedNodes;
   }
+  
+  // Algorithm from Jeanne Ferrante, Karl J. Ottenstein, Joe D. Warren,
+  // "The Program Dependence Graph and Its Use in Optimization"
+  public static Dictionary<Node, HashSet<Node>> ControlDependence<Node>(this Graph<Node> g) where Node : class, new() {
+    Graph<Node> dual = g.Dual(new Node());
+    DomRelation<Node> pdom = dual.DominatorMap;
+    var result = new Dictionary<Node, HashSet<Node>>();
+
+    var S = g.Edges.Where(e => !pdom.DominatedBy(e.Item1, e.Item2));
+    foreach (var edge in S) {
+      var L = pdom.LeastCommonAncestor(edge.Item1, edge.Item2);
+      var deps = new List<Node>();
+      if (L == edge.Item1) {
+        pdom.DominatedBy(edge.Item2, edge.Item1, deps);
+        deps.Add(edge.Item2);
+        deps.Add(edge.Item1);
+      } else {
+        pdom.DominatedBy(edge.Item2, L, deps);
+        deps.Add(edge.Item2);
+      }
+      if (result.ContainsKey(edge.Item1)) {
+        result[edge.Item1].UnionWith(deps);
+      } else {
+        result[edge.Item1] = new HashSet<Node>(deps);
+      }
+    }
+    return result;
+  }
 
 }