X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FOwnershipAnalysis%2FOwnershipGraph.java;h=5b7dc3cf8c1b1edf696114e9263d4c836f16ec1f;hb=b1053795b767f4152e4cf51b8b091d5e3f1d6249;hp=fce6f0d0be3785848fa34ccf3cc2514823c5e2f0;hpb=84e434cf05530d0b929a849e5c54da93d595381a;p=IRC.git diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index fce6f0d0..5b7dc3cf 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -17,29 +17,78 @@ public class OwnershipGraph { // actions to take during the traversal protected static final int VISIT_HRN_WRITE_FULL = 0; - protected static TempDescriptor tdReturn = new TempDescriptor("_Return___"); + protected static final String qString = new String( "Q_spec_" ); + protected static final String rString = new String( "R_spec_" ); + protected static final String blobString = new String( "_AliasBlob___" ); + + protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" ); + protected static final TempDescriptor tdAliasBlob = new TempDescriptor( blobString ); + + protected static final TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); + protected static final ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical(); + protected static final ReachabilitySet rsWttsEmpty = new ReachabilitySet( ttsEmpty ).makeCanonical(); + + // add a bogus entry with the identity rule for easy rewrite + // of new callee nodes and edges, doesn't belong to any parameter + protected static final int bogusParamIndexInt = -2; + protected static final Integer bogusID = new Integer( bogusParamIndexInt ); + protected static final Integer bogusIndex = new Integer( bogusParamIndexInt ); + protected static final TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE ).makeCanonical(); + protected static final TokenTuple bogusTokenPlus = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONEORMORE ).makeCanonical(); + protected static final TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_ZEROORMORE ).makeCanonical(); + protected static final ReachabilitySet rsIdentity = + new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical(); public Hashtable id2hrn; public Hashtable td2ln; - public Hashtable id2paramIndex; - public Hashtable paramIndex2id; + + public Hashtable > idPrimary2paramIndexSet; + public Hashtable paramIndex2idPrimary; + + public Hashtable > idSecondary2paramIndexSet; + public Hashtable paramIndex2idSecondary; + public Hashtable paramIndex2tdQ; + public Hashtable paramIndex2tdR; + public HashSet allocationSites; + public Hashtable paramTokenPrimary2paramIndex; + public Hashtable paramIndex2paramTokenPrimary; + + public Hashtable paramTokenSecondary2paramIndex; + public Hashtable paramIndex2paramTokenSecondary; + public Hashtable paramTokenSecondaryPlus2paramIndex; + public Hashtable paramIndex2paramTokenSecondaryPlus; + public Hashtable paramTokenSecondaryStar2paramIndex; + public Hashtable paramIndex2paramTokenSecondaryStar; public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) { this.allocationDepth = allocationDepth; this.typeUtil = typeUtil; - id2hrn = new Hashtable(); - td2ln = new Hashtable(); - id2paramIndex = new Hashtable(); - paramIndex2id = new Hashtable(); - paramIndex2tdQ = new Hashtable(); + id2hrn = new Hashtable(); + td2ln = new Hashtable(); + idPrimary2paramIndexSet = new Hashtable >(); + paramIndex2idPrimary = new Hashtable(); + idSecondary2paramIndexSet = new Hashtable >(); + paramIndex2idSecondary = new Hashtable(); + paramIndex2tdQ = new Hashtable(); + paramIndex2tdR = new Hashtable(); + + paramTokenPrimary2paramIndex = new Hashtable(); + paramIndex2paramTokenPrimary = new Hashtable(); + + paramTokenSecondary2paramIndex = new Hashtable(); + paramIndex2paramTokenSecondary = new Hashtable(); + paramTokenSecondaryPlus2paramIndex = new Hashtable(); + paramIndex2paramTokenSecondaryPlus = new Hashtable(); + paramTokenSecondaryStar2paramIndex = new Hashtable(); + paramIndex2paramTokenSecondaryStar = new Hashtable(); allocationSites = new HashSet (); } @@ -71,33 +120,52 @@ public class OwnershipGraph { protected HeapRegionNode createNewHeapRegionNode(Integer id, boolean isSingleObject, - boolean isFlagged, boolean isNewSummary, + boolean isFlagged, boolean isParameter, + TypeDescriptor type, AllocationSite allocSite, ReachabilitySet alpha, String description) { + boolean markForAnalysis = isFlagged || isParameter; + + TypeDescriptor typeToUse = null; + if( allocSite != null ) { + typeToUse = allocSite.getType(); + } else { + typeToUse = type; + } + + if( allocSite != null && allocSite.getDisjointId() != null ) { + markForAnalysis = true; + } + if( id == null ) { id = OwnershipAnalysis.generateUniqueHeapRegionNodeID(); } if( alpha == null ) { - if( isFlagged || isParameter ) { - alpha = new ReachabilitySet(new TokenTuple(id, - !isSingleObject, - TokenTuple.ARITY_ONE) - ).makeCanonical(); + if( markForAnalysis ) { + alpha = new ReachabilitySet( + new TokenTuple(id, + !isSingleObject, + TokenTuple.ARITY_ONE + ).makeCanonical() + ).makeCanonical(); } else { - alpha = new ReachabilitySet(new TokenTupleSet() - ).makeCanonical(); + alpha = new ReachabilitySet( + new TokenTupleSet().makeCanonical() + ).makeCanonical(); } } HeapRegionNode hrn = new HeapRegionNode(id, isSingleObject, - isFlagged, + markForAnalysis, + isParameter, isNewSummary, + typeToUse, allocSite, alpha, description); @@ -132,22 +200,31 @@ public class OwnershipGraph { protected void removeReferenceEdge(OwnershipNode referencer, HeapRegionNode referencee, - FieldDescriptor fieldDesc) { + TypeDescriptor type, + String field) { assert referencer != null; assert referencee != null; - + ReferenceEdge edge = referencer.getReferenceTo(referencee, - fieldDesc); + type, + field); assert edge != null; assert edge == referencee.getReferenceFrom(referencer, - fieldDesc); + type, + field); + +// int oldTaint=edge.getTaintIdentifier(); +// if(referencer instanceof HeapRegionNode){ +// depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet()); +// } referencer.removeReferencee(edge); referencee.removeReferencer(edge); } protected void clearReferenceEdgesFrom(OwnershipNode referencer, - FieldDescriptor fieldDesc, + TypeDescriptor type, + String field, boolean removeAll) { assert referencer != null; @@ -158,18 +235,23 @@ public class OwnershipGraph { while( i.hasNext() ) { ReferenceEdge edge = i.next(); - if( removeAll || edge.getFieldDesc() == fieldDesc ) { - HeapRegionNode referencee = edge.getDst(); + if( removeAll || + (edge.typeEquals( type ) && edge.fieldEquals( field )) + ){ + HeapRegionNode referencee = edge.getDst(); + removeReferenceEdge(referencer, referencee, - edge.getFieldDesc() ); + edge.getType(), + edge.getField() ); } } } protected void clearReferenceEdgesTo(HeapRegionNode referencee, - FieldDescriptor fieldDesc, + TypeDescriptor type, + String field, boolean removeAll) { assert referencee != null; @@ -180,149 +262,16 @@ public class OwnershipGraph { while( i.hasNext() ) { ReferenceEdge edge = i.next(); - if( removeAll || edge.getFieldDesc() == fieldDesc ) { + if( removeAll || + (edge.typeEquals( type ) && edge.fieldEquals( field )) + ){ + OwnershipNode referencer = edge.getSrc(); + removeReferenceEdge(referencer, referencee, - edge.getFieldDesc() ); - } - } - } - - - protected void propagateTokensOverNodes(HeapRegionNode nPrime, - ChangeTupleSet c0, - HashSet nodesWithNewAlpha, - HashSet edgesWithNewBeta) { - - HashSet todoNodes - = new HashSet(); - todoNodes.add(nPrime); - - HashSet todoEdges - = new HashSet(); - - Hashtable nodePlannedChanges - = new Hashtable(); - nodePlannedChanges.put(nPrime, c0); - - Hashtable edgePlannedChanges - = new Hashtable(); - - - while( !todoNodes.isEmpty() ) { - HeapRegionNode n = todoNodes.iterator().next(); - ChangeTupleSet C = nodePlannedChanges.get(n); - - Iterator itrC = C.iterator(); - while( itrC.hasNext() ) { - ChangeTuple c = (ChangeTuple) itrC.next(); - - if( n.getAlpha().contains(c.getSetToMatch() ) ) { - ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() ); - n.setAlphaNew(n.getAlphaNew().union(withChange) ); - nodesWithNewAlpha.add(n); - } - } - - Iterator referItr = n.iteratorToReferencers(); - while( referItr.hasNext() ) { - ReferenceEdge edge = referItr.next(); - todoEdges.add(edge); - - if( !edgePlannedChanges.containsKey(edge) ) { - edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() ); - } - - edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) ); - } - - Iterator refeeItr = n.iteratorToReferencees(); - while( refeeItr.hasNext() ) { - ReferenceEdge edgeF = refeeItr.next(); - HeapRegionNode m = edgeF.getDst(); - - ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); - - Iterator itrCprime = C.iterator(); - while( itrCprime.hasNext() ) { - ChangeTuple c = itrCprime.next(); - if( edgeF.getBeta().contains(c.getSetToMatch() ) ) { - changesToPass = changesToPass.union(c); - } - } - - if( !changesToPass.isEmpty() ) { - if( !nodePlannedChanges.containsKey(m) ) { - nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() ); - } - - ChangeTupleSet currentChanges = nodePlannedChanges.get(m); - - if( !changesToPass.isSubset(currentChanges) ) { - - nodePlannedChanges.put(m, currentChanges.union(changesToPass) ); - todoNodes.add(m); - } - } - } - - todoNodes.remove(n); - } - - propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta); - } - - - protected void propagateTokensOverEdges( - HashSet todoEdges, - Hashtable edgePlannedChanges, - HashSet edgesWithNewBeta) { - - - while( !todoEdges.isEmpty() ) { - ReferenceEdge edgeE = todoEdges.iterator().next(); - todoEdges.remove(edgeE); - - if( !edgePlannedChanges.containsKey(edgeE) ) { - edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() ); - } - - ChangeTupleSet C = edgePlannedChanges.get(edgeE); - - ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); - - Iterator itrC = C.iterator(); - while( itrC.hasNext() ) { - ChangeTuple c = itrC.next(); - if( edgeE.getBeta().contains(c.getSetToMatch() ) ) { - ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() ); - edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) ); - edgesWithNewBeta.add(edgeE); - changesToPass = changesToPass.union(c); - } - } - - OwnershipNode onSrc = edgeE.getSrc(); - - if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) { - HeapRegionNode n = (HeapRegionNode) onSrc; - - Iterator referItr = n.iteratorToReferencers(); - while( referItr.hasNext() ) { - ReferenceEdge edgeF = referItr.next(); - - if( !edgePlannedChanges.containsKey(edgeF) ) { - edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() ); - } - - ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF); - - if( !changesToPass.isSubset(currentChanges) ) { - todoEdges.add(edgeF); - edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) ); - } - } + edge.getType(), + edge.getField() ); } } } @@ -350,13 +299,13 @@ public class OwnershipGraph { LabelNode lnX = getLabelNodeFromTemp(x); LabelNode lnY = getLabelNodeFromTemp(y); - clearReferenceEdgesFrom(lnX, null, true); + clearReferenceEdgesFrom(lnX, null, null, true); Iterator itrYhrn = lnY.iteratorToReferencees(); while( itrYhrn.hasNext() ) { - ReferenceEdge edgeY = itrYhrn.next(); + ReferenceEdge edgeY = itrYhrn.next(); HeapRegionNode referencee = edgeY.getDst(); - ReferenceEdge edgeNew = edgeY.copy(); + ReferenceEdge edgeNew = edgeY.copy(); edgeNew.setSrc(lnX); addReferenceEdge(lnX, referencee, edgeNew); @@ -364,34 +313,63 @@ public class OwnershipGraph { } + public void assignTypedTempXEqualToTempY(TempDescriptor x, + TempDescriptor y, + TypeDescriptor type) { + + LabelNode lnX = getLabelNodeFromTemp(x); + LabelNode lnY = getLabelNodeFromTemp(y); + + clearReferenceEdgesFrom(lnX, null, null, true); + + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode referencee = edgeY.getDst(); + ReferenceEdge edgeNew = edgeY.copy(); + edgeNew.setSrc( lnX ); + edgeNew.setType( type ); + edgeNew.setField( null ); + + addReferenceEdge(lnX, referencee, edgeNew); + } + } + + public void assignTempXEqualToTempYFieldF(TempDescriptor x, TempDescriptor y, FieldDescriptor f) { LabelNode lnX = getLabelNodeFromTemp(x); LabelNode lnY = getLabelNodeFromTemp(y); - clearReferenceEdgesFrom(lnX, null, true); + clearReferenceEdgesFrom(lnX, null, null, true); Iterator itrYhrn = lnY.iteratorToReferencees(); while( itrYhrn.hasNext() ) { - ReferenceEdge edgeY = itrYhrn.next(); - HeapRegionNode hrnY = edgeY.getDst(); + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode hrnY = edgeY.getDst(); ReachabilitySet betaY = edgeY.getBeta(); Iterator itrHrnFhrn = hrnY.iteratorToReferencees(); while( itrHrnFhrn.hasNext() ) { - ReferenceEdge edgeHrn = itrHrnFhrn.next(); - HeapRegionNode hrnHrn = edgeHrn.getDst(); + ReferenceEdge edgeHrn = itrHrnFhrn.next(); + HeapRegionNode hrnHrn = edgeHrn.getDst(); ReachabilitySet betaHrn = edgeHrn.getBeta(); - if( edgeHrn.getFieldDesc() == null || - edgeHrn.getFieldDesc() == f ) { + if( edgeHrn.getType() == null || + (edgeHrn.getType() .equals( f.getType() ) && + edgeHrn.getField().equals( f.getSymbol() ) ) + ) { ReferenceEdge edgeNew = new ReferenceEdge(lnX, hrnHrn, - f, + f.getType(), + null, false, betaY.intersection(betaHrn) ); + + int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn); + edgeNew.setTaintIdentifier(newTaintIdentifier); addReferenceEdge(lnX, hrnHrn, edgeNew); } @@ -409,10 +387,31 @@ public class OwnershipGraph { HashSet nodesWithNewAlpha = new HashSet(); HashSet edgesWithNewBeta = new HashSet(); + // first look for possible strong updates and remove those edges + boolean strongUpdate = false; + Iterator itrXhrn = lnX.iteratorToReferencees(); while( itrXhrn.hasNext() ) { ReferenceEdge edgeX = itrXhrn.next(); - HeapRegionNode hrnX = edgeX.getDst(); + HeapRegionNode hrnX = edgeX.getDst(); + + // we can do a strong update here if one of two cases holds + if( f != null && + f != OwnershipAnalysis.getArrayField( f.getType() ) && + ( (hrnX.getNumReferencers() == 1) || // case 1 + (hrnX.isSingleObject() && lnX.getNumReferencees() == 1) // case 2 + ) + ) { + strongUpdate = true; + clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false ); + } + } + + // then do all token propagation + itrXhrn = lnX.iteratorToReferencees(); + while( itrXhrn.hasNext() ) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); ReachabilitySet betaX = edgeX.getBeta(); ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() ); @@ -420,8 +419,8 @@ public class OwnershipGraph { Iterator itrYhrn = lnY.iteratorToReferencees(); while( itrYhrn.hasNext() ) { ReferenceEdge edgeY = itrYhrn.next(); - HeapRegionNode hrnY = edgeY.getDst(); - ReachabilitySet O = edgeY.getBeta(); + HeapRegionNode hrnY = edgeY.getDst(); + ReachabilitySet O = edgeY.getBeta(); // propagate tokens over nodes starting from hrnSrc, and it will @@ -432,8 +431,7 @@ public class OwnershipGraph { // then propagate back just up the edges from hrn ChangeTupleSet Cx = R.unionUpArityToChangeSet(O); - - HashSet todoEdges = new HashSet(); + HashSet todoEdges = new HashSet(); Hashtable edgePlannedChanges = new Hashtable(); @@ -448,168 +446,761 @@ public class OwnershipGraph { propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta); + } + } + // apply the updates to reachability + Iterator nodeItr = nodesWithNewAlpha.iterator(); + while( nodeItr.hasNext() ) { + nodeItr.next().applyAlphaNew(); + } + + Iterator edgeItr = edgesWithNewBeta.iterator(); + while( edgeItr.hasNext() ) { + edgeItr.next().applyBetaNew(); + } + + + // then go back through and add the new edges + itrXhrn = lnX.iteratorToReferencees(); + while( itrXhrn.hasNext() ) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); - //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() ); + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode hrnY = edgeY.getDst(); - // create the actual reference edge hrnX.f -> hrnY + // prepare the new reference edge hrnX.f -> hrnY ReferenceEdge edgeNew = new ReferenceEdge(hrnX, hrnY, - f, + f.getType(), + f.getSymbol(), false, - edgeY.getBetaNew().pruneBy(hrnX.getAlpha() ) - //edgeY.getBeta().pruneBy( hrnX.getAlpha() ) + edgeY.getBeta().pruneBy( hrnX.getAlpha() ) ); - addReferenceEdge(hrnX, hrnY, edgeNew); - - /* - if( f != null ) { - // we can do a strong update here if one of two cases holds - // SAVE FOR LATER, WITHOUT STILL CORRECT - if( (hrnX.getNumReferencers() == 1) || - ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() ) - ) { - clearReferenceEdgesFrom( hrnX, f, false ); - } - addReferenceEdge( hrnX, hrnY, edgeNew ); + // look to see if an edge with same field exists + // and merge with it, otherwise just add the edge + ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, + f.getType(), + f.getSymbol() ); + + if( edgeExisting != null ) { + edgeExisting.setBeta( + edgeExisting.getBeta().union( edgeNew.getBeta() ) + ); + if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){ + int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY); + edgeExisting.unionTaintIdentifier(newTaintIdentifier); + } + // a new edge here cannot be reflexive, so existing will + // always be also not reflexive anymore + edgeExisting.setIsInitialParam( false ); + } else { + + if((!hrnX.isParameter() && hrnY.isParameter()) || ( hrnX.isParameter() && hrnY.isParameter())){ + int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY); + edgeNew.setTaintIdentifier(newTaintIdentifier); + } + //currently, taint isn't propagated through the chain of refrences + //propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet()); + addReferenceEdge( hrnX, hrnY, edgeNew ); + } + } + } + + // if there was a strong update, make sure to improve + // reachability with a global sweep + if( strongUpdate ) { + globalSweep(); + } + } - } else { - // if the field is null, or "any" field, then - // look to see if an any field already exists - // and merge with it, otherwise just add the edge - ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f ); - if( edgeExisting != null ) { - edgeExisting.setBetaNew( - edgeExisting.getBetaNew().union( edgeNew.getBeta() ) - ); - // a new edge here cannot be reflexive, so existing will - // always be also not reflexive anymore - edgeExisting.setIsInitialParamReflexive( false ); - } else { - addReferenceEdge( hrnX, hrnY, edgeNew ); - } - } - */ + + // the parameter model is to use a single-object heap region + // for the primary parameter, and a multiple-object heap + // region for the secondary objects reachable through the + // primary object, if necessary + public void assignTempEqualToParamAlloc( TempDescriptor td, + boolean isTask, + Integer paramIndex ) { + assert td != null; + + TypeDescriptor typeParam = td.getType(); + assert typeParam != null; + + // either the parameter is an array or a class to be in this method + assert typeParam.isArray() || typeParam.isClass(); + + // discover some info from the param type and use it below + // to get parameter model as precise as we can + boolean createSecondaryRegion = false; + Set primary2primaryFields = new HashSet(); + Set primary2secondaryFields = new HashSet(); + + // there might be an element reference for array types + if( typeParam.isArray() ) { + // only bother with this if the dereferenced type can + // affect reachability + TypeDescriptor typeDeref = typeParam.dereference(); + if( !typeDeref.isImmutable() || typeDeref.isArray() ) { + primary2secondaryFields.add( + OwnershipAnalysis.getArrayField( typeDeref ) + ); + createSecondaryRegion = true; + + // also handle a special case where an array of objects + // can point back to the array, which is an object! + if( typeParam.toPrettyString().equals( "Object[]" ) && + typeDeref.toPrettyString().equals( "Object" ) ) { + + primary2primaryFields.add( + OwnershipAnalysis.getArrayField( typeDeref ) + ); + } } } - Iterator nodeItr = nodesWithNewAlpha.iterator(); - while( nodeItr.hasNext() ) { - nodeItr.next().applyAlphaNew(); - } + // there might be member references for class types + if( typeParam.isClass() ) { + ClassDescriptor cd = typeParam.getClassDesc(); + while( cd != null ) { + + Iterator fieldItr = cd.getFields(); + while( fieldItr.hasNext() ) { + + FieldDescriptor fd = (FieldDescriptor) fieldItr.next(); + TypeDescriptor typeField = fd.getType(); + assert typeField != null; + + if( !typeField.isImmutable() || typeField.isArray() ) { + primary2secondaryFields.add( fd ); + createSecondaryRegion = true; + } + + if( typeUtil.isSuperorType( typeField, typeParam ) ) { + primary2primaryFields.add( fd ); + } + } - Iterator edgeItr = edgesWithNewBeta.iterator(); - while( edgeItr.hasNext() ) { - edgeItr.next().applyBetaNew(); + cd = cd.getSuperDesc(); + } } - } - - public void assignTempEqualToParamAlloc(TempDescriptor td, - boolean isTask, - Integer paramIndex) { - assert td != null; - LabelNode lnParam = getLabelNodeFromTemp(td); - HeapRegionNode hrn = createNewHeapRegionNode(null, - false, - isTask, - false, - true, - null, - null, - "param" + paramIndex); + // now build everything we need + LabelNode lnParam = getLabelNodeFromTemp( td ); + HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one + true, // single object? + false, // summary? + false, // flagged? + true, // is a parameter? + typeParam, // type + null, // allocation site + null, // reachability set + "param"+paramIndex+" obj" ); // this is a non-program-accessible label that picks up beta // info to be used for fixing a caller of this method - TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ"); - LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ); + TempDescriptor tdParamQ = new TempDescriptor( td+qString ); + paramIndex2tdQ.put( paramIndex, tdParamQ ); + LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ ); // keep track of heap regions that were created for // parameter labels, the index of the parameter they // are for is important when resolving method calls - Integer newID = hrn.getID(); - assert !id2paramIndex.containsKey(newID); - assert !id2paramIndex.containsValue(paramIndex); - id2paramIndex.put(newID, paramIndex); - paramIndex2id.put(paramIndex, newID); - paramIndex2tdQ.put(paramIndex, tdParamQ); - - ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID, - true, - TokenTuple.ARITY_ONE) ); - - // heap regions for parameters are always multiple object (see above) - // and have a reference to themselves, because we can't know the - // structure of memory that is passed into the method. We're assuming - // the worst here. + Integer newPrimaryID = hrnPrimary.getID(); + assert !idPrimary2paramIndexSet.containsKey( newPrimaryID ); + Set s = new HashSet(); + s.add( paramIndex ); + idPrimary2paramIndexSet.put( newPrimaryID, s ); + paramIndex2idPrimary.put( paramIndex, newPrimaryID ); + + + TokenTuple ttPrimary = new TokenTuple( newPrimaryID, + false, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + + HeapRegionNode hrnSecondary = null; + Integer newSecondaryID = null; + TokenTuple ttSecondary = null; + TempDescriptor tdParamR = null; + LabelNode lnParamR = null; + + if( createSecondaryRegion ) { + tdParamR = new TempDescriptor( td+rString ); + paramIndex2tdR.put( paramIndex, tdParamR ); + lnParamR = getLabelNodeFromTemp( tdParamR ); + + hrnSecondary = createNewHeapRegionNode( null, // id or null to generate a new one + false, // single object? + false, // summary? + false, // flagged? + true, // is a parameter? + null, // type + null, // allocation site + null, // reachability set + "param"+paramIndex+" reachable" ); + + newSecondaryID = hrnSecondary.getID(); + assert !idSecondary2paramIndexSet.containsKey( newSecondaryID ); + Set s2 = new HashSet(); + s2.add( paramIndex ); + idSecondary2paramIndexSet.put( newSecondaryID, s2 ); + paramIndex2idSecondary.put( paramIndex, newSecondaryID ); + + + ttSecondary = new TokenTuple( newSecondaryID, + true, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + } + + // use a beta that has everything and put it all over the + // parameter model, then use a global sweep later to fix + // it up, since parameters can have different shapes + TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical(); + ReachabilitySet betaSoup; + if( createSecondaryRegion ) { + TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical(); + TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary ); + betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 ); + } else { + betaSoup = ReachabilitySet.factory( tts0 ); + } ReferenceEdge edgeFromLabel = - new ReferenceEdge(lnParam, hrn, null, false, beta); + new ReferenceEdge( lnParam, // src + hrnPrimary, // dst + typeParam, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabel.tainedBy(paramIndex); + addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel ); ReferenceEdge edgeFromLabelQ = - new ReferenceEdge(lnParamQ, hrn, null, false, beta); - - ReferenceEdge edgeReflexive = - new ReferenceEdge(hrn, hrn, null, true, beta); + new ReferenceEdge( lnParamQ, // src + hrnPrimary, // dst + null, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabelQ.tainedBy(paramIndex); + addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ ); + + ReferenceEdge edgeSecondaryReflexive; + if( createSecondaryRegion ) { + edgeSecondaryReflexive = + new ReferenceEdge( hrnSecondary, // src + hrnSecondary, // dst + null, // match all types + null, // match all fields + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive ); + + ReferenceEdge edgeSecondary2Primary = + new ReferenceEdge( hrnSecondary, // src + hrnPrimary, // dst + null, // match all types + null, // match all fields + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary ); + + ReferenceEdge edgeFromLabelR = + new ReferenceEdge( lnParamR, // src + hrnSecondary, // dst + null, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabelR.tainedBy(paramIndex); + addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR ); + } + + Iterator fieldItr = primary2primaryFields.iterator(); + while( fieldItr.hasNext() ) { + FieldDescriptor fd = fieldItr.next(); + + ReferenceEdge edgePrimaryReflexive = + new ReferenceEdge( hrnPrimary, // src + hrnPrimary, // dst + fd.getType(), // type + fd.getSymbol(), // field + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive ); + } - addReferenceEdge(lnParam, hrn, edgeFromLabel); - addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ); - addReferenceEdge(hrn, hrn, edgeReflexive); + fieldItr = primary2secondaryFields.iterator(); + while( fieldItr.hasNext() ) { + FieldDescriptor fd = fieldItr.next(); + + ReferenceEdge edgePrimary2Secondary = + new ReferenceEdge( hrnPrimary, // src + hrnSecondary, // dst + fd.getType(), // type + fd.getSymbol(), // field + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary ); + } } - public void assignReturnEqualToTemp(TempDescriptor x) { + public void makeAliasedParamHeapRegionNode() { + + LabelNode lnBlob = getLabelNodeFromTemp( tdAliasBlob ); + HeapRegionNode hrn = createNewHeapRegionNode( null, // id or null to generate a new one + false, // single object? + false, // summary? + false, // flagged? + true, // is a parameter? + null, // type + null, // allocation site + null, // reachability set + "aliasedParams" ); + + + ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(), + true, + TokenTuple.ARITY_ONE).makeCanonical() + ).makeCanonical(); + + ReferenceEdge edgeFromLabel = + new ReferenceEdge( lnBlob, hrn, null, null, false, beta ); - LabelNode lnR = getLabelNodeFromTemp(tdReturn); - LabelNode lnX = getLabelNodeFromTemp(x); + ReferenceEdge edgeReflexive = + new ReferenceEdge( hrn, hrn, null, null, true, beta ); + + addReferenceEdge( lnBlob, hrn, edgeFromLabel ); + addReferenceEdge( hrn, hrn, edgeReflexive ); + } - clearReferenceEdgesFrom(lnR, null, true); - Iterator itrXhrn = lnX.iteratorToReferencees(); - while( itrXhrn.hasNext() ) { - ReferenceEdge edgeX = itrXhrn.next(); - HeapRegionNode referencee = edgeX.getDst(); - ReferenceEdge edgeNew = edgeX.copy(); - edgeNew.setSrc(lnR); + public void assignTempEqualToAliasedParam( TempDescriptor tdParam, + Integer paramIndex ) { + assert tdParam != null; - addReferenceEdge(lnR, referencee, edgeNew); + TypeDescriptor typeParam = tdParam.getType(); + assert typeParam != null; + + LabelNode lnParam = getLabelNodeFromTemp( tdParam ); + LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob ); + + // this is a non-program-accessible label that picks up beta + // info to be used for fixing a caller of this method + TempDescriptor tdParamQ = new TempDescriptor( tdParam+qString ); + TempDescriptor tdParamR = new TempDescriptor( tdParam+rString ); + + paramIndex2tdQ.put( paramIndex, tdParamQ ); + paramIndex2tdR.put( paramIndex, tdParamR ); + + LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ ); + LabelNode lnParamR = getLabelNodeFromTemp( tdParamR ); + + // the lnAliased should always only reference one node, and that + // heap region node is the aliased param blob + assert lnAliased.getNumReferencees() == 1; + HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst(); + Integer idAliased = hrnAliasBlob.getID(); + + + TokenTuple ttAliased = new TokenTuple( idAliased, + true, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + + + HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one + true, // single object? + false, // summary? + false, // flagged? + true, // is a parameter? + typeParam, // type + null, // allocation site + null, // reachability set + "param"+paramIndex+" obj" ); + + Integer newPrimaryID = hrnPrimary.getID(); + assert !idPrimary2paramIndexSet.containsKey( newPrimaryID ); + Set s1 = new HashSet(); + s1.add( paramIndex ); + idPrimary2paramIndexSet.put( newPrimaryID, s1 ); + paramIndex2idPrimary.put( paramIndex, newPrimaryID ); + + Set s2 = idSecondary2paramIndexSet.get( idAliased ); + if( s2 == null ) { + s2 = new HashSet(); } - } + s2.add( paramIndex ); + idSecondary2paramIndexSet.put( idAliased, s2 ); + paramIndex2idSecondary.put( paramIndex, idAliased ); + + + TokenTuple ttPrimary = new TokenTuple( newPrimaryID, + false, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); - public void assignTempEqualToNewAlloc(TempDescriptor x, - AllocationSite as) { - assert x != null; - assert as != null; + + TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical(); + TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical(); + TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased ); + ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 ); - age(as); - // after the age operation the newest (or zero-ith oldest) - // node associated with the allocation site should have - // no references to it as if it were a newly allocated - // heap region, so make a reference to it to complete - // this operation + ReferenceEdge edgeFromLabel = + new ReferenceEdge( lnParam, // src + hrnPrimary, // dst + typeParam, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabel.tainedBy(paramIndex); + addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel ); - Integer idNewest = as.getIthOldest(0); - HeapRegionNode hrnNewest = id2hrn.get(idNewest); - assert hrnNewest != null; + ReferenceEdge edgeFromLabelQ = + new ReferenceEdge( lnParamQ, // src + hrnPrimary, // dst + null, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabelQ.tainedBy(paramIndex); + addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ ); + + ReferenceEdge edgeAliased2Primary = + new ReferenceEdge( hrnAliasBlob, // src + hrnPrimary, // dst + null, // match all types + null, // match all fields + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary ); + + ReferenceEdge edgeFromLabelR = + new ReferenceEdge( lnParamR, // src + hrnAliasBlob, // dst + null, // type + null, // field + false, // special param initial (not needed on label->node) + betaSoup ); // reachability + edgeFromLabelR.tainedBy(paramIndex); + addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR ); + } - LabelNode lnX = getLabelNodeFromTemp(x); - clearReferenceEdgesFrom(lnX, null, true); - ReferenceEdge edgeNew = - new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() ); + public void addParam2ParamAliasEdges( FlatMethod fm, + Set aliasedParamIndices ) { + + LabelNode lnAliased = getLabelNodeFromTemp( tdAliasBlob ); + + // the lnAliased should always only reference one node, and that + // heap region node is the aliased param blob + assert lnAliased.getNumReferencees() == 1; + HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst(); + Integer idAliased = hrnAliasBlob.getID(); + + + TokenTuple ttAliased = new TokenTuple( idAliased, + true, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + + + Iterator apItrI = aliasedParamIndices.iterator(); + while( apItrI.hasNext() ) { + Integer i = apItrI.next(); + TempDescriptor tdParamI = fm.getParameter( i ); + TypeDescriptor typeI = tdParamI.getType(); + LabelNode lnParamI = getLabelNodeFromTemp( tdParamI ); + + Integer idPrimaryI = paramIndex2idPrimary.get( i ); + assert idPrimaryI != null; + HeapRegionNode primaryI = id2hrn.get( idPrimaryI ); + assert primaryI != null; + + TokenTuple ttPrimaryI = new TokenTuple( idPrimaryI, + false, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + + TokenTupleSet ttsI = new TokenTupleSet( ttPrimaryI ).makeCanonical(); + TokenTupleSet ttsA = new TokenTupleSet( ttAliased ).makeCanonical(); + TokenTupleSet ttsIA = new TokenTupleSet( ttPrimaryI ).makeCanonical().union( ttAliased ); + ReachabilitySet betaSoup = ReachabilitySet.factory( ttsI ).union( ttsA ).union( ttsIA ); + + + // calculate whether fields of this aliased parameter are able to + // reference its own primary object, the blob, or other parameter's + // primary objects! + Set primary2primaryFields = new HashSet(); + Set primary2secondaryFields = new HashSet(); + + // there might be an element reference for array types + if( typeI.isArray() ) { + // only bother with this if the dereferenced type can + // affect reachability + TypeDescriptor typeDeref = typeI.dereference(); + + // for this parameter to be aliased the following must be true + assert !typeDeref.isImmutable() || typeDeref.isArray(); + + primary2secondaryFields.add( + OwnershipAnalysis.getArrayField( typeDeref ) + ); + + // also handle a special case where an array of objects + // can point back to the array, which is an object! + if( typeI .toPrettyString().equals( "Object[]" ) && + typeDeref.toPrettyString().equals( "Object" ) ) { + primary2primaryFields.add( + OwnershipAnalysis.getArrayField( typeDeref ) + ); + } + } + + // there might be member references for class types + if( typeI.isClass() ) { + ClassDescriptor cd = typeI.getClassDesc(); + while( cd != null ) { + + Iterator fieldItr = cd.getFields(); + while( fieldItr.hasNext() ) { + + FieldDescriptor fd = (FieldDescriptor) fieldItr.next(); + TypeDescriptor typeField = fd.getType(); + assert typeField != null; + + if( !typeField.isImmutable() || typeField.isArray() ) { + primary2secondaryFields.add( fd ); + } + + if( typeUtil.isSuperorType( typeField, typeI ) ) { + primary2primaryFields.add( fd ); + } + } + + cd = cd.getSuperDesc(); + } + } + + Iterator fieldItr = primary2primaryFields.iterator(); + while( fieldItr.hasNext() ) { + FieldDescriptor fd = fieldItr.next(); + + ReferenceEdge edgePrimaryReflexive = + new ReferenceEdge( primaryI, // src + primaryI, // dst + fd.getType(), // type + fd.getSymbol(), // field + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive ); + } - addReferenceEdge(lnX, hrnNewest, edgeNew); + fieldItr = primary2secondaryFields.iterator(); + while( fieldItr.hasNext() ) { + FieldDescriptor fd = fieldItr.next(); + TypeDescriptor typeField = fd.getType(); + assert typeField != null; + + ReferenceEdge edgePrimary2Secondary = + new ReferenceEdge( primaryI, // src + hrnAliasBlob, // dst + fd.getType(), // type + fd.getSymbol(), // field + true, // special param initial + betaSoup ); // reachability + addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary ); + + // ask whether these fields might match any of the other aliased + // parameters and make those edges too + Iterator apItrJ = aliasedParamIndices.iterator(); + while( apItrJ.hasNext() ) { + Integer j = apItrJ.next(); + TempDescriptor tdParamJ = fm.getParameter( j ); + TypeDescriptor typeJ = tdParamJ.getType(); + + if( !i.equals( j ) && typeUtil.isSuperorType( typeField, typeJ ) ) { + + Integer idPrimaryJ = paramIndex2idPrimary.get( j ); + assert idPrimaryJ != null; + HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ ); + assert primaryJ != null; + + TokenTuple ttPrimaryJ = new TokenTuple( idPrimaryJ, + false, // multi-object + TokenTuple.ARITY_ONE ).makeCanonical(); + + TokenTupleSet ttsJ = new TokenTupleSet( ttPrimaryJ ).makeCanonical(); + TokenTupleSet ttsIJ = ttsI.union( ttsJ ); + TokenTupleSet ttsAJ = ttsA.union( ttsJ ); + TokenTupleSet ttsIAJ = ttsIA.union( ttsJ ); + ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ ); + + ReferenceEdge edgePrimaryI2PrimaryJ = + new ReferenceEdge( primaryI, // src + primaryJ, // dst + fd.getType(), // type + fd.getSymbol(), // field + true, // special param initial + betaSoupWJ ); // reachability + addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ ); + } + } + } + + + // look at whether aliased parameters i and j can + // possibly be the same primary object, add edges + Iterator apItrJ = aliasedParamIndices.iterator(); + while( apItrJ.hasNext() ) { + Integer j = apItrJ.next(); + TempDescriptor tdParamJ = fm.getParameter( j ); + TypeDescriptor typeJ = tdParamJ.getType(); + LabelNode lnParamJ = getLabelNodeFromTemp( tdParamJ ); + + if( !i.equals( j ) && typeUtil.isSuperorType( typeI, typeJ ) ) { + + Integer idPrimaryJ = paramIndex2idPrimary.get( j ); + assert idPrimaryJ != null; + HeapRegionNode primaryJ = id2hrn.get( idPrimaryJ ); + assert primaryJ != null; + + ReferenceEdge lnJ2PrimaryJ = lnParamJ.getReferenceTo( primaryJ, + tdParamJ.getType(), + null ); + assert lnJ2PrimaryJ != null; + + ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy(); + lnI2PrimaryJ.setSrc( lnParamI ); + lnI2PrimaryJ.setType( tdParamI.getType() ); + lnI2PrimaryJ.tainedBy(new Integer(j)); + addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ ); + } + } + } } + public void prepareParamTokenMaps( FlatMethod fm ) { - // use the allocation site (unique to entire analysis) to + // always add the bogus mappings that are used to + // rewrite "with respect to no parameter" + paramTokenPrimary2paramIndex.put( bogusToken, bogusIndex ); + paramIndex2paramTokenPrimary.put( bogusIndex, bogusToken ); + + paramTokenSecondary2paramIndex.put( bogusToken, bogusIndex ); + paramIndex2paramTokenSecondary.put( bogusIndex, bogusToken ); + paramTokenSecondaryPlus2paramIndex.put( bogusTokenPlus, bogusIndex ); + paramIndex2paramTokenSecondaryPlus.put( bogusIndex, bogusTokenPlus ); + paramTokenSecondaryStar2paramIndex.put( bogusTokenStar, bogusIndex ); + paramIndex2paramTokenSecondaryStar.put( bogusIndex, bogusTokenStar ); + + for( int i = 0; i < fm.numParameters(); ++i ) { + Integer paramIndex = new Integer( i ); + + // immutable objects have no primary regions + if( paramIndex2idPrimary.containsKey( paramIndex ) ) { + Integer idPrimary = paramIndex2idPrimary.get( paramIndex ); + + assert id2hrn.containsKey( idPrimary ); + HeapRegionNode hrnPrimary = id2hrn.get( idPrimary ); + + TokenTuple p_i = new TokenTuple( hrnPrimary.getID(), + false, // multiple-object? + TokenTuple.ARITY_ONE ).makeCanonical(); + paramTokenPrimary2paramIndex.put( p_i, paramIndex ); + paramIndex2paramTokenPrimary.put( paramIndex, p_i ); + } + + // any parameter object, by type, may have no secondary region + if( paramIndex2idSecondary.containsKey( paramIndex ) ) { + Integer idSecondary = paramIndex2idSecondary.get( paramIndex ); + + assert id2hrn.containsKey( idSecondary ); + HeapRegionNode hrnSecondary = id2hrn.get( idSecondary ); + + TokenTuple s_i = new TokenTuple( hrnSecondary.getID(), + true, // multiple-object? + TokenTuple.ARITY_ONE ).makeCanonical(); + paramTokenSecondary2paramIndex.put( s_i, paramIndex ); + paramIndex2paramTokenSecondary.put( paramIndex, s_i ); + + TokenTuple s_i_plus = new TokenTuple( hrnSecondary.getID(), + true, // multiple-object? + TokenTuple.ARITY_ONEORMORE ).makeCanonical(); + paramTokenSecondaryPlus2paramIndex.put( s_i_plus, paramIndex ); + paramIndex2paramTokenSecondaryPlus.put( paramIndex, s_i_plus ); + + TokenTuple s_i_star = new TokenTuple( hrnSecondary.getID(), + true, // multiple-object? + TokenTuple.ARITY_ZEROORMORE ).makeCanonical(); + paramTokenSecondaryStar2paramIndex.put( s_i_star, paramIndex ); + paramIndex2paramTokenSecondaryStar.put( paramIndex, s_i_star ); + } + } + } + + + + public void assignReturnEqualToTemp(TempDescriptor x) { + + LabelNode lnR = getLabelNodeFromTemp(tdReturn); + LabelNode lnX = getLabelNodeFromTemp(x); + + clearReferenceEdgesFrom(lnR, null, null, true); + + Iterator itrXhrn = lnX.iteratorToReferencees(); + while( itrXhrn.hasNext() ) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode referencee = edgeX.getDst(); + ReferenceEdge edgeNew = edgeX.copy(); + edgeNew.setSrc(lnR); + + addReferenceEdge(lnR, referencee, edgeNew); + } + } + + + public void assignTempEqualToNewAlloc(TempDescriptor x, + AllocationSite as) { + assert x != null; + assert as != null; + + age( as ); + + // after the age operation the newest (or zero-ith oldest) + // node associated with the allocation site should have + // no references to it as if it were a newly allocated + // heap region + Integer idNewest = as.getIthOldest( 0 ); + HeapRegionNode hrnNewest = id2hrn.get( idNewest ); + assert hrnNewest != null; + + LabelNode lnX = getLabelNodeFromTemp( x ); + clearReferenceEdgesFrom( lnX, null, null, true ); + + // make a new reference to allocated node + TypeDescriptor type = as.getType(); + ReferenceEdge edgeNew = + new ReferenceEdge( lnX, // source + hrnNewest, // dest + type, // type + null, // field name + false, // is initial param + hrnNewest.getAlpha() // beta + ); + + addReferenceEdge( lnX, hrnNewest, edgeNew ); + } + + + // use the allocation site (unique to entire analysis) to // locate the heap region nodes in this ownership graph // that should be aged. The process models the allocation // of new objects and collects all the oldest allocations @@ -663,8 +1254,8 @@ public class OwnershipGraph { assert hrn0 != null; // clear all references in and out of newest node - clearReferenceEdgesFrom(hrn0, null, true); - clearReferenceEdgesTo(hrn0, null, true); + clearReferenceEdgesFrom(hrn0, null, null, true); + clearReferenceEdgesTo(hrn0, null, null, true); // now tokens in reachability sets need to "age" also @@ -695,14 +1286,16 @@ public class OwnershipGraph { // after tokens have been aged, reset newest node's reachability if( hrn0.isFlagged() ) { - hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet( - new TokenTuple(hrn0) - ) - ).makeCanonical() + hrn0.setAlpha(new ReachabilitySet( + new TokenTupleSet( + new TokenTuple(hrn0).makeCanonical() + ).makeCanonical() + ).makeCanonical() ); } else { - hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet() - ).makeCanonical() + hrn0.setAlpha(new ReachabilitySet( + new TokenTupleSet().makeCanonical() + ).makeCanonical() ); } } @@ -727,26 +1320,28 @@ public class OwnershipGraph { hasFlags = as.getType().getClassDesc().hasFlags(); } - hrnSummary = createNewHeapRegionNode(idSummary, - false, - hasFlags, - true, - false, - as, - null, - as + "\\n" + as.getType() + "\\nsummary"); + hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one + false, // single object? + true, // summary? + hasFlags, // flagged? + false, // is a parameter? + as.getType(), // type + as, // allocation site + null, // reachability set + as.toStringForDOT() + "\\nsummary"); for( int i = 0; i < as.getAllocationDepth(); ++i ) { Integer idIth = as.getIthOldest(i); assert !id2hrn.containsKey(idIth); - createNewHeapRegionNode(idIth, - true, - hasFlags, - false, - false, - as, - null, - as + "\\n" + as.getType() + "\\n" + i + " oldest"); + createNewHeapRegionNode(idIth, // id or null to generate a new one + true, // single object? + false, // summary? + hasFlags, // flagged? + false, // is a parameter? + as.getType(), // type + as, // allocation site + null, // reachability set + as.toStringForDOT() + "\\n" + i + " oldest"); } } @@ -766,25 +1361,27 @@ public class OwnershipGraph { hasFlags = as.getType().getClassDesc().hasFlags(); } - hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, - false, - hasFlags, - true, - false, - as, - null, + hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one + false, // single object? + true, // summary? + hasFlags, // flagged? + false, // is a parameter? + as.getType(), // type + as, // allocation site + null, // reachability set as + "\\n" + as.getType() + "\\nshadowSum"); for( int i = 0; i < as.getAllocationDepth(); ++i ) { Integer idShadowIth = as.getIthOldestShadow(i); assert !id2hrn.containsKey(idShadowIth); - createNewHeapRegionNode(idShadowIth, - true, - hasFlags, - false, - false, - as, - null, + createNewHeapRegionNode(idShadowIth, // id or null to generate a new one + true, // single object? + false, // summary? + hasFlags, // flagged? + false, // is a parameter? + as.getType(), // type + as, // allocation site + null, // reachability set as + "\\n" + as.getType() + "\\n" + i + " shadow"); } } @@ -804,7 +1401,9 @@ public class OwnershipGraph { edgeMerged.setSrc(hrnSummary); HeapRegionNode hrnReferencee = edge.getDst(); - ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() ); + ReferenceEdge edgeSummary = hrnSummary.getReferenceTo(hrnReferencee, + edge.getType(), + edge.getField() ); if( edgeSummary == null ) { // the merge is trivial, nothing to be done @@ -817,182 +1416,640 @@ public class OwnershipGraph { addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged); } - // next transfer references _to_ hrn over to hrnSummary - Iterator itrReferencer = hrn.iteratorToReferencers(); - while( itrReferencer.hasNext() ) { - ReferenceEdge edge = itrReferencer.next(); - ReferenceEdge edgeMerged = edge.copy(); - edgeMerged.setDst(hrnSummary); + // next transfer references _to_ hrn over to hrnSummary + Iterator itrReferencer = hrn.iteratorToReferencers(); + while( itrReferencer.hasNext() ) { + ReferenceEdge edge = itrReferencer.next(); + ReferenceEdge edgeMerged = edge.copy(); + edgeMerged.setDst(hrnSummary); + + OwnershipNode onReferencer = edge.getSrc(); + ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, + edge.getType(), + edge.getField() ); + + if( edgeSummary == null ) { + // the merge is trivial, nothing to be done + } else { + // otherwise an edge from the referencer to alpha_S exists already + // and the edge referencer->alpha_K should be merged with it + edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) ); + } + + addReferenceEdge(onReferencer, hrnSummary, edgeMerged); + } + + // then merge hrn reachability into hrnSummary + hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) ); + } + + + protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) { + + // clear references in and out of node b + clearReferenceEdgesFrom(hrnB, null, null, true); + clearReferenceEdgesTo(hrnB, null, null, true); + + // copy each edge in and out of A to B + Iterator itrReferencee = hrnA.iteratorToReferencees(); + while( itrReferencee.hasNext() ) { + ReferenceEdge edge = itrReferencee.next(); + HeapRegionNode hrnReferencee = edge.getDst(); + ReferenceEdge edgeNew = edge.copy(); + edgeNew.setSrc(hrnB); + + addReferenceEdge(hrnB, hrnReferencee, edgeNew); + } + + Iterator itrReferencer = hrnA.iteratorToReferencers(); + while( itrReferencer.hasNext() ) { + ReferenceEdge edge = itrReferencer.next(); + OwnershipNode onReferencer = edge.getSrc(); + ReferenceEdge edgeNew = edge.copy(); + edgeNew.setDst(hrnB); + + addReferenceEdge(onReferencer, hrnB, edgeNew); + } + + // replace hrnB reachability with hrnA's + hrnB.setAlpha(hrnA.getAlpha() ); + } + + + protected void ageTokens(AllocationSite as, ReferenceEdge edge) { + edge.setBeta(edge.getBeta().ageTokens(as) ); + } + + protected void ageTokens(AllocationSite as, HeapRegionNode hrn) { + hrn.setAlpha(hrn.getAlpha().ageTokens(as) ); + } + + + + protected void propagateTokensOverNodes(HeapRegionNode nPrime, + ChangeTupleSet c0, + HashSet nodesWithNewAlpha, + HashSet edgesWithNewBeta) { + + HashSet todoNodes + = new HashSet(); + todoNodes.add(nPrime); + + HashSet todoEdges + = new HashSet(); + + Hashtable nodePlannedChanges + = new Hashtable(); + nodePlannedChanges.put(nPrime, c0); + + Hashtable edgePlannedChanges + = new Hashtable(); + + // first propagate change sets everywhere they can go + while( !todoNodes.isEmpty() ) { + HeapRegionNode n = todoNodes.iterator().next(); + ChangeTupleSet C = nodePlannedChanges.get(n); + + Iterator referItr = n.iteratorToReferencers(); + while( referItr.hasNext() ) { + ReferenceEdge edge = referItr.next(); + todoEdges.add(edge); + + if( !edgePlannedChanges.containsKey(edge) ) { + edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() ); + } + + edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) ); + } + + Iterator refeeItr = n.iteratorToReferencees(); + while( refeeItr.hasNext() ) { + ReferenceEdge edgeF = refeeItr.next(); + HeapRegionNode m = edgeF.getDst(); + + ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); + + Iterator itrCprime = C.iterator(); + while( itrCprime.hasNext() ) { + ChangeTuple c = itrCprime.next(); + if( edgeF.getBeta().contains( c.getSetToMatch() ) ) { + changesToPass = changesToPass.union(c); + } + } + + if( !changesToPass.isEmpty() ) { + if( !nodePlannedChanges.containsKey(m) ) { + nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet currentChanges = nodePlannedChanges.get(m); + + if( !changesToPass.isSubset(currentChanges) ) { + + nodePlannedChanges.put(m, currentChanges.union(changesToPass) ); + todoNodes.add(m); + } + } + } + + todoNodes.remove(n); + } + + // then apply all of the changes for each node at once + Iterator itrMap = nodePlannedChanges.entrySet().iterator(); + while( itrMap.hasNext() ) { + Map.Entry me = (Map.Entry) itrMap.next(); + HeapRegionNode n = (HeapRegionNode) me.getKey(); + ChangeTupleSet C = (ChangeTupleSet) me.getValue(); + + n.setAlphaNew( n.getAlpha().applyChangeSet( C, true ) ); + nodesWithNewAlpha.add( n ); + } + + propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta); + } + + + protected void propagateTokensOverEdges( + HashSet todoEdges, + Hashtable edgePlannedChanges, + HashSet edgesWithNewBeta) { + + // first propagate all change tuples everywhere they can go + while( !todoEdges.isEmpty() ) { + ReferenceEdge edgeE = todoEdges.iterator().next(); + todoEdges.remove(edgeE); + + if( !edgePlannedChanges.containsKey(edgeE) ) { + edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet C = edgePlannedChanges.get(edgeE); + + ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical(); + + Iterator itrC = C.iterator(); + while( itrC.hasNext() ) { + ChangeTuple c = itrC.next(); + if( edgeE.getBeta().contains( c.getSetToMatch() ) ) { + changesToPass = changesToPass.union(c); + } + } + + OwnershipNode onSrc = edgeE.getSrc(); + + if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) { + HeapRegionNode n = (HeapRegionNode) onSrc; + + Iterator referItr = n.iteratorToReferencers(); + while( referItr.hasNext() ) { + ReferenceEdge edgeF = referItr.next(); + + if( !edgePlannedChanges.containsKey(edgeF) ) { + edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() ); + } + + ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF); + + if( !changesToPass.isSubset(currentChanges) ) { + todoEdges.add(edgeF); + edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) ); + } + } + } + } + + // then apply all of the changes for each edge at once + Iterator itrMap = edgePlannedChanges.entrySet().iterator(); + while( itrMap.hasNext() ) { + Map.Entry me = (Map.Entry) itrMap.next(); + ReferenceEdge e = (ReferenceEdge) me.getKey(); + ChangeTupleSet C = (ChangeTupleSet) me.getValue(); + + e.setBetaNew( e.getBetaNew().union( e.getBeta().applyChangeSet( C, true ) ) ); + edgesWithNewBeta.add( e ); + } + } + + + public Set calculateAliasedParamSet( FlatCall fc, + boolean isStatic, + FlatMethod fm ) { + + Hashtable paramIndex2ln = + new Hashtable(); + + Hashtable > paramIndex2reachableCallerNodes = + new Hashtable >(); + + for( int i = 0; i < fm.numParameters(); ++i ) { + Integer paramIndex = new Integer( i ); + TempDescriptor tdParam = fm.getParameter( i ); + TypeDescriptor typeParam = tdParam.getType(); + + if( typeParam.isImmutable() && !typeParam.isArray() ) { + // don't bother with this primitive parameter, it + // cannot affect reachability + continue; + } + + // now depending on whether the callee is static or not + // we need to account for a "this" argument in order to + // find the matching argument in the caller context + TempDescriptor argTemp_i; + if( isStatic ) { + argTemp_i = fc.getArg(paramIndex); + } else { + if( paramIndex.equals(0) ) { + argTemp_i = fc.getThis(); + } else { + argTemp_i = fc.getArg(paramIndex - 1); + } + } + + // in non-static methods there is a "this" pointer + // that should be taken into account + if( isStatic ) { + assert fc.numArgs() == fm.numParameters(); + } else { + assert fc.numArgs() + 1 == fm.numParameters(); + } + + LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i); + paramIndex2ln.put(paramIndex, argLabel_i); + } + + Iterator lnArgItr = paramIndex2ln.entrySet().iterator(); + while( lnArgItr.hasNext() ) { + Map.Entry me = (Map.Entry)lnArgItr.next(); + Integer index = (Integer) me.getKey(); + LabelNode lnArg_i = (LabelNode) me.getValue(); + + HashSet reachableNodes = new HashSet(); + HashSet todoNodes = new HashSet(); + + // to find all reachable nodes, start with label referencees + Iterator edgeArgItr = lnArg_i.iteratorToReferencees(); + while( edgeArgItr.hasNext() ) { + ReferenceEdge edge = edgeArgItr.next(); + todoNodes.add( edge.getDst() ); + } + + // then follow links until all reachable nodes have been found + while( !todoNodes.isEmpty() ) { + HeapRegionNode hrn = todoNodes.iterator().next(); + todoNodes.remove(hrn); + reachableNodes.add(hrn); + + Iterator edgeItr = hrn.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + if( !reachableNodes.contains(edge.getDst() ) ) { + todoNodes.add(edge.getDst() ); + } + } + } + + // save for later + paramIndex2reachableCallerNodes.put(index, reachableNodes); + } + + Set aliasedIndices = new HashSet(); + + // check for arguments that are aliased + for( int i = 0; i < fm.numParameters(); ++i ) { + for( int j = 0; j < i; ++j ) { + HashSet s1 = paramIndex2reachableCallerNodes.get( i ); + HashSet s2 = paramIndex2reachableCallerNodes.get( j ); + + // some parameters are immutable or primitive, so skip em + if( s1 == null || s2 == null ) { + continue; + } - OwnershipNode onReferencer = edge.getSrc(); - ReferenceEdge edgeSummary = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() ); + Set intersection = new HashSet(s1); + intersection.retainAll(s2); - if( edgeSummary == null ) { - // the merge is trivial, nothing to be done - } else { - // otherwise an edge from the referencer to alpha_S exists already - // and the edge referencer->alpha_K should be merged with it - edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) ); + if( !intersection.isEmpty() ) { + aliasedIndices.add( new Integer( i ) ); + aliasedIndices.add( new Integer( j ) ); + } } - - addReferenceEdge(onReferencer, hrnSummary, edgeMerged); } - // then merge hrn reachability into hrnSummary - hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) ); + return aliasedIndices; } - protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) { + private String makeMapKey( Integer i, Integer j, String field ) { + return i+","+j+","+field; + } - // clear references in and out of node i - clearReferenceEdgesFrom(hrnB, null, true); - clearReferenceEdgesTo(hrnB, null, true); + private String makeMapKey( Integer i, String field ) { + return i+","+field; + } - // copy each edge in and out of A to B - Iterator itrReferencee = hrnA.iteratorToReferencees(); - while( itrReferencee.hasNext() ) { - ReferenceEdge edge = itrReferencee.next(); - HeapRegionNode hrnReferencee = edge.getDst(); - ReferenceEdge edgeNew = edge.copy(); - edgeNew.setSrc(hrnB); + // these hashtables are used during the mapping procedure to say that + // with respect to some argument i there is an edge placed into some + // category for mapping with respect to another argument index j + // so the key into the hashtable is i, the value is a two-element vector + // that contains in 0 the edge and in 1 the Integer index j + private void ensureEmptyEdgeIndexPair( Hashtable< Integer, Set > edge_index_pairs, + Integer indexI ) { + + Set ei = edge_index_pairs.get( indexI ); + if( ei == null ) { + ei = new HashSet(); + } + edge_index_pairs.put( indexI, ei ); + } - addReferenceEdge(hrnB, hrnReferencee, edgeNew); + private void addEdgeIndexPair( Hashtable< Integer, Set > edge_index_pairs, + Integer indexI, + ReferenceEdge edge, + Integer indexJ ) { + + Vector v = new Vector(); v.setSize( 2 ); + v.set( 0 , edge ); + v.set( 1 , indexJ ); + Set ei = edge_index_pairs.get( indexI ); + if( ei == null ) { + ei = new HashSet(); } + ei.add( v ); + edge_index_pairs.put( indexI, ei ); + } - Iterator itrReferencer = hrnA.iteratorToReferencers(); - while( itrReferencer.hasNext() ) { - ReferenceEdge edge = itrReferencer.next(); - OwnershipNode onReferencer = edge.getSrc(); - ReferenceEdge edgeNew = edge.copy(); - edgeNew.setDst(hrnB); + private ReachabilitySet funcScriptR( ReachabilitySet rsIn, + OwnershipGraph ogCallee, + MethodContext mc ) { - addReferenceEdge(onReferencer, hrnB, edgeNew); - } + ReachabilitySet rsOut = new ReachabilitySet( rsIn ); - // replace hrnB reachability with hrnA's - hrnB.setAlpha(hrnA.getAlpha() ); - } + Iterator itr = ogCallee.paramIndex2paramTokenPrimary.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry me = (Map.Entry) itr.next(); + Integer i = (Integer) me.getKey(); + TokenTuple p_i = (TokenTuple) me.getValue(); + TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( i ); + // skip this if there is no secondary token or the parameter + // is part of the aliasing context + if( s_i == null || mc.getAliasedParamIndices().contains( i ) ) { + continue; + } - protected void ageTokens(AllocationSite as, ReferenceEdge edge) { - edge.setBeta(edge.getBeta().ageTokens(as) ); + rsOut = rsOut.removeTokenAIfTokenB( p_i, s_i ); + } + + return rsOut; } - protected void ageTokens(AllocationSite as, HeapRegionNode hrn) { - hrn.setAlpha(hrn.getAlpha().ageTokens(as) ); + // detects strong updates to the primary parameter object and + // effects the removal of old edges in the calling graph + private void effectCalleeStrongUpdates( Integer paramIndex, + OwnershipGraph ogCallee, + HeapRegionNode hrnCaller + ) { + Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex ); + assert idPrimary != null; + + HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary ); + assert hrnPrimary != null; + + TypeDescriptor typeParam = hrnPrimary.getType(); + assert typeParam.isClass(); + + Set fieldNamesToRemove = new HashSet(); + + ClassDescriptor cd = typeParam.getClassDesc(); + while( cd != null ) { + + Iterator fieldItr = cd.getFields(); + while( fieldItr.hasNext() ) { + + FieldDescriptor fd = (FieldDescriptor) fieldItr.next(); + TypeDescriptor typeField = fd.getType(); + assert typeField != null; + + if( ogCallee.hasFieldBeenUpdated( hrnPrimary, fd.getSymbol() ) ) { + clearReferenceEdgesFrom( hrnCaller, fd.getType(), fd.getSymbol(), false ); + } + } + + cd = cd.getSuperDesc(); + } } + private boolean hasFieldBeenUpdated( HeapRegionNode hrnPrimary, String field ) { - public void resolveMethodCall(FlatCall fc, - boolean isStatic, - FlatMethod fm, - OwnershipGraph ogCallee) { + Iterator itr = hrnPrimary.iteratorToReferencees(); + while( itr.hasNext() ) { + ReferenceEdge e = itr.next(); + if( e.fieldEquals( field ) && e.isInitialParam() ) { + return false; + } + } - // define rewrite rules and other structures to organize - // data by parameter/argument index - Hashtable paramIndex2rewriteH = - new Hashtable(); + return true; + } - Hashtable paramIndex2rewriteJ = - new Hashtable(); + // resolveMethodCall() is used to incorporate a callee graph's effects into + // *this* graph, which is the caller. This method can also be used, after + // the entire analysis is complete, to perform parameter decomposition for + // a given call chain. + public void resolveMethodCall(FlatCall fc, // call site in caller method + boolean isStatic, // whether it is a static method + FlatMethod fm, // the callee method (when virtual, can be many) + OwnershipGraph ogCallee, // the callee's current ownership graph + MethodContext mc, // the aliasing context for this call + ParameterDecomposition pd // if this is not null, we're calling after analysis + ) { + + + // this debug snippet is harmless for regular use and INVALUABLE at debug time + // to see what potentially goes wrong when a specific method calls another + String debugCaller = "foo"; + String debugCallee = "bar"; + //String debugCaller = "StandardEngine"; + //String debugCaller = "register_by_type"; + //String debugCaller = "register_by_type_front"; + //String debugCaller = "addFirst"; + //String debugCallee = "LinkedListElement"; + + if( mc.getDescriptor().getSymbol().equals( debugCaller ) && + fm.getMethod().getSymbol().equals( debugCallee ) ) { + + try { + writeGraph( "debug1BeforeCall", true, true, true, false, false ); + ogCallee.writeGraph( "debug0Callee", true, true, true, false, false ); + } catch( IOException e ) {} + + System.out.println( " "+mc+" is calling "+fm ); + } - Hashtable paramIndex2rewriteK = - new Hashtable(); - Hashtable paramIndex2rewriteD = - new Hashtable(); - // helpful structures - Hashtable paramToken2paramIndex = - new Hashtable(); + // define rewrite rules and other structures to organize data by parameter/argument index + Hashtable paramIndex2rewriteH_p = new Hashtable(); + Hashtable paramIndex2rewriteH_s = new Hashtable(); + + Hashtable paramIndex2rewriteJ_p2p = new Hashtable(); // select( i, j, f ) + Hashtable paramIndex2rewriteJ_p2s = new Hashtable(); // select( i, f ) + Hashtable paramIndex2rewriteJ_s2p = new Hashtable(); + Hashtable paramIndex2rewriteJ_s2s = new Hashtable(); - Hashtable paramIndex2paramToken = - new Hashtable(); + Hashtable paramIndex2rewriteK_p = new Hashtable(); + Hashtable paramIndex2rewriteK_p2 = new Hashtable(); + Hashtable paramIndex2rewriteK_s = new Hashtable(); - Hashtable paramTokenStar2paramIndex = - new Hashtable(); + Hashtable paramIndex2rewrite_d_p = new Hashtable(); + Hashtable paramIndex2rewrite_d_s = new Hashtable(); - Hashtable paramIndex2paramTokenStar = - new Hashtable(); + Hashtable paramIndex2rewriteD = new Hashtable(); - Hashtable paramIndex2ln = - new Hashtable(); - Hashtable > paramIndex2reachableCallerNodes = - new Hashtable >(); + Hashtable paramIndex2ln = new Hashtable(); - // add a bogus entry with the identity rule for easy rewrite - // of new callee nodes and edges, doesn't belong to any parameter - Integer bogusID = new Integer(-1); - Integer bogusIndex = new Integer(-1); - TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE); - TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY); - ReachabilitySet rsIdentity = - new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical(); + paramIndex2rewriteH_p.put( bogusIndex, rsIdentity ); + paramIndex2rewriteH_s.put( bogusIndex, rsIdentity ); - paramIndex2rewriteH.put(bogusIndex, rsIdentity); - paramIndex2rewriteJ.put(bogusIndex, rsIdentity); - paramToken2paramIndex.put(bogusToken, bogusIndex); - paramIndex2paramToken.put(bogusIndex, bogusToken); - paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex); - paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar); + paramIndex2rewriteJ_p2p.put( bogusIndex.toString(), rsIdentity ); + paramIndex2rewriteJ_p2s.put( bogusIndex.toString(), rsIdentity ); + paramIndex2rewriteJ_s2p.put( bogusIndex, rsIdentity ); + paramIndex2rewriteJ_s2s.put( bogusIndex, rsIdentity ); for( int i = 0; i < fm.numParameters(); ++i ) { Integer paramIndex = new Integer(i); - assert ogCallee.paramIndex2id.containsKey(paramIndex); - Integer idParam = ogCallee.paramIndex2id.get(paramIndex); - - assert ogCallee.id2hrn.containsKey(idParam); - HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam); - assert hrnParam != null; - paramIndex2rewriteH.put(paramIndex, - - toShadowTokens(ogCallee, hrnParam.getAlpha() ) - ); + if( !ogCallee.paramIndex2idPrimary.containsKey( paramIndex ) ) { + // skip this immutable parameter + continue; + } + + // setup H (primary) + Integer idPrimary = ogCallee.paramIndex2idPrimary.get( paramIndex ); + assert ogCallee.id2hrn.containsKey( idPrimary ); + HeapRegionNode hrnPrimary = ogCallee.id2hrn.get( idPrimary ); + assert hrnPrimary != null; + paramIndex2rewriteH_p.put( paramIndex, toShadowTokens( ogCallee, hrnPrimary.getAlpha() ) ); + + // setup J (primary->X) + Iterator p2xItr = hrnPrimary.iteratorToReferencees(); + while( p2xItr.hasNext() ) { + ReferenceEdge p2xEdge = p2xItr.next(); + + // we only care about initial parameter edges here + if( !p2xEdge.isInitialParam() ) { continue; } + + HeapRegionNode hrnDst = p2xEdge.getDst(); + + if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) { + Iterator jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator(); + while( jItr.hasNext() ) { + Integer j = jItr.next(); + paramIndex2rewriteJ_p2p.put( makeMapKey( i, j, p2xEdge.getField() ), + toShadowTokens( ogCallee, p2xEdge.getBeta() ) ); + } - ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null); - assert edgeReflexive_i != null; - paramIndex2rewriteJ.put(paramIndex, - toShadowTokens(ogCallee, edgeReflexive_i.getBeta() ) - ); + } else { + assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() ); + paramIndex2rewriteJ_p2s.put( makeMapKey( i, p2xEdge.getField() ), + toShadowTokens( ogCallee, p2xEdge.getBeta() ) ); + } + } - TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex); + // setup K (primary) + TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex ); assert tdParamQ != null; - LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ); + LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ ); assert lnParamQ != null; - ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null); + ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnPrimary, null, null ); assert edgeSpecialQ_i != null; - paramIndex2rewriteK.put(paramIndex, - toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() ) - ); - - TokenTuple p_i = new TokenTuple(hrnParam.getID(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); - paramToken2paramIndex.put(p_i, paramIndex); - paramIndex2paramToken.put(paramIndex, p_i); - - TokenTuple p_i_star = new TokenTuple(hrnParam.getID(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); - paramTokenStar2paramIndex.put(p_i_star, paramIndex); - paramIndex2paramTokenStar.put(paramIndex, p_i_star); + ReachabilitySet qBeta = toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() ); + + TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary .get( paramIndex ); + TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( paramIndex ); + + ReachabilitySet K_p = new ReachabilitySet().makeCanonical(); + ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical(); + if( s_i == null ) { + K_p = qBeta; + } else { + // sort qBeta into K_p1 and K_p2 + Iterator ttsItr = qBeta.iterator(); + while( ttsItr.hasNext() ) { + TokenTupleSet tts = ttsItr.next(); + if( s_i != null && tts.containsBoth( p_i, s_i ) ) { + K_p2 = K_p2.union( tts ); + } else { + K_p = K_p.union( tts ); + } + } + } + paramIndex2rewriteK_p .put( paramIndex, K_p ); + paramIndex2rewriteK_p2.put( paramIndex, K_p2 ); + + + // if there is a secondary node, compute the rest of the rewrite rules + if( ogCallee.paramIndex2idSecondary.containsKey( paramIndex ) ) { + + // setup H (secondary) + Integer idSecondary = ogCallee.paramIndex2idSecondary.get( paramIndex ); + assert ogCallee.id2hrn.containsKey( idSecondary ); + HeapRegionNode hrnSecondary = ogCallee.id2hrn.get( idSecondary ); + assert hrnSecondary != null; + paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) ); + + + // setup J (secondary->X) + Iterator s2xItr = hrnSecondary.iteratorToReferencees(); + while( s2xItr.hasNext() ) { + ReferenceEdge s2xEdge = s2xItr.next(); + + if( !s2xEdge.isInitialParam() ) { continue; } + + HeapRegionNode hrnDst = s2xEdge.getDst(); + + if( ogCallee.idPrimary2paramIndexSet.containsKey( hrnDst.getID() ) ) { + Iterator jItr = ogCallee.idPrimary2paramIndexSet.get( hrnDst.getID() ).iterator(); + while( jItr.hasNext() ) { + Integer j = jItr.next(); + paramIndex2rewriteJ_s2p.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) ); + } + + } else { + assert ogCallee.idSecondary2paramIndexSet.containsKey( hrnDst.getID() ); + paramIndex2rewriteJ_s2s.put( i, toShadowTokens( ogCallee, s2xEdge.getBeta() ) ); + } + } + + // setup K (secondary) + TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get( paramIndex ); + assert tdParamR != null; + LabelNode lnParamR = ogCallee.td2ln.get( tdParamR ); + assert lnParamR != null; + ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo( hrnSecondary, null, null ); + assert edgeSpecialR_i != null; + paramIndex2rewriteK_s.put( paramIndex, + toShadowTokens( ogCallee, edgeSpecialR_i.getBeta() ) ); + } + // now depending on whether the callee is static or not // we need to account for a "this" argument in order to // find the matching argument in the caller context TempDescriptor argTemp_i; if( isStatic ) { - argTemp_i = fc.getArg(paramIndex); + argTemp_i = fc.getArg( paramIndex ); } else { - if( paramIndex == 0 ) { + if( paramIndex.equals( 0 ) ) { argTemp_i = fc.getThis(); } else { - argTemp_i = fc.getArg(paramIndex - 1); + argTemp_i = fc.getArg( paramIndex - 1 ); } } @@ -1004,153 +2061,575 @@ public class OwnershipGraph { assert fc.numArgs() + 1 == fm.numParameters(); } - LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i); - paramIndex2ln.put(paramIndex, argLabel_i); + // remember which caller arg label maps to param index + LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i ); + paramIndex2ln.put( paramIndex, argLabel_i ); + + // do a callee-effect strong update pre-pass here + if( argTemp_i.getType().isClass() ) { + + Iterator edgeItr = argLabel_i.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + HeapRegionNode hrn = edge.getDst(); - ReachabilitySet D_i = new ReachabilitySet().makeCanonical(); + if( (hrn.getNumReferencers() == 1) || // case 1 + (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2 + ) { + + effectCalleeStrongUpdates( paramIndex, ogCallee, hrn ); + } + } + } + + // then calculate the d and D rewrite rules + ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical(); + ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical(); Iterator edgeItr = argLabel_i.iteratorToReferencees(); while( edgeItr.hasNext() ) { ReferenceEdge edge = edgeItr.next(); - D_i = D_i.union(edge.getBeta() ); - } - D_i = D_i.exhaustiveArityCombinations(); + d_i_p = d_i_p.union( edge.getBeta().intersection( edge.getDst().getAlpha() ) ); + d_i_s = d_i_s.union( edge.getBeta() ); + } + paramIndex2rewrite_d_p.put( paramIndex, d_i_p ); + paramIndex2rewrite_d_s.put( paramIndex, d_i_s ); - paramIndex2rewriteD.put(paramIndex, D_i); + // TODO: we should only do this when we need it, and then + // memoize it for the rest of the mapping procedure + ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations(); + paramIndex2rewriteD.put( paramIndex, D_i ); } + // with respect to each argument, map parameter effects into caller HashSet nodesWithNewAlpha = new HashSet(); HashSet edgesWithNewBeta = new HashSet(); - HashSet edgesReachable = new HashSet(); - HashSet edgesUpstream = new HashSet(); + Hashtable > pi2dr = + new Hashtable >(); + + Hashtable > pi2r = + new Hashtable >(); + + Set defParamObj = new HashSet(); Iterator lnArgItr = paramIndex2ln.entrySet().iterator(); while( lnArgItr.hasNext() ) { - Map.Entry me = (Map.Entry)lnArgItr.next(); - Integer index = (Integer) me.getKey(); + Map.Entry me = (Map.Entry) lnArgItr.next(); + Integer index = (Integer) me.getKey(); LabelNode lnArg_i = (LabelNode) me.getValue(); + + Set dr = new HashSet(); + Set r = new HashSet(); + Set todo = new HashSet(); - // rewrite alpha for the nodes reachable from argument label i - HashSet reachableNodes = new HashSet(); - HashSet todoNodes = new HashSet(); - - // to find all reachable nodes, start with label referencees + // find all reachable nodes starting with label referencees Iterator edgeArgItr = lnArg_i.iteratorToReferencees(); while( edgeArgItr.hasNext() ) { ReferenceEdge edge = edgeArgItr.next(); - todoNodes.add(edge.getDst() ); - } + HeapRegionNode hrn = edge.getDst(); - // then follow links until all reachable nodes have been found - while( !todoNodes.isEmpty() ) { - HeapRegionNode hrn = todoNodes.iterator().next(); - todoNodes.remove(hrn); - reachableNodes.add(hrn); + dr.add( hrn ); - Iterator edgeItr = hrn.iteratorToReferencees(); - while( edgeItr.hasNext() ) { - ReferenceEdge edge = edgeItr.next(); + if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) { + defParamObj.add( hrn ); + } - if( !reachableNodes.contains(edge.getDst() ) ) { - todoNodes.add(edge.getDst() ); + Iterator edgeHrnItr = hrn.iteratorToReferencees(); + while( edgeHrnItr.hasNext() ) { + ReferenceEdge edger = edgeHrnItr.next(); + todo.add( edger.getDst() ); + } + + // then follow links until all reachable nodes have been found + while( !todo.isEmpty() ) { + HeapRegionNode hrnr = todo.iterator().next(); + todo.remove( hrnr ); + + r.add( hrnr ); + + Iterator edgeItr = hrnr.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edger = edgeItr.next(); + if( !r.contains( edger.getDst() ) ) { + todo.add( edger.getDst() ); + } } } + + if( hrn.isSingleObject() ) { + r.remove( hrn ); + } } - // save for later - paramIndex2reachableCallerNodes.put(index, reachableNodes); + pi2dr.put( index, dr ); + pi2r .put( index, r ); + } - // now iterate over reachable nodes to update their alpha, and - // classify edges found as "argument reachable" or "upstream" - Iterator hrnItr = reachableNodes.iterator(); + assert defParamObj.size() <= fm.numParameters(); + + // if we're in parameter decomposition mode, report some results here + if( pd != null ) { + Iterator mapItr; + + // report primary parameter object mappings + mapItr = pi2dr.entrySet().iterator(); + while( mapItr.hasNext() ) { + Map.Entry me = (Map.Entry) mapItr.next(); + Integer paramIndex = (Integer) me.getKey(); + Set hrnAset = (Set) me.getValue(); + + Iterator hrnItr = hrnAset.iterator(); + while( hrnItr.hasNext() ) { + HeapRegionNode hrnA = hrnItr.next(); + pd.mapRegionToParamObject( hrnA, paramIndex ); + } + } + + // report parameter-reachable mappings + mapItr = pi2r.entrySet().iterator(); + while( mapItr.hasNext() ) { + Map.Entry me = (Map.Entry) mapItr.next(); + Integer paramIndex = (Integer) me.getKey(); + Set hrnRset = (Set) me.getValue(); + + Iterator hrnItr = hrnRset.iterator(); + while( hrnItr.hasNext() ) { + HeapRegionNode hrnR = hrnItr.next(); + pd.mapRegionToParamReachable( hrnR, paramIndex ); + } + } + + // and we're done in this method for special param decomp mode + return; + } + + + // now iterate over reachable nodes to rewrite their alpha, and + // classify edges found for beta rewrite + Hashtable tokens2states = new Hashtable(); + + Hashtable< Integer, Set > edges_p2p = new Hashtable< Integer, Set >(); + Hashtable< Integer, Set > edges_p2s = new Hashtable< Integer, Set >(); + Hashtable< Integer, Set > edges_s2p = new Hashtable< Integer, Set >(); + Hashtable< Integer, Set > edges_s2s = new Hashtable< Integer, Set >(); + Hashtable< Integer, Set > edges_up_dr = new Hashtable< Integer, Set >(); + Hashtable< Integer, Set > edges_up_r = new Hashtable< Integer, Set >(); + + + // so again, with respect to some arg i... + lnArgItr = paramIndex2ln.entrySet().iterator(); + while( lnArgItr.hasNext() ) { + Map.Entry me = (Map.Entry) lnArgItr.next(); + Integer index = (Integer) me.getKey(); + LabelNode lnArg_i = (LabelNode) me.getValue(); + + TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get( index ); + TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get( index ); + assert p_i != null; + + ensureEmptyEdgeIndexPair( edges_p2p, index ); + ensureEmptyEdgeIndexPair( edges_p2s, index ); + ensureEmptyEdgeIndexPair( edges_s2p, index ); + ensureEmptyEdgeIndexPair( edges_s2s, index ); + ensureEmptyEdgeIndexPair( edges_up_dr, index ); + ensureEmptyEdgeIndexPair( edges_up_r, index ); + + Set dr = pi2dr.get( index ); + Iterator hrnItr = dr.iterator(); while( hrnItr.hasNext() ) { + // this heap region is definitely an "a_i" or primary by virtue of being in dr HeapRegionNode hrn = hrnItr.next(); - rewriteCallerNodeAlpha(fm.numParameters(), - index, - hrn, - paramIndex2rewriteH, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar); + tokens2states.clear(); + tokens2states.put( p_i, hrn.getAlpha() ); + + rewriteCallerReachability( index, + hrn, + null, + paramIndex2rewriteH_p.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); - nodesWithNewAlpha.add(hrn); + nodesWithNewAlpha.add( hrn ); - // look at all incoming edges to the reachable nodes - // and sort them as edges reachable from the argument - // label node, or upstream edges + // sort edges Iterator edgeItr = hrn.iteratorToReferencers(); while( edgeItr.hasNext() ) { ReferenceEdge edge = edgeItr.next(); + OwnershipNode on = edge.getSrc(); + + boolean edge_classified = false; + - OwnershipNode on = edge.getSrc(); + if( on instanceof HeapRegionNode ) { + // hrn0 may be "a_j" and/or "r_j" or even neither + HeapRegionNode hrn0 = (HeapRegionNode) on; - if( on instanceof LabelNode ) { + Iterator itr = pi2dr.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry mo = (Map.Entry) itr.next(); + Integer pi = (Integer) mo.getKey(); + Set dr_i = (Set) mo.getValue(); - LabelNode ln0 = (LabelNode) on; - if( ln0.equals(lnArg_i) ) { - edgesReachable.add(edge); - } else { - edgesUpstream.add(edge); + if( dr_i.contains( hrn0 ) ) { + addEdgeIndexPair( edges_p2p, pi, edge, index ); + edge_classified = true; + } } - } else { + itr = pi2r.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry mo = (Map.Entry) itr.next(); + Integer pi = (Integer) mo.getKey(); + Set r_i = (Set) mo.getValue(); + + if( r_i.contains( hrn0 ) ) { + addEdgeIndexPair( edges_s2p, pi, edge, index ); + edge_classified = true; + } + } + } + + // all of these edges are upstream of directly reachable objects + if( !edge_classified ) { + addEdgeIndexPair( edges_up_dr, index, edge, index ); + } + } + } + + + Set r = pi2r.get( index ); + hrnItr = r.iterator(); + while( hrnItr.hasNext() ) { + // this heap region is definitely an "r_i" or secondary by virtue of being in r + HeapRegionNode hrn = hrnItr.next(); + + if( paramIndex2rewriteH_s.containsKey( index ) ) { + + tokens2states.clear(); + tokens2states.put( p_i, new ReachabilitySet().makeCanonical() ); + tokens2states.put( s_i, hrn.getAlpha() ); + + rewriteCallerReachability( index, + hrn, + null, + paramIndex2rewriteH_s.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); + + nodesWithNewAlpha.add( hrn ); + } + + // sort edges + Iterator edgeItr = hrn.iteratorToReferencers(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + OwnershipNode on = edge.getSrc(); + boolean edge_classified = false; + + if( on instanceof HeapRegionNode ) { + // hrn0 may be "a_j" and/or "r_j" or even neither HeapRegionNode hrn0 = (HeapRegionNode) on; - if( reachableNodes.contains(hrn0) ) { - edgesReachable.add(edge); - } else { - edgesUpstream.add(edge); + + Iterator itr = pi2dr.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry mo = (Map.Entry) itr.next(); + Integer pi = (Integer) mo.getKey(); + Set dr_i = (Set) mo.getValue(); + + if( dr_i.contains( hrn0 ) ) { + addEdgeIndexPair( edges_p2s, pi, edge, index ); + edge_classified = true; + } + } + + itr = pi2r.entrySet().iterator(); + while( itr.hasNext() ) { + Map.Entry mo = (Map.Entry) itr.next(); + Integer pi = (Integer) mo.getKey(); + Set r_i = (Set) mo.getValue(); + + if( r_i.contains( hrn0 ) ) { + addEdgeIndexPair( edges_s2s, pi, edge, index ); + edge_classified = true; + } } } + + // these edges are all upstream of some reachable node + if( !edge_classified ) { + addEdgeIndexPair( edges_up_r, index, edge, index ); + } } } + } + + + // and again, with respect to some arg i... + lnArgItr = paramIndex2ln.entrySet().iterator(); + while( lnArgItr.hasNext() ) { + Map.Entry me = (Map.Entry) lnArgItr.next(); + Integer index = (Integer) me.getKey(); + LabelNode lnArg_i = (LabelNode) me.getValue(); + // update reachable edges - Iterator edgeReachableItr = edgesReachable.iterator(); - while( edgeReachableItr.hasNext() ) { - ReferenceEdge edgeReachable = edgeReachableItr.next(); + Iterator edgeItr = edges_p2p.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); + + if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index, + indexJ, + edge.getField() ) ) ) { + continue; + } + + TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ ); + assert p_j != null; + + tokens2states.clear(); + tokens2states.put( p_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteJ_p2p.get( makeMapKey( index, + indexJ, + edge.getField() ) ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); + + edgesWithNewBeta.add( edge ); + } + + + edgeItr = edges_p2s.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); + + if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index, + edge.getField() ) ) ) { + continue; + } + + TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ ); + assert s_j != null; + + tokens2states.clear(); + tokens2states.put( s_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteJ_p2s.get( makeMapKey( index, + edge.getField() ) ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); + + edgesWithNewBeta.add( edge ); + } + - rewriteCallerEdgeBeta(fm.numParameters(), - index, - edgeReachable, - paramIndex2rewriteJ, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar, - false, - null); + edgeItr = edges_s2p.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); + + if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) { + continue; + } + + TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ ); + assert p_j != null; + + tokens2states.clear(); + tokens2states.put( p_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteJ_s2p.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); + + edgesWithNewBeta.add( edge ); + } + + + edgeItr = edges_s2s.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); + + if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) { + continue; + } + + TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ ); + assert s_j != null; + + tokens2states.clear(); + tokens2states.put( s_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteJ_s2s.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); + + edgesWithNewBeta.add( edge ); + } + + + // update directly upstream edges + Hashtable edgeUpstreamPlannedChanges = + new Hashtable(); + + HashSet edgesDirectlyUpstream = + new HashSet(); - edgesWithNewBeta.add(edgeReachable); + edgeItr = edges_up_dr.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); + + edgesDirectlyUpstream.add( edge ); + + TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ ); + assert p_j != null; + + // start with K_p2 and p_j + tokens2states.clear(); + tokens2states.put( p_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteK_p2.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + true, + edgeUpstreamPlannedChanges ); + + // and add in s_j, if required, and do K_p + TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ ); + if( s_j != null ) { + tokens2states.put( s_j, edge.getBeta() ); + } + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteK_p.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + true, + edgeUpstreamPlannedChanges ); + + edgesWithNewBeta.add( edge ); } + propagateTokensOverEdges( edgesDirectlyUpstream, + edgeUpstreamPlannedChanges, + edgesWithNewBeta ); + + // update upstream edges - Hashtable edgeUpstreamPlannedChanges - = new Hashtable(); + edgeUpstreamPlannedChanges = + new Hashtable(); + + HashSet edgesUpstream = + new HashSet(); + + edgeItr = edges_up_r.get( index ).iterator(); + while( edgeItr.hasNext() ) { + Vector mo = (Vector) edgeItr.next(); + ReferenceEdge edge = (ReferenceEdge) mo.get( 0 ); + Integer indexJ = (Integer) mo.get( 1 ); - Iterator edgeUpstreamItr = edgesUpstream.iterator(); - while( edgeUpstreamItr.hasNext() ) { - ReferenceEdge edgeUpstream = edgeUpstreamItr.next(); + if( !paramIndex2rewriteK_s.containsKey( index ) ) { + continue; + } + + edgesUpstream.add( edge ); + + TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get( indexJ ); + assert p_j != null; - rewriteCallerEdgeBeta(fm.numParameters(), - index, - edgeUpstream, - paramIndex2rewriteK, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar, - true, - edgeUpstreamPlannedChanges); + TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get( indexJ ); + assert s_j != null; - edgesWithNewBeta.add(edgeUpstream); + tokens2states.clear(); + tokens2states.put( p_j, rsWttsEmpty ); + tokens2states.put( s_j, edge.getBeta() ); + + rewriteCallerReachability( index, + null, + edge, + paramIndex2rewriteK_s.get( index ), + tokens2states, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + true, + edgeUpstreamPlannedChanges ); + + edgesWithNewBeta.add( edge ); } - propagateTokensOverEdges(edgesUpstream, - edgeUpstreamPlannedChanges, - edgesWithNewBeta); - } + propagateTokensOverEdges( edgesUpstream, + edgeUpstreamPlannedChanges, + edgesWithNewBeta ); + + } // end effects per argument/parameter map // commit changes to alpha and beta @@ -1164,40 +2643,47 @@ public class OwnershipGraph { edgeItr.next().applyBetaNew(); } - + // verify the existence of allocation sites and their // shadows from the callee in the context of this caller graph // then map allocated nodes of callee onto the caller shadows // of them + Hashtable tokens2statesEmpty = new Hashtable(); + Iterator asItr = ogCallee.allocationSites.iterator(); while( asItr.hasNext() ) { AllocationSite allocSite = asItr.next(); - HeapRegionNode hrnSummary = getSummaryNode(allocSite); + + // grab the summary in the caller just to make sure + // the allocation site has nodes in the caller + HeapRegionNode hrnSummary = getSummaryNode( allocSite ); // assert that the shadow nodes have no reference edges // because they're brand new to the graph, or last time // they were used they should have been cleared of edges - HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite); + HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite ); assert hrnShadowSummary.getNumReferencers() == 0; assert hrnShadowSummary.getNumReferencees() == 0; // then bring g_ij onto g'_ij and rewrite - transferOnto(hrnSummary, hrnShadowSummary); - - HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite); - hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) ); + HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite ); + hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) ); // shadow nodes only are touched by a rewrite one time, // so rewrite and immediately commit--and they don't belong // to a particular parameter, so use a bogus param index // that pulls a self-rewrite out of H - rewriteCallerNodeAlpha(fm.numParameters(), - bogusIndex, - hrnShadowSummary, - paramIndex2rewriteH, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar); + rewriteCallerReachability( bogusIndex, + hrnShadowSummary, + null, + funcScriptR( hrnShadowSummary.getAlpha(), ogCallee, mc ), + tokens2statesEmpty, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); hrnShadowSummary.applyAlphaNew(); @@ -1213,19 +2699,21 @@ public class OwnershipGraph { assert hrnIthShadow.getNumReferencers() == 0; assert hrnIthShadow.getNumReferencees() == 0; - transferOnto(hrnIth, hrnIthShadow); - assert ogCallee.id2hrn.containsKey(idIth); HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth); hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) ); - rewriteCallerNodeAlpha(fm.numParameters(), - bogusIndex, - hrnIthShadow, - paramIndex2rewriteH, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar); + rewriteCallerReachability( bogusIndex, + hrnIthShadow, + null, + funcScriptR( hrnIthShadow.getAlpha(), ogCallee, mc ), + tokens2statesEmpty, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); hrnIthShadow.applyAlphaNew(); } @@ -1235,21 +2723,21 @@ public class OwnershipGraph { // for every heap region->heap region edge in the // callee graph, create the matching edge or edges // in the caller graph - Set sCallee = ogCallee.id2hrn.entrySet(); + Set sCallee = ogCallee.id2hrn.entrySet(); Iterator iCallee = sCallee.iterator(); while( iCallee.hasNext() ) { - Map.Entry meCallee = (Map.Entry)iCallee.next(); - Integer idCallee = (Integer) meCallee.getKey(); + Map.Entry meCallee = (Map.Entry) iCallee.next(); + Integer idCallee = (Integer) meCallee.getKey(); HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue(); Iterator heapRegionsItrCallee = hrnCallee.iteratorToReferencees(); while( heapRegionsItrCallee.hasNext() ) { - ReferenceEdge edgeCallee = heapRegionsItrCallee.next(); + ReferenceEdge edgeCallee = heapRegionsItrCallee.next(); HeapRegionNode hrnChildCallee = edgeCallee.getDst(); - Integer idChildCallee = hrnChildCallee.getID(); + Integer idChildCallee = hrnChildCallee.getID(); - // only address this edge if it is not a special reflexive edge - if( !edgeCallee.isInitialParamReflexive() ) { + // only address this edge if it is not a special initial edge + if( !edgeCallee.isInitialParam() ) { // now we know that in the callee method's ownership graph // there is a heap region->heap region reference edge given @@ -1261,21 +2749,30 @@ public class OwnershipGraph { // make the edge with src and dst so beta info is // calculated once, then copy it for each new edge in caller - ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null, - null, - edgeCallee.getFieldDesc(), - false, - toShadowTokens(ogCallee, edgeCallee.getBeta() ) - ); - rewriteCallerEdgeBeta(fm.numParameters(), - bogusIndex, - edgeNewInCallerTemplate, - paramIndex2rewriteJ, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar, - false, - null); + + ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null, + null, + edgeCallee.getType(), + edgeCallee.getField(), + false, + funcScriptR( toShadowTokens( ogCallee, + edgeCallee.getBeta() + ), + ogCallee, + mc ) + ); + + rewriteCallerReachability( bogusIndex, + null, + edgeNewInCallerTemplate, + edgeNewInCallerTemplate.getBeta(), + tokens2statesEmpty, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); edgeNewInCallerTemplate.applyBetaNew(); @@ -1284,22 +2781,23 @@ public class OwnershipGraph { // and a set of destination heaps in the caller graph, and make // a reference edge in the caller for every possible (src,dst) pair HashSet possibleCallerSrcs = - getHRNSetThatPossiblyMapToCalleeHRN(ogCallee, - (HeapRegionNode) edgeCallee.getSrc(), - paramIndex2reachableCallerNodes); + getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, + (HeapRegionNode) edgeCallee.getSrc(), + pi2dr, + pi2r ); HashSet possibleCallerDsts = - getHRNSetThatPossiblyMapToCalleeHRN(ogCallee, - edgeCallee.getDst(), - paramIndex2reachableCallerNodes); - + getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, + edgeCallee.getDst(), + pi2dr, + pi2r ); // make every possible pair of {srcSet} -> {dstSet} edges in the caller Iterator srcItr = possibleCallerSrcs.iterator(); while( srcItr.hasNext() ) { HeapRegionNode src = (HeapRegionNode) srcItr.next(); - if( !hasMatchingField(src, edgeCallee) ) { + if( !hasMatchingField( src, edgeCallee ) ) { // prune this source node possibility continue; } @@ -1308,23 +2806,44 @@ public class OwnershipGraph { while( dstItr.hasNext() ) { HeapRegionNode dst = (HeapRegionNode) dstItr.next(); - if( !hasMatchingType(edgeCallee, dst) ) { + if( !hasMatchingType( edgeCallee, dst ) ) { // prune continue; } // otherwise the caller src and dst pair can match the edge, so make it ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy(); - edgeNewInCaller.setSrc(src); - edgeNewInCaller.setDst(dst); + edgeNewInCaller.setSrc( src ); + edgeNewInCaller.setDst( dst ); + + // handle taint info if callee created this edge + // added by eom + Set pParamSet=idPrimary2paramIndexSet.get(dst.getID()); + Set sParamSet=idSecondary2paramIndexSet.get(dst.getID()); + HashSet paramSet=new HashSet(); + if(pParamSet!=null){ + paramSet.addAll(pParamSet); + } + if(sParamSet!=null){ + paramSet.addAll(sParamSet); + } + Iterator paramIter=paramSet.iterator(); + int newTaintIdentifier=0; + while(paramIter.hasNext()){ + Integer paramIdx=paramIter.next(); + edgeNewInCaller.tainedBy(paramIdx); + } - ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() ); + ReferenceEdge edgeExisting = src.getReferenceTo( dst, + edgeNewInCaller.getType(), + edgeNewInCaller.getField() ); if( edgeExisting == null ) { // if this edge doesn't exist in the caller, create it - addReferenceEdge(src, dst, edgeNewInCaller); + addReferenceEdge( src, dst, edgeNewInCaller ); + } else { // if it already exists, merge with it - edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) ); + edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) ); } } } @@ -1334,68 +2853,87 @@ public class OwnershipGraph { // return value may need to be assigned in caller - if( fc.getReturnTemp() != null ) { + TempDescriptor returnTemp = fc.getReturnTemp(); + if( returnTemp != null && !returnTemp.getType().isImmutable() ) { - LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() ); - clearReferenceEdgesFrom(lnLhsCaller, null, true); + LabelNode lnLhsCaller = getLabelNodeFromTemp( returnTemp ); + clearReferenceEdgesFrom( lnLhsCaller, null, null, true ); - LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn); + LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp( tdReturn ); Iterator edgeCalleeItr = lnReturnCallee.iteratorToReferencees(); while( edgeCalleeItr.hasNext() ) { ReferenceEdge edgeCallee = edgeCalleeItr.next(); - ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null, - null, - edgeCallee.getFieldDesc(), - false, - toShadowTokens(ogCallee, edgeCallee.getBeta() ) - ); - rewriteCallerEdgeBeta(fm.numParameters(), - bogusIndex, - edgeNewInCallerTemplate, - paramIndex2rewriteJ, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar, - false, - null); + ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null, + null, + edgeCallee.getType(), + edgeCallee.getField(), + false, + funcScriptR( toShadowTokens(ogCallee, + edgeCallee.getBeta() ), + ogCallee, + mc ) + ); + rewriteCallerReachability( bogusIndex, + null, + edgeNewInCallerTemplate, + edgeNewInCallerTemplate.getBeta(), + tokens2statesEmpty, + paramIndex2rewrite_d_p, + paramIndex2rewrite_d_s, + paramIndex2rewriteD, + ogCallee, + false, + null ); edgeNewInCallerTemplate.applyBetaNew(); HashSet assignCallerRhs = - getHRNSetThatPossiblyMapToCalleeHRN(ogCallee, - edgeCallee.getDst(), - paramIndex2reachableCallerNodes); + getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, + edgeCallee.getDst(), + pi2dr, + pi2r ); Iterator itrHrn = assignCallerRhs.iterator(); while( itrHrn.hasNext() ) { HeapRegionNode hrnCaller = itrHrn.next(); - if( !hasMatchingType(edgeCallee, hrnCaller) ) { + if( !hasMatchingType( edgeCallee, hrnCaller ) ) { // prune continue; } // otherwise caller node can match callee edge, so make it ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy(); - edgeNewInCaller.setSrc(lnLhsCaller); - edgeNewInCaller.setDst(hrnCaller); + edgeNewInCaller.setSrc( lnLhsCaller ); + edgeNewInCaller.setDst( hrnCaller ); - ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() ); + ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo( hrnCaller, + edgeNewInCaller.getType(), + edgeNewInCaller.getField() ); if( edgeExisting == null ) { // if this edge doesn't exist in the caller, create it - addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller); + addReferenceEdge( lnLhsCaller, hrnCaller, edgeNewInCaller ); } else { // if it already exists, merge with it - edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) ); + edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) ); } } } } + if( mc.getDescriptor().getSymbol().equals( debugCaller ) && + fm.getMethod().getSymbol().equals( debugCallee ) ) { + try { + writeGraph( "debug7JustBeforeMergeToKCapacity", true, true, true, false, false ); + } catch( IOException e ) {} + } + + + // merge the shadow nodes of allocation sites back down to normal capacity Iterator allocItr = ogCallee.allocationSites.iterator(); while( allocItr.hasNext() ) { @@ -1403,92 +2941,138 @@ public class OwnershipGraph { // first age each allocation site enough times to make room for the shadow nodes for( int i = 0; i < as.getAllocationDepth(); ++i ) { - age(as); + age( as ); } // then merge the shadow summary into the normal summary - HeapRegionNode hrnSummary = getSummaryNode(as); + HeapRegionNode hrnSummary = getSummaryNode( as ); assert hrnSummary != null; - HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as); + HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as ); assert hrnSummaryShadow != null; - mergeIntoSummary(hrnSummaryShadow, hrnSummary); + mergeIntoSummary( hrnSummaryShadow, hrnSummary ); // then clear off after merge - clearReferenceEdgesFrom(hrnSummaryShadow, null, true); - clearReferenceEdgesTo(hrnSummaryShadow, null, true); - hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() ); + clearReferenceEdgesFrom( hrnSummaryShadow, null, null, true ); + clearReferenceEdgesTo ( hrnSummaryShadow, null, null, true ); + hrnSummaryShadow.setAlpha( new ReachabilitySet().makeCanonical() ); // then transplant shadow nodes onto the now clean normal nodes for( int i = 0; i < as.getAllocationDepth(); ++i ) { - Integer idIth = as.getIthOldest(i); - HeapRegionNode hrnIth = id2hrn.get(idIth); - - Integer idIthShadow = as.getIthOldestShadow(i); - HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow); + Integer idIth = as.getIthOldest( i ); + HeapRegionNode hrnIth = id2hrn.get( idIth ); + Integer idIthShadow = as.getIthOldestShadow( i ); + HeapRegionNode hrnIthShadow = id2hrn.get( idIthShadow ); - transferOnto(hrnIthShadow, hrnIth); + transferOnto( hrnIthShadow, hrnIth ); // clear off shadow nodes after transfer - clearReferenceEdgesFrom(hrnIthShadow, null, true); - clearReferenceEdgesTo(hrnIthShadow, null, true); - hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() ); + clearReferenceEdgesFrom( hrnIthShadow, null, null, true ); + clearReferenceEdgesTo ( hrnIthShadow, null, null, true ); + hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() ); } // finally, globally change shadow tokens into normal tokens Iterator itrAllLabelNodes = td2ln.entrySet().iterator(); while( itrAllLabelNodes.hasNext() ) { - Map.Entry me = (Map.Entry)itrAllLabelNodes.next(); + Map.Entry me = (Map.Entry) itrAllLabelNodes.next(); LabelNode ln = (LabelNode) me.getValue(); Iterator itrEdges = ln.iteratorToReferencees(); while( itrEdges.hasNext() ) { - unshadowTokens(as, itrEdges.next() ); + unshadowTokens( as, itrEdges.next() ); + } + } + + Iterator itrAllHRNodes = id2hrn.entrySet().iterator(); + while( itrAllHRNodes.hasNext() ) { + Map.Entry me = (Map.Entry) itrAllHRNodes.next(); + HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue(); + + unshadowTokens( as, hrnToAge ); + + Iterator itrEdges = hrnToAge.iteratorToReferencees(); + while( itrEdges.hasNext() ) { + unshadowTokens( as, itrEdges.next() ); } } + } + + + if( mc.getDescriptor().getSymbol().equals( debugCaller ) && + fm.getMethod().getSymbol().equals( debugCallee ) ) { + try { + writeGraph( "debug8JustBeforeSweep", true, true, true, false, false ); + } catch( IOException e ) {} + } - Iterator itrAllHRNodes = id2hrn.entrySet().iterator(); - while( itrAllHRNodes.hasNext() ) { - Map.Entry me = (Map.Entry)itrAllHRNodes.next(); - HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue(); - unshadowTokens(as, hrnToAge); + // improve reachability as much as possible + globalSweep(); - Iterator itrEdges = hrnToAge.iteratorToReferencees(); - while( itrEdges.hasNext() ) { - unshadowTokens(as, itrEdges.next() ); - } + + + if( mc.getDescriptor().getSymbol().equals( debugCaller ) && + fm.getMethod().getSymbol().equals( debugCallee ) ) { + try { + writeGraph( "debug9endResolveCall", true, true, true, false, false ); + } catch( IOException e ) {} + System.out.println( " "+mc+" done calling "+fm ); + ++x; + if( x > 2 ) { + System.exit( -1 ); } } } + static int x = 0; + protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) { - // if no allocation site, then it's a match-everything region - AllocationSite asSrc = src.getAllocationSite(); - if( asSrc == null ) { + // if no type, then it's a match-everything region + TypeDescriptor tdSrc = src.getType(); + if( tdSrc == null ) { return true; } - TypeDescriptor tdSrc = asSrc.getType(); - assert tdSrc != null; + if( tdSrc.isArray() ) { + TypeDescriptor td = edge.getType(); + assert td != null; + + TypeDescriptor tdSrcDeref = tdSrc.dereference(); + assert tdSrcDeref != null; + + if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) { + return false; + } + + return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName ); + } // if it's not a class, it doesn't have any fields to match if( !tdSrc.isClass() ) { return false; } - Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields(); - while( fieldsSrcItr.hasNext() ) { - FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next(); - if( fd == edge.getFieldDesc() ) { - return true; + ClassDescriptor cd = tdSrc.getClassDesc(); + while( cd != null ) { + Iterator fieldItr = cd.getFields(); + + while( fieldItr.hasNext() ) { + FieldDescriptor fd = (FieldDescriptor) fieldItr.next(); + + if( fd.getType().equals( edge.getType() ) && + fd.getSymbol().equals( edge.getField() ) ) { + return true; + } } + + cd = cd.getSuperDesc(); } - + // otherwise it is a class with fields // but we didn't find a match return false; @@ -1496,32 +3080,27 @@ public class OwnershipGraph { protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) { - + // if the region has no type, matches everything - AllocationSite asDst = dst.getAllocationSite(); - if( asDst == null ) { + TypeDescriptor tdDst = dst.getType(); + if( tdDst == null ) { return true; } - TypeDescriptor tdDst = asDst.getType(); - assert tdDst != null; - - // if the type is not a class don't match because - // primitives are copied, no memory aliases + // if the type is not a class or an array, don't + // match because primitives are copied, no aliases ClassDescriptor cdDst = tdDst.getClassDesc(); - if( cdDst == null ) { + if( cdDst == null && !tdDst.isArray() ) { return false; } - // if the field is null, it matches everything - FieldDescriptor fd = edge.getFieldDesc(); - if( fd == null ) { + // if the edge type is null, it matches everything + TypeDescriptor tdEdge = edge.getType(); + if( tdEdge == null ) { return true; } - TypeDescriptor tdFd = fd.getType(); - assert tdFd != null; - return typeUtil.isSuperorType(tdFd, tdDst); + return typeUtil.isSuperorType(tdEdge, tdDst); } @@ -1538,7 +3117,7 @@ public class OwnershipGraph { private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee, ReachabilitySet rsIn) { - ReachabilitySet rsOut = new ReachabilitySet(rsIn); + ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical(); Iterator allocItr = ogCallee.allocationSites.iterator(); while( allocItr.hasNext() ) { @@ -1551,251 +3130,516 @@ public class OwnershipGraph { } - private void rewriteCallerNodeAlpha(int numParameters, - Integer paramIndex, - HeapRegionNode hrn, - Hashtable paramIndex2rewriteH, - Hashtable paramIndex2rewriteD, - Hashtable paramIndex2paramToken, - Hashtable paramIndex2paramTokenStar) { - - ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex); - assert rules != null; - - TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex); - assert tokenToRewrite != null; - - ReachabilitySet r0 = new ReachabilitySet().makeCanonical(); - Iterator ttsItr = rules.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - r0 = r0.union(tts.rewriteToken(tokenToRewrite, - hrn.getAlpha(), - false, - null) ); - } - - ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); - ttsItr = r0.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - r1 = r1.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); - } - - hrn.setAlphaNew(hrn.getAlphaNew().union(r1) ); - } - + private void rewriteCallerReachability(Integer paramIndex, + HeapRegionNode hrn, + ReferenceEdge edge, + ReachabilitySet rules, + Hashtable tokens2states, + Hashtable paramIndex2rewrite_d_p, + Hashtable paramIndex2rewrite_d_s, + Hashtable paramIndex2rewriteD, + OwnershipGraph ogCallee, + boolean makeChangeSet, + Hashtable edgePlannedChanges) { + + assert(hrn == null && edge != null) || + (hrn != null && edge == null); + + assert rules != null; + assert tokens2states != null; + + ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical(); + + // for initializing structures in this method + TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical(); + + // use this to construct a change set if required; the idea is to + // map every partially rewritten token tuple set to the set of + // caller-context token tuple sets that were used to generate it + Hashtable > rewritten2source = + new Hashtable >(); + rewritten2source.put( ttsEmpty, new HashSet() ); + + + Iterator rulesItr = rules.iterator(); + while(rulesItr.hasNext()) { + TokenTupleSet rule = rulesItr.next(); + + ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical(); + + Iterator ruleItr = rule.iterator(); + while(ruleItr.hasNext()) { + TokenTuple ttCallee = ruleItr.next(); + + // compute the possibilities for rewriting this callee token + ReachabilitySet ttCalleeRewrites = null; + boolean callerSourceUsed = false; + + if( tokens2states.containsKey( ttCallee ) ) { + callerSourceUsed = true; + ttCalleeRewrites = tokens2states.get( ttCallee ); + assert ttCalleeRewrites != null; + + } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey( ttCallee ) ) { + // use little d_p + Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get( ttCallee ); + assert paramIndex_j != null; + ttCalleeRewrites = paramIndex2rewrite_d_p.get( paramIndex_j ); + assert ttCalleeRewrites != null; + + } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey( ttCallee ) ) { + // use little d_s + Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get( ttCallee ); + assert paramIndex_j != null; + ttCalleeRewrites = paramIndex2rewrite_d_s.get( paramIndex_j ); + assert ttCalleeRewrites != null; + + } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey( ttCallee ) ) { + // worse, use big D + Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get( ttCallee ); + assert paramIndex_j != null; + ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j ); + assert ttCalleeRewrites != null; + + } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey( ttCallee ) ) { + // worse, use big D + Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get( ttCallee ); + assert paramIndex_j != null; + ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j ); + assert ttCalleeRewrites != null; - private void rewriteCallerEdgeBeta(int numParameters, - Integer paramIndex, - ReferenceEdge edge, - Hashtable paramIndex2rewriteJorK, - Hashtable paramIndex2rewriteD, - Hashtable paramIndex2paramToken, - Hashtable paramIndex2paramTokenStar, - boolean makeChangeSet, - Hashtable edgePlannedChanges) { + } else { + // otherwise there's no need for a rewrite, just pass this one on + TokenTupleSet ttsCaller = new TokenTupleSet( ttCallee ).makeCanonical(); + ttCalleeRewrites = new ReachabilitySet( ttsCaller ).makeCanonical(); + } - ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex); - assert rules != null; + // branch every version of the working rewritten rule with + // the possibilities for rewriting the current callee token + ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical(); - TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex); - assert tokenToRewrite != null; + Iterator rewrittenRuleItr = rewrittenRule.iterator(); + while( rewrittenRuleItr.hasNext() ) { + TokenTupleSet ttsRewritten = rewrittenRuleItr.next(); - ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical(); + Iterator ttCalleeRewritesItr = ttCalleeRewrites.iterator(); + while( ttCalleeRewritesItr.hasNext() ) { + TokenTupleSet ttsBranch = ttCalleeRewritesItr.next(); - Iterator ttsItr = rules.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); + TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch ); - Hashtable > forChangeSet = - new Hashtable >(); + if( makeChangeSet ) { + // in order to keep the list of source token tuple sets + // start with the sets used to make the partially rewritten + // rule up to this point + HashSet sourceSets = rewritten2source.get( ttsRewritten ); + assert sourceSets != null; - ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite, - edge.getBeta(), - true, - forChangeSet); + // make a shallow copy for possible modification + sourceSets = (HashSet) sourceSets.clone(); - Iterator fcsItr = forChangeSet.entrySet().iterator(); - while( fcsItr.hasNext() ) { - Map.Entry me = (Map.Entry)fcsItr.next(); - TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey(); - HashSet ttsAddSet = (HashSet) me.getValue(); - Iterator ttsAddItr = ttsAddSet.iterator(); - while( ttsAddItr.hasNext() ) { - TokenTupleSet ttsAdd = ttsAddItr.next(); + // if we used something from the caller to rewrite it, remember + if( callerSourceUsed ) { + sourceSets.add( ttsBranch ); + } - ChangeTuple ct = new ChangeTuple(ttsMatch, - ttsAdd - ).makeCanonical(); + // set mapping for the further rewritten rule + rewritten2source.put( ttsRewrittenNext, sourceSets ); + } - cts0 = cts0.union(ct); + rewrittenRuleWithTTCallee = + rewrittenRuleWithTTCallee.union( ttsRewrittenNext ); + } } - } - } - - ReachabilitySet r1 = new ReachabilitySet().makeCanonical(); - ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical(); - - Iterator ctItr = cts0.iterator(); - while( ctItr.hasNext() ) { - ChangeTuple ct = ctItr.next(); - - ReachabilitySet rTemp = rewriteDpass(numParameters, - paramIndex, - ct.getSetToAdd(), - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar - ).makeCanonical(); - r1 = r1.union(rTemp); - - if( makeChangeSet ) { - assert edgePlannedChanges != null; - - Iterator ttsTempItr = rTemp.iterator(); - while( ttsTempItr.hasNext() ) { - TokenTupleSet tts = ttsTempItr.next(); - - ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(), - tts - ).makeCanonical(); - - cts1 = cts1.union(ctFinal); - } + // now the rewritten rule's possibilities have been extended by + // rewriting the current callee token, remember result + rewrittenRule = rewrittenRuleWithTTCallee; } + + // the rule has been entirely rewritten into the caller context + // now, so add it to the new reachability information + callerReachabilityNew = + callerReachabilityNew.union( rewrittenRule ); } if( makeChangeSet ) { - edgePlannedChanges.put(edge, cts1); - } - - edge.setBetaNew(edge.getBetaNew().union(r1) ); - } - - - private ReachabilitySet rewriteDpass(int numParameters, - Integer paramIndex, - TokenTupleSet ttsIn, - Hashtable paramIndex2rewriteD, - Hashtable paramIndex2paramToken, - Hashtable paramIndex2paramTokenStar) { - - ReachabilitySet rsOut = new ReachabilitySet().makeCanonical(); - - boolean rewritten = false; - - for( int j = 0; j < numParameters; ++j ) { - Integer paramIndexJ = new Integer(j); - ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ); - assert D_j != null; - - if( paramIndexJ != paramIndex ) { - TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ); - assert tokenToRewriteJ != null; - if( ttsIn.containsTuple(tokenToRewriteJ) ) { - ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ, - D_j, - false, - null); - Iterator ttsItr = r.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - rsOut = rsOut.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); - rewritten = true; - } + ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical(); + + // each possibility for the final reachability should have a set of + // caller sources mapped to it, use to create the change set + Iterator callerReachabilityItr = callerReachabilityNew.iterator(); + while( callerReachabilityItr.hasNext() ) { + TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next(); + HashSet sourceSets = rewritten2source.get( ttsRewrittenFinal ); + assert sourceSets != null; + + Iterator sourceSetsItr = sourceSets.iterator(); + while( sourceSetsItr.hasNext() ) { + TokenTupleSet ttsSource = sourceSetsItr.next(); + + callerChangeSet = + callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) ); } } - TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ); - assert tokenStarToRewriteJ != null; - if( ttsIn.containsTuple(tokenStarToRewriteJ) ) { - ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ, - D_j, - false, - null); - Iterator ttsItr = r.iterator(); - while( ttsItr.hasNext() ) { - TokenTupleSet tts = ttsItr.next(); - rsOut = rsOut.union(rewriteDpass(numParameters, - paramIndex, - tts, - paramIndex2rewriteD, - paramIndex2paramToken, - paramIndex2paramTokenStar) ); - rewritten = true; - } - } + assert edgePlannedChanges != null; + edgePlannedChanges.put( edge, callerChangeSet ); } - if( !rewritten ) { - rsOut = rsOut.union(ttsIn); + if( hrn == null ) { + edge.setBetaNew( edge.getBetaNew().union( callerReachabilityNew ) ); + } else { + hrn.setAlphaNew( hrn.getAlphaNew().union( callerReachabilityNew ) ); } - - return rsOut; } - private HashSet - getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee, - HeapRegionNode hrnCallee, - Hashtable > paramIndex2reachableCallerNodes - ) { + private HashSet + getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee, + HeapRegionNode hrnCallee, + Hashtable > pi2dr, + Hashtable > pi2r + ) { + HashSet possibleCallerHRNs = new HashSet(); - Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() ); + Set paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet .get( hrnCallee.getID() ); + Set paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get( hrnCallee.getID() ); - if( paramIndexCallee == null ) { - // this is a node allocated in the callee then and it has + if( paramIndicesCallee_p == null && + paramIndicesCallee_s == null ) { + // this is a node allocated in the callee and it has // exactly one shadow node in the caller to map to AllocationSite as = hrnCallee.getAllocationSite(); assert as != null; - int age = as.getAgeCategory(hrnCallee.getID() ); + int age = as.getAgeCategory( hrnCallee.getID() ); assert age != AllocationSite.AGE_notInThisSite; Integer idCaller; if( age == AllocationSite.AGE_summary ) { idCaller = as.getSummaryShadow(); + } else if( age == AllocationSite.AGE_oldest ) { idCaller = as.getOldestShadow(); + } else { assert age == AllocationSite.AGE_in_I; - Integer I = as.getAge(hrnCallee.getID() ); + Integer I = as.getAge( hrnCallee.getID() ); assert I != null; - idCaller = as.getIthOldestShadow(I); + idCaller = as.getIthOldestShadow( I ); } - assert id2hrn.containsKey(idCaller); - HeapRegionNode hrnCaller = id2hrn.get(idCaller); - possibleCallerHRNs.add(hrnCaller); + assert id2hrn.containsKey( idCaller ); + possibleCallerHRNs.add( id2hrn.get( idCaller ) ); - } else { + return possibleCallerHRNs; + } + + // find out what primary objects this might be + if( paramIndicesCallee_p != null ) { // this is a node that was created to represent a parameter - // so it maps to a whole mess of heap regions - assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee); - possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee); + // so it maps to some regions directly reachable from the arg labels + Iterator itrIndex = paramIndicesCallee_p.iterator(); + while( itrIndex.hasNext() ) { + Integer paramIndexCallee = itrIndex.next(); + assert pi2dr.containsKey( paramIndexCallee ); + possibleCallerHRNs.addAll( pi2dr.get( paramIndexCallee ) ); + } } + // find out what secondary objects this might be + if( paramIndicesCallee_s != null ) { + // this is a node that was created to represent objs reachable from + // some parameter, so it maps to regions reachable from the arg labels + Iterator itrIndex = paramIndicesCallee_s.iterator(); + while( itrIndex.hasNext() ) { + Integer paramIndexCallee = itrIndex.next(); + assert pi2r.containsKey( paramIndexCallee ); + possibleCallerHRNs.addAll( pi2r.get( paramIndexCallee ) ); + } + } + + // TODO: is this true? + // one of the two cases above should have put something in here + //assert !possibleCallerHRNs.isEmpty(); + return possibleCallerHRNs; } + //////////////////////////////////////////////////// + // + // This global sweep is an optional step to prune + // reachability sets that are not internally + // consistent with the global graph. It should be + // invoked after strong updates or method calls. + // + //////////////////////////////////////////////////// + public void globalSweep() { + + // boldB is part of the phase 1 sweep + Hashtable< Integer, Hashtable > boldB = + new Hashtable< Integer, Hashtable >(); + + // visit every heap region to initialize alphaNew and calculate boldB + Set hrns = id2hrn.entrySet(); + Iterator itrHrns = hrns.iterator(); + while( itrHrns.hasNext() ) { + Map.Entry me = (Map.Entry)itrHrns.next(); + Integer token = (Integer) me.getKey(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + // assert that this node and incoming edges have clean alphaNew + // and betaNew sets, respectively + assert rsEmpty.equals( hrn.getAlphaNew() ); + + Iterator itrRers = hrn.iteratorToReferencers(); + while( itrRers.hasNext() ) { + ReferenceEdge edge = itrRers.next(); + assert rsEmpty.equals( edge.getBetaNew() ); + } + + // calculate boldB for this flagged node + if( hrn.isFlagged() || hrn.isParameter() ) { + + Hashtable boldB_f = + new Hashtable(); + + Set workSetEdges = new HashSet(); + + // initial boldB_f constraints + Iterator itrRees = hrn.iteratorToReferencees(); + while( itrRees.hasNext() ) { + ReferenceEdge edge = itrRees.next(); + + assert !boldB.containsKey( edge ); + boldB_f.put( edge, edge.getBeta() ); + + assert !workSetEdges.contains( edge ); + workSetEdges.add( edge ); + } + + // enforce the boldB_f constraint at edges until we reach a fixed point + while( !workSetEdges.isEmpty() ) { + ReferenceEdge edge = workSetEdges.iterator().next(); + workSetEdges.remove( edge ); + + Iterator itrPrime = edge.getDst().iteratorToReferencees(); + while( itrPrime.hasNext() ) { + ReferenceEdge edgePrime = itrPrime.next(); + + ReachabilitySet prevResult = boldB_f.get( edgePrime ); + ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() ); + + if( prevResult == null || + prevResult.union( intersection ).size() > prevResult.size() ) { + + if( prevResult == null ) { + boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) ); + } else { + boldB_f.put( edgePrime, prevResult .union( intersection ) ); + } + workSetEdges.add( edgePrime ); + } + } + } + + boldB.put( token, boldB_f ); + } + } + + + // use boldB to prune tokens from alpha states that are impossible + // and propagate the differences backwards across edges + HashSet edgesForPropagation = new HashSet(); + + Hashtable edgePlannedChanges = + new Hashtable(); + + hrns = id2hrn.entrySet(); + itrHrns = hrns.iterator(); + while( itrHrns.hasNext() ) { + Map.Entry me = (Map.Entry)itrHrns.next(); + Integer token = (Integer) me.getKey(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + // never remove the identity token from a flagged region + // because it is trivially satisfied + TokenTuple ttException = new TokenTuple( token, + !hrn.isSingleObject(), + TokenTuple.ARITY_ONE ).makeCanonical(); + + ChangeTupleSet cts = new ChangeTupleSet().makeCanonical(); + + // mark tokens for removal + Iterator stateItr = hrn.getAlpha().iterator(); + while( stateItr.hasNext() ) { + TokenTupleSet ttsOld = stateItr.next(); + + TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical(); + + Iterator ttItr = ttsOld.iterator(); + while( ttItr.hasNext() ) { + TokenTuple ttOld = ttItr.next(); + + // never remove the identity token from a flagged region + // because it is trivially satisfied + if( hrn.isFlagged() || hrn.isParameter() ) { + if( ttOld == ttException ) { + continue; + } + } + + // does boldB_ttOld allow this token? + boolean foundState = false; + Iterator incidentEdgeItr = hrn.iteratorToReferencers(); + while( incidentEdgeItr.hasNext() ) { + ReferenceEdge incidentEdge = incidentEdgeItr.next(); + + // if it isn't allowed, mark for removal + Integer idOld = ttOld.getToken(); + assert id2hrn.containsKey( idOld ); + Hashtable B = boldB.get( idOld ); + ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL! + if( boldB_ttOld_incident != null && + boldB_ttOld_incident.contains( ttsOld ) ) { + foundState = true; + } + } + + if( !foundState ) { + markedTokens = markedTokens.add( ttOld ); + } + } + + // if there is nothing marked, just move on + if( markedTokens.isEmpty() ) { + hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) ); + continue; + } + + // remove all marked tokens and establish a change set that should + // propagate backwards over edges from this node + TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical(); + ttItr = ttsOld.iterator(); + while( ttItr.hasNext() ) { + TokenTuple ttOld = ttItr.next(); + + if( !markedTokens.containsTuple( ttOld ) ) { + ttsPruned = ttsPruned.union( ttOld ); + } + } + assert !ttsOld.equals( ttsPruned ); + + hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) ); + ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical(); + cts = cts.union( ct ); + } + + // throw change tuple set on all incident edges + if( !cts.isEmpty() ) { + Iterator incidentEdgeItr = hrn.iteratorToReferencers(); + while( incidentEdgeItr.hasNext() ) { + ReferenceEdge incidentEdge = incidentEdgeItr.next(); + + edgesForPropagation.add( incidentEdge ); + + if( edgePlannedChanges.get( incidentEdge ) == null ) { + edgePlannedChanges.put( incidentEdge, cts ); + } else { + edgePlannedChanges.put( + incidentEdge, + edgePlannedChanges.get( incidentEdge ).union( cts ) + ); + } + } + } + } + + HashSet edgesUpdated = new HashSet(); + + propagateTokensOverEdges( edgesForPropagation, + edgePlannedChanges, + edgesUpdated ); + + // at the end of the 1st phase reference edges have + // beta, betaNew that correspond to beta and betaR + // + // commit beta<-betaNew, so beta=betaR and betaNew + // will represent the beta' calculation in 2nd phase + // + // commit alpha<-alphaNew because it won't change + HashSet res = new HashSet(); + + Iterator nodeItr = id2hrn.values().iterator(); + while( nodeItr.hasNext() ) { + HeapRegionNode hrn = nodeItr.next(); + hrn.applyAlphaNew(); + Iterator itrRes = hrn.iteratorToReferencers(); + while( itrRes.hasNext() ) { + res.add( itrRes.next() ); + } + } + + + // 2nd phase + Iterator edgeItr = res.iterator(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + HeapRegionNode hrn = edge.getDst(); + + // commit results of last phase + if( edgesUpdated.contains( edge ) ) { + edge.applyBetaNew(); + } + + // compute intial condition of 2nd phase + edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) ); + } + + // every edge in the graph is the initial workset + Set edgeWorkSet = (Set) res.clone(); + while( !edgeWorkSet.isEmpty() ) { + ReferenceEdge edgePrime = edgeWorkSet.iterator().next(); + edgeWorkSet.remove( edgePrime ); + + OwnershipNode on = edgePrime.getSrc(); + if( !(on instanceof HeapRegionNode) ) { + continue; + } + HeapRegionNode hrn = (HeapRegionNode) on; + + Iterator itrEdge = hrn.iteratorToReferencers(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + + ReachabilitySet prevResult = edge.getBetaNew(); + assert prevResult != null; + + ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() ); + + if( prevResult.union( intersection ).size() > prevResult.size() ) { + edge.setBetaNew( prevResult.union( intersection ) ); + edgeWorkSet.add( edge ); + } + } + } + + // commit beta' (beta<-betaNew) + edgeItr = res.iterator(); + while( edgeItr.hasNext() ) { + edgeItr.next().applyBetaNew(); + } + } + + + //////////////////////////////////////////////////// // in merge() and equals() methods the suffix A // represents the passed in graph and the suffix @@ -1812,7 +3656,7 @@ public class OwnershipGraph { mergeOwnershipNodes(og); mergeReferenceEdges(og); - mergeId2paramIndex(og); + mergeParamIndexMappings(og); mergeAllocationSites(og); } @@ -1886,8 +3730,9 @@ public class OwnershipGraph { // don't use the ReferenceEdge.equals() here because // we're talking about existence between graphs - if( idChildB.equals(idChildA) && - edgeB.getFieldDesc() == edgeA.getFieldDesc() ) { + if( idChildB.equals( idChildA ) && + edgeB.typeAndFieldEquals( edgeA ) ) { + edgeToMerge = edgeB; } } @@ -1910,8 +3755,10 @@ public class OwnershipGraph { edgeToMerge.setBeta( edgeToMerge.getBeta().union(edgeA.getBeta() ) ); - if( !edgeA.isInitialParamReflexive() ) { - edgeToMerge.setIsInitialParamReflexive(false); + //TODO eom + edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier()); + if( !edgeA.isInitialParam() ) { + edgeToMerge.setIsInitialParam(false); } } } @@ -1937,24 +3784,19 @@ public class OwnershipGraph { LabelNode lnB = td2ln.get(tdA); ReferenceEdge edgeToMerge = null; - // labels never have edges with a field - //assert edgeA.getFieldDesc() == null; - Iterator heapRegionsItrB = lnB.iteratorToReferencees(); while( heapRegionsItrB.hasNext() && edgeToMerge == null ) { - ReferenceEdge edgeB = heapRegionsItrB.next(); + ReferenceEdge edgeB = heapRegionsItrB.next(); HeapRegionNode hrnChildB = edgeB.getDst(); - Integer idChildB = hrnChildB.getID(); - - // labels never have edges with a field - //assert edgeB.getFieldDesc() == null; + Integer idChildB = hrnChildB.getID(); // don't use the ReferenceEdge.equals() here because // we're talking about existence between graphs - if( idChildB.equals(idChildA) && - edgeB.getFieldDesc() == edgeA.getFieldDesc() ) { + if( idChildB.equals( idChildA ) && + edgeB.typeAndFieldEquals( edgeA ) ) { + edgeToMerge = edgeB; } } @@ -1976,8 +3818,9 @@ public class OwnershipGraph { edgeToMerge.setBeta( edgeToMerge.getBeta().union(edgeA.getBeta() ) ); - if( !edgeA.isInitialParamReflexive() ) { - edgeToMerge.setIsInitialParamReflexive(false); + edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier()); + if( !edgeA.isInitialParam() ) { + edgeToMerge.setIsInitialParam(false); } } } @@ -1987,19 +3830,58 @@ public class OwnershipGraph { // you should only merge ownership graphs that have the // same number of parameters, or if one or both parameter // index tables are empty - protected void mergeId2paramIndex(OwnershipGraph og) { - if( id2paramIndex.size() == 0 ) { - id2paramIndex = og.id2paramIndex; - paramIndex2id = og.paramIndex2id; - paramIndex2tdQ = og.paramIndex2tdQ; + protected void mergeParamIndexMappings(OwnershipGraph og) { + + if( idPrimary2paramIndexSet.size() == 0 ) { + + idPrimary2paramIndexSet = og.idPrimary2paramIndexSet; + paramIndex2idPrimary = og.paramIndex2idPrimary; + + idSecondary2paramIndexSet = og.idSecondary2paramIndexSet; + paramIndex2idSecondary = og.paramIndex2idSecondary; + + paramIndex2tdQ = og.paramIndex2tdQ; + paramIndex2tdR = og.paramIndex2tdR; + + paramTokenPrimary2paramIndex = og.paramTokenPrimary2paramIndex; + paramIndex2paramTokenPrimary = og.paramIndex2paramTokenPrimary; + + paramTokenSecondary2paramIndex = og.paramTokenSecondary2paramIndex; + paramIndex2paramTokenSecondary = og.paramIndex2paramTokenSecondary; + paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex; + paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus; + paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex; + paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar; + return; } - if( og.id2paramIndex.size() == 0 ) { + if( og.idPrimary2paramIndexSet.size() == 0 ) { + + og.idPrimary2paramIndexSet = idPrimary2paramIndexSet; + og.paramIndex2idPrimary = paramIndex2idPrimary; + + og.idSecondary2paramIndexSet = idSecondary2paramIndexSet; + og.paramIndex2idSecondary = paramIndex2idSecondary; + + og.paramIndex2tdQ = paramIndex2tdQ; + og.paramIndex2tdR = paramIndex2tdR; + + og.paramTokenPrimary2paramIndex = paramTokenPrimary2paramIndex; + og.paramIndex2paramTokenPrimary = paramIndex2paramTokenPrimary; + + og.paramTokenSecondary2paramIndex = paramTokenSecondary2paramIndex; + og.paramIndex2paramTokenSecondary = paramIndex2paramTokenSecondary; + og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex; + og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus; + og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex; + og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar; + return; } - assert id2paramIndex.size() == og.id2paramIndex.size(); + assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size(); + assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size(); } protected void mergeAllocationSites(OwnershipGraph og) { @@ -2036,7 +3918,7 @@ public class OwnershipGraph { return false; } - if( !areId2paramIndexEqual(og) ) { + if( !areParamIndexMappingsEqual(og) ) { return false; } @@ -2210,16 +4092,13 @@ public class OwnershipGraph { HeapRegionNode hrnChildB = edgeB.getDst(); Integer idChildB = hrnChildB.getID(); - if( idChildA.equals(idChildB) && - edgeA.getFieldDesc() == edgeB.getFieldDesc() ) { + if( idChildA.equals( idChildB ) && + edgeA.typeAndFieldEquals( edgeB ) ) { // there is an edge in the right place with the right field, // but do they have the same attributes? if( edgeA.getBeta().equals(edgeB.getBeta() ) ) { - edgeFound = true; - //} else { - //return false; } } } @@ -2233,211 +4112,254 @@ public class OwnershipGraph { } - protected boolean areId2paramIndexEqual(OwnershipGraph og) { - return id2paramIndex.size() == og.id2paramIndex.size(); - } - + protected boolean areParamIndexMappingsEqual(OwnershipGraph og) { - public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) { + if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) { + return false; + } - // get parameter's heap region - assert paramIndex2id.containsKey(paramIndex1); - Integer idParam1 = paramIndex2id.get(paramIndex1); + if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) { + return false; + } - assert id2hrn.containsKey(idParam1); - HeapRegionNode hrnParam1 = id2hrn.get(idParam1); - assert hrnParam1 != null; + return true; + } - // get tokens for this parameter - TokenTuple p1 = new TokenTuple(hrnParam1.getID(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); - TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); + public Set hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) { + assert hrn1 != null; + assert hrn2 != null; + // then get the various tokens for these heap regions + TokenTuple h1 = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ONE).makeCanonical(); - // get tokens for the other parameter - assert paramIndex2id.containsKey(paramIndex2); - Integer idParam2 = paramIndex2id.get(paramIndex2); + TokenTuple h1plus = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ONEORMORE).makeCanonical(); - assert id2hrn.containsKey(idParam2); - HeapRegionNode hrnParam2 = id2hrn.get(idParam2); - assert hrnParam2 != null; + TokenTuple h1star = new TokenTuple(hrn1.getID(), + !hrn1.isSingleObject(), + TokenTuple.ARITY_ZEROORMORE).makeCanonical(); - TokenTuple p2 = new TokenTuple(hrnParam2.getID(), - true, + TokenTuple h2 = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), TokenTuple.ARITY_ONE).makeCanonical(); - TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); + TokenTuple h2plus = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), + TokenTuple.ARITY_ONEORMORE).makeCanonical(); + TokenTuple h2star = new TokenTuple(hrn2.getID(), + !hrn2.isSingleObject(), + TokenTuple.ARITY_ZEROORMORE).makeCanonical(); - // get special label p_q for first parameter - TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1); - assert tdParamQ1 != null; - LabelNode lnParamQ1 = td2ln.get(tdParamQ1); - assert lnParamQ1 != null; + // then get the merged beta of all out-going edges from these heap regions + ReachabilitySet beta1 = new ReachabilitySet().makeCanonical(); + Iterator itrEdge = hrn1.iteratorToReferencees(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + beta1 = beta1.union( edge.getBeta() ); + } - // then get the edge from label q to parameter's hrn - ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null); - assert edgeSpecialQ1 != null; + ReachabilitySet beta2 = new ReachabilitySet().makeCanonical(); + itrEdge = hrn2.iteratorToReferencees(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + beta2 = beta2.union( edge.getBeta() ); + } - // if the beta of this edge has tokens from both parameters in one - // token tuple set, then there is a potential alias between them - ReachabilitySet beta1 = edgeSpecialQ1.getBeta(); - assert beta1 != null; + boolean aliasDetected = false; - if( beta1.containsTupleSetWithBoth(p1, p2) ) { - return true; + // only do this one if they are different tokens + if( h1 != h2 && + beta1.containsTupleSetWithBoth(h1, h2) ) { + aliasDetected = true; } - if( beta1.containsTupleSetWithBoth(pStar1, p2) ) { - return true; + if( beta1.containsTupleSetWithBoth(h1plus, h2) ) { + aliasDetected = true; } - if( beta1.containsTupleSetWithBoth(p1, pStar2) ) { - return true; + if( beta1.containsTupleSetWithBoth(h1star, h2) ) { + aliasDetected = true; } - if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) { - return true; + if( beta1.containsTupleSetWithBoth(h1, h2plus) ) { + aliasDetected = true; + } + if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) { + aliasDetected = true; + } + if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) { + aliasDetected = true; + } + if( beta1.containsTupleSetWithBoth(h1, h2star) ) { + aliasDetected = true; + } + if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) { + aliasDetected = true; + } + if( beta1.containsTupleSetWithBoth(h1star, h2star) ) { + aliasDetected = true; } - return false; + if( h1 != h2 && + beta2.containsTupleSetWithBoth(h1, h2) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1, h2plus) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1, h2star) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) { + aliasDetected = true; + } + if( beta2.containsTupleSetWithBoth(h1star, h2star) ) { + aliasDetected = true; + } + + Set common = new HashSet(); + if( aliasDetected ) { + common = findCommonReachableNodes( hrn1, hrn2 ); + assert !common.isEmpty(); + } + + return common; } - public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) { + public Set hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) { - // get parameter's heap region - assert paramIndex2id.containsKey(paramIndex); - Integer idParam = paramIndex2id.get(paramIndex); + // get parameter 1's heap regions + assert paramIndex2idPrimary.containsKey(paramIndex1); + Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1); - assert id2hrn.containsKey(idParam); - HeapRegionNode hrnParam = id2hrn.get(idParam); - assert hrnParam != null; + assert id2hrn.containsKey(idParamPri1); + HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1); + assert hrnParamPri1 != null; - // get tokens for this parameter - TokenTuple p = new TokenTuple(hrnParam.getID(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); + HeapRegionNode hrnParamSec1 = null; + if( paramIndex2idSecondary.containsKey(paramIndex1) ) { + Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1); - TokenTuple pStar = new TokenTuple(hrnParam.getID(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); + assert id2hrn.containsKey(idParamSec1); + hrnParamSec1 = id2hrn.get(idParamSec1); + assert hrnParamSec1 != null; + } - // get special label p_q - TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex); - assert tdParamQ != null; - LabelNode lnParamQ = td2ln.get(tdParamQ); - assert lnParamQ != null; - // then get the edge from label q to parameter's hrn - ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null); - assert edgeSpecialQ != null; + // get the other parameter + assert paramIndex2idPrimary.containsKey(paramIndex2); + Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2); - // look through this beta set for potential aliases - ReachabilitySet beta = edgeSpecialQ.getBeta(); - assert beta != null; + assert id2hrn.containsKey(idParamPri2); + HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2); + assert hrnParamPri2 != null; + HeapRegionNode hrnParamSec2 = null; + if( paramIndex2idSecondary.containsKey(paramIndex2) ) { + Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2); - // get tokens for summary node - TokenTuple gs = new TokenTuple(as.getSummary(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); + assert id2hrn.containsKey(idParamSec2); + hrnParamSec2 = id2hrn.get(idParamSec2); + assert hrnParamSec2 != null; + } - TokenTuple gsStar = new TokenTuple(as.getSummary(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); + Set common = new HashSet(); + common.addAll( hasPotentialAlias( hrnParamPri1, hrnParamPri2 ) ); - if( beta.containsTupleSetWithBoth(p, gs) ) { - return true; + if( hrnParamSec1 != null ) { + common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamPri2 ) ); } - if( beta.containsTupleSetWithBoth(pStar, gs) ) { - return true; + + if( hrnParamSec2 != null ) { + common.addAll( hasPotentialAlias( hrnParamSec2, hrnParamPri1 ) ); } - if( beta.containsTupleSetWithBoth(p, gsStar) ) { - return true; + + if( hrnParamSec1 != null && hrnParamSec2 != null ) { + common.addAll( hasPotentialAlias( hrnParamSec1, hrnParamSec2 ) ); } - if( beta.containsTupleSetWithBoth(pStar, gsStar) ) { - return true; + + return common; + } + + + public Set hasPotentialAlias(Integer paramIndex, AllocationSite as) { + + // get parameter's heap regions + assert paramIndex2idPrimary.containsKey(paramIndex); + Integer idParamPri = paramIndex2idPrimary.get(paramIndex); + + assert id2hrn.containsKey(idParamPri); + HeapRegionNode hrnParamPri = id2hrn.get(idParamPri); + assert hrnParamPri != null; + + HeapRegionNode hrnParamSec = null; + if( paramIndex2idSecondary.containsKey(paramIndex) ) { + Integer idParamSec = paramIndex2idSecondary.get(paramIndex); + + assert id2hrn.containsKey(idParamSec); + hrnParamSec = id2hrn.get(idParamSec); + assert hrnParamSec != null; + } + + // get summary node + assert id2hrn.containsKey( as.getSummary() ); + HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() ); + assert hrnSummary != null; + + Set common = hasPotentialAlias( hrnParamPri, hrnSummary ); + + if( hrnParamSec != null ) { + common.addAll( hasPotentialAlias( hrnParamSec, hrnSummary ) ); } // check for other nodes for( int i = 0; i < as.getAllocationDepth(); ++i ) { - // the other nodes of an allocation site are single, no stars - TokenTuple gi = new TokenTuple(as.getIthOldest(i), - false, - TokenTuple.ARITY_ONE).makeCanonical(); + assert id2hrn.containsKey( as.getIthOldest( i ) ); + HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) ); + assert hrnIthOldest != null; - if( beta.containsTupleSetWithBoth(p, gi) ) { - return true; - } - if( beta.containsTupleSetWithBoth(pStar, gi) ) { - return true; + common = hasPotentialAlias( hrnParamPri, hrnIthOldest ); + + if( hrnParamSec != null ) { + common.addAll( hasPotentialAlias( hrnParamSec, hrnIthOldest ) ); } } - - return false; + + return common; } - public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) { + public Set hasPotentialAlias(AllocationSite as1, AllocationSite as2) { - // get tokens for summary nodes - TokenTuple gs1 = new TokenTuple(as1.getSummary(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); - - TokenTuple gsStar1 = new TokenTuple(as1.getSummary(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); - - // get summary node's alpha + // get summary node 1's alpha Integer idSum1 = as1.getSummary(); assert id2hrn.containsKey(idSum1); HeapRegionNode hrnSum1 = id2hrn.get(idSum1); assert hrnSum1 != null; - ReachabilitySet alphaSum1 = hrnSum1.getAlpha(); - assert alphaSum1 != null; - - - // and for the other one - TokenTuple gs2 = new TokenTuple(as2.getSummary(), - true, - TokenTuple.ARITY_ONE).makeCanonical(); - TokenTuple gsStar2 = new TokenTuple(as2.getSummary(), - true, - TokenTuple.ARITY_MANY).makeCanonical(); - - // get summary node's alpha + // get summary node 2's alpha Integer idSum2 = as2.getSummary(); assert id2hrn.containsKey(idSum2); HeapRegionNode hrnSum2 = id2hrn.get(idSum2); assert hrnSum2 != null; - ReachabilitySet alphaSum2 = hrnSum2.getAlpha(); - assert alphaSum2 != null; - - // does either one report reachability from the other tokens? - if( alphaSum1.containsTuple(gsStar2) ) { - return true; - } - if( alphaSum2.containsTuple(gsStar1) ) { - return true; - } - - // only check non-star token if they are different sites - if( as1 != as2 ) { - if( alphaSum1.containsTuple(gs2) ) { - return true; - } - if( alphaSum2.containsTuple(gs1) ) { - return true; - } - } + Set common = hasPotentialAlias( hrnSum1, hrnSum2 ); // check sum2 against alloc1 nodes for( int i = 0; i < as1.getAllocationDepth(); ++i ) { @@ -2445,23 +4367,8 @@ public class OwnershipGraph { assert id2hrn.containsKey(idI1); HeapRegionNode hrnI1 = id2hrn.get(idI1); assert hrnI1 != null; - ReachabilitySet alphaI1 = hrnI1.getAlpha(); - assert alphaI1 != null; - // the other nodes of an allocation site are single, no stars - TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i), - false, - TokenTuple.ARITY_ONE).makeCanonical(); - - if( alphaSum2.containsTuple(gi1) ) { - return true; - } - if( alphaI1.containsTuple(gs2) ) { - return true; - } - if( alphaI1.containsTuple(gsStar2) ) { - return true; - } + common.addAll( hasPotentialAlias( hrnI1, hrnSum2 ) ); } // check sum1 against alloc2 nodes @@ -2470,63 +4377,92 @@ public class OwnershipGraph { assert id2hrn.containsKey(idI2); HeapRegionNode hrnI2 = id2hrn.get(idI2); assert hrnI2 != null; - ReachabilitySet alphaI2 = hrnI2.getAlpha(); - assert alphaI2 != null; - TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i), - false, - TokenTuple.ARITY_ONE).makeCanonical(); - - if( alphaSum1.containsTuple(gi2) ) { - return true; - } - if( alphaI2.containsTuple(gs1) ) { - return true; - } - if( alphaI2.containsTuple(gsStar1) ) { - return true; - } + common.addAll( hasPotentialAlias( hrnSum1, hrnI2 ) ); // while we're at it, do an inner loop for alloc2 vs alloc1 nodes for( int j = 0; j < as1.getAllocationDepth(); ++j ) { Integer idI1 = as1.getIthOldest(j); - // if these are the same site, don't look for the same token, no alias + // if these are the same site, don't look for the same token, no alias. // different tokens of the same site could alias together though - if( idI1 == idI2 ) { + if( idI1.equals( idI2 ) ) { continue; } HeapRegionNode hrnI1 = id2hrn.get(idI1); - ReachabilitySet alphaI1 = hrnI1.getAlpha(); - TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j), - false, - TokenTuple.ARITY_ONE).makeCanonical(); - if( alphaI2.containsTuple(gi1) ) { - return true; + + common.addAll( hasPotentialAlias( hrnI1, hrnI2 ) ); + } + } + + return common; + } + + + public Set findCommonReachableNodes( HeapRegionNode hrn1, + HeapRegionNode hrn2 ) { + + Set reachableNodes1 = new HashSet(); + Set reachableNodes2 = new HashSet(); + + Set todoNodes1 = new HashSet(); + todoNodes1.add( hrn1 ); + + Set todoNodes2 = new HashSet(); + todoNodes2.add( hrn2 ); + + // follow links until all reachable nodes have been found + while( !todoNodes1.isEmpty() ) { + HeapRegionNode hrn = todoNodes1.iterator().next(); + todoNodes1.remove( hrn ); + reachableNodes1.add(hrn); + + Iterator edgeItr = hrn.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + if( !reachableNodes1.contains( edge.getDst() ) ) { + todoNodes1.add( edge.getDst() ); } - if( alphaI1.containsTuple(gi2) ) { - return true; + } + } + + while( !todoNodes2.isEmpty() ) { + HeapRegionNode hrn = todoNodes2.iterator().next(); + todoNodes2.remove( hrn ); + reachableNodes2.add(hrn); + + Iterator edgeItr = hrn.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + if( !reachableNodes2.contains( edge.getDst() ) ) { + todoNodes2.add( edge.getDst() ); } } } + + Set intersection = + new HashSet( reachableNodes1 ); - return false; + intersection.retainAll( reachableNodes2 ); + + return intersection; } // for writing ownership graphs to dot files - public void writeGraph(Descriptor methodDesc, + public void writeGraph(MethodContext mc, FlatNode fn, boolean writeLabels, boolean labelSelect, boolean pruneGarbage, boolean writeReferencers, - boolean writeParamMappings + boolean writeParamMappings ) throws java.io.IOException { writeGraph( - methodDesc.getSymbol() + - methodDesc.getNum() + + mc.toString() + fn.toString(), writeLabels, labelSelect, @@ -2536,38 +4472,40 @@ public class OwnershipGraph { ); } - public void writeGraph(Descriptor methodDesc, + public void writeGraph(MethodContext mc, boolean writeLabels, boolean labelSelect, boolean pruneGarbage, boolean writeReferencers, - boolean writeParamMappings + boolean writeParamMappings ) throws java.io.IOException { - writeGraph(methodDesc+"COMPLETE", + writeGraph(mc+"COMPLETE", writeLabels, labelSelect, pruneGarbage, writeReferencers, - writeParamMappings + writeParamMappings ); } - public void writeGraph(Descriptor methodDesc, + public void writeGraph(MethodContext mc, Integer numUpdate, boolean writeLabels, boolean labelSelect, boolean pruneGarbage, boolean writeReferencers, - boolean writeParamMappings + boolean writeParamMappings ) throws java.io.IOException { - writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate), + + + writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate), writeLabels, labelSelect, pruneGarbage, writeReferencers, - writeParamMappings + writeParamMappings ); } @@ -2576,7 +4514,7 @@ public class OwnershipGraph { boolean labelSelect, boolean pruneGarbage, boolean writeReferencers, - boolean writeParamMappings + boolean writeParamMappings ) throws java.io.IOException { // remove all non-word characters from the graph name so @@ -2589,12 +4527,17 @@ public class OwnershipGraph { HashSet visited = new HashSet(); // then visit every heap region node - if( !pruneGarbage ) { - Set s = id2hrn.entrySet(); - Iterator i = s.iterator(); - while( i.hasNext() ) { - Map.Entry me = (Map.Entry)i.next(); - HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + Set s = id2hrn.entrySet(); + Iterator i = s.iterator(); + while( i.hasNext() ) { + Map.Entry me = (Map.Entry)i.next(); + HeapRegionNode hrn = (HeapRegionNode) me.getValue(); + + if( !pruneGarbage || + (hrn.isFlagged() && hrn.getID() > 0) || + hrn.getDescription().startsWith("param") + ) { + if( !visited.contains(hrn) ) { traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL, hrn, @@ -2609,6 +4552,7 @@ public class OwnershipGraph { bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n"); if( writeParamMappings ) { + /* UNMAINTAINED Set df = paramIndex2id.entrySet(); Iterator ih = df.iterator(); while( ih.hasNext() ) { @@ -2617,12 +4561,13 @@ public class OwnershipGraph { Integer id = (Integer) meh.getValue(); bw.write(" pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n"); } + */ } // then visit every label node, useful for debugging if( writeLabels ) { - Set s = td2ln.entrySet(); - Iterator i = s.iterator(); + s = td2ln.entrySet(); + i = s.iterator(); while( i.hasNext() ) { Map.Entry me = (Map.Entry)i.next(); LabelNode ln = (LabelNode) me.getValue(); @@ -2632,12 +4577,16 @@ public class OwnershipGraph { if( labelStr.startsWith("___temp") || labelStr.startsWith("___dst") || labelStr.startsWith("___srctmp") || - labelStr.startsWith("___neverused") ) { + labelStr.startsWith("___neverused") || + labelStr.contains(qString) || + labelStr.contains(rString) || + labelStr.contains(blobString) + ) { continue; } } - bw.write(ln.toString() + ";\n"); + //bw.write(" "+ln.toString() + ";\n"); Iterator heapRegionsItr = ln.iteratorToReferencees(); while( heapRegionsItr.hasNext() ) { @@ -2694,11 +4643,16 @@ public class OwnershipGraph { attributes += ",style=filled,fillcolor=lightgrey"; } - attributes += ",label=\"ID" + - hrn.getID() + - "\\n" + - hrn.getDescription() + - "\\n" + + attributes += ",label=\"ID" + + hrn.getID() + + "\\n"; + + if( hrn.getType() != null ) { + attributes += hrn.getType().toPrettyString() + "\\n"; + } + + attributes += hrn.getDescription() + + "\\n" + hrn.getAlphaString() + "\"]"; @@ -2708,6 +4662,8 @@ public class OwnershipGraph { // useful for debugging + // UNMAINTAINED + /* if( writeReferencers ) { OwnershipNode onRef = null; Iterator refItr = hrn.iteratorToReferencers(); @@ -2723,6 +4679,7 @@ public class OwnershipGraph { } } } + */ Iterator childRegionsItr = hrn.iteratorToReferencees(); while( childRegionsItr.hasNext() ) { @@ -2746,4 +4703,61 @@ public class OwnershipGraph { writeReferencers); } } + + public int getTaintIdentifierFromHRN(HeapRegionNode hrn){ + HashSet referenceEdges=hrn.referencers; + Iterator iter=referenceEdges.iterator(); + + int taintIdentifier=0; + while(iter.hasNext()){ + ReferenceEdge edge=iter.next(); + taintIdentifier=taintIdentifier | edge.getTaintIdentifier(); + } + + return taintIdentifier; + + } + + public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet visitedSet){ + + HashSet setEdge=hrn.referencers; + Iterator iter=setEdge.iterator(); + while(iter.hasNext()){ + ReferenceEdge edge= iter.next(); + edge.unionTaintIdentifier(newTaintIdentifier); + if(edge.getSrc() instanceof HeapRegionNode){ + + HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc(); + //check whether it is reflexive edge + if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){ + visitedSet.add(refHRN); + propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet); + } + + } + } + + } + + public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet visitedSet){ + + HashSet setEdge=hrn.referencers; + Iterator iter=setEdge.iterator(); + while(iter.hasNext()){ + ReferenceEdge edge= iter.next(); + edge.minusTaintIdentifier(newTaintIdentifier); + if(edge.getSrc() instanceof HeapRegionNode){ + + HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc(); + //check whether it is reflexive edge + if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){ + visitedSet.add(refHRN); + depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet); + } + + } + } + + } + }