From c5ce6ce4abd8c3c1d8f07d99782e9fbf725c6df8 Mon Sep 17 00:00:00 2001 From: yeom Date: Fri, 19 Mar 2010 00:51:39 +0000 Subject: [PATCH] add interface. --- .../Analysis/Disjoint/DisjointAnalysis.java | 430 ++++++++++++++++++ Robust/src/Analysis/Disjoint/ReachGraph.java | 268 +++++++++++ 2 files changed, 698 insertions(+) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index fdb092fe..028860dc 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -11,6 +11,290 @@ import java.io.*; public class DisjointAnalysis { + + /////////////////////////////////////////// + // + // Public interface to discover possible + // aliases in the program under analysis + // + /////////////////////////////////////////// + + public HashSet + getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) { + checkAnalysisComplete(); + return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td); + } + + public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) { + checkAnalysisComplete(); + return getAllocSiteFromFlatNewPRIVATE(fn); + } + + public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) { + checkAnalysisComplete(); + return mapHrnIdToAllocSite.get(id); + } + + public Set createsPotentialAliases(Descriptor taskOrMethod, + int paramIndex1, + int paramIndex2) { + checkAnalysisComplete(); + ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert(rg != null); + return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2); + } + + public Set createsPotentialAliases(Descriptor taskOrMethod, + int paramIndex, AllocSite alloc) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(fm, paramIndex, alloc); + } + + public Set createsPotentialAliases(Descriptor taskOrMethod, + AllocSite alloc, int paramIndex) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + FlatMethod fm=state.getMethodFlat(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(fm, paramIndex, alloc); + } + + public Set createsPotentialAliases(Descriptor taskOrMethod, + AllocSite alloc1, AllocSite alloc2) { + checkAnalysisComplete(); + ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); + assert (rg != null); + return rg.mayReachSharedObjects(alloc1, alloc2); + } + + public String prettyPrintNodeSet(Set s) { + checkAnalysisComplete(); + + String out = "{\n"; + + Iterator i = s.iterator(); + while (i.hasNext()) { + HeapRegionNode n = i.next(); + + AllocSite as = n.getAllocSite(); + if (as == null) { + out += " " + n.toString() + ",\n"; + } else { + out += " " + n.toString() + ": " + as.toStringVerbose() + + ",\n"; + } + } + + out += "}\n"; + return out; + } + + // use the methods given above to check every possible alias + // between task parameters and flagged allocation sites reachable + // from the task + public void writeAllAliases(String outputFile, + String timeReport, + String justTime, + boolean tabularOutput, + int numLines +) + throws java.io.IOException { + checkAnalysisComplete(); + + BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile)); + + if (!tabularOutput) { + bw.write("Conducting ownership analysis with allocation depth = " + + allocationDepth + "\n"); + bw.write(timeReport + "\n"); + } + + int numAlias = 0; + + // look through every task for potential aliases + Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator(); + while (taskItr.hasNext()) { + TaskDescriptor td = (TaskDescriptor) taskItr.next(); + + if (!tabularOutput) { + bw.write("\n---------" + td + "--------\n"); + } + + 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 + boolean foundSomeAlias = false; + + 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) { + common = createsPotentialAliases(td, i, j); + if (!common.isEmpty()) { + foundSomeAlias = true; + if (!tabularOutput) { + bw.write("Potential alias between parameters " + i + + " and " + j + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } else { + ++numAlias; + } + } + } + + // 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()) { + AllocSite as = (AllocSite) allocItr.next(); + common = createsPotentialAliases(td, i, as); + if (!common.isEmpty()) { + foundSomeAlias = true; + if (!tabularOutput) { + bw.write("Potential alias between parameter " + i + + " and " + as.getFlatNew() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } else { + ++numAlias; + } + } + } + } + + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + HashSet outerChecked = new HashSet(); + Iterator allocItr1 = allocSites.iterator(); + while (allocItr1.hasNext()) { + AllocSite as1 = (AllocSite) allocItr1.next(); + + Iterator allocItr2 = allocSites.iterator(); + while (allocItr2.hasNext()) { + AllocSite as2 = (AllocSite) allocItr2.next(); + + if (!outerChecked.contains(as2)) { + common = createsPotentialAliases(td, as1, as2); + + if (!common.isEmpty()) { + foundSomeAlias = true; + if (!tabularOutput) { + bw.write("Potential alias between " + + as1.getFlatNew() + " and " + + as2.getFlatNew() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } else { + ++numAlias; + } + } + } + } + + outerChecked.add(as1); + } + + if (!foundSomeAlias) { + if (!tabularOutput) { + bw.write("No aliases between flagged objects in Task " + td + + ".\n"); + } + } + } + + /* + if (!tabularOutput) { + bw.write("\n" + computeAliasContextHistogram()); + } else { + bw.write(" & " + numAlias + " & " + justTime + " & " + numLines + + " & " + numMethodsAnalyzed() + " \\\\\n"); + } + */ + + bw.close(); + } + + // this version of writeAllAliases is for Java programs that have no tasks + public void writeAllAliasesJava(String outputFile, + String timeReport, + String justTime, + boolean tabularOutput, + int numLines +) + throws java.io.IOException { + checkAnalysisComplete(); + + assert !state.TASK; + + BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile)); + + bw.write("Conducting ownership analysis with allocation depth = " + + allocationDepth + "\n"); + bw.write(timeReport + "\n\n"); + + boolean foundSomeAlias = false; + + Descriptor d = typeUtil.getMain(); + HashSet allocSites = getFlaggedAllocationSites(d); + + // for each allocation site check for aliases with + // other allocation sites in the context of execution + // of this task + HashSet outerChecked = new HashSet(); + Iterator allocItr1 = allocSites.iterator(); + while (allocItr1.hasNext()) { + AllocSite as1 = (AllocSite) allocItr1.next(); + + Iterator allocItr2 = allocSites.iterator(); + while (allocItr2.hasNext()) { + AllocSite as2 = (AllocSite) allocItr2.next(); + + if (!outerChecked.contains(as2)) { + Set common = createsPotentialAliases(d, + as1, as2); + + if (!common.isEmpty()) { + foundSomeAlias = true; + bw.write("Potential alias between " + + as1.getDisjointAnalysisId() + " and " + + as2.getDisjointAnalysisId() + ".\n"); + bw.write(prettyPrintNodeSet(common) + "\n"); + } + } + } + + outerChecked.add(as1); + } + + if (!foundSomeAlias) { + bw.write("No aliases between flagged objects found.\n"); + } + +// bw.write("\n" + computeAliasContextHistogram()); + bw.close(); + } + + /////////////////////////////////////////// + // + // end public interface + // + /////////////////////////////////////////// + + protected void checkAnalysisComplete() { + if( !analysisComplete ) { + throw new Error("Warning: public interface method called while analysis is running."); + } + } // data from the compiler @@ -20,6 +304,14 @@ public class DisjointAnalysis { public ArrayReferencees arrayReferencees; public TypeUtil typeUtil; public int allocationDepth; + + // data structure for public interface + private Hashtable > mapDescriptorToAllocationSiteSet; + + + // for public interface methods to warn that they + // are grabbing results during analysis + private boolean analysisComplete; // used to identify HeapRegionNode objects @@ -173,6 +465,8 @@ public class DisjointAnalysis { Liveness liveness, ArrayReferencees arrayReferencees ) throws java.io.IOException { + + analysisComplete = false; this.state = state; this.typeUtil = typeUtil; @@ -193,6 +487,7 @@ public class DisjointAnalysis { // start interprocedural fixed-point computation analyzeMethods(); + analysisComplete=true; double timeEndAnalysis = (double) System.nanoTime(); double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) ); @@ -1352,8 +1647,143 @@ private ReachGraph createInitialTaskReachGraph(FlatMethod fm) { // debugSnapshot(rg, fm, true); return rg; } + +// return all allocation sites in the method (there is one allocation +// site per FlatNew node in a method) +private HashSet getAllocationSiteSet(Descriptor d) { + if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) { + buildAllocationSiteSet(d); + } + + return mapDescriptorToAllocationSiteSet.get(d); + +} + +private void buildAllocationSiteSet(Descriptor d) { + HashSet s = new HashSet(); + + FlatMethod fm; + if( d instanceof MethodDescriptor ) { + fm = state.getMethodFlat( (MethodDescriptor) d); + } else { + assert d instanceof TaskDescriptor; + fm = state.getMethodFlat( (TaskDescriptor) d); + } + + // visit every node in this FlatMethod's IR graph + // and make a set of the allocation sites from the + // FlatNew node's visited + HashSet visited = new HashSet(); + HashSet toVisit = new HashSet(); + toVisit.add(fm); + + while( !toVisit.isEmpty() ) { + FlatNode n = toVisit.iterator().next(); + + if( n instanceof FlatNew ) { + s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) ); + } + + toVisit.remove(n); + visited.add(n); + + for( int i = 0; i < n.numNext(); ++i ) { + FlatNode child = n.getNext(i); + if( !visited.contains(child) ) { + toVisit.add(child); + } + } + } + + mapDescriptorToAllocationSiteSet.put(d, s); + } + + private HashSet getFlaggedAllocationSites(Descriptor dIn) { + + HashSet out = new HashSet(); + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + toVisit.add(dIn); + + while (!toVisit.isEmpty()) { + Descriptor d = toVisit.iterator().next(); + toVisit.remove(d); + visited.add(d); + + HashSet asSet = getAllocationSiteSet(d); + Iterator asItr = asSet.iterator(); + while (asItr.hasNext()) { + AllocSite as = (AllocSite) asItr.next(); + if (as.getDisjointAnalysisId() != null) { + out.add(as); + } + } + + // enqueue callees of this method to be searched for + // allocation sites also + Set callees = callGraph.getCalleeSet(d); + if (callees != null) { + Iterator methItr = callees.iterator(); + while (methItr.hasNext()) { + MethodDescriptor md = (MethodDescriptor) methItr.next(); + + if (!visited.contains(md)) { + toVisit.add(md); + } + } + } + } + + return out; + } + +private HashSet +getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) { + + HashSet asSetTotal = new HashSet(); + HashSet toVisit = new HashSet(); + HashSet visited = new HashSet(); + + toVisit.add(td); + // traverse this task and all methods reachable from this task + while( !toVisit.isEmpty() ) { + Descriptor d = toVisit.iterator().next(); + toVisit.remove(d); + visited.add(d); + + HashSet asSet = getAllocationSiteSet(d); + Iterator asItr = asSet.iterator(); + while( asItr.hasNext() ) { + AllocSite as = (AllocSite) asItr.next(); + TypeDescriptor typed = as.getType(); + if( typed != null ) { + ClassDescriptor cd = typed.getClassDesc(); + if( cd != null && cd.hasFlags() ) { + asSetTotal.add(as); + } + } + } + + // enqueue callees of this method to be searched for + // allocation sites also + Set callees = callGraph.getCalleeSet(d); + if( callees != null ) { + Iterator methItr = callees.iterator(); + while( methItr.hasNext() ) { + MethodDescriptor md = (MethodDescriptor) methItr.next(); + + if( !visited.contains(md) ) { + toVisit.add(md); + } + } + } + } + + return asSetTotal; +} int zzz = 0; diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 72f42dbd..d1b5bab5 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -4000,5 +4000,273 @@ public class ReachGraph { callerNodeIDsCopiedToCallee ); } } + + 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()) { + RefEdge 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()) { + RefEdge edge = edgeItr.next(); + + if (!reachableNodes2.contains(edge.getDst())) { + todoNodes2.add(edge.getDst()); + } + } + } + + Set intersection = new HashSet( + reachableNodes1); + + intersection.retainAll(reachableNodes2); + + return intersection; + } + + public Set mayReachSharedObjects(HeapRegionNode hrn1, + HeapRegionNode hrn2) { + assert hrn1 != null; + assert hrn2 != null; + + // then get the various tokens for these heap regions + ReachTuple h1 = ReachTuple.factory(hrn1.getID(), + !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false); + + ReachTuple h1plus = ReachTuple.factory(hrn1.getID(), !hrn1 + .isSingleObject(), ReachTuple.ARITY_ONEORMORE, false); + + ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1 + .isSingleObject(), ReachTuple.ARITY_ZEROORMORE, false); + + ReachTuple h2 = ReachTuple.factory(hrn2.getID(), + !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false); + + ReachTuple h2plus = ReachTuple.factory(hrn2.getID(), !hrn2 + .isSingleObject(), ReachTuple.ARITY_ONEORMORE, false); + + ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2 + .isSingleObject(), ReachTuple.ARITY_ZEROORMORE, false); + + // then get the merged beta of all out-going edges from these heap + // regions + + ReachSet beta1 = ReachSet.factory(); + Iterator itrEdge = hrn1.iteratorToReferencees(); + while (itrEdge.hasNext()) { + RefEdge edge = itrEdge.next(); + beta1 = Canonical.union(beta1, edge.getBeta()); + } + + ReachSet beta2 = ReachSet.factory(); + itrEdge = hrn2.iteratorToReferencees(); + while (itrEdge.hasNext()) { + RefEdge edge = itrEdge.next(); + beta2 = Canonical.union(beta2, edge.getBeta()); + } + + boolean aliasDetected = false; + + // only do this one if they are different tokens + if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1plus, h2)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1star, h2)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1, h2plus)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1plus, h2plus)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1star, h2plus)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1, h2star)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1plus, h2star)) { + aliasDetected = true; + } + if (beta1.containsStateWithBoth(h1star, h2star)) { + aliasDetected = true; + } + + if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1plus, h2)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1star, h2)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1, h2plus)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1plus, h2plus)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1star, h2plus)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1, h2star)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1plus, h2star)) { + aliasDetected = true; + } + if (beta2.containsStateWithBoth(h1star, h2star)) { + aliasDetected = true; + } + + Set common = new HashSet(); + if (aliasDetected) { + common = findCommonReachableNodes(hrn1, hrn2); + if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) { + assert !common.isEmpty(); + } + } + + return common; + } + + public Set mayReachSharedObjects(FlatMethod fm, + Integer paramIndex1, Integer paramIndex2) { + + // get parameter's heap regions + TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue()); + VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1); + RefEdge argEdge1 = argVar1.iteratorToReferencees().next(); + HeapRegionNode hrnParam1 = argEdge1.getDst(); + + TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue()); + VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2); + RefEdge argEdge2 = argVar2.iteratorToReferencees().next(); + HeapRegionNode hrnParam2 = argEdge2.getDst(); + + Set common = new HashSet(); + common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2)); + + return common; + } + + public Set mayReachSharedObjects(FlatMethod fm, + Integer paramIndex, AllocSite as) { + // get parameter's heap regions + TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue()); + VariableNode argVar = getVariableNodeFromTemp(paramTemp); + RefEdge argEdge = argVar.iteratorToReferencees().next(); + HeapRegionNode hrnParam = argEdge.getDst(); + + // get summary node + assert id2hrn.containsKey(as.getSummary()); + HeapRegionNode hrnSummary = id2hrn.get(as.getSummary()); + assert hrnSummary != null; + + Set common = mayReachSharedObjects(hrnParam, hrnSummary); + + // check for other nodes + for (int i = 0; i < as.getAllocationDepth(); ++i) { + + assert id2hrn.containsKey(as.getIthOldest(i)); + HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i)); + assert hrnIthOldest != null; + + common = mayReachSharedObjects(hrnParam, hrnIthOldest); + + } + + return common; + } + + public Set mayReachSharedObjects(AllocSite as1, + AllocSite as2) { + + // get summary node 1's alpha + Integer idSum1 = as1.getSummary(); + assert id2hrn.containsKey(idSum1); + HeapRegionNode hrnSum1 = id2hrn.get(idSum1); + assert hrnSum1 != null; + + // get summary node 2's alpha + Integer idSum2 = as2.getSummary(); + assert id2hrn.containsKey(idSum2); + HeapRegionNode hrnSum2 = id2hrn.get(idSum2); + assert hrnSum2 != null; + + Set common = mayReachSharedObjects(hrnSum1, hrnSum2); + + // check sum2 against alloc1 nodes + for (int i = 0; i < as1.getAllocationDepth(); ++i) { + Integer idI1 = as1.getIthOldest(i); + assert id2hrn.containsKey(idI1); + HeapRegionNode hrnI1 = id2hrn.get(idI1); + assert hrnI1 != null; + + common.addAll(mayReachSharedObjects(hrnI1, hrnSum2)); + } + + // check sum1 against alloc2 nodes + for (int i = 0; i < as2.getAllocationDepth(); ++i) { + Integer idI2 = as2.getIthOldest(i); + assert id2hrn.containsKey(idI2); + HeapRegionNode hrnI2 = id2hrn.get(idI2); + assert hrnI2 != null; + + common.addAll(mayReachSharedObjects(hrnSum1, hrnI2)); + + // while we're at it, do an inner loop for alloc2 vs alloc1 nodes + for (int j = 0; j < as1.getAllocationDepth(); ++j) { + Integer idI1 = as1.getIthOldest(j); + + // if these are the same site, don't look for the same token, no + // alias. + // different tokens of the same site could alias together though + if (idI1.equals(idI2)) { + continue; + } + + HeapRegionNode hrnI1 = id2hrn.get(idI1); + + common.addAll(mayReachSharedObjects(hrnI1, hrnI2)); + } + } + + return common; + } + } -- 2.34.1