From cc701f275ad8d87f04457591a978cc4ec3f3f9e6 Mon Sep 17 00:00:00 2001
From: jjenista <jjenista>
Date: Wed, 28 Nov 2007 21:51:44 +0000
Subject: [PATCH] OwnershipGraph and Node classes are working and tested.
OwnershipAnalysis does not correctly construct the ownership graph for a
simple program, consider this version of that class invalid.
---
.../OwnershipAnalysis/OwnershipAnalysis.java | 109 ++--
.../OwnershipAnalysis/OwnershipGraph.java | 539 ++++++++++++++----
.../OwnershipHeapRegionNode.java | 35 +-
.../OwnershipAnalysis/OwnershipLabelNode.java | 20 +-
.../OwnershipAnalysis/OwnershipNode.java | 81 +--
.../OwnershipAnalysisTest/test01/makefile | 8 +-
.../OwnershipAnalysisTest/test01/test01.java | 2 -
.../testGraphs/Main.java | 89 +++
.../OwnershipAnalysisTest/testGraphs/makefile | 11 +
9 files changed, 631 insertions(+), 263 deletions(-)
create mode 100644 Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java
create mode 100644 Robust/src/Tests/OwnershipAnalysisTest/testGraphs/makefile
diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
index f7698581..8cfaf953 100644
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java
@@ -22,7 +22,6 @@ public class OwnershipAnalysis {
// in the program
public OwnershipAnalysis(State state) throws java.io.IOException {
this.state=state;
-
analyzeTasks();
}
@@ -36,7 +35,7 @@ public class OwnershipAnalysis {
flatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
TaskDescriptor td = (TaskDescriptor)it_tasks.next();
- FlatMethod fm = state.getMethodFlat( td );
+ FlatMethod fm = state.getMethodFlat( td );
// give every node in the flat IR graph a unique label
// so a human being can inspect the graph and verify
@@ -46,16 +45,7 @@ public class OwnershipAnalysis {
labelindex = 0;
labelFlatNodes( fm );
- // add method parameters to the list of heap regions
- // and remember names for analysis
- OwnershipGraph og = getGraphFromFlat( fm );
- for( int i = 0; i < fm.numParameters(); ++i ) {
- TempDescriptor tdParam = fm.getParameter( i );
- og.newHeapRegion( tdParam );
- og.addAnalysisRegion( tdParam );
- }
-
- String taskname = td.getSymbol();
+ String taskname = td.getSymbol();
analyzeFlatIRGraph( fm, taskname );
}
}
@@ -72,34 +62,62 @@ public class OwnershipAnalysis {
}
private OwnershipGraph getGraphFromFlat( FlatNode fn ) {
- if( !flatNodeToOwnershipGraph.containsKey(fn) ) {
+ if( !flatNodeToOwnershipGraph.containsKey( fn ) ) {
flatNodeToOwnershipGraph.put( fn, new OwnershipGraph() );
}
- return flatNodeToOwnershipGraph.get(fn);
+ return flatNodeToOwnershipGraph.get( fn );
}
- private void analyzeFlatIRGraph( FlatMethod fm, String taskname ) throws java.io.IOException {
+ private void setGraphForFlat( FlatNode fn, OwnershipGraph og ) {
+ flatNodeToOwnershipGraph.put( fn, og );
+ }
+
+ private void analyzeFlatIRGraph( FlatMethod flatm, String taskname ) throws java.io.IOException {
visited=new HashSet<FlatNode>();
toVisit=new HashSet<FlatNode>();
- toVisit.add(fm);
+ toVisit.add( flatm );
while( !toVisit.isEmpty() ) {
- FlatNode fn=(FlatNode)toVisit.iterator().next();
- toVisit.remove(fn);
- visited.add(fn);
-
- // get this node's ownership graph, or create a new one
- OwnershipGraph og = getGraphFromFlat( fn );
-
+ FlatNode fn = (FlatNode)toVisit.iterator().next();
+ toVisit.remove( fn );
+ visited.add( fn );
+
+ // perform this node's contributions to the ownership
+ // graph on a new copy, then compare it to the old graph
+ // at this node to see if anything was updated.
+ OwnershipGraph og = new OwnershipGraph();
+
+ // start by merging all incoming node's graphs
+ for( int i = 0; i < fn.numPrev(); ++i ) {
+ FlatNode pn = fn.getPrev( i );
+ OwnershipGraph ogParent = getGraphFromFlat( pn );
+ og.merge( ogParent );
+ }
+
TempDescriptor src;
TempDescriptor dst;
FieldDescriptor fld;
+ String nodeDescription = "No description";
+ boolean writeGraph = false;
- switch(fn.kind()) {
+ // use node type to decide what alterations to make
+ // to the ownership graph
+ switch( fn.kind() ) {
case FKind.FlatMethod:
- og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Method" ) );
+ FlatMethod fm = (FlatMethod) fn;
+
+ // add method parameters to the list of heap regions
+ // and remember names for analysis
+ for( int i = 0; i < fm.numParameters(); ++i ) {
+ TempDescriptor tdParam = fm.getParameter( i );
+ og.newHeapRegion( tdParam );
+ og.addAnalysisRegion( tdParam );
+ }
+
+ nodeDescription = "Method";
+ writeGraph = true;
break;
case FKind.FlatOpNode:
@@ -108,7 +126,8 @@ public class OwnershipAnalysis {
src = fon.getLeft();
dst = fon.getDest();
og.assignTempToTemp( src, dst );
- og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Op" ) );
+ nodeDescription = "Op";
+ writeGraph = true;
}
break;
@@ -118,7 +137,8 @@ public class OwnershipAnalysis {
dst = ffn.getDst();
fld = ffn.getField();
og.assignTempToField( src, dst, fld );
- og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Field" ) );
+ nodeDescription = "Field";
+ writeGraph = true;
break;
case FKind.FlatSetFieldNode:
@@ -127,25 +147,36 @@ public class OwnershipAnalysis {
dst = fsfn.getDst();
fld = fsfn.getField();
og.assignFieldToTemp( src, dst, fld );
- og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "SetField" ) );
+ nodeDescription = "SetField";
+ writeGraph = true;
+
break;
case FKind.FlatReturnNode:
- og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Return" ) );
+ nodeDescription = "Return";
+ writeGraph = true;
og.writeCondensedAnalysis( makeCondensedAnalysisName( taskname, flatnodetolabel.get(fn) ) );
break;
}
+
+ if( writeGraph ) {
+ og.writeGraph( makeNodeName( taskname,
+ flatnodetolabel.get( fn ),
+ nodeDescription ) );
+ }
- // send this flat node's ownership graph along the out edges
- // to be taken by the next flat edges in the flow, or if they
- // already have a graph, to be merged
- for(int i=0;i<fn.numNext();i++) {
- FlatNode nn=fn.getNext(i);
-
- if( !visited.contains( nn ) ) {
- // FIX THE COPY!!!!!!!!!!!!!!!
- //flatNodeToOwnershipGraph.put( nn, og.copy() );
- flatNodeToOwnershipGraph.put( nn, og );
+ // if the results of the new graph are different from
+ // the current graph at this node, replace the graph
+ // with the update and enqueue the children for
+ // processing
+ OwnershipGraph ogOld = getGraphFromFlat( fn );
+
+ if( !og.equivalent( ogOld ) ) {
+ setGraphForFlat( fn, og );
+
+ for( int i = 0; i < fn.numNext(); i++ ) {
+ FlatNode nn = fn.getNext( i );
+ visited.remove( nn );
toVisit.add( nn );
}
}
diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
index 1142b59e..10854040 100644
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java
@@ -8,20 +8,23 @@ import java.io.*;
public class OwnershipGraph {
- protected int heapRegionNodeIDs;
- protected Vector<OwnershipHeapRegionNode> heapRoots;
+ protected static int heapRegionNodeIDs = 0;
+ public Hashtable<Integer, OwnershipHeapRegionNode> id2ohrn;
+ public Hashtable<Integer, OwnershipHeapRegionNode> heapRoots;
- protected int labelNodeIDs;
- protected Hashtable<TempDescriptor, OwnershipLabelNode> td2ln;
+ protected static int labelNodeIDs = 0;
+ public Hashtable<TempDescriptor, OwnershipLabelNode> td2ln;
protected Vector<TempDescriptor> analysisRegionLabels;
protected Hashtable<TempDescriptor, TempDescriptor> linkedRegions;
-
+
+ protected static final int VISIT_OHRN_WRITE_FULL = 0;
+ protected static final int VISIT_OHRN_WRITE_CONDENSED = 1;
+
public OwnershipGraph() {
- heapRegionNodeIDs = 0;
- heapRoots = new Vector<OwnershipHeapRegionNode>();
+ id2ohrn = new Hashtable<Integer, OwnershipHeapRegionNode>();
+ heapRoots = new Hashtable<Integer, OwnershipHeapRegionNode>();
- labelNodeIDs = 0;
td2ln = new Hashtable<TempDescriptor, OwnershipLabelNode>();
analysisRegionLabels = new Vector<TempDescriptor>();
@@ -30,136 +33,402 @@ public class OwnershipGraph {
public void assignTempToTemp( TempDescriptor src,
TempDescriptor dst ) {
+
OwnershipLabelNode srcln = getLabelNodeFromTemp( src );
- OwnershipHeapRegionNode hrn = srcln.getOwnershipHeapRegionNode();
OwnershipLabelNode dstln = getLabelNodeFromTemp( dst );
- dstln.setOwnershipHeapRegionNode( hrn );
+
+ dstln.clearReachableRegions();
+ OwnershipHeapRegionNode ohrn = null;
+ Iterator srcRegionsItr = srcln.iteratorToReachableRegions();
+ while( srcRegionsItr.hasNext() ) {
+ ohrn = (OwnershipHeapRegionNode)srcRegionsItr.next();
+
+ dstln.addReachableRegion( ohrn );
+ }
}
- public void assignTempToField( TempDescriptor src,
+ public void assignTempToField( TempDescriptor src,
TempDescriptor dst,
FieldDescriptor fd ) {
+
OwnershipLabelNode srcln = getLabelNodeFromTemp( src );
- OwnershipHeapRegionNode hrn = srcln.getOwnershipHeapRegionNode();
OwnershipLabelNode dstln = getLabelNodeFromTemp( dst );
- dstln.setOwnershipHeapRegionNode( hrn.getField( fd ) );
+
+ dstln.clearReachableRegions();
+ OwnershipHeapRegionNode ohrn = null;
+ Iterator srcRegionsItr = srcln.iteratorToReachableRegions();
+ while( srcRegionsItr.hasNext() ) {
+ ohrn = (OwnershipHeapRegionNode)srcRegionsItr.next();
+
+ OwnershipHeapRegionNode ohrnOneHop = null;
+ Iterator ohrnRegionsItr = ohrn.iteratorToReachableRegions();
+ while( ohrnRegionsItr.hasNext() ) {
+ ohrnOneHop = (OwnershipHeapRegionNode)ohrnRegionsItr.next();
+
+ dstln.addReachableRegion( ohrnOneHop );
+ }
+ }
}
public void assignFieldToTemp( TempDescriptor src,
TempDescriptor dst,
FieldDescriptor fd ) {
+
OwnershipLabelNode srcln = getLabelNodeFromTemp( src );
- OwnershipHeapRegionNode srchrn = srcln.getOwnershipHeapRegionNode();
OwnershipLabelNode dstln = getLabelNodeFromTemp( dst );
- OwnershipHeapRegionNode dsthrn = dstln.getOwnershipHeapRegionNode();
- dsthrn.setField( fd, srchrn );
+
+ OwnershipHeapRegionNode ohrn = null;
+ Iterator dstRegionsItr = dstln.iteratorToReachableRegions();
+ while( dstRegionsItr.hasNext() ) {
+ ohrn = (OwnershipHeapRegionNode)dstRegionsItr.next();
+
+ OwnershipHeapRegionNode ohrnSrc = null;
+ Iterator srcRegionsItr = srcln.iteratorToReachableRegions();
+ while( srcRegionsItr.hasNext() ) {
+ ohrnSrc = (OwnershipHeapRegionNode)srcRegionsItr.next();
+
+ ohrn.addReachableRegion( ohrnSrc );
+ }
+ }
}
+ // for parameters
public void newHeapRegion( TempDescriptor td ) {
- TypeDescriptor typeDesc = td.getType();
- OwnershipHeapRegionNode hrn = allocate( typeDesc );
+
+ Integer id = new Integer( heapRegionNodeIDs );
+ ++heapRegionNodeIDs;
+ OwnershipHeapRegionNode ohrn = new OwnershipHeapRegionNode( id );
+ ohrn.addReachableRegion( ohrn );
+ id2ohrn.put( id, ohrn );
+
OwnershipLabelNode ln = getLabelNodeFromTemp( td );
- ln.setOwnershipHeapRegionNode( hrn );
- heapRoots.add( hrn );
+ ln.clearReachableRegions();
+ ln.addReachableRegion( ohrn );
+
+ heapRoots.put( ohrn.getID(), ohrn );
}
public void addAnalysisRegion( TempDescriptor td ) {
analysisRegionLabels.add( td );
}
- protected OwnershipHeapRegionNode allocate( TypeDescriptor typeDesc ) {
- OwnershipHeapRegionNode hrn =
- new OwnershipHeapRegionNode( heapRegionNodeIDs );
- ++heapRegionNodeIDs;
-
- if( typeDesc.isClass() ) {
- ClassDescriptor classDesc = typeDesc.getClassDesc();
- Iterator fieldItr = classDesc.getFields();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor)fieldItr.next();
- TypeDescriptor fieldType = fd.getType();
- OwnershipHeapRegionNode fieldNode = allocate( fieldType );
- hrn.setField( fd, fieldNode );
- }
- }
-
- return hrn;
- }
-
protected OwnershipLabelNode getLabelNodeFromTemp( TempDescriptor td ) {
if( !td2ln.containsKey( td ) ) {
- td2ln.put( td, new OwnershipLabelNode( labelNodeIDs, td ) );
+ Integer id = new Integer( labelNodeIDs );
+ td2ln.put( td, new OwnershipLabelNode( id, td ) );
++labelNodeIDs;
}
return td2ln.get( td );
}
- /*
- public OwnershipGraph copy() {
- OwnershipGraph newog = new OwnershipGraph();
- // first create a node in the new graph from
- // every temp desc in the old graph
- Set s = td2on.entrySet();
- Iterator i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- OwnershipLabelNode nu = (OwnershipLabelNode) me.getValue();
- newog.getOwnershipFromTemp( nu.getTempDescriptor() );
+
+ ////////////////////////////////////////////////////
+ //
+ // In the functions merge() and equivalent(),
+ // use the heap region node IDs to equate heap
+ // region nodes and use temp descriptors to equate
+ // label nodes.
+ //
+ // in these functions the graph of this object is B
+ // and the graph of the incoming object is A
+ //
+ ////////////////////////////////////////////////////
+
+ public void merge( OwnershipGraph og ) {
+
+ // make sure all the heap region nodes from the
+ // incoming graph that this graph does not have
+ // are allocated-their edges will be added later
+ Set sA = og.id2ohrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ OwnershipHeapRegionNode ohrnA = (OwnershipHeapRegionNode) meA.getValue();
+
+ // if this graph doesn't have a node the
+ // incoming graph has, allocate it
+ if( !id2ohrn.containsKey( idA ) ) {
+ OwnershipHeapRegionNode ohrnNewB = new OwnershipHeapRegionNode( idA );
+ id2ohrn.put( idA, ohrnNewB );
+ }
}
- // then use every out-edge of the old graph to
- // create the edges of the new graph
- i = s.iterator();
- while( i.hasNext() ) {
- Map.Entry me = (Map.Entry) i.next();
- OwnershipLabelNode nu = (OwnershipLabelNode) me.getValue();
- for( int j = 0; j < nu.numOutEdges(); ++j ) {
- OwnershipLabelNode nv = nu.getOutEdge( j );
- newog.addEdge( nu.getTempDescriptor(), nv.getTempDescriptor() );
+ // add heap region->heap region edges that are
+ // in the incoming graph and not in this graph
+ sA = og.id2ohrn.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ OwnershipHeapRegionNode ohrnA = (OwnershipHeapRegionNode) meA.getValue();
+
+ OwnershipHeapRegionNode ohrnChildA = null;
+ Iterator heapRegionsItrA = ohrnA.iteratorToReachableRegions();
+
+ while( heapRegionsItrA.hasNext() ) {
+ ohrnChildA = (OwnershipHeapRegionNode)heapRegionsItrA.next();
+
+ Integer idChildA = ohrnChildA.getID();
+
+ // at this point we know an edge in graph A exists
+ // idA -> idChildA, does this exist in B?
+ boolean edgeFound = false;
+ assert id2ohrn.containsKey( idA );
+ OwnershipHeapRegionNode ohrnB = id2ohrn.get( idA );
+
+ OwnershipHeapRegionNode ohrnChildB = null;
+ Iterator heapRegionsItrB = ohrnB.iteratorToReachableRegions();
+ while( heapRegionsItrB.hasNext() ) {
+ ohrnChildB = (OwnershipHeapRegionNode)heapRegionsItrB.next();
+
+ if( ohrnChildB.getID() == idChildA ) {
+ edgeFound = true;
+ }
+ }
+
+ if( !edgeFound ) {
+ assert id2ohrn.containsKey( idChildA );
+ OwnershipHeapRegionNode ohrnChildToAddB = id2ohrn.get( idChildA );
+ ohrnB.addReachableRegion( ohrnChildToAddB );
+ }
+ }
+ }
+
+ // now add any label nodes that are in graph B but
+ // not in A, and at the same time construct any
+ // edges that are not in A
+ sA = og.td2ln.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ OwnershipLabelNode olnA = (OwnershipLabelNode) meA.getValue();
+
+ // if the label doesn't exist in B, allocate and add it
+ if( !td2ln.containsKey( tdA ) ) {
+ Integer idA = olnA.getID();
+ OwnershipLabelNode olnNewB = new OwnershipLabelNode( idA, tdA );
+ td2ln.put( tdA, olnNewB );
+ }
+
+ OwnershipHeapRegionNode ohrnChildA = null;
+ Iterator heapRegionsItrA = olnA.iteratorToReachableRegions();
+ while( heapRegionsItrA.hasNext() ) {
+ ohrnChildA = (OwnershipHeapRegionNode)heapRegionsItrA.next();
+
+ Integer idChildA = ohrnChildA.getID();
+
+ // at this point we know an edge in graph A exists
+ // tdA -> idChildA, does this edge exist in B?
+ boolean edgeFound = false;
+ assert td2ln.containsKey( tdA );
+ OwnershipLabelNode olnB = td2ln.get( tdA );
+
+ OwnershipHeapRegionNode ohrnChildB = null;
+ Iterator heapRegionsItrB = olnB.iteratorToReachableRegions();
+ while( heapRegionsItrB.hasNext() ) {
+ ohrnChildB = (OwnershipHeapRegionNode)heapRegionsItrB.next();
+
+ if( ohrnChildB.getID() == idChildA ) {
+ edgeFound = true;
+ }
+ }
+
+ if( !edgeFound ) {
+ assert id2ohrn.containsKey( idChildA );
+ OwnershipHeapRegionNode ohrnChildToAddB = id2ohrn.get( idChildA );
+ olnB.addReachableRegion( ohrnChildToAddB );
+ }
+ }
+ }
+
+ // also merge the heapRoots
+ sA = og.heapRoots.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ OwnershipHeapRegionNode ohrnA = (OwnershipHeapRegionNode) meA.getValue();
+
+ if( !heapRoots.containsKey( idA ) ) {
+
+ assert id2ohrn.containsKey( idA );
+ OwnershipHeapRegionNode ohrnB = id2ohrn.get( idA );
+ heapRoots.put( idA, ohrnB );
+ }
+ }
+ }
+
+ // see notes for merge() above about how to equate
+ // nodes in ownership graphs
+ public boolean equivalent( OwnershipGraph og ) {
+
+ // are all heap region nodes in B also in A?
+ Set sB = id2ohrn.entrySet();
+ Iterator iB = sB.iterator();
+ while( iB.hasNext() ) {
+ Map.Entry meB = (Map.Entry) iB.next();
+ Integer idB = (Integer) meB.getKey();
+ if( !og.id2ohrn.containsKey( idB ) ) {
+ return false;
}
+ }
+
+ // for every heap region node in A, make sure
+ // it is in B and then check that they have
+ // all the same edges
+ Set sA = og.id2ohrn.entrySet();
+ Iterator iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ OwnershipHeapRegionNode ohrnA = (OwnershipHeapRegionNode) meA.getValue();
+
+ if( !id2ohrn.containsKey( idA ) ) {
+ return false;
+ }
+
+ OwnershipHeapRegionNode ohrnChildA = null;
+ Iterator heapRegionsItrA = ohrnA.iteratorToReachableRegions();
+ while( heapRegionsItrA.hasNext() ) {
+ ohrnChildA = (OwnershipHeapRegionNode)heapRegionsItrA.next();
+
+ Integer idChildA = ohrnChildA.getID();
+
+ // does this child exist in B?
+ if( !id2ohrn.containsKey( idChildA ) ) {
+ return false;
+ }
+
+ // at this point we know an edge in graph A exists
+ // idA -> idChildA, does this edge exist in B?
+ boolean edgeFound = false;
+ assert id2ohrn.containsKey( idA );
+ OwnershipHeapRegionNode ohrnB = id2ohrn.get( idA );
+
+ OwnershipHeapRegionNode ohrnChildB = null;
+ Iterator heapRegionsItrB = ohrnB.iteratorToReachableRegions();
+ while( heapRegionsItrB.hasNext() ) {
+ ohrnChildB = (OwnershipHeapRegionNode)heapRegionsItrB.next();
+
+ if( ohrnChildB.getID() == idChildA ) {
+ edgeFound = true;
+ }
+ }
+
+ if( !edgeFound ) {
+ return false;
+ }
+ }
+ }
+
+ // are all label nodes in B also in A?
+ sB = td2ln.entrySet();
+ iB = sB.iterator();
+ while( iB.hasNext() ) {
+ Map.Entry meB = (Map.Entry) iB.next();
+ TempDescriptor tdB = (TempDescriptor) meB.getKey();
+ if( !og.td2ln.containsKey( tdB ) ) {
+ return false;
+ }
+ }
+
+ // for every label node in A make sure it is in
+ // B and has the same references
+ sA = og.td2ln.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ TempDescriptor tdA = (TempDescriptor) meA.getKey();
+ OwnershipLabelNode olnA = (OwnershipLabelNode) meA.getValue();
+
+ if( !td2ln.containsKey( tdA ) ) {
+ return false;
+ }
+
+ OwnershipHeapRegionNode ohrnChildA = null;
+ Iterator heapRegionsItrA = olnA.iteratorToReachableRegions();
+ while( heapRegionsItrA.hasNext() ) {
+ ohrnChildA = (OwnershipHeapRegionNode)heapRegionsItrA.next();
+
+ Integer idChildA = ohrnChildA.getID();
+
+ // does this child exist in B?
+ if( !id2ohrn.containsKey( idChildA ) ) {
+ return false;
+ }
+
+ // at this point we know an edge in graph A exists
+ // tdA -> idChildA, does this edge exist in B?
+ boolean edgeFound = false;
+ assert td2ln.containsKey( tdA );
+ OwnershipLabelNode olnB = td2ln.get( tdA );
+
+ OwnershipHeapRegionNode ohrnChildB = null;
+ Iterator heapRegionsItrB = olnB.iteratorToReachableRegions();
+ while( heapRegionsItrB.hasNext() ) {
+ ohrnChildB = (OwnershipHeapRegionNode)heapRegionsItrB.next();
+
+ if( ohrnChildB.getID() == idChildA ) {
+ edgeFound = true;
+ }
+ }
+
+ if( !edgeFound ) {
+ return false;
+ }
+ }
}
- return newog;
- }
- */
+ // finally check if the heapRoots are equivalent
+ sA = og.heapRoots.entrySet();
+ iA = sA.iterator();
+ while( iA.hasNext() ) {
+ Map.Entry meA = (Map.Entry) iA.next();
+ Integer idA = (Integer) meA.getKey();
+ OwnershipHeapRegionNode ohrnA = (OwnershipHeapRegionNode) meA.getValue();
+
+ if( !heapRoots.containsKey( idA ) ) {
+ return false;
+ }
+ }
+
+ return true;
+ }
public void writeGraph( String graphName ) throws java.io.IOException {
+
BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
bw.write( "digraph "+graphName+" {\n" );
- for( int i = 0; i < heapRoots.size(); ++i ) {
- OwnershipHeapRegionNode hrn = heapRoots.get( i );
- visitHeapNodes( bw, hrn );
- }
-
- Set s = td2ln.entrySet();
+ Set s = heapRoots.entrySet();
Iterator i = s.iterator();
while( i.hasNext() ) {
Map.Entry me = (Map.Entry) i.next();
- OwnershipLabelNode ln = (OwnershipLabelNode) me.getValue();
- OwnershipHeapRegionNode lnhrn = ln.getOwnershipHeapRegionNode();
- bw.write( " "+ln.toString()+" -> "+lnhrn.toString()+";\n" );
+ OwnershipHeapRegionNode ohrn = (OwnershipHeapRegionNode) me.getValue();
+ traverseHeapNodesTop( VISIT_OHRN_WRITE_FULL, ohrn, bw, null );
}
- bw.write( "}\n" );
- bw.close();
- }
+ s = td2ln.entrySet();
+ i = s.iterator();
+ while( i.hasNext() ) {
+ Map.Entry me = (Map.Entry) i.next();
+ OwnershipLabelNode oln = (OwnershipLabelNode) me.getValue();
- protected void visitHeapNodes( BufferedWriter bw,
- OwnershipHeapRegionNode hrn ) throws java.io.IOException {
- bw.write( " "+hrn.toString()+"[shape=box];\n" );
+ OwnershipHeapRegionNode ohrn = null;
+ Iterator heapRegionsItr = oln.iteratorToReachableRegions();
+ while( heapRegionsItr.hasNext() ) {
+ ohrn = (OwnershipHeapRegionNode)heapRegionsItr.next();
- Iterator fitr = hrn.getFieldIterator();
- while( fitr.hasNext() ) {
- Map.Entry me = (Map.Entry) fitr.next();
- FieldDescriptor fd = (FieldDescriptor) me.getKey();
- OwnershipHeapRegionNode childhrn = (OwnershipHeapRegionNode) me.getValue();
- bw.write( " "+hrn.toString()+" -> "+childhrn.toString()+
- "[label=\""+fd.getSymbol()+"\"];\n" );
- visitHeapNodes( bw, childhrn );
+ bw.write( " "+oln.toString()+" -> "+ohrn.toString()+";\n" );
+ }
}
+
+ bw.write( "}\n" );
+ bw.close();
}
public void writeCondensedAnalysis( String graphName ) throws java.io.IOException {
@@ -170,10 +439,15 @@ public class OwnershipGraph {
for( int i = 0; i < analysisRegionLabels.size(); ++i ) {
TempDescriptor td = analysisRegionLabels.get( i );
bw.write( " "+td.getSymbol()+";\n" );
+ OwnershipLabelNode oln = getLabelNodeFromTemp( td );
+
+ OwnershipHeapRegionNode ohrn = null;
+ Iterator heapRegionsItr = oln.iteratorToReachableRegions();
+ while( heapRegionsItr.hasNext() ) {
+ ohrn = (OwnershipHeapRegionNode)heapRegionsItr.next();
- OwnershipLabelNode oln = getLabelNodeFromTemp( td );
- OwnershipHeapRegionNode hrn = oln.getOwnershipHeapRegionNode();
- condensedVisitHeapNodes( bw, hrn, td );
+ traverseHeapNodesTop( VISIT_OHRN_WRITE_CONDENSED, ohrn, bw, td );
+ }
}
// write out linked regions
@@ -190,38 +464,69 @@ public class OwnershipGraph {
bw.close();
}
- protected void condensedVisitHeapNodes( BufferedWriter bw,
- OwnershipHeapRegionNode hrn,
- TempDescriptor td ) throws java.io.IOException {
- hrn.addAnalysisRegionAlias( td );
-
- Iterator fitr = hrn.getFieldIterator();
- while( fitr.hasNext() ) {
- Map.Entry me = (Map.Entry) fitr.next();
- FieldDescriptor fd = (FieldDescriptor) me.getKey();
- OwnershipHeapRegionNode childhrn = (OwnershipHeapRegionNode) me.getValue();
-
- Vector<TempDescriptor> aliases = childhrn.getAnalysisRegionAliases();
- for( int i = 0; i < aliases.size(); ++i ) {
- TempDescriptor tdn = aliases.get( i );
-
- // only add this alias if it has not been already added
- TempDescriptor tdAlias = null;
- if( linkedRegions.containsKey( td ) ) {
- tdAlias = linkedRegions.get( td );
- }
+ protected void traverseHeapNodesTop( int mode,
+ OwnershipHeapRegionNode ohrn,
+ BufferedWriter bw,
+ TempDescriptor td
+ ) throws java.io.IOException {
+ HashSet<OwnershipHeapRegionNode> visited = new HashSet<OwnershipHeapRegionNode>();
+ traverseHeapNodes( mode, ohrn, bw, td, visited );
+ }
- TempDescriptor tdnAlias = null;
- if( linkedRegions.containsKey( tdn ) ) {
- tdnAlias = linkedRegions.get( tdn );
- }
+ protected void traverseHeapNodes( int mode,
+ OwnershipHeapRegionNode ohrn,
+ BufferedWriter bw,
+ TempDescriptor td,
+ HashSet<OwnershipHeapRegionNode> visited
+ ) throws java.io.IOException {
+ visited.add( ohrn );
+
+ switch( mode ) {
+ case VISIT_OHRN_WRITE_FULL:
+ bw.write( " "+ohrn.toString()+"[shape=box];\n" );
+ break;
+
+ case VISIT_OHRN_WRITE_CONDENSED:
+ ohrn.addAnalysisRegionAlias( td );
+ break;
+ }
- if( tdn != tdAlias && td != tdnAlias ) {
- linkedRegions.put( td, tdn );
+ OwnershipHeapRegionNode ohrnChild = null;
+ Iterator childRegionsItr = ohrn.iteratorToReachableRegions();
+ while( childRegionsItr.hasNext() ) {
+ ohrnChild = (OwnershipHeapRegionNode) childRegionsItr.next();
+
+ switch( mode ) {
+ case VISIT_OHRN_WRITE_FULL:
+ bw.write( " "+ohrn.toString()+" -> "+ohrnChild.toString()+";\n" );
+ break;
+
+ case VISIT_OHRN_WRITE_CONDENSED:
+ Vector<TempDescriptor> aliases = ohrnChild.getAnalysisRegionAliases();
+ for( int i = 0; i < aliases.size(); ++i ) {
+ TempDescriptor tdn = aliases.get( i );
+
+ // only add this alias if it has not been already added
+ TempDescriptor tdAlias = null;
+ if( linkedRegions.containsKey( td ) ) {
+ tdAlias = linkedRegions.get( td );
+ }
+
+ TempDescriptor tdnAlias = null;
+ if( linkedRegions.containsKey( tdn ) ) {
+ tdnAlias = linkedRegions.get( tdn );
+ }
+
+ if( tdn != tdAlias && td != tdnAlias ) {
+ linkedRegions.put( td, tdn );
+ }
}
- }
+ break;
+ }
- condensedVisitHeapNodes( bw, childhrn, td );
+ if( !visited.contains( ohrnChild ) ) {
+ traverseHeapNodes( mode, ohrnChild, bw, td, visited );
+ }
}
}
}
diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java
index ef8bb7dd..54cd1996 100644
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java
@@ -4,40 +4,15 @@ import IR.*;
import IR.Flat.*;
import java.util.*;
-public class OwnershipHeapRegionNode {
+public class OwnershipHeapRegionNode extends OwnershipNode {
- protected int id;
- protected Hashtable<FieldDescriptor, OwnershipHeapRegionNode> fields;
protected Vector<TempDescriptor> analysisRegionAliases;
- public OwnershipHeapRegionNode( int id ) {
- this.id = id;
- fields = new Hashtable<FieldDescriptor, OwnershipHeapRegionNode>();
+ public OwnershipHeapRegionNode( Integer id ) {
+ super( id );
analysisRegionAliases = new Vector<TempDescriptor>();
}
- public void setField( FieldDescriptor fd,
- OwnershipHeapRegionNode ohrn ) {
- fields.put( fd, ohrn );
- }
-
- public OwnershipHeapRegionNode getField( FieldDescriptor fd ) {
- return fields.get( fd );
- }
-
- public Iterator getFieldIterator() {
- Set s = fields.entrySet();
- return s.iterator();
- }
-
- public String getIDString() {
- return (new Integer( id )).toString();
- }
-
- public String toString() {
- return "OHRN"+getIDString();
- }
-
public void addAnalysisRegionAlias( TempDescriptor td ) {
analysisRegionAliases.add( td );
}
@@ -45,4 +20,8 @@ public class OwnershipHeapRegionNode {
public Vector<TempDescriptor> getAnalysisRegionAliases() {
return analysisRegionAliases;
}
+
+ public String toString() {
+ return "OHRN"+getIDString();
+ }
}
diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipLabelNode.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipLabelNode.java
index e6fe8ce2..2c28e53a 100644
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipLabelNode.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipLabelNode.java
@@ -4,33 +4,19 @@ import IR.*;
import IR.Flat.*;
import java.util.*;
-public class OwnershipLabelNode {
+public class OwnershipLabelNode extends OwnershipNode {
- protected int id;
protected TempDescriptor td;
- protected OwnershipHeapRegionNode ohrn;
- public OwnershipLabelNode( int id, TempDescriptor td ) {
- this.id = id;
+ public OwnershipLabelNode( Integer id, TempDescriptor td ) {
+ super( id );
this.td = td;
}
- public OwnershipHeapRegionNode getOwnershipHeapRegionNode() {
- return ohrn;
- }
-
- public void setOwnershipHeapRegionNode( OwnershipHeapRegionNode ohrn ) {
- this.ohrn = ohrn;
- }
-
public TempDescriptor getTempDescriptor() {
return td;
}
- public String getIDString() {
- return (new Integer( id )).toString();
- }
-
public String getTempDescriptorString() {
return td.toString();
}
diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java
index 2555b6cd..2895705a 100644
--- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java
+++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipNode.java
@@ -6,75 +6,46 @@ import java.util.*;
public class OwnershipNode {
- protected int id;
- protected Vector<OwnershipNode> inEdges;
- protected Vector<OwnershipNode> outEdges;
+ protected Integer id;
+ protected HashSet<OwnershipHeapRegionNode> reachableRegions;
+ protected HashSet<OwnershipNode> referencers;
- public OwnershipNode( int id ) {
- this.id = id;
- inEdges = new Vector<OwnershipNode>();
- outEdges = new Vector<OwnershipNode>();
+ public OwnershipNode( Integer id ) {
+ this.id = id;
+ reachableRegions = new HashSet<OwnershipHeapRegionNode>();
+ referencers = new HashSet<OwnershipNode>();
}
- public String getIDString() {
- return (new Integer( id )).toString();
+ public Integer getID() {
+ return id;
}
-
-
- /*
-digraph test
-{
- node [shape=record];
- p1 [label="{P1 p1|{<x>int x| {<m>Thing m|{<j>int j|{Part f|{a|<b>b|c}}|{Part g|{a|b|c}}}}}}"];
- p2 [label="{P2 p2|{<y>int y|<z>int z|{<n>Thing n|{<j>int j|{Part f|{a|<b>b|c}}|{Part g|{a|b|c}}}}}}"];
-
- edge [color=red];
- p1:b -> p2:j;
-}
- */
-
- /*
- public String makeDotNode() {
- String
- TypeDescriptor typeDesc = td.getType();
- if( typeDesc.isClass() ) {
- ClassDescriptor classDesc = typeDesc.getClassDesc();
- Iterator fieldItr = classDesc.getFields();
- while( fieldItr.hasNext() ) {
- FieldDescriptor fd = (FieldDescriptor)it.next();
- }
- } else if( typeDesc.isArray() ) {
- // deal with arrays
- } else {
-
- }
- return toString();
+ public String getIDString() {
+ return id.toString();
}
- */
+ public Iterator iteratorToReachableRegions() {
+ return reachableRegions.iterator();
+ }
- public int numInEdges() {
- return inEdges.size();
+ public void addReachableRegion( OwnershipHeapRegionNode ohrn ) {
+ assert ohrn!=null;
+ reachableRegions.add( ohrn );
}
- public OwnershipNode getInEdge(int i) {
- return (OwnershipNode) inEdges.get(i);
+ public void clearReachableRegions() {
+ reachableRegions.clear();
}
- public void addInEdge(OwnershipNode n) {
- inEdges.add(n);
+ public Iterator iteratorToReferencers() {
+ return referencers.iterator();
}
- public int numOutEdges() {
- return outEdges.size();
+ public void addReferencer( OwnershipNode on ) {
+ referencers.add( on );
}
- public OwnershipNode getOutEdge(int i) {
- return (OwnershipNode) outEdges.get(i);
- }
-
- public void addOutEdge(OwnershipNode n) {
- outEdges.add(n);
+ public void clearReferencers() {
+ referencers.clear();
}
-}
+}
\ No newline at end of file
diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile
index 26548ad3..72b2f27e 100644
--- a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile
+++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile
@@ -3,14 +3,12 @@ PROGRAM=test01
SOURCE_FILES=test01.java
BUILDSCRIPT=~/research/Robust/src/buildscript
-
+BSFLAGS= -recover -flatirtasks -ownership -enable-assertions
all: view
view: PNGs
- eog task*_flatIRGraph*.png &
- eog task*_FN*.png &
- eog task*_Ownership*.png &
+ eog *.png &
PNGs: DOTs
rm -f *Startup*.dot
@@ -19,7 +17,7 @@ PNGs: DOTs
DOTs: $(PROGRAM).bin
$(PROGRAM).bin: $(SOURCE_FILES)
- $(BUILDSCRIPT) -recover -flatirtasks -ownership -o $(PROGRAM) $(SOURCE_FILES)
+ $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES)
clean:
rm -f $(PROGRAM).bin
diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
index 92ef1a35..5e3bd7d5 100644
--- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
+++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java
@@ -34,8 +34,6 @@ task A( P1 p1f{!a},
{
p1f.m = p2f.n;
- //p2t.n = p2f.n;
-
taskexit( p1f{ a},
p2f{ b} );
}
\ No newline at end of file
diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java
new file mode 100644
index 00000000..76c84fa2
--- /dev/null
+++ b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/Main.java
@@ -0,0 +1,89 @@
+import IR.*;
+import IR.Flat.*;
+import Analysis.OwnershipAnalysis.*;
+import java.util.*;
+import java.io.*;
+
+
+public class Main {
+
+ public static void main(String args[]) throws Exception {
+
+ // ownership graphs g3 and g4 are equivalent
+ // graphs as specified in OwnershipGraph.java,
+ // just built different objects that contain the
+ // equivalent values and merged in a different
+ // order
+
+ OwnershipGraph g0 = new OwnershipGraph();
+ TempDescriptor g0tdp1 = new TempDescriptor( "p1" );
+ TempDescriptor g0tdx = new TempDescriptor( "x" );
+ g0.newHeapRegion ( g0tdp1 );
+ g0.assignTempToTemp( g0tdx, g0tdp1 );
+
+ OwnershipGraph g1 = new OwnershipGraph();
+ TempDescriptor g1tdp2 = new TempDescriptor( "p2" );
+ TempDescriptor g1tdy = new TempDescriptor( "y" );
+ TempDescriptor g1tdz = new TempDescriptor( "z" );
+ g1.newHeapRegion ( g1tdp2 );
+ g1.assignTempToTemp ( g1tdy, g1tdp2 );
+ g1.assignTempToField( g1tdz, g1tdp2, null );
+
+ OwnershipGraph g2 = new OwnershipGraph();
+ TempDescriptor g2tdp3 = new TempDescriptor( "p3" );
+ TempDescriptor g2tdp4 = new TempDescriptor( "p4" );
+ TempDescriptor g2tdw = new TempDescriptor( "w" );
+ g2.newHeapRegion ( g2tdp3 );
+ g2.newHeapRegion ( g2tdp4 );
+ g2.assignTempToTemp ( g2tdw, g2tdp4 );
+ g2.assignFieldToTemp( g2tdp3, g2tdw, null );
+
+ OwnershipGraph g3 = new OwnershipGraph();
+ g3.merge( g0 );
+ g3.merge( g1 );
+ g3.merge( g2 );
+
+ OwnershipGraph g4 = new OwnershipGraph();
+ g4.merge( g1 );
+ g4.merge( g2 );
+ g4.merge( g0 );
+
+ test( "4 == 5?", false, 4 == 5 );
+ test( "3 == 3?", true, 3 == 3 );
+
+ test( "g0 equivalent to g1?", false, g0.equivalent( g1 ) );
+ test( "g1 equivalent to g0?", false, g1.equivalent( g0 ) );
+
+ test( "g0 equivalent to g2?", false, g0.equivalent( g2 ) );
+ test( "g2 equivalent to g0?", false, g2.equivalent( g0 ) );
+
+ test( "g1 equivalent to g2?", false, g1.equivalent( g2 ) );
+ test( "g2 equivalent to g1?", false, g2.equivalent( g1 ) );
+
+ test( "g3 equivalent to g0?", false, g3.equivalent( g0 ) );
+ test( "g3 equivalent to g1?", false, g3.equivalent( g1 ) );
+ test( "g3 equivalent to g2?", false, g3.equivalent( g2 ) );
+
+ test( "g4 equivalent to g0?", false, g4.equivalent( g0 ) );
+ test( "g4 equivalent to g1?", false, g4.equivalent( g1 ) );
+ test( "g4 equivalent to g2?", false, g4.equivalent( g2 ) );
+
+ test( "g3 equivalent to g4?", true, g3.equivalent( g4 ) );
+ test( "g4 equivalent to g3?", true, g4.equivalent( g3 ) );
+ }
+
+ protected static void test( String test,
+ boolean expected,
+ boolean result ) {
+
+ String outcome = "... FAILED";
+ if( expected == result ) {
+ outcome = "... passed";
+ }
+
+ System.out.println( test +
+ " expected " +
+ expected +
+ outcome );
+ }
+}
\ No newline at end of file
diff --git a/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/makefile b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/makefile
new file mode 100644
index 00000000..a7b49017
--- /dev/null
+++ b/Robust/src/Tests/OwnershipAnalysisTest/testGraphs/makefile
@@ -0,0 +1,11 @@
+all: run
+
+Main.class: Main.java
+ javac -classpath ../../.. Main.java
+
+run: Main.class
+ java -classpath .:../../.. Main
+
+clean:
+ rm -f *~
+ rm -f *.class
--
2.34.1