From ef7399cf6163bd6505cb58ddff29f1bbe6b70d47 Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 10 Mar 2009 19:39:56 +0000 Subject: [PATCH] changed analysis public interface to report a set of common heap regions rather than a boolean for alias indication. Changed multicore code builder to check for non-empty set rather than boolean value --- .../OwnershipAnalysis/OwnershipAnalysis.java | 62 ++++++-- .../OwnershipAnalysis/OwnershipGraph.java | 141 +++++++++++++----- Robust/src/IR/Flat/BuildCodeMultiCore.java | 11 +- 3 files changed, 159 insertions(+), 55 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index d6e0530d..6b237c1d 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -28,7 +28,7 @@ public class OwnershipAnalysis { } - public boolean createsPotentialAliases(Descriptor taskOrMethod, + public Set createsPotentialAliases(Descriptor taskOrMethod, int paramIndex1, int paramIndex2) { @@ -37,7 +37,7 @@ public class OwnershipAnalysis { return og.hasPotentialAlias(paramIndex1, paramIndex2); } - public boolean createsPotentialAliases(Descriptor taskOrMethod, + public Set createsPotentialAliases(Descriptor taskOrMethod, int paramIndex, AllocationSite alloc) { @@ -46,7 +46,7 @@ public class OwnershipAnalysis { return og.hasPotentialAlias(paramIndex, alloc); } - public boolean createsPotentialAliases(Descriptor taskOrMethod, + public Set createsPotentialAliases(Descriptor taskOrMethod, AllocationSite alloc, int paramIndex) { @@ -55,7 +55,7 @@ public class OwnershipAnalysis { return og.hasPotentialAlias(paramIndex, alloc); } - public boolean createsPotentialAliases(Descriptor taskOrMethod, + public Set createsPotentialAliases(Descriptor taskOrMethod, AllocationSite alloc1, AllocationSite alloc2) { @@ -86,6 +86,26 @@ public class OwnershipAnalysis { } + public String prettyPrintNodeSet( Set s ) { + String out = "{\n"; + + Iterator i = s.iterator(); + while( i.hasNext() ) { + HeapRegionNode n = i.next(); + + AllocationSite as = n.getAllocationSite(); + if( as == null ) { + out += " "+n.toString()+",\n"; + } else { + out += " "+n.toString()+"-"+as.toStringVerbose()+",\n"; + } + } + + out += "}"; + return out; + } + + // use the methods given above to check every possible alias // between task parameters and flagged allocation sites reachable // from the task @@ -104,6 +124,8 @@ public class OwnershipAnalysis { HashSet allocSites = getFlaggedAllocationSitesReachableFromTask(td); + Set common; + // for each task parameter, check for aliases with // other task parameters and every allocation site // reachable from this task @@ -115,9 +137,11 @@ public class OwnershipAnalysis { // 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) ) { + common = createsPotentialAliases(td, i, j); + if( !common.isEmpty() ) { foundSomeAlias = true; bw.write("Potential alias between parameters "+i+" and "+j+".\n"); + bw.write(prettyPrintNodeSet( common )+"\n" ); } } @@ -127,9 +151,11 @@ public class OwnershipAnalysis { Iterator allocItr = allocSites.iterator(); while( allocItr.hasNext() ) { AllocationSite as = (AllocationSite) allocItr.next(); - if( createsPotentialAliases(td, i, as) ) { + common = createsPotentialAliases(td, i, as); + if( !common.isEmpty() ) { foundSomeAlias = true; bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n"); + bw.write(prettyPrintNodeSet( common )+"\n" ); } } } @@ -145,11 +171,15 @@ public class OwnershipAnalysis { Iterator allocItr2 = allocSites.iterator(); while( allocItr2.hasNext() ) { AllocationSite as2 = (AllocationSite) allocItr2.next(); + + if( !outerChecked.contains(as2) ) { + common = createsPotentialAliases(td, as1, as2); - if( !outerChecked.contains(as2) && - createsPotentialAliases(td, as1, as2) ) { - foundSomeAlias = true; - bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n"); + if( !common.isEmpty() ) { + foundSomeAlias = true; + bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n"); + bw.write(prettyPrintNodeSet( common )+"\n" ); + } } } @@ -189,10 +219,14 @@ public class OwnershipAnalysis { while( allocItr2.hasNext() ) { AllocationSite as2 = (AllocationSite) allocItr2.next(); - if( !outerChecked.contains(as2) && - createsPotentialAliases(d, as1, as2) ) { - foundSomeAlias = true; - bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n"); + if( !outerChecked.contains(as2) ) { + Set common = createsPotentialAliases(d, as1, as2); + + if( !common.isEmpty() ) { + foundSomeAlias = true; + bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n"); + bw.write( prettyPrintNodeSet( common )+"\n" ); + } } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index bb883d25..3dca5619 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -2742,7 +2742,7 @@ public class OwnershipGraph { } - public boolean hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) { + public Set hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) { assert hrn1 != null; assert hrn2 != null; @@ -2786,70 +2786,78 @@ public class OwnershipGraph { beta2 = beta2.union( edge.getBeta() ); } + boolean aliasDetected = false; + // only do this one if they are different tokens if( h1 != h2 && beta1.containsTupleSetWithBoth(h1, h2) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1plus, h2) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1star, h2) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1, h2plus) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1, h2star) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) { - return true; + aliasDetected = true; } if( beta1.containsTupleSetWithBoth(h1star, h2star) ) { - return true; + aliasDetected = true; } if( h1 != h2 && beta2.containsTupleSetWithBoth(h1, h2) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1plus, h2) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1star, h2) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1, h2plus) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1, h2star) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) { - return true; + aliasDetected = true; } if( beta2.containsTupleSetWithBoth(h1star, h2star) ) { - return true; + aliasDetected = true; } - return false; + Set common = new HashSet(); + if( aliasDetected ) { + common = findCommonReachableNodes( hrn1, hrn2 ); + assert !common.isEmpty(); + } + + return common; } - public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) { + public Set hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) { // get parameter's heap region assert paramIndex2id.containsKey(paramIndex1); @@ -2873,7 +2881,7 @@ public class OwnershipGraph { } - public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) { + public Set hasPotentialAlias(Integer paramIndex, AllocationSite as) { // get parameter's heap region assert paramIndex2id.containsKey(paramIndex); @@ -2888,8 +2896,9 @@ public class OwnershipGraph { HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() ); assert hrnSummary != null; - if( hasPotentialAlias( hrnParam, hrnSummary ) ) { - return true; + Set common = hasPotentialAlias( hrnParam, hrnSummary ); + if( !common.isEmpty() ) { + return common; } // check for other nodes @@ -2899,17 +2908,17 @@ public class OwnershipGraph { HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) ); assert hrnIthOldest != null; - if( hasPotentialAlias( hrnParam, hrnIthOldest ) ) { - return true; + common = hasPotentialAlias( hrnParam, hrnIthOldest ); + if( !common.isEmpty() ) { + return common; } } - return false; + return new HashSet(); } - public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) { - + public Set hasPotentialAlias(AllocationSite as1, AllocationSite as2) { // get summary node 1's alpha Integer idSum1 = as1.getSummary(); @@ -2923,8 +2932,9 @@ public class OwnershipGraph { HeapRegionNode hrnSum2 = id2hrn.get(idSum2); assert hrnSum2 != null; - if( hasPotentialAlias( hrnSum1, hrnSum2 ) ) { - return true; + Set common = hasPotentialAlias( hrnSum1, hrnSum2 ); + if( !common.isEmpty() ) { + return common; } // check sum2 against alloc1 nodes @@ -2934,8 +2944,9 @@ public class OwnershipGraph { HeapRegionNode hrnI1 = id2hrn.get(idI1); assert hrnI1 != null; - if( hasPotentialAlias( hrnI1, hrnSum2 ) ) { - return true; + common = hasPotentialAlias( hrnI1, hrnSum2 ); + if( !common.isEmpty() ) { + return common; } } @@ -2946,8 +2957,9 @@ public class OwnershipGraph { HeapRegionNode hrnI2 = id2hrn.get(idI2); assert hrnI2 != null; - if( hasPotentialAlias( hrnSum1, hrnI2 ) ) { - return true; + common = hasPotentialAlias( hrnSum1, hrnI2 ); + if( common.isEmpty() ) { + return common; } // while we're at it, do an inner loop for alloc2 vs alloc1 nodes @@ -2962,13 +2974,66 @@ public class OwnershipGraph { HeapRegionNode hrnI1 = id2hrn.get(idI1); - if( hasPotentialAlias( hrnI1, hrnI2 ) ) { - return true; + common = hasPotentialAlias( hrnI1, hrnI2 ); + if( !common.isEmpty() ) { + return common; } } } - return false; + return new HashSet(); + } + + + public Set findCommonReachableNodes( HeapRegionNode hrn1, + HeapRegionNode hrn2 ) { + + Set reachableNodes1 = new HashSet(); + Set reachableNodes2 = new HashSet(); + + Set todoNodes1 = new HashSet(); + todoNodes1.add( hrn1 ); + + Set todoNodes2 = new HashSet(); + todoNodes2.add( hrn2 ); + + // follow links until all reachable nodes have been found + while( !todoNodes1.isEmpty() ) { + HeapRegionNode hrn = todoNodes1.iterator().next(); + todoNodes1.remove( hrn ); + reachableNodes1.add(hrn); + + Iterator edgeItr = hrn.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + if( !reachableNodes1.contains( edge.getDst() ) ) { + todoNodes1.add( edge.getDst() ); + } + } + } + + while( !todoNodes2.isEmpty() ) { + HeapRegionNode hrn = todoNodes2.iterator().next(); + todoNodes2.remove( hrn ); + reachableNodes2.add(hrn); + + Iterator edgeItr = hrn.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + ReferenceEdge edge = edgeItr.next(); + + if( !reachableNodes2.contains( edge.getDst() ) ) { + todoNodes2.add( edge.getDst() ); + } + } + } + + Set intersection = + new HashSet( reachableNodes1 ); + + intersection.retainAll( reachableNodes2 ); + + return intersection; } diff --git a/Robust/src/IR/Flat/BuildCodeMultiCore.java b/Robust/src/IR/Flat/BuildCodeMultiCore.java index d5bcd870..0389f28c 100644 --- a/Robust/src/IR/Flat/BuildCodeMultiCore.java +++ b/Robust/src/IR/Flat/BuildCodeMultiCore.java @@ -17,6 +17,7 @@ import Analysis.TaskStateAnalysis.FlagState; import Analysis.TaskStateAnalysis.SafetyAnalysis; import Analysis.OwnershipAnalysis.AllocationSite; import Analysis.OwnershipAnalysis.OwnershipAnalysis; +import Analysis.OwnershipAnalysis.HeapRegionNode; import Analysis.Prefetch.*; import IR.ClassDescriptor; import IR.Descriptor; @@ -1328,12 +1329,14 @@ public class BuildCodeMultiCore extends BuildCode { Vector> aliasFNSets = new Vector>(); Hashtable> aliasFNTbl4Para = new Hashtable>(); Hashtable> aliasFNTbl = new Hashtable>(); + Set common; for( int i = 0; i < fm.numParameters(); ++i ) { // for the ith parameter check for aliases to all // higher numbered parameters aliasSets.add(null); for( int j = i + 1; j < fm.numParameters(); ++j ) { - if(this.m_oa.createsPotentialAliases(td, i, j)) { + common = this.m_oa.createsPotentialAliases(td, i, j); + if(!common.isEmpty()) { // ith parameter and jth parameter has alias, create lock to protect them if(aliasSets.elementAt(i) == null) { aliasSets.setElementAt(new Vector(), i); @@ -1348,7 +1351,8 @@ public class BuildCodeMultiCore extends BuildCode { aliasFNSets.add(null); for(int j = 0; j < allocSites.length; j++) { AllocationSite as = (AllocationSite)allocSites[j]; - if( this.m_oa.createsPotentialAliases(td, i, as) ) { + common = this.m_oa.createsPotentialAliases(td, i, as); + if( !common.isEmpty() ) { // ith parameter and allocationsite as has alias if(aliasFNSets.elementAt(i) == null) { aliasFNSets.setElementAt(new Vector(), i); @@ -1366,7 +1370,8 @@ public class BuildCodeMultiCore extends BuildCode { for(int j = i + 1; j < allocSites.length; j++) { AllocationSite as2 = (AllocationSite)allocSites[j]; - if( this.m_oa.createsPotentialAliases(td, as1, as2) ) { + common = this.m_oa.createsPotentialAliases(td, as1, as2); + if( !common.isEmpty() ) { // as1 and as2 has alias if(!aliasFNTbl.containsKey(as1.getFlatNew())) { aliasFNTbl.put(as1.getFlatNew(), new Vector()); -- 2.34.1