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