From 867859fa855734749ec581b0d6b529b787fba099 Mon Sep 17 00:00:00 2001 From: yeom Date: Thu, 8 Oct 2009 02:04:43 +0000 Subject: [PATCH] disjoint analysis with a set of flagged allocation sites of live-in variable. --- Robust/src/Analysis/MLP/MLPAnalysis.java | 296 ++++++++++++------ .../OwnershipAnalysis/AllocationSite.java | 10 + .../OwnershipAnalysis/OwnershipAnalysis.java | 38 +++ .../OwnershipAnalysis/OwnershipGraph.java | 4 + 4 files changed, 245 insertions(+), 103 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index be46e945..fdb44dc8 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -48,6 +48,8 @@ public class MLPAnalysis { private Hashtable< FlatNode, CodePlan > codePlans; private Hashtable< FlatEdge, FlatWriteDynamicVarNode > wdvNodesToSpliceIn; + + private Hashtable< MethodContext, HashSet> mapMethodContextToLiveInAllocationSiteSet; public static int maxSESEage = -1; @@ -101,6 +103,8 @@ public class MLPAnalysis { codePlans = new Hashtable< FlatNode, CodePlan >(); wdvNodesToSpliceIn = new Hashtable< FlatEdge, FlatWriteDynamicVarNode >(); + mapMethodContextToLiveInAllocationSiteSet = new Hashtable< MethodContext, HashSet>(); + FlatMethod fmMain = state.getMethodFlat( typeUtil.getMain() ); @@ -191,6 +195,26 @@ public class MLPAnalysis { FlatMethod fm = state.getMethodFlat( d ); methodEffects(fm); } + + // disjoint analysis with a set of flagged allocation sites of live-in variable + try { + OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph, + state.OWNERSHIPALLOCDEPTH, state.OWNERSHIPWRITEDOTS, + state.OWNERSHIPWRITEALL, state.OWNERSHIPALIASFILE, + state.METHODEFFECTS, + mapMethodContextToLiveInAllocationSiteSet); + // debug + methItr = oa2.descriptorsToAnalyze.iterator(); + while (methItr.hasNext()) { + Descriptor d = methItr.next(); + FlatMethod fm = state.getMethodFlat(d); + debugFunction(oa2, fm); + } + // + } catch (IOException e) { + System.err.println(e); + } + // 7th pass @@ -789,6 +813,35 @@ public class MLPAnalysis { } // end switch } + private void debugFunction(OwnershipAnalysis oa2, FlatMethod fm) { + + String methodName="method1"; + + MethodDescriptor md=fm.getMethod(); + HashSet mcSet=oa2.getAllMethodContextSetByDescriptor(md); + Iterator mcIter=mcSet.iterator(); + + while(mcIter.hasNext()){ + MethodContext mc=mcIter.next(); + + OwnershipGraph og=oa2.getOwnvershipGraphByMethodContext(mc); +// System.out.println("FM="+fm.toString()); + + if(fm.toString().indexOf(methodName)>0){ + try { + og.writeGraph(methodName + "SECONDGRAPH", true, true, true, true, false); + } catch (IOException e) { + System.out.println("Error writing debug capture."); + System.exit(0); + } + } + + + + } + + } + private void methodEffects(FlatMethod fm) { MethodDescriptor md=fm.getMethod(); @@ -853,7 +906,22 @@ public class MLPAnalysis { if (ln != null) { int taint = (int) Math.pow(2, idx); taintLabelNode(ln, taint); + + // collects related allocation sites + Iterator referenceeIter = ln + .iteratorToReferencees(); + while (referenceeIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) referenceeIter + .next(); + HeapRegionNode dstHRN = referenceEdge.getDst(); + if (!dstHRN.isParameter()) { + addLiveInAllocationSite(mc, dstHRN + .getAllocationSite()); + } + } + } + idx++; } @@ -882,14 +950,16 @@ public class MLPAnalysis { if (parentEffectsSet == null) { parentEffectsSet = new HashSet(); } - + for (Iterator iterator = effectsSet.iterator(); iterator .hasNext();) { SESEEffectsKey seseKey = (SESEEffectsKey) iterator .next(); - parentEffectsSet.add(new SESEEffectsKey(seseKey.getFieldDescriptor(), seseKey.getTypeDescriptor(), seseKey.getHRNId())); + parentEffectsSet.add(new SESEEffectsKey(seseKey + .getFieldDescriptor(), seseKey + .getTypeDescriptor(), seseKey.getHRNId())); } - + parentReadTable.put(td, parentEffectsSet); } @@ -907,7 +977,7 @@ public class MLPAnalysis { if (parentEffectsSet == null) { parentEffectsSet = new HashSet(); } - + for (Iterator iterator = effectsSet.iterator(); iterator .hasNext();) { SESEEffectsKey seseKey = (SESEEffectsKey) iterator @@ -916,10 +986,10 @@ public class MLPAnalysis { .getFieldDescriptor(), seseKey .getTypeDescriptor(), seseKey.getHRNId())); } - + parentWriteTable.put(td, parentEffectsSet); } - + Hashtable> strongUpdateTable = set .getStrongUpdateTable(); Hashtable> parentstrongUpdateTable = parent @@ -928,7 +998,8 @@ public class MLPAnalysis { keyIter = keys.iterator(); while (keyIter.hasNext()) { TempDescriptor td = (TempDescriptor) keyIter.next(); - HashSet effectsSet = strongUpdateTable.get(td); + HashSet effectsSet = strongUpdateTable + .get(td); HashSet parentEffectsSet = parentstrongUpdateTable .get(td); if (parentEffectsSet == null) { @@ -965,6 +1036,7 @@ public class MLPAnalysis { .iterator(); while (affectedIter.hasNext()) { TempDescriptor affectedTD = affectedIter.next(); + if (currentSESE.getInVarSet().contains(affectedTD)) { HashSet hrnSet = getReferenceHeapIDSet( @@ -989,41 +1061,48 @@ public class MLPAnalysis { } } } - - // handle tainted case - + + // handle tainted case + Iterator edgeIter = srcLN .iteratorToReferencees(); while (edgeIter.hasNext()) { ReferenceEdge edge = edgeIter.next(); - - if(edge.getTaintIdentifier()>0){ - HeapRegionNode accessHRN = edge.getDst(); - /// follow the chain of reference to identify possible accesses - Iterator referIter=accessHRN.iteratorToReferencers(); - while (referIter.hasNext()) { - ReferenceEdge referEdge = (ReferenceEdge) referIter.next(); - - if (referEdge.getTaintIdentifier() > 0) { - HashSet referSet = new HashSet(); - followReference(accessHRN, referSet, new HashSet(), - currentSESE); - - Iterator referSetIter=referSet.iterator(); - while (referSetIter.hasNext()) { - TempDescriptor tempDescriptor = (TempDescriptor) referSetIter - .next(); - currentSESE.readEffects(tempDescriptor, field - .getSymbol(), src.getType(), accessHRN - .getID()); - } - } + HeapRegionNode accessHRN = edge.getDst(); + // / follow the chain of reference to identify possible + // accesses + Iterator referIter = accessHRN + .iteratorToReferencers(); + while (referIter.hasNext()) { + ReferenceEdge referEdge = (ReferenceEdge) referIter + .next(); + + // if (referEdge.getTaintIdentifier() >0 || + // referEdge.getSESETaintIdentifier()>0 ) { + HashSet referSet = new HashSet(); + followReference(accessHRN, referSet, + new HashSet(), currentSESE); + + Iterator referSetIter = referSet + .iterator(); + while (referSetIter.hasNext()) { + TempDescriptor tempDescriptor = (TempDescriptor) referSetIter + .next(); + currentSESE.readEffects(tempDescriptor, field + .getSymbol(), src.getType(), accessHRN + .getID()); } - /// + // } + } + // / + if (edge.getTaintIdentifier() > 0 + || edge.getSESETaintIdentifier() > 0) { + affectedTDSet = getReferenceNodeSet(accessHRN); affectedIter = affectedTDSet.iterator(); while (affectedIter.hasNext()) { TempDescriptor affectedTD = affectedIter.next(); + if (currentSESE.getInVarSet().contains(affectedTD)) { HashSet hrnSet = getReferenceHeapIDSet( @@ -1056,26 +1135,29 @@ public class MLPAnalysis { LabelNode dstLN = og.td2ln.get(dst); if (dstLN != null) { // check possible strong updates - boolean strongUpdate = false; - - if( !field.getType().isImmutable() || field.getType().isArray() ) { - Iterator itrXhrn = dstLN.iteratorToReferencees(); - while( itrXhrn.hasNext() ) { - ReferenceEdge edgeX = itrXhrn.next(); - HeapRegionNode hrnX = edgeX.getDst(); - - // we can do a strong update here if one of two cases holds - if( field != null && - field != OwnershipAnalysis.getArrayField( field.getType() ) && - ( (hrnX.getNumReferencers() == 1) || // case 1 - (hrnX.isSingleObject() && dstLN.getNumReferencees() == 1) // case 2 - ) - ) { - strongUpdate = true; - } - } - } - + boolean strongUpdate = false; + + if (!field.getType().isImmutable() || field.getType().isArray()) { + Iterator itrXhrn = dstLN + .iteratorToReferencees(); + while (itrXhrn.hasNext()) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); + + // we can do a strong update here if one of two cases + // holds + if (field != null + && field != OwnershipAnalysis + .getArrayField(field.getType()) + && ((hrnX.getNumReferencers() == 1) || // case 1 + (hrnX.isSingleObject() && dstLN + .getNumReferencees() == 1) // case 2 + )) { + strongUpdate = true; + } + } + } + HashSet affectedTDSet = getAccessedTaintNodeSet(dstLN); Iterator affectedIter = affectedTDSet @@ -1091,60 +1173,58 @@ public class MLPAnalysis { while (hrnIter.hasNext()) { HeapRegionNode hrn = hrnIter.next(); - if (field.getType().isImmutable()) { - currentSESE.writeEffects(affectedTD, field - .getSymbol(), dst.getType(), hrn - .getID(),strongUpdate); - - } else { - Iterator referencers = hrn - .iteratorToReferencers(); - while (referencers.hasNext()) { - ReferenceEdge referenceEdge = (ReferenceEdge) referencers - .next(); - if (field.getSymbol().equals( - referenceEdge.getField())) { - currentSESE.writeEffects(affectedTD, - field.getSymbol(), dst - .getType(), - referenceEdge.getDst().getID(),strongUpdate); - } + Iterator referencers = hrn + .iteratorToReferencers(); + while (referencers.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) referencers + .next(); + if (field.getSymbol().equals( + referenceEdge.getField())) { + currentSESE.writeEffects(affectedTD, field + .getSymbol(), dst.getType(), + referenceEdge.getDst().getID(), + strongUpdate); } } } } } - + // handle tainted case Iterator edgeIter = dstLN .iteratorToReferencees(); while (edgeIter.hasNext()) { ReferenceEdge edge = edgeIter.next(); - if (edge.getTaintIdentifier() > 0) { - HeapRegionNode accessHRN = edge.getDst(); - /// follow the chain of reference to identify possible accesses - Iterator referIter=accessHRN.iteratorToReferencers(); - while (referIter.hasNext()) { - ReferenceEdge referEdge = (ReferenceEdge) referIter.next(); - - if (referEdge.getTaintIdentifier() > 0) { - HashSet referSet = new HashSet(); - followReference(accessHRN, referSet, new HashSet(), - currentSESE); - Iterator referSetIter=referSet.iterator(); - while (referSetIter.hasNext()) { - TempDescriptor tempDescriptor = (TempDescriptor) referSetIter - .next(); - currentSESE.writeEffects(tempDescriptor, field - .getSymbol(), dst.getType(), accessHRN - .getID(),strongUpdate); - } - } - + HeapRegionNode accessHRN = edge.getDst(); + // / follow the chain of reference to identify possible + // accesses + Iterator referIter = accessHRN + .iteratorToReferencers(); + while (referIter.hasNext()) { + ReferenceEdge referEdge = (ReferenceEdge) referIter + .next(); + + // if (referEdge.getTaintIdentifier() > 0 || + // referEdge.getSESETaintIdentifier() > 0 ) { + HashSet referSet = new HashSet(); + followReference(accessHRN, referSet, + new HashSet(), currentSESE); + Iterator referSetIter = referSet + .iterator(); + while (referSetIter.hasNext()) { + TempDescriptor tempDescriptor = (TempDescriptor) referSetIter + .next(); + currentSESE.writeEffects(tempDescriptor, field + .getSymbol(), dst.getType(), accessHRN + .getID(), strongUpdate); } - /// + // } + } + // / + if (edge.getTaintIdentifier() > 0 + || edge.getSESETaintIdentifier() > 0) { affectedTDSet = getReferenceNodeSet(accessHRN); affectedIter = affectedTDSet.iterator(); while (affectedIter.hasNext()) { @@ -1159,8 +1239,8 @@ public class MLPAnalysis { HeapRegionNode hrn = hrnIter.next(); currentSESE.writeEffects(affectedTD, field .getSymbol(), dst.getType(), hrn - .getID(),strongUpdate); - + .getID(), strongUpdate); + } } @@ -1203,9 +1283,9 @@ public class MLPAnalysis { i + base); Set writeSet = me.getEffects().getWritingSet( i + base); - - Set strongUpdateSet = me.getEffects().getStrongUpdateSet( - i + base); + + Set strongUpdateSet = me.getEffects() + .getStrongUpdateSet(i + base); LabelNode argLN = og.td2ln.get(arg); if (argLN != null) { @@ -1255,12 +1335,12 @@ public class MLPAnalysis { currentSESE.writeEffects(affectedTD, key.getFieldDescriptor(), key .getTypeDescriptor(), - hrnID,false); + hrnID, false); } } } - + if (strongUpdateSet != null) { Iterator strongUpdateIter = strongUpdateSet .iterator(); @@ -1278,12 +1358,11 @@ public class MLPAnalysis { currentSESE.writeEffects(affectedTD, key.getFieldDescriptor(), key .getTypeDescriptor(), - hrnID,true); + hrnID, true); } } } - } @@ -1299,6 +1378,15 @@ public class MLPAnalysis { } } + private void addLiveInAllocationSite(MethodContext mc, AllocationSite ac){ + HashSet set=mapMethodContextToLiveInAllocationSiteSet.get(mc); + if(set==null){ + set=new HashSet(); + } + set.add(ac); + mapMethodContextToLiveInAllocationSiteSet.put(mc, set); + } + private void followReference(HeapRegionNode hrn,HashSet tdSet, HashSet visited, FlatSESEEnterNode currentSESE){ Iterator referIter=hrn.iteratorToReferencers(); @@ -1354,6 +1442,8 @@ public class MLPAnalysis { OwnershipNode node = referencerEdge.getSrc(); if (node instanceof LabelNode) { referencerEdge.unionSESETaintIdentifier(identifier); + }else if(node instanceof HeapRegionNode){ + referencerEdge.unionSESETaintIdentifier(identifier); } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index 96aa73eb..d6616e67 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -39,6 +39,8 @@ public class AllocationSite { public static final int SHADOWAGE_in_I = -101; public static final int SHADOWAGE_oldest = -102; public static final int SHADOWAGE_summary = -103; + + private boolean flag=false; public AllocationSite(int allocationDepth, FlatNew flatNew, String disjointId) { @@ -196,4 +198,12 @@ public class AllocationSite { return toString()+"\\n"+getType().toPrettyString(); } } + + public void setFlag(boolean flag){ + this.flag=flag; + } + + public boolean getFlag(){ + return flag; + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 147cc3c1..e323687e 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -343,6 +343,9 @@ public class OwnershipAnalysis { //keep internal ownership graph by method context and flat node private Hashtable> mapMethodContextToFlatNodeOwnershipGraph; + + //map method context to a set of allocation sites of live-in vars + private Hashtable> mapMethodContextToLiveInAllocationSiteSet; @@ -375,6 +378,26 @@ public class OwnershipAnalysis { } + // new constructor for on-demand disjoint analysis + public OwnershipAnalysis( + State state, + TypeUtil tu, + CallGraph callGraph, + int allocationDepth, + boolean writeDOTs, + boolean writeAllDOTs, + String aliasFile, + boolean methodEffects, + Hashtable> mapMethodContextToLiveInAllocationSiteSet) + throws java.io.IOException { + + this.methodEffects = methodEffects; + this.mapMethodContextToLiveInAllocationSiteSet=mapMethodContextToLiveInAllocationSiteSet; + init(state, tu, callGraph, allocationDepth, writeDOTs, writeAllDOTs, + aliasFile); + + } + private void init(State state, TypeUtil tu, CallGraph callGraph, @@ -874,6 +897,21 @@ public class OwnershipAnalysis { lhs = fnn.getDst(); if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn); + + if (mapMethodContextToLiveInAllocationSiteSet != null){ + HashSet alllocSet=mapMethodContextToLiveInAllocationSiteSet.get(mc); + if(alllocSet!=null){ + for (Iterator iterator = alllocSet.iterator(); iterator + .hasNext();) { + AllocationSite allocationSite = (AllocationSite) iterator + .next(); + if(allocationSite.flatNew.equals(as.flatNew)){ + as.setFlag(true); + } + } + } + } + og.assignTempEqualToNewAlloc(lhs, as); } break; diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 4b538f19..61e076f4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -1330,6 +1330,10 @@ public class OwnershipGraph { if( as.getType().isClass() ) { hasFlags = as.getType().getClassDesc().hasFlags(); } + + if(as.getFlag()){ + hasFlags=as.getFlag(); + } hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one false, // single object? -- 2.34.1