From a53844d600da95e27085f7c12a11b1290b9497ef Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 29 Jun 2010 22:11:27 +0000 Subject: [PATCH] reachability query interface for ooojava heap conflict analysis added --- .../Analysis/Disjoint/DisjointAnalysis.java | 180 +++++++++++------- Robust/src/Analysis/Disjoint/ReachGraph.java | 18 ++ 2 files changed, 129 insertions(+), 69 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index ee933a70..8ec1e4c9 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -14,86 +14,122 @@ 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 interface to discover possible + // sharing in the program under analysis + // + /////////////////////////////////////////// + + // if an object allocated at the target site may be + // reachable from both an object from root1 and an + // object allocated at root2, return TRUE + public boolean mayBothReachTarget( FlatNew fnRoot1, + FlatNew fnRoot2, + FlatNew fnTarget ) { + + AllocSite asr1 = getAllocationSiteFromFlatNew( fnRoot1 ); + AllocSite asr2 = getAllocationSiteFromFlatNew( fnRoot2 ); + assert asr1.isFlagged(); + assert asr2.isFlagged(); + + AllocSite ast = getAllocationSiteFromFlatNew( fnTarget ); + ReachGraph rg = getPartial( typeUtil.getMain() ); + + return rg.mayBothReachTarget( asr1, asr2, ast ); + } + + // similar to the method above, return TRUE if ever + // more than one object from the root allocation site + // may reach an object from the target site + public boolean mayManyReachTarget( FlatNew fnRoot, + FlatNew fnTarget ) { + + AllocSite asr = getAllocationSiteFromFlatNew( fnRoot ); + assert asr.isFlagged(); + + AllocSite ast = getAllocationSiteFromFlatNew( fnTarget ); + ReachGraph rg = getPartial( typeUtil.getMain() ); + + return rg.mayManyReachTarget( asr, ast ); + } + + + + + public HashSet + getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) { + checkAnalysisComplete(); + return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td); + } - public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) { - checkAnalysisComplete(); - return getAllocSiteFromFlatNewPRIVATE(fn); - } + public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) { + checkAnalysisComplete(); + return getAllocSiteFromFlatNewPRIVATE(fn); + } - public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) { - checkAnalysisComplete(); - return mapHrnIdToAllocSite.get(id); - } + public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) { + checkAnalysisComplete(); + return mapHrnIdToAllocSite.get(id); + } - public Set hasPotentialSharing(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 hasPotentialSharing(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 hasPotentialSharing(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 hasPotentialSharing(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 hasPotentialSharing(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 hasPotentialSharing(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 hasPotentialSharing(Descriptor taskOrMethod, - AllocSite alloc1, AllocSite alloc2) { - checkAnalysisComplete(); - ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod); - assert (rg != null); - return rg.mayReachSharedObjects(alloc1, alloc2); - } + public Set hasPotentialSharing(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(); + public String prettyPrintNodeSet(Set s) { + checkAnalysisComplete(); - String out = "{\n"; + String out = "{\n"; - Iterator i = s.iterator(); - while (i.hasNext()) { - HeapRegionNode n = i.next(); + 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"; - } - } + AllocSite as = n.getAllocSite(); + if (as == null) { + out += " " + n.toString() + ",\n"; + } else { + out += " " + n.toString() + ": " + as.toStringVerbose() + + ",\n"; + } + } - out += "}\n"; - return out; - } + out += "}\n"; + return out; + } // use the methods given above to check every possible sharing class // between task parameters and flagged allocation sites reachable @@ -308,6 +344,8 @@ public class DisjointAnalysis { // /////////////////////////////////////////// + + protected void checkAnalysisComplete() { if( !analysisComplete ) { throw new Error("Warning: public interface method called while analysis is running."); @@ -315,6 +353,10 @@ public class DisjointAnalysis { } + + + + // run in faster mode, only when bugs wrung out! public static boolean releaseMode; diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index f9fc18c8..09389674 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -4619,6 +4619,24 @@ public class ReachGraph { + public boolean mayBothReachTarget( AllocSite asRoot1, + AllocSite asRoot2, + AllocSite asTarget ) { + + return false; + } + + + public boolean mayManyReachTarget( AllocSite asRoot, + AllocSite asTarget ) { + + return false; + } + + + + + public Set findCommonReachableNodes( ReachSet proofOfSharing ) { Set exhibitProofState = -- 2.34.1