Robust/src/Analysis/Disjoint/ProcessStateMachines.java

   1 package Analysis.Disjoint;
   2 import java.util.*;
   3
   4 import Analysis.OoOJava.*;
   5 import IR.FieldDescriptor;
   6 import IR.Flat.*;
   7 import Util.Pair;
   8
   9 public class ProcessStateMachines {
  10   protected HashMap<FlatSESEEnterNode, Set<StateMachineForEffects>> groupMap;
  11   protected BuildStateMachines bsm;
  12   protected RBlockRelationAnalysis taskAnalysis;
  13
  14
  15   public ProcessStateMachines(BuildStateMachines bsm, RBlockRelationAnalysis taskAnalysis) {
  16     this.bsm=bsm;
  17     this.taskAnalysis=taskAnalysis;
  18   }
  19
  20   public void doProcess() {
  21     groupStateMachines();
  22     prune();
  23   }
  24
  25   private void prune() {
  26     for(Pair<FlatNode, TempDescriptor> machinepair: bsm.getAllMachineNames()) {
  27       StateMachineForEffects sm=bsm.getStateMachine(machinepair);
  28       pruneNonConflictingStates(sm);
  29       pruneEffects(sm);
  30     }
  31   }
  32
  33   private void pruneEffects(StateMachineForEffects sm) {
  34     for(Iterator<FlatNode> fnit=sm.fn2state.keySet().iterator(); fnit.hasNext();) {
  35       FlatNode fn=fnit.next();
  36       SMFEState state=sm.fn2state.get(fn);
  37       for(Iterator<Effect> efit=state.effects.iterator();efit.hasNext();) {
  38         Effect e=efit.next();
  39         //Is it a conflicting effecting
  40         if (state.getConflicts().contains(e))
  41           continue;
  42         //Does it still have transitions
  43         if (state.e2states.contains(e))
  44           continue;
  45         //If no to both, remove it
  46         efit.remove();
  47       }
  48     }
  49   }
  50
  51   private void pruneNonConflictingStates(StateMachineForEffects sm) {
  52     Set<SMFEState> canReachConflicts=buildConflictsAndMap(sm);
  53     for(Iterator<FlatNode> fnit=sm.fn2state.keySet().iterator(); fnit.hasNext();) {
  54       FlatNode fn=fnit.next();
  55       SMFEState state=sm.fn2state.get(fn);
  56       if (canReachConflicts.contains(state)) {
  57         for(Iterator<Effect> efit=state.e2states.keySet().iterator(); efit.hasNext();) {
  58           Effect e=efit.next();
  59           Set<SMFEState> stateset=state.e2states.get(e);
  60           for(Iterator<SMFEState> stit=stateset.iterator(); stit.hasNext();) {
  61             SMFEState tostate=stit.next();
  62             if(!canReachConflicts.contains(tostate))
  63               stit.remove();
  64           }
  65           if (stateset.isEmpty())
  66             efit.remove();
  67         }
  68       } else {
  69         fnit.remove();
  70       }
  71     }
  72   }
  73
  74
  75   private Set<SMFEState> buildConflictsAndMap(StateMachineForEffects sm) {
  76     Set<SMFEState> conflictStates=new HashSet<SMFEState>();
  77     HashMap<SMFEState, Set<SMFEState>> backMap=new HashMap<SMFEState, Set<SMFEState>>();
  78     Stack<SMFEState> toprocess=new Stack<SMFEState>();
  79     toprocess.add(sm.initialState);
  80     backMap.put(sm.initialState, new HashSet<SMFEState>());
  81     while(!toprocess.isEmpty()) {
  82       SMFEState state=toprocess.pop();
  83       if (!state.getConflicts().isEmpty())
  84         conflictStates.add(state);
  85       for(SMFEState stateout:state.transitionsTo()) {
  86         if (!backMap.containsKey(stateout)) {
  87           toprocess.add(stateout);
  88           backMap.put(stateout, new HashSet<SMFEState>());
  89         }
  90         backMap.get(stateout).add(state);
  91       }
  92     }
  93     Set<SMFEState> canReachConflicts=new HashSet<SMFEState>();
  94     toprocess.addAll(conflictStates);
  95     canReachConflicts.addAll(conflictStates);
  96     while(!toprocess.isEmpty()) {
  97       SMFEState state=toprocess.pop();
  98
  99       for(SMFEState instate:backMap.get(state)) {
 100         if (!canReachConflicts.contains(instate)) {
 101           toprocess.add(instate);
 102           canReachConflicts.add(instate);
 103         }
 104       }
 105     }
 106     return canReachConflicts;
 107   }
 108
 109   private void groupStateMachines() {
 110     for(Pair<FlatNode, TempDescriptor> machinePair: bsm.getAllMachineNames()) {
 111       FlatNode fn=machinePair.getFirst();
 112       StateMachineForEffects sm=bsm.getStateMachine(machinePair);
 113       Set<FlatSESEEnterNode> taskSet=taskAnalysis.getPossibleExecutingRBlocks(fn);
 114       for(FlatSESEEnterNode sese:taskSet) {
 115         if (!groupMap.containsKey(sese))
 116           groupMap.put(sese, new HashSet<StateMachineForEffects>());
 117         groupMap.get(sese).add(sm);
 118       }
 119     }
 120   }
 121
 122   private void computeConflictEffects() {
 123     //Loop through all state machines
 124     for(Pair<FlatNode, TempDescriptor> machinePair: bsm.getAllMachineNames()) {
 125       FlatNode fn=machinePair.getFirst();
 126       StateMachineForEffects sm=bsm.getStateMachine(machinePair);
 127       Set<FlatSESEEnterNode> taskSet=taskAnalysis.getPossibleExecutingRBlocks(fn);
 128       for(FlatSESEEnterNode sese:taskSet) {
 129         Set<StateMachineForEffects> smgroup=groupMap.get(sese);
 130         computeConflictingEffects(sm, smgroup);
 131       }
 132     }
 133   }
 134
 135   private void computeConflictingEffects(StateMachineForEffects sm, Set<StateMachineForEffects> smgroup) {
 136     boolean isStall=sm.getStallorSESE().kind()!=FKind.FlatSESEEnterNode;
 137     for(SMFEState state:sm.getStates()) {
 138       for(Effect e:state.getEffectsAllowed()) {
 139         Alloc a=e.getAffectedAllocSite();
 140         FieldDescriptor fd=e.getField();
 141         int type=e.getType();
 142         boolean hasConflict=false;
 143         if (!isStall&&Effect.isWrite(type)) {
 144           hasConflict=true;
 145         } else {
 146           for(StateMachineForEffects othersm:smgroup) {
 147             boolean otherIsStall=othersm.getStallorSESE().kind()!=FKind.FlatSESEEnterNode;
 148             //Stall sites can't conflict with each other
 149             if (isStall&&otherIsStall) continue;
 150
 151             int effectType=othersm.getEffects(a, fd);
 152             if (Effect.isWrite(type)&&effectType!=0) {
 153               //Original effect is a write and we have some effect on the same field/alloc site
 154               hasConflict=true;
 155               break;
 156             }
 157             if (Effect.isWrite(effectType)) {
 158               //We are a write
 159               hasConflict=true;
 160               break;
 161             }
 162           }
 163         }
 164         if (hasConflict) {
 165           state.addConflict(e);
 166         }
 167       }
 168     }
 169   }
 170 }