}
-
-
// 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
LabelNode lnParamI = getLabelNodeFromTemp( tdParamI );
Integer idPrimaryI = paramIndex2idPrimary.get( i );
-
- /*
- if( idPrimaryI == null ) {
- try {
- writeGraph( "debugalias",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // show back edges to confirm graph validity
- false, // show parameter indices (unmaintained!)
- true, // hide subset reachability states
- true); // hide edge taints
- } catch( Exception e ) {}
- System.out.println( "FlatMethod="+fm+"\nalias set="+aliasedParamIndices+
- "\nindex bad="+i);
- }
- */
-
assert idPrimaryI != null;
HeapRegionNode primaryI = id2hrn.get( idPrimaryI );
assert primaryI != null;
public Set<Integer> calculateAliasedParamSet( FlatCall fc,
+ boolean isStatic,
FlatMethod fm ) {
- // to decide if two parameters are aliased, look
- // at the caller graph (this graph) and if these
- // two conditions are met, they may be aliased:
- // 1. The argument labels reference a shared node
- // 2. The edges to that shared node have a common
- // reachability state.
-
- Set<Integer> aliasedIndices = new HashSet<Integer>();
+ Hashtable<Integer, LabelNode> paramIndex2ln =
+ new Hashtable<Integer, LabelNode>();
- //System.out.println("Aliases for "+fm+" at "+fc);
-
+ Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
+ new Hashtable<Integer, HashSet<HeapRegionNode> >();
for( int i = 0; i < fm.numParameters(); ++i ) {
- for( int j = 0; j < i; ++j ) {
-
- TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, i );
- LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
-
- TempDescriptor argTemp_j = fc.getArgMatchingParamIndex( fm, j );
- LabelNode argLabel_j = getLabelNodeFromTemp( argTemp_j );
+ Integer paramIndex = new Integer( i );
+ TempDescriptor tdParam = fm.getParameter( i );
+ TypeDescriptor typeParam = tdParam.getType();
- /*
- System.out.println(" "+argTemp_i.getType()+" "+argTemp_i+" and "+
- argTemp_j.getType()+" "+argTemp_j+" aliased?");
- */
-
- // first condition--do these arguments
- // reference any common nodes?
- Iterator<ReferenceEdge> edgeItr;
+ if( typeParam.isImmutable() && !typeParam.isArray() ) {
+ // don't bother with this primitive parameter, it
+ // cannot affect reachability
+ continue;
+ }
- Set<HeapRegionNode> hrnSetI = new HashSet<HeapRegionNode>();
- edgeItr = argLabel_i.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- hrnSetI.add( edgeItr.next().getDst() );
- }
+ // 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 = fc.getArgMatchingParamIndex( fm, paramIndex );
- Set<HeapRegionNode> hrnSetJ = new HashSet<HeapRegionNode>();
- edgeItr = argLabel_j.iteratorToReferencees();
- while( edgeItr.hasNext() ) {
- hrnSetJ.add( edgeItr.next().getDst() );
- }
+ LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
+ paramIndex2ln.put(paramIndex, argLabel_i);
+ }
- Set<HeapRegionNode> intersection =
- new HashSet<HeapRegionNode>( hrnSetI );
- intersection.retainAll( hrnSetJ );
+ 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();
- // condition two--for each shared node, do the reference
- // edges to it from arguments have a common reachability
- // state that is *ALSO* on the shared node?
- boolean foundAlias = false;
+ HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
+ HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
- Iterator<HeapRegionNode> hrnItr = intersection.iterator();
- while( hrnItr.hasNext() ) {
- HeapRegionNode hrn = hrnItr.next();
+ // 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() );
+ }
- ReferenceEdge ei = argLabel_i.getReferenceTo( hrn,
- argTemp_i.getType(),
- null );
+ // then follow links until all reachable nodes have been found
+ while( !todoNodes.isEmpty() ) {
+ HeapRegionNode hrn = todoNodes.iterator().next();
+ todoNodes.remove(hrn);
+ reachableNodes.add(hrn);
- ReferenceEdge ej = argLabel_j.getReferenceTo( hrn,
- argTemp_j.getType(),
- null );
- assert ei != null;
- assert ej != null;
+ Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
+ while( edgeItr.hasNext() ) {
+ ReferenceEdge edge = edgeItr.next();
- ReachabilitySet allStatesForParamI =
- ei.getBeta().intersection( hrn.getAlpha() );
+ if( !reachableNodes.contains(edge.getDst() ) ) {
+ todoNodes.add(edge.getDst() );
+ }
+ }
+ }
- ReachabilitySet allStatesForParamJ =
- ej.getBeta().intersection( hrn.getAlpha() );
+ // save for later
+ paramIndex2reachableCallerNodes.put(index, reachableNodes);
+ }
- ReachabilitySet commonStates =
- allStatesForParamI.intersection( allStatesForParamJ );
+ Set<Integer> aliasedIndices = new HashSet<Integer>();
- if( !commonStates.isEmpty() ) {
- foundAlias = true;
- aliasedIndices.add( new Integer( i ) );
- aliasedIndices.add( new Integer( j ) );
+ // check for arguments that are aliased
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ for( int j = 0; j < i; ++j ) {
+ HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
+ HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
- //System.out.println( " yes!" );
- }
+ // some parameters are immutable or primitive, so skip em
+ if( s1 == null || s2 == null ) {
+ continue;
}
- // as soon as we detect one possible way to alias
- // these parameters, skip on to another pair
- if( foundAlias ) {
- continue;
+ Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
+ intersection.retainAll(s2);
+
+ if( !intersection.isEmpty() ) {
+ aliasedIndices.add( new Integer( i ) );
+ aliasedIndices.add( new Integer( j ) );
}
}
}
- if( !aliasedIndices.isEmpty() ) {
- try {
- writeGraph( "foundaliases",
- true, // write labels (variables)
- true, // selectively hide intermediate temp vars
- true, // prune unreachable heap regions
- false, // show back edges to confirm graph validity
- false, // show parameter indices (unmaintained!)
- true, // hide subset reachability states
- true); // hide edge taints
- } catch( Exception e ) {}
- /*
- System.out.println("FlatCall="+fc+
- "\nflat method="+fm+
- "\nAliases="+aliasedIndices );
- */
- }
-
return aliasedIndices;
}
assert hrnSecondary != null;
paramIndex2rewriteH_s.put( paramIndex, toShadowTokens( ogCallee, hrnSecondary.getAlpha() ) );
-
// setup J (secondary->X)
Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
while( s2xItr.hasNext() ) {
return intersection;
}
-
- /*
- // for writing ownership graphs to dot files
- public void writeGraph(MethodContext mc,
- FlatNode fn,
- boolean writeLabels,
- boolean labelSelect,
- boolean pruneGarbage,
- boolean writeReferencers,
- boolean writeParamMappings
- ) throws java.io.IOException {
- writeGraph(
- mc.toString() +
- fn.toString(),
- writeLabels,
- labelSelect,
- pruneGarbage,
- writeReferencers,
- writeParamMappings
- );
- }
-
- public void writeGraph(MethodContext mc,
- boolean writeLabels,
- boolean labelSelect,
- boolean pruneGarbage,
- boolean writeReferencers,
- boolean writeParamMappings
- ) throws java.io.IOException {
-
- writeGraph(mc+"COMPLETE",
- writeLabels,
- labelSelect,
- pruneGarbage,
- writeReferencers,
- writeParamMappings
- );
- }
-
- 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 labelSelect,
- boolean pruneGarbage,
- boolean writeReferencers,
- 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,
- hideSubsetReachability
- );
- }
-
- public void writeGraph(String graphName,
- boolean writeLabels,
- boolean labelSelect,
- boolean pruneGarbage,
- 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,
projects / IRC.git / commitdiff