1 package Analysis.TaskStateAnalysis;
3 import java.util.Hashtable;
4 import java.util.Stack;
6 import java.util.HashSet;
7 import java.util.Iterator;
9 import Analysis.CallGraph.CallGraph;
10 import IR.SymbolTable;
12 import IR.TagDescriptor;
13 import IR.TaskDescriptor;
14 import IR.MethodDescriptor;
17 public class TagAnalysis {
22 Hashtable tasktotagbindings;
23 Hashtable tasktoflagstates;
26 public TagAnalysis(State state, CallGraph callgraph) {
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;
37 public Set getFlagStates(TaskDescriptor task) {
38 return (Set)tasktoflagstates.get(task);
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());
57 for(Iterator compit=flagset.iterator();compit.hasNext();) {
58 TagBinding tb=(TagBinding)compit.next();
59 tb.getAllocations().addAll(flagset);
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());
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);
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());
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&¶mmap!=null&¶mmap.containsKey(temp)) {
108 tag=(TagDescriptor)parammap.get(temp);
111 nodetb.setBinding(i,tag);
113 if (!discovered.containsKey(nodetb)) {
114 discovered.put(nodetb,nodetb);
117 nodetb=(TagBinding)discovered.get(nodetb);
118 tagbindings.add(nodetb);
120 } else if (fn.kind()==FKind.FlatFlagActionNode) {
121 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
122 if (ffan.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
123 TempDescriptor ffantemp=null;
127 Iterator it=ffan.getTempFlagPairs();
129 TempFlagPair tfp=(TempFlagPair)it.next();
130 ffantemp=tfp.getTemp();
132 it=ffan.getTempTagPairs();
135 TempTagPair ttp=(TempTagPair)it.next();
136 ffantemp=ttp.getTemp();
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);
145 fs=fs.setFlag(tfp.getFlag(), false);
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&¶mmap!=null&¶mmap.containsKey(ttp.getTagTemp())) {
152 tag=(TagDescriptor)parammap.get(ttp.getTagTemp());
156 throw new Error("Don't clear tag in new object allocation");
158 if (!flagmap.containsKey(fs))
161 fs=(FlagState) flagmap.get(fs);
168 private void computeTagBindings(Set roots) {
169 tovisit.addAll(roots);
170 for(Iterator it=roots.iterator();it.hasNext();) {
171 TagBinding tb=(TagBinding)it.next();
172 discovered.put(tb,tb);
175 while(!tovisit.empty()) {
176 TagBinding tb=(TagBinding) tovisit.pop();
177 MethodDescriptor md=tb.getMethod();
178 FlatMethod fm=state.getMethodFlat(md);
179 /* Build map from temps -> tagdescriptors */
180 Hashtable parammap=new Hashtable();
181 int offset=md.isStatic()?0:1;
183 for(int i=0;i<fm.numParameters();i++) {
184 TempDescriptor temp=fm.getParameter(i);
185 int offsetindex=i-offset;
186 if (offsetindex>=0) {
187 TagDescriptor tag=tb.getBinding(offsetindex);
190 parammap.put(temp,tag);
194 HashSet newtags=new HashSet();
195 computeCallsFlags(fm, parammap, newtags, tb.getAllocations());
196 for(Iterator tagit=newtags.iterator();tagit.hasNext();) {
197 TagBinding newtag=(TagBinding)tagit.next();
198 Edge e=new Edge(newtag);