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