From c509fc389c34307e6100207db5b4819a39e662cd Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 26 Mar 2008 21:55:55 +0000 Subject: [PATCH] Stable capture of work on method call resolution, specifically the guts of it in OwnershipGraph.java. Added a new attribute to the ReferenceEdgeProperties class indicating an initial reflexive param edge. --- .../OwnershipAnalysis/OwnershipAnalysis.java | 6 +- .../OwnershipAnalysis/OwnershipGraph.java | 158 ++++++++++++++---- .../ReferenceEdgeProperties.java | 37 ++-- .../test01/MAKESURETOTESTTHIS | 3 + 4 files changed, 159 insertions(+), 45 deletions(-) create mode 100644 Robust/src/Tests/OwnershipAnalysisTest/test01/MAKESURETOTESTTHIS diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index aa53286d..48664522 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -253,11 +253,13 @@ public class OwnershipAnalysis { for( int i = 0; i < fm.numParameters(); ++i ) { TempDescriptor tdParam = fm.getParameter( i ); og.assignTempToParameterAllocation( methodDesc instanceof TaskDescriptor, - tdParam ); + tdParam, + new Integer( i ) ); //og.writeGraph( methodDesc, fn ); } + break; - + case FKind.FlatOpNode: FlatOpNode fon = (FlatOpNode) fn; if( fon.getOp().getOp() == Operation.ASSIGN ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index f84c9c66..5753eb53 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -19,13 +19,15 @@ public class OwnershipGraph { public Hashtable id2hrn; public Hashtable td2ln; + public Hashtable id2paramIndex; public OwnershipGraph( int allocationDepth ) { this.allocationDepth = allocationDepth; - id2hrn = new Hashtable(); - td2ln = new Hashtable(); + id2hrn = new Hashtable(); + td2ln = new Hashtable(); + id2paramIndex = new Hashtable(); } @@ -215,8 +217,9 @@ public class OwnershipGraph { } } - public void assignTempToParameterAllocation( boolean isTask, - TempDescriptor td ) { + public void assignTempToParameterAllocation( boolean isTask, + TempDescriptor td, + Integer paramIndex ) { assert td != null; LabelNode lnParam = getLabelNodeFromTemp( td ); @@ -226,8 +229,20 @@ public class OwnershipGraph { false, "param" ); + // keep track of heap regions that were created for + // parameter labels, the index of the parameter they + // are for is important when resolving method calls + Integer newID = hrn.getID(); + assert !id2paramIndex.containsKey ( newID ); + assert !id2paramIndex.containsValue( paramIndex ); + id2paramIndex.put( newID, paramIndex ); + + // heap regions for parameters are always multiple object (see above) + // and have a reference to themselves, because we can't know the + // structure of memory that is passed into the method. We're assuming + // the worst here. addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) ); - addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false ) ); + addReferenceEdge( hrn, hrn, new ReferenceEdgeProperties( false, true ) ); } public void assignTempToNewAllocation( TempDescriptor td, @@ -459,6 +474,14 @@ public class OwnershipGraph { this.age( (AllocationSite) i.next() ); } + // in non-static methods there is a "this" pointer + // that should be taken into account + if( isStatic ) { + assert fc.numArgs() == fm.numParameters(); + } else { + assert fc.numArgs() + 1 == fm.numParameters(); + } + // the heap regions represented by the arguments (caller graph) // and heap regions for the parameters (callee graph) // don't correspond to each other by heap region ID. In fact, @@ -466,21 +489,7 @@ public class OwnershipGraph { // so the parameter label always references a multiple-object // heap region in order to handle the range of possible contexts // for a method call. This means we need to make a special mapping - // of argument->parameter regions in order to update the caller graph, - // then remember which heap regions were used so we can ignore them - // in the more general algorithm below that includes all heap regions - // of the callee graph - HashSet calleeParameterIDs = new HashSet(); - - if( isStatic ) { - assert fc.numArgs() == fm.numParameters(); - } else { - assert fc.numArgs() + 1 == fm.numParameters(); - } - - for( int a = 0; a < fc.numArgs(); ++a ) { - - } + // of argument->parameter regions in order to update the caller graph // for every heap region->heap region edge in the // callee graph, create the matching edge or edges @@ -500,16 +509,78 @@ public class OwnershipGraph { ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue(); Integer idChildCallee = hrnChildCallee.getID(); - - // now we know that in the callee method's ownership graph - // there is a heap region->heap region reference edge given - // by the ownership-graph independent ID's: - // idCallee->idChildCallee - // + // only address this edge if it is not a special reflexive edge + if( !repC.isInitialParamReflexive() ) { + + // now we know that in the callee method's ownership graph + // there is a heap region->heap region reference edge given + // by heap region pointers: + // hrnCallee -> heapChildCallee + // + // or by the ownership-graph independent ID's: + // idCallee -> idChildCallee + // + // 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 ); + } + } + + 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 ) ); + } - // at this point we know an edge in graph A exists - // idA -> idChildA, does this exist in B? + // second find the set of possible destinations in the caller + } } } } @@ -528,8 +599,9 @@ public class OwnershipGraph { return; } - mergeOwnershipNodes ( og ); - mergeReferenceEdges ( og ); + mergeOwnershipNodes( og ); + mergeReferenceEdges( og ); + mergeId2paramIndex( og ); } protected void mergeOwnershipNodes( OwnershipGraph og ) { @@ -675,6 +747,22 @@ public class OwnershipGraph { } } + // you should only merge ownership graphs that have the + // same number of parameters, or if one or both parameter + // index tables are empty + protected void mergeId2paramIndex( OwnershipGraph og ) { + if( id2paramIndex.size() == 0 ) { + id2paramIndex = og.id2paramIndex; + return; + } + + if( og.id2paramIndex.size() == 0 ) { + return; + } + + assert id2paramIndex.size() == og.id2paramIndex.size(); + } + // it is necessary in the equals() member functions // to "check both ways" when comparing the data @@ -708,6 +796,10 @@ public class OwnershipGraph { return false; } + if( !areId2paramIndexEqual( og ) ) { + return false; + } + return true; } @@ -957,6 +1049,12 @@ public class OwnershipGraph { } + protected boolean areId2paramIndexEqual( OwnershipGraph og ) { + return id2paramIndex.size() == og.id2paramIndex.size(); + } + + + /* // use this method to determine if two temp descriptors can possibly // access the same heap regions, which means there is a possible alias diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java index 9541d0d3..bc62ed84 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdgeProperties.java @@ -3,32 +3,43 @@ package Analysis.OwnershipAnalysis; public class ReferenceEdgeProperties { public ReferenceEdgeProperties( boolean isUnique ) { - this.isUnique = isUnique; + this.isUnique = isUnique; + this.isInitialParamReflexive = false; + } + + public ReferenceEdgeProperties( boolean isUnique, + boolean isInitialParamReflexive ) { + this.isUnique = isUnique; + this.isInitialParamReflexive = isInitialParamReflexive; } + public ReferenceEdgeProperties copy() { - return new ReferenceEdgeProperties( isUnique ); + return new ReferenceEdgeProperties( isUnique, + isInitialParamReflexive ); } - ///////////////// - // equality - ///////////////// protected boolean isUnique; - public boolean isUnique() { return isUnique; } + public void setIsUnique( boolean isUnique ) { + this.isUnique = isUnique; + } - public boolean equals( ReferenceEdgeProperties rep ) { - return isUnique == rep.isUnique(); + + protected boolean isInitialParamReflexive; + public boolean isInitialParamReflexive() { + return isInitialParamReflexive; + } + public void setIsInitialParamReflexive( boolean isInitialParamReflexive ) { + this.isInitialParamReflexive = isInitialParamReflexive; } - ///////////////// - // end equality - ///////////////// - public void setIsUnique( boolean isUnique ) { - this.isUnique = isUnique; + public boolean equals( ReferenceEdgeProperties rep ) { + return isUnique == rep.isUnique() && + isInitialParamReflexive == rep.isInitialParamReflexive(); } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/MAKESURETOTESTTHIS b/Robust/src/Tests/OwnershipAnalysisTest/test01/MAKESURETOTESTTHIS new file mode 100644 index 00000000..2fb91b11 --- /dev/null +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/MAKESURETOTESTTHIS @@ -0,0 +1,3 @@ +Make sure to test that an initial parameter has a special reflexive edge, but if you +actually remake that edge during the method analysis, it becomes a regular edge and +then will get picked up by the method call resolution! -- 2.34.1