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;
9 import java.util.Vector;
12 import Analysis.CallGraph.CallGraph;
13 import IR.SymbolTable;
15 import IR.TagDescriptor;
16 import IR.TaskDescriptor;
17 import IR.MethodDescriptor;
20 public class TagAnalysis {
25 Hashtable tasktotagbindings;
26 Hashtable tasktoflagstates;
29 public TagAnalysis(State state, CallGraph callgraph) {
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;
40 public Set getFlagStates(TaskDescriptor task) {
41 return (Set)tasktoflagstates.get(task);
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());
60 for(Iterator compit=component.iterator(); compit.hasNext();) {
61 TagBinding tb=(TagBinding)compit.next();
62 tb.getAllocations().addAll(flagset);
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());
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);
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());
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&¶mmap!=null&¶mmap.containsKey(temp)) {
111 tag=(TagDescriptor)parammap.get(temp);
114 nodetb.setBinding(i,tag);
116 if (!discovered.containsKey(nodetb)) {
117 discovered.put(nodetb,nodetb);
120 nodetb=(TagBinding)discovered.get(nodetb);
121 tagbindings.add(nodetb);
123 } else if (fn.kind()==FKind.FlatFlagActionNode) {
124 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
125 if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
126 TempDescriptor ffantemp=null;
130 Iterator it=ffan.getTempFlagPairs();
132 TempFlagPair tfp=(TempFlagPair)it.next();
133 ffantemp=tfp.getTemp();
135 it=ffan.getTempTagPairs();
138 TempTagPair ttp=(TempTagPair)it.next();
139 ffantemp=ttp.getTemp();
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);
149 fs=fs.setFlag(tfp.getFlag(), false);
152 HashSet fsset=new HashSet();
155 for(Iterator it=ffan.getTempTagPairs(); it.hasNext();) {
156 HashSet oldfsset=fsset;
159 TempTagPair ttp=(TempTagPair)it.next();
160 if (ffan.getTagChange(ttp)) {
161 TagDescriptor tag=ttp.getTag();
162 if (tag==null&¶mmap!=null&¶mmap.containsKey(ttp.getTagTemp())) {
163 tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
165 for(Iterator setit=oldfsset.iterator(); setit.hasNext();) {
166 FlagState fs2=(FlagState)setit.next();
167 fsset.addAll(Arrays.asList(fs2.setTag(tag)));
170 throw new Error("Don't clear tag in new object allocation");
173 for(Iterator setit=fsset.iterator(); setit.hasNext();) {
174 FlagState fs2=(FlagState)setit.next();
175 if (!flagmap.containsKey(fs2))
176 flagmap.put(fs2,fs2);
178 fs2=(FlagState) flagmap.get(fs2);
180 if(!targetFStates.contains(fs2)) {
181 targetFStates.addElement(fs2);
189 private void computeTagBindings(Set roots) {
190 tovisit.addAll(roots);
192 for(Iterator it=roots.iterator(); it.hasNext();) {
193 TagBinding tb=(TagBinding)it.next();
194 discovered.put(tb,tb);
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;
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);
213 parammap.put(temp,tag);
218 HashSet newtags=new HashSet();
220 computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
222 for(Iterator tagit=newtags.iterator(); tagit.hasNext();) {
223 TagBinding newtag=(TagBinding)tagit.next();
224 Edge e=new Edge(newtag);