From: yeom Date: Fri, 23 Oct 2009 21:34:50 +0000 (+0000) Subject: initial commit for parent/child SESE memory conflicts analysis X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=038972e781f8230be1bce357622ad64c558ff59e initial commit for parent/child SESE memory conflicts analysis --- diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index a26e2c6a..809482e4 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -51,6 +51,9 @@ public class MLPAnalysis { private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn; private Hashtable< MethodContext, HashSet> mapMethodContextToLiveInAllocationSiteSet; + + private Hashtable < FlatNode, ParentChildConflictsMap > conflictsResults; + private ParentChildConflictsMap currentConflictsMap; public static int maxSESEage = -1; @@ -106,6 +109,8 @@ public class MLPAnalysis { mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet>(); + conflictsResults = new Hashtable < FlatNode, ParentChildConflictsMap >(); + FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() ); @@ -198,6 +203,16 @@ public class MLPAnalysis { methodEffects(fm,javaCallGraph); } + // 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); + } + + // disjoint analysis with a set of flagged allocation sites of live-in variable try { OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph, new Liveness(), @@ -1641,11 +1656,13 @@ public class MLPAnalysis { HashSet returnSet=new HashSet(); LabelNode ln=og.td2ln.get(td); - Iterator edgeIter=ln.iteratorToReferencees(); - while(edgeIter.hasNext()){ - ReferenceEdge edge=edgeIter.next(); - HeapRegionNode hrn=edge.getDst(); - returnSet.add(hrn); + if(ln!=null){ + Iterator edgeIter=ln.iteratorToReferencees(); + while(edgeIter.hasNext()){ + ReferenceEdge edge=edgeIter.next(); + HeapRegionNode hrn=edge.getDst(); + returnSet.add(hrn); + } } return returnSet; } @@ -1682,6 +1699,230 @@ public class MLPAnalysis { return returnSet; } + + private HashSet getTempDescSetReferenceToSameHRN( + OwnershipGraph og, TempDescriptor td) { + + HashSet returnSet = new HashSet(); + + HashSet heapIDs = getReferenceHeapIDSet(og, td); + for (Iterator iterator = heapIDs.iterator(); iterator + .hasNext();) { + HeapRegionNode heapRegionNode = (HeapRegionNode) iterator.next(); + Iterator referencerIter = heapRegionNode + .iteratorToReferencers(); + while (referencerIter.hasNext()) { + ReferenceEdge edge = (ReferenceEdge) referencerIter.next(); + if (edge.getSrc() instanceof LabelNode) { + LabelNode ln = (LabelNode) edge.getSrc(); + returnSet.add(ln.getTempDescriptor()); + } + } + } + return returnSet; + } + + private void seseConflictsForward(FlatMethod fm, JavaCallGraph callGraph) { + + MethodDescriptor md = fm.getMethod(); + HashSet mcSet = ownAnalysis + .getAllMethodContextSetByDescriptor(md); + Iterator mcIter = mcSet.iterator(); + + while (mcIter.hasNext()) { + MethodContext mc = mcIter.next(); + + Set visited = new HashSet(); + + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add(fm); + + while (!flatNodesToVisit.isEmpty()) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove(fn); + + Stack seseStack = seseStacks.get(fn); + assert seseStack != null; + + if (!seseStack.empty()) { + conflicts_nodeAction(mc, fn, seseStack.peek(), 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) { + + OwnershipGraph og = ownAnalysis.getOwnvershipGraphByMethodContext(mc); + + switch (fn.kind()) { + + case FKind.FlatSESEEnterNode: { + + } + break; + + case FKind.FlatSESEExitNode: { + + // all object variables are inaccessible + currentConflictsMap = new ParentChildConflictsMap(); + + } + break; + + case FKind.FlatNew: { + + if (currentConflictsMap != null) { + FlatNew fnew = (FlatNew) fn; + TempDescriptor dst = fnew.getDst(); + currentConflictsMap.addAccessibleVar(dst); + } + + } + break; + + case FKind.FlatFieldNode: { + + if (currentConflictsMap != null) { + FlatFieldNode ffn = (FlatFieldNode) fn; + TempDescriptor dst = ffn.getDst(); + TempDescriptor src = ffn.getSrc(); + FieldDescriptor field = ffn.getField(); + + HashSet srcTempSet = getTempDescSetReferenceToSameHRN( + og, src); + for (Iterator iterator = srcTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor possibleSrc = (TempDescriptor) iterator + .next(); + if (!currentConflictsMap.isAccessible(possibleSrc)) { + currentConflictsMap.addStallSite(possibleSrc); + } + + currentConflictsMap.addAccessibleVar(possibleSrc); + + // contribute read effect on source's stall site + currentConflictsMap.contributeEffect(src, field.getType() + .getSafeSymbol(), field.toString(), + StallSite.READ_EFFECT); + } + + HashSet dstTempSet = getTempDescSetReferenceToSameHRN( + og, dst); + for (Iterator iterator = dstTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor possibleDst = (TempDescriptor) iterator + .next(); + currentConflictsMap.addAccessibleVar(possibleDst); + } + + } + + } + break; + + case FKind.FlatSetFieldNode: { + + if (currentConflictsMap != null) { + + FlatSetFieldNode fsen = (FlatSetFieldNode) fn; + TempDescriptor dst = fsen.getDst(); + FieldDescriptor field = fsen.getField(); + TempDescriptor src = fsen.getSrc(); + + HashSet srcTempSet = getTempDescSetReferenceToSameHRN( + og, src); + for (Iterator iterator = srcTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor possibleSrc = (TempDescriptor) iterator + .next(); + if (!currentConflictsMap.isAccessible(possibleSrc)) { + currentConflictsMap.addStallSite(possibleSrc); + } + currentConflictsMap.addAccessibleVar(possibleSrc); + } + + HashSet dstTempSet = getTempDescSetReferenceToSameHRN( + og, dst); + for (Iterator iterator = dstTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor possibleDst = (TempDescriptor) iterator + .next(); + + if (!currentConflictsMap.isAccessible(possibleDst)) { + currentConflictsMap.addStallSite(possibleDst); + } + currentConflictsMap.addAccessibleVar(possibleDst); + // contribute write effect on destination's stall site + currentConflictsMap.contributeEffect(possibleDst, field + .getType().getSafeSymbol(), field.toString(), + StallSite.WRITE_EFFECT); + } + + // TODO need to create edge mapping for newly created edge + + } + + } + break; + + case FKind.FlatOpNode: { + + // destination variable gets the status of source. + FlatOpNode fon = (FlatOpNode) fn; + + if (fon.getOp().getOp() == Operation.ASSIGN + && currentConflictsMap != null) { + + TempDescriptor dst = fon.getDest(); + TempDescriptor src = fon.getLeft(); + + Integer sourceStatus = currentConflictsMap.getAccessibleMap() + .get(src); + if(sourceStatus==null){ + sourceStatus=ParentChildConflictsMap.INACCESSIBLE; + } + + HashSet dstTempSet = getTempDescSetReferenceToSameHRN( + og, dst); + + for (Iterator iterator = dstTempSet.iterator(); iterator + .hasNext();) { + TempDescriptor possibleDst = iterator.next(); + + if (sourceStatus.equals(ParentChildConflictsMap.ACCESSIBLE)) { + currentConflictsMap.addAccessibleVar(possibleDst); + } else { + currentConflictsMap.addInaccessibleVar(possibleDst); + } + + } + } + } + break; + } + + // for every program point, we keep accessible map and stall map. + if (currentConflictsMap != null) { + conflictsResults.put(fn, currentConflictsMap); + } + + } + private void codePlansForward( FlatMethod fm ) { diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java new file mode 100644 index 00000000..58d31b1f --- /dev/null +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -0,0 +1,59 @@ +package Analysis.MLP; + +import java.util.Hashtable; + +import IR.Flat.TempDescriptor; + +public class ParentChildConflictsMap { + + public static final Integer ACCESSIBLE = new Integer(1); + public static final Integer INACCESSIBLE = new Integer(2); + + private Hashtable accessibleMap; + private Hashtable stallMap; + + public ParentChildConflictsMap() { + + accessibleMap = new Hashtable(); + stallMap = new Hashtable(); + + } + + public Hashtable getAccessibleMap() { + return accessibleMap; + } + + public Hashtable getStallMap() { + return stallMap; + } + + public void addAccessibleVar(TempDescriptor td){ + accessibleMap.put(td, ACCESSIBLE); + } + + public void addInaccessibleVar(TempDescriptor td){ + accessibleMap.put(td, INACCESSIBLE); + } + + 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)){ + return true; + } + return false; + } + + public void contributeEffect(TempDescriptor td, String type, String field, int effect){ + + StallSite stallSite=stallMap.get(td); + if(stallSite!=null){ + stallSite.addEffect(type, field, effect); + } + + } + +} diff --git a/Robust/src/Analysis/MLP/StallSite.java b/Robust/src/Analysis/MLP/StallSite.java new file mode 100644 index 00000000..23480a34 --- /dev/null +++ b/Robust/src/Analysis/MLP/StallSite.java @@ -0,0 +1,39 @@ +package Analysis.MLP; + +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); + + private HashSet effectSet; + private int hrnID; + private ReachabilitySet rechabilitySet; + + public StallSite(){ + effectSet=new HashSet(); + } + + public void addEffect(String type, String field, Integer effect){ + Effect e=new Effect(type,field,effect); + effectSet.add(e); + } + +} + +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; + } + +} \ No newline at end of file