From b3257da7e5732960d4824df4336d69dd8b4d8669 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Sat, 26 Mar 2011 20:28:00 +0000 Subject: [PATCH] changes --- .../Disjoint/ProcessStateMachines.java | 156 ++++++++++++++++-- Robust/src/Analysis/Disjoint/SMFEState.java | 6 +- 2 files changed, 146 insertions(+), 16 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/ProcessStateMachines.java b/Robust/src/Analysis/Disjoint/ProcessStateMachines.java index 03873c2f..718c60df 100644 --- a/Robust/src/Analysis/Disjoint/ProcessStateMachines.java +++ b/Robust/src/Analysis/Disjoint/ProcessStateMachines.java @@ -11,7 +11,6 @@ public class ProcessStateMachines { protected BuildStateMachines bsm; protected RBlockRelationAnalysis taskAnalysis; - public ProcessStateMachines(BuildStateMachines bsm, RBlockRelationAnalysis taskAnalysis) { this.bsm=bsm; this.taskAnalysis=taskAnalysis; @@ -22,8 +21,123 @@ public class ProcessStateMachines { groupStateMachines(); computeConflictEffects(); prune(); + merge(); + } + + private void merge() { + for(Pair machinepair: bsm.getAllMachineNames()) { + StateMachineForEffects sm=bsm.getStateMachine(machinepair); + merge(sm); + } + } + + + private void merge(StateMachineForEffects sm) { + HashMap>> backMap=buildBackMap(sm); + boolean mergeAgain=false; + do { + mergeAgain=false; + HashMap, Set> revMap=buildReverse(backMap); + for(Map.Entry, Set> entry:revMap.entrySet()) { + if (entry.getValue().size()>1) { + SMFEState first=null; + for(SMFEState state:entry.getValue()) { + if (first==null) { + first=state; + } else { + mergeAgain=true; + System.out.println("MERGING:"+first+" and "+state); + //Make sure we don't merge the initial state someplace else + if (state==sm.initialState) { + state=first; + first=sm.initialState; + } + mergeTwoStates(first, state, backMap); + sm.fn2state.remove(state.whereDefined); + } + } + } + } + } while(mergeAgain); } + + private HashMap, Set> buildReverse(HashMap>> backMap) { + HashMap, Set> revMap=new HashMap, Set>(); + for(Map.Entry>>entry:backMap.entrySet()) { + SMFEState state=entry.getKey(); + for(Pair pair:entry.getValue()) { + if (!revMap.containsKey(pair)) + revMap.put(pair, new HashSet()); + revMap.get(pair).add(state); + } + } + return revMap; + } + + private void mergeTwoStates(SMFEState state1, SMFEState state2, HashMap>> backMap) { + //Merge effects and conflicts + state1.effects.addAll(state2.effects); + state1.conflicts.addAll(state2.conflicts); + + //fix up our backmap + backMap.get(state1).addAll(backMap.get(state2)); + + //merge outgoing transitions + for(Map.Entry> entry:state2.e2states.entrySet()) { + Effect e=entry.getKey(); + Set states=entry.getValue(); + if (state1.e2states.containsKey(e)) { + for(SMFEState statetoadd:states) { + if (!state1.e2states.get(e).add(statetoadd)) { + //already added...reduce reference count + statetoadd.refCount--; + } + } + } else { + state1.e2states.put(e, states); + } + Set states1=state1.e2states.get(e); + + //move now-self edges + if (states1.contains(state2)) { + states1.remove(state2); + states1.add(state1); + } + + //fix up the backmap of the edges we point to + for(SMFEState st:states1) { + HashSet> toRemove=new HashSet>(); + HashSet> toAdd=new HashSet>(); + for(Pair backpair:backMap.get(st)) { + if (backpair.getFirst()==state2) { + Pair newpair=new Pair(state1, backpair.getSecond()); + toRemove.add(backpair); + toAdd.add(newpair); + } + } + backMap.get(st).removeAll(toRemove); + backMap.get(st).addAll(toAdd); + } + } + + //Fix up our new incoming edges + for(Pair fromStatePair:backMap.get(state2)) { + SMFEState fromState=fromStatePair.getFirst(); + for(Map.Entry> fromEntry:fromState.e2states.entrySet()) { + Effect e=fromEntry.getKey(); + Set states=fromEntry.getValue(); + if (states.contains(state2)) { + states.remove(state2); + states.add(state1); + } + } + } + //Clear out unreachable state's backmap + backMap.remove(state2); + } + + private void prune() { for(Pair machinepair: bsm.getAllMachineNames()) { StateMachineForEffects sm=bsm.getStateMachine(machinepair); @@ -72,33 +186,49 @@ public class ProcessStateMachines { } } } + + private HashMap>> buildBackMap(StateMachineForEffects sm) { + return buildBackMap(sm, null); + } - - private Set buildConflictsAndMap(StateMachineForEffects sm) { - Set conflictStates=new HashSet(); - HashMap> backMap=new HashMap>(); + private HashMap>> buildBackMap(StateMachineForEffects sm, Set conflictStates) { Stack toprocess=new Stack(); + HashMap>> backMap=new HashMap>>(); toprocess.add(sm.initialState); - backMap.put(sm.initialState, new HashSet()); + backMap.put(sm.initialState, new HashSet>()); while(!toprocess.isEmpty()) { SMFEState state=toprocess.pop(); - if (!state.getConflicts().isEmpty()) + if (!state.getConflicts().isEmpty()&&conflictStates!=null) { conflictStates.add(state); - for(SMFEState stateout:state.transitionsTo()) { - if (!backMap.containsKey(stateout)) { - toprocess.add(stateout); - backMap.put(stateout, new HashSet()); + } + for(Effect e:state.getEffectsAllowed()) { + for(SMFEState stateout:state.transitionsTo(e)) { + if (!backMap.containsKey(stateout)) { + toprocess.add(stateout); + backMap.put(stateout, new HashSet>()); + } + Pair p=new Pair(state, e.getField()); + backMap.get(stateout).add(p); } - backMap.get(stateout).add(state); } } + return backMap; + } + + + private Set buildConflictsAndMap(StateMachineForEffects sm) { + Set conflictStates=new HashSet(); + HashMap>> backMap=buildBackMap(sm, conflictStates); + + Stack toprocess=new Stack(); Set canReachConflicts=new HashSet(); toprocess.addAll(conflictStates); canReachConflicts.addAll(conflictStates); while(!toprocess.isEmpty()) { SMFEState state=toprocess.pop(); - for(SMFEState instate:backMap.get(state)) { + for(Pair instatepair:backMap.get(state)) { + SMFEState instate=instatepair.getFirst(); if (!canReachConflicts.contains(instate)) { toprocess.add(instate); canReachConflicts.add(instate); diff --git a/Robust/src/Analysis/Disjoint/SMFEState.java b/Robust/src/Analysis/Disjoint/SMFEState.java index 2899d318..efbe690f 100644 --- a/Robust/src/Analysis/Disjoint/SMFEState.java +++ b/Robust/src/Analysis/Disjoint/SMFEState.java @@ -48,13 +48,13 @@ public class SMFEState { // code gen protected int refCount; - + protected FlatNode whereDefined; public SMFEState( FlatNode fnWhereDefined, int id ) { - this.id = id; this.iHashCode = fnWhereDefined.hashCode(); - + this.whereDefined=fnWhereDefined; + effects = new HashSet(); conflicts = new HashSet(); e2states = new Hashtable< Effect, Set >(); -- 2.34.1