From cd559c4d07518080f49b2aa986e452e577d95fbe Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 13 Nov 2007 21:34:22 +0000 Subject: [PATCH] Fine heap representation, can only handle simple code. --- .../OwnershipAnalysis/OwnershipAnalysis.java | 26 +++--- .../OwnershipAnalysis/OwnershipGraph.java | 86 ++++++++++++++++--- .../OwnershipHeapRegionNode.java | 12 ++- .../OwnershipAnalysisTest/test01/makefile | 7 +- .../OwnershipAnalysisTest/test01/test01.java | 24 ++++-- 5 files changed, 123 insertions(+), 32 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 0315ac1a..f7698581 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -46,6 +46,15 @@ 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(); analyzeFlatIRGraph( fm, taskname ); } @@ -83,20 +92,10 @@ public class OwnershipAnalysis { // get this node's ownership graph, or create a new one OwnershipGraph og = getGraphFromFlat( fn ); - if( fn.kind() == FKind.FlatMethod ) { - FlatMethod fmd = (FlatMethod) fn; - // the FlatMethod is the top-level node, so generate - // regions of the heap for each parameter to start the - // analysis - for( int i = 0; i < fmd.numParameters(); ++i ) { - TempDescriptor tdParam = fmd.getParameter( i ); - og.newHeapRegion( tdParam ); - } - } - TempDescriptor src; TempDescriptor dst; FieldDescriptor fld; + switch(fn.kind()) { case FKind.FlatMethod: @@ -133,6 +132,7 @@ public class OwnershipAnalysis { case FKind.FlatReturnNode: og.writeGraph( makeNodeName( taskname, flatnodetolabel.get(fn), "Return" ) ); + og.writeCondensedAnalysis( makeCondensedAnalysisName( taskname, flatnodetolabel.get(fn) ) ); break; } @@ -156,4 +156,8 @@ public class OwnershipAnalysis { String s = String.format( "%05d", id ); return "task"+taskname+"_FN"+s+"_"+type; } + + private String makeCondensedAnalysisName( String taskname, Integer id ) { + return "task"+taskname+"_Ownership_from"+id; + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index a60d5340..1142b59e 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -13,6 +13,9 @@ public class OwnershipGraph { protected int labelNodeIDs; protected Hashtable td2ln; + + protected Vector analysisRegionLabels; + protected Hashtable linkedRegions; public OwnershipGraph() { heapRegionNodeIDs = 0; @@ -20,6 +23,9 @@ public class OwnershipGraph { labelNodeIDs = 0; td2ln = new Hashtable(); + + analysisRegionLabels = new Vector(); + linkedRegions = new Hashtable(); } public void assignTempToTemp( TempDescriptor src, @@ -57,6 +63,10 @@ public class OwnershipGraph { heapRoots.add( hrn ); } + public void addAnalysisRegion( TempDescriptor td ) { + analysisRegionLabels.add( td ); + } + protected OwnershipHeapRegionNode allocate( TypeDescriptor typeDesc ) { OwnershipHeapRegionNode hrn = new OwnershipHeapRegionNode( heapRegionNodeIDs ); @@ -86,14 +96,6 @@ public class OwnershipGraph { } /* - public void addEdge( TempDescriptor tu, TempDescriptor tv ) { - OwnershipLabelNode nu = getOwnershipFromTemp( tu ); - OwnershipLabelNode nv = getOwnershipFromTemp( tv ); - - nu.addOutEdge( nv ); - nv.addInEdge( nu ); - } - public OwnershipGraph copy() { OwnershipGraph newog = new OwnershipGraph(); @@ -120,10 +122,9 @@ public class OwnershipGraph { } return newog; - } + } */ - - + public void writeGraph( String graphName ) throws java.io.IOException { BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) ); bw.write( "digraph "+graphName+" {\n" ); @@ -160,4 +161,67 @@ public class OwnershipGraph { visitHeapNodes( bw, childhrn ); } } + + public void writeCondensedAnalysis( String graphName ) throws java.io.IOException { + BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) ); + bw.write( "graph "+graphName+" {\n" ); + + // find linked regions + for( int i = 0; i < analysisRegionLabels.size(); ++i ) { + TempDescriptor td = analysisRegionLabels.get( i ); + bw.write( " "+td.getSymbol()+";\n" ); + + OwnershipLabelNode oln = getLabelNodeFromTemp( td ); + OwnershipHeapRegionNode hrn = oln.getOwnershipHeapRegionNode(); + condensedVisitHeapNodes( bw, hrn, td ); + } + + // write out linked regions + Set s = linkedRegions.entrySet(); + Iterator lri = s.iterator(); + while( lri.hasNext() ) { + Map.Entry me = (Map.Entry) lri.next(); + TempDescriptor t1 = (TempDescriptor) me.getKey(); + TempDescriptor t2 = (TempDescriptor) me.getValue(); + bw.write( " "+t1.getSymbol()+" -- "+t2.getSymbol()+";\n" ); + } + + bw.write( "}\n" ); + 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 ); + } + + TempDescriptor tdnAlias = null; + if( linkedRegions.containsKey( tdn ) ) { + tdnAlias = linkedRegions.get( tdn ); + } + + if( tdn != tdAlias && td != tdnAlias ) { + linkedRegions.put( td, tdn ); + } + } + + condensedVisitHeapNodes( bw, childhrn, td ); + } + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java index 79ef7828..ef8bb7dd 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipHeapRegionNode.java @@ -8,10 +8,12 @@ public class OwnershipHeapRegionNode { protected int id; protected Hashtable fields; + protected Vector analysisRegionAliases; public OwnershipHeapRegionNode( int id ) { this.id = id; fields = new Hashtable(); + analysisRegionAliases = new Vector(); } public void setField( FieldDescriptor fd, @@ -35,4 +37,12 @@ public class OwnershipHeapRegionNode { public String toString() { return "OHRN"+getIDString(); } -} \ No newline at end of file + + public void addAnalysisRegionAlias( TempDescriptor td ) { + analysisRegionAliases.add( td ); + } + + public Vector getAnalysisRegionAliases() { + return analysisRegionAliases; + } +} diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile index 40a71515..26548ad3 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/makefile @@ -8,11 +8,12 @@ BUILDSCRIPT=~/research/Robust/src/buildscript all: view view: PNGs - eog *flatIRGraph*.png & - eog *FN*.png & + eog task*_flatIRGraph*.png & + eog task*_FN*.png & + eog task*_Ownership*.png & PNGs: DOTs - rm -f graph*.dot + rm -f *Startup*.dot d2p *.dot DOTs: $(PROGRAM).bin diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 1eff12be..92ef1a35 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -14,16 +14,28 @@ public class P2 { Thing n; } +public class P3 { + public P2(){} + flag b; + int y; + Thing n; +} + task Startup( StartupObject s{ initialstate } ) { - P1 p1 = new P1(){}; - P2 p2 = new P2(){}; + P1 p1f = new P1(){!a}; + P2 p2f = new P2(){!b}; + P1 p1t = new P1(){ a}; + P2 p2t = new P2(){ b}; taskexit( s{ !initialstate } ); } - -task A( P1 p1{!a}, P2 p2{!b} ) +task A( P1 p1f{!a}, + P2 p2f{!b} ) { - p1.m = p2.n; + p1f.m = p2f.n; + + //p2t.n = p2f.n; - taskexit( p1{a}, p2{b} ); + taskexit( p1f{ a}, + p2f{ b} ); } \ No newline at end of file -- 2.34.1