From 2a8167b3ca561eeba2eb74d8bc760c16773d1cb9 Mon Sep 17 00:00:00 2001 From: jjenista Date: Sat, 13 Mar 2010 18:16:13 +0000 Subject: [PATCH] a start on reachability, not fully functioning yet --- Robust/src/Analysis/Disjoint/AllocSite.java | 8 - Robust/src/Analysis/Disjoint/Canonical.java | 162 ++++++++++++++++-- Robust/src/Analysis/Disjoint/CanonicalOp.java | 2 + .../Analysis/Disjoint/DisjointAnalysis.java | 38 ++-- Robust/src/Analysis/Disjoint/ReachGraph.java | 41 +++-- Robust/src/Analysis/Disjoint/ReachState.java | 7 +- Robust/src/Analysis/Disjoint/ReachTuple.java | 44 +++-- 7 files changed, 237 insertions(+), 65 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/AllocSite.java b/Robust/src/Analysis/Disjoint/AllocSite.java index a4d8f349..f7b635da 100644 --- a/Robust/src/Analysis/Disjoint/AllocSite.java +++ b/Robust/src/Analysis/Disjoint/AllocSite.java @@ -31,19 +31,16 @@ public class AllocSite extends Canonical { public static final int AGE_in_I = 101; public static final int AGE_oldest = 102; public static final int AGE_summary = 103; - public static final int AGE_siteSummary = 200; public static final int SHADOWAGE_notInThisSite = -100; public static final int SHADOWAGE_in_I = -101; public static final int SHADOWAGE_oldest = -102; public static final int SHADOWAGE_summary = -103; - public static final int SHADOWAGE_siteSummary = -200; protected Integer id; protected int allocationDepth; protected Vector ithOldest; protected Integer summary; - protected Integer siteSummary; protected FlatNew flatNew; protected String disjointId; protected boolean flag; @@ -122,11 +119,6 @@ public class AllocSite extends Canonical { return -summary; } - public void setSiteSummary( Integer id ) { - assert id != null; - siteSummary = id; - } - public FlatNew getFlatNew() { return flatNew; } diff --git a/Robust/src/Analysis/Disjoint/Canonical.java b/Robust/src/Analysis/Disjoint/Canonical.java index 3ef81361..7c913fbc 100644 --- a/Robust/src/Analysis/Disjoint/Canonical.java +++ b/Robust/src/Analysis/Disjoint/Canonical.java @@ -34,7 +34,7 @@ abstract public class Canonical { - public static Canonical makeCanonical( Canonical c ) { + public static Canonical makeCanonical( Canonical c ) { if( canon.containsKey( c ) ) { return canon.get( c ); @@ -110,8 +110,9 @@ abstract public class Canonical { assert rt2 != null; assert rt1.isCanonical(); assert rt2.isCanonical(); - assert rt1.hrnID == rt2.hrnID; - assert rt1.isMultiObject == rt2.isMultiObject; + assert rt1.hrnID == rt2.hrnID; + assert rt1.isMultiObject == rt2.isMultiObject; + assert rt1.isOutOfContext == rt2.isOutOfContext; ReachTuple out; @@ -120,7 +121,8 @@ abstract public class Canonical { // ZERO-OR-MORE out = ReachTuple.factory( rt1.hrnID, true, - ReachTuple.ARITY_ZEROORMORE ); + ReachTuple.ARITY_ZEROORMORE, + rt1.isOutOfContext ); } else { // a single object region can only be ARITY_ONE (or zero by @@ -141,7 +143,8 @@ abstract public class Canonical { ReachTuple out = ReachTuple.factory( hrnIDToChangeTo, rt.isMultiObject, - rt.arity + rt.arity, + rt.isOutOfContext ); assert out.isCanonical(); return out; @@ -225,8 +228,9 @@ abstract public class Canonical { Iterator rtItr = rs1.iterator(); while( rtItr.hasNext() ) { ReachTuple rt1 = rtItr.next(); - ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID() ); - + ReachTuple rt2 = rs2.containsHrnID( rt1.getHrnID(), + rt1.isOutOfContext() + ); if( rt2 != null ) { out.reachTuples.add( unionArity( rt1, rt2 ) ); } else { @@ -237,8 +241,9 @@ abstract public class Canonical { rtItr = rs2.iterator(); while( rtItr.hasNext() ) { ReachTuple rt2 = rtItr.next(); - ReachTuple rto = out.containsHrnID( rt2.getHrnID() ); - + ReachTuple rto = out.containsHrnID( rt2.getHrnID(), + rt2.isOutOfContext() + ); if( rto == null ) { out.reachTuples.add( rto ); } @@ -308,8 +313,11 @@ abstract public class Canonical { int age = as.getAgeCategory( hrnID ); // hrnIDs not associated with - // the site should be left alone - if( age == AllocSite.AGE_notInThisSite ) { + // the site should be left alone, and + // those from this site but out-of-context + if( age == AllocSite.AGE_notInThisSite || + rt.isOutOfContext() + ) { out.reachTuples.add( rt ); } else if( age == AllocSite.AGE_summary ) { @@ -350,16 +358,18 @@ abstract public class Canonical { } else if( rtSummary == null && rtOldest != null ) { out.reachTuples.add( ReachTuple.factory( as.getSummary(), - true, - rtOldest.getArity() + true, // multi + rtOldest.getArity(), + false // out-of-context ) ); } else if( rtSummary != null && rtOldest != null ) { out.reachTuples.add( Canonical.unionArity( rtSummary, ReachTuple.factory( as.getSummary(), - true, - rtOldest.getArity() + true, // muli + rtOldest.getArity(), + false // out-of-context ) ) ); @@ -584,8 +594,9 @@ abstract public class Canonical { Iterator itrRelement = r.iterator(); while( itrRelement.hasNext() ) { ReachTuple rtR = itrRelement.next(); - ReachTuple rtO = o.containsHrnID( rtR.getHrnID() ); - + ReachTuple rtO = o.containsHrnID( rtR.getHrnID(), + rtR.isOutOfContext() + ); if( rtO != null ) { theUnion = Canonical.union( theUnion, Canonical.unionArity( rtR, @@ -602,8 +613,9 @@ abstract public class Canonical { Iterator itrOelement = o.iterator(); while( itrOelement.hasNext() ) { ReachTuple rtO = itrOelement.next(); - ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID() ); - + ReachTuple rtR = theUnion.containsHrnID( rtO.getHrnID(), + rtO.isOutOfContext() + ); if( rtR == null ) { theUnion = Canonical.union( theUnion, rtO @@ -818,6 +830,118 @@ abstract public class Canonical { op2result.put( op, out ); return out; } + + + + public static ReachSet toCalleeContext( ReachSet rs, + AllocSite as ) { + assert rs != null; + assert as != null; + assert rs.isCanonical(); + assert as.isCanonical(); + + CanonicalOp op = + new CanonicalOp( CanonicalOp.REACHSET_TOCALLEECONTEXT_ALLOCSITE, + rs, + as ); + + Canonical result = op2result.get( op ); + if( result != null ) { + return (ReachSet) result; + } + + // otherwise, no cached result... + ReachSet out = ReachSet.factory(); + Iterator itr = rs.iterator(); + while( itr.hasNext() ) { + ReachState state = itr.next(); + out = Canonical.add( out, + Canonical.toCalleeContext( state, as ) + ); + } + + assert out.isCanonical(); + op2result.put( op, out ); + return out; + } + + public static ReachState toCalleeContext( ReachState state, + AllocSite as ) { + assert state != null; + assert as != null; + assert state.isCanonical(); + assert as.isCanonical(); + + CanonicalOp op = + new CanonicalOp( CanonicalOp.REACHSTATE_TOCALLEECONTEXT_ALLOCSITE, + state, + as ); + + Canonical result = op2result.get( op ); + if( result != null ) { + return (ReachState) result; + } + + // otherwise, no cached result... + ReachState out = ReachState.factory(); + Iterator itr = state.iterator(); + while( itr.hasNext() ) { + ReachTuple rt = itr.next(); + + int age = as.getAgeCategory( rt.getHrnID() ); + + // this is the current mapping, where 0, 1, 2S were allocated + // in the current context, 0?, 1? and 2S? were allocated in a + // previous context, and we're translating to a future context + // + // 0 -> 0? + // 1 -> 1? + // 2S -> 2S? + // 2S* -> 2S?* + // + // 0? -> 2S? + // 1? -> 2S? + // 2S? -> 2S? + // 2S?* -> 2S?* + + if( age == AllocSite.AGE_notInThisSite ) { + // things not from the site just go back in + out = Canonical.union( out, rt ); + + } else if( age == AllocSite.AGE_summary || + rt.isOutOfContext() + ) { + // the in-context summary and all existing out-of-context + // stuff all become + out = Canonical.union( out, + ReachTuple.factory( as.getSummary(), + true, // multi + rt.getArity(), + true // out-of-context + ) + ); + } else { + // otherwise everything else just goes to an out-of-context + // version, everything else the same + Integer I = as.getAge( rt.getHrnID() ); + assert I != null; + + assert !rt.isMultiObject(); + + out = Canonical.union( out, + ReachTuple.factory( rt.getHrnID(), + rt.isMultiObject(), + rt.getArity(), + true // out-of-context + ) + ); + } + } + + assert out.isCanonical(); + op2result.put( op, out ); + return out; + } } diff --git a/Robust/src/Analysis/Disjoint/CanonicalOp.java b/Robust/src/Analysis/Disjoint/CanonicalOp.java index 6cccb4b5..b9e8a155 100644 --- a/Robust/src/Analysis/Disjoint/CanonicalOp.java +++ b/Robust/src/Analysis/Disjoint/CanonicalOp.java @@ -27,6 +27,8 @@ public class CanonicalOp { public static final int EXISTPREDSET_JOIN_EXISTPREDSET = 0x8a21; public static final int EXISTPREDSET_ADD_EXISTPRED = 0xba5f; public static final int PRIM_OP_UNUSED = 0xef01; + public static final int REACHSET_TOCALLEECONTEXT_ALLOCSITE = 0x56f6; + public static final int REACHSTATE_TOCALLEECONTEXT_ALLOCSITE = 0x7faf; protected int opCode; protected Canonical operand1; diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 4c8e0915..7f0d7ea6 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -349,15 +349,19 @@ public class DisjointAnalysis { } } + if( takeDebugSnapshots && + d.getSymbol().equals( descSymbolDebug ) + ) { + debugSnapshot( rg, fn, true ); + } + // modify rg with appropriate transfer function rg = analyzeFlatNode( d, fm, fn, setReturns, rg ); - - if( takeDebugSnapshots && d.getSymbol().equals( descSymbolDebug ) ) { - debugSnapshot( rg, fn ); + debugSnapshot( rg, fn, false ); } @@ -751,10 +755,6 @@ public class DisjointAnalysis { // the oldest node is a summary node as.setSummary( generateUniqueHeapRegionNodeID() ); - // and one special node is older than all - // nodes and shadow nodes for the site - as.setSiteSummary( generateUniqueHeapRegionNodeID() ); - mapFlatNewToAllocSite.put( fnew, as ); } @@ -1176,6 +1176,11 @@ public class DisjointAnalysis { + + + int zzz = 0; + + // get successive captures of the analysis state @@ -1199,12 +1204,15 @@ public class DisjointAnalysis { // the number of snapshots to take int numIterToCapture = 300; - void debugSnapshot( ReachGraph rg, FlatNode fn ) { + void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) { if( debugCounter > iterStartCapture + numIterToCapture ) { return; } - ++debugCounter; + if( in ) { + ++debugCounter; + } + if( debugCounter > numStartCountReport && freqCountReport > 0 && debugCounter % freqCountReport == 0 @@ -1212,13 +1220,19 @@ public class DisjointAnalysis { System.out.println( " @@@ debug counter = "+ debugCounter ); } + if( debugCounter > iterStartCapture ) { System.out.println( " @@@ capturing debug "+ (debugCounter - iterStartCapture)+ " @@@" ); - String graphName = - String.format( "snap%04d", - debugCounter - iterStartCapture ); + String graphName; + if( in ) { + graphName = String.format( "snap%04din", + debugCounter - iterStartCapture ); + } else { + graphName = String.format( "snap%04dout", + debugCounter - iterStartCapture ); + } if( fn != null ) { graphName = graphName + fn; } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 04f3197f..ff811bc4 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -125,7 +125,8 @@ public class ReachGraph { ReachState.factory( ReachTuple.factory( id, !isSingleObject, - ReachTuple.ARITY_ONE + ReachTuple.ARITY_ONE, + false // out-of-context ) ) ); @@ -1277,6 +1278,19 @@ public class ReachGraph { return null; } + // used below to convert a ReachSet to its callee-context + // equivalent with respect to allocation sites in this graph + protected ReachSet toCalleeContext( ReachSet rs ) { + ReachSet out = rs; + Iterator asItr = allocSites.iterator(); + while( asItr.hasNext() ) { + AllocSite as = asItr.next(); + out = Canonical.toCalleeContext( out, as ); + } + assert out.isCanonical(); + return out; + } + // use this method to make a new reach graph that is // what heap the FlatMethod callee from the FlatCall @@ -1374,8 +1388,8 @@ public class ReachGraph { false, // out-of-context? hrnSrcCaller.getType(), hrnSrcCaller.getAllocSite(), - /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/, - /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/, + toCalleeContext( hrnSrcCaller.getInherent() ), + toCalleeContext( hrnSrcCaller.getAlpha() ), preds, hrnSrcCaller.getDescription() ); @@ -1414,8 +1428,8 @@ public class ReachGraph { false, // out-of-context? hrnCaller.getType(), hrnCaller.getAllocSite(), - /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/, - /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/, + toCalleeContext( hrnCaller.getInherent() ), + toCalleeContext( hrnCaller.getAlpha() ), preds, hrnCaller.getDescription() ); @@ -1451,7 +1465,7 @@ public class ReachGraph { hrnCallee, reCaller.getType(), reCaller.getField(), - /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/, + toCalleeContext( reCaller.getBeta() ), preds ) ); @@ -1568,8 +1582,8 @@ public class ReachGraph { true, // out-of-context? oocNodeType, null, // alloc site, shouldn't be used - /*toShadowTokens( this,*/ oocReach /*)*/, // inherent - /*toShadowTokens( this,*/ oocReach /*)*/, // alpha + toCalleeContext( oocReach ), // inherent + toCalleeContext( oocReach ), // alpha preds, "out-of-context" ); @@ -1591,8 +1605,8 @@ public class ReachGraph { true, // out-of-context? oocNodeType, null, // alloc site, shouldn't be used - /*toShadowTokens( this,*/ oocReach /*)*/, // inherent - /*toShadowTokens( this,*/ oocReach /*)*/, // alpha + toCalleeContext( oocReach ), // inherent + toCalleeContext( oocReach ), // alpha preds, "out-of-context" ); @@ -1605,7 +1619,7 @@ public class ReachGraph { hrnCalleeAndInContext, edgeMightCross.getType(), edgeMightCross.getField(), - /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/, + toCalleeContext( edgeMightCross.getBeta() ), preds ) ); @@ -1613,7 +1627,7 @@ public class ReachGraph { } else { // the out-of-context edge already exists oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(), - edgeMightCross.getBeta() + toCalleeContext( edgeMightCross.getBeta() ) ) ); @@ -2464,7 +2478,8 @@ public class ReachGraph { ReachTuple rtException = ReachTuple.factory( hrnID, !hrn.isSingleObject(), - ReachTuple.ARITY_ONE + ReachTuple.ARITY_ONE, + false // out-of-context ); ChangeSet cts = ChangeSet.factory(); diff --git a/Robust/src/Analysis/Disjoint/ReachState.java b/Robust/src/Analysis/Disjoint/ReachState.java index 22e7e79b..aa175561 100644 --- a/Robust/src/Analysis/Disjoint/ReachState.java +++ b/Robust/src/Analysis/Disjoint/ReachState.java @@ -71,13 +71,16 @@ public class ReachState extends Canonical { } // this should be a hash table so we can do this by key - public ReachTuple containsHrnID( Integer hrnID ) { + public ReachTuple containsHrnID( Integer hrnID, + boolean isOutOfContext ) { assert hrnID != null; Iterator rtItr = reachTuples.iterator(); while( rtItr.hasNext() ) { ReachTuple rt = rtItr.next(); - if( hrnID.equals( rt.getHrnID() ) ) { + if( hrnID.equals( rt.getHrnID() ) && + isOutOfContext == rt.isOutOfContext() + ) { return rt; } } diff --git a/Robust/src/Analysis/Disjoint/ReachTuple.java b/Robust/src/Analysis/Disjoint/ReachTuple.java index 70982d32..1d09abfa 100644 --- a/Robust/src/Analysis/Disjoint/ReachTuple.java +++ b/Robust/src/Analysis/Disjoint/ReachTuple.java @@ -39,13 +39,19 @@ public class ReachTuple extends Canonical { public static final int ARITY_ONEORMORE = 2; protected int arity; + // whether this represents heap regions out + // of the current calling context or not + protected boolean isOutOfContext; + public static ReachTuple factory( Integer hrnID, boolean isMultiObject, - int arity ) { + int arity, + boolean ooc ) { ReachTuple out = new ReachTuple( hrnID, isMultiObject, - arity ); + arity, + ooc ); out = (ReachTuple) Canonical.makeCanonical( out ); return out; } @@ -53,19 +59,22 @@ public class ReachTuple extends Canonical { public static ReachTuple factory( HeapRegionNode hrn ) { ReachTuple out = new ReachTuple( hrn.getID(), !hrn.isSingleObject(), - ARITY_ONE ); + ARITY_ONE, + false ); out = (ReachTuple) Canonical.makeCanonical( out ); return out; } protected ReachTuple( Integer hrnID, boolean isMultiObject, - int arity ) { + int arity, + boolean ooc ) { assert hrnID != null; - this.hrnID = hrnID; - this.isMultiObject = isMultiObject; - this.arity = arity; + this.hrnID = hrnID; + this.isMultiObject = isMultiObject; + this.arity = arity; + this.isOutOfContext = ooc; // just make sure this stuff is true now // that analysis doesn't use ONEORMORE @@ -88,6 +97,10 @@ public class ReachTuple extends Canonical { return arity; } + public boolean isOutOfContext() { + return isOutOfContext; + } + public boolean equals( Object o ) { if( o == null ) { @@ -99,13 +112,18 @@ public class ReachTuple extends Canonical { } ReachTuple rt = (ReachTuple) o; - return - hrnID.equals( rt.hrnID ) && - arity == rt.arity; + + return hrnID.equals( rt.hrnID ) && + arity == rt.arity && + isOutOfContext == rt.isOutOfContext; } public int hashCodeSpecific() { - return (hrnID.intValue() << 2) ^ arity; + int hash = (hrnID.intValue() << 2) ^ arity; + if( isOutOfContext ) { + hash = ~hash; + } + return hash; } @@ -116,6 +134,10 @@ public class ReachTuple extends Canonical { s += "M"; } + if( isOutOfContext ) { + s += "?"; + } + if( arity == ARITY_ZEROORMORE ) { s += "*"; } else if( arity == ARITY_ONEORMORE ) { -- 2.34.1