From 9be3f7ad75adb13bd08878b6e832c57b0a03c7c3 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 19 Oct 2009 21:15:42 +0000 Subject: [PATCH] omputation to determine set of aliased parameter indices was very conservative, but correct, fortunately. It used to list every parameter pair that could reach a common node as aliased! Yikes! Actually, we want to see that parameters can directly reference a common node, but further, they can only be aliased if the edges to the shared node both have a common reachability state that is also on the shared node. Otherwise they cannot be referencing a common concrete object. --- .../OwnershipAnalysis/OwnershipAnalysis.java | 6 +- .../OwnershipAnalysis/OwnershipGraph.java | 203 +++++++++--------- Robust/src/Benchmarks/Ownership/makefile | 1 + Robust/src/IR/Flat/FlatCall.java | 20 ++ 4 files changed, 129 insertions(+), 101 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index f7ff02f6..ee9954b7 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -977,7 +977,7 @@ public class OwnershipAnalysis { ogMergeOfAllPossibleCalleeResults = og; Set aliasedParamIndices = - ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm); + ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, flatm); MethodContext mcNew = new MethodContext( md, aliasedParamIndices ); Set contexts = mapDescriptorToAllMethodContexts.get( md ); @@ -1023,7 +1023,7 @@ public class OwnershipAnalysis { ogCopy.merge(og); Set aliasedParamIndices = - ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm); + ogCopy.calculateAliasedParamSet(fc, pflatm); MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices ); Set contexts = mapDescriptorToAllMethodContexts.get( md ); @@ -1516,7 +1516,7 @@ public class OwnershipAnalysis { MethodDescriptor md=fc.getMethod(); FlatMethod flatm = state.getMethodFlat(md); - Set aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, md.isStatic(), flatm); + Set aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, flatm); MethodContext calleeMC = new MethodContext( md, aliasedParamIndices ); return calleeMC; diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 4f8567f3..c61a9ea4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -931,6 +931,24 @@ public class OwnershipGraph { LabelNode lnParamI = getLabelNodeFromTemp( tdParamI ); Integer idPrimaryI = paramIndex2idPrimary.get( i ); + + /* + if( idPrimaryI == null ) { + try { + writeGraph( "debugalias", + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // show back edges to confirm graph validity + false, // show parameter indices (unmaintained!) + true, // hide subset reachability states + true); // hide edge taints + } catch( Exception e ) {} + System.out.println( "FlatMethod="+fm+"\nalias set="+aliasedParamIndices+ + "\nindex bad="+i); + } + */ + assert idPrimaryI != null; HeapRegionNode primaryI = id2hrn.get( idPrimaryI ); assert primaryI != null; @@ -1658,111 +1676,117 @@ public class OwnershipGraph { public Set calculateAliasedParamSet( FlatCall fc, - boolean isStatic, FlatMethod fm ) { + // to decide if two parameters are aliased, look + // at the caller graph (this graph) and if these + // two conditions are met, they may be aliased: + // 1. The argument labels reference a shared node + // 2. The edges to that shared node have a common + // reachability state. + + Set aliasedIndices = new HashSet(); + - Hashtable paramIndex2ln = - new Hashtable(); + //System.out.println("Aliases for "+fm+" at "+fc); - Hashtable > paramIndex2reachableCallerNodes = - new Hashtable >(); for( int i = 0; i < fm.numParameters(); ++i ) { - Integer paramIndex = new Integer( i ); - TempDescriptor tdParam = fm.getParameter( i ); - TypeDescriptor typeParam = tdParam.getType(); + for( int j = 0; j < i; ++j ) { - if( typeParam.isImmutable() && !typeParam.isArray() ) { - // don't bother with this primitive parameter, it - // cannot affect reachability - continue; - } + TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, i ); + LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i ); - // 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 - TempDescriptor argTemp_i; - if( isStatic ) { - argTemp_i = fc.getArg(paramIndex); - } else { - if( paramIndex.equals(0) ) { - argTemp_i = fc.getThis(); - } else { - argTemp_i = fc.getArg(paramIndex - 1); - } - } + TempDescriptor argTemp_j = fc.getArgMatchingParamIndex( fm, j ); + LabelNode argLabel_j = getLabelNodeFromTemp( argTemp_j ); - // 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(); - } + /* + System.out.println(" "+argTemp_i.getType()+" "+argTemp_i+" and "+ + argTemp_j.getType()+" "+argTemp_j+" aliased?"); + */ - LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i); - paramIndex2ln.put(paramIndex, argLabel_i); - } + // first condition--do these arguments + // reference any common nodes? + Iterator edgeItr; - Iterator lnArgItr = paramIndex2ln.entrySet().iterator(); - while( lnArgItr.hasNext() ) { - Map.Entry me = (Map.Entry)lnArgItr.next(); - Integer index = (Integer) me.getKey(); - LabelNode lnArg_i = (LabelNode) me.getValue(); + Set hrnSetI = new HashSet(); + edgeItr = argLabel_i.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + hrnSetI.add( edgeItr.next().getDst() ); + } - HashSet reachableNodes = new HashSet(); - HashSet todoNodes = new HashSet(); + Set hrnSetJ = new HashSet(); + edgeItr = argLabel_j.iteratorToReferencees(); + while( edgeItr.hasNext() ) { + hrnSetJ.add( edgeItr.next().getDst() ); + } - // to find all reachable nodes, start with label referencees - Iterator edgeArgItr = lnArg_i.iteratorToReferencees(); - while( edgeArgItr.hasNext() ) { - ReferenceEdge edge = edgeArgItr.next(); - todoNodes.add( edge.getDst() ); - } + Set intersection = + new HashSet( hrnSetI ); + intersection.retainAll( hrnSetJ ); - // then follow links until all reachable nodes have been found - while( !todoNodes.isEmpty() ) { - HeapRegionNode hrn = todoNodes.iterator().next(); - todoNodes.remove(hrn); - reachableNodes.add(hrn); + // condition two--for each shared node, do the reference + // edges to it from arguments have a common reachability + // state that is *ALSO* on the shared node? + boolean foundAlias = false; - Iterator edgeItr = hrn.iteratorToReferencees(); - while( edgeItr.hasNext() ) { - ReferenceEdge edge = edgeItr.next(); + Iterator hrnItr = intersection.iterator(); + while( hrnItr.hasNext() ) { + HeapRegionNode hrn = hrnItr.next(); - if( !reachableNodes.contains(edge.getDst() ) ) { - todoNodes.add(edge.getDst() ); - } - } - } + ReferenceEdge ei = argLabel_i.getReferenceTo( hrn, + argTemp_i.getType(), + null ); - // save for later - paramIndex2reachableCallerNodes.put(index, reachableNodes); - } + ReferenceEdge ej = argLabel_j.getReferenceTo( hrn, + argTemp_j.getType(), + null ); + assert ei != null; + assert ej != null; - Set aliasedIndices = new HashSet(); + ReachabilitySet allStatesForParamI = + ei.getBeta().intersection( hrn.getAlpha() ); - // check for arguments that are aliased - for( int i = 0; i < fm.numParameters(); ++i ) { - for( int j = 0; j < i; ++j ) { - HashSet s1 = paramIndex2reachableCallerNodes.get( i ); - HashSet s2 = paramIndex2reachableCallerNodes.get( j ); + ReachabilitySet allStatesForParamJ = + ej.getBeta().intersection( hrn.getAlpha() ); - // some parameters are immutable or primitive, so skip em - if( s1 == null || s2 == null ) { - continue; - } + ReachabilitySet commonStates = + allStatesForParamI.intersection( allStatesForParamJ ); - Set intersection = new HashSet(s1); - intersection.retainAll(s2); + if( !commonStates.isEmpty() ) { + foundAlias = true; + aliasedIndices.add( new Integer( i ) ); + aliasedIndices.add( new Integer( j ) ); - if( !intersection.isEmpty() ) { - aliasedIndices.add( new Integer( i ) ); - aliasedIndices.add( new Integer( j ) ); + //System.out.println( " yes!" ); + } + } + + // as soon as we detect one possible way to alias + // these parameters, skip on to another pair + if( foundAlias ) { + continue; } } } + if( !aliasedIndices.isEmpty() ) { + try { + writeGraph( "foundaliases", + true, // write labels (variables) + true, // selectively hide intermediate temp vars + true, // prune unreachable heap regions + false, // show back edges to confirm graph validity + false, // show parameter indices (unmaintained!) + true, // hide subset reachability states + true); // hide edge taints + } catch( Exception e ) {} + /* + System.out.println("FlatCall="+fc+ + "\nflat method="+fm+ + "\nAliases="+aliasedIndices ); + */ + } + return aliasedIndices; } @@ -2073,24 +2097,7 @@ public class OwnershipGraph { // 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 - TempDescriptor argTemp_i; - if( isStatic ) { - argTemp_i = fc.getArg( paramIndex ); - } else { - if( paramIndex.equals( 0 ) ) { - argTemp_i = fc.getThis(); - } else { - argTemp_i = fc.getArg( paramIndex - 1 ); - } - } - - // 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(); - } + TempDescriptor argTemp_i = fc.getArgMatchingParamIndex( fm, paramIndex ); // remember which caller arg label maps to param index LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i ); diff --git a/Robust/src/Benchmarks/Ownership/makefile b/Robust/src/Benchmarks/Ownership/makefile index 426d1b7d..0efaf50e 100644 --- a/Robust/src/Benchmarks/Ownership/makefile +++ b/Robust/src/Benchmarks/Ownership/makefile @@ -37,3 +37,4 @@ clean: rm -f *.log rm -f *.pdf rm -f aliases.txt + rm -f tabResults.tex diff --git a/Robust/src/IR/Flat/FlatCall.java b/Robust/src/IR/Flat/FlatCall.java index f8a5d39e..5130b1c4 100644 --- a/Robust/src/IR/Flat/FlatCall.java +++ b/Robust/src/IR/Flat/FlatCall.java @@ -50,6 +50,26 @@ public class FlatCall extends FlatNode { return args[i]; } + public TempDescriptor getArgMatchingParamIndex(FlatMethod fm, int i) { + // in non-static methods the "this" pointer + // affects the matching index + if( method.isStatic() ) { + assert numArgs() == fm.numParameters(); + } else { + assert numArgs()+1 == fm.numParameters(); + } + + if( method.isStatic() ) { + return args[i]; + } + + if( i == 0 ) { + return this_temp; + } + + return args[i-1]; + } + public String toString() { String st="FlatCall_"; if (dst==null) { -- 2.34.1