1 package Analysis.Locality;
4 import Analysis.CallGraph.CallGraph;
8 import IR.MethodDescriptor;
11 public class LocalityAnalysis {
14 Hashtable<LocalityBinding,LocalityBinding> discovered;
15 Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
16 Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
17 Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
18 Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
22 public static final Integer LOCAL=new Integer(0);
23 public static final Integer GLOBAL=new Integer(1);
24 public static final Integer EITHER=new Integer(2);
25 public static final Integer CONFLICT=new Integer(3);
27 public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
28 this.typeutil=typeutil;
30 this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
31 this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
32 this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
33 this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
34 this.lbtovisit=new Stack();
35 this.callgraph=callgraph;
36 this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
41 public Set<LocalityBinding> getLocalityBindings() {
42 return discovered.keySet();
45 public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
46 return temptab.get(lb);
49 public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
50 return atomictab.get(lb);
53 private void doAnalysis() {
54 computeLocalityBindings();
57 private void computeLocalityBindings() {
58 LocalityBinding lbmain=new LocalityBinding(typeutil.getMain(), false);
59 lbmain.setGlobal(0, LOCAL);
60 lbtovisit.add(lbmain);
61 discovered.put(lbmain, lbmain);
63 while(!lbtovisit.empty()) {
64 LocalityBinding lb=(LocalityBinding) lbtovisit.pop();
65 Integer returnglobal=lb.getGlobalReturn();
66 MethodDescriptor md=lb.getMethod();
67 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
68 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
69 computeCallsFlags(md, lb, temptable, atomictable);
70 atomictab.put(lb, atomictable);
71 temptab.put(lb, temptable);
73 if (!md.isStatic()&&!returnglobal.equals(lb.getGlobalReturn())) {
74 //return type is more precise now
75 //rerun everything that call us
76 lbtovisit.addAll(dependence.get(lb));
82 public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
83 FlatMethod fm=state.getMethodFlat(md);
84 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
85 tovisit.add(fm.getNext(0));
87 // Build table for initial node
88 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
89 temptable.put(fm, table);
90 atomictable.put(fm, lb.isAtomic()?1:0);
91 int offset=md.isStatic()?0:1;
93 table.put(fm.getParameter(0), lb.getGlobalThis());
95 for(int i=offset;i<fm.numParameters();i++) {
96 TempDescriptor temp=fm.getParameter(i);
97 Integer b=lb.isGlobal(i-offset);
102 while(!tovisit.isEmpty()) {
103 FlatNode fn=tovisit.iterator().next();
105 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
107 for(int i=0;i<fn.numPrev();i++) {
108 FlatNode prevnode=fn.getPrev(i);
109 if (atomictable.containsKey(prevnode)) {
110 atomicstate=atomictable.get(prevnode).intValue();
112 if (!temptable.containsKey(prevnode))
114 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
115 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator();tempit.hasNext();) {
116 TempDescriptor temp=tempit.next();
117 Integer tmpint=prevtable.get(temp);
118 Integer oldint=currtable.containsKey(temp)?currtable.get(temp):EITHER;
119 Integer newint=merge(tmpint, oldint);
120 currtable.put(temp, newint);
123 atomictable.put(fn, atomicstate);
126 case FKind.FlatAtomicEnterNode:
127 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
129 case FKind.FlatAtomicExitNode:
130 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
133 processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn));
135 case FKind.FlatFieldNode:
136 processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
138 case FKind.FlatSetFieldNode:
139 processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
142 processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
144 case FKind.FlatOpNode:
145 processOpNode((FlatOpNode)fn, currtable);
147 case FKind.FlatCastNode:
148 processCastNode((FlatCastNode)fn, currtable);
150 case FKind.FlatLiteralNode:
151 processLiteralNode((FlatLiteralNode)fn, currtable);
153 case FKind.FlatReturnNode:
154 processReturnNode(lb, (FlatReturnNode)fn, currtable);
156 case FKind.FlatSetElementNode:
157 processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
159 case FKind.FlatElementNode:
160 processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
162 case FKind.FlatCondBranch:
163 case FKind.FlatBackEdge:
165 //No action needed for these
167 case FKind.FlatFlagActionNode:
168 case FKind.FlatCheckNode:
169 case FKind.FlatTagDeclaration:
170 throw new Error("Incompatible with tasks!");
171 case FKind.FlatMethod:
175 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
176 if (oldtable==null||!oldtable.equals(currtable)) {
177 // Update table for this node
178 temptable.put(fn, currtable);
179 for(int i=0;i<fn.numNext();i++) {
180 tovisit.add(fn.getNext(i));
186 private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
187 return atomictable.get(fn).intValue()>0;
190 private static Integer merge(Integer a, Integer b) {
191 if (a==null||a.equals(EITHER))
193 if (b==null||b.equals(EITHER))
200 void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
201 MethodDescriptor nodemd=fc.getMethod();
202 Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
203 callgraph.getMethods(nodemd, fc.getThis().getType());
204 Integer currreturnval=EITHER; //Start off with the either value
205 for(Iterator methodit=methodset.iterator();methodit.hasNext();) {
206 MethodDescriptor md=(MethodDescriptor) methodit.next();
207 LocalityBinding lb=new LocalityBinding(md, isatomic);
208 for(int i=0;i<fc.numArgs();i++) {
209 TempDescriptor arg=fc.getArg(i);
210 lb.setGlobal(i,currtable.get(arg));
212 if (fc.getThis()!=null) {
213 Integer thistype=currtable.get(fc.getThis());
216 if(thistype.equals(CONFLICT))
217 throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
218 if(thistype.equals(GLOBAL)&&!isatomic)
219 throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
220 lb.setGlobalThis(thistype);
222 lb.setGlobalThis(EITHER);//default value
224 if (!discovered.containsKey(lb)) {
225 lb.setGlobalReturn(EITHER);
226 lb.setParent(currlb);
228 discovered.put(lb, lb);
230 lb=discovered.get(lb);
231 Integer returnval=lb.getGlobalReturn();
232 currreturnval=merge(returnval, currreturnval);
233 if (!dependence.containsKey(lb))
234 dependence.put(lb, new HashSet<LocalityBinding>());
235 dependence.get(lb).add(currlb);
237 if (fc.getReturnTemp()!=null) {
238 currtable.put(fc.getReturnTemp(), currreturnval);
242 void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
243 Integer type=currtable.get(ffn.getSrc());
244 TempDescriptor dst=ffn.getDst();
245 if (type.equals(LOCAL)) {
246 if (ffn.getField().isGlobal())
247 currtable.put(dst,GLOBAL);
249 currtable.put(dst,LOCAL);
250 } else if (type.equals(GLOBAL)) {
252 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
253 if (ffn.getField().getType().isPrimitive())
254 currtable.put(dst, LOCAL); // primitives are local
256 currtable.put(dst, GLOBAL);
257 } else if (type.equals(EITHER)) {
258 if (ffn.getField().getType().isPrimitive())
259 currtable.put(dst, LOCAL); // primitives are local
261 currtable.put(dst, EITHER);
262 } else if (type.equals(CONFLICT)) {
263 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
267 //need to handle primitives
268 void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
269 Integer srctype=currtable.get(fsfn.getSrc());
270 Integer dsttype=currtable.get(fsfn.getDst());
272 if (dsttype.equals(LOCAL)) {
273 if (fsfn.getField().isGlobal()) {
274 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
275 throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
277 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
278 throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
280 } else if (dsttype.equals(GLOBAL)) {
282 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
283 //okay to store primitives in global object
284 if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive())
286 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
287 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
288 } else if (dsttype.equals(EITHER)) {
289 if (srctype.equals(CONFLICT))
290 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
291 } else if (dsttype.equals(CONFLICT)) {
292 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
296 void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
297 if (fn.isGlobal()&&!transaction) {
298 throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
301 currtable.put(fn.getDst(), GLOBAL);
303 currtable.put(fn.getDst(), LOCAL);
306 void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
307 /* Just propagate value */
308 currtable.put(fon.getDest(), currtable.get(fon.getLeft()));
311 void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
312 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
315 void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
317 if (fln.getValue()==null)
318 currtable.put(fln.getDst(), EITHER);
320 currtable.put(fln.getDst(), LOCAL);
323 void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
324 if(frn.getReturnTemp()!=null) {
325 Integer returntype=currtable.get(frn.getReturnTemp());
326 lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
330 void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
331 Integer srctype=currtable.get(fsen.getSrc());
332 Integer dsttype=currtable.get(fsen.getDst());
334 if (dsttype.equals(LOCAL)) {
335 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
336 throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation());
337 } else if (dsttype.equals(GLOBAL)) {
338 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
339 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
341 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
342 } else if (dsttype.equals(EITHER)) {
343 if (srctype.equals(CONFLICT))
344 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
345 } else if (dsttype.equals(CONFLICT)) {
346 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
350 void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
351 Integer type=currtable.get(fen.getSrc());
352 TempDescriptor dst=fen.getDst();
353 if (type.equals(LOCAL)) {
354 currtable.put(dst,LOCAL);
355 } else if (type.equals(GLOBAL)) {
357 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
358 currtable.put(dst, GLOBAL);
359 } else if (type.equals(EITHER)) {
360 currtable.put(dst, EITHER);
361 } else if (type.equals(CONFLICT)) {
362 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
366 void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
367 int atomic=atomictable.get(fen).intValue();
368 atomictable.put(fen, new Integer(atomic+1));
371 void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
372 int atomic=atomictable.get(fen).intValue();
373 atomictable.put(fen, new Integer(atomic-1));
376 private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
377 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
379 Set<FlatNode> toprocess=fm.getNodeSet();
381 while(!toprocess.isEmpty()) {
382 FlatNode fn=toprocess.iterator().next();
383 toprocess.remove(fn);
385 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
386 List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
388 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
389 for(int i=0;i<fn.numNext();i++) {
390 FlatNode fnnext=fn.getNext(i);
391 if (nodetotemps.containsKey(fnnext))
392 tempset.addAll(nodetotemps.get(fnnext));
394 tempset.removeAll(writes);
395 tempset.addAll(reads);
396 if (!nodetotemps.containsKey(fn)||
397 nodetotemps.get(fn).equals(tempset)) {
398 nodetotemps.put(fn, tempset);
399 for(int i=0;i<fn.numPrev();i++)
400 toprocess.add(fn.getPrev(i));
406 /* Need to checkpoint all temps that could be read from along any
407 * path that are either:
408 1) Written to by any assignment inside the transaction
409 2) Read from a global temp.
411 Generate tempstosave map from
412 localitybinding->flatatomicenternode->Set<TempDescriptors>
415 private void computeTempstoCheckpoint(LocalityBinding lb) {
416 Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
417 Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
418 MethodDescriptor md=lb.getMethod();
419 FlatMethod fm=state.getMethodFlat(md);
421 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=computeLiveTemps(fm);