changes towards method context insensitive analysis.
authoryeom <yeom>
Mon, 26 Oct 2009 18:41:25 +0000 (18:41 +0000)
committeryeom <yeom>
Mon, 26 Oct 2009 18:41:25 +0000 (18:41 +0000)
add stall edge mapping.

Robust/src/Analysis/MLP/MLPAnalysis.java
Robust/src/Analysis/MLP/ParentChildConflictsMap.java
Robust/src/Analysis/MLP/StallSite.java

index 809482e..64a12d5 100644 (file)
@@ -54,6 +54,7 @@ public class MLPAnalysis {
   
   private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults;
   private ParentChildConflictsMap currentConflictsMap;
+  private Hashtable < ReferenceEdge, StallSite > stallEdgeMapping;
 
   public static int maxSESEage = -1;
 
@@ -110,7 +111,7 @@ public class MLPAnalysis {
     mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet<AllocationSite>>();
     
     conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >();
-    
+    stallEdgeMapping = new Hashtable < ReferenceEdge, StallSite >();
 
     FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() );
 
@@ -204,13 +205,7 @@ public class MLPAnalysis {
     }
     
     // Parent/child memory conflicts analysis
-    methItr = ownAnalysis.descriptorsToAnalyze.iterator();
-    javaCallGraph = new JavaCallGraph(state,tu);
-    while( methItr.hasNext() ) {
-        Descriptor d  = methItr.next();      
-        FlatMethod fm = state.getMethodFlat( d );
-        seseConflictsForward(fm,javaCallGraph);
-      }
+    seseConflictsForward(javaCallGraph);
     
     
     // disjoint analysis with a set of flagged allocation sites of live-in variable
@@ -1053,6 +1048,9 @@ public class MLPAnalysis {
                                if (obj instanceof MethodDescriptor) {
                                        MethodDescriptor callerMD = (MethodDescriptor) obj;
 
+                                       if(callerMD.equals(mc.getDescriptor())){
+                                               continue;
+                                       }
                                        analyzeRelatedAllocationSite(callerMD, mc, paramIndexSet,visitedHRN);
 
                                }
@@ -1700,6 +1698,27 @@ public class MLPAnalysis {
 
        }
        
+       private HashSet<ReferenceEdge> getRefEdgeSetReferenceToSameHRN(
+                       OwnershipGraph og, TempDescriptor td) {
+
+               HashSet<ReferenceEdge> returnSet = new HashSet<ReferenceEdge>();
+
+               HashSet<HeapRegionNode> heapIDs = getReferenceHeapIDSet(og, td);
+               for (Iterator<HeapRegionNode> iterator = heapIDs.iterator(); iterator
+                               .hasNext();) {
+                       HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next();
+                       Iterator<ReferenceEdge> referenceeIter = heapRegionNode
+                                       .iteratorToReferencees();
+                       while (referenceeIter.hasNext()) {
+                               ReferenceEdge edge = (ReferenceEdge) referenceeIter.next();
+                               if (edge.getSrc() instanceof HeapRegionNode) {
+                                       returnSet.add(edge);
+                               }
+                       }
+               }
+               return returnSet;
+       }
+       
        private HashSet<TempDescriptor> getTempDescSetReferenceToSameHRN(
                        OwnershipGraph og, TempDescriptor td) {
 
@@ -1722,65 +1741,102 @@ public class MLPAnalysis {
                return returnSet;
        }
        
-       private void seseConflictsForward(FlatMethod fm, JavaCallGraph callGraph) {
+       private void DFSVisit( MethodDescriptor md,
+                        LinkedList<MethodDescriptor> sorted,
+                       HashSet<MethodDescriptor> discovered, JavaCallGraph javaCallGraph) {
 
-               MethodDescriptor md = fm.getMethod();
-               HashSet<MethodContext> mcSet = ownAnalysis
-                               .getAllMethodContextSetByDescriptor(md);
-               Iterator<MethodContext> mcIter = mcSet.iterator();
+               discovered.add(md);
 
-               while (mcIter.hasNext()) {
-                       MethodContext mc = mcIter.next();
+               Iterator itr = javaCallGraph.getCallerSet(md).iterator();
+               while (itr.hasNext()) {
+                       MethodDescriptor mdCaller = (MethodDescriptor) itr.next();
 
-                       Set<FlatNode> visited = new HashSet<FlatNode>();
+                       if (!discovered.contains(mdCaller)) {
+                               DFSVisit(mdCaller, sorted, discovered, javaCallGraph);
+                       }
+               }
 
-                       Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
-                       flatNodesToVisit.add(fm);
+               sorted.addFirst(md);
+       }
+       
+       
+       private LinkedList<MethodDescriptor> topologicalSort(Set set,
+                       JavaCallGraph javaCallGraph) {
+               HashSet<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
+               LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
 
-                       while (!flatNodesToVisit.isEmpty()) {
-                               FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
-                               flatNodesToVisit.remove(fn);
+               Iterator<MethodDescriptor> itr = set.iterator();
+               while (itr.hasNext()) {
+                       MethodDescriptor md = itr.next();
 
-                               Stack<FlatSESEEnterNode> seseStack = seseStacks.get(fn);
-                               assert seseStack != null;
+                       if (!discovered.contains(md)) {
+                               DFSVisit(md, sorted, discovered, javaCallGraph);
+                       }
+               }
 
-                               if (!seseStack.empty()) {
-                                       conflicts_nodeAction(mc, fn, seseStack.peek(), callGraph);
-                               }
+               return sorted;
+       }
+        
+       
+       private void seseConflictsForward(JavaCallGraph javaCallGraph) {
 
-                               flatNodesToVisit.remove(fn);
-                               visited.add(fn);
+               Set methodCallSet = javaCallGraph.getAllMethods(typeUtil.getMain());
 
-                               for (int i = 0; i < fn.numNext(); i++) {
-                                       FlatNode nn = fn.getNext(i);
-                                       if (!visited.contains(nn)) {
-                                               flatNodesToVisit.add(nn);
+               // topologically sort java call chain so that leaf calls are ordered
+               // first
+               LinkedList<MethodDescriptor> sortedMethodCalls = topologicalSort(
+                               methodCallSet, javaCallGraph);
+
+               for (Iterator iterator = sortedMethodCalls.iterator(); iterator
+                               .hasNext();) {
+                       MethodDescriptor md = (MethodDescriptor) iterator.next();
+
+                       FlatMethod fm = state.getMethodFlat(md);
+
+                       HashSet<MethodContext> mcSet = ownAnalysis
+                                       .getAllMethodContextSetByDescriptor(md);
+                       Iterator<MethodContext> mcIter = mcSet.iterator();
+
+                       while (mcIter.hasNext()) {
+
+                               MethodContext mc = mcIter.next();
+
+                               Set<FlatNode> visited = new HashSet<FlatNode>();
+
+                               Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+                               flatNodesToVisit.add(fm);
+
+                               while (!flatNodesToVisit.isEmpty()) {
+                                       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+                                       flatNodesToVisit.remove(fn);
+
+                                       conflicts_nodeAction(mc, fn, callGraph);
+
+                                       flatNodesToVisit.remove(fn);
+                                       visited.add(fn);
+
+                                       for (int i = 0; i < fn.numNext(); i++) {
+                                               FlatNode nn = fn.getNext(i);
+                                               if (!visited.contains(nn)) {
+                                                       flatNodesToVisit.add(nn);
+                                               }
                                        }
                                }
-
                        }
-
                }
 
        }
        
        private void conflicts_nodeAction(MethodContext mc, FlatNode fn,
-                       FlatSESEEnterNode currentSESE, CallGraph callGraph) {
+                       CallGraph callGraph) {
 
                OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc);
 
                switch (fn.kind()) {
 
-               case FKind.FlatSESEEnterNode: {
-
-               }
-                       break;
-
                case FKind.FlatSESEExitNode: {
-
                        // all object variables are inaccessible
                        currentConflictsMap = new ParentChildConflictsMap();
-
                }
                        break;
 
@@ -1798,6 +1854,7 @@ public class MLPAnalysis {
                case FKind.FlatFieldNode: {
 
                        if (currentConflictsMap != null) {
+
                                FlatFieldNode ffn = (FlatFieldNode) fn;
                                TempDescriptor dst = ffn.getDst();
                                TempDescriptor src = ffn.getSrc();
@@ -1874,46 +1931,95 @@ public class MLPAnalysis {
                                }
 
                                // TODO need to create edge mapping for newly created edge
+                               HashSet<ReferenceEdge> edges = getRefEdgeSetReferenceToSameHRN(
+                                               og, dst);
 
+                               StallSite ss = currentConflictsMap.getStallMap().get(dst);
+                               if (ss != null) {
+                                       for (Iterator iterator = edges.iterator(); iterator
+                                                       .hasNext();) {
+                                               ReferenceEdge referenceEdge = (ReferenceEdge) iterator
+                                                               .next();
+                                               stallEdgeMapping.put(referenceEdge, ss);
+                                               // System.out.println("STALL EDGE MAPPING WITH "+referenceEdge+" -> "+ss);
+                                       }
+                               }
                        }
-
                }
                        break;
 
                case FKind.FlatOpNode: {
+                       if (currentConflictsMap != null) {
 
-                       // destination variable gets the status of source.
-                       FlatOpNode fon = (FlatOpNode) fn;
+                               // destination variable gets the status of source.
+                               FlatOpNode fon = (FlatOpNode) fn;
 
-                       if (fon.getOp().getOp() == Operation.ASSIGN
-                                       && currentConflictsMap != null) {
+                               if (fon.getOp().getOp() == Operation.ASSIGN
+                                               && currentConflictsMap != null) {
 
-                               TempDescriptor dst = fon.getDest();
-                               TempDescriptor src = fon.getLeft();
+                                       TempDescriptor dst = fon.getDest();
+                                       TempDescriptor src = fon.getLeft();
 
-                               Integer sourceStatus = currentConflictsMap.getAccessibleMap()
-                                               .get(src);
-                               if(sourceStatus==null){
-                                       sourceStatus=ParentChildConflictsMap.INACCESSIBLE;
-                               }
+                                       Integer sourceStatus = currentConflictsMap
+                                                       .getAccessibleMap().get(src);
+                                       if (sourceStatus == null) {
+                                               sourceStatus = ParentChildConflictsMap.INACCESSIBLE;
+                                       }
 
-                               HashSet<TempDescriptor> dstTempSet = getTempDescSetReferenceToSameHRN(
-                                               og, dst);
+                                       HashSet<TempDescriptor> dstTempSet = getTempDescSetReferenceToSameHRN(
+                                                       og, dst);
 
-                               for (Iterator<TempDescriptor> iterator = dstTempSet.iterator(); iterator
-                                               .hasNext();) {
-                                       TempDescriptor possibleDst = iterator.next();
+                                       for (Iterator<TempDescriptor> iterator = dstTempSet
+                                                       .iterator(); iterator.hasNext();) {
+                                               TempDescriptor possibleDst = iterator.next();
+
+                                               if (sourceStatus
+                                                               .equals(ParentChildConflictsMap.ACCESSIBLE)) {
+                                                       currentConflictsMap.addAccessibleVar(possibleDst);
+                                               } else {
+                                                       currentConflictsMap.addInaccessibleVar(possibleDst);
+                                               }
 
-                                       if (sourceStatus.equals(ParentChildConflictsMap.ACCESSIBLE)) {
-                                               currentConflictsMap.addAccessibleVar(possibleDst);
-                                       } else {
-                                               currentConflictsMap.addInaccessibleVar(possibleDst);
                                        }
+                               }
+
+                       }
+               }
+                       break;
 
+               case FKind.FlatNop: {
+
+                       FlatNop fnop = (FlatNop) fn;
+                       if (fnop.numPrev() > 1) {
+                               // merge point
+                               for (int i = 0; i < fnop.numPrev(); i++) {
+                                       FlatNode prev = fnop.getPrev(i);
+                                       ParentChildConflictsMap prevConflictsMap = conflictsResults
+                                                       .get(prev);
+                                       if (prevConflictsMap != null) {
+                                               if (currentConflictsMap == null) {
+                                                       currentConflictsMap = new ParentChildConflictsMap();
+                                               }
+                                               currentConflictsMap.merge(prevConflictsMap);
+                                       }
                                }
                        }
+
+                       // TODO: need to merge edge mappings
+
+               }
+                       break;
+
+               case FKind.FlatCall: {
+
+                       FlatCall fc = (FlatCall) fn;
+
+                       // look at all possible context, and then take all of them into one
+                       // context
+
                }
                        break;
+
                }
 
                // for every program point, we keep accessible map and stall map.
index 58d31b1..0d549a5 100644 (file)
@@ -1,7 +1,12 @@
 package Analysis.MLP;
 
+import java.util.HashSet;
 import java.util.Hashtable;
+import java.util.Iterator;
+import java.util.Set;
 
+import Analysis.OwnershipAnalysis.ReachabilitySet;
+import Analysis.OwnershipAnalysis.TokenTupleSet;
 import IR.Flat.TempDescriptor;
 
 public class ParentChildConflictsMap {
@@ -26,34 +31,106 @@ public class ParentChildConflictsMap {
        public Hashtable<TempDescriptor, StallSite> getStallMap() {
                return stallMap;
        }
-       
-       public void addAccessibleVar(TempDescriptor td){
+
+       public void addAccessibleVar(TempDescriptor td) {
                accessibleMap.put(td, ACCESSIBLE);
        }
-       
-       public void addInaccessibleVar(TempDescriptor td){
+
+       public void addInaccessibleVar(TempDescriptor td) {
                accessibleMap.put(td, INACCESSIBLE);
        }
-       
-       public void addStallSite(TempDescriptor td){
-               StallSite stallSite=new StallSite();
+
+       public void addStallSite(TempDescriptor td) {
+               StallSite stallSite = new StallSite();
                stallMap.put(td, stallSite);
        }
 
-       public boolean isAccessible(TempDescriptor td){
-               if(accessibleMap.contains(td) && accessibleMap.get(td).equals(ACCESSIBLE)){
+       public boolean isAccessible(TempDescriptor td) {
+               if (accessibleMap.contains(td)
+                               && accessibleMap.get(td).equals(ACCESSIBLE)) {
                        return true;
                }
                return false;
        }
-       
-       public void contributeEffect(TempDescriptor td, String type, String field, int effect){
-               
-               StallSite stallSite=stallMap.get(td);
-               if(stallSite!=null){
+
+       public void contributeEffect(TempDescriptor td, String type, String field,
+                       int effect) {
+
+               StallSite stallSite = stallMap.get(td);
+               if (stallSite != null) {
                        stallSite.addEffect(type, field, effect);
                }
-               
+
        }
-       
+
+       public void merge(ParentChildConflictsMap newConflictsMap) {
+
+               Hashtable<TempDescriptor, Integer> newAccessibleMap = newConflictsMap
+                               .getAccessibleMap();
+               Hashtable<TempDescriptor, StallSite> newStallMap = newConflictsMap
+                               .getStallMap();
+
+               Set<TempDescriptor> keySet = newAccessibleMap.keySet();
+               for (Iterator<TempDescriptor> iterator = keySet.iterator(); iterator
+                               .hasNext();) {
+                       TempDescriptor key = iterator.next();
+
+                       Integer newStatus = newAccessibleMap.get(key);
+
+                       // inaccessible is prior to accessible
+                       Integer currentStatus = getAccessibleMap().get(key);
+                       if (currentStatus != null && currentStatus == ACCESSIBLE
+                                       && newStatus == INACCESSIBLE) {
+                               getAccessibleMap().put(key, INACCESSIBLE);
+                       }
+               }
+
+               keySet = newStallMap.keySet();
+               for (Iterator<TempDescriptor> iterator = keySet.iterator(); iterator
+                               .hasNext();) {
+                       TempDescriptor key = iterator.next();
+
+                       StallSite newStallSite = newStallMap.get(key);
+                       StallSite currentStallSite = getStallMap().get(key);
+
+                       // handle effects
+                       HashSet<Effect> currentEffectSet = currentStallSite.getEffectSet();
+                       HashSet<Effect> newEffectSet = newStallSite.getEffectSet();
+                       for (Iterator iterator2 = newEffectSet.iterator(); iterator2
+                                       .hasNext();) {
+                               Effect effect = (Effect) iterator2.next();
+                               if (!currentEffectSet.contains(effect)) {
+                                       currentEffectSet.add(effect);
+                               }
+                       }
+
+                       // handle heap region
+                       HashSet<Integer> currentHRNSet = currentStallSite.getHRNIDSet();
+                       HashSet<Integer> newHRNSet = newStallSite.getHRNIDSet();
+                       for (Iterator iterator2 = newHRNSet.iterator(); iterator2.hasNext();) {
+                               Integer hrnID = (Integer) iterator2.next();
+                               if (!currentHRNSet.contains(hrnID)) {
+                                       currentHRNSet.add(hrnID);
+                               }
+                       }
+
+                       // handle reachabilitySet
+                       ReachabilitySet currentRSet = currentStallSite.getReachabilitySet();
+                       ReachabilitySet newRSet = newStallSite.getReachabilitySet();
+                       Iterator<TokenTupleSet> ttsIter = newRSet.iterator();
+                       while (ttsIter.hasNext()) {
+                               TokenTupleSet tokenTupleSet = (TokenTupleSet) ttsIter.next();
+                               currentRSet.add(tokenTupleSet);
+                       }
+
+                       getStallMap()
+                                       .put(
+                                                       key,
+                                                       new StallSite(currentEffectSet, currentHRNSet,
+                                                                       currentRSet));
+
+               }
+
+       }
+
 }
index 23480a3..edb794d 100644 (file)
@@ -5,35 +5,110 @@ import java.util.HashSet;
 import Analysis.OwnershipAnalysis.ReachabilitySet;
 
 public class StallSite {
-       
-       public static final Integer READ_EFFECT=new Integer(1);
-       public static final Integer WRITE_EFFECT=new Integer(2);
-       
+
+       public static final Integer READ_EFFECT = new Integer(1);
+       public static final Integer WRITE_EFFECT = new Integer(2);
+
        private HashSet<Effect> effectSet;
-       private int hrnID;
+       private HashSet<Integer> hrnIDSet;
        private ReachabilitySet rechabilitySet;
-       
-       public StallSite(){
-               effectSet=new HashSet<Effect>();
+
+       public StallSite() {
+               effectSet = new HashSet<Effect>();
+               hrnIDSet = new HashSet<Integer>();
+               rechabilitySet = new ReachabilitySet();
+       }
+
+       public StallSite(HashSet<Effect> effectSet, HashSet<Integer> hrnIDSet,
+                       ReachabilitySet rechabilitySet) {
+               this.effectSet = effectSet;
+               this.hrnIDSet = hrnIDSet;
+               this.rechabilitySet = rechabilitySet;
        }
-       
-       public void addEffect(String type, String field, Integer effect){
-               Effect e=new Effect(type,field,effect);
+
+       public void addEffect(String type, String field, Integer effect) {
+               Effect e = new Effect(type, field, effect);
                effectSet.add(e);
        }
-       
+
+       public HashSet<Effect> getEffectSet() {
+               return effectSet;
+       }
+
+       public HashSet<Integer> getHRNIDSet() {
+               return hrnIDSet;
+       }
+
+       public ReachabilitySet getReachabilitySet() {
+               return rechabilitySet;
+       }
+
+       public boolean equals(Object o) {
+
+               if (o == null) {
+                       return false;
+               }
+
+               if (!(o instanceof StallSite)) {
+                       return false;
+               }
+
+               StallSite in = (StallSite) o;
+
+               if (effectSet.equals(in.getEffectSet())
+                               && hrnIDSet.equals(in.getHRNIDSet())
+                               && rechabilitySet.equals(in.getReachabilitySet())) {
+                       return true;
+               } else {
+                       return false;
+               }
+
+       }
 }
 
-class Effect{
-       
+class Effect {
+
        private String field;
        private String type;
        private Integer effect;
-       
-       public Effect(String type, String field, Integer effect){
-               this.type=type;
-               this.field=field;
-               this.effect=effect;
+
+       public Effect(String type, String field, Integer effect) {
+               this.type = type;
+               this.field = field;
+               this.effect = effect;
+       }
+
+       public String getField() {
+               return field;
+       }
+
+       public String getType() {
+               return type;
+       }
+
+       public Integer getEffect() {
+               return effect;
        }
-       
+
+       public boolean equals(Object o) {
+
+               if (o == null) {
+                       return false;
+               }
+
+               if (!(o instanceof StallSite)) {
+                       return false;
+               }
+
+               Effect in = (Effect) o;
+
+               if (type.equals(in.getType()) && field.equals(in.getField())
+                               && effect.equals(in.getEffect())) {
+                       return true;
+               } else {
+                       return false;
+               }
+
+       }
+
 }
\ No newline at end of file