From 3d6beffd93c29be052752a3e080b19053c3cf976 Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 3 Sep 2008 23:03:53 +0000 Subject: [PATCH] minor bug fixes and support for matching classes to super class when mapping edges into callers --- .../OwnershipAnalysis/AllocationSite.java | 4 + .../OwnershipAnalysis/OwnershipAnalysis.java | 41 +++--- .../OwnershipAnalysis/OwnershipGraph.java | 119 ++++++++++-------- Robust/src/Main/Main.java | 2 +- 4 files changed, 96 insertions(+), 70 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java index 3bcbdb7a..6d7e3b5f 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java +++ b/Robust/src/Analysis/OwnershipAnalysis/AllocationSite.java @@ -167,4 +167,8 @@ public class AllocationSite { public String toString() { return "allocSite" + id; } + + public String toStringVerbose() { + return "allocSite" + id + " "+type.toPrettyString(); + } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 79186c6f..45f52593 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -76,6 +76,7 @@ public class OwnershipAnalysis { TaskDescriptor td = (TaskDescriptor) taskItr.next(); bw.write("\n---------"+td+"--------\n"); + bw.flush(); HashSet allocSites = getFlaggedAllocationSitesReachableFromTask(td); @@ -123,6 +124,7 @@ public class OwnershipAnalysis { if( !outerChecked.contains(as2) && createsPotentialAliases(td, as1, as2) ) { + foundSomeAlias = true; bw.write("Potential alias between "+as1+" and "+as2+".\n"); } } @@ -153,6 +155,7 @@ public class OwnershipAnalysis { // data from the compiler private State state; + private TypeUtil typeUtil; private CallGraph callGraph; private int allocationDepth; @@ -208,12 +211,14 @@ public class OwnershipAnalysis { // this analysis generates an ownership graph for every task // in the program public OwnershipAnalysis(State state, + TypeUtil tu, CallGraph callGraph, int allocationDepth, boolean writeFinalGraphs, boolean writeAllUpdates) throws java.io.IOException { this.state = state; + this.typeUtil = tu; this.callGraph = callGraph; this.allocationDepth = allocationDepth; this.writeFinalGraphs = writeFinalGraphs; @@ -252,7 +257,7 @@ public class OwnershipAnalysis { Iterator dItr = descriptorsToAnalyze.iterator(); while( dItr.hasNext() ) { Descriptor d = dItr.next(); - OwnershipGraph og = new OwnershipGraph(allocationDepth); + OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil); FlatMethod fm; if( d instanceof MethodDescriptor ) { @@ -264,7 +269,7 @@ public class OwnershipAnalysis { System.out.println("Previsiting " + d); - analyzeFlatNode(d, fm, null, og); + og = analyzeFlatNode(d, fm, null, og); setGraphForDescriptor(d, og); } @@ -389,7 +394,7 @@ public class OwnershipAnalysis { // perform this node's contributions to the ownership // graph on a new copy, then compare it to the old graph // at this node to see if anything was updated. - OwnershipGraph og = new OwnershipGraph(allocationDepth); + OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil); // start by merging all node's parents' graphs for( int i = 0; i < fn.numPrev(); ++i ) { @@ -401,10 +406,10 @@ public class OwnershipAnalysis { // apply the analysis of the flat node to the // ownership graph made from the merge of the // parent graphs - analyzeFlatNode(mDesc, - fn, - returnNodesToCombineForCompleteOwnershipGraph, - og); + og = analyzeFlatNode(mDesc, + fn, + returnNodesToCombineForCompleteOwnershipGraph, + og); // if the results of the new graph are different from // the current graph at this node, replace the graph @@ -425,7 +430,7 @@ public class OwnershipAnalysis { // end by merging all return nodes into a complete // ownership graph that represents all possible heap // states after the flat method returns - OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth); + OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil); Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator(); while( retItr.hasNext() ) { FlatReturnNode frn = (FlatReturnNode) retItr.next(); @@ -436,7 +441,7 @@ public class OwnershipAnalysis { } - private void + private OwnershipGraph analyzeFlatNode(Descriptor methodDesc, FlatNode fn, HashSet setRetNodes, @@ -473,7 +478,7 @@ public class OwnershipAnalysis { } // then remember it - OwnershipGraph ogResult = new OwnershipGraph(allocationDepth); + OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil); ogResult.merge(og); mapFlatMethodToInitialParamAllocGraph.put(fm, ogResult); @@ -540,7 +545,7 @@ public class OwnershipAnalysis { FlatCall fc = (FlatCall) fn; MethodDescriptor md = fc.getMethod(); FlatMethod flatm = state.getMethodFlat(md); - OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth); + OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil); if( md.isStatic() ) { // a static method is simply always the same, makes life easy @@ -560,7 +565,7 @@ public class OwnershipAnalysis { // don't alter the working graph (og) until we compute a result for every // possible callee, merge them all together, then set og to that - OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth); + OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil); ogCopy.merge(og); OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd); @@ -583,6 +588,8 @@ public class OwnershipAnalysis { setRetNodes.add(frn); break; } + + return og; } @@ -625,7 +632,7 @@ public class OwnershipAnalysis { private OwnershipGraph getGraphFromFlatNode(FlatNode fn) { if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) { - mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) ); + mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth, typeUtil) ); } return mapFlatNodeToOwnershipGraph.get(fn); @@ -729,8 +736,12 @@ public class OwnershipAnalysis { Iterator asItr = asSet.iterator(); while( asItr.hasNext() ) { AllocationSite as = (AllocationSite) asItr.next(); - if( as.getType().getClassDesc().hasFlags() ) { - asSetTotal.add(as); + TypeDescriptor typed = as.getType(); + if( typed != null ) { + ClassDescriptor cd = typed.getClassDesc(); + if( cd != null && cd.hasFlags() ) { + asSetTotal.add(as); + } } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 7c281455..bda12c73 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -8,6 +8,7 @@ import java.io.*; public class OwnershipGraph { private int allocationDepth; + private TypeUtil typeUtil; // there was already one other very similar reason // for traversing heap nodes that is no longer needed @@ -30,8 +31,9 @@ public class OwnershipGraph { - public OwnershipGraph(int allocationDepth) { + public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) { this.allocationDepth = allocationDepth; + this.typeUtil = typeUtil; id2hrn = new Hashtable(); td2ln = new Hashtable(); @@ -1297,48 +1299,19 @@ public class OwnershipGraph { Iterator srcItr = possibleCallerSrcs.iterator(); while( srcItr.hasNext() ) { HeapRegionNode src = (HeapRegionNode) srcItr.next(); - - // check that if this source node has a definite type that - // it also has the appropriate field, otherwise prune this - AllocationSite asSrc = src.getAllocationSite(); - if( asSrc != null ) { - boolean foundField = false; - TypeDescriptor tdSrc = asSrc.getType(); - if( tdSrc != null && tdSrc.isClass() ) { - Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields(); - while( fieldsSrcItr.hasNext() ) { - FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next(); - if( fd == edgeCallee.getFieldDesc() ) { - foundField = true; - break; - } - } - if( !foundField ) { - // prune this source node possibility - continue; - } - } + + if( !hasMatchingField( src, edgeCallee ) ) { + // prune this source node possibility + continue; } Iterator dstItr = possibleCallerDsts.iterator(); while( dstItr.hasNext() ) { HeapRegionNode dst = (HeapRegionNode) dstItr.next(); - // check if this dst node has a definite type and - // if it matches the callee edge - AllocationSite asDst = dst.getAllocationSite(); - if( asDst != null && edgeCallee.getFieldDesc() != null ) { - if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { - continue; - } - if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { - continue; - } - if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) { - if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) { - continue; - } - } + if( !hasMatchingType( edgeCallee, dst ) ) { + // prune + continue; } // otherwise the caller src and dst pair can match the edge, so make it @@ -1401,23 +1374,9 @@ public class OwnershipGraph { while( itrHrn.hasNext() ) { HeapRegionNode hrnCaller = itrHrn.next(); - // check if this dst node has a definite type and - // if it matches the callee edge - // check if this dst node has a definite type and - // if it matches the callee edge - AllocationSite asDst = hrnCaller.getAllocationSite(); - if( asDst != null && edgeCallee.getFieldDesc() != null ) { - if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { - continue; - } - if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { - continue; - } - if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) { - if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) { - continue; - } - } + if( !hasMatchingType( edgeCallee, hrnCaller ) ) { + // prune + continue; } // otherwise caller node can match callee edge, so make it @@ -1427,6 +1386,7 @@ public class OwnershipGraph { 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 { @@ -1508,6 +1468,57 @@ public class OwnershipGraph { } + protected boolean hasMatchingField( HeapRegionNode src, ReferenceEdge edge ) { + + // if no allocation site, then it's a match-everything region + AllocationSite asSrc = src.getAllocationSite(); + if( asSrc == null ) { return true; } + + TypeDescriptor tdSrc = asSrc.getType(); + assert tdSrc != null; + + // if it's not a class, it doesn't have any fields to match + if( !tdSrc.isClass() ) { return false; } + + Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields(); + while( fieldsSrcItr.hasNext() ) { + FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next(); + if( fd == edge.getFieldDesc() ) { + return true; + } + } + + // otherwise it is a class with fields + // but we didn't find a match + return false; + } + + + protected boolean hasMatchingType( ReferenceEdge edge, HeapRegionNode dst ) { + + // if the region has no type, matches everything + AllocationSite asDst = dst.getAllocationSite(); + if( asDst == null ) { return true; } + + TypeDescriptor tdDst = asDst.getType(); + assert tdDst != null; + + // if the type is not a class don't match because + // primitives are copied, no memory aliases + ClassDescriptor cdDst = tdDst.getClassDesc(); + if( cdDst == null ) { return false; } + + // if the field is null, it matches everything + FieldDescriptor fd = edge.getFieldDesc(); + if( fd == null ) { return true; } + TypeDescriptor tdFd = fd.getType(); + assert tdFd != null; + + return typeUtil.isSuperorType( tdFd, tdDst ); + } + + + protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) { edge.setBeta(edge.getBeta().unshadowTokens(as) ); } diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 0573bdab..6620e41b 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -453,7 +453,7 @@ public class Main { CallGraph callGraph = new CallGraph(state); int allocationDepth = 3; OwnershipAnalysis oa = - new OwnershipAnalysis(state, callGraph, allocationDepth, true, true); + new OwnershipAnalysis(state, tu, callGraph, allocationDepth, true, false); // oa.writeAllAliases( "identifiedAliases.txt" ); } -- 2.34.1