From be51da047ec7d43446649ad7726211baa0e6640c Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Fri, 18 Sep 2009 04:32:27 +0000
Subject: [PATCH] add SESETree

---
 Robust/src/Analysis/MLP/SESETree.java | 154 ++++++++++++++++++++++++++
 1 file changed, 154 insertions(+)
 create mode 100644 Robust/src/Analysis/MLP/SESETree.java

diff --git a/Robust/src/Analysis/MLP/SESETree.java b/Robust/src/Analysis/MLP/SESETree.java
new file mode 100644
index 00000000..62e91c10
--- /dev/null
+++ b/Robust/src/Analysis/MLP/SESETree.java
@@ -0,0 +1,154 @@
+package Analysis.MLP;
+import IR.*;
+import IR.Flat.*;
+import java.util.*;
+import Analysis.CallGraph.*;
+
+public class SESETree {
+  State state;
+  TypeUtil typeutil;
+  CallGraph callgraph;
+  SESENode root;
+  Hashtable<MethodDescriptor, Set<SESENode>> toanalyze=new Hashtable<MethodDescriptor,Set<SESENode>>();
+  Hashtable<MethodDescriptor, Set<SESENode>> discovered=new Hashtable<MethodDescriptor,Set<SESENode>>();
+  Hashtable<FlatSESEEnterNode, SESENode> sesemap=new Hashtable<FlatSESEEnterNode, SESENode>();
+
+  public SESETree(State state, TypeUtil typeutil, CallGraph callgraph) {
+    this.state=state;
+    this.typeutil=typeutil;
+    this.callgraph=callgraph;
+    root=new SESENode(null, true);
+    doAnalysis();
+  }
+
+  public SESENode getRoot() {
+    return root;
+  }
+
+  public void doAnalysis() {
+    MethodDescriptor main=typeutil.getMain();
+    add(toanalyze, main, root);
+    add(discovered, main, root);
+    
+    while(!toanalyze.isEmpty()) {
+      MethodDescriptor md=toanalyze.keySet().iterator().next();
+      Set<SESENode> context=toanalyze.get(md);
+      toanalyze.remove(md);
+      FlatMethod fm=state.getMethodFlat(md);
+      analyzeMethod(fm, context);
+    }
+  }
+
+  public SESENode getSESE(FlatSESEEnterNode enter) {
+    if (!sesemap.containsKey(enter)) {
+      sesemap.put(enter, new SESENode(enter, false));
+    }
+    return sesemap.get(enter);
+  }
+
+  private void analyzeMethod(FlatMethod fm, Set<SESENode> context) {
+    Hashtable<FlatNode, Stack<SESENode>> stacks=new Hashtable<FlatNode, Stack<SESENode>> ();
+    stacks.put(fm, new Stack<SESENode>());
+    HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
+    HashSet<FlatNode> fndiscovered=new HashSet<FlatNode>();
+    tovisit.add(fm);
+    fndiscovered.add(fm);
+    while(!tovisit.isEmpty()) {
+      FlatNode fn=tovisit.iterator().next();
+      tovisit.remove(fn);
+      Stack<SESENode> instack=stacks.get(fm);
+      switch(fn.kind()) {
+      case FKind.FlatCall: {
+	FlatCall fc=(FlatCall)fn;
+	//handle method call
+	Set<SESENode> parents;
+	if (instack.isEmpty()) {
+	  parents=context;
+	} else {
+	  parents=new HashSet<SESENode>();
+	  parents.add(instack.peek());
+	}
+	for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
+	  SESENode parentsese=parentit.next();
+	  for(Iterator<MethodDescriptor> calleeit=(fc.getThis()==null?callgraph.getMethods(fc.getMethod()):callgraph.getMethods(fc.getMethod(), fc.getThis().getType())).iterator(); calleeit.hasNext();) {
+	    MethodDescriptor md=calleeit.next();
+	    if (add(discovered,md, parentsese)) {
+	      add(toanalyze, md, parentsese);
+	    }
+	  }
+	}
+	break;
+      }
+      case FKind.FlatSESEEnterNode: {
+	FlatSESEEnterNode enter=(FlatSESEEnterNode)fn;
+	Set<SESENode> parents;
+	if (instack.isEmpty()) {
+	  parents=context;
+	} else {
+	  parents=new HashSet<SESENode>();
+	  parents.add(instack.peek());
+	}
+	SESENode sese=getSESE(enter);
+	for(Iterator<SESENode> parentit=parents.iterator();parentit.hasNext();) {
+	  SESENode parentsese=parentit.next();
+	  parentsese.addChild(sese);
+	}
+	Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
+	copy.push(sese);
+	instack=copy;
+	break;
+      }
+      case FKind.FlatSESEExitNode: {
+	FlatSESEExitNode exit=(FlatSESEExitNode)fn;
+	Stack<SESENode> copy=(Stack<SESENode>)instack.clone();
+	copy.pop();
+	instack=copy;
+	break;
+      }
+      }
+      for(int i=0;i<fn.numNext();i++) {
+	FlatNode fnext=fn.getNext(i);
+	if (!fndiscovered.contains(fnext)) {
+	  fndiscovered.add(fnext);
+	  tovisit.add(fnext);
+	  stacks.put(fnext, instack);
+	}
+      }
+    }
+
+
+  }
+
+  public static boolean add(Hashtable<MethodDescriptor, Set<SESENode>> discovered, MethodDescriptor md, SESENode sese) {
+    if (!discovered.containsKey(md))
+      discovered.put(md, new HashSet<SESENode>());
+    if (discovered.get(md).contains(sese))
+      return false;
+    discovered.get(md).add(sese);
+    return true;
+  }
+
+
+  class SESENode {
+    boolean isRoot;
+    HashSet<SESENode> children;
+    FlatSESEEnterNode node;
+    SESENode(FlatSESEEnterNode node, boolean isRoot) {
+      children=new HashSet<SESENode>();
+      this.isRoot=isRoot;
+      this.node=node;
+    }
+
+    public boolean isLeaf() {
+      return children.isEmpty();
+    }
+
+    public void addChild(SESENode child) {
+      children.add(child);
+    }
+    
+    public Set<SESENode> getChildren() {
+      return children;
+    }
+  }
+}
\ No newline at end of file
-- 
2.34.1