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=flagset.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=flagset.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 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());
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&¶mmap!=null&¶mmap.containsKey(temp)) {
109 tag=(TagDescriptor)parammap.get(temp);
112 nodetb.setBinding(i,tag);
114 if (!discovered.containsKey(nodetb)) {
115 discovered.put(nodetb,nodetb);
118 nodetb=(TagBinding)discovered.get(nodetb);
119 tagbindings.add(nodetb);
121 } else if (fn.kind()==FKind.FlatFlagActionNode) {
122 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
123 if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
124 TempDescriptor ffantemp=null;
128 Iterator it=ffan.getTempFlagPairs();
130 TempFlagPair tfp=(TempFlagPair)it.next();
131 ffantemp=tfp.getTemp();
133 it=ffan.getTempTagPairs();
136 TempTagPair ttp=(TempTagPair)it.next();
137 ffantemp=ttp.getTemp();
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);
146 fs=fs.setFlag(tfp.getFlag(), false);
149 HashSet fsset=new HashSet();
152 for(Iterator it=ffan.getTempTagPairs();it.hasNext();) {
153 HashSet oldfsset=fsset;
156 TempTagPair ttp=(TempTagPair)it.next();
157 if (ffan.getTagChange(ttp)) {
158 TagDescriptor tag=ttp.getTag();
159 if (tag==null&¶mmap!=null&¶mmap.containsKey(ttp.getTagTemp())) {
160 tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
162 for(Iterator setit=oldfsset.iterator();setit.hasNext();) {
163 FlagState fs2=(FlagState)setit.next();
164 fsset.addAll(Arrays.asList(fs2.setTag(tag)));
167 throw new Error("Don't clear tag in new object allocation");
170 for(Iterator setit=fsset.iterator();setit.hasNext();) {
171 FlagState fs2=(FlagState)setit.next();
172 if (!flagmap.containsKey(fs2))
173 flagmap.put(fs2,fs2);
175 fs2=(FlagState) flagmap.get(fs2);
183 private void computeTagBindings(Set roots) {
184 tovisit.addAll(roots);
186 for(Iterator it=roots.iterator();it.hasNext();) {
187 TagBinding tb=(TagBinding)it.next();
188 discovered.put(tb,tb);
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;
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);
207 parammap.put(temp,tag);
212 HashSet newtags=new HashSet();
214 computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
216 for(Iterator tagit=newtags.iterator();tagit.hasNext();) {
217 TagBinding newtag=(TagBinding)tagit.next();
218 Edge e=new Edge(newtag);