From 7034316ea7bcf724d2b34584b4cf2fa1d7c5dad3 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 10 Mar 2011 22:12:05 +0000 Subject: [PATCH] state machines for traverers seem to be working for small examples --- .../Analysis/Disjoint/BuildStateMachines.java | 23 +++++++++ Robust/src/Analysis/Disjoint/Canonical.java | 48 +++++++++++++++++++ .../Analysis/Disjoint/DisjointAnalysis.java | 15 +++--- Robust/src/Analysis/Disjoint/ReachGraph.java | 30 ++++++++++-- Robust/src/Analysis/Disjoint/SMFEState.java | 1 + .../Disjoint/StateMachineForEffects.java | 6 +-- Robust/src/Tests/dfj/case3/test.java | 6 ++- 7 files changed, 114 insertions(+), 15 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/BuildStateMachines.java b/Robust/src/Analysis/Disjoint/BuildStateMachines.java index e0d6e2ef..d7e404f2 100644 --- a/Robust/src/Analysis/Disjoint/BuildStateMachines.java +++ b/Robust/src/Analysis/Disjoint/BuildStateMachines.java @@ -20,6 +20,8 @@ import IR.Flat.*; public class BuildStateMachines { + // map a task or stall site (both a FlatNode) to a variable + // and then finally to a state machine protected Hashtable< FlatNode, Hashtable > fn2var2smfe; @@ -77,4 +79,25 @@ public class BuildStateMachines { e ); } } + + + public void writeStateMachines() { + + Iterator fnItr = fn2var2smfe.keySet().iterator(); + while( fnItr.hasNext() ) { + FlatNode fn = fnItr.next(); + + Hashtable + var2smfe = fn2var2smfe.get( fn ); + + Iterator varItr = var2smfe.keySet().iterator(); + while( varItr.hasNext() ) { + TempDescriptor var = varItr.next(); + + StateMachineForEffects smfe = var2smfe.get( var ); + + smfe.writeAsDOT( "statemachine_"+fn.toString()+var.toString() ); + } + } + } } diff --git a/Robust/src/Analysis/Disjoint/Canonical.java b/Robust/src/Analysis/Disjoint/Canonical.java index 456b9dfe..633b96e3 100644 --- a/Robust/src/Analysis/Disjoint/Canonical.java +++ b/Robust/src/Analysis/Disjoint/Canonical.java @@ -1572,4 +1572,52 @@ abstract public class Canonical { op2result.put( op, out ); return out; } + + + + // BOO, HISS! FlatNode operand does NOT extend + // Canonical, so we can't cache this op by its + // canonical arguments--THINK ABOUT A BETTER WAY! + public static Taint changeWhereDefined( Taint t, + FlatNode pp ) { + assert t != null; + assert t.isCanonical(); + + // never a cached result... + Taint out = new Taint( t.sese, + t.stallSite, + t.var, + t.allocSite, + pp, + t.preds + ); + + out = (Taint) makeCanonical( out ); + //op2result.put( op, out ); CRY CRY + return out; + } + + // BOO, HISS! FlatNode operand does NOT extend + // Canonical, so we can't cache this op by its + // canonical arguments--THINK ABOUT A BETTER WAY! + public static TaintSet changeWhereDefined( TaintSet ts, + FlatNode pp ) { + assert ts != null; + assert ts.isCanonical(); + + // never a cached result... + TaintSet out = TaintSet.factory(); + Iterator itr = ts.iterator(); + while( itr.hasNext() ) { + Taint t = itr.next(); + out = Canonical.add( out, + Canonical.changeWhereDefined( t, pp ) + ); + } + + out = (TaintSet) makeCanonical( out ); + //op2result.put( op, out ); CRY CRY + return out; + } + } diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index de09d5ec..5e107d37 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -730,7 +730,6 @@ public class DisjointAnalysis { analysisComplete=true; - double timeEndAnalysis = (double) System.nanoTime(); double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) ); @@ -772,10 +771,14 @@ public class DisjointAnalysis { ); } } + + if( state.RCR ) { + buildStateMachines.writeStateMachines(); + } + } catch( IOException e ) { throw new Error( "IO Exception while writing disjointness analysis output." ); } - } @@ -1250,7 +1253,7 @@ public class DisjointAnalysis { if( shouldAnalysisTrack( fld.getType() ) ) { // transfer func - rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld ); + rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld, fn ); } // after transfer, use updated graph to @@ -1292,7 +1295,7 @@ public class DisjointAnalysis { if( shouldAnalysisTrack( fld.getType() ) ) { // transfer func - strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs ); + strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs, fn ); } // use transformed graph to do effects analysis @@ -1331,7 +1334,7 @@ public class DisjointAnalysis { if( shouldAnalysisTrack( lhs.getType() ) ) { // transfer func - rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement ); + rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement, fn ); } // use transformed graph to do effects analysis @@ -1377,7 +1380,7 @@ public class DisjointAnalysis { // transfer func, BUT // skip this node if it cannot create new reachability paths if( !arrayReferencees.doesNotCreateNewReaching( fsen ) ) { - rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs ); + rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs, fn ); } } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index d296bf24..b17b3f01 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -443,7 +443,10 @@ public class ReachGraph { public void assignTempXEqualToTempYFieldF( TempDescriptor x, TempDescriptor y, - FieldDescriptor f ) { + FieldDescriptor f, + FlatNode currentProgramPoint + ) { + VariableNode lnX = getVariableNodeFromTemp( x ); VariableNode lnY = getVariableNodeFromTemp( y ); @@ -484,6 +487,15 @@ public class ReachGraph { mostSpecificType( edgeHrn.getType(), hrnHrn.getType() ); + + TaintSet taints = Canonical.unionORpreds( edgeHrn.getTaints(), + edgeY.getTaints() + ); + if( state.RCR ) { + // the DFJ way to generate taints changes for field statements + taints = Canonical.changeWhereDefined( taints, + currentProgramPoint ); + } RefEdge edgeNew = new RefEdge( lnX, hrnHrn, @@ -491,7 +503,7 @@ public class ReachGraph { null, Canonical.intersection( betaY, betaHrn ), predsTrue, - Canonical.unionORpreds(edgeHrn.getTaints(),edgeY.getTaints()) + taints ); addEdgeOrMergeWithExisting( edgeNew ); @@ -518,7 +530,9 @@ public class ReachGraph { // return whether a strong update was actually effected public boolean assignTempXFieldFEqualToTempY( TempDescriptor x, FieldDescriptor f, - TempDescriptor y ) { + TempDescriptor y, + FlatNode currentProgramPoint + ) { VariableNode lnX = getVariableNodeFromTemp( x ); VariableNode lnY = getVariableNodeFromTemp( y ); @@ -646,6 +660,14 @@ public class ReachGraph { hrnY.getType() ); + TaintSet taints = edgeY.getTaints(); + + if( state.RCR ) { + // the DFJ way to generate taints changes for field statements + taints = Canonical.changeWhereDefined( taints, + currentProgramPoint ); + } + RefEdge edgeNew = new RefEdge( hrnX, hrnY, @@ -658,7 +680,7 @@ public class ReachGraph { predsTrue ), predsTrue, - edgeY.getTaints() + taints ); addEdgeOrMergeWithExisting( edgeNew ); diff --git a/Robust/src/Analysis/Disjoint/SMFEState.java b/Robust/src/Analysis/Disjoint/SMFEState.java index fee844d0..96753398 100644 --- a/Robust/src/Analysis/Disjoint/SMFEState.java +++ b/Robust/src/Analysis/Disjoint/SMFEState.java @@ -49,6 +49,7 @@ public class SMFEState { Set states = e2states.get( effect ); if( states == null ) { states = new HashSet(); + e2states.put( effect, states ); } states.add( stateTo ); } diff --git a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java index 69abb040..f12aa2d6 100644 --- a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java +++ b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java @@ -33,7 +33,6 @@ public class StateMachineForEffects { public void addEffect( FlatNode fnState, Effect e ) { - assert fn2state.containsKey( fnState ); SMFEState state = getState( fnState ); state.addEffect( e ); } @@ -58,13 +57,14 @@ public class StateMachineForEffects { SMFEState state = fn2state.get( fn ); if( state == null ) { state = new SMFEState( fn ); + fn2state.put( fn, state ); } return state; } - public void writeAsDOT() { - String graphName = initialState.getID().toString(); + public void writeAsDOT( String graphName ) { + //String graphName = initialState.getID().toString(); graphName = graphName.replaceAll( "[\\W]", "" ); try { diff --git a/Robust/src/Tests/dfj/case3/test.java b/Robust/src/Tests/dfj/case3/test.java index aabeb91f..f6682533 100644 --- a/Robust/src/Tests/dfj/case3/test.java +++ b/Robust/src/Tests/dfj/case3/test.java @@ -28,12 +28,12 @@ public class Test { t.f = a; } - genreach p1; - rblock T { Foo x = a.f; Foo y = x.f; y.z = 1; + + genreach pT; } rblock S { @@ -42,6 +42,8 @@ public class Test { w = w.f; } w.z = 5; + + genreach pS; } int total = 0; -- 2.34.1