1 package Analysis.TaskStateAnalysis;
3 import java.util.Hashtable;
4 import java.util.Stack;
6 import java.util.HashSet;
7 import java.util.Iterator;
8 import java.util.Arrays;
10 import Analysis.CallGraph.CallGraph;
11 import IR.SymbolTable;
13 import IR.TagDescriptor;
14 import IR.TaskDescriptor;
15 import IR.MethodDescriptor;
18 public class TagAnalysis {
23 Hashtable tasktotagbindings;
24 Hashtable tasktoflagstates;
27 public TagAnalysis(State state, CallGraph callgraph) {
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;
38 public Set getFlagStates(TaskDescriptor task) {
39 return (Set)tasktoflagstates.get(task);
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());
58 for(Iterator compit=component.iterator();compit.hasNext();) {
59 TagBinding tb=(TagBinding)compit.next();
60 tb.getAllocations().addAll(flagset);
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());
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);
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());
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&¶mmap!=null&¶mmap.containsKey(temp)) {
110 tag=(TagDescriptor)parammap.get(temp);
113 nodetb.setBinding(i,tag);
115 if (!discovered.containsKey(nodetb)) {
116 discovered.put(nodetb,nodetb);
119 nodetb=(TagBinding)discovered.get(nodetb);
120 tagbindings.add(nodetb);
122 } else if (fn.kind()==FKind.FlatFlagActionNode) {
123 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
124 if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
125 TempDescriptor ffantemp=null;
129 Iterator it=ffan.getTempFlagPairs();
131 TempFlagPair tfp=(TempFlagPair)it.next();
132 ffantemp=tfp.getTemp();
134 it=ffan.getTempTagPairs();
137 TempTagPair ttp=(TempTagPair)it.next();
138 ffantemp=ttp.getTemp();
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);
147 fs=fs.setFlag(tfp.getFlag(), false);
150 HashSet fsset=new HashSet();
153 for(Iterator it=ffan.getTempTagPairs();it.hasNext();) {
154 HashSet oldfsset=fsset;
157 TempTagPair ttp=(TempTagPair)it.next();
158 if (ffan.getTagChange(ttp)) {
159 TagDescriptor tag=ttp.getTag();
160 if (tag==null&¶mmap!=null&¶mmap.containsKey(ttp.getTagTemp())) {
161 tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
163 for(Iterator setit=oldfsset.iterator();setit.hasNext();) {
164 FlagState fs2=(FlagState)setit.next();
165 fsset.addAll(Arrays.asList(fs2.setTag(tag)));
168 throw new Error("Don't clear tag in new object allocation");
171 for(Iterator setit=fsset.iterator();setit.hasNext();) {
172 FlagState fs2=(FlagState)setit.next();
173 if (!flagmap.containsKey(fs2))
174 flagmap.put(fs2,fs2);
176 fs2=(FlagState) flagmap.get(fs2);
184 private void computeTagBindings(Set roots) {
185 tovisit.addAll(roots);
187 for(Iterator it=roots.iterator();it.hasNext();) {
188 TagBinding tb=(TagBinding)it.next();
189 discovered.put(tb,tb);
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;
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);
208 parammap.put(temp,tag);
213 HashSet newtags=new HashSet();
215 computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
217 for(Iterator tagit=newtags.iterator();tagit.hasNext();) {
218 TagBinding newtag=(TagBinding)tagit.next();
219 Edge e=new Edge(newtag);