From 4c270df3b0d8257f14c5df80f98fff1c9959817b Mon Sep 17 00:00:00 2001 From: jjenista Date: Sat, 30 Aug 2008 00:03:57 +0000 Subject: [PATCH] step toward repairing top-level alias query interface --- .../OwnershipAnalysis/OwnershipAnalysis.java | 221 +++++------ .../OwnershipAnalysis/OwnershipGraph.java | 94 +++-- .../OwnershipAnalysis/ReachabilitySet.java | 10 + .../OwnershipAnalysisTest/test02/test02.java | 349 +++++++++--------- 4 files changed, 358 insertions(+), 316 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index f669dc4a..dedc6ad5 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -10,83 +10,82 @@ import java.io.*; public class OwnershipAnalysis { + /////////////////////////////////////////// // // Public interface to discover possible // aliases in the program under analysis // /////////////////////////////////////////// - /* - public HashSet - getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) { - - return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td ); - } - public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) { - return getAllocationSiteFromFlatNewPRIVATE( fn ); - } + public HashSet + getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) { + return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td ); + } - public boolean createsPotentialAliases( Descriptor taskOrMethod, - int paramIndex1, - int paramIndex2 ) { + public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) { + return getAllocationSiteFromFlatNewPRIVATE( fn ); + } - OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); - assert( og != null ); + public boolean createsPotentialAliases( Descriptor taskOrMethod, + int paramIndex1, + int paramIndex2 ) { + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); - return createsPotentialAliases( og, - getHeapRegionIDset( og, paramIndex1 ), - getHeapRegionIDset( og, paramIndex2 ) ); - } + return og.hasPotentialAlias( paramIndex1, paramIndex2 ); + /* + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex1 ), + getHeapRegionIDset( og, paramIndex2 ) ); + */ + } - public boolean createsPotentialAliases( Descriptor taskOrMethod, + /* + 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 ) ); - } - - public boolean createsPotentialAliases( Descriptor taskOrMethod, + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex ), + getHeapRegionIDset( 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 ) ); - } - - public boolean createsPotentialAliases( Descriptor taskOrMethod, + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + return createsPotentialAliases( og, + getHeapRegionIDset( og, paramIndex ), + getHeapRegionIDset( alloc ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, AllocationSite alloc1, AllocationSite alloc2 ) { - - OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); - assert( og != null ); - - return createsPotentialAliases( og, - getHeapRegionIDset( alloc1 ), - getHeapRegionIDset( alloc2 ) ); - } - - public boolean createsPotentialAliases( Descriptor taskOrMethod, + + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + return createsPotentialAliases( og, + getHeapRegionIDset( alloc1 ), + getHeapRegionIDset( alloc2 ) ); + } + + public boolean createsPotentialAliases( Descriptor taskOrMethod, AllocationSite alloc, - HashSet allocSet ) { - - OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); - assert( og != null ); - - return createsPotentialAliases( og, - getHeapRegionIDset( alloc ), - getHeapRegionIDset( allocSet ) ); - } - */ + HashSet allocSet ) { + OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod ); + assert( og != null ); + return createsPotentialAliases( og, + getHeapRegionIDset( alloc ), + getHeapRegionIDset( allocSet ) ); + } + */ // use the methods given above to check every possible alias // between task parameters and flagged allocation sites reachable @@ -94,54 +93,64 @@ public class OwnershipAnalysis { public void writeAllAliases(String outputFile) throws java.io.IOException { BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) ); - /* - // look through every task for potential aliases - Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); - while( taskItr.hasNext() ) { - TaskDescriptor td = (TaskDescriptor) taskItr.next(); - - HashSet allocSites = getFlaggedAllocationSitesReachableFromTask( td ); - - // for each task parameter, check for aliases with - // other task parameters and every allocation site - // reachable from this task - FlatMethod fm = state.getMethodFlat( td ); - for( int i = 0; i < fm.numParameters(); ++i ) { - - // for the ith parameter check for aliases to all - // higher numbered parameters - for( int j = i + 1; j < fm.numParameters(); ++j ) { - if( createsPotentialAliases( td, i, j ) ) { - bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" ); - } - } - - // for the ith parameter, check for aliases against - // the set of allocation sites reachable from this - // task context - Iterator allocItr = allocSites.iterator(); - while( allocItr.hasNext() ) { - AllocationSite as = (AllocationSite) allocItr.next(); - if( createsPotentialAliases( td, i, as ) ) { - bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" ); - } - } - } - // for each allocation site check for aliases with - // other allocation sites in the context of execution - // of this task - Iterator allocItr = allocSites.iterator(); - while( allocItr.hasNext() ) { - AllocationSite as = (AllocationSite) allocItr.next(); - if( createsPotentialAliases( td, as, allocSites ) ) { - bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" ); - } - } - } + // look through every task for potential aliases + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while( taskItr.hasNext() ) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + + //HashSet allocSites = getFlaggedAllocationSitesReachableFromTask( td ); + + // for each task parameter, check for aliases with + // other task parameters and every allocation site + // reachable from this task + boolean foundSomeAlias = false; + + FlatMethod fm = state.getMethodFlat( td ); + for( int i = 0; i < fm.numParameters(); ++i ) { - bw.close(); - */ + // for the ith parameter check for aliases to all + // higher numbered parameters + for( int j = i + 1; j < fm.numParameters(); ++j ) { + if( createsPotentialAliases( td, i, j ) ) { + foundSomeAlias = true; + bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" ); + } + } + + /* + // for the ith parameter, check for aliases against + // the set of allocation sites reachable from this + // task context + Iterator allocItr = allocSites.iterator(); + while( allocItr.hasNext() ) { + AllocationSite as = (AllocationSite) allocItr.next(); + if( createsPotentialAliases( td, i, as ) ) { + bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" ); + } + } + */ + } + + /* + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + Iterator allocItr = allocSites.iterator(); + while( allocItr.hasNext() ) { + AllocationSite as = (AllocationSite) allocItr.next(); + if( createsPotentialAliases( td, as, allocSites ) ) { + bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" ); + } + } + */ + + if( !foundSomeAlias ) { + bw.write( "Task "+td+" contains no aliases between flagged objects.\n" ); + } + } + + bw.close(); } /////////////////////////////////////////// @@ -263,6 +272,8 @@ public class OwnershipAnalysis { // as mentioned above, analyze methods one-by-one, possibly revisiting // a method if the methods that it calls are updated analyzeMethods(); + + writeAllAliases( "identifiedAliases.txt" ); } // called from the constructor to help initialize the set diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 72cc326b..fee59db0 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -2202,6 +2202,67 @@ public class OwnershipGraph { } + public boolean hasPotentialAlias( Integer paramIndex1, Integer paramIndex2 ) { + + // get parameter's heap region + assert paramIndex2id.containsKey(paramIndex1); + Integer idParam1 = paramIndex2id.get(paramIndex1); + + assert id2hrn.containsKey(idParam1); + HeapRegionNode hrnParam1 = id2hrn.get(idParam1); + assert hrnParam1 != null; + + // get tokens for this parameter + TokenTuple p1 = new TokenTuple(hrnParam1.getID(), + true, + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(), + true, + TokenTuple.ARITY_MANY).makeCanonical(); + + + // get tokens for the other parameter + assert paramIndex2id.containsKey(paramIndex2); + Integer idParam2 = paramIndex2id.get(paramIndex2); + + assert id2hrn.containsKey(idParam2); + HeapRegionNode hrnParam2 = id2hrn.get(idParam2); + assert hrnParam2 != null; + + TokenTuple p2 = new TokenTuple(hrnParam2.getID(), + true, + TokenTuple.ARITY_ONE).makeCanonical(); + + TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(), + true, + TokenTuple.ARITY_MANY).makeCanonical(); + + + // get special label p_q for first parameter + TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1); + assert tdParamQ1 != null; + LabelNode lnParamQ1 = td2ln.get(tdParamQ1); + assert lnParamQ1 != null; + + // then get the edge from label q to parameter's hrn + ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null); + assert edgeSpecialQ1 != null; + + // if the beta of this edge has tokens from both parameters in one + // token tuple set, then there is a potential alias between them + ReachabilitySet beta1 = edgeSpecialQ1.getBeta(); + assert beta1 != null; + + if( beta1.containsTupleSetWithBoth( p1, p2 ) ) { return true; } + if( beta1.containsTupleSetWithBoth( pStar1, p2 ) ) { return true; } + if( beta1.containsTupleSetWithBoth( p1, pStar2 ) ) { return true; } + if( beta1.containsTupleSetWithBoth( pStar1, pStar2 ) ) { 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 @@ -2322,39 +2383,6 @@ public class OwnershipGraph { ); } - /* - public void writeGraph(Descriptor methodDesc, - FlatNode fn, - boolean writeLabels, - boolean writeReferencers - ) throws java.io.IOException { - writeGraph( - methodDesc.getSymbol() + - methodDesc.getNum() + - fn.toString(), - writeLabels, - false, - false, - writeReferencers - ); - } - - public void writeGraph(Descriptor methodDesc, - boolean writeLabels, - boolean writeReferencers - ) throws java.io.IOException { - writeGraph( - methodDesc.getSymbol() + - methodDesc.getNum() + - "COMPLETE", - writeLabels, - false, - false, - writeReferencers - ); - } - */ - public void writeGraph(Descriptor methodDesc, boolean writeLabels, boolean labelSelect, diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java index 4409a99b..64e1cc40 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java @@ -63,6 +63,16 @@ public class ReachabilitySet extends Canonical { return false; } + public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) { + Iterator itr = iterator(); + while( itr.hasNext() ) { + TokenTupleSet tts = (TokenTupleSet) itr.next(); + if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) { + return true; + } + } + return false; + } public ReachabilitySet increaseArity(Integer token) { assert token != null; diff --git a/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java b/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java index 7aad47c1..4ce10637 100644 --- a/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java +++ b/Robust/src/Tests/OwnershipAnalysisTest/test02/test02.java @@ -1,241 +1,234 @@ public class Parameter { - flag w; - int a, b; - Parameter f, g; - Penguin penguin; - - public Parameter() { a = 0; b = 0; f = null; g = null; } - - public void bar() { foo(); } - public void foo() { bar(); } + flag w; + int a; + int b; + Parameter f; + Parameter g; + Penguin penguin; + public Parameter() { a = 0; b = 0; f = null; g = null; } + public void bar() { foo(); } + public void foo() { bar(); } } public class Penguin { - int x, y; - - public Penguin() { x = 0; y = 0; } - - public void bar() { x = 1; } + int x; + int y; + public Penguin() { x = 0; y = 0; } + public void bar() { x = 1; } } public class Voo { - flag f; int x; Baw b; Baw bb; - - public Voo() {} + flag f; int x; Baw b; Baw bb; + public Voo() {} } public class Baw { - int y; - Foo f; - - public Baw() {} - - public void doTheBaw( Voo v ) { v = new Voo(); } + int y; + Foo f; + public Baw() {} + public void doTheBaw( Voo v ) { v = new Voo(); } } public class Foo { - flag f; - - public Foo() {} - - public Foo x; - public Foo y; - public Foo z; - - public void ruinSomeFoos( Foo a, Foo b ) { - a.x = b.x; - } - - static public void aStaticMethod( Foo p0, Foo p1 ) { - Foo f0 = new Foo(); - Foo f1 = new Foo(); - Foo f2 = new Foo(); - - f0.x = f1; - p0.x = f0; - p1.x = f1; - p1.x = f2; - } + flag f; + public Foo() {} + public Foo x; + public Foo y; + public Foo z; + + public void ruinSomeFoos( Foo a, Foo b ) { + a.x = b.x; + } + + static public void aStaticMethod( Foo p0, Foo p1 ) { + Foo f0 = new Foo(); + Foo f1 = new Foo(); + Foo f2 = new Foo(); + f0.x = f1; + p0.x = f0; + p1.x = f1; + p1.x = f2; + } } task Startup( StartupObject s{ initialstate } ) { - - /* + + /* Parameter p = new Parameter(){!w}; p.foo(); - + Penguin g = new Penguin(); g.bar(); - */ - - Parameter p; - - for( int i = 0; i < 3; ++i ) { - p = new Parameter(); - p.penguin = new Penguin(); - p.penguin.bar(); - } - - p = null; - - taskexit( s{ !initialstate } ); + */ + + Parameter p; + + for( int i = 0; i < 3; ++i ) { + p = new Parameter(); + p.penguin = new Penguin(); + p.penguin.bar(); + } + + p = null; + + taskexit( s{ !initialstate } ); } task aliasFromObjectAssignment - ( Parameter p1{!w}, Parameter p2{!w} ) { - - p1.f = p2.g; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + p1.f = p2.g; + + taskexit( p1{w}, p2{w} ); } task noAliasFromPrimitiveAssignment - ( Parameter p1{!w}, Parameter p2{!w} ) { - - p1.a = p2.b; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + p1.a = p2.b; + + taskexit( p1{w}, p2{w} ); } task aliasWithTwoLinks - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter j = p1.f; - p2.f = j; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter j = p1.f; + p2.f = j; + + taskexit( p1{w}, p2{w} ); } task aliasWithThreeLinks - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter j = p1.f; - Parameter k = j; - p2.f = k; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter j = p1.f; + Parameter k = j; + p2.f = k; + + taskexit( p1{w}, p2{w} ); } task noAliasBreakLinks - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter j = p1.f; - Parameter k = j; - k = p2.f; - p2.f = k; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter j = p1.f; + Parameter k = j; + k = p2.f; + p2.f = k; + + taskexit( p1{w}, p2{w} ); } task possibleAliasConditional - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter y; - - if( p1.a == 0 ) { - y = p1.f; - } else { - y = p2.f; - } - - p2.g = y; - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter y; + + if( p1.a == 0 ) { + y = p1.f; + } else { + y = p2.f; + } + + p2.g = y; + + taskexit( p1{w}, p2{w} ); } task bunchOfPaths - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter y; - - for( int i =0; i < 100; ++i ) { - - if( y == p1 ) { - Parameter z; - - for( int j = 0; i < 50; ++j ) { - if( z == y ) { - p1.f = y; - } else { - z = p2.g; - } - - p1.f = z; - } - - y = p1.g; + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter y; + + for( int i =0; i < 100; ++i ) { + + if( y == p1 ) { + Parameter z; + + for( int j = 0; i < 50; ++j ) { + if( z == y ) { + p1.f = y; } else { - - p2.f = y; + z = p2.g; } + + p1.f = z; + } + + y = p1.g; + } else { + + p2.f = y; } - - p1.f = p2.g; - - - taskexit( p1{w}, p2{w} ); + } + + p1.f = p2.g; + + + taskexit( p1{w}, p2{w} ); } task literalTest( Parameter p1{!w} ) { - Parameter x = null; - int y = 5; - String s = "Dude"; - - taskexit( p1{w} ); + Parameter x = null; + int y = 5; + String s = "Dude"; + + taskexit( p1{w} ); } task newNoAlias - ( Parameter p1{!w}, Parameter p2{!w} ) { - - for( int i = 0; i < 1; ++i ) { - p1.f = new Parameter(); - } - - taskexit( p1{w}, p2{w} ); + ( Parameter p1{!w}, Parameter p2{!w} ) { + + for( int i = 0; i < 1; ++i ) { + p1.f = new Parameter(); + } + + taskexit( p1{w}, p2{w} ); } task newPossibleAlias - ( Parameter p1{!w}, Parameter p2{!w} ) { - - Parameter x, y; - - for( int i = 0; i < 1; ++i ) { - p1.f = new Parameter(); - if( true ) { - x = p1.f; - } else { - y = p1.f; - } + ( Parameter p1{!w}, Parameter p2{!w} ) { + + Parameter x, y; + + for( int i = 0; i < 1; ++i ) { + p1.f = new Parameter(); + if( true ) { + x = p1.f; + } else { + y = p1.f; } - - p2.f = y; - - taskexit( p1{w}, p2{w} ); + } + + p2.f = y; + + taskexit( p1{w}, p2{w} ); } task NoAliasNewInLoop( Voo v{ f } ) { - - for( int i = 0; i < 10; ++i ) { - Voo w = new Voo(); - w.b = new Baw(); - w.b.f = new Foo(); - } - - taskexit( v{ !f } ); + + for( int i = 0; i < 10; ++i ) { + Voo w = new Voo(); + w.b = new Baw(); + w.b.f = new Foo(); + } + + taskexit( v{ !f } ); } task NoAliasNewInLoopAnotherWay( Voo v{ f } ) { - - for( int i = 0; i < 10; ++i ) { - Voo w = new Voo(); - Baw b = new Baw(); - Foo f = new Foo(); - - w.b = b; - b.f = f; - } - - taskexit( v{ !f } ); + + for( int i = 0; i < 10; ++i ) { + Voo w = new Voo(); + Baw b = new Baw(); + Foo f = new Foo(); + + w.b = b; + b.f = f; + } + + taskexit( v{ !f } ); } -- 2.34.1