From fff59443c5ca22bcb37074c9cf1d65cc8e0c6b1f Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 25 Mar 2011 00:10:05 +0000 Subject: [PATCH] changes to process/prune state machines --- .../Analysis/Disjoint/BuildStateMachines.java | 13 ++++---- Robust/src/Analysis/Disjoint/Effect.java | 6 +++- Robust/src/Analysis/Disjoint/SMFEState.java | 21 ++++++++++--- .../Disjoint/StateMachineForEffects.java | 29 ++++++++++++++--- .../src/Analysis/OoOJava/ConflictGraph.java | 25 --------------- .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 31 ++----------------- .../OoOJava/RBlockRelationAnalysis.java | 4 +-- 7 files changed, 57 insertions(+), 72 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/BuildStateMachines.java b/Robust/src/Analysis/Disjoint/BuildStateMachines.java index 9360226b..525b58c1 100644 --- a/Robust/src/Analysis/Disjoint/BuildStateMachines.java +++ b/Robust/src/Analysis/Disjoint/BuildStateMachines.java @@ -31,16 +31,19 @@ public class BuildStateMachines { // remember all the FlatNode/TempDescriptor pairs that have a state machines // for easy retrieval of all machines - protected Set allMachineNamePairs; + protected Set> allMachineNamePairs; public BuildStateMachines() { fn2var2smfe = new Hashtable< FlatNode, Hashtable >(); - allMachineNamePairs = new HashSet(); + allMachineNamePairs = new HashSet>(); } + public StateMachineForEffects getStateMachine(Pair fnpair) { + return getStateMachine(fnpair.getFirst(), fnpair.getSecond()); + } public StateMachineForEffects getStateMachine( FlatNode fn, TempDescriptor var ) { @@ -56,14 +59,14 @@ public class BuildStateMachines { smfe = new StateMachineForEffects( fn ); var2smfe.put( var, smfe ); - allMachineNamePairs.add( new Pair( fn, var ) ); + allMachineNamePairs.add( new Pair( fn, var ) ); } return smfe; } - public Set getAllMachineNames() { + public Set> getAllMachineNames() { return allMachineNamePairs; } @@ -118,8 +121,6 @@ public class BuildStateMachines { } } } - - //TODO JIM! Give me the REAALL number here. public int getTotalNumOfWeakGroups() { // TODO Auto-generated method stub diff --git a/Robust/src/Analysis/Disjoint/Effect.java b/Robust/src/Analysis/Disjoint/Effect.java index 5e59e005..fe07ebcc 100644 --- a/Robust/src/Analysis/Disjoint/Effect.java +++ b/Robust/src/Analysis/Disjoint/Effect.java @@ -8,7 +8,7 @@ public class Effect { // operation type public static final int read = 1; public static final int write = 2; - public static final int strongupdate = 3; + public static final int strongupdate = 4; // identify an allocation site of affected object protected Alloc affectedAllocSite; @@ -25,6 +25,10 @@ public class Effect { this.field = field; } + public static boolean isWrite(int effect) { + return (effect & Effect.write)==Effect.write; + } + public Alloc getAffectedAllocSite() { return affectedAllocSite; } diff --git a/Robust/src/Analysis/Disjoint/SMFEState.java b/Robust/src/Analysis/Disjoint/SMFEState.java index 2250d05d..dbb793da 100644 --- a/Robust/src/Analysis/Disjoint/SMFEState.java +++ b/Robust/src/Analysis/Disjoint/SMFEState.java @@ -76,8 +76,7 @@ public class SMFEState { e2states.put( effect, states ); } states.add( stateTo ); - - ++stateTo.refCount; + stateTo.refCount++; } @@ -92,10 +91,12 @@ public class SMFEState { return effects; } + public void addConflict(Effect e) { + conflicts.add(e); + } + public Set getConflicts() { - //TODO JIM! Fix this when have a chance! - conflicts.addAll(effects); - return this.conflicts; + return conflicts; } public Set getTransistionEffects() { @@ -112,6 +113,16 @@ public class SMFEState { return statesOut; } + // some subset of the above effects may transition to + // other states + public Set transitionsTo() { + Set statesOut = new HashSet(); + for(Map.Entry> entry:e2states.entrySet()) { + statesOut.addAll(entry.getValue()); + } + return statesOut; + } + public int getRefCount() { return refCount; } diff --git a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java index af0c6e9a..360a1d28 100644 --- a/Robust/src/Analysis/Disjoint/StateMachineForEffects.java +++ b/Robust/src/Analysis/Disjoint/StateMachineForEffects.java @@ -5,6 +5,7 @@ import java.io.*; import IR.*; import IR.Flat.*; +import Util.Pair; ////////////////////////////////////////////// // @@ -17,6 +18,7 @@ import IR.Flat.*; public class StateMachineForEffects { public final static FlatNode startNode=new FlatNop(); + protected HashMap, Integer> effectsMap; // states in the machine are uniquely identified // by a flat node (program point) @@ -26,21 +28,41 @@ public class StateMachineForEffects { protected Hashtable fn2weaklyConnectedGroupID; protected SMFEState initialState; - + protected FlatNode fn; public StateMachineForEffects( FlatNode fnInitial ) { fn2state = new Hashtable(); - + effectsMap = new HashMap, Integer>(); initialState = getState( fnInitial ); + this.fn=fnInitial; + } + + public Set getStates() { + HashSet set=new HashSet(); + set.addAll(fn2state.values()); + return set; + } + + public FlatNode getStallorSESE() { + return fn; + } + + public int getEffects(Alloc affectedNode, FieldDescriptor fd) { + return effectsMap.get(new Pair(affectedNode, fd)).intValue(); } public void addEffect( FlatNode fnState, Effect e ) { - if (fnState==null) fnState=startNode; SMFEState state = getState( fnState ); state.addEffect( e ); + Pair p=new Pair(e.getAffectedAllocSite(), e.getField()); + int type=e.getType(); + if (!effectsMap.containsKey(p)) + effectsMap.put(p, new Integer(type)); + else + effectsMap.put(p, new Integer(type|effectsMap.get(p).intValue())); } public void addTransition( FlatNode fnFrom, @@ -75,7 +97,6 @@ public class StateMachineForEffects { return 0; } - public void writeAsDOT( String graphName ) { //String graphName = initialState.getID().toString(); graphName = graphName.replaceAll( "[\\W]", "" ); diff --git a/Robust/src/Analysis/OoOJava/ConflictGraph.java b/Robust/src/Analysis/OoOJava/ConflictGraph.java index ac14cf4c..d8e72529 100644 --- a/Robust/src/Analysis/OoOJava/ConflictGraph.java +++ b/Robust/src/Analysis/OoOJava/ConflictGraph.java @@ -29,8 +29,6 @@ public class ConflictGraph { protected Hashtable id2cn; protected Hashtable>> sese2te; - protected HashMap, Integer> seseEffects; - protected HashMap, Integer> stallEffects; protected DisjointAnalysis da; protected FlatMethod fmEnclosing; @@ -45,16 +43,6 @@ public class ConflictGraph { this.state=state; id2cn = new Hashtable(); sese2te = new Hashtable>>(); - seseEffects = new HashMap, Integer>(); - stallEffects = new HashMap, Integer>(); - } - - public int getStallEffects(Alloc affectedNode, FieldDescriptor fd) { - return stallEffects.get(new Pair(affectedNode, fd)).intValue(); - } - - public int getSESEEffects(Alloc affectedNode, FieldDescriptor fd) { - return seseEffects.get(new Pair(affectedNode, fd)).intValue(); } public void setDisJointAnalysis(DisjointAnalysis da) { @@ -118,13 +106,6 @@ public class ConflictGraph { node.addEffect(as, e); node.addTaint(t); id2cn.put(id, node); - - Pair p=new Pair(e.getAffectedAllocSite(), e.getField()); - int type=e.getType(); - if (!stallEffects.containsKey(p)) - stallEffects.put(p, new Integer(type)); - else - stallEffects.put(p, new Integer(type|stallEffects.get(p).intValue())); } public void addLiveInNodeEffect(Taint t, Effect e) { @@ -143,12 +124,6 @@ public class ConflictGraph { id2cn.put(id, node); - Pair p=new Pair(e.getAffectedAllocSite(), e.getField()); - int type=e.getType(); - if (!seseEffects.containsKey(p)) - seseEffects.put(p, new Integer(type)); - else - seseEffects.put(p, new Integer(type|seseEffects.get(p).intValue())); } public void addConflictEdge(int type, ConflictNode nodeU, ConflictNode nodeV) { diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index 3162ab22..db55e6f7 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -10,7 +10,6 @@ import Analysis.Pointer.*; import IR.*; import IR.Flat.*; - public class OoOJavaAnalysis { // data from the compiler @@ -1288,34 +1287,8 @@ public class OoOJavaAnalysis { // effects between heap roots, so it is smart to compute all of // this together public void pruneMachinesAndFindWeaklyConnectedExaminers() { - - /* - // TODO, calcualte the set of taints that lead to conflicts (for which - // traversers must be built...) - - EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis(); - - // visit every conflict graph once, so iterate through the - // the non-leaf tasks to find them all - Set allSESEs = rblockRel.getAllSESEs(); - for( Iterator allItr = allSESEs.iterator(); allItr.hasNext(); ) { - - FlatSESEEnterNode parent = (FlatSESEEnterNode) allItr.next(); - if( parent.getIsLeafSESE() ) { - continue; - } - - ConflictGraph conflictGraph = sese2conflictGraph.get( parent ); - assert conflictGraph != null; - - // from the conflict graph we want to extract all conflicting effects - // and use them to identify (1) weakly connected heap examiners and - // (2) states/examiner nodes with a conflicting effect that will later - // support the examiner pruning process - Hashtable> conflicts = conflictGraph.getConflictEffectSet( fsen ) ); - - } - */ + ProcessStateMachines psm=new ProcessStateMachines(buildStateMachines, rblockRel); + psm.doProcess(); } diff --git a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java index 951e4cd8..080203c4 100644 --- a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java +++ b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java @@ -89,8 +89,8 @@ public class RBlockRelationAnalysis { // node it will be in this set protected Hashtable< FlatNode, Set > fn2currentSESEs; - // if you want to know which rblocks might be executing a given flat - // node it will be in this set + // if you want to know which rblocks might be TRANSITIVELY executing + // a given flat node it will be in this set protected Hashtable< FlatNode, Set > fn2allSESEs; // if you want to know the method-local, inner-most nested task that -- 2.34.1