1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
using Graphing;
using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
namespace Microsoft.Boogie {
public static class GraphAlgorithms {
public static Graph<Node> Dual<Node>(this Graph<Node> g, Node dummySource) {
var exits = g.Nodes.Where(n => g.Successors(n).Count() == 0).ToList();
if (exits.Count == 0)
return null;
var dual = new Graph<Node>(new HashSet<Tuple<Node, Node>>(g.Edges.Select(e => new Tuple<Node, Node>(e.Item2, e.Item1))));
if (exits.Count == 1)
dual.AddSource(exits[0]);
else {
dual.AddSource(dummySource);
foreach (var exit in exits)
dual.AddEdge(dummySource, exit);
}
return dual;
}
public static List<Tuple<Node, bool>> LoopyTopSort<Node>(this Graph<Node> g) {
Contract.Assert(g.Reducible);
int n = g.Nodes.Count;
var nodeToNumber = new Dictionary<Node, int>(n);
var numberToNode = new Node[n];
var allNodes = new List<int>();
int counter = 0;
foreach (Node node in g.Nodes) {
numberToNode[counter] = node;
nodeToNumber[node] = counter;
allNodes.Add(counter);
counter++;
}
var loops = new List<int>[n];
foreach (var h in g.Headers) {
var loopNodes = new HashSet<Node>();
foreach (var b in g.BackEdgeNodes(h))
loopNodes.UnionWith(g.NaturalLoops(h, b));
loops[nodeToNumber[h]] =
new List<int>(loopNodes.Select(node => nodeToNumber[node]));
}
var successors = new List<int>[n];
int[] incomingEdges = new int[n];
foreach (var e in g.Edges) {
Contract.Assert(e.Item1 != null);
Contract.Assert(e.Item2 != null);
int source = nodeToNumber[e.Item1], target = nodeToNumber[e.Item2];
if (loops[target] == null || !loops[target].Contains(source)) {
if (successors[source] == null)
successors[source] = new List<int>();
successors[source].Add(target);
incomingEdges[target]++;
}
}
var sortedNodes = new List<Tuple<Node, bool>>();
var regionStack = new Stack<Tuple<Node, List<int>>>();
regionStack.Push(new Tuple<Node, List<int>>(default(Node), allNodes));
while (regionStack.Count != 0) {
int rootIndex = -1;
foreach (var i in regionStack.Peek().Item2) {
if (incomingEdges[i] == 0) {
rootIndex = i;
break;
}
}
if (rootIndex == -1) {
var region = regionStack.Pop();
if (regionStack.Count != 0)
sortedNodes.Add(new Tuple<Node, bool>(region.Item1, true));
continue;
}
incomingEdges[rootIndex] = -1;
sortedNodes.Add(new Tuple<Node, bool>(numberToNode[rootIndex], false));
if (successors[rootIndex] != null)
foreach (int s in successors[rootIndex])
incomingEdges[s]--;
if (loops[rootIndex] != null)
regionStack.Push(new Tuple<Node, List<int>>(numberToNode[rootIndex],
loops[rootIndex]));
}
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;
}
}
}
|
