From c921ed028030c5185022557ff8ac34469301e7b8 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky>
Date: Sat, 19 Mar 2011 00:55:37 +0000
Subject: [PATCH] changes...extra accessible analysis

---
 Robust/src/Analysis/Liveness.java             |  10 +
 Robust/src/Analysis/OoOJava/Accessible.java   | 192 ++++++++++++++++++
 .../OoOJava/RBlockRelationAnalysis.java       |   4 +
 Robust/src/Util/Pair.java                     |  14 +-
 4 files changed, 216 insertions(+), 4 deletions(-)
 create mode 100644 Robust/src/Analysis/OoOJava/Accessible.java

diff --git a/Robust/src/Analysis/Liveness.java b/Robust/src/Analysis/Liveness.java
index 9f93732d..b4b3a8dc 100644
--- a/Robust/src/Analysis/Liveness.java
+++ b/Robust/src/Analysis/Liveness.java
@@ -72,8 +72,18 @@ public class Liveness {
   // Also allow an instantiation of this object that memoizes results
   protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveMap;
 
+  protected Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > > fm2liveOutMap;
+
   public Liveness() {
     fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
+    fm2liveOutMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set<TempDescriptor> > >();
+  }
+
+  public Set<TempDescriptor> getLiveOutTemps( FlatMethod fm, FlatNode fn ) {
+    if( !fm2liveOutMap.containsKey( fm ) ) {
+      fm2liveOutMap.put( fm, Liveness.computeLiveOut( fm ) );
+    }
+    return fm2liveOutMap.get( fm ).get( fn );
   }
 
   public Set<TempDescriptor> getLiveInTemps( FlatMethod fm, FlatNode fn ) {
diff --git a/Robust/src/Analysis/OoOJava/Accessible.java b/Robust/src/Analysis/OoOJava/Accessible.java
new file mode 100644
index 00000000..f0f1855a
--- /dev/null
+++ b/Robust/src/Analysis/OoOJava/Accessible.java
@@ -0,0 +1,192 @@
+package Analysis.OoOJava;
+import Util.Pair;
+import java.util.*;
+import IR.Flat.*;
+import IR.*;
+import Analysis.Liveness;
+import Analysis.CallGraph.CallGraph;
+
+public class Accessible {
+  //Try to compute InAccessible
+  HashMap<FlatNode, Set<TempDescriptor>> inAccessible;
+  State state;
+  CallGraph callGraph;
+  RBlockRelationAnalysis taskAnalysis;
+  Liveness liveness;
+  Stack<Pair<FlatNode,MethodDescriptor>> toprocess=new Stack<Pair<FlatNode, MethodDescriptor>>();
+  HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>> methodmap=new HashMap<MethodDescriptor, Set<Pair<FlatCall, MethodDescriptor>>>();
+
+  public Accessible(State state, CallGraph callGraph, RBlockRelationAnalysis taskAnalysis, Liveness liveness) {
+    inAccessible=new HashMap<FlatNode, Set<TempDescriptor>>();
+    this.state=state;
+    this.callGraph=callGraph;
+    this.taskAnalysis=taskAnalysis;
+    this.liveness=liveness;
+  }
+
+  public void computeFixPoint() {
+    nextNode:
+    while(!toprocess.isEmpty()) {
+      Pair<FlatNode, MethodDescriptor> fnpair=toprocess.pop();
+      FlatNode fn=fnpair.getFirst();
+      MethodDescriptor pairmd=fnpair.getSecond();
+      HashSet<TempDescriptor> inAccessibleSet=new HashSet<TempDescriptor>();
+      for(int i=0;i<fn.numPrev();i++) {
+	Set<TempDescriptor> inAccess=inAccessible.get(fn.getPrev(i));
+	if (inAccess!=null)
+	  inAccessibleSet.addAll(inAccess);
+      }
+
+      switch(fn.kind()) {
+      case FKind.FlatNew:
+      case FKind.FlatFieldNode:
+      case FKind.FlatElementNode:
+      case FKind.FlatSetFieldNode:
+      case FKind.FlatSetElementNode:
+	{
+	  TempDescriptor[] rdtmps=fn.readsTemps();
+	  for(int i=0;i<rdtmps.length;i++) {
+	    inAccessibleSet.remove(rdtmps[i]);
+	  }
+	  TempDescriptor[] wrtmps=fn.writesTemps();
+	  for(int i=0;i<wrtmps.length;i++) {
+	    inAccessibleSet.remove(wrtmps[i]);
+	  }
+	}
+	break;
+      case FKind.FlatCastNode:
+      case FKind.FlatOpNode:
+	{
+	  TempDescriptor[] rdtmps=fn.readsTemps();
+	  TempDescriptor[] wrtmps=fn.writesTemps();
+	  if (inAccessibleSet.contains(rdtmps[0]))
+	    inAccessibleSet.add(wrtmps[0]);
+	}
+	break;
+      case FKind.FlatReturnNode:
+	{
+	  FlatReturnNode fr=(FlatReturnNode)fn;
+	  if (fr.getReturnTemp()!=null&&inAccessibleSet.contains(fr.getReturnTemp())) {
+	    //Need to inform callers
+	    Set<Pair<FlatCall, MethodDescriptor>> callset=methodmap.get(pairmd);
+	    for(Pair<FlatCall, MethodDescriptor> fcallpair:callset) {
+	      FlatCall fcall=fcallpair.getFirst();
+	      Set<TempDescriptor> inAccess=inAccessible.get(fcall);
+	      if (fcall.getReturnTemp()!=null&&!inAccess.contains(fcall.getReturnTemp())) {
+		inAccess.add(fcall.getReturnTemp());
+		toprocess.add(new Pair<FlatNode, MethodDescriptor>(fcall, fcallpair.getSecond()));
+	      }
+	    }
+	  }
+	}
+	continue nextNode;
+      case FKind.FlatSESEEnterNode:
+      case FKind.FlatSESEExitNode:
+	continue nextNode;
+      case FKind.FlatCall: {
+	FlatCall fcall=(FlatCall)fn;
+	MethodDescriptor calledmethod=fcall.getMethod();
+	Set methodsthatcouldbecalled=fcall.getThis()==null ? callGraph.getMethods(calledmethod) :
+	  callGraph.getMethods(calledmethod, fcall.getThis().getType());	
+	for(Object o:methodsthatcouldbecalled) {
+	  MethodDescriptor md=(MethodDescriptor)o;
+	  FlatMethod fm=state.getMethodFlat(md);
+	  HashSet<TempDescriptor> tmpinaccess=new HashSet<TempDescriptor>();
+	  for(int i=0;i<fm.numParameters();i++) {
+	    TempDescriptor fmtmp=fm.getParameter(i);
+	    TempDescriptor tmpcall=fcall.getArgMatchingParamIndex(fm, i);
+	    if (inAccessibleSet.contains(tmpcall)) {
+	      tmpinaccess.add(fmtmp);
+	    }
+	  }
+	  if (!tmpinaccess.isEmpty()&&(!inAccessible.containsKey(fm)||!inAccessible.get(fm).containsAll(tmpinaccess))) {
+	    for(int i=0;i<fm.numNext();i++)
+	      toprocess.add(new Pair<FlatNode, MethodDescriptor>(fm.getNext(i),md));
+	    inAccessible.get(fm).addAll(tmpinaccess);
+	  }
+	}
+	//be sure not to wipe out return value or other inaccessible temps
+	inAccessibleSet.addAll(inAccessible.get(fcall));
+      }
+	break;
+      default:
+      }
+      if (!inAccessibleSet.isEmpty()&&(!inAccessible.containsKey(fn)||!inAccessible.get(fn).equals(inAccessibleSet))) {
+	inAccessible.put(fn, inAccessibleSet);
+	for(int i=0;i<fn.numNext();i++)
+	  toprocess.add(new Pair<FlatNode, MethodDescriptor>(fn.getNext(i),pairmd));
+      }
+    }
+  }
+
+  public void doAnalysis() {
+    for(FlatSESEEnterNode sese: taskAnalysis.getAllSESEs()) {
+      FlatSESEExitNode seseexit=sese.getFlatExit();
+      HashSet<TempDescriptor> liveout=new HashSet<TempDescriptor>(liveness.getLiveOutTemps(sese.getfmEnclosing(), seseexit));
+      for(Iterator<TempDescriptor> tmpit=liveout.iterator();tmpit.hasNext();) {
+	TempDescriptor tmp=tmpit.next();
+	if (!tmp.getType().isPtr())
+	  tmpit.remove();
+      }
+      inAccessible.put(seseexit, liveout);
+      for(int i=0;i<seseexit.numNext();i++)
+	toprocess.add(new Pair<FlatNode, MethodDescriptor>(seseexit.getNext(i),sese.getmdEnclosing()));
+    }
+    
+    Set<MethodDescriptor> methodSet=taskAnalysis.getMethodsWithSESEs();
+    Set<MethodDescriptor> canCallSESE=new HashSet<MethodDescriptor>(methodSet);
+    Stack<MethodDescriptor> methodStack=new Stack<MethodDescriptor>();
+    methodStack.addAll(methodSet);
+    //Set up exits of SESEs
+    while(!methodStack.isEmpty()) {
+      MethodDescriptor md=methodStack.pop();
+      Set callers=callGraph.getCallerSet(md);
+      for(Object o:callers) {
+	MethodDescriptor callermd=(MethodDescriptor)o;
+	if (!canCallSESE.contains(callermd)) {
+	  //new method descriptor
+	  canCallSESE.add(callermd);
+	  methodStack.add(callermd);
+	}
+      }
+    }
+
+    //Set up exits of methods
+    for(MethodDescriptor md:canCallSESE) {
+      FlatMethod fm=state.getMethodFlat(md);
+      for(FlatNode fn:fm.getNodeSet()) {
+	if (fn.kind()==FKind.FlatCall) {
+	  FlatCall fcall=(FlatCall)fn;
+	  MethodDescriptor calledmethod=fcall.getMethod();
+	  Set methodsthatcouldbecalled=fcall.getThis()==null ? callGraph.getMethods(calledmethod) :
+	    callGraph.getMethods(calledmethod, fcall.getThis().getType());
+	  boolean specialcall=false;
+	  for(Object o:methodsthatcouldbecalled) {
+	    MethodDescriptor callermd=(MethodDescriptor)o;
+	    if (canCallSESE.contains(callermd)) {
+	      //TODO: NEED TO BUILD MAP FROM MD -> CALLS
+	      specialcall=true;
+	      if (!methodmap.containsKey(callermd))
+		methodmap.put(callermd, new HashSet<Pair<FlatCall, MethodDescriptor>>());
+	      methodmap.get(callermd).add(new Pair<FlatCall, MethodDescriptor>(fcall,md));
+	    }
+	  }
+	  if (specialcall) {
+	    Set<TempDescriptor> liveout=new HashSet<TempDescriptor>(liveness.getLiveOutTemps(fm, fcall));
+	    TempDescriptor returntmp=fcall.getReturnTemp();
+	    liveout.remove(returntmp);
+	    for(Iterator<TempDescriptor> tmpit=liveout.iterator();tmpit.hasNext();) {
+	      TempDescriptor tmp=tmpit.next();
+	      if (!tmp.getType().isPtr())
+		tmpit.remove();
+	    }
+	    inAccessible.put(fcall, liveout);
+	    for(int i=0;i<fcall.numNext();i++)
+	      toprocess.add(new Pair<FlatNode, MethodDescriptor>(fcall.getNext(i),md));
+	  }
+	}
+      }
+    }
+    computeFixPoint();
+  }
+}
\ No newline at end of file
diff --git a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java
index bf8ea0fa..951e4cd8 100644
--- a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java
+++ b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java
@@ -134,6 +134,10 @@ public class RBlockRelationAnalysis {
     }
     return out;
   }
+
+  public Set<MethodDescriptor> getMethodsWithSESEs() {
+    return methodsContainingSESEs;
+  }
   
   /* Returns all SESE's that this fn can be a member of
    * transitively. */
diff --git a/Robust/src/Util/Pair.java b/Robust/src/Util/Pair.java
index dea902c9..061804f4 100644
--- a/Robust/src/Util/Pair.java
+++ b/Robust/src/Util/Pair.java
@@ -1,12 +1,18 @@
 package Util;
 
-public class Pair {
-  private Object a;
-  private Object b;
-  public Pair(Object a, Object b) {
+public class Pair<A,B> {
+  private A a;
+  private B b;
+  public Pair(A a, B b) {
     this.a=a;
     this.b=b;
   }
+  public A getFirst() {
+    return a;
+  }
+  public B getSecond() {
+    return b;
+  }
   public int hashCode() {
     return a.hashCode()*31+b.hashCode();
   }
-- 
2.34.1