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     Set nodeset=fm.getNodeSet();
  94     for(Iterator nodeit=nodeset.iterator();nodeit.hasNext();) {
  95         FlatNode fn=(FlatNode)nodeit.next();
  96         if(fn.kind()==FKind.FlatCall) {
  97             FlatCall fc=(FlatCall)fn;
  98             MethodDescriptor nodemd=fc.getMethod();
  99             Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
 100                 callgraph.getMethods(nodemd, fc.getThis().getType());
 101
 102             for(Iterator methodit=methodset.iterator();methodit.hasNext();) {
 103                 MethodDescriptor md=(MethodDescriptor) methodit.next();
 104                 TagBinding nodetb=new TagBinding(md);
 105                 for(int i=0;i<md.numParameters();i++) {
 106                     TempDescriptor temp=fc.getArg(i);
 107                     TagDescriptor tag=temp.getTag();
 108                     if (tag==null&&parammap!=null&&parammap.containsKey(temp)) {
 109                         tag=(TagDescriptor)parammap.get(temp);
 110                     }
 111                     if (tag!=null)
 112                         nodetb.setBinding(i,tag);
 113                 }
 114                 if (!discovered.containsKey(nodetb)) {
 115                     discovered.put(nodetb,nodetb);
 116                     tovisit.add(nodetb);
 117                 } else
 118                     nodetb=(TagBinding)discovered.get(nodetb);
 119                 tagbindings.add(nodetb);
 120             }
 121         } else if (fn.kind()==FKind.FlatFlagActionNode) {
 122             FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
 123             if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
 124                 TempDescriptor ffantemp=null;
 125                 {
 126                     /* Compute type */
 127
 128                     Iterator it=ffan.getTempFlagPairs();
 129                     if (it.hasNext()) {
 130                         TempFlagPair tfp=(TempFlagPair)it.next();
 131                         ffantemp=tfp.getTemp();
 132                     } else {
 133                         it=ffan.getTempTagPairs();
 134                         if (!it.hasNext())
 135                             throw new Error();
 136                         TempTagPair ttp=(TempTagPair)it.next();
 137                         ffantemp=ttp.getTemp();
 138                     }
 139                 }
 140                 FlagState fs=new FlagState(ffantemp.getType().getClassDesc());
 141                 for(Iterator it=ffan.getTempFlagPairs();it.hasNext();) {
 142                     TempFlagPair tfp=(TempFlagPair)it.next();
 143                     if (ffan.getFlagChange(tfp))
 144                         fs=fs.setFlag(tfp.getFlag(), true);
 145                     else
 146                         fs=fs.setFlag(tfp.getFlag(), false);
 147                 }
 148
 149                 HashSet fsset=new HashSet();
 150                 fsset.add(fs);
 151
 152                 for(Iterator it=ffan.getTempTagPairs();it.hasNext();) {
 153                     HashSet oldfsset=fsset;
 154                     fsset=new HashSet();
 155
 156                     TempTagPair ttp=(TempTagPair)it.next();
 157                     if (ffan.getTagChange(ttp)) {
 158                         TagDescriptor tag=ttp.getTag();
 159                         if (tag==null&&parammap!=null&&parammap.containsKey(ttp.getTagTemp())) {
 160                             tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
 161                         }
 162                         for(Iterator setit=oldfsset.iterator();setit.hasNext();) {
 163                             FlagState fs2=(FlagState)setit.next();
 164                             fsset.addAll(Arrays.asList(fs2.setTag(tag)));
 165                         }
 166                     } else
 167                         throw new Error("Don't clear tag in new object allocation");
 168                 }
 169
 170                 for(Iterator setit=fsset.iterator();setit.hasNext();) {
 171                     FlagState fs2=(FlagState)setit.next();
 172                     if (!flagmap.containsKey(fs2))
 173                         flagmap.put(fs2,fs2);
 174                     else
 175                         fs2=(FlagState) flagmap.get(fs2);
 176                     newflags.add(fs2);
 177                 }
 178             }
 179         }
 180     }
 181 }
 182
 183     private void computeTagBindings(Set roots) {
 184         tovisit.addAll(roots);
 185
 186         for(Iterator it=roots.iterator();it.hasNext();) {
 187             TagBinding tb=(TagBinding)it.next();
 188             discovered.put(tb,tb);
 189         }
 190
 191         while(!tovisit.empty()) {
 192             TagBinding tb=(TagBinding) tovisit.pop();
 193             MethodDescriptor md=tb.getMethod();
 194             FlatMethod fm=state.getMethodFlat(md);
 195             /* Build map from temps -> tagdescriptors */
 196             Hashtable parammap=new Hashtable();
 197             int offset=md.isStatic()?0:1;
 198
 199
 200             for(int i=0;i<fm.numParameters();i++) {
 201                 TempDescriptor temp=fm.getParameter(i);
 202                 int offsetindex=i-offset;
 203                 if (offsetindex>=0) {
 204                     TagDescriptor tag=tb.getBinding(offsetindex);
 205
 206                     if (tag!=null) {
 207                         parammap.put(temp,tag);
 208                     }
 209                 }
 210             }
 211
 212             HashSet newtags=new HashSet();
 213
 214             computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
 215
 216             for(Iterator tagit=newtags.iterator();tagit.hasNext();) {
 217                 TagBinding newtag=(TagBinding)tagit.next();
 218                 Edge e=new Edge(newtag);
 219                 tb.addEdge(e);
 220             }
 221         }
 222     }
 223 }