From e80b12b7baa4ec69727b8e60dc7b994313332dcf Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 24 Jun 2008 18:51:27 +0000 Subject: [PATCH] Some initial implementation of reachability for ownership analysis. --- .../OwnershipAnalysis/OwnershipGraph.java | 40 ++++++++++++++ .../OwnershipAnalysis/ReachabilitySet.java | 15 ++++++ .../OwnershipAnalysis/TokenTuple.java | 54 +++++++++++++++++++ .../OwnershipAnalysis/TokenTupleSet.java | 31 +++++++++++ Robust/src/Makefile | 3 ++ 5 files changed, 143 insertions(+) create mode 100644 Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java create mode 100644 Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java create mode 100644 Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index e5061e12..e58dff7f 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -24,6 +24,10 @@ public class OwnershipGraph { public HashSet allocationSites; + // CHANGE! Map HRN ID's to token sets (sets of IDs!) + public Hashtable< HeapRegionNode, HashSet< HashSet > > alpha; + //public Hashtable< touple< HRN, HRN >, HashSet< HashSet > > beta; + public OwnershipGraph( int allocationDepth ) { this.allocationDepth = allocationDepth; @@ -34,6 +38,8 @@ public class OwnershipGraph { paramIndex2id = new Hashtable(); allocationSites = new HashSet (); + + alpha = new Hashtable< HeapRegionNode, HashSet< HashSet > >(); } @@ -644,6 +650,7 @@ public class OwnershipGraph { mergeReferenceEdges ( og ); mergeId2paramIndex ( og ); mergeAllocationSites( og ); + mergeTokenSets ( og ); } protected void mergeOwnershipNodes( OwnershipGraph og ) { @@ -811,6 +818,39 @@ public class OwnershipGraph { } + + protected void mergeTokenSets( OwnershipGraph og ) { + // alpha = new Hashtable< HeapRegionNode, HashSet< HashSet > >(); + + // if a key is in one or the other token set, + // add it to the merged token set. + // if a key is in both graphs, the merged + // token set should have that key and the union + // of values as the merged value. + + /* + Set alphaB = og.alpha.entrySet(); + Iterator iB = alphaB.iterator(); + while( iB.hasNext() ) { + Map.Entry meB = (Map.Entry) iB.next(); + HeapRegionNode hrnKeyB = (HeapRegionNode) meB.getKey(); + HashSet< HashSet > > tokenSetsB = + (HashSet< HashSet > >) meB.getValue(); + + if( !alpha.containsKey( hrnKeyB ) ) { + alpha.put( hrnKeyB, tokenSetsB ); + } else { + + } + } + */ + } + + + + + + // it is necessary in the equals() member functions // to "check both ways" when comparing the data // structures of two graphs. For instance, if all diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java new file mode 100644 index 00000000..46c4c8f2 --- /dev/null +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -0,0 +1,15 @@ +package Analysis.OwnershipAnalysis; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + + +public class ReachabilitySet { + + public HashSet possibleReachabilities; + + + +} \ No newline at end of file diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java new file mode 100644 index 00000000..2185f273 --- /dev/null +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTuple.java @@ -0,0 +1,54 @@ +package Analysis.OwnershipAnalysis; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + + +// a token touple is a pair that indicates a +// heap region node and an arity +public class TokenTuple +{ + 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(); + arity = ARITY_ONE; + } + + public TokenTuple( Integer token, + boolean isNewSummary, + int arity ) { + this.token = token; + this.isNewSummary = isNewSummary; + this.arity = arity; + } + + public Integer getToken() { return token; } + public int getArity() { return arity; } + + public void increaseArity() { + if( isNewSummary ) { + arity = ARITY_MANY; + } + } + + public boolean equals( TokenTuple tt ) { + return token.equals( tt.getToken() ) && + arity == tt.getArity(); + } + + public TokenTuple copy() { + return new TokenTuple( token, + isNewSummary, + arity ); + } +} diff --git a/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java new file mode 100644 index 00000000..e07b615b --- /dev/null +++ b/Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.java @@ -0,0 +1,31 @@ +package Analysis.OwnershipAnalysis; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + + +public class TokenTupleSet { + + public HashSet tokenTuples; + + public TokenTupleSet() { + tokenTuples = new HashSet(); + } + + public TokenTupleSet( TokenTuple tt ) { + this(); + tokenTuples.add( tt ); + } + + public TokenTupleSet( TokenTupleSet tts ) { + tokenTuples = (HashSet) tts.tokenTuples.clone(); //COPY?! + } + + public TokenTupleSet union( TokenTupleSet ttsIn ) { + TokenTupleSet ttsOut = new TokenTupleSet( this ); + ttsOut.tokenTuples.addAll( ttsIn.tokenTuples ); + return ttsOut; + } +} diff --git a/Robust/src/Makefile b/Robust/src/Makefile index 3aeaeddd..6efe1c0f 100644 --- a/Robust/src/Makefile +++ b/Robust/src/Makefile @@ -80,6 +80,9 @@ Analysis/OwnershipAnalysis/LabelNode.class \ Analysis/OwnershipAnalysis/HeapRegionNode.class \ Analysis/OwnershipAnalysis/ReferenceEdgeProperties.class \ Analysis/OwnershipAnalysis/AllocationSite.class \ +Analysis/OwnershipAnalysis/TokenTuple.class \ +Analysis/OwnershipAnalysis/TokenTupleSet.class \ +Analysis/OwnershipAnalysis/ReachabilitySet.class \ Util/GraphNode.class Util/Namer.class Util/Relation.class \ Interface/HTTPHeader.class Interface/HTTPResponse.class \ Interface/HTTPServices.class Interface/HashStrings.class \ -- 2.34.1