From c8b620e0d0bd272333397e327c4f0f4d0bc085b7 Mon Sep 17 00:00:00 2001 From: yeom Date: Thu, 21 Jan 2010 06:38:35 +0000 Subject: [PATCH] bug fix, converting method effects into sese effects. --- Robust/src/Analysis/MLP/ConflictGraph.java | 33 ++++- Robust/src/Analysis/MLP/MLPAnalysis.java | 94 ++++++++++++--- Robust/src/Analysis/MLP/SESEEffectsKey.java | 9 ++ Robust/src/Analysis/MLP/WaitingElement.java | 44 +++++++ .../OwnershipAnalysis/EffectsKey.java | 8 +- .../OwnershipAnalysis/MethodEffects.java | 113 ++++++++++++++++-- 6 files changed, 270 insertions(+), 31 deletions(-) diff --git a/Robust/src/Analysis/MLP/ConflictGraph.java b/Robust/src/Analysis/MLP/ConflictGraph.java index 4b6497ea..3c289010 100644 --- a/Robust/src/Analysis/MLP/ConflictGraph.java +++ b/Robust/src/Analysis/MLP/ConflictGraph.java @@ -458,6 +458,17 @@ public class ConflictGraph { Set readEffectsSetB = nodeB.getReadEffectsSet(); Set writeEffectsSetB = nodeB.getWriteEffectsSet(); Set strongUpdateSetB = nodeB.getStrongUpdateSet(); + /* + System.out.println("nodeA="+nodeA); + System.out.println("readEffectsSetA="+readEffectsSetA); + System.out.println("writeEffectsSetA="+writeEffectsSetA); + System.out.println("strongUpdateSetA="+strongUpdateSetA); + System.out.println("nodeB="+nodeB); + System.out.println("readEffectsSetB="+readEffectsSetB); + System.out.println("writeEffectsSetB="+writeEffectsSetB); + System.out.println("strongUpdateSetB="+strongUpdateSetB); + System.out.println("--"); + */ // if node A has write effects on reading/writing regions of node B if (writeEffectsSetA != null) { @@ -466,7 +477,7 @@ public class ConflictGraph { SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterA .next(); - if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetA)) { +// if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetA)) { String writeHeapRegionID = seseEffectsKey.getHRNUniqueId(); String writeFieldName = seseEffectsKey.getFieldDescriptor(); @@ -503,7 +514,7 @@ public class ConflictGraph { } } - } +// } // end of if(hasStrong) } } @@ -515,7 +526,7 @@ public class ConflictGraph { SESEEffectsKey seseEffectsKey = (SESEEffectsKey) writeIterB .next(); - if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetB)) { + //if (!hasStrongUpdate(seseEffectsKey, strongUpdateSetB)) { String writeHeapRegionID = seseEffectsKey.getHRNUniqueId(); String writeFieldName = seseEffectsKey.getFieldDescriptor(); @@ -549,7 +560,7 @@ public class ConflictGraph { } } } - } + //} // if(hasStrong) } } @@ -573,8 +584,13 @@ public class ConflictGraph { if (hasStrongUpdate(writeEffect, strongUpdateSet)) { strongUpdateCount++; } + + if(writeEffect.isStrong()){ + return false; + } } + if (liveInNode.getWriteEffectsSet().size() == strongUpdateCount) { return false; }else{ @@ -1022,7 +1038,12 @@ public class ConflictGraph { newElement.setAllocList(allocSet); newElement.setWaitingID(seseLock.getID()); newElement.setStatus(type); - waitingElementSet.add(newElement); + if(!waitingElementSet.contains(newElement)){ + waitingElementSet.add(newElement); + }else{ + } + + } } } @@ -1152,6 +1173,8 @@ public class ConflictGraph { // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier()); if (hrn.getAllocationSite() != null) { returnSet.add(new Integer(hrn.getAllocationSite().getID())); + }else{ + returnSet.add(new Integer(hrn.getID())); } } } diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 44629657..cb7e7fb1 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -1196,6 +1196,13 @@ 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 @@ -1461,13 +1468,22 @@ public class MLPAnalysis { TempDescriptor src=fon.getLeft(); // if(!currentSESE.getIsCallerSESEplaceholder()){ - if( fon.getOp().getOp() ==Operation.ASSIGN && currentSESE.getInVarSet().contains(src)){ + if( fon.getOp().getOp() ==Operation.ASSIGN && ( currentSESE.getInVarSet().contains(src) || (currentSESE.getOutVarSet().contains(src)))){ invarMap.put(dest, src); } // } }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; @@ -1487,7 +1503,18 @@ public class MLPAnalysis { if(invarMap.containsKey(dst)){ TempDescriptor invarTD=invarMap.get(dst); - currentSESE.getSeseEffectsSet().addWritingVar(invarTD, new SESEEffectsKey("", dst.getType(), new Integer(0), "")); + + 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), "")); + } + ///// + } }break; @@ -1635,31 +1662,55 @@ public class MLPAnalysis { MethodEffects me = ownAnalysis.getMethodEffectsAnalysis() .getMethodEffectsByMethodContext(calleeMC); + OwnershipGraph calleeOG = ownAnalysis .getOwnvershipGraphByMethodContext(calleeMC); + FlatMethod fm = state.getMethodFlat(fc.getMethod()); ParameterDecomposition decomp = new ParameterDecomposition( ownAnalysis, fc, fm, calleeMC, calleeOG, og); - int base; + int base=0; if (((MethodDescriptor) calleeMC.getDescriptor()).isStatic()) { base = 0; } else { base = 1; } - for (int i = 0; i < fc.numArgs(); i++) { - - TempDescriptor arg = fc.getArg(i); - Set readSet = me.getEffects().getReadingSet( - i + base); - Set writeSet = me.getEffects().getWritingSet( - i + base); - - Set strongUpdateSet = me.getEffects() - .getStrongUpdateSet(i + base); + for (int i = 0; i < fc.numArgs()+base; i++) { + + TempDescriptor arg ; + Set readSet; + Set writeSet; + Set strongUpdateSet; + + int paramIdx=0; + + boolean isThis=false; + if(i==fc.numArgs()){ + paramIdx=0; + arg = fc.getThis(); + Integer hrnPrimaryID = calleeOG.paramIndex2idPrimary.get(paramIdx); + Integer hrnSecondaryID = calleeOG.paramIndex2idSecondary.get(paramIdx); + readSet = me.getEffects().getReadingSet( + 0); + writeSet = me.getEffects().getWritingSet( + 0); + strongUpdateSet = me.getEffects() + .getStrongUpdateSet(0); + isThis=true; + }else{ + paramIdx=i + base; + arg = fc.getArg(i); + readSet = me.getEffects().getReadingSet( + i + base); + writeSet = me.getEffects().getWritingSet( + i + base); + strongUpdateSet = me.getEffects() + .getStrongUpdateSet(i + base); + } LabelNode argLN = og.td2ln.get(arg); if (argLN != null) { @@ -1670,6 +1721,14 @@ public class MLPAnalysis { 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) { @@ -1678,7 +1737,7 @@ public class MLPAnalysis { while (readIter.hasNext()) { EffectsKey key = readIter.next(); Set hrnSet = getCallerHRNId( - new Integer(i + base), calleeOG, + new Integer(paramIdx), calleeOG, key.getHRNId(), decomp); Iterator hrnIter = hrnSet .iterator(); @@ -1692,6 +1751,7 @@ public class MLPAnalysis { currentSESE.readEffects(affectedTD, key .getFieldDescriptor(), key .getTypeDescriptor(), refHRN); + } } } @@ -1703,7 +1763,7 @@ public class MLPAnalysis { EffectsKey key = writeIter.next(); Set hrnSet = getCallerHRNId( - new Integer(i + base), calleeOG, + new Integer(paramIdx), calleeOG, key.getHRNId(), decomp); Iterator hrnIter = hrnSet .iterator(); @@ -1729,7 +1789,7 @@ public class MLPAnalysis { EffectsKey key = strongUpdateIter.next(); Set hrnSet = getCallerHRNId( - new Integer(i + base), calleeOG, + new Integer(paramIdx), calleeOG, key.getHRNId(), decomp); Iterator hrnIter = hrnSet .iterator(); @@ -2256,6 +2316,7 @@ public class MLPAnalysis { .getOwnvershipGraphByMethodContext(mc); LabelNode ln = lastOG.td2ln.get(tempDescriptor); + Set hrnSet = new HashSet(); Iterator refIter = ln .iteratorToReferencees(); @@ -2269,6 +2330,7 @@ public class MLPAnalysis { readEffectsSet, writeEffectsSet, strongUpdateSet, reachabilitySet); } + if(conflictGraph.id2cn.size()>0){ conflictGraphResults.put(seseSummary.getCurrentParent(),conflictGraph); } diff --git a/Robust/src/Analysis/MLP/SESEEffectsKey.java b/Robust/src/Analysis/MLP/SESEEffectsKey.java index 01844465..dc824900 100644 --- a/Robust/src/Analysis/MLP/SESEEffectsKey.java +++ b/Robust/src/Analysis/MLP/SESEEffectsKey.java @@ -8,6 +8,7 @@ public class SESEEffectsKey { private TypeDescriptor td; private Integer hrnId; private String hrnUniqueId; + private boolean wStrong=false; public SESEEffectsKey(String fd, TypeDescriptor td, Integer hrnId, String hrnUniqueId) { this.fd = fd; @@ -15,6 +16,14 @@ public class SESEEffectsKey { this.hrnId = hrnId; this.hrnUniqueId=hrnUniqueId; } + + public void setStrong(boolean wStrong){ + this.wStrong=wStrong; + } + + public boolean isStrong(){ + return wStrong; + } public String getFieldDescriptor() { return fd; diff --git a/Robust/src/Analysis/MLP/WaitingElement.java b/Robust/src/Analysis/MLP/WaitingElement.java index ccaf4fa2..33606cf5 100644 --- a/Robust/src/Analysis/MLP/WaitingElement.java +++ b/Robust/src/Analysis/MLP/WaitingElement.java @@ -1,6 +1,7 @@ package Analysis.MLP; import java.util.HashSet; +import java.util.Iterator; public class WaitingElement { @@ -36,4 +37,47 @@ public class WaitingElement { this.allocList.addAll(allocList); } + public boolean equals(Object o) { + + if (o == null) { + return false; + } + + if (!(o instanceof WaitingElement)) { + return false; + } + + WaitingElement in = (WaitingElement) o; + + if (waitingID == in.getWaitingID() && status == in.getStatus() + && allocList.equals(in.getAllocList())) { + return true; + } else { + return false; + } + + } + + public String toString() { + return "[waitingID=" + waitingID + " status=" + status + " allocList=" + + allocList + "]"; + } + + public int hashCode() { + + int hash = 1; + + hash = hash * 31 + waitingID; + + hash += status; + + for (Iterator iterator = allocList.iterator(); iterator.hasNext();) { + Integer type = (Integer) iterator.next(); + hash += type.intValue(); + } + + return hash; + + } + } \ No newline at end of file diff --git a/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java b/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java index 9a2b97ee..632f11b4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java +++ b/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java @@ -8,12 +8,18 @@ public class EffectsKey { private TypeDescriptor td; private Integer hrnId; private String hrnUniqueId; + private int paramIden; - public EffectsKey(String fd, TypeDescriptor td, Integer hrnId, String hrnUniqueId) { + public EffectsKey(String fd, TypeDescriptor td, Integer hrnId, String hrnUniqueId, int paramIden) { this.fd = fd; this.td = td; this.hrnId = hrnId; this.hrnUniqueId=hrnUniqueId; + this.paramIden=paramIden; + } + + public int getParamIden(){ + return paramIden; } public String getFieldDescriptor() { diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java index e84fc8c6..ece3a5bf 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java @@ -40,7 +40,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier())); + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); // effectsSet.addReadingVar(paramID, new EffectsKey( // fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); @@ -57,7 +57,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier())); + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); // effectsSet.addReadingVar(paramID, new EffectsKey( // fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); @@ -111,12 +111,12 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier())); + 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())); + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),0)); // effectsSet.addStrongUpdateVar(paramID, new EffectsKey( // fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } @@ -134,12 +134,12 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier())); + 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())); + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID(),hrn.getGloballyUniqueIdentifier(),1)); // effectsSet.addStrongUpdateVar(paramID, new EffectsKey( // fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } @@ -222,7 +222,39 @@ public class MethodEffects { Integer paramIdx = paramIter.next(); HashSet newSet = callee.getEffects().getReadTable() .get(calleeParamIdx); - effectsSet.addReadingEffectsSet(paramIdx, newSet); + + + if(newSet!=null){ + HashSet thisSet=new HashSet(); + HeapRegionNode priHRN=og.id2hrn.get(og.paramIndex2idPrimary.get(paramIdx)); + Integer secIdx=og.paramIndex2idSecondary.get(paramIdx); + HeapRegionNode secHRN=null; + if(secIdx!=null){ + secHRN=og.id2hrn.get(secIdx); + }else{ + secHRN=priHRN; + } + + for (Iterator iterator = newSet.iterator(); iterator.hasNext();) { + EffectsKey effectsKey = (EffectsKey) iterator.next(); + HeapRegionNode hrnTemp; + if(effectsKey.getParamIden()==0){//primary + hrnTemp=priHRN; + }else{//secondary + hrnTemp=secHRN; + } + EffectsKey newEffectsKey; + if(secIdx==null){ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),0); + }else{ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),effectsKey.getParamIden()); + } + thisSet.add(newEffectsKey); + } + + effectsSet.addReadingEffectsSet(paramIdx, thisSet); + } + } // handle write effects @@ -231,7 +263,39 @@ public class MethodEffects { Integer paramIdx = paramIter.next(); HashSet newSet = callee.getEffects() .getWriteTable().get(calleeParamIdx); - effectsSet.addWritingEffectsSet(paramIdx, newSet); + + if(newSet!=null){ + + HashSet thisSet=new HashSet(); + HeapRegionNode priHRN=og.id2hrn.get(og.paramIndex2idPrimary.get(paramIdx)); + Integer secIdx=og.paramIndex2idSecondary.get(paramIdx); + HeapRegionNode secHRN=null; + if(secIdx!=null){ + secHRN=og.id2hrn.get(secIdx); + }else{ + secHRN=priHRN; + } + + for (Iterator iterator = newSet.iterator(); iterator.hasNext();) { + EffectsKey effectsKey = (EffectsKey) iterator.next(); + HeapRegionNode hrnTemp; + if(effectsKey.getParamIden()==0){//primary + hrnTemp=priHRN; + }else{//secondary + hrnTemp=secHRN; + } + EffectsKey newEffectsKey; + if(secIdx==null){ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),0); + }else{ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),effectsKey.getParamIden()); + } + thisSet.add(newEffectsKey); + } + + effectsSet.addWritingEffectsSet(paramIdx, thisSet); + } + } // handle strong update effects @@ -240,7 +304,38 @@ public class MethodEffects { Integer paramIdx = paramIter.next(); HashSet newSet = callee.getEffects() .getStrongUpdateTable().get(calleeParamIdx); - effectsSet.addStrongUpdateEffectsSet(paramIdx, newSet); + if(newSet!=null){ + + HashSet thisSet=new HashSet(); + HeapRegionNode priHRN=og.id2hrn.get(og.paramIndex2idPrimary.get(paramIdx)); + Integer secIdx=og.paramIndex2idSecondary.get(paramIdx); + HeapRegionNode secHRN=null; + if(secIdx!=null){ + secHRN=og.id2hrn.get(secIdx); + }else{ + secHRN=priHRN; + } + + for (Iterator iterator = newSet.iterator(); iterator.hasNext();) { + EffectsKey effectsKey = (EffectsKey) iterator.next(); + HeapRegionNode hrnTemp; + if(effectsKey.getParamIden()==0){//primary + hrnTemp=priHRN; + }else{//secondary + hrnTemp=secHRN; + } + EffectsKey newEffectsKey; + if(secIdx==null){ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),0); + }else{ + newEffectsKey=new EffectsKey(effectsKey.getFieldDescriptor(), effectsKey.getTypeDescriptor(), hrnTemp.getID(),hrnTemp.getGloballyUniqueIdentifier(),effectsKey.getParamIden()); + } + thisSet.add(newEffectsKey); + } + + effectsSet.addStrongUpdateEffectsSet(paramIdx, thisSet); + } + } } -- 2.34.1