From 0f8fae95905ca691e13b065d163982184ffd160f Mon Sep 17 00:00:00 2001 From: jjenista Date: Fri, 29 Aug 2008 21:54:02 +0000 Subject: [PATCH] added support for array element nodes --- .../OwnershipAnalysis/OwnershipAnalysis.java | 28 +++++++- .../OwnershipAnalysis/OwnershipGraph.java | 69 ++++++++++++------- .../OwnershipAnalysis/ReferenceEdge.java | 6 +- .../OwnershipAnalysisTest/test01/test01.java | 16 +++++ .../OwnershipAnalysisTest/test03/test03.java | 53 +++++++------- 5 files changed, 120 insertions(+), 52 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 630ca3d3..f669dc4a 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -3,6 +3,7 @@ package Analysis.OwnershipAnalysis; import Analysis.CallGraph.*; import IR.*; import IR.Flat.*; +import IR.Tree.Modifiers; import java.util.*; import java.io.*; @@ -196,6 +197,12 @@ public class OwnershipAnalysis { // should be re-added to this set private HashSet descriptorsToVisit; + // a special field descriptor for all array elements + private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), + new TypeDescriptor( "Array[]" ), + "elements", + null, + false); // this analysis generates an ownership graph for every task @@ -487,6 +494,24 @@ public class OwnershipAnalysis { rhs = fsfn.getSrc(); og.assignTempXFieldFEqualToTempY(lhs, fld, rhs); break; + + case FKind.FlatElementNode: + FlatElementNode fen = (FlatElementNode) fn; + lhs = fen.getDst(); + rhs = fen.getSrc(); + if( !lhs.getType().isPrimitive() ) { + og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement); + } + break; + + case FKind.FlatSetElementNode: + FlatSetElementNode fsen = (FlatSetElementNode) fn; + lhs = fsen.getDst(); + rhs = fsen.getSrc(); + if( !rhs.getType().isPrimitive() ) { + og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs); + } + break; case FKind.FlatNew: FlatNew fnn = (FlatNew) fn; @@ -576,9 +601,6 @@ public class OwnershipAnalysis { - - - // return just the allocation site associated with one FlatNew node private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index fd018948..ff8e20c9 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -16,6 +16,8 @@ public class OwnershipGraph { // actions to take during the traversal protected static final int VISIT_HRN_WRITE_FULL = 0; + protected static TempDescriptor tdReturn = new TempDescriptor("_Return___"); + public Hashtable id2hrn; public Hashtable td2ln; @@ -26,7 +28,6 @@ public class OwnershipGraph { public HashSet allocationSites; - protected static TempDescriptor tdReturn = new TempDescriptor("_Return___"); public OwnershipGraph(int allocationDepth) { @@ -364,7 +365,6 @@ public class OwnershipGraph { public void assignTempXEqualToTempYFieldF(TempDescriptor x, TempDescriptor y, FieldDescriptor f) { - LabelNode lnX = getLabelNodeFromTemp(x); LabelNode lnY = getLabelNodeFromTemp(y); @@ -401,7 +401,6 @@ public class OwnershipGraph { public void assignTempXFieldFEqualToTempY(TempDescriptor x, FieldDescriptor f, TempDescriptor y) { - LabelNode lnX = getLabelNodeFromTemp(x); LabelNode lnY = getLabelNodeFromTemp(y); @@ -1329,37 +1328,56 @@ public class OwnershipGraph { // return value may need to be assigned in caller if( fc.getReturnTemp() != null ) { - HashSet assignCallerRhs = new HashSet(); + LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() ); + clearReferenceEdgesFrom(lnLhsCaller, null, true); LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn); Iterator edgeCalleeItr = lnReturnCallee.iteratorToReferencees(); while( edgeCalleeItr.hasNext() ) { ReferenceEdge edgeCallee = edgeCalleeItr.next(); - HashSet possibleCallerHRNs = + ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null, + null, + edgeCallee.getFieldDesc(), + false, + toShadowTokens(ogCallee, edgeCallee.getBeta() ) + ); + rewriteCallerEdgeBeta(fm.numParameters(), + bogusIndex, + edgeNewInCallerTemplate, + paramIndex2rewriteJ, + paramIndex2rewriteD, + paramIndex2paramToken, + paramIndex2paramTokenStar, + false, + null); + + edgeNewInCallerTemplate.applyBetaNew(); + + + HashSet assignCallerRhs = getHRNSetThatPossiblyMapToCalleeHRN(ogCallee, edgeCallee.getDst(), false, paramIndex2reachableCallerNodes); - assignCallerRhs.addAll(possibleCallerHRNs); - } - - LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() ); - clearReferenceEdgesFrom(lnLhsCaller, null, true); - - Iterator itrHrn = assignCallerRhs.iterator(); - while( itrHrn.hasNext() ) { - HeapRegionNode hrnCaller = itrHrn.next(); - - ReferenceEdge edgeNew = new ReferenceEdge(lnLhsCaller, - hrnCaller, - null, - false, - new ReachabilitySet().makeCanonical() - ); - - addReferenceEdge(lnLhsCaller, hrnCaller, edgeNew); + Iterator itrHrn = assignCallerRhs.iterator(); + while( itrHrn.hasNext() ) { + HeapRegionNode hrnCaller = itrHrn.next(); + + ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy(); + edgeNewInCaller.setSrc(lnLhsCaller); + edgeNewInCaller.setDst(hrnCaller); + + ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() ); + if( edgeExisting == null ) { + // if this edge doesn't exist in the caller, create it + addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller); + } else { + // if it already exists, merge with it + edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) ); + } + } } } @@ -1384,6 +1402,11 @@ public class OwnershipGraph { mergeIntoSummary(hrnSummaryShadow, hrnSummary); + // then clear off after merge + clearReferenceEdgesFrom(hrnSummaryShadow, null, true); + clearReferenceEdgesTo(hrnSummaryShadow, null, true); + hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() ); + // then transplant shadow nodes onto the now clean normal nodes for( int i = 0; i < as.getAllocationDepth(); ++i ) { diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java index 7e625b15..09c6ae3a 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java @@ -86,7 +86,7 @@ public class ReferenceEdge { int hash = 0; if( fieldDesc != null ) { - hash += fieldDesc.getType().hashCode(); + hash += fieldDesc.hashCode(); } hash += src.hashCode()*11; @@ -173,4 +173,8 @@ public class ReferenceEdge { return edgeLabel; } + + public String toString() { + return new String( "("+src+" "+fieldDesc+" "+dst+")" ); + } } diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java index d7785462..a432b914 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test01/test01.java @@ -339,8 +339,24 @@ task strongUpdates( Foo p0{ f } ) { taskexit( p0{ !f } ); } +*/ + +task arrayAssignments( Foo a{ f } ) { + + Foo f[] = new Foo[3]; + + Foo g = new Foo(); + Foo h = new Foo(); + + f[1] = g; + f[2] = h; + Foo i = f[0]; + taskexit( a{ !f } ); +} + +/* task methodTest( Foo p0{ f } ) { Foo up0 = new Foo(); diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test03/test03.java b/Robust/src/Tests/OwnershipAnalysisTest/test03/test03.java index 99f3c754..b59d683a 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test03/test03.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test03/test03.java @@ -1,46 +1,49 @@ public class Parameter { - flag w; - Node root; - public Parameter() {} + flag w; + Node root; + public Parameter() {} } public class Node { - HashSet neighbors; - - public Node() { - neighbors = new HashSet(); - } - - public static Node makeNode() { - return new Node(); - } - - public addNeighbor( Node n ) { - neighbors.add( n ); - } + HashSet neighbors; + + public Node() { + neighbors = new HashSet(); + } + + public static Node makeNode() { + return new Node(); + } + + public addNeighbor( Node n ) { + neighbors.add( n ); + } } task Startup( StartupObject s{ initialstate } ) { - - Parameter p1 = new Parameter(); - - taskexit( s{ !initialstate } ); + + Parameter p1 = new Parameter(); + + taskexit( s{ !initialstate } ); } task MakeGraph( Parameter p1{ !w } ) { + while( false ) { + Parameter p2 = new Parameter(); + Node n1 = Node.makeNode(); Node n2 = Node.makeNode(); Node n3 = Node.makeNode(); - + n1.addNeighbor( n2 ); n2.addNeighbor( n3 ); n3.addNeighbor( n1 ); + + p2.root = n1; + } - p1.root = n1; - - - taskexit( p1{ w } ); + taskexit( p1{ w } ); } -- 2.34.1