From e84f8aa5de7d48f744e2935081bee8f88f0c186c Mon Sep 17 00:00:00 2001 From: jjenista Date: Sat, 30 Aug 2008 00:30:17 +0000 Subject: [PATCH] alias query for param to alloc site --- .../OwnershipAnalysis/OwnershipAnalysis.java | 25 ++------ .../OwnershipAnalysis/OwnershipGraph.java | 64 +++++++++++++++++++ .../OwnershipAnalysisTest/test02/test02.java | 12 ++++ 3 files changed, 83 insertions(+), 18 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index dedc6ad5..181764b6 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -33,38 +33,28 @@ public class OwnershipAnalysis { OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); assert( og != null ); - return og.hasPotentialAlias( paramIndex1, paramIndex2 ); - /* - return createsPotentialAliases( og, - getHeapRegionIDset( og, paramIndex1 ), - getHeapRegionIDset( og, paramIndex2 ) ); - */ } - /* public boolean createsPotentialAliases( Descriptor taskOrMethod, int paramIndex, AllocationSite alloc ) { OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); assert( og != null ); - return createsPotentialAliases( og, - getHeapRegionIDset( og, paramIndex ), - getHeapRegionIDset( alloc ) ); + return og.hasPotentialAlias( paramIndex, alloc ); } - + public boolean createsPotentialAliases( Descriptor taskOrMethod, AllocationSite alloc, int paramIndex ) { OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); assert( og != null ); - return createsPotentialAliases( og, - getHeapRegionIDset( og, paramIndex ), - getHeapRegionIDset( alloc ) ); + return og.hasPotentialAlias( paramIndex, alloc ); } - + + /* public boolean createsPotentialAliases( Descriptor taskOrMethod, AllocationSite alloc1, AllocationSite alloc2 ) { @@ -99,7 +89,7 @@ public class OwnershipAnalysis { while( taskItr.hasNext() ) { TaskDescriptor td = (TaskDescriptor) taskItr.next(); - //HashSet allocSites = getFlaggedAllocationSitesReachableFromTask( td ); + HashSet allocSites = getFlaggedAllocationSitesReachableFromTask( td ); // for each task parameter, check for aliases with // other task parameters and every allocation site @@ -118,7 +108,6 @@ public class OwnershipAnalysis { } } - /* // for the ith parameter, check for aliases against // the set of allocation sites reachable from this // task context @@ -126,10 +115,10 @@ public class OwnershipAnalysis { while( allocItr.hasNext() ) { AllocationSite as = (AllocationSite) allocItr.next(); if( createsPotentialAliases( td, i, as ) ) { + foundSomeAlias = true; bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" ); } } - */ } /* diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index fee59db0..7e8783a0 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -2263,6 +2263,70 @@ public class OwnershipGraph { } + public boolean hasPotentialAlias( Integer paramIndex, AllocationSite as ) { + + // get parameter's heap region + assert paramIndex2id.containsKey(paramIndex); + Integer idParam = paramIndex2id.get(paramIndex); + + assert id2hrn.containsKey(idParam); + HeapRegionNode hrnParam = id2hrn.get(idParam); + assert hrnParam != null; + + // get tokens for this parameter + TokenTuple p = new TokenTuple(hrnParam.getID(), + true, + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple pStar = new TokenTuple(hrnParam.getID(), + true, + TokenTuple.ARITY_MANY).makeCanonical(); + + // get special label p_q + TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex); + assert tdParamQ != null; + LabelNode lnParamQ = td2ln.get(tdParamQ); + assert lnParamQ != null; + + // then get the edge from label q to parameter's hrn + ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null); + assert edgeSpecialQ != null; + + // look through this beta set for potential aliases + ReachabilitySet beta = edgeSpecialQ.getBeta(); + assert beta != null; + + + // get tokens for summary node + TokenTuple gs = new TokenTuple(as.getSummary(), + true, + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple gsStar = new TokenTuple(as.getSummary(), + true, + TokenTuple.ARITY_MANY).makeCanonical(); + + if( beta.containsTupleSetWithBoth( p, gs ) ) { return true; } + if( beta.containsTupleSetWithBoth( pStar, gs ) ) { return true; } + if( beta.containsTupleSetWithBoth( p, gsStar ) ) { return true; } + if( beta.containsTupleSetWithBoth( pStar, gsStar ) ) { return true; } + + // check for other nodes + for( int i = 0; i < as.getAllocationDepth(); ++i ) { + + // the other nodes of an allocation site are single, no stars + TokenTuple gi = new TokenTuple(as.getIthOldest(i), + false, + TokenTuple.ARITY_ONE).makeCanonical(); + + if( beta.containsTupleSetWithBoth( p, gi ) ) { return true; } + if( beta.containsTupleSetWithBoth( pStar, gi ) ) { return true; } + } + + return false; + } + + /* // given a set B of heap region node ID's, return the set of heap // region node ID's that is reachable from B diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java b/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java index 4ce10637..893927bc 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java @@ -232,3 +232,15 @@ task NoAliasNewInLoopAnotherWay( Voo v{ f } ) { taskexit( v{ !f } ); } + + +task AliasParamToNew( Voo v{ f }, Voo w{ f } ) { + + Baw m = new Baw(); + w.b = m; + + Voo x = new Voo(); + x.b = m; + + taskexit( v{ !f }, w{ !f } ); +} -- 2.34.1