public class OwnershipGraph {
+ // use to disable improvements for comparison
+ protected static final boolean DISABLE_STRONG_UPDATES = false;
+ protected static final boolean DISABLE_GLOBAL_SWEEP = false;
+
+
private int allocationDepth;
private TypeUtil typeUtil;
assert edge == referencee.getReferenceFrom(referencer,
type,
field);
+
+// int oldTaint=edge.getTaintIdentifier();
+// if(referencer instanceof HeapRegionNode){
+// depropagateTaintIdentifier((HeapRegionNode)referencer,oldTaint,new HashSet<HeapRegionNode>());
+// }
referencer.removeReferencee(edge);
referencee.removeReferencer(edge);
ReferenceEdge edge = i.next();
if( removeAll ||
- (type != null && edge.getType() .equals( type )) ||
- (field != null && edge.getField().equals( field ))
+ (edge.typeEquals( type ) && edge.fieldEquals( field ))
){
HeapRegionNode referencee = edge.getDst();
ReferenceEdge edge = i.next();
if( removeAll ||
- (type != null && edge.getType() .equals( type )) ||
- (field != null && edge.getField().equals( field ))
+ (edge.typeEquals( type ) && edge.fieldEquals( field ))
){
OwnershipNode referencer = edge.getSrc();
Iterator<ReferenceEdge> 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<ReferenceEdge> 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.getType() == null ||
- edgeHrn.getType().equals( f.getType() ) ) {
+ if( edgeHrn.getType() == null ||
+ (edgeHrn.getType() .equals( f.getType() ) &&
+ edgeHrn.getField().equals( f.getSymbol() ) )
+ ) {
ReferenceEdge edgeNew = new ReferenceEdge(lnX,
hrnHrn,
null,
false,
betaY.intersection(betaHrn) );
+
+ int newTaintIdentifier=getTaintIdentifierFromHRN(hrnHrn);
+ edgeNew.setTaintIdentifier(newTaintIdentifier);
addReferenceEdge(lnX, hrnHrn, edgeNew);
}
HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
HashSet<ReferenceEdge> edgesWithNewBeta = new HashSet<ReferenceEdge>();
-
// first look for possible strong updates and remove those edges
boolean strongUpdate = false;
ReferenceEdge edgeX = itrXhrn.next();
HeapRegionNode hrnX = edgeX.getDst();
- Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
- while( itrYhrn.hasNext() ) {
- ReferenceEdge edgeY = itrYhrn.next();
- HeapRegionNode hrnY = edgeY.getDst();
-
- // we can do a strong update here if one of two cases holds
- if( f != null &&
- hrnX.isSingleObject() &&
- ( (hrnX.getNumReferencers() == 1) ||
- ( lnX.getNumReferencees() == 1)
- )
+ // 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 );
- }
+ if( !DISABLE_STRONG_UPDATES ) {
+ strongUpdate = true;
+ clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
+ }
}
}
// then propagate back just up the edges from hrn
ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
-
-
HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
edgeItr.next().applyBetaNew();
}
+
// then go back through and add the new edges
itrXhrn = lnX.iteratorToReferencees();
while( itrXhrn.hasNext() ) {
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<HeapRegionNode>());
addReferenceEdge( hrnX, hrnY, edgeNew );
}
}
// if there was a strong update, make sure to improve
// reachability with a global sweep
- if( strongUpdate ) {
- globalSweep();
+ if( strongUpdate ) {
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
}
}
+
+
// 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
idPrimary2paramIndexSet.put( newPrimaryID, s );
paramIndex2idPrimary.put( paramIndex, newPrimaryID );
+
TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
false, // multi-object
- TokenTuple.ARITY_ONE ).makeCanonical();
+ TokenTuple.ARITY_ONE ).makeCanonical();
HeapRegionNode hrnSecondary = null;
Integer newSecondaryID = null;
idSecondary2paramIndexSet.put( newSecondaryID, s2 );
paramIndex2idSecondary.put( paramIndex, newSecondaryID );
+
ttSecondary = new TokenTuple( newSecondaryID,
true, // multi-object
- TokenTuple.ARITY_ONE ).makeCanonical();
+ TokenTuple.ARITY_ONE ).makeCanonical();
}
// use a beta that has everything and put it all over the
ReachabilitySet betaSoup;
if( createSecondaryRegion ) {
TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
- TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).union( ttSecondary );
- betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
+ TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttSecondary );
+ betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
} else {
- betaSoup = new ReachabilitySet().union( tts0 );
+ betaSoup = ReachabilitySet.factory( tts0 );
}
ReferenceEdge edgeFromLabel =
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabel.tainedBy(paramIndex);
addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
ReferenceEdge edgeFromLabelQ =
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabelQ.tainedBy(paramIndex);
addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
ReferenceEdge edgeSecondaryReflexive;
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabelR.tainedBy(paramIndex);
addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR );
}
fd.getType(), // type
fd.getSymbol(), // field
true, // special param initial
- betaSoup ); // reachability
+ betaSoup ); // reachability
addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
}
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 );
ReferenceEdge edgeReflexive =
new ReferenceEdge( hrn, hrn, null, null, true, beta );
-
+
addReferenceEdge( lnBlob, hrn, edgeFromLabel );
addReferenceEdge( hrn, hrn, edgeReflexive );
}
HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
Integer idAliased = hrnAliasBlob.getID();
+
TokenTuple ttAliased = new TokenTuple( idAliased,
true, // multi-object
- TokenTuple.ARITY_ONE ).makeCanonical();
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
HeapRegionNode hrnPrimary = createNewHeapRegionNode( null, // id or null to generate a new one
true, // single object?
paramIndex2idSecondary.put( paramIndex, idAliased );
+
TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
false, // multi-object
- TokenTuple.ARITY_ONE ).makeCanonical();
+ TokenTuple.ARITY_ONE ).makeCanonical();
+
TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
- TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).union( ttAliased );
- ReachabilitySet betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
+ TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).makeCanonical().union( ttAliased );
+ ReachabilitySet betaSoup = ReachabilitySet.factory( tts0 ).union( tts1 ).union( tts2 );
ReferenceEdge edgeFromLabel =
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabel.tainedBy(paramIndex);
addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
ReferenceEdge edgeFromLabelQ =
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabelQ.tainedBy(paramIndex);
addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
ReferenceEdge edgeAliased2Primary =
null, // field
false, // special param initial (not needed on label->node)
betaSoup ); // reachability
+ edgeFromLabelR.tainedBy(paramIndex);
addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR );
}
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();
+ TokenTuple.ARITY_ONE ).makeCanonical();
Iterator<Integer> apItrI = aliasedParamIndices.iterator();
TypeDescriptor typeI = tdParamI.getType();
LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
- Integer idPrimaryI = paramIndex2idPrimary.get( i );
- assert idPrimaryI != null;
- HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
-
-
- System.out.println( " **idPrimaryI="+idPrimaryI );
- try {
- writeGraph( "paramProblem", true, true, true, false, false );
- } catch( IOException e ) {}
-
-
-
- assert primaryI != null;
-
+ 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 ).union( ttAliased );
- ReachabilitySet betaSoup = new ReachabilitySet().union( ttsI ).union( ttsA ).union( ttsIA );
+ 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
// affect reachability
TypeDescriptor typeDeref = typeI.dereference();
+
+
+ /////////////////////////////////////////////////////////////
+ // NOTE! For the KMeans benchmark a parameter of type float
+ // array, which has an immutable dereferenced type, is causing
+ // this assertion to fail. I'm commenting it out for now which
+ // is safe, because it allows aliasing where no aliasing can occur,
+ // so it can only get a worse-but-not-wrong answer. FIX!
+ /////////////////////////////////////////////////////////////
// for this parameter to be aliased the following must be true
- assert !typeDeref.isImmutable() || typeDeref.isArray();
+ //assert !typeDeref.isImmutable() || typeDeref.isArray();
+
+
primary2secondaryFields.add(
OwnershipAnalysis.getArrayField( typeDeref )
);
TokenTupleSet ttsIJ = ttsI.union( ttsJ );
TokenTupleSet ttsAJ = ttsA.union( ttsJ );
TokenTupleSet ttsIAJ = ttsIA.union( ttsJ );
- ReachabilitySet betaSoupWJ = new ReachabilitySet().union( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
+ ReachabilitySet betaSoupWJ = ReachabilitySet.factory( ttsJ ).union( ttsIJ ).union( ttsAJ ).union( ttsIAJ );
ReferenceEdge edgePrimaryI2PrimaryJ =
new ReferenceEdge( primaryI, // src
ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy();
lnI2PrimaryJ.setSrc( lnParamI );
lnI2PrimaryJ.setType( tdParamI.getType() );
+ lnI2PrimaryJ.tainedBy(new Integer(j));
addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ );
}
}
assert x != null;
assert as != null;
- age(as);
+ 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
-
- Integer idNewest = as.getIthOldest(0);
- HeapRegionNode hrnNewest = id2hrn.get(idNewest);
- assert hrnNewest != null;
-
- LabelNode lnX = getLabelNodeFromTemp(x);
- clearReferenceEdgesFrom(lnX, null, null, true);
-
- ReferenceEdge edgeNew =
- new ReferenceEdge(lnX, hrnNewest, null, null, false, hrnNewest.getAlpha() );
-
- addReferenceEdge(lnX, hrnNewest, edgeNew);
+ // 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 );
}
if( as.getType().isClass() ) {
hasFlags = as.getType().getClassDesc().hasFlags();
}
+
+ if(as.getFlag()){
+ hasFlags=as.getFlag();
+ }
hrnSummary = createNewHeapRegionNode(idSummary, // id or null to generate a new one
false, // single object?
HeapRegionNode n = (HeapRegionNode) me.getKey();
ChangeTupleSet C = (ChangeTupleSet) me.getValue();
- n.setAlphaNew( n.getAlpha().applyChangeSet( C, false ) );
+ n.setAlphaNew( n.getAlpha().applyChangeSet( C, true ) );
nodesWithNewAlpha.add( n );
}
ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
-
Iterator<ChangeTuple> itrC = C.iterator();
while( itrC.hasNext() ) {
ChangeTuple c = itrC.next();
ReferenceEdge e = (ReferenceEdge) me.getKey();
ChangeTupleSet C = (ChangeTupleSet) me.getValue();
- e.setBetaNew( e.getBeta().applyChangeSet( C, true ) );
+ e.setBetaNew( e.getBetaNew().union( e.getBeta().applyChangeSet( C, true ) ) );
edgesWithNewBeta.add( e );
}
}
- public Set<Integer> calculateAliasedParamSet(FlatCall fc,
- boolean isStatic,
- FlatMethod fm) {
+ public Set<Integer> calculateAliasedParamSet( FlatCall fc,
+ boolean isStatic,
+ FlatMethod fm ) {
Hashtable<Integer, LabelNode> paramIndex2ln =
new Hashtable<Integer, LabelNode>();
new Hashtable<Integer, HashSet<HeapRegionNode> >();
for( int i = 0; i < fm.numParameters(); ++i ) {
- Integer paramIndex = new Integer(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
Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
while( lnArgItr.hasNext() ) {
Map.Entry me = (Map.Entry)lnArgItr.next();
- Integer index = (Integer) me.getKey();
+ Integer index = (Integer) me.getKey();
LabelNode lnArg_i = (LabelNode) me.getValue();
- // rewrite alpha for the nodes reachable from argument label i
HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
- HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
+ HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
// to find all reachable nodes, start with label referencees
Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
while( edgeArgItr.hasNext() ) {
ReferenceEdge edge = edgeArgItr.next();
- todoNodes.add(edge.getDst() );
+ todoNodes.add( edge.getDst() );
}
// then follow links until all reachable nodes have been found
HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
+ // some parameters are immutable or primitive, so skip em
+ if( s1 == null || s2 == null ) {
+ continue;
+ }
+
Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
intersection.retainAll(s2);
return rsOut;
}
- public void resolveMethodCall(FlatCall fc,
- boolean isStatic,
- FlatMethod fm,
- OwnershipGraph ogCallee,
- MethodContext mc
+ // 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<String> fieldNamesToRemove = new HashSet<String>();
+
+ 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 ) {
+
+ Iterator<ReferenceEdge> itr = hrnPrimary.iteratorToReferencees();
+ while( itr.hasNext() ) {
+ ReferenceEdge e = itr.next();
+ if( e.fieldEquals( field ) && e.isInitialParam() ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ // 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
) {
- System.out.println( " In mapping proc" );
+ // 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( "debug1Before", true, true, true, false, false );
+ writeGraph( "debug1BeforeCall", true, true, true, false, false );
ogCallee.writeGraph( "debug0Callee", true, true, true, false, false );
} catch( IOException e ) {}
}
+
// define rewrite rules and other structures to organize data by parameter/argument index
Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
assert hrnSecondary != null;
paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
+
// setup J (secondary->X)
Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
while( s2xItr.hasNext() ) {
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<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
+ HeapRegionNode hrn = edge.getDst();
+
+ if( (hrn.getNumReferencers() == 1) || // case 1
+ (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1) // case 2
+ ) {
+ if( !DISABLE_STRONG_UPDATES ) {
+ 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<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
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<HeapRegionNode> hrnAset = (Set<HeapRegionNode>) me.getValue();
+
+ Iterator<HeapRegionNode> 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<HeapRegionNode> hrnRset = (Set<HeapRegionNode>) me.getValue();
+
+ Iterator<HeapRegionNode> 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
boolean edge_classified = false;
+
if( on instanceof HeapRegionNode ) {
// hrn0 may be "a_j" and/or "r_j" or even neither
HeapRegionNode hrn0 = (HeapRegionNode) on;
Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>) mo.getValue();
if( dr_i.contains( hrn0 ) ) {
-
- //System.out.println( " "+edge+" is classified p2p from arg "+lnArg_i );
-
addEdgeIndexPair( edges_p2p, pi, edge, index );
edge_classified = true;
}
while( hrnItr.hasNext() ) {
// this heap region is definitely an "r_i" or secondary by virtue of being in r
HeapRegionNode hrn = hrnItr.next();
-
- //assert s_i != null;
- //assert paramIndex2rewriteH_s.get( index ) != null;
-
- // TODO decide which of these things to do--if the caller node doesn't
- // have something in the callee to model it, we ought to skip it--but
- // should we skip the edge classification stuff that comes afterward, too?
- //if( s_i == null ) { continue; }
- // OR
- //if( s_i != null && paramIndex2rewriteH_s.get( index ) != null ) {
- // OR
- if( paramIndex2rewriteH_s.contains( index ) ) {
+
+ if( paramIndex2rewriteH_s.containsKey( index ) ) {
tokens2states.clear();
tokens2states.put( p_i, new ReachabilitySet().makeCanonical() );
Vector mo = (Vector) edgeItr.next();
ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
Integer indexJ = (Integer) mo.get( 1 );
-
- if( !paramIndex2rewriteJ_p2p.contains( makeMapKey( index,
+
+ if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
indexJ,
edge.getField() ) ) ) {
continue;
tokens2states.clear();
tokens2states.put( p_j, edge.getBeta() );
- /*
- try {
- writeGraph( "debugCaller"+mc, true, true, true, false, false );
- ogCallee.writeGraph( "debugCallee"+fm, true, true, true, false, false );
- } catch( IOException e ) {}
- System.out.println( " looking for "+edge+" and key["+makeMapKey( index,
- indexJ,
- edge.getField() )+"] in "+paramIndex2rewriteJ_p2p );
- */
+ rewriteCallerReachability( index,
+ null,
+ edge,
+ paramIndex2rewriteJ_p2p.get( makeMapKey( index,
+ indexJ,
+ edge.getField() ) ),
+ tokens2states,
+ paramIndex2rewrite_d_p,
+ paramIndex2rewrite_d_s,
+ paramIndex2rewriteD,
+ ogCallee,
+ false,
+ null );
-
- // it's possible that you won't find this rule, if a multiple-object
- // heap region in the caller maps to both the primary and secondary
- // nodes in the callee, so p2s and sp2 rules will take care of it
- // TODO
- if( !paramIndex2rewriteJ_p2p.containsKey( makeMapKey( index,
- indexJ,
- edge.getField() ) ) ) {
- //HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
- //System.out.println( " ASSERT "+hrnSrc+" is multi" );
- //assert !hrnSrc.isSingleObject();
-
- } else {
- 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 );
- }
+ edgesWithNewBeta.add( edge );
}
ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteJ_p2s.contains( makeMapKey( index,
- edge.getField() ) ) ) {
+ if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
+ edge.getField() ) ) ) {
continue;
}
tokens2states.clear();
tokens2states.put( s_j, edge.getBeta() );
- // it's possible that you won't find this rule, if a multiple-object
- // heap region in the caller maps to both the primary and secondary
- // nodes in the callee, so other rules will take care of it
- // TODO
- if( !paramIndex2rewriteJ_p2s.containsKey( makeMapKey( index,
- edge.getField() ) ) ) {
- //HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
- //assert !hrnSrc.isSingleObject();
-
- } else {
- 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 );
- }
+ 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 );
}
ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteJ_s2p.contains( index ) ) {
+ if( !paramIndex2rewriteJ_s2p.containsKey( index ) ) {
continue;
}
tokens2states.clear();
tokens2states.put( p_j, edge.getBeta() );
- // TODO
- if( paramIndex2rewriteJ_s2p.containsKey( index ) ) {
-
rewriteCallerReachability( index,
null,
edge,
false,
null );
- // TODO
- }
-
-
edgesWithNewBeta.add( edge );
}
ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteJ_s2s.contains( index ) ) {
+ if( !paramIndex2rewriteJ_s2s.containsKey( index ) ) {
continue;
}
tokens2states.clear();
tokens2states.put( s_j, edge.getBeta() );
- // TODO
- if( paramIndex2rewriteJ_s2s.containsKey( index ) ) {
-
rewriteCallerReachability( index,
null,
edge,
false,
null );
- // TODO
- }
-
edgesWithNewBeta.add( edge );
}
ReferenceEdge edge = (ReferenceEdge) mo.get( 0 );
Integer indexJ = (Integer) mo.get( 1 );
- if( !paramIndex2rewriteK_s.contains( index ) ) {
+ if( !paramIndex2rewriteK_s.containsKey( index ) ) {
continue;
}
// 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.getType(),
ogCallee,
mc )
);
+
rewriteCallerReachability( bogusIndex,
null,
edgeNewInCallerTemplate,
// 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.setDst( dst );
+
+ // handle taint info if callee created this edge
+ // added by eom
+ Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
+ Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
+ HashSet<Integer> paramSet=new HashSet<Integer>();
+ if(pParamSet!=null){
+ paramSet.addAll(pParamSet);
+ }
+ if(sParamSet!=null){
+ paramSet.addAll(sParamSet);
+ }
+ Iterator<Integer> paramIter=paramSet.iterator();
+ int newTaintIdentifier=0;
+ while(paramIter.hasNext()){
+ Integer paramIdx=paramIter.next();
+ edgeNewInCaller.tainedBy(paramIdx);
+ }
ReferenceEdge edgeExisting = src.getReferenceTo( dst,
edgeNewInCaller.getType(),
}
+ 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<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
while( allocItr.hasNext() ) {
if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
fm.getMethod().getSymbol().equals( debugCallee ) ) {
try {
- writeGraph( "debug2JustBeforeSweep", true, true, true, false, false );
+ writeGraph( "debug8JustBeforeSweep", true, true, true, false, false );
} catch( IOException e ) {}
}
// improve reachability as much as possible
- globalSweep();
-
+ if( !DISABLE_GLOBAL_SWEEP ) {
+ globalSweep();
+ }
if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
try {
writeGraph( "debug9endResolveCall", true, true, true, false, false );
} catch( IOException e ) {}
- System.out.println( " "+mc+" done calling "+fm );
+ System.out.println( " "+mc+" done calling "+fm );
+ ++x;
+ if( x > 2 ) {
+ System.exit( -1 );
+ }
}
-
- System.out.println( " End mapping proc" );
}
+ static int x = 0;
+
protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
return false;
}
- Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
- while( fieldsSrcItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
- if( fd.getType().equals( edge.getType() ) &&
- fd.getSymbol().equals( edge.getField() ) ) {
- 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;
Iterator<TokenTuple> ruleItr = rule.iterator();
while(ruleItr.hasNext()) {
- TokenTuple ttCallee = ruleItr.next();
+ TokenTuple ttCallee = ruleItr.next();
// compute the possibilities for rewriting this callee token
ReachabilitySet ttCalleeRewrites = null;
boolean callerSourceUsed = false;
- if( tokens2states.containsKey( ttCallee ) ) {
+ if( tokens2states.containsKey( ttCallee ) ) {
callerSourceUsed = true;
ttCalleeRewrites = tokens2states.get( ttCallee );
assert ttCalleeRewrites != null;
// invoked after strong updates or method calls.
//
////////////////////////////////////////////////////
-
- static int x = 0;
-
public void globalSweep() {
- System.out.println( " In global sweep" );
-
// boldB is part of the phase 1 sweep
Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
ReferenceEdge edgePrime = itrPrime.next();
ReachabilitySet prevResult = boldB_f.get( edgePrime );
- ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
+ 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 ) );
+ boldB_f.put( edgePrime, prevResult .union( intersection ) );
}
workSetEdges.add( edgePrime );
}
ReferenceEdge incidentEdge = incidentEdgeItr.next();
// if it isn't allowed, mark for removal
-
-
- x++;
- if( x % 1000 == 0 && x > 4000000 ) {
- System.out.println( "x="+x );
- //System.out.println( boldB.get( ttOld.getToken() ) );
- }
-
-
Integer idOld = ttOld.getToken();
+ assert id2hrn.containsKey( idOld );
Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get( idOld );
ReachabilitySet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
if( boldB_ttOld_incident != null &&
while( edgeItr.hasNext() ) {
edgeItr.next().applyBetaNew();
}
-
- System.out.println( " End global sweep" );
}
edgeToMerge.setBeta(
edgeToMerge.getBeta().union(edgeA.getBeta() )
);
+ //TODO eom
+ edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
if( !edgeA.isInitialParam() ) {
edgeToMerge.setIsInitialParam(false);
}
edgeToMerge.setBeta(
edgeToMerge.getBeta().union(edgeA.getBeta() )
);
+ edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
if( !edgeA.isInitialParam() ) {
edgeToMerge.setIsInitialParam(false);
}
TokenTuple.ARITY_ZEROORMORE).makeCanonical();
// then get the merged beta of all out-going edges from these heap regions
- ReachabilitySet beta1 = new ReachabilitySet();
+ ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
while( itrEdge.hasNext() ) {
ReferenceEdge edge = itrEdge.next();
beta1 = beta1.union( edge.getBeta() );
}
- ReachabilitySet beta2 = new ReachabilitySet();
+ ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
itrEdge = hrn2.iteratorToReferencees();
while( itrEdge.hasNext() ) {
ReferenceEdge edge = itrEdge.next();
Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
if( aliasDetected ) {
common = findCommonReachableNodes( hrn1, hrn2 );
- assert !common.isEmpty();
+ if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
+ assert !common.isEmpty();
+ }
}
return common;
public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
HeapRegionNode hrn2 ) {
- //assert hrn1 != hrn2;
Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
);
}
+ public void writeGraph(MethodContext mc,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings,
+ boolean hideSubsetReachability
+ ) throws java.io.IOException {
+
+ writeGraph(mc+"COMPLETE",
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings,
+ hideSubsetReachability
+ );
+ }
+
public void writeGraph(MethodContext mc,
Integer numUpdate,
boolean writeLabels,
boolean writeParamMappings
) throws java.io.IOException {
+ writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings
+ );
+ }
+ public void writeGraph(MethodContext mc,
+ Integer numUpdate,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings,
+ boolean hideSubsetReachability
+ ) throws java.io.IOException {
writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
writeLabels,
labelSelect,
pruneGarbage,
writeReferencers,
- writeParamMappings
+ writeParamMappings,
+ hideSubsetReachability
);
}
boolean writeReferencers,
boolean writeParamMappings
) throws java.io.IOException {
+ writeGraph(graphName,
+ writeLabels,
+ labelSelect,
+ pruneGarbage,
+ writeReferencers,
+ writeParamMappings,
+ false
+ );
+ }
+
+ public void writeGraph(String graphName,
+ boolean writeLabels,
+ boolean labelSelect,
+ boolean pruneGarbage,
+ boolean writeReferencers,
+ boolean writeParamMappings,
+ boolean hideSubsetReachability
+ ) throws java.io.IOException {
// remove all non-word characters from the graph name so
// the filename and identifier in dot don't cause errors
bw,
null,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability);
}
}
}
bw.write(" graphTitle[label=\""+graphName+"\",shape=box];\n");
if( writeParamMappings ) {
- /*
+ /* UNMAINTAINED
Set df = paramIndex2id.entrySet();
Iterator ih = df.iterator();
while( ih.hasNext() ) {
bw,
null,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability);
}
bw.write(" " + ln.toString() +
" -> " + hrn.toString() +
- "[label=\"" + edge.toGraphEdgeString() +
+ "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability) +
"\",decorate];\n");
}
}
BufferedWriter bw,
TempDescriptor td,
HashSet<HeapRegionNode> visited,
- boolean writeReferencers
+ boolean writeReferencers,
+ boolean hideSubsetReachability
) throws java.io.IOException {
if( visited.contains(hrn) ) {
attributes += hrn.getDescription() +
"\\n" +
- hrn.getAlphaString() +
+ hrn.getAlphaString(hideSubsetReachability) +
"\"]";
bw.write(" " + hrn.toString() + attributes + ";\n");
case VISIT_HRN_WRITE_FULL:
bw.write(" " + hrn.toString() +
" -> " + hrnChild.toString() +
- "[label=\"" + edge.toGraphEdgeString() +
+ "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability) +
"\",decorate];\n");
break;
}
bw,
td,
visited,
- writeReferencers);
+ writeReferencers,
+ hideSubsetReachability);
}
}
+
+ public int getTaintIdentifierFromHRN(HeapRegionNode hrn){
+ HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
+ Iterator<ReferenceEdge> 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<HeapRegionNode> visitedSet){
+
+ HashSet<ReferenceEdge> setEdge=hrn.referencers;
+ Iterator<ReferenceEdge> 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<HeapRegionNode> visitedSet){
+
+ HashSet<ReferenceEdge> setEdge=hrn.referencers;
+ Iterator<ReferenceEdge> 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);
+ }
+
+ }
+ }
+
+ }
+
}
projects / IRC.git / blobdiff