Robust/src/Analysis/TaskStateAnalysis/TagAnalysis.java

   1 package Analysis.TaskStateAnalysis;
   2
   3 import java.util.Hashtable;
   4 import java.util.Stack;
   5 import java.util.Set;
   6 import java.util.HashSet;
   7 import java.util.Iterator;
   8 import java.util.Arrays;
   9 import java.util.Vector;
  10
  11 import Util.Edge;
  12 import Analysis.CallGraph.CallGraph;
  13 import IR.SymbolTable;
  14 import IR.State;
  15 import IR.TagDescriptor;
  16 import IR.TaskDescriptor;
  17 import IR.MethodDescriptor;
  18 import IR.Flat.*;
  19
  20 public class TagAnalysis {
  21   State state;
  22   Hashtable flagmap;
  23   Stack tovisit;
  24   Hashtable discovered;
  25   Hashtable tasktotagbindings;
  26   Hashtable tasktoflagstates;
  27   CallGraph callgraph;
  28
  29   public TagAnalysis(State state, CallGraph callgraph) {
  30     this.state=state;
  31     this.flagmap=new Hashtable();
  32     this.discovered=new Hashtable();
  33     this.tovisit=new Stack();
  34     this.tasktoflagstates=new Hashtable();
  35     this.tasktotagbindings=new Hashtable();
  36     this.callgraph=callgraph;
  37     doAnalysis();
  38   }
  39
  40   public Set getFlagStates(TaskDescriptor task) {
  41     return (Set)tasktoflagstates.get(task);
  42   }
  43
  44   private void doAnalysis() {
  45     Set rootset=computeRootSet();
  46     computeTagBindings(rootset);
  47     TagBinding.SCC scc=TagBinding.DFS.computeSCC(discovered.keySet());
  48     for(int i=0; i<scc.numSCC(); i++) {
  49       Set component=scc.getSCC(i);
  50       HashSet flagset=new HashSet();
  51       for(Iterator compit=component.iterator(); compit.hasNext(); ) {
  52         TagBinding tb=(TagBinding)compit.next();
  53         flagset.addAll(tb.getAllocations());
  54         for(Iterator edgeit=tb.edges(); edgeit.hasNext(); ) {
  55           Edge e=(Edge)edgeit.next();
  56           TagBinding tb2=(TagBinding)e.getTarget();
  57           flagset.addAll(tb2.getAllocations());
  58         }
  59       }
  60       for(Iterator compit=component.iterator(); compit.hasNext(); ) {
  61         TagBinding tb=(TagBinding)compit.next();
  62         tb.getAllocations().addAll(flagset);
  63       }
  64     }
  65
  66     SymbolTable tasktable=state.getTaskSymbolTable();
  67     for(Iterator taskit=tasktable.getDescriptorsIterator(); taskit.hasNext(); ) {
  68       TaskDescriptor task=(TaskDescriptor)taskit.next();
  69       HashSet roottags=(HashSet)tasktotagbindings.get(task);
  70       HashSet taskflags=(HashSet)tasktoflagstates.get(task);
  71       for(Iterator tagit=roottags.iterator(); tagit.hasNext(); ) {
  72         TagBinding tb=(TagBinding)tagit.next();
  73         taskflags.addAll(tb.getAllocations());
  74       }
  75     }
  76   }
  77
  78   private Set computeRootSet() {
  79     HashSet rootset=new HashSet();
  80     SymbolTable tasktable=state.getTaskSymbolTable();
  81     for(Iterator taskit=tasktable.getDescriptorsIterator(); taskit.hasNext(); ) {
  82       TaskDescriptor task=(TaskDescriptor)taskit.next();
  83       HashSet roottags=new HashSet();
  84       HashSet taskflags=new HashSet();
  85       FlatMethod fm=state.getMethodFlat(task);
  86       computeCallsFlags(fm, null, roottags, taskflags);
  87       rootset.addAll(roottags);
  88       tasktotagbindings.put(task,roottags);
  89       tasktoflagstates.put(task,taskflags);
  90     }
  91     return rootset;
  92   }
  93
  94   private void computeCallsFlags(FlatMethod fm, Hashtable parammap, Set tagbindings, Set newflags) {
  95     Set nodeset=fm.getNodeSet();
  96     for(Iterator nodeit=nodeset.iterator(); nodeit.hasNext(); ) {
  97       FlatNode fn=(FlatNode)nodeit.next();
  98       if(fn.kind()==FKind.FlatCall) {
  99         FlatCall fc=(FlatCall)fn;
 100         MethodDescriptor nodemd=fc.getMethod();
 101         Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
 102                        callgraph.getMethods(nodemd, fc.getThis().getType());
 103
 104         for(Iterator methodit=methodset.iterator(); methodit.hasNext(); ) {
 105           MethodDescriptor md=(MethodDescriptor) methodit.next();
 106           TagBinding nodetb=new TagBinding(md);
 107           for(int i=0; i<md.numParameters(); i++) {
 108             TempDescriptor temp=fc.getArg(i);
 109             TagDescriptor tag=temp.getTag();
 110             if (tag==null&&parammap!=null&&parammap.containsKey(temp)) {
 111               tag=(TagDescriptor)parammap.get(temp);
 112             }
 113             if (tag!=null)
 114               nodetb.setBinding(i,tag);
 115           }
 116           if (!discovered.containsKey(nodetb)) {
 117             discovered.put(nodetb,nodetb);
 118             tovisit.add(nodetb);
 119           } else
 120             nodetb=(TagBinding)discovered.get(nodetb);
 121           tagbindings.add(nodetb);
 122         }
 123       } else if (fn.kind()==FKind.FlatFlagActionNode) {
 124         FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
 125         if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
 126           TempDescriptor ffantemp=null;
 127           {
 128             /* Compute type */
 129
 130             Iterator it=ffan.getTempFlagPairs();
 131             if (it.hasNext()) {
 132               TempFlagPair tfp=(TempFlagPair)it.next();
 133               ffantemp=tfp.getTemp();
 134             } else {
 135               it=ffan.getTempTagPairs();
 136               if (!it.hasNext())
 137                 throw new Error();
 138               TempTagPair ttp=(TempTagPair)it.next();
 139               ffantemp=ttp.getTemp();
 140             }
 141           }
 142           Vector<FlagState> targetFStates = ffan.getTargetFStates4NewObj(ffantemp.getType().getClassDesc());
 143           FlagState fs=new FlagState(ffantemp.getType().getClassDesc());
 144           for(Iterator it=ffan.getTempFlagPairs(); it.hasNext(); ) {
 145             TempFlagPair tfp=(TempFlagPair)it.next();
 146             if (ffan.getFlagChange(tfp))
 147               fs=fs.setFlag(tfp.getFlag(), true);
 148             else
 149               fs=fs.setFlag(tfp.getFlag(), false);
 150           }
 151
 152           HashSet fsset=new HashSet();
 153           fsset.add(fs);
 154
 155           for(Iterator it=ffan.getTempTagPairs(); it.hasNext(); ) {
 156             HashSet oldfsset=fsset;
 157             fsset=new HashSet();
 158
 159             TempTagPair ttp=(TempTagPair)it.next();
 160             if (ffan.getTagChange(ttp)) {
 161               TagDescriptor tag=ttp.getTag();
 162               if (tag==null&&parammap!=null&&parammap.containsKey(ttp.getTagTemp())) {
 163                 tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
 164               }
 165               for(Iterator setit=oldfsset.iterator(); setit.hasNext(); ) {
 166                 FlagState fs2=(FlagState)setit.next();
 167                 fsset.addAll(Arrays.asList(fs2.setTag(tag)));
 168               }
 169             } else
 170               throw new Error("Don't clear tag in new object allocation");
 171           }
 172
 173           for(Iterator setit=fsset.iterator(); setit.hasNext(); ) {
 174             FlagState fs2=(FlagState)setit.next();
 175             if (!flagmap.containsKey(fs2))
 176               flagmap.put(fs2,fs2);
 177             else
 178               fs2=(FlagState) flagmap.get(fs2);
 179             newflags.add(fs2);
 180             if(!targetFStates.contains(fs2)) {
 181               targetFStates.addElement(fs2);
 182             }
 183           }
 184         }
 185       }
 186     }
 187   }
 188
 189   private void computeTagBindings(Set roots) {
 190     tovisit.addAll(roots);
 191
 192     for(Iterator it=roots.iterator(); it.hasNext(); ) {
 193       TagBinding tb=(TagBinding)it.next();
 194       discovered.put(tb,tb);
 195     }
 196
 197     while(!tovisit.empty()) {
 198       TagBinding tb=(TagBinding) tovisit.pop();
 199       MethodDescriptor md=tb.getMethod();
 200       FlatMethod fm=state.getMethodFlat(md);
 201       /* Build map from temps -> tagdescriptors */
 202       Hashtable parammap=new Hashtable();
 203       int offset=md.isStatic()?0:1;
 204
 205
 206       for(int i=0; i<fm.numParameters(); i++) {
 207         TempDescriptor temp=fm.getParameter(i);
 208         int offsetindex=i-offset;
 209         if (offsetindex>=0) {
 210           TagDescriptor tag=tb.getBinding(offsetindex);
 211
 212           if (tag!=null) {
 213             parammap.put(temp,tag);
 214           }
 215         }
 216       }
 217
 218       HashSet newtags=new HashSet();
 219
 220       computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
 221
 222       for(Iterator tagit=newtags.iterator(); tagit.hasNext(); ) {
 223         TagBinding newtag=(TagBinding)tagit.next();
 224         Edge e=new Edge(newtag);
 225         tb.addEdge(e);
 226       }
 227     }
 228   }
 229 }