From 473fc4921dcecab1415c96d1c2b93a76efd1ac9f Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 12 Aug 2008 23:09:48 +0000 Subject: [PATCH] Made a big change to reference edges, touched a lot of code. This commit is stable, but reachability needs to be added back in, a little bit at a time with testing to make sure everything gets put back together. --- .../OwnershipAnalysis/HeapRegionNode.java | 49 +- .../Analysis/OwnershipAnalysis/LabelNode.java | 4 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 19 +- .../OwnershipAnalysis/OwnershipGraph.java | 772 +++++++++--------- .../OwnershipAnalysis/OwnershipNode.java | 49 +- ...EdgeProperties.java => ReferenceEdge.java} | 127 +-- .../OwnershipAnalysis/TokenTuple.java | 14 +- .../OwnershipAnalysis/TokenTupleSet.java | 13 +- .../OwnershipAnalysisTest/test01/test01.java | 7 +- .../testGraphs/Main.java | 18 +- .../testTokens/Main.java | 130 ++- 11 files changed, 635 insertions(+), 567 deletions(-) rename Robust/src/Analysis/OwnershipAnalysis/{ReferenceEdgeProperties.java => ReferenceEdge.java} (70%) diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 43d808d2..8141f6e4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -12,8 +12,7 @@ public class HeapRegionNode extends OwnershipNode { protected boolean isFlagged; protected boolean isNewSummary; - protected HashSet memberFields; - protected HashSet referencers; + protected HashSet referencers; protected AllocationSite allocSite; @@ -39,11 +38,8 @@ public class HeapRegionNode extends OwnershipNode { this.alpha = alpha; this.description = description; - alphaNew = new ReachabilitySet(); - alphaNew = alphaNew.makeCanonical(); - - referencers = new HashSet(); - memberFields = new HashSet(); + referencers = new HashSet(); + alphaNew = new ReachabilitySet().makeCanonical(); } public HeapRegionNode copy() { @@ -62,7 +58,6 @@ public class HeapRegionNode extends OwnershipNode { } - /* public boolean equals( Object o ) { if( o == null ) { return false; @@ -85,7 +80,6 @@ public class HeapRegionNode extends OwnershipNode { public int hashCode() { return id.intValue(); } - */ public boolean isSingleObject() { @@ -102,31 +96,42 @@ public class HeapRegionNode extends OwnershipNode { - public Iterator iteratorToReferencers() { + public Iterator iteratorToReferencers() { return referencers.iterator(); } - public Iterator iteratorToReferencersClone() { - HashSet hs = (HashSet) referencers.clone(); - return hs.iterator(); + public Iterator iteratorToReferencersClone() { + HashSet clone = (HashSet) referencers.clone(); + return clone.iterator(); } - public void addReferencer( OwnershipNode on ) { - assert on != null; + public void addReferencer( ReferenceEdge edge ) { + assert edge != null; - referencers.add( on ); + referencers.add( edge ); } - public void removeReferencer( OwnershipNode on ) { - assert on != null; - assert referencers.contains( on ); + public void removeReferencer( ReferenceEdge edge ) { + assert edge != null; + assert referencers.contains( edge ); - referencers.remove( on ); + referencers.remove( edge ); } - public boolean isReferencedBy( OwnershipNode on ) { + public ReferenceEdge getReferenceFrom( OwnershipNode on, + FieldDescriptor fd ) { assert on != null; - return referencers.contains( on ); + + Iterator itrEdge = referencers.iterator(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + if( edge.getSrc().equals( on ) && + edge.getFieldDesc() == fd ) { + return edge; + } + } + + return null; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/LabelNode.java b/Robust/src/Analysis/OwnershipAnalysis/LabelNode.java index 8802d673..5be55331 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/LabelNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/LabelNode.java @@ -15,7 +15,7 @@ public class LabelNode extends OwnershipNode { return td; } - /* + public boolean equals( Object o ) { if( o == null ) { return false; @@ -33,7 +33,7 @@ public class LabelNode extends OwnershipNode { public int hashCode() { return td.getNum(); } - */ + public String getTempDescriptorString() { return td.toString(); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index cb8147d0..864c60a6 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -15,6 +15,7 @@ public class OwnershipAnalysis { // aliases in the program under analysis // /////////////////////////////////////////// + /* public HashSet getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) { @@ -84,14 +85,15 @@ public class OwnershipAnalysis { getHeapRegionIDset( alloc ), getHeapRegionIDset( allocSet ) ); } + */ // use the methods given above to check every possible alias // between task parameters and flagged allocation sites reachable // from the task public void writeAllAliases( String outputFile ) throws java.io.IOException { - - BufferedWriter bw = new BufferedWriter( new FileWriter( outputFile ) ); + BufferedWriter bw = new BufferedWriter( new FileWriter( outputFile ) ); + /* // look through every task for potential aliases Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); while( taskItr.hasNext() ) { @@ -138,8 +140,9 @@ public class OwnershipAnalysis { } bw.close(); + */ } - + /////////////////////////////////////////// // // end public interface @@ -440,7 +443,7 @@ public class OwnershipAnalysis { if( fon.getOp().getOp() == Operation.ASSIGN ) { src = fon.getLeft(); dst = fon.getDest(); - og.assignTempToTemp( src, dst ); + og.assignTempXToTempY( src, dst ); } break; @@ -450,7 +453,7 @@ public class OwnershipAnalysis { dst = ffn.getDst(); fld = ffn.getField(); if( !fld.getType().isPrimitive() ) { - og.assignTempToField( src, dst, fld ); + og.assignTempXToTempYFieldF( src, dst, fld ); } break; @@ -459,7 +462,7 @@ public class OwnershipAnalysis { src = fsfn.getSrc(); dst = fsfn.getDst(); fld = fsfn.getField(); - og.assignFieldToTemp( src, dst, fld ); + og.assignTempXFieldFToTempY( src, fld, dst ); break; case FKind.FlatNew: @@ -467,7 +470,7 @@ public class OwnershipAnalysis { dst = fnn.getDst(); AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn ); - og.assignTempToNewAllocation( dst, as ); + og.assignTempXToNewAllocation( dst, as ); break; case FKind.FlatCall: @@ -745,6 +748,7 @@ public class OwnershipAnalysis { HashSet idSetB ) { boolean potentialAlias = false; + /* // first expand set B into the set of all heap region node ID's // reachable from the nodes in set B HashSet idSetReachableFromB = og.getReachableSet( idSetB ); @@ -758,6 +762,7 @@ public class OwnershipAnalysis { return true; } } + */ return false; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 2eb6a05d..611234b7 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -109,55 +109,77 @@ public class OwnershipGraph { //////////////////////////////////////////////// protected void addReferenceEdge( OwnershipNode referencer, HeapRegionNode referencee, - ReferenceEdgeProperties rep ) { + ReferenceEdge edge ) { assert referencer != null; assert referencee != null; - assert rep != null; - referencer.addReferencedRegion( referencee, rep ); - referencee.addReferencer( referencer ); - rep.setSrc( referencer ); - rep.setDst( referencee ); + assert edge != null; + assert edge.getSrc() == referencer; + assert edge.getDst() == referencee; + + referencer.addReferencee( edge ); + referencee.addReferencer( edge ); } - protected void removeReferenceEdge( OwnershipNode referencer, - HeapRegionNode referencee ) { + protected void removeReferenceEdge( OwnershipNode referencer, + HeapRegionNode referencee, + FieldDescriptor fieldDesc ) { assert referencer != null; assert referencee != null; - assert referencer.getReferenceTo( referencee ) != null; - assert referencee.isReferencedBy( referencer ); + + ReferenceEdge edge = referencer.getReferenceTo( referencee, + fieldDesc ); + assert edge != null; + assert edge == referencee.getReferenceFrom( referencer, + fieldDesc ); - referencer.removeReferencedRegion( referencee ); - referencee.removeReferencer( referencer ); + referencer.removeReferencee( edge ); + referencee.removeReferencer( edge ); } - protected void clearReferenceEdgesFrom( OwnershipNode referencer ) { + protected void clearReferenceEdgesFrom( OwnershipNode referencer, + FieldDescriptor fieldDesc, + boolean removeAll ) { assert referencer != null; - // get a copy of the table to iterate over, otherwise - // we will be trying to take apart the table as we + // get a copy of the set to iterate over, otherwise + // we will be trying to take apart the set as we // are iterating over it, which won't work - Iterator i = referencer.setIteratorToReferencedRegionsClone(); + Iterator i = referencer.iteratorToReferenceesClone(); while( i.hasNext() ) { - Map.Entry me = (Map.Entry) i.next(); - HeapRegionNode referencee = (HeapRegionNode) me.getKey(); - removeReferenceEdge( referencer, referencee ); + ReferenceEdge edge = i.next(); + + if( removeAll || edge.getFieldDesc() == fieldDesc ) { + HeapRegionNode referencee = edge.getDst(); + removeReferenceEdge( referencer, + referencee, + edge.getFieldDesc() ); + } } } - protected void clearReferenceEdgesTo( HeapRegionNode referencee ) { + protected void clearReferenceEdgesTo( HeapRegionNode referencee, + FieldDescriptor fieldDesc, + boolean removeAll ) { assert referencee != null; - // get a copy of the table to iterate over, otherwise - // we will be trying to take apart the table as we + // get a copy of the set to iterate over, otherwise + // we will be trying to take apart the set as we // are iterating over it, which won't work - Iterator i = referencee.iteratorToReferencersClone(); + Iterator i = referencee.iteratorToReferencersClone(); while( i.hasNext() ) { - OwnershipNode referencer = (OwnershipNode) i.next(); - removeReferenceEdge( referencer, referencee ); - } + ReferenceEdge edge = i.next(); + + if( removeAll || edge.getFieldDesc() == fieldDesc ) { + OwnershipNode referencer = edge.getSrc(); + removeReferenceEdge( referencer, + referencee, + edge.getFieldDesc() ); + } + } } + /* protected void propagateTokensOverNodes( HeapRegionNode nPrime, ChangeTupleSet c0, HashSet nodesWithNewAlpha, @@ -300,6 +322,7 @@ public class OwnershipGraph { } } } + */ //////////////////////////////////////////////////// @@ -318,110 +341,92 @@ public class OwnershipGraph { // of the nodes and edges involved. // //////////////////////////////////////////////////// - public void assignTempToTemp( TempDescriptor src, - TempDescriptor dst ) { - LabelNode srcln = getLabelNodeFromTemp( src ); - LabelNode dstln = getLabelNodeFromTemp( dst ); - - clearReferenceEdgesFrom( dstln ); - - HeapRegionNode newReferencee = null; - Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); - while( srcRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) srcRegionsItr.next(); - newReferencee = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); + public void assignTempXToTempY( TempDescriptor x, + TempDescriptor y ) { - addReferenceEdge( dstln, newReferencee, rep.copy() ); - } - } + LabelNode lnX = getLabelNodeFromTemp( x ); + LabelNode lnY = getLabelNodeFromTemp( y ); - public void assignTempToField( TempDescriptor src, - TempDescriptor dst, - FieldDescriptor fd ) { - LabelNode srcln = getLabelNodeFromTemp( src ); - LabelNode dstln = getLabelNodeFromTemp( dst ); - - clearReferenceEdgesFrom( dstln ); - - HeapRegionNode hrn = null; - Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); - while( srcRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) srcRegionsItr.next(); - hrn = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue(); - ReachabilitySet beta1 = rep1.getBeta(); - - HeapRegionNode hrnOneHop = null; - Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions(); - while( hrnRegionsItr.hasNext() ) { - Map.Entry meH = (Map.Entry) hrnRegionsItr.next(); - hrnOneHop = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue(); - ReachabilitySet beta2 = rep2.getBeta(); - - ReferenceEdgeProperties rep = - new ReferenceEdgeProperties( null, - false, - beta1.intersection( beta2 ) ); - - addReferenceEdge( dstln, hrnOneHop, rep ); - } + clearReferenceEdgesFrom( lnX, null, true ); + + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode referencee = edgeY.getDst(); + ReferenceEdge edgeNew = edgeY.copy(); + edgeNew.setSrc( lnX ); + + addReferenceEdge( lnX, referencee, edgeNew ); } } + public void assignTempXToTempYFieldF( TempDescriptor x, + TempDescriptor y, + FieldDescriptor f ) { + LabelNode lnX = getLabelNodeFromTemp( x ); + LabelNode lnY = getLabelNodeFromTemp( y ); + clearReferenceEdgesFrom( lnX, null, true ); - static int x = 0; + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode hrnY = edgeY.getDst(); + ReachabilitySet betaY = edgeY.getBeta(); - public void assignFieldToTemp( TempDescriptor src, - TempDescriptor dst, - FieldDescriptor fd ) { + Iterator itrHrnFhrn = hrnY.iteratorToReferencees(); + while( itrHrnFhrn.hasNext() ) { + ReferenceEdge edgeHrn = itrHrnFhrn.next(); + HeapRegionNode hrnHrn = edgeHrn.getDst(); + ReachabilitySet betaHrn = edgeHrn.getBeta(); - // I think my use of src and dst are actually backwards in this method! - // acccording to the Reachability Notes, think of dst at N and src as N prime + if( edgeHrn.getFieldDesc() == null || + edgeHrn.getFieldDesc() == f ) { - LabelNode srcln = getLabelNodeFromTemp( src ); - LabelNode dstln = getLabelNodeFromTemp( dst ); + ReferenceEdge edgeNew = new ReferenceEdge( lnX, + hrnHrn, + f, + false, + betaY.intersection( betaHrn ) ); + + addReferenceEdge( lnX, hrnHrn, edgeNew ); + } + } + } + } - HashSet nodesWithNewAlpha = new HashSet(); - HashSet edgesWithNewBeta = new HashSet(); - HeapRegionNode hrn = null; - ReferenceEdgeProperties rep = null; - Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions(); - while( dstRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) dstRegionsItr.next(); - hrn = (HeapRegionNode) me.getKey(); - rep = (ReferenceEdgeProperties) me.getValue(); - - ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() ); - - HeapRegionNode hrnSrc = null; - ReferenceEdgeProperties repSrc = null; - Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions(); - while( srcRegionsItr.hasNext() ) { - Map.Entry meS = (Map.Entry) srcRegionsItr.next(); - hrnSrc = (HeapRegionNode) meS.getKey(); - repSrc = (ReferenceEdgeProperties) meS.getValue(); - - ReachabilitySet O = repSrc.getBeta(); + public void assignTempXFieldFToTempY( TempDescriptor x, + FieldDescriptor f, + TempDescriptor y ) { + LabelNode lnX = getLabelNodeFromTemp( x ); + LabelNode lnY = getLabelNodeFromTemp( y ); - x++; - System.out.println( "x is "+x ); - if( x > 0 ) { - String s = String.format( "debug%04d", x ); - try { - writeGraph( s, true, true, true, false ); - } catch( Exception e ) {} - } + /* + HashSet nodesWithNewAlpha = new HashSet(); + HashSet edgesWithNewBeta = new HashSet(); + */ + + Iterator itrXhrn = lnX.iteratorToReferencees(); + while( itrXhrn.hasNext() ) { + ReferenceEdge edgeX = itrXhrn.next(); + HeapRegionNode hrnX = edgeX.getDst(); + ReachabilitySet betaX = edgeX.getBeta(); + //ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() ); - System.out.println( " O is "+O ); + Iterator itrYhrn = lnY.iteratorToReferencees(); + while( itrYhrn.hasNext() ) { + ReferenceEdge edgeY = itrYhrn.next(); + HeapRegionNode hrnY = edgeY.getDst(); + ReachabilitySet betaY = edgeY.getBeta(); + + //ReachabilitySet O = repSrc.getBeta(); + /* // propagate tokens over nodes starting from hrnSrc, and it will // take care of propagating back up edges from any touched nodes ChangeTupleSet Cy = O.unionUpArityToChangeSet( R ); @@ -457,18 +462,24 @@ public class OwnershipGraph { edgesWithNewBeta ); System.out.println( " Onew = "+repSrc.getBetaNew() ); + */ + + // finally, create the actual reference edge hrnX.f -> hrnY + ReferenceEdge edgeNew = new ReferenceEdge( hrnX, + hrnY, + f, + false, + null ); - // finally, create the actual reference edge hrn->hrnSrc - ReferenceEdgeProperties repNew - = new ReferenceEdgeProperties( fd, - false, - repSrc.getBetaNew().pruneBy( hrn.getAlpha() ) - ); + /* + repSrc.getBetaNew().pruneBy( hrn.getAlpha() + */ - addReferenceEdge( hrn, hrnSrc, repNew ); + addReferenceEdge( hrnX, hrnY, edgeNew ); } } + /* Iterator nodeItr = nodesWithNewAlpha.iterator(); while( nodeItr.hasNext() ) { ((HeapRegionNode) nodeItr.next()).applyAlphaNew(); @@ -478,8 +489,10 @@ public class OwnershipGraph { while( edgeItr.hasNext() ) { ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew(); } + */ } + public void assignTempToParameterAllocation( boolean isTask, TempDescriptor td, Integer paramIndex ) { @@ -512,35 +525,50 @@ public class OwnershipGraph { // 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. - addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( null, false, beta ) ); - addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( null, true, beta ) ); + + ReferenceEdge edgeFromLabel = + new ReferenceEdge( lnParam, hrn, null, false, beta ); + + ReferenceEdge edgeReflexive = + new ReferenceEdge( hrn, hrn, null, true, beta ); + + addReferenceEdge( lnParam, hrn, edgeFromLabel ); + addReferenceEdge( hrn, hrn, edgeReflexive ); } + - public void assignTempToNewAllocation( TempDescriptor td, - AllocationSite as ) { - assert td != null; + public void assignTempXToNewAllocation( TempDescriptor x, + AllocationSite as ) { + 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 dst = getLabelNodeFromTemp( td ); - - clearReferenceEdgesFrom( dst ); + LabelNode lnX = getLabelNodeFromTemp( x ); + clearReferenceEdgesFrom( lnX, null, true ); + + ReferenceEdge edgeNew = + new ReferenceEdge( lnX, hrnNewest, null, false, hrnNewest.getAlpha() ); - addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( null, false, hrnNewest.getAlpha() ) ); + 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 @@ -595,8 +623,8 @@ public class OwnershipGraph { assert hrn0 != null; // clear all references in and out of newest node - clearReferenceEdgesFrom( hrn0 ); - clearReferenceEdgesTo ( hrn0 ); + clearReferenceEdgesFrom( hrn0, null, true ); + clearReferenceEdgesTo ( hrn0, null, true ); // now tokens in reachability sets need to "age" also @@ -640,7 +668,7 @@ public class OwnershipGraph { ).makeCanonical() ); } - + protected HeapRegionNode getSummaryNode( AllocationSite as ) { @@ -810,7 +838,7 @@ public class OwnershipGraph { // replace hrnB reachability with hrnA's hrnB.setAlpha( hrnA.getAlpha() ); } - + */ protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) { rep.setBeta( rep.getBeta().ageTokens( as ) ); @@ -993,7 +1021,7 @@ public class OwnershipGraph { */ } - + /* private HashSet getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee, Integer idCallee, FlatCall fc, @@ -1046,7 +1074,7 @@ public class OwnershipGraph { return possibleCallerHRNs; } - + */ //////////////////////////////////////////////////// @@ -1108,13 +1136,6 @@ public class OwnershipGraph { } protected void mergeReferenceEdges( OwnershipGraph og ) { - // there is a data structure for storing label nodes - // retireved by temp descriptors, and a data structure - // for stroing heap region nodes retrieved by integer - // ids. Because finding edges requires interacting - // with these disparate data structures frequently the - // process is nearly duplicated, one for each structure - // that stores edges // heap regions Set sA = og.id2hrn.entrySet(); @@ -1124,49 +1145,54 @@ public class OwnershipGraph { Integer idA = (Integer) meA.getKey(); HeapRegionNode hrnA = (HeapRegionNode) meA.getValue(); - HeapRegionNode hrnChildA = null; - Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions(); + Iterator heapRegionsItrA = hrnA.iteratorToReferencees(); while( heapRegionsItrA.hasNext() ) { - Map.Entry me = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue(); - - Integer idChildA = hrnChildA.getID(); + ReferenceEdge edgeA = heapRegionsItrA.next(); + HeapRegionNode hrnChildA = edgeA.getDst(); + Integer idChildA = hrnChildA.getID(); // at this point we know an edge in graph A exists // idA -> idChildA, does this exist in B? - boolean edgeFound = false; assert id2hrn.containsKey( idA ); - HeapRegionNode hrnB = id2hrn.get( idA ); + HeapRegionNode hrnB = id2hrn.get( idA ); + ReferenceEdge edgeToMerge = null; - HeapRegionNode hrnChildB = null; - ReferenceEdgeProperties repB = null; - Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry meC = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) meC.getKey(); - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue(); + Iterator heapRegionsItrB = hrnB.iteratorToReferencees(); + while( heapRegionsItrB.hasNext() && + edgeToMerge == null ) { - if( hrnChildB.equals( idChildA ) ) { - edgeFound = true; - repB = rep; + ReferenceEdge edgeB = heapRegionsItrB.next(); + HeapRegionNode hrnChildB = edgeB.getDst(); + + // don't use the ReferenceEdge.equals() here because + // we're talking about existence between graphs + if( hrnChildB.equals( idChildA ) && + edgeB.getFieldDesc() == edgeA.getFieldDesc() ) { + edgeToMerge = edgeB; } } // if the edge from A was not found in B, // add it to B. - if( !edgeFound ) { + if( edgeToMerge == null ) { assert id2hrn.containsKey( idChildA ); - hrnChildB = id2hrn.get( idChildA ); - repB = repA.copy(); - addReferenceEdge( hrnB, hrnChildB, repB ); + HeapRegionNode hrnChildB = id2hrn.get( idChildA ); + edgeToMerge = edgeA.copy(); + edgeToMerge.setSrc( hrnB ); + edgeToMerge.setDst( hrnChildB ); + addReferenceEdge( hrnB, hrnChildB, edgeToMerge ); } // otherwise, the edge already existed in both graphs // so merge their reachability sets else { // just replace this beta set with the union - assert repB != null; - repB.setBeta( repB.getBeta().union( repA.getBeta() ) ); + assert edgeToMerge != null; + edgeToMerge.setBeta( + edgeToMerge.getBeta().union( edgeA.getBeta() ) + ); + if( !edgeA.isInitialParamReflexive() ) { + edgeToMerge.setIsInitialParamReflexive( false ); + } } } } @@ -1179,49 +1205,54 @@ public class OwnershipGraph { TempDescriptor tdA = (TempDescriptor) meA.getKey(); LabelNode lnA = (LabelNode) meA.getValue(); - HeapRegionNode hrnChildA = null; - Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions(); + Iterator heapRegionsItrA = lnA.iteratorToReferencees(); while( heapRegionsItrA.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue(); - - Integer idChildA = hrnChildA.getID(); + ReferenceEdge edgeA = heapRegionsItrA.next(); + HeapRegionNode hrnChildA = edgeA.getDst(); + Integer idChildA = hrnChildA.getID(); // at this point we know an edge in graph A exists // tdA -> idChildA, does this exist in B? - boolean edgeFound = false; assert td2ln.containsKey( tdA ); - LabelNode lnB = td2ln.get( tdA ); + LabelNode lnB = td2ln.get( tdA ); + ReferenceEdge edgeToMerge = null; - HeapRegionNode hrnChildB = null; - ReferenceEdgeProperties repB = null; - Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry meC = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) meC.getKey(); - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue(); + Iterator heapRegionsItrB = lnB.iteratorToReferencees(); + while( heapRegionsItrB.hasNext() && + edgeToMerge == null ) { - if( hrnChildB.equals( idChildA ) ) { - edgeFound = true; - repB = rep; + ReferenceEdge edgeB = heapRegionsItrB.next(); + HeapRegionNode hrnChildB = edgeB.getDst(); + + // don't use the ReferenceEdge.equals() here because + // we're talking about existence between graphs + if( hrnChildB.equals( idChildA ) && + edgeB.getFieldDesc() == edgeA.getFieldDesc() ) { + edgeToMerge = edgeB; } } // if the edge from A was not found in B, // add it to B. - if( !edgeFound ) { + if( edgeToMerge == null ) { assert id2hrn.containsKey( idChildA ); - hrnChildB = id2hrn.get( idChildA ); - repB = repA.copy(); - addReferenceEdge( lnB, hrnChildB, repB ); + HeapRegionNode hrnChildB = id2hrn.get( idChildA ); + edgeToMerge = edgeA.copy(); + edgeToMerge.setSrc( lnB ); + edgeToMerge.setDst( hrnChildB ); + addReferenceEdge( lnB, hrnChildB, edgeToMerge ); } // otherwise, the edge already existed in both graphs - // so merge the reachability sets + // so merge their reachability sets else { // just replace this beta set with the union - assert repB != null; - repB.setBeta( repB.getBeta().union( repA.getBeta() ) ); + assert edgeToMerge != null; + edgeToMerge.setBeta( + edgeToMerge.getBeta().union( edgeA.getBeta() ) + ); + if( !edgeA.isInitialParamReflexive() ) { + edgeToMerge.setIsInitialParamReflexive( false ); + } } } } @@ -1270,15 +1301,11 @@ public class OwnershipGraph { return false; } - if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) { - return false; - } - if( !areLabelNodesEqual( og ) ) { return false; } - if( !areLabelToHeapRegionEdgesEqual( og ) ) { + if( !areReferenceEdgesEqual( og ) ) { return false; } @@ -1294,50 +1321,85 @@ public class OwnershipGraph { return true; } - protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) { - // check all nodes in A for presence in graph B - Set sA = og.id2hrn.entrySet(); + protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) { + + if( !areallHRNinAalsoinBandequal( this, og ) ) { + return false; + } + + if( !areallHRNinAalsoinBandequal( og, this ) ) { + return false; + } + + return true; + } + + static protected boolean areallHRNinAalsoinBandequal( OwnershipGraph ogA, + OwnershipGraph ogB ) { + Set sA = ogA.id2hrn.entrySet(); Iterator iA = sA.iterator(); while( iA.hasNext() ) { Map.Entry meA = (Map.Entry) iA.next(); Integer idA = (Integer) meA.getKey(); HeapRegionNode hrnA = (HeapRegionNode) meA.getValue(); - if( !id2hrn.containsKey( idA ) ) { + if( !ogB.id2hrn.containsKey( idA ) ) { return false; } - //HeapRegionNode hrnB = og.id2hrn.get( idA ); - HeapRegionNode hrnB = id2hrn.get( idA ); + HeapRegionNode hrnB = ogB.id2hrn.get( idA ); if( !hrnA.equals( hrnB ) ) { return false; } - } + } + + return true; + } - // then check all nodes in B verses graph A - Set sB = id2hrn.entrySet(); - Iterator iB = sB.iterator(); - while( iB.hasNext() ) { - Map.Entry meB = (Map.Entry) iB.next(); - Integer idB = (Integer) meB.getKey(); - HeapRegionNode hrnB = (HeapRegionNode) meB.getValue(); - if( !og.id2hrn.containsKey( idB ) ) { + protected boolean areLabelNodesEqual( OwnershipGraph og ) { + + if( !areallLNinAalsoinBandequal( this, og ) ) { + return false; + } + + if( !areallLNinAalsoinBandequal( og, this ) ) { + return false; + } + + return true; + } + + static protected boolean areallLNinAalsoinBandequal( OwnershipGraph ogA, + OwnershipGraph ogB ) { + Set sA = ogA.td2ln.entrySet(); + Iterator iA = sA.iterator(); + while( iA.hasNext() ) { + Map.Entry meA = (Map.Entry) iA.next(); + TempDescriptor tdA = (TempDescriptor) meA.getKey(); + + if( !ogB.td2ln.containsKey( tdA ) ) { return false; } - - // we should have already checked the equality - // of this pairing in the last pass if they both - // exist so assert that they are equal now - HeapRegionNode hrnA = og.id2hrn.get( idB ); - assert hrnB.equals( hrnA ); + } + + return true; + } + + + protected boolean areReferenceEdgesEqual( OwnershipGraph og ) { + if( !areallREinAandBequal( this, og ) ) { + return false; } return true; } - protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) { - Set sA = og.id2hrn.entrySet(); + static protected boolean areallREinAandBequal( OwnershipGraph ogA, + OwnershipGraph ogB ) { + + // check all the heap region->heap region edges + Set sA = ogA.id2hrn.entrySet(); Iterator iA = sA.iterator(); while( iA.hasNext() ) { Map.Entry meA = (Map.Entry) iA.next(); @@ -1346,105 +1408,42 @@ public class OwnershipGraph { // we should have already checked that the same // heap regions exist in both graphs - assert id2hrn.containsKey( idA ); - - // and are their edges the same? first check every - // edge in A for presence and equality in B - HeapRegionNode hrnChildA = null; - Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions(); - while( heapRegionsItrA.hasNext() ) { - Map.Entry me = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue(); - - Integer idChildA = hrnChildA.getID(); - assert id2hrn.containsKey( idChildA ); - - // at this point we know an edge in graph A exists - // idA -> idChildA, does this edge exist in B? - boolean edgeFound = false; - HeapRegionNode hrnB = id2hrn.get( idA ); + assert ogB.id2hrn.containsKey( idA ); - HeapRegionNode hrnChildB = null; - Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue(); - - if( idChildA.equals( hrnChildB.getID() ) ) { - if( !repA.equals( repB ) ) { - return false; - } - edgeFound = true; - } - } - - if( !edgeFound ) { - return false; - } + if( !areallREfromAequaltoB( ogA, hrnA, ogB ) ) { + return false; } // then check every edge in B for presence in A, starting // from the same parent HeapRegionNode - HeapRegionNode hrnB = id2hrn.get( idA ); - - HeapRegionNode hrnChildB = null; - Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry me = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue(); - - Integer idChildB = hrnChildB.getID(); - - // at this point we know an edge in graph B exists - // idB -> idChildB, does this edge exist in A? - boolean edgeFound = false; - - hrnChildA = null; - heapRegionsItrA = hrnA.setIteratorToReferencedRegions(); - while( heapRegionsItrA.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue(); - - if( idChildB.equals( hrnChildA.getID() ) ) { - assert repB.equals( repA ); - edgeFound = true; - } - } + HeapRegionNode hrnB = ogB.id2hrn.get( idA ); - if( !edgeFound ) { - return false; - } - } - } - - return true; - } + if( !areallREfromAequaltoB( ogB, hrnB, ogA ) ) { + return false; + } + } - protected boolean areLabelNodesEqual( OwnershipGraph og ) { - // are all label nodes in A also in graph B? - Set sA = og.td2ln.entrySet(); - Iterator iA = sA.iterator(); + // then check all the label->heap region edges + sA = ogA.td2ln.entrySet(); + iA = sA.iterator(); while( iA.hasNext() ) { Map.Entry meA = (Map.Entry) iA.next(); TempDescriptor tdA = (TempDescriptor) meA.getKey(); + LabelNode lnA = (LabelNode) meA.getValue(); + + // we should have already checked that the same + // label nodes exist in both graphs + assert ogB.td2ln.containsKey( tdA ); - if( !td2ln.containsKey( tdA ) ) { + if( !areallREfromAequaltoB( ogA, lnA, ogB ) ) { return false; } - } - // are all label nodes in B also in A? - Set sB = td2ln.entrySet(); - Iterator iB = sB.iterator(); - while( iB.hasNext() ) { - Map.Entry meB = (Map.Entry) iB.next(); - TempDescriptor tdB = (TempDescriptor) meB.getKey(); + // then check every edge in B for presence in A, starting + // from the same parent LabelNode + LabelNode lnB = ogB.td2ln.get( tdA ); - if( !og.td2ln.containsKey( tdB ) ) { + if( !areallREfromAequaltoB( ogB, lnB, ogA ) ) { return false; } } @@ -1452,91 +1451,57 @@ public class OwnershipGraph { return true; } - protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) { - Set sA = og.td2ln.entrySet(); - Iterator iA = sA.iterator(); - while( iA.hasNext() ) { - Map.Entry meA = (Map.Entry) iA.next(); - TempDescriptor tdA = (TempDescriptor) meA.getKey(); - LabelNode lnA = (LabelNode) meA.getValue(); - // we should have already checked that the same - // label nodes exist in both graphs - assert td2ln.containsKey( tdA ); + static protected boolean areallREfromAequaltoB( OwnershipGraph ogA, + OwnershipNode onA, + OwnershipGraph ogB ) { + + Iterator itrA = onA.iteratorToReferencees(); + while( itrA.hasNext() ) { + ReferenceEdge edgeA = itrA.next(); + HeapRegionNode hrnChildA = edgeA.getDst(); + Integer idChildA = hrnChildA.getID(); + + assert ogB.id2hrn.containsKey( idChildA ); + + // at this point we know an edge in graph A exists + // onA -> idChildA, does this exact edge exist in B? + boolean edgeFound = false; + + OwnershipNode onB = null; + if( onA instanceof HeapRegionNode ) { + HeapRegionNode hrnA = (HeapRegionNode) onA; + onB = ogB.id2hrn.get( hrnA.getID() ); + } else { + LabelNode lnA = (LabelNode) onA; + onB = ogB.td2ln.get( lnA.getTempDescriptor() ); + } - // and are their edges the same? first check every - // edge in A for presence and equality in B - HeapRegionNode hrnChildA = null; - Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions(); - while( heapRegionsItrA.hasNext() ) { - Map.Entry me = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue(); + Iterator itrB = onB.iteratorToReferencees(); + while( itrB.hasNext() ) { + ReferenceEdge edgeB = itrB.next(); + HeapRegionNode hrnChildB = edgeB.getDst(); - Integer idChildA = hrnChildA.getID(); - assert id2hrn.containsKey( idChildA ); + if( idChildA.equals( hrnChildB.getID() ) && + edgeA.getFieldDesc() == edgeB.getFieldDesc() ) { - // at this point we know an edge in graph A exists - // tdA -> idChildA, does this edge exist in B? - boolean edgeFound = false; - LabelNode lnB = td2ln.get( tdA ); - - HeapRegionNode hrnChildB = null; - Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue(); - - if( idChildA.equals( hrnChildB.getID() ) ) { - if( !repA.equals( repB ) ) { - return false; - } + // there is an edge in the right place with the right field, + // but do they have the same attributes? + if( edgeA.isInitialParamReflexive() == edgeB.isInitialParamReflexive() && + edgeA.getBeta().equals( edgeB.getBeta() ) ) { + edgeFound = true; + } else { + return false; } } - - if( !edgeFound ) { - return false; - } } - // then check every edge in B for presence in A, starting - // from the same parent LabelNode - LabelNode lnB = td2ln.get( tdA ); - - HeapRegionNode hrnChildB = null; - Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions(); - while( heapRegionsItrB.hasNext() ) { - Map.Entry me = (Map.Entry) heapRegionsItrB.next(); - hrnChildB = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue(); - - Integer idChildB = hrnChildB.getID(); - - // at this point we know an edge in graph B exists - // tdB -> idChildB, does this edge exist in A? - boolean edgeFound = false; - - hrnChildA = null; - heapRegionsItrA = lnA.setIteratorToReferencedRegions(); - while( heapRegionsItrA.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItrA.next(); - hrnChildA = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue(); - - if( idChildB.equals( hrnChildA.getID() ) ) { - assert repB.equals( repA ); - edgeFound = true; - } - } - - if( !edgeFound ) { - return false; - } - } - } - + if( !edgeFound ) { + return false; + } + } + return true; } @@ -1546,7 +1511,7 @@ public class OwnershipGraph { } - + /* // given a set B of heap region node ID's, return the set of heap // region node ID's that is reachable from B public HashSet getReachableSet( HashSet idSetB ) { @@ -1602,16 +1567,16 @@ public class OwnershipGraph { assert id2hrn.contains( id ); HeapRegionNode hrn = id2hrn.get( id ); - /* - HashSet hrnSet = new HashSet(); - - Iterator i = idSet.iterator(); - while( i.hasNext() ) { - Integer idFromSet = (Integer) i.next(); - assert id2hrn.contains( idFromSet ); - hrnSet.add( id2hrn.get( idFromSet ) ); - } - */ + + //HashSet hrnSet = new HashSet(); + + //Iterator i = idSet.iterator(); + //while( i.hasNext() ) { + // Integer idFromSet = (Integer) i.next(); + // assert id2hrn.contains( idFromSet ); + // hrnSet.add( id2hrn.get( idFromSet ) ); + //} + // do a traversal from hrn and see if any of the // heap regions from the set come up during that @@ -1644,7 +1609,7 @@ public class OwnershipGraph { return false; } - + */ // for writing ownership graphs to dot files @@ -1770,12 +1735,10 @@ public class OwnershipGraph { } } - HeapRegionNode hrn = null; - Iterator heapRegionsItr = ln.setIteratorToReferencedRegions(); + Iterator heapRegionsItr = ln.iteratorToReferencees(); while( heapRegionsItr.hasNext() ) { - Map.Entry meH = (Map.Entry) heapRegionsItr.next(); - hrn = (HeapRegionNode) meH.getKey(); - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue(); + ReferenceEdge edge = heapRegionsItr.next(); + HeapRegionNode hrn = edge.getDst(); if( pruneGarbage && !visited.contains( hrn ) ) { traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, @@ -1788,7 +1751,7 @@ public class OwnershipGraph { bw.write( " " + ln.toString() + " -> " + hrn.toString() + - "[label=\"" + rep.toEdgeLabelString() + + "[label=\"" + edge.toGraphEdgeString() + "\",decorate];\n" ); } } @@ -1857,19 +1820,16 @@ public class OwnershipGraph { } } - - HeapRegionNode hrnChild = null; - Iterator childRegionsItr = hrn.setIteratorToReferencedRegions(); + Iterator childRegionsItr = hrn.iteratorToReferencees(); while( childRegionsItr.hasNext() ) { - Map.Entry me = (Map.Entry) childRegionsItr.next(); - hrnChild = (HeapRegionNode) me.getKey(); - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue(); + ReferenceEdge edge = childRegionsItr.next(); + HeapRegionNode hrnChild = edge.getDst(); switch( mode ) { case VISIT_HRN_WRITE_FULL: bw.write( " " + hrn.toString() + " -> " + hrnChild.toString() + - "[label=\"" + rep.toEdgeLabelString() + + "[label=\"" + edge.toGraphEdgeString() + "\",decorate];\n" ); break; } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java index f66bf0dc..b7063c37 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java @@ -6,46 +6,51 @@ import java.util.*; public abstract class OwnershipNode { - protected Hashtable referencedRegions; + protected HashSet referencees; public OwnershipNode() { - referencedRegions = - new Hashtable(); + referencees = new HashSet(); } - public Iterator setIteratorToReferencedRegions() { - Set s = referencedRegions.entrySet(); - return s.iterator(); + public Iterator iteratorToReferencees() { + return referencees.iterator(); } - public Iterator setIteratorToReferencedRegionsClone() { - Hashtable ht = (Hashtable) referencedRegions.clone(); - Set s = ht.entrySet(); - return s.iterator(); + public Iterator iteratorToReferenceesClone() { + HashSet clone = (HashSet) referencees.clone(); + return clone.iterator(); } - public void addReferencedRegion( HeapRegionNode hrn, - ReferenceEdgeProperties rep ) { - assert hrn != null; - assert rep != null; - referencedRegions.put( hrn, rep ); + public void addReferencee( ReferenceEdge edge ) { + assert edge != null; + + referencees.add( edge ); } - public void removeReferencedRegion( HeapRegionNode hrn ) { - assert hrn != null; - assert referencedRegions.containsKey( hrn ); + public void removeReferencee( ReferenceEdge edge ) { + assert edge != null; + assert referencees.contains( edge ); - referencedRegions.remove( hrn ); + referencees.remove( edge ); } - public ReferenceEdgeProperties getReferenceTo( HeapRegionNode hrn ) { + public ReferenceEdge getReferenceTo( HeapRegionNode hrn, + FieldDescriptor fd ) { assert hrn != null; - return referencedRegions.get( hrn ); - } + Iterator itrEdge = referencees.iterator(); + while( itrEdge.hasNext() ) { + ReferenceEdge edge = itrEdge.next(); + if( edge.getDst().equals( hrn ) && + edge.getFieldDesc() == fd ) { + return edge; + } + } + return null; + } /* abstract public boolean equals( Object o ); diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java similarity index 70% rename from Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java rename to Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java index a8bb7714..270697a8 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java @@ -4,7 +4,7 @@ import IR.*; import IR.Flat.*; -public class ReferenceEdgeProperties { +public class ReferenceEdge { // a null field descriptor means "any field" @@ -19,14 +19,14 @@ public class ReferenceEdgeProperties { protected HeapRegionNode dst; - public ReferenceEdgeProperties() { - this( null, false, null ); - } - - public ReferenceEdgeProperties( FieldDescriptor fieldDesc, - boolean isInitialParamReflexive, - ReachabilitySet beta ) { + public ReferenceEdge( OwnershipNode src, + HeapRegionNode dst, + FieldDescriptor fieldDesc, + boolean isInitialParamReflexive, + ReachabilitySet beta ) { + this.src = src; + this.dst = dst; this.fieldDesc = fieldDesc; this.isInitialParamReflexive = isInitialParamReflexive; @@ -36,18 +36,61 @@ public class ReferenceEdgeProperties { this.beta = new ReachabilitySet().makeCanonical(); } - // these members are set by higher-level code - // when this ReferenceEdgeProperties object is - // applied to an edge - this.src = null; - this.dst = null; - // when edges are not undergoing a transitional operation // that is changing beta info, betaNew is always empty betaNew = new ReachabilitySet().makeCanonical(); } + public ReferenceEdge copy() { + return new ReferenceEdge( src, + dst, + fieldDesc, + isInitialParamReflexive, + beta ); + } + + + public boolean equals( Object o ) { + if( o == null ) { + return false; + } + + if( !(o instanceof ReferenceEdge) ) { + return false; + } + + ReferenceEdge re = (ReferenceEdge) o; + + // field descriptors maintain the invariant that they are reference comparable + return fieldDesc == re.fieldDesc && + isInitialParamReflexive == re.isInitialParamReflexive && + src.equals ( re.src ) && + dst.equals ( re.dst ) && + beta.equals( re.beta ); + } + + public int hashCode() { + int hash = 0; + + if( fieldDesc != null ) { + hash += fieldDesc.getType().hashCode(); + } + + if( isInitialParamReflexive ) { + hash += 1; + } + + hash += src.hashCode(); + + hash += dst.hashCode(); + + hash += beta.hashCode(); + + return hash; + } + + public OwnershipNode getSrc() { return src; } @@ -67,14 +110,6 @@ public class ReferenceEdgeProperties { } - // copying does not copy source and destination members! or betaNew - public ReferenceEdgeProperties copy() { - return new ReferenceEdgeProperties( fieldDesc, - isInitialParamReflexive, - beta ); - } - - public FieldDescriptor getFieldDesc() { return fieldDesc; } @@ -119,58 +154,24 @@ public class ReferenceEdgeProperties { /* - - WHY ARE THESE METHODS INCORRECT? WHEN INCLUDED, THE ANALYSIS GOES - HAYWIRE WITH REGARD TO REFERENCE EDGES - - public boolean equals( Object o ) { - if( o == null ) { - return false; - } - - if( !(o instanceof ReferenceEdgeProperties) ) { - return false; - } - - ReferenceEdgeProperties rep = (ReferenceEdgeProperties) o; - - // field descriptors maintain the invariant that they are reference comparable - return fieldDesc == rep.fieldDesc && - isInitialParamReflexive == rep.isInitialParamReflexive && - beta.equals( rep.beta ); - } - - public int hashCode() { - int hash = 0; - - if( fieldDesc != null ) { - hash += fieldDesc.getType().hashCode(); - } - - if( isInitialParamReflexive ) { - hash += 1; - } - - hash += beta.hashCode(); - - return hash; - } - */ - - public String getBetaString() { return beta.toStringEscapeNewline(); } + */ - public String toEdgeLabelString() { + public String toGraphEdgeString() { String edgeLabel = ""; + if( fieldDesc != null ) { edgeLabel += fieldDesc.toStringBrief() + "\\n"; } + if( isInitialParamReflexive ) { edgeLabel += "Rflx\\n"; } - edgeLabel += getBetaString(); + + edgeLabel += beta.toStringEscapeNewline(); + return edgeLabel; } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java index e8fd95a9..52b31924 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java @@ -11,16 +11,18 @@ import java.io.*; // THIS CLASS IS IMMUTABLE! -public class TokenTuple extends Canonical -{ +public class TokenTuple extends Canonical { + private Integer token; private boolean isNewSummary; + // only summary tokens should have ARITY_MANY? public static final int ARITY_ONE = 1; public static final int ARITY_MANY = 2; private int arity; + public TokenTuple( HeapRegionNode hrn ) { token = hrn.getID(); isNewSummary = hrn.isNewSummary(); @@ -35,13 +37,16 @@ public class TokenTuple extends Canonical this.arity = arity; } + public TokenTuple makeCanonical() { return (TokenTuple) Canonical.makeCanonical( this ); } + public Integer getToken() { return token; } public int getArity() { return arity; } + public TokenTuple increaseArity() { if( isNewSummary ) { return (TokenTuple) Canonical.makeCanonical( @@ -51,6 +56,7 @@ public class TokenTuple extends Canonical return this; } + public TokenTuple changeTokenTo( Integer tokenToChangeTo ) { assert isNewSummary == false; @@ -59,6 +65,7 @@ public class TokenTuple extends Canonical arity ).makeCanonical(); } + public boolean equals( Object o ) { if( o == null ) { return false; @@ -75,9 +82,10 @@ public class TokenTuple extends Canonical } public int hashCode() { - return token.intValue(); + return token.intValue() + arity*100000; } + public String toString() { String s = ""; if( isNewSummary ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java index fb6ee256..114c142b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -31,19 +31,18 @@ public class TokenTupleSet extends Canonical { return tokenTuples.iterator(); } - /* - public TokenTupleSet add( TokenTuple tt ) { - TokenTupleSet ttsOut = new TokenTupleSet( tt ); - return this.union( ttsOut ); - } - */ - public TokenTupleSet union( TokenTupleSet ttsIn ) { TokenTupleSet ttsOut = new TokenTupleSet( this ); ttsOut.tokenTuples.addAll( ttsIn.tokenTuples ); return ttsOut.makeCanonical(); } + public TokenTupleSet add( TokenTuple tt ) { + TokenTupleSet ttsOut = new TokenTupleSet( this ); + ttsOut = ttsOut.union( this ); + return ttsOut; + } + /* public TokenTupleSet unionUpArity( TokenTupleSet ttsIn ) { TokenTupleSet ttsOut = new TokenTupleSet(); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 1becdb6e..9d428175 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -46,7 +46,7 @@ public class Foo { a.x = b.x; } - /* + static public void test( Foo p0, Foo p1 ) { Foo f0 = new Foo(); Foo f1 = new Foo(); @@ -57,7 +57,6 @@ public class Foo { p1.x = f1; p1.x = f2; } - */ } @@ -67,7 +66,7 @@ public class Foo { // a heap region that is multi-object, flagged, not summary task Startup( StartupObject s{ initialstate } ) { - /* + while( false ) { Foo a = new Foo(); a.x = new Foo(); @@ -111,7 +110,7 @@ task Startup( StartupObject s{ initialstate } ) { c.x = b; b = c; } - */ + taskexit( s{ !initialstate } ); } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java index d089f3af..e54ae7f8 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java @@ -54,25 +54,25 @@ public class Main { OwnershipGraph g0 = new OwnershipGraph( allocationDepth ); TempDescriptor g0tdp1 = new TempDescriptor( "p1" ); TempDescriptor g0tdx = new TempDescriptor( "x" ); - g0.parameterAllocation( true, g0tdp1 ); - g0.assignTempToTemp ( g0tdx, g0tdp1 ); + g0.assignTempToParameterAllocation( true, g0tdp1, new Integer( 0 ) ); + g0.assignTempXToTempY ( g0tdx, g0tdp1 ); OwnershipGraph g1 = new OwnershipGraph( allocationDepth ); TempDescriptor g1tdp2 = new TempDescriptor( "p2" ); TempDescriptor g1tdy = new TempDescriptor( "y" ); TempDescriptor g1tdz = new TempDescriptor( "z" ); - g1.parameterAllocation( true, g1tdp2 ); - g1.assignTempToTemp ( g1tdy, g1tdp2 ); - g1.assignTempToField ( g1tdz, g1tdp2, null ); + g1.assignTempToParameterAllocation( true, g1tdp2, new Integer( 0 ) ); + g1.assignTempXToTempY ( g1tdy, g1tdp2 ); + g1.assignTempXToTempYFieldF ( g1tdz, g1tdp2, null ); OwnershipGraph g2 = new OwnershipGraph( allocationDepth ); TempDescriptor g2tdp3 = new TempDescriptor( "p3" ); TempDescriptor g2tdp4 = new TempDescriptor( "p4" ); TempDescriptor g2tdw = new TempDescriptor( "w" ); - g2.parameterAllocation( true, g2tdp3 ); - g2.parameterAllocation( true, g2tdp4 ); - g2.assignTempToTemp ( g2tdw, g2tdp4 ); - g2.assignFieldToTemp ( g2tdp3, g2tdw, null ); + g2.assignTempToParameterAllocation( true, g2tdp3, new Integer( 0 ) ); + g2.assignTempToParameterAllocation( true, g2tdp4, new Integer( 1 ) ); + g2.assignTempXToTempY ( g2tdw, g2tdp4 ); + g2.assignTempXFieldFToTempY ( g2tdp3, null, g2tdw ); OwnershipGraph g3 = new OwnershipGraph( allocationDepth ); g3.merge( g0 ); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java index 7fe74733..6639f245 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/testTokens/Main.java @@ -7,61 +7,145 @@ import java.io.*; public class Main { + static boolean aTestFailed; + + protected static void test( String test, boolean expected, boolean result ) { - - String outcome = "...\tFAILED"; + String outcome; if( expected == result ) { outcome = "...\tpassed"; + } else { + outcome = "...\tFAILED"; + aTestFailed = true; } System.out.println( test+" expected "+expected+outcome ); } + public static void main(String args[]) throws Exception { - /* + aTestFailed = false; + + testExample(); + System.out.println( "---------------------------------------" ); + testTokenTuple(); + System.out.println( "---------------------------------------" ); + testTokenTupleSet(); + System.out.println( "---------------------------------------" ); + + if( aTestFailed ) { + System.out.println( "<><><><><><><><><><><><><><><><><><><><><><><><>" ); + System.out.println( "<><><> WARNING: At least one test failed. <><><>" ); + System.out.println( "<><><><><><><><><><><><><><><><><><><><><><><><>" ); + } else { + System.out.println( "All tests passed." ); + } + } + + + public static void testExample() { + // example test to know the testing routine is correct! test( "4 == 5?", false, 4 == 5 ); test( "3 == 3?", true, 3 == 3 ); + } - TokenTuple tt0 = new TokenTuple( new Integer( 1 ), - true, - TokenTuple.ARITY_ONE ); - - TokenTuple tt1 = new TokenTuple( new Integer( 1 ), - true, - TokenTuple.ARITY_ONE ); - - TokenTuple tt2 = new TokenTuple( new Integer( 2 ), - true, - TokenTuple.ARITY_ONE ); + public static void testTokenTuple() { - TokenTuple tt3 = new TokenTuple( new Integer( 1 ), - true, - TokenTuple.ARITY_MANY ); + TokenTuple tt0 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_ONE ); + TokenTuple tt1 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_ONE ); + TokenTuple tt2 = new TokenTuple( new Integer( 2 ), true, TokenTuple.ARITY_ONE ); + TokenTuple tt3 = new TokenTuple( new Integer( 1 ), true, TokenTuple.ARITY_MANY ); + TokenTuple tt4 = new TokenTuple( new Integer( 3 ), false, TokenTuple.ARITY_ONE ); + TokenTuple tt5 = new TokenTuple( new Integer( 3 ), false, TokenTuple.ARITY_ONE ); test( "tt0 equals tt1?", true, tt0.equals( tt1 ) ); test( "tt1 equals tt0?", true, tt1.equals( tt0 ) ); + test( "tt1.hashCode == tt0.hashCode?", true, tt1.hashCode() == tt0.hashCode() ); test( "tt0 equals tt2?", false, tt0.equals( tt2 ) ); test( "tt2 equals tt0?", false, tt2.equals( tt0 ) ); + test( "tt2.hashCode == tt0.hashCode?", false, tt2.hashCode() == tt0.hashCode() ); test( "tt0 equals tt3?", false, tt0.equals( tt3 ) ); test( "tt3 equals tt0?", false, tt3.equals( tt0 ) ); + test( "tt3.hashCode == tt0.hashCode?", false, tt3.hashCode() == tt0.hashCode() ); test( "tt2 equals tt3?", false, tt2.equals( tt3 ) ); test( "tt3 equals tt2?", false, tt3.equals( tt2 ) ); + test( "tt3.hashCode == tt2.hashCode?", false, tt3.hashCode() == tt2.hashCode() ); tt1 = tt1.increaseArity(); test( "tt1 equals tt2?", false, tt1.equals( tt2 ) ); test( "tt2 equals tt1?", false, tt2.equals( tt1 ) ); + test( "tt2.hashCode == tt1.hashCode?", false, tt2.hashCode() == tt1.hashCode() ); test( "tt1 equals tt3?", true, tt1.equals( tt3 ) ); - test( "tt3 equals tt1?", true, tt3.equals( tt1 ) ); + test( "tt3 equals tt1?", true, tt3.equals( tt1 ) ); + test( "tt3.hashCode == tt1.hashCode?", true, tt3.hashCode() == tt1.hashCode() ); + + test( "tt4 equals tt5?", true, tt4.equals( tt5 ) ); + test( "tt5 equals tt4?", true, tt5.equals( tt4 ) ); + test( "tt5.hashCode == tt4.hashCode?", true, tt5.hashCode() == tt4.hashCode() ); + + tt4 = tt4.increaseArity(); + + test( "tt4 equals tt5?", true, tt4.equals( tt5 ) ); + test( "tt5 equals tt4?", true, tt5.equals( tt4 ) ); + test( "tt5.hashCode == tt4.hashCode?", true, tt5.hashCode() == tt4.hashCode() ); + + + TokenTuple tt6 = new TokenTuple( new Integer( 6 ), false, TokenTuple.ARITY_ONE ); + TokenTuple tt7 = new TokenTuple( new Integer( 6 ), false, TokenTuple.ARITY_ONE ); + TokenTuple tt8 = new TokenTuple( new Integer( 8 ), false, TokenTuple.ARITY_ONE ); + TokenTuple tt9 = new TokenTuple( new Integer( 9 ), false, TokenTuple.ARITY_ONE ); + + test( "tt6 equals tt7?", true, tt6.equals( tt7 ) ); + test( "tt6.hashCode == tt7.hashCode?", true, tt6.hashCode() == tt7.hashCode() ); + + test( "tt8 equals tt7?", false, tt8.equals( tt7 ) ); + test( "tt8.hashCode == tt7.hashCode?", false, tt8.hashCode() == tt7.hashCode() ); + + // notice that this makes tt7 canonical + tt7 = tt7.changeTokenTo( new Integer( 8 ) ); + + test( "tt6 equals tt7?", false, tt6.equals( tt7 ) ); + test( "tt6.hashCode == tt7.hashCode?", false, tt6.hashCode() == tt7.hashCode() ); + + test( "tt8 equals tt7?", true, tt8.equals( tt7 ) ); + test( "tt8.hashCode == tt7.hashCode?", true, tt8.hashCode() == tt7.hashCode() ); + + test( "tt6 == tt7?", false, tt6 == tt7 ); + test( "tt8 == tt7?", false, tt8 == tt7 ); + test( "tt9 == tt7?", false, tt9 == tt7 ); + + tt6 = tt6.makeCanonical(); + tt8 = tt8.makeCanonical(); + tt9 = tt9.makeCanonical(); + + test( "tt6 == tt7?", false, tt6 == tt7 ); + test( "tt8 == tt7?", true, tt8 == tt7 ); + test( "tt9 == tt7?", false, tt9 == tt7 ); + } + + + public static void testTokenTupleSet() { + + + } + + + + + public static void garbage() { + /* + + TokenTupleSet tts0 = new TokenTupleSet( tt0 ); @@ -191,7 +275,7 @@ public class Main { System.out.println( "rs3 is "+rs3 ); */ - + /* TokenTuple tt11 = new TokenTuple( new Integer( 1 ), false, TokenTuple.ARITY_ONE ); @@ -215,7 +299,7 @@ public class Main { TokenTuple tt16 = new TokenTuple( new Integer( 6 ), true, TokenTuple.ARITY_MANY ); - + */ /* TokenTupleSet tts10 = new TokenTupleSet(); tts10 = tts10.add( tt11 ); @@ -226,6 +310,7 @@ public class Main { tts10 = tts10.add( tt16 ); */ + /* TokenTuple tt21 = new TokenTuple( new Integer( 1 ), false, TokenTuple.ARITY_ONE ); @@ -249,7 +334,7 @@ public class Main { TokenTuple tt26 = new TokenTuple( new Integer( 8 ), true, TokenTuple.ARITY_MANY ); - + */ /* TokenTupleSet tts20 = new TokenTupleSet(); tts20 = tts20.add( tt21 ); @@ -266,7 +351,7 @@ public class Main { System.out.println( "" ); System.out.println( "tts30 is "+tts30 ); */ - + /* TokenTupleSet tts40 = new TokenTupleSet(); tts40 = tts40.add( tt21 ); tts40 = tts40.add( tt23 ); @@ -314,5 +399,6 @@ public class Main { System.out.println( "rs50 is "+rs50 ); System.out.println( "" ); System.out.println( "rs60 is "+rs60 ); + */ } } -- 2.34.1