From 5209160c963589ac52ff053e4fd8938b8778438e Mon Sep 17 00:00:00 2001 From: jjenista Date: Sat, 5 Mar 2011 00:02:19 +0000 Subject: [PATCH] more code for state machines in dfj traversers --- .../Analysis/Disjoint/BuildStateMachines.java | 80 +++++++++++++++++++ .../Analysis/Disjoint/DisjointAnalysis.java | 20 +++-- .../Analysis/Disjoint/EffectsAnalysis.java | 27 ++++--- Robust/src/Analysis/Disjoint/SMFEState.java | 17 ++-- .../Disjoint/StateMachineForEffects.java | 12 ++- 5 files changed, 131 insertions(+), 25 deletions(-) create mode 100644 Robust/src/Analysis/Disjoint/BuildStateMachines.java diff --git a/Robust/src/Analysis/Disjoint/BuildStateMachines.java b/Robust/src/Analysis/Disjoint/BuildStateMachines.java new file mode 100644 index 00000000..e0d6e2ef --- /dev/null +++ b/Robust/src/Analysis/Disjoint/BuildStateMachines.java @@ -0,0 +1,80 @@ +package Analysis.Disjoint; + +import java.util.*; +import java.io.*; + +import IR.*; +import IR.Flat.*; + +////////////////////////////////////////////// +// +// BuildStateMachines builds a state machine +// for every task/stall site and variable pair +// +// StateMachineForEffects describes an intial +// state and the effect transtions a DFJ +// traverser should make from the current state +// when searching for possible runtime conflicts. +// +////////////////////////////////////////////// + +public class BuildStateMachines { + + protected + Hashtable< FlatNode, Hashtable > + fn2var2smfe; + + public BuildStateMachines() { + fn2var2smfe = new + Hashtable< FlatNode, Hashtable >(); + } + + protected StateMachineForEffects getStateMachine( FlatNode fn, + TempDescriptor var ) { + + Hashtable var2smfe = fn2var2smfe.get( fn ); + if( var2smfe == null ) { + var2smfe = new Hashtable(); + fn2var2smfe.put( fn, var2smfe ); + } + + StateMachineForEffects smfe = var2smfe.get( var ); + if( smfe == null ) { + smfe = new StateMachineForEffects( fn ); + var2smfe.put( var, smfe ); + } + + return smfe; + } + + + + public void addToStateMachine( Taint t, + Effect e, + FlatNode currentProgramPoint ) { + + FlatNode taskOrStallSite; + if( t.isStallSiteTaint() ) { + taskOrStallSite = t.getStallSite(); + } else { + taskOrStallSite = t.getSESE(); + } + + TempDescriptor var = t.getVar(); + + StateMachineForEffects smfe = getStateMachine( taskOrStallSite, var ); + + FlatNode whereDefined = t.getWhereDefined(); + + smfe.addEffect( whereDefined, e ); + + // reads of pointers make a transition + if( e.getType() == Effect.read && + e.getField().getType().isPtr() ) { + + smfe.addTransition( whereDefined, + currentProgramPoint, + e ); + } + } +} diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 81ea411e..de09d5ec 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -390,6 +390,8 @@ public class DisjointAnalysis { protected boolean doEffectsAnalysis = false; protected EffectsAnalysis effectsAnalysis; + protected BuildStateMachines buildStateMachines; + // data structure for public interface private Hashtable< Descriptor, HashSet > @@ -662,6 +664,10 @@ public class DisjointAnalysis { effectsAnalysis = new EffectsAnalysis(); } + if( state.RCR ) { + buildStateMachines = new BuildStateMachines(); + } + this.allocationDepth = state.DISJOINTALLOCDEPTH; this.releaseMode = state.DISJOINTRELEASEMODE; this.determinismDesired = state.DISJOINTDETERMINISM; @@ -690,7 +696,6 @@ public class DisjointAnalysis { ReachGraph.typeUtil = typeUtil; ReachGraph.state = state; - ReachGraph.debugCallSiteVisitStartCapture = state.DISJOINTDEBUGCALLVISITTOSTART; @@ -703,6 +708,11 @@ public class DisjointAnalysis { ReachGraph.debugCallSiteVisitCounter = 0; // count visits from 1, is incremented before first visit + + EffectsAnalysis.state = state; + EffectsAnalysis.buildStateMachines = buildStateMachines; + + if( suppressOutput ) { System.out.println( "* Running disjoint reachability analysis with output suppressed! *" ); } @@ -1246,7 +1256,7 @@ public class DisjointAnalysis { // after transfer, use updated graph to // do effects analysis if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fld ); + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fld, fn ); } break; @@ -1287,7 +1297,7 @@ public class DisjointAnalysis { // use transformed graph to do effects analysis if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fld, strongUpdate ); + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fld, fn, strongUpdate ); } break; @@ -1326,7 +1336,7 @@ public class DisjointAnalysis { // use transformed graph to do effects analysis if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fdElement ); + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fdElement, fn ); } break; @@ -1373,7 +1383,7 @@ public class DisjointAnalysis { // use transformed graph to do effects analysis if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fdElement, + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fdElement, fn, false ); } break; diff --git a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java index 221f23ae..bb133116 100644 --- a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java +++ b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java @@ -4,12 +4,8 @@ import java.util.*; import java.util.Map.Entry; import java.io.*; -import IR.FieldDescriptor; -import IR.Flat.FlatCall; -import IR.Flat.FlatMethod; -import IR.Flat.FlatNode; -import IR.Flat.TempDescriptor; -import IR.Flat.FlatSESEEnterNode; +import IR.*; +import IR.Flat.*; ///////////////////////////////////////////// // @@ -39,6 +35,9 @@ public class EffectsAnalysis { private Hashtable> > sese2te; private Hashtable> > stallSite2te; + public static State state; + public static BuildStateMachines buildStateMachines; + public EffectsAnalysis() { taint2effects = new Hashtable>(); @@ -59,12 +58,16 @@ public class EffectsAnalysis { return taint2effects.entrySet().iterator(); } - protected void add(Taint t, Effect e) { + protected void add(Taint t, Effect e, FlatNode currentProgramPoint) { Taint tNoPreds = Canonical.changePredsTo( t, ReachGraph.predsEmpty ); + if( state.RCR ) { + buildStateMachines.addToStateMachine( t, e, currentProgramPoint ); + } + // add to the global bag Set effectSet = taint2effects.get(tNoPreds); if (effectSet == null) { @@ -121,7 +124,7 @@ public class EffectsAnalysis { - public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) { + public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld, FlatNode currentProgramPoint) { VariableNode vn = rg.td2vn.get(rhs); if( vn == null ) { @@ -136,12 +139,12 @@ public class EffectsAnalysis { for (Iterator taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) { Taint taint = taintSetIter.next(); - add(taint, effect); + add(taint, effect, currentProgramPoint); } } } - public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, boolean strongUpdate) { + public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, FlatNode currentProgramPoint, boolean strongUpdate) { VariableNode vn = rg.td2vn.get(lhs); if( vn == null ) { @@ -161,10 +164,10 @@ public class EffectsAnalysis { for (Iterator taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) { Taint taint = taintSetIter.next(); - add( taint, effect ); + add( taint, effect, currentProgramPoint ); if (strongUpdate) { - add( taint, effectSU ); + add( taint, effectSU, currentProgramPoint ); } } } diff --git a/Robust/src/Analysis/Disjoint/SMFEState.java b/Robust/src/Analysis/Disjoint/SMFEState.java index f427cd99..fee844d0 100644 --- a/Robust/src/Analysis/Disjoint/SMFEState.java +++ b/Robust/src/Analysis/Disjoint/SMFEState.java @@ -102,14 +102,19 @@ public class SMFEState { s += "\"];"; // then each transition is an edge - Iterator eItr = e2states.entrySet().iterator(); + Iterator eItr = e2states.keySet().iterator(); while( eItr.hasNext() ) { - Effect e = eItr.next(); - SMFEState state = e2states.get( e ); + Effect e = eItr.next(); + Set states = e2states.get( e ); - s += "\n "+ - id.nodeid+" -> "+state.id.nodeid+ - "[label=\""+e+"\"];" + Iterator sItr = states.iterator(); + while( sItr.hasNext() ) { + SMFEState state = sItr.next(); + + s += "\n "+ + id.nodeid+" -> "+state.id.nodeid+ + "[label=\""+e+"\"];"; + } } return s; diff --git a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java index 0becddb8..69abb040 100644 --- a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java +++ b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java @@ -30,6 +30,14 @@ public class StateMachineForEffects { initialState = getState( fnInitial ); } + public void addEffect( FlatNode fnState, + Effect e ) { + + assert fn2state.containsKey( fnState ); + SMFEState state = getState( fnState ); + state.addEffect( e ); + } + public void addTransition( FlatNode fnFrom, FlatNode fnTo, Effect e ) { @@ -49,7 +57,7 @@ public class StateMachineForEffects { protected SMFEState getState( FlatNode fn ) { SMFEState state = fn2state.get( fn ); if( state == null ) { - state = new SMFEState(); + state = new SMFEState( fn ); } return state; } @@ -65,7 +73,7 @@ public class StateMachineForEffects { bw.write( "digraph "+graphName+" {\n" ); - Iterator fnItr = fn2state.entrySet().iterator(); + Iterator fnItr = fn2state.keySet().iterator(); while( fnItr.hasNext() ) { SMFEState state = fn2state.get( fnItr.next() ); bw.write( state.toStringDOT()+"\n" ); -- 2.34.1