From cc701f275ad8d87f04457591a978cc4ec3f3f9e6 Mon Sep 17 00:00:00 2001 From: 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(); 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(); toVisit=new HashSet(); - 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 heapRoots; + protected static int heapRegionNodeIDs = 0; + public Hashtable id2ohrn; + public Hashtable heapRoots; - protected int labelNodeIDs; - protected Hashtable td2ln; + protected static int labelNodeIDs = 0; + public Hashtable td2ln; protected Vector analysisRegionLabels; protected Hashtable 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(); + id2ohrn = new Hashtable(); + heapRoots = new Hashtable(); - labelNodeIDs = 0; td2ln = new Hashtable(); analysisRegionLabels = new Vector(); @@ -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 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 visited = new HashSet(); + 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 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 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 fields; protected Vector analysisRegionAliases; - public OwnershipHeapRegionNode( int id ) { - this.id = id; - fields = new Hashtable(); + public OwnershipHeapRegionNode( Integer id ) { + super( id ); analysisRegionAliases = new Vector(); } - 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 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 inEdges; - protected Vector outEdges; + protected Integer id; + protected HashSet reachableRegions; + protected HashSet referencers; - public OwnershipNode( int id ) { - this.id = id; - inEdges = new Vector(); - outEdges = new Vector(); + public OwnershipNode( Integer id ) { + this.id = id; + reachableRegions = new HashSet(); + referencers = new HashSet(); } - public String getIDString() { - return (new Integer( id )).toString(); + public Integer getID() { + return id; } - - - /* -digraph test -{ - node [shape=record]; - p1 [label="{P1 p1|{int x| {Thing m|{int j|{Part f|{a|b|c}}|{Part g|{a|b|c}}}}}}"]; - p2 [label="{P2 p2|{int y|int z|{Thing n|{int j|{Part f|{a|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