Initial set of files.

1 files changed, 352 insertions, 0 deletions

diff --git a/Source/Core/Graph.as b/Source/Core/Graph.as
new file mode 100644
index 00000000..1466c341
--- /dev/null
+++ b/Source/Core/Graph.as
@@ -0,0 +1,352 @@
+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