Programming Languages Research Group: Git - IRC.git/blob

   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 }