From f7c64d166f69db2ad9ccdfd1e843c128e543e6e3 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 27 Mar 2008 21:31:29 +0000 Subject: [PATCH] Stable capture. Method call resolution algorithm is drafted, but clearly there are bugs because a simple program with an alias-creating method doesn't reflect the correct heap structure in the caller graph. --- .../OwnershipAnalysis/OwnershipGraph.java | 138 +++++++++++------- .../ReferenceEdgeProperties.java | 5 + .../OwnershipAnalysisTest/test01/test01.java | 20 +++ 3 files changed, 109 insertions(+), 54 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 5753eb53..1bc279c7 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -524,67 +524,97 @@ public class OwnershipGraph { // So now make a set of possible source heaps in the caller graph // and a set of destination heaps in the caller graph, and make // a reference edge in the caller for every possible (src,dst) pair - HashSet possibleCallerSrcs = new HashSet(); - HashSet possibleCallerDsts = new HashSet(); - - // first figure out the set of possible sources in the caller - if( ogCallee.id2paramIndex.containsKey( idCallee ) ) { - // the heap region that is the source of this - // reference edge won't have a matching ID in the - // caller graph because it is specifically allocated - // for a particular parameter. Use that information - // to find the corresponding argument label in the - // caller in order to create the proper reference edge - // or edges. - assert !id2hrn.containsKey( idCallee ); - - Integer paramIndex = ogCallee.id2paramIndex.get( idCallee ); - TempDescriptor argTemp; - - // now depending on whether the callee is static or not - // we need to account for a "this" argument in order to - // find the matching argument in the caller context - if( isStatic ) { - argTemp = fc.getArg( paramIndex ); - } else { - if( paramIndex == 0 ) { - argTemp = fc.getThis(); - } else { - argTemp = fc.getArg( paramIndex - 1 ); - } + HashSet possibleCallerSrcs = + getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, + idCallee, + fc, + isStatic ); + + HashSet possibleCallerDsts = + getHRNSetThatPossiblyMapToCalleeHRN( ogCallee, + idChildCallee, + fc, + isStatic ); + + // make every possible pair of {srcSet} -> {dstSet} edges in the caller + Iterator srcItr = possibleCallerSrcs.iterator(); + while( srcItr.hasNext() ) { + HeapRegionNode src = (HeapRegionNode) srcItr.next(); + + Iterator dstItr = possibleCallerDsts.iterator(); + while( dstItr.hasNext() ) { + HeapRegionNode dst = (HeapRegionNode) dstItr.next(); + + ReferenceEdgeProperties rep = new ReferenceEdgeProperties(); + addReferenceEdge( src, dst, rep ); } - - LabelNode argLabel = getLabelNodeFromTemp( argTemp ); - Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions(); - while( argHeapRegionsItr.hasNext() ) { - Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next(); - HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey(); - ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue(); - - possibleCallerSrcs.add( (HeapRegionNode) argHeapRegion ); - } - - } else { - // this heap region is not a parameter, so it should - // have a matching heap region in the caller graph - - /* - try { - ogCallee.writeGraph( "TheCallee" ); - writeGraph( "TheCaller" ); - } catch( Exception e ) {} - */ - - assert id2hrn.containsKey( idCallee ); - possibleCallerSrcs.add( id2hrn.get( idCallee ) ); } - - // second find the set of possible destinations in the caller } } } } + private HashSet getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee, + Integer idCallee, + FlatCall fc, + boolean isStatic ) { + + HashSet possibleCallerHRNs = new HashSet(); + + if( ogCallee.id2paramIndex.containsKey( idCallee ) ) { + // the heap region that is part of this + // reference edge won't have a matching ID in the + // caller graph because it is specifically allocated + // for a particular parameter. Use that information + // to find the corresponding argument label in the + // caller in order to create the proper reference edge + // or edges. + assert !id2hrn.containsKey( idCallee ); + + Integer paramIndex = ogCallee.id2paramIndex.get( idCallee ); + TempDescriptor argTemp; + + // now depending on whether the callee is static or not + // we need to account for a "this" argument in order to + // find the matching argument in the caller context + if( isStatic ) { + argTemp = fc.getArg( paramIndex ); + } else { + if( paramIndex == 0 ) { + argTemp = fc.getThis(); + } else { + argTemp = fc.getArg( paramIndex - 1 ); + } + } + + LabelNode argLabel = getLabelNodeFromTemp( argTemp ); + Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions(); + while( argHeapRegionsItr.hasNext() ) { + Map.Entry meArg = (Map.Entry) argHeapRegionsItr.next(); + HeapRegionNode argHeapRegion = (HeapRegionNode) meArg.getKey(); + ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue(); + + possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion ); + } + + } else { + // this heap region is not a parameter, so it should + // have a matching heap region in the caller graph + + /* + try { + ogCallee.writeGraph( "TheCallee" ); + writeGraph( "TheCaller" ); + } catch( Exception e ) {} + */ + + assert id2hrn.containsKey( idCallee ); + possibleCallerHRNs.add( id2hrn.get( idCallee ) ); + } + + return possibleCallerHRNs; + } + //////////////////////////////////////////////////// diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java index bc62ed84..eee52986 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java @@ -2,6 +2,11 @@ package Analysis.OwnershipAnalysis; public class ReferenceEdgeProperties { + public ReferenceEdgeProperties() { + this.isUnique = false; + this.isInitialParamReflexive = false; + } + public ReferenceEdgeProperties( boolean isUnique ) { this.isUnique = isUnique; this.isInitialParamReflexive = false; diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index 541f8dba..483c3e31 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -20,6 +20,7 @@ public class Penguin { } */ +/* public class Voo { flag f; int x; Baw b; @@ -33,13 +34,30 @@ public class Baw { public void doTheBaw( Voo v ) { v = new Voo(); } } +*/ + +public class Foo { + public Foo() {} + public Foo x; + + public void ruinSomeFoos( Foo a, Foo b ) { + a.x = b.x; + } +} // this empty task should still create a non-empty // ownership graph showing parameter allocation // look for the parameter s as a label referencing // a heap region that is multi-object, flagged, not summary task Startup( StartupObject s{ initialstate } ) { + + Foo a = new Foo(); + Foo b = new Foo(); + Foo c = new Foo(); + + c.ruinSomeFoos( a, b ); + taskexit( s{ !initialstate } ); } @@ -47,6 +65,7 @@ task Startup( StartupObject s{ initialstate } ) { // be a heap region for the parameter, and several // heap regions for the allocation site, but the label // merely points to the newest region +/* task NewObject( Voo v{ f } ) { Voo w = new Voo(); Baw b = new Baw(); @@ -80,3 +99,4 @@ task NewInLoop( Voo v{ f } ) { taskexit( v{ !f } ); } +*/ -- 2.34.1