diff options
Diffstat (limited to 'Source/Core/Graph.as')
| -rw-r--r-- | Source/Core/Graph.as | 352 |
1 files changed, 0 insertions, 352 deletions
diff --git a/Source/Core/Graph.as b/Source/Core/Graph.as deleted file mode 100644 index 1466c341..00000000 --- a/Source/Core/Graph.as +++ /dev/null @@ -1,352 +0,0 @@ -using System.Collections;
-namespace Graphing;
-
-type Node = object;
-type Edge = <Node,Node>;
-
-class PreHeader {
- Node myHeader;
- PreHeader(Node h) { myHeader = h; }
-
- public override string ToString() { return "#" + myHeader.ToString(); }
-}
-
-public class Graph {
- private Set<Edge> es;
- private Set<Node> ns;
- private Node source;
- private bool reducible;
- private Set<Node> headers;
- private Map<Node,Set<Node>> backEdgeNodes;
- private Map<Edge,Set<Node>> naturalLoops;
- private Map<Node,Set<Node>> dominatorMap;
- private Map<Node,Set<Node>> immediateDominatorMap;
-
- public Graph(Set<Edge> edges)
- {
- es = edges;
- ns = Set<Node>{ x : <x,y> in es } + Set<Node>{ y : <x,y> in es };
- }
- public Graph()
- { es = Set<Edge>{}; ns = Set<Node>{}; }
-
- public void AddSource(Node x)
- {
- ns += Set<Node>{x};
- source = x;
- }
- public void AddEdge(Node source, Node dest)
- {
- es += Set<Edge>{<source,dest>};
- ns += Set<Node>{source, dest};
- }
-
- public Set<Node> Nodes { get { return ns; } }
- public Set<Edge> Edges { get { return es; } }
-
- public bool Edge(Node x, Node y) { return <x,y> in es; }
- Set<Node> predecessors(Node n)
- {
- Set<Node> result = Set{ x : x in Nodes, Edge(x,n) };
- return result;
- }
- public override string ToString() { return es.ToString(); }
-
- public IEnumerable TopologicalSort()
- {
- <bool,Seq<Node>> <res,ns> = TopSort(this);
- return res ? ns : null;
- }
- public void ComputeLoops()
- {
- <bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
- <reducible,headers,backEdgeNodes,naturalLoops> = Reducible(this,this.source);
- this.reducible = reducible;
- this.headers = headers;
- this.backEdgeNodes = backEdgeNodes;
- this.naturalLoops = naturalLoops;
- return;
- }
- public bool Reducible { get { return reducible; } }
- public IEnumerable Headers { get { return headers; } }
- public IEnumerable BackEdgeNodes(Node h) { return h in backEdgeNodes ? backEdgeNodes[h] : null; }
- public IEnumerable NaturalLoops(Node header, Node backEdgeNode)
- { Edge e = <backEdgeNode,header>; return e in naturalLoops ? naturalLoops[e] : null; }
- public bool Acyclic { get { return Acyclic(this,this.source); } }
- public Map<Node,Set<Node>> DominatorMap
- {
- get {
- if (dominatorMap == null) dominatorMap = ComputeDominators(this, source);
- return dominatorMap;
- }
- }
- public Map<Node,Set<Node>> ImmediateDominatorMap
- {
- get {
- if (immediateDominatorMap == null)
- {
- immediateDominatorMap = Map{};
- foreach(Node y in Nodes)
- {
- Set<Node> nodesThatYDominates = Set{ x : x in Nodes, x != y && (y in DominatorMap[x]) };
- Set<Node> immediateDominatees = Set{ x : x in nodesThatYDominates,
- !(Exists{ v != y && v != x && (v in DominatorMap[x]) : v in nodesThatYDominates })
- };
- immediateDominatorMap[y] = immediateDominatees;
- }
- }
- return immediateDominatorMap;
- }
- }
- public Set<Node> ImmediatelyDominatedBy(Node n) { return ImmediateDominatorMap[n]; }
-
-}
-
-// From AsmL distribution example: TopologicalSort
-<bool,Seq<Node>> TopSort(Graph g)
-{
- Seq<Node> S = Seq{};
- Set<Node> V = g.Nodes;
- bool change = true;
- while ( change )
- {
- change = false;
- Set<Node> X = V - ((Set<Node>) S);
- if ( X != Set{} )
- {
- Node temp = Choose{ v : v in X, !(Exists{ g.Edge(u,v) : u in X }) ifnone null };
- if ( temp == null )
- {
- return <false,Seq<Node>{}>;
- }
- else if ( temp != Seq<Node>{} )
- {
- S += Seq{temp};
- change = true;
- }
- }
- }
- return <true,S>;
-}
-
-bool Acyclic(Graph g, Node source)
-{
- <bool,Seq<Node>> <acyc,xs> = TopSort(g);
- return acyc;
-}
-
-//
-// [Dragon, pp. 670--671]
-// returns map D s.t. d in D(n) iff d dom n
-//
-Map<Node,Set<Node>> ComputeDominators(Graph g, Node source) {
- Set<Node> N = g.Nodes;
- Set<Node> nonSourceNodes = N - Set{source};
- Map<Node,Set<Node>> D = Map{};
- D[source] = Set<Node>{ source };
- foreach (Node n in nonSourceNodes)
- {
- D[n] = N;
- }
- bool change = true;
- while ( change )
- {
- change = false;
- foreach (Node n in nonSourceNodes)
- {
- Set<Set<Node>> allPreds = Set{ D[p] : p in g.predecessors(n) };
- Set<Node> temp = Set<Node>{ n } + BigIntersect(allPreds);
- if ( temp != D[n] )
- {
- change = true;
- D[n] = temp;
- }
- }
- }
- return D;
-}
-
-// [Dragon, Fig. 10.15, p. 604. Algorithm for constructing the natural loop.]
-Set<Node> NaturalLoop(Graph g, Edge backEdge)
-{
- <Node,Node> <n,d> = backEdge;
- Seq<Node> stack = Seq{};
- Set<Node> loop = Set{ d };
- if ( n != d ) // then n is not in loop
- {
- loop += Set{ n };
- stack = Seq{ n } + stack; // push n onto stack
- }
- while ( stack != Seq{} ) // not empty
- {
- Node m = Head(stack);
- stack = Tail(stack); // pop stack
- foreach (Node p in g.predecessors(m))
- {
- if ( !(p in loop) )
- {
- loop += Set{ p };
- stack = Seq{ p } + stack; // push p onto stack
- }
- }
- }
- return loop;
-}
-
-// [Dragon, p. 606]
-<bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
- Reducible(Graph g, Node source) {
- // first, compute the dom relation
- Map<Node,Set<Node>> D = g.DominatorMap;
- return Reducible(g,source,D);
-}
-
-// [Dragon, p. 606]
-<bool, Set<Node>, Map<Node,Set<Node>>, Map<Edge,Set<Node>>>
- Reducible(Graph g, Node source, Map<Node,Set<Node>> DomRelation) {
-
- Set<Edge> edges = g.Edges;
- Set<Edge> backEdges = Set{};
- Set<Edge> nonBackEdges = Set{};
- foreach (Edge e in edges)
- {
- <Node,Node> <x,y> = e; // so there is an edge from x to y
- if ( y in DomRelation[x] ) // y dom x: which means y dominates x
- {
- backEdges += Set{ e };
- }
- else
- {
- nonBackEdges += Set{ e };
- }
- }
- if ( !Acyclic(new Graph(nonBackEdges), source) )
- {
- return <false,Set<Node>{},Map<Node,Set<Node>>{},Map<Edge,Set<Node>>{}>;
- }
- else
- {
- Set<Node> headers = Set{ d : <n,d> in backEdges };
- Map<Node,Set<Node>> backEdgeNodes = Map{ h -> bs : h in headers, bs = Set<Node>{ b : <b,x> in backEdges, x == h } };
- Map<Edge,Set<Node>> naturalLoops = Map{ e -> NaturalLoop(g,e) : e in backEdges };
-
- return <true, headers, backEdgeNodes, naturalLoops>;
- }
-}
-
-// [Dragon, p. 606]
-bool OldReducible(Graph g, Node source) {
- // first, compute the dom relation
- Map<Node,Set<Node>> D = ComputeDominators(g, source);
- return OldReducible(g,source,D);
-}
-
-// [Dragon, p. 606]
-bool OldReducible(Graph g, Node source, Map<Node,Set<Node>> DomRelation) {
-
- Set<Edge> edges = g.Edges;
- Set<Edge> backEdges = Set{};
- Set<Edge> nonBackEdges = Set{};
- foreach (Edge e in edges)
- {
- <Node,Node> <x,y> = e;
- if ( y in DomRelation[x] ) // y dom x
- {
- backEdges += Set{ e };
- }
- else
- {
- nonBackEdges += Set{ e };
- }
- }
- WriteLine("backEdges: " + backEdges);
- WriteLine("nonBackEdges: " + nonBackEdges);
- if ( Acyclic(new Graph(nonBackEdges), source) )
- {
- foreach(Edge e in backEdges)
- {
- Set<Node> naturalLoop = NaturalLoop(g,e);
- WriteLine("Natural loop for back edge '" + e + "' is: " + naturalLoop);
- }
- Set<Node> headers = Set{ d : <n,d> in backEdges };
- WriteLine("Loop headers = " + headers);
-
- edges -= backEdges; // this cuts all of the back edges
- foreach (Node h in headers)
- {
- Set<Edge> bs = Set{ <n,d> : <n,d> in backEdges, d == h };
- Set<Node> preds = Set<Node>{ p : <p,y> in edges, y == h };
- Node preheader = new PreHeader(h);
- edges += Set{ <preheader,h> };
- foreach (Node p in preds)
- {
- edges -= Set{ <p,h> };
- edges += Set{ <p,preheader> };
- }
- }
- Graph newGraph = new Graph(edges);
- WriteLine("transformed graph = " + newGraph);
- return true;
- }
- else
- {
- return false;
- }
-}
-
-void Main()
-{
- Graph g;
- Map<Node,Set<Node>> D;
-/*
- g = new Graph(Set<Edge>{ <1,2>, <1,3>, <2,3> });
- g.AddSource(1);
- Map<Node,Set<Node>> doms = ComputeDominators(g,1);
- WriteLine(doms);
-*/
- g = new Graph(Set<Edge>{
- <1,2>, <1,3>,
- <2,3>,
- <3,4>,
- <4,3>, <4,5>, <4,6>,
- <5,7>,
- <6,7>,
- <7,4>, <7,8>,
- <8,3>, <8,9>, <8,10>,
- <9,1>,
- <10,7>
- });
- g.AddSource(1);
- WriteLine("G = " + g);
- D = ComputeDominators(g,1);
- WriteLine("Dom relation: " + D);
- WriteLine("G's Dominator Map = " + g.DominatorMap);
- WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
- WriteLine("G is reducible: " + OldReducible(g,1,D));
- g.ComputeLoops();
-
- WriteLine("");
-
- g = new Graph(Set<Edge>{ <1,2>, <1,3>, <2,3>, <3,2> });
- g.AddSource(1);
- WriteLine("G = " + g);
- D = ComputeDominators(g,1);
- WriteLine("Dom relation: " + D);
- WriteLine("G's Dominator Map = " + g.DominatorMap);
- WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
- WriteLine("G is reducible: " + OldReducible(g,1,D));
- g.ComputeLoops();
-
- WriteLine("");
-
- g = new Graph(Set<Edge>{ <1,2>, <2,3>, <2,4>, <3,2> });
- g.AddSource(1);
- WriteLine("G = " + g);
- WriteLine("G's Dominator Map = " + g.DominatorMap);
- WriteLine("G's Immediate Dominator Map = " + g.ImmediateDominatorMap);
-// D = ComputeDominators(g,1);
-// WriteLine("Dom relation: " + D);
-// WriteLine("G is reducible: " + OldReducible(g,1,D));
- g.ComputeLoops();
-
-}
\ No newline at end of file |