From 9f9640e77dd76b4d6eb9a5e6e56b3313015ad179 Mon Sep 17 00:00:00 2001 From: yeom Date: Wed, 31 Mar 2010 23:45:11 +0000 Subject: [PATCH] fixes for memory effects analysis. --- Robust/src/Analysis/MLP/MLPAnalysis.java | 684 +++++++----------- Robust/src/Analysis/MLP/SESEEffectsSet.java | 19 + .../OwnershipAnalysis/MethodEffects.java | 138 +++- .../MethodEffectsAnalysis.java | 21 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 14 +- 5 files changed, 444 insertions(+), 432 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 2533d5a2..0f805a46 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -34,6 +34,7 @@ import IR.FieldDescriptor; import IR.MethodDescriptor; import IR.Operation; import IR.State; +import IR.TypeDescriptor; import IR.TypeUtil; import IR.Flat.FKind; import IR.Flat.FlatCall; @@ -41,7 +42,6 @@ import IR.Flat.FlatCondBranch; import IR.Flat.FlatEdge; import IR.Flat.FlatElementNode; import IR.Flat.FlatFieldNode; -import IR.Flat.FlatLiteralNode; import IR.Flat.FlatMethod; import IR.Flat.FlatNew; import IR.Flat.FlatNode; @@ -1131,6 +1131,7 @@ public class MLPAnalysis { dstHRN, visitedHRN); } } else { +// System.out.println("FLAGGED "+callerMC+":fc="+fc+":arg="+arg+" , paramIdx="+paramIdx); flagAllocationSite(callerMC, dstHRN .getAllocationSite()); } @@ -1203,24 +1204,9 @@ public class MLPAnalysis { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; assert fsen.equals(currentSESE); -// if(fsen.getParent()!=null && fsen.getParent().getSeseEffectsSet()!=null){ -// Hashtable> strongTable= -// fsen.getParent().getSeseEffectsSet().getStrongUpdateTable(); -// fsen.getSeseEffectsSet().getStrongUpdateTable().putAll(strongTable); -// } - - if (!fsen.getIsCallerSESEplaceholder()) { // uniquely taint each live-in variable Set set = fsen.getInVarSet(); - // -// Set tempSet=fsen.getOutVarSet(); -// for (Iterator iterator = tempSet.iterator(); iterator.hasNext();) { -// TempDescriptor tempDescriptor = (TempDescriptor) iterator -// .next(); -// set.add(tempDescriptor); -// } - // Iterator iter = set.iterator(); int idx = 0; while (iter.hasNext()) { @@ -1229,6 +1215,7 @@ public class MLPAnalysis { if (ln != null) { int taint = (int) Math.pow(2, idx); taintLabelNode(ln, taint); + currentSESE.getSeseEffectsSet().setInVarIdx(idx, td); // collects related allocation sites Iterator referenceeIter = ln @@ -1245,6 +1232,7 @@ public class MLPAnalysis { visitedHRN); } else { +// System.out.println("FLAGGED "+fsen+":"+td); flagAllocationSite(mc, dstHRN .getAllocationSite()); } @@ -1263,6 +1251,19 @@ public class MLPAnalysis { FlatSESEExitNode fsexit = (FlatSESEExitNode) fn; if (!fsexit.getFlatEnter().getIsCallerSESEplaceholder()) { + + // clear taint information of live-in variables + Set keySet=og.id2hrn.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer hrnID = (Integer) iterator.next(); + HeapRegionNode hrn=og.id2hrn.get(hrnID); + Iterator edgeIter=hrn.iteratorToReferencers(); + while (edgeIter.hasNext()) { + ReferenceEdge refEdge = (ReferenceEdge) edgeIter + .next(); + refEdge.setSESETaintIdentifier(0); + } + } FlatSESEEnterNode enterNode = fsexit.getFlatEnter(); FlatSESEEnterNode parent = enterNode.getParent(); @@ -1368,97 +1369,26 @@ public class MLPAnalysis { FieldDescriptor field = ffn.getField(); LabelNode srcLN = og.td2ln.get(src); - if (srcLN != null) { - HashSet affectedTDSet = getAccessedTaintNodeSet(srcLN); - Iterator affectedIter = affectedTDSet - .iterator(); - while (affectedIter.hasNext()) { - TempDescriptor affectedTD = affectedIter.next(); - - if (currentSESE.getInVarSet().contains(affectedTD) || ((!currentSESE.getInVarSet().contains(affectedTD)) && currentSESE.getOutVarSet().contains(affectedTD)) ) { - - HashSet hrnSet = getReferenceHeapIDSet( - og, affectedTD); - Iterator hrnIter = hrnSet.iterator(); - while (hrnIter.hasNext()) { - HeapRegionNode hrn = hrnIter.next(); - - Iterator referencers = hrn - .iteratorToReferencers(); - while (referencers.hasNext()) { - ReferenceEdge referenceEdge = (ReferenceEdge) referencers - .next(); - if (field.getSymbol().equals( - referenceEdge.getField())) { - - HeapRegionNode refHRN = og.id2hrn - .get(referenceEdge.getDst().getID()); - - currentSESE - .readEffects(affectedTD, field - .getSymbol(), - src.getType(), refHRN); - } - } - - } - } - } - - // handle tainted case - - Iterator edgeIter = srcLN - .iteratorToReferencees(); + if(srcLN!=null){ + Iterator edgeIter=srcLN.iteratorToReferencees(); while (edgeIter.hasNext()) { - ReferenceEdge edge = edgeIter.next(); - HeapRegionNode accessHRN = edge.getDst(); - // / follow the chain of reference to identify possible - // accesses - Iterator referIter = accessHRN - .iteratorToReferencers(); - while (referIter.hasNext()) { - ReferenceEdge referEdge = (ReferenceEdge) referIter + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + HeapRegionNode refHRN=referenceEdge.getDst(); + int edgeTaint=referenceEdge.getSESETaintIdentifier(); + + // figure out which invar has related effects + int taint=referenceEdge.getSESETaintIdentifier(); + Hashtable map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx(); + Set keySet=map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor inVarTD = (TempDescriptor) iterator .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); - } - // } - } - // / - 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( - og, affectedTD); - Iterator hrnIter = hrnSet - .iterator(); - while (hrnIter.hasNext()) { - HeapRegionNode hrn = hrnIter.next(); - currentSESE.readEffects(affectedTD, field - .getSymbol(), src.getType(), hrn); - } - - } - + int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue()); + if((inVarMask&edgeTaint)>0){ + // found related invar, contribute effects + currentSESE.readEffects(inVarTD, field.getSymbol(),src.getType(), refHRN); } } } @@ -1473,56 +1403,122 @@ public class MLPAnalysis { TempDescriptor dest=fon.getDest(); TempDescriptor src=fon.getLeft(); -// if(!currentSESE.getIsCallerSESEplaceholder()){ - if( fon.getOp().getOp() ==Operation.ASSIGN && ( currentSESE.getInVarSet().contains(src) || (currentSESE.getOutVarSet().contains(src)))){ - invarMap.put(dest, src); + if(currentSESE.getInVarSet().contains(src)){ + int idx=currentSESE.getSeseEffectsSet().getInVarIdx(src); + if(idx==-1){ + break; + } + + //mark dest's edges for corresponding sese live in-var. + LabelNode srcLN = og.td2ln.get(dest); + if (srcLN != null) { + Iterator refEdgeIter=srcLN.iteratorToReferencees(); + while (refEdgeIter.hasNext()) { + ReferenceEdge edge = refEdgeIter.next(); + int newTaint = (int) Math.pow(2, idx); + edge.unionSESETaintIdentifier(newTaint); + } } -// } - - }break; - - case FKind.FlatNew:{ - FlatNew fnew=(FlatNew)fn; - TempDescriptor dst=fnew.getDst(); - if(dst.getType().isArray()){ - currentSESE.getSeseEffectsSet().addStrongUpdateVar(dst, new SESEEffectsKey("", dst.getType(), new Integer(0), "")); } - }break; case FKind.FlatElementNode:{ FlatElementNode fsen=(FlatElementNode)fn; TempDescriptor src = fsen.getSrc(); + TempDescriptor dst = fsen.getDst(); + String field="___element_"; + + LabelNode srcLN = og.td2ln.get(src); + int taintIdentifier=0; + if(srcLN!=null){ + Iterator edgeIter=srcLN.iteratorToReferencees(); + while (edgeIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + HeapRegionNode dstHRN=referenceEdge.getDst(); + taintIdentifier=referenceEdge.getSESETaintIdentifier(); + + // figure out which invar has related effects + int taint=referenceEdge.getSESETaintIdentifier(); + Hashtable map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx(); + Set keySet=map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor inVarTD = (TempDescriptor) iterator + .next(); + int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue()); + if((inVarMask&taintIdentifier)>0){ + // found related invar, contribute effects + currentSESE.readEffects(inVarTD, field,src.getType(), dstHRN); + } + } + + } + } - if(invarMap.containsKey(src)){ - TempDescriptor invarTD=invarMap.get(src); - currentSESE.getSeseEffectsSet().addReadingVar(invarTD, new SESEEffectsKey("", src.getType(), new Integer(0), "")); + // taint + LabelNode dstLN = og.td2ln.get(dst); + if(dstLN!=null){ + Iterator edgeIter=dstLN.iteratorToReferencees(); + while (edgeIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + referenceEdge.unionSESETaintIdentifier(taintIdentifier); + } } }break; - case FKind.FlatSetElementNode:{ - - FlatSetElementNode fsen=(FlatSetElementNode)fn; + case FKind.FlatSetElementNode: { + + FlatSetElementNode fsen = (FlatSetElementNode) fn; TempDescriptor dst = fsen.getDst(); + TypeDescriptor tdElement = dst.getType().dereference(); + + String field = "___element_"; - if(invarMap.containsKey(dst)){ - TempDescriptor invarTD=invarMap.get(dst); + LabelNode dstLN=og.td2ln.get(dst); + if(dst!=null){ - SESEEffectsSet effectSet=currentSESE.getSeseEffectsSet(); - ///// if write effects occurs through variable which was strongly updated, ignore it? - if(effectSet.getStrongUpdateSet(invarTD)!=null && effectSet.getStrongUpdateSet(invarTD).size()>0){ - SESEEffectsKey key=new SESEEffectsKey("", dst.getType(), new Integer(0), ""); - key.setStrong(true); - currentSESE.getSeseEffectsSet().addWritingVar(invarTD, key); - }else{ - currentSESE.getSeseEffectsSet().addWritingVar(invarTD, new SESEEffectsKey("", dst.getType(), new Integer(0), "")); + Iterator edgeIter=dstLN.iteratorToReferencees(); + while (edgeIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + HeapRegionNode dstHRN=referenceEdge.getDst(); + int edgeTaint=referenceEdge.getSESETaintIdentifier(); + + // we can do a strong update here if one of two cases + // holds + boolean strongUpdate=false; + if (field != null && !dst.getType().isImmutable() + && ((dstHRN.getNumReferencers() == 1) || // case 1 + (dstHRN.isSingleObject() && dstLN + .getNumReferencees() == 1) // case 2 + )) { + strongUpdate = true; + } + + + // figure out which invar has related effects + Hashtable map=currentSESE.getSeseEffectsSet().getMapTempDescToInVarIdx(); + Set keySet=map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor inVarTD = (TempDescriptor) iterator + .next(); + int inVarMask=(int) Math.pow(2, map.get(inVarTD).intValue()); + if((inVarMask&edgeTaint)>0){ + // found related invar, contribute effects + currentSESE.writeEffects(inVarTD, field, dst.getType(),dstHRN, strongUpdate); + } } - ///// + } + } + }break; case FKind.FlatSetFieldNode: { @@ -1532,132 +1528,50 @@ public class MLPAnalysis { FieldDescriptor field = fsen.getField(); 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; - } - } - } - HashSet affectedTDSet = getAccessedTaintNodeSet(dstLN); - Iterator affectedIter = affectedTDSet - .iterator(); - - while (affectedIter.hasNext()) { - TempDescriptor affectedTD = affectedIter.next(); - if (currentSESE.getInVarSet().contains(affectedTD) || ((!currentSESE.getInVarSet().contains(affectedTD)) && currentSESE.getOutVarSet().contains(affectedTD)) ) { - - HashSet hrnSet = getReferenceHeapIDSet( - og, affectedTD); - Iterator hrnIter = hrnSet.iterator(); - while (hrnIter.hasNext()) { - HeapRegionNode hrn = hrnIter.next(); - Iterator referencers = hrn - .iteratorToReferencers(); - while (referencers.hasNext()) { - ReferenceEdge referenceEdge = (ReferenceEdge) referencers - .next(); - if (field.getSymbol().equals( - referenceEdge.getField())) { - - HeapRegionNode refHRN = og.id2hrn - .get(referenceEdge.getDst().getID()); - currentSESE.writeEffects(affectedTD, field - .getSymbol(), dst.getType(), - refHRN, strongUpdate); - } - } - - } - } - } - - // handle tainted case - Iterator edgeIter = dstLN - .iteratorToReferencees(); + if(dstLN!=null){ + + Iterator edgeIter=dstLN.iteratorToReferencees(); while (edgeIter.hasNext()) { - ReferenceEdge edge = edgeIter.next(); - - 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(); - SESEEffectsSet effectSet=currentSESE.getSeseEffectsSet(); - ///// if write effects occurs through variable which was strongly updated, ignore it? - if(effectSet.getStrongUpdateSet(tempDescriptor)!=null && effectSet.getStrongUpdateSet(tempDescriptor).size()>0){ -// System.out.println("not write effect?"); - }else{ - currentSESE.writeEffects(tempDescriptor, field - .getSymbol(), dst.getType(), accessHRN, - strongUpdate); - } - ///// - } - // } + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + HeapRegionNode dstHRN=referenceEdge.getDst(); + int edgeTaint=referenceEdge.getSESETaintIdentifier(); + + // we can do a strong update here if one of two cases + // holds + boolean strongUpdate=false; + if (field != null && !field.getType().isImmutable() + && field != OwnershipAnalysis + .getArrayField(field.getType()) + && ((dstHRN.getNumReferencers() == 1) || // case 1 + (dstHRN.isSingleObject() && dstLN + .getNumReferencees() == 1) // case 2 + )) { + strongUpdate = true; } - // / - 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( - og, affectedTD); - Iterator hrnIter = hrnSet - .iterator(); - while (hrnIter.hasNext()) { - HeapRegionNode hrn = hrnIter.next(); - currentSESE.writeEffects(affectedTD, field - .getSymbol(), dst.getType(), hrn, - strongUpdate); - - } - - } - + + + // figure out which invar has related effects + Hashtable map = currentSESE + .getSeseEffectsSet().getMapTempDescToInVarIdx(); + Set keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor inVarTD = (TempDescriptor) iterator + .next(); + int inVarMask = (int) Math.pow(2, map.get(inVarTD) + .intValue()); + if ((inVarMask & edgeTaint) > 0) { + // found related invar, contribute effects + currentSESE.writeEffects(inVarTD, + field.getSymbol(), dst.getType(), dstHRN, + strongUpdate); } } - } - + + + } } - } break; @@ -1668,7 +1582,6 @@ public class MLPAnalysis { MethodEffects me = ownAnalysis.getMethodEffectsAnalysis() .getMethodEffectsByMethodContext(calleeMC); - OwnershipGraph calleeOG = ownAnalysis .getOwnvershipGraphByMethodContext(calleeMC); @@ -1719,107 +1632,114 @@ public class MLPAnalysis { } LabelNode argLN = og.td2ln.get(arg); - if (argLN != null) { - HashSet affectedTDSet = getAccessedTaintNodeSet(argLN); - Iterator affectedIter = affectedTDSet - .iterator(); - - while (affectedIter.hasNext()) { - - TempDescriptor affectedTD = affectedIter.next(); - if(isThis){ - if (currentSESE.getInVarSet().contains(affectedTD)) { -// Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx); -// Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx); -// System.out.println("primID="+hrnPrimaryID); -// System.out.println("seconID="+hrnSecondaryID); - } - } - if (currentSESE.getInVarSet().contains(affectedTD)) { - - if (readSet != null) { - Iterator readIter = readSet - .iterator(); - while (readIter.hasNext()) { - EffectsKey key = readIter.next(); - Set hrnSet = getCallerHRNId( - new Integer(paramIdx), calleeOG, - key.getHRNId(), decomp); - Iterator hrnIter = hrnSet + if( argLN!=null){ + Iterator edgeIter=argLN.iteratorToReferencees(); + while (edgeIter.hasNext()) { + ReferenceEdge referenceEdge = (ReferenceEdge) edgeIter + .next(); + HeapRegionNode dstHRN=referenceEdge.getDst(); + int edgeTaint=referenceEdge.getSESETaintIdentifier(); + + // figure out which invar has related effects + Hashtable map = currentSESE + .getSeseEffectsSet().getMapTempDescToInVarIdx(); + Set keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator + .hasNext();) { + TempDescriptor inVarTD = (TempDescriptor) iterator + .next(); + int inVarMask = (int) Math.pow(2, map.get(inVarTD) + .intValue()); + + if ((inVarMask & edgeTaint) > 0) { + // found related invar, contribute effects + + if (readSet != null) { + Iterator readIter = readSet .iterator(); - while (hrnIter.hasNext()) { - Integer hrnID = (Integer) hrnIter - .next(); - - HeapRegionNode refHRN = og.id2hrn - .get(hrnID); - - currentSESE.readEffects(affectedTD, key - .getFieldDescriptor(), key - .getTypeDescriptor(), refHRN); - + while (readIter.hasNext()) { + EffectsKey key = readIter.next(); + Set hrnSet = getCallerHRNId( + new Integer(paramIdx), calleeOG, + key.getHRNId(), decomp); + Iterator hrnIter = hrnSet + .iterator(); + while (hrnIter.hasNext()) { + Integer hrnID = (Integer) hrnIter + .next(); + + HeapRegionNode refHRN = og.id2hrn + .get(hrnID); + + currentSESE.readEffects(inVarTD, key + .getFieldDescriptor(), key + .getTypeDescriptor(), refHRN); + + } } } - } - - if (writeSet != null) { - Iterator writeIter = writeSet - .iterator(); - while (writeIter.hasNext()) { - EffectsKey key = writeIter.next(); - - Set hrnSet = getCallerHRNId( - new Integer(paramIdx), calleeOG, - key.getHRNId(), decomp); - Iterator hrnIter = hrnSet + + if (writeSet != null) { + Iterator writeIter = writeSet .iterator(); - while (hrnIter.hasNext()) { - Integer hrnID = (Integer) hrnIter - .next(); + while (writeIter.hasNext()) { + EffectsKey key = writeIter.next(); + + Set hrnSet = getCallerHRNId( + new Integer(paramIdx), calleeOG, + key.getHRNId(), decomp); + Iterator hrnIter = hrnSet + .iterator(); + while (hrnIter.hasNext()) { + Integer hrnID = (Integer) hrnIter + .next(); + + HeapRegionNode refHRN = og.id2hrn + .get(hrnID); + + currentSESE.writeEffects(inVarTD, + key.getFieldDescriptor(), key + .getTypeDescriptor(), + refHRN, false); + } - HeapRegionNode refHRN = og.id2hrn - .get(hrnID); - currentSESE.writeEffects(affectedTD, - key.getFieldDescriptor(), key - .getTypeDescriptor(), - refHRN, false); } - } - } - if (strongUpdateSet != null) { - Iterator strongUpdateIter = strongUpdateSet - .iterator(); - while (strongUpdateIter.hasNext()) { - EffectsKey key = strongUpdateIter.next(); - - Set hrnSet = getCallerHRNId( - new Integer(paramIdx), calleeOG, - key.getHRNId(), decomp); - Iterator hrnIter = hrnSet + if (strongUpdateSet != null) { + Iterator strongUpdateIter = strongUpdateSet .iterator(); - while (hrnIter.hasNext()) { - Integer hrnID = (Integer) hrnIter + while (strongUpdateIter.hasNext()) { + EffectsKey key = strongUpdateIter .next(); - HeapRegionNode refHRN = og.id2hrn - .get(hrnID); - currentSESE.writeEffects(affectedTD, - key.getFieldDescriptor(), key - .getTypeDescriptor(), - refHRN, true); + Set hrnSet = getCallerHRNId( + new Integer(paramIdx), + calleeOG, key.getHRNId(), + decomp); + Iterator hrnIter = hrnSet + .iterator(); + while (hrnIter.hasNext()) { + Integer hrnID = (Integer) hrnIter + .next(); + + HeapRegionNode refHRN = og.id2hrn + .get(hrnID); + + currentSESE.writeEffects(inVarTD, + key.getFieldDescriptor(), + key.getTypeDescriptor(), + refHRN, true); + } } - - } - } - + } // end of if (strongUpdateSet != null) + + } // end of if ((inVarMask & edgeTaint) > 0) } - + } - } - + } } @@ -1829,7 +1749,6 @@ public class MLPAnalysis { } private void flagAllocationSite(MethodContext mc, AllocationSite ac){ - HashSet set=mapMethodContextToLiveInAllocationSiteSet.get(mc); if(set==null){ set=new HashSet(); @@ -1884,42 +1803,11 @@ public class MLPAnalysis { Iterator edgeIter = ln.iteratorToReferencees(); while (edgeIter.hasNext()) { ReferenceEdge edge = edgeIter.next(); - HeapRegionNode hrn = edge.getDst(); - - Iterator edgeReferencerIter = hrn - .iteratorToReferencers(); - while (edgeReferencerIter.hasNext()) { - ReferenceEdge referencerEdge = edgeReferencerIter.next(); - OwnershipNode node = referencerEdge.getSrc(); - if (node instanceof LabelNode) { - referencerEdge.unionSESETaintIdentifier(identifier); - }else if(node instanceof HeapRegionNode){ - referencerEdge.unionSESETaintIdentifier(identifier); - } - } - + edge.setSESETaintIdentifier(identifier); } } - private HashSet getReferenceNodeSet(HeapRegionNode hrn){ - - HashSet returnSet=new HashSet(); - - Iterator edgeIter=hrn.iteratorToReferencers(); - while(edgeIter.hasNext()){ - ReferenceEdge edge=edgeIter.next(); - if(edge.getSrc() instanceof LabelNode){ - LabelNode ln=(LabelNode)edge.getSrc(); - returnSet.add(ln.getTempDescriptor()); - } - } - - return returnSet; - - } - - private HashSet getReferenceHeapIDSet(OwnershipGraph og, TempDescriptor td){ HashSet returnSet=new HashSet(); @@ -1937,38 +1825,6 @@ public class MLPAnalysis { } - private HashSet getAccessedTaintNodeSet(LabelNode ln) { - - HashSet returnSet = new HashSet(); - - Iterator edgeIter = ln.iteratorToReferencees(); - while (edgeIter.hasNext()) { - ReferenceEdge edge = edgeIter.next(); - HeapRegionNode hrn = edge.getDst(); - - Iterator edgeReferencerIter = hrn - .iteratorToReferencers(); - while (edgeReferencerIter.hasNext()) { - ReferenceEdge referencerEdge = edgeReferencerIter.next(); - - if (referencerEdge.getSrc() instanceof LabelNode) { - if (!((LabelNode) referencerEdge.getSrc()).equals(ln)) { - - if (referencerEdge.getSESETaintIdentifier() > 0) { - TempDescriptor td = ((LabelNode) referencerEdge - .getSrc()).getTempDescriptor(); - returnSet.add(td); - } - } - } - } - - } - - return returnSet; - - } - private HashSet getRefEdgeSetReferenceToSameHRN( OwnershipGraph og, TempDescriptor td) { @@ -2049,7 +1905,7 @@ public class MLPAnalysis { } private void calculateCovering(ConflictGraph conflictGraph){ - + uniqueLockSetId=0; // reset lock counter for every new conflict graph HashSet fineToCover = new HashSet(); HashSet coarseToCover = new HashSet(); HashSet lockSet=new HashSet(); @@ -2813,6 +2669,7 @@ public class MLPAnalysis { setupRelatedAllocSiteAnalysis(og, mc, hrn, visitedHRN); } else { +// System.out.println("FLAGGED "+mc+":"+ffn); flagAllocationSite(mc, hrn.getAllocationSite()); } } @@ -2863,7 +2720,6 @@ public class MLPAnalysis { currentConflictsMap.addAccessibleVar(src); if (!currentConflictsMap.isAccessible(dst)) { - if(invarMap.containsKey(dst)){ currentConflictsMap.addStallSite(dst, new HashSet(), new StallTag(fn),invarMap.get(dst)); @@ -2884,14 +2740,6 @@ public class MLPAnalysis { preEffectAnalysis(og, dst, null, PreEffectsKey.WRITE_EFFECT); } - -// if(invarMap.containsKey(dst)){ -// System.out.println("THIS IS FLAT SET FIELD:"+dst+ "with sese="+currentSESE); -// TempDescriptor invarTD=invarMap.get(dst); -// currentSESE.getSeseEffectsSet().addWritingVar(invarTD, new SESEEffectsKey("", dst.getType(), new Integer(0), "")); -// } - - } break; case FKind.FlatSetFieldNode: { diff --git a/Robust/src/Analysis/MLP/SESEEffectsSet.java b/Robust/src/Analysis/MLP/SESEEffectsSet.java index c03edfc7..e8f0da96 100644 --- a/Robust/src/Analysis/MLP/SESEEffectsSet.java +++ b/Robust/src/Analysis/MLP/SESEEffectsSet.java @@ -12,13 +12,32 @@ public class SESEEffectsSet { private Hashtable> readTable; private Hashtable> writeTable; private Hashtable> strongUpdateTable; + private Hashtable mapTempDescToInVarIdx; public SESEEffectsSet() { readTable = new Hashtable>(); writeTable = new Hashtable>(); strongUpdateTable = new Hashtable>(); + mapTempDescToInVarIdx = new Hashtable(); } + public void setInVarIdx(int idx, TempDescriptor td){ + mapTempDescToInVarIdx.put(td,new Integer(idx)); + } + + public int getInVarIdx(TempDescriptor td){ + Integer idx=mapTempDescToInVarIdx.get(td); + if(idx==null){ + // if invar is from SESE placeholder, it is going to be ignored. + return -1; + } + return idx.intValue(); + } + + public Hashtable getMapTempDescToInVarIdx(){ + return mapTempDescToInVarIdx; + } + public void addReadingVar(TempDescriptor td, SESEEffectsKey access) { HashSet aSet = readTable.get(td); if (aSet == null) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java index ece3a5bf..048892b0 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java @@ -41,8 +41,6 @@ public class MethodEffects { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); -// effectsSet.addReadingVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); } } @@ -58,8 +56,6 @@ public class MethodEffects { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); -// effectsSet.addReadingVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); } } @@ -69,6 +65,132 @@ public class MethodEffects { } } + + public void analyzeFlatElementNode(OwnershipGraph og, + TempDescriptor srcDesc, FieldDescriptor fieldDesc){ + + LabelNode ln = getLabelNodeFromTemp(og, srcDesc); + if (ln != null) { + Iterator heapRegionsItr = ln.iteratorToReferencees(); + + while (heapRegionsItr.hasNext()) { + ReferenceEdge edge = heapRegionsItr.next(); + HeapRegionNode hrn = edge.getDst(); + + if (hrn.isParameter()) { + Set paramSet = og.idPrimary2paramIndexSet.get(hrn + .getID()); + + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + effectsSet.addReadingVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); + } + } + + // check weather this heap region is parameter + // reachable... + + paramSet = og.idSecondary2paramIndexSet.get(hrn.getID()); + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + effectsSet.addReadingVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); + } + } + + } + } + } + + + + + } + + public void analyzeFlatSetElementNode(OwnershipGraph og, + TempDescriptor dstDesc, FieldDescriptor fieldDesc) { + + LabelNode ln = getLabelNodeFromTemp(og, dstDesc); + if (ln != null) { + + // / check possible strong updates + boolean strongUpdate = false; + if (!fieldDesc.getType().isImmutable() + || fieldDesc.getType().isArray()) { + Iterator itrXhrn = ln.iteratorToReferencees(); + while (itrXhrn.hasNext()) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); + + if (fieldDesc != null + && fieldDesc != OwnershipAnalysis + .getArrayField(fieldDesc.getType()) + && ((hrnX.getNumReferencers() == 1) || // case 1 + (hrnX.isSingleObject() && ln.getNumReferencees() == 1) // case + // 2 + )) { + strongUpdate = true; + } + } + } + // // + + Iterator heapRegionsItr = ln.iteratorToReferencees(); + while (heapRegionsItr.hasNext()) { + ReferenceEdge edge = heapRegionsItr.next(); + HeapRegionNode hrn = edge.getDst(); + + if (hrn.isParameter()) { + Set paramSet = og.idPrimary2paramIndexSet.get(hrn + .getID()); + + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + effectsSet.addWritingVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), dstDesc.getType(), + hrn.getID(), hrn + .getGloballyUniqueIdentifier(), 0)); + if(strongUpdate){ + effectsSet.addStrongUpdateVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); + } + } + } + + // check weather this heap region is parameter + // reachable... + + paramSet = og.idSecondary2paramIndexSet.get(hrn.getID()); + if (paramSet != null) { + Iterator paramIter = paramSet.iterator(); + + while (paramIter.hasNext()) { + Integer paramID = paramIter.next(); + effectsSet.addWritingVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), dstDesc.getType(), + hrn.getID(), hrn + .getGloballyUniqueIdentifier(), 1)); + if(strongUpdate){ + effectsSet.addStrongUpdateVar(paramID, new EffectsKey( + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); + } + } + } + + } + + } + } + + } public void analyzeFlatSetFieldNode(OwnershipGraph og, TempDescriptor dstDesc, FieldDescriptor fieldDesc) { @@ -112,13 +234,9 @@ public class MethodEffects { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); -// effectsSet.addWritingVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); if(strongUpdate){ effectsSet.addStrongUpdateVar(paramID, new EffectsKey( fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); -// effectsSet.addStrongUpdateVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } } @@ -135,13 +253,9 @@ public class MethodEffects { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); -// effectsSet.addWritingVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); if(strongUpdate){ effectsSet.addStrongUpdateVar(paramID, new EffectsKey( fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); -// effectsSet.addStrongUpdateVar(paramID, new EffectsKey( -// fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodEffectsAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/MethodEffectsAnalysis.java index 51c77aa3..1dc3f20a 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/MethodEffectsAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodEffectsAnalysis.java @@ -9,7 +9,9 @@ import java.util.Set; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.TypeDescriptor; import IR.Flat.FlatCall; +import IR.Flat.FlatSetElementNode; import IR.Flat.TempDescriptor; public class MethodEffectsAnalysis { @@ -59,12 +61,29 @@ public class MethodEffectsAnalysis { me.analyzeFlatSetFieldNode(og, dstDesc, fieldDesc); mapMethodContextToMethodEffects.put(mc, me); } + + public void analyzeFlatSetElementNode(MethodContext mc, OwnershipGraph og, + TempDescriptor dstDesc, FieldDescriptor fieldDesc) { + if(!methodeffects) return; + MethodEffects me = mapMethodContextToMethodEffects.get(mc); + me.analyzeFlatSetElementNode(og, dstDesc, fieldDesc); + mapMethodContextToMethodEffects.put(mc, me); + } + + public void analyzeFlatElementNode(MethodContext mc, OwnershipGraph og, + TempDescriptor dstDesc, FieldDescriptor fieldDesc) { + if(!methodeffects) return; + MethodEffects me = mapMethodContextToMethodEffects.get(mc); + me.analyzeFlatElementNode(og, dstDesc, fieldDesc); + mapMethodContextToMethodEffects.put(mc, me); + } + public void writeMethodEffectsResult() throws IOException { try { BufferedWriter bw = new BufferedWriter(new FileWriter( - "MethodEffects_resport.txt")); + "MethodEffects_report.txt")); Set mcSet = mapMethodContextToMethodEffects.keySet(); Iterator mcIter = mcSet.iterator(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index f3606325..56a78ad9 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -939,6 +939,7 @@ public class OwnershipAnalysis { case FKind.FlatElementNode: FlatElementNode fen = (FlatElementNode) fn; + lhs = fen.getDst(); rhs = fen.getSrc(); if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { @@ -948,13 +949,22 @@ public class OwnershipAnalysis { TypeDescriptor tdElement = rhs.getType().dereference(); FieldDescriptor fdElement = getArrayField( tdElement ); - og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement); + meAnalysis.analyzeFlatElementNode(mc, og, lhs, fdElement); + } break; case FKind.FlatSetElementNode: FlatSetElementNode fsen = (FlatSetElementNode) fn; + + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { + TypeDescriptor tdElement = lhs.getType().dereference(); + FieldDescriptor fdElement = getArrayField( tdElement ); + meAnalysis.analyzeFlatSetElementNode(mc, og, lhs, fdElement); + } if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) { // skip this node if it cannot create new reachability paths @@ -972,6 +982,8 @@ public class OwnershipAnalysis { FieldDescriptor fdElement = getArrayField( tdElement ); og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs); + meAnalysis.analyzeFlatSetElementNode(mc, og, lhs, fdElement); + } break; -- 2.34.1