1 package Analysis.Locality;
4 import Analysis.CallGraph.CallGraph;
8 import IR.MethodDescriptor;
10 import IR.ClassDescriptor;
12 public class LocalityAnalysis {
15 Hashtable<LocalityBinding,LocalityBinding> discovered;
16 Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
17 Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
18 Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
19 Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
20 Hashtable<ClassDescriptor, Set<LocalityBinding>> classtolb;
21 Hashtable<MethodDescriptor, Set<LocalityBinding>> methodtolb;
25 public static final Integer LOCAL=new Integer(0);
26 public static final Integer GLOBAL=new Integer(1);
27 public static final Integer EITHER=new Integer(2);
28 public static final Integer CONFLICT=new Integer(3);
30 public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
31 this.typeutil=typeutil;
33 this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
34 this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
35 this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
36 this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
37 this.lbtovisit=new Stack();
38 this.callgraph=callgraph;
39 this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
40 this.classtolb=new Hashtable<ClassDescriptor, Set<LocalityBinding>>();
41 this.methodtolb=new Hashtable<MethodDescriptor, Set<LocalityBinding>>();
45 /** This method returns a set of LocalityBindings for the parameter class. */
47 public Set<LocalityBinding> getClassBindings(ClassDescriptor cd) {
48 return classtolb.get(cd);
51 /** This method returns a set of LocalityBindings for the parameter method. */
53 public Set<LocalityBinding> getMethodBindings(MethodDescriptor md) {
54 return methodtolb.get(md);
57 /** This method returns a set of LocalityBindings. A
58 * LocalityBinding specifies a context a method can be invoked in.
59 * It specifies whether the method is in a transaction and whether
60 * its parameter objects are locals or globals. */
62 public Set<LocalityBinding> getLocalityBindings() {
63 return discovered.keySet();
66 /** This method returns a hashtable for a given LocalityBinding
67 * that tells the current local/global status of temps at the each
68 * node in the flat representation. */
70 public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
71 return temptab.get(lb);
74 /** This method returns an hashtable for a given LocalitBinding
75 * that tells whether a node in the flat represenation is in a
76 * transaction or not. Integer values greater than 0 indicate
77 * that the node is in a transaction and give the nesting depth.
78 * The outermost AtomicEnterNode will have a value of 1 and the
79 * outermost AtomicExitNode will have a value of 0. */
81 public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
82 return atomictab.get(lb);
85 /** This methods returns a hashtable for a given LocalityBinding
86 * that tells which temps needs to be saved for each
89 public Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> getTemps(LocalityBinding lb) {
90 return tempstosave.get(lb);
93 public Set<TempDescriptor> getTempSet(LocalityBinding lb) {
94 HashSet<TempDescriptor> set=new HashSet<TempDescriptor>();
95 Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> table=getTemps(lb);
96 for(Iterator<FlatAtomicEnterNode> faenit=table.keySet().iterator();faenit.hasNext();) {
97 FlatAtomicEnterNode faen=faenit.next();
98 set.addAll(table.get(faen));
103 private void doAnalysis() {
104 computeLocalityBindings();
105 computeTempstoSave();
108 private void computeLocalityBindings() {
109 LocalityBinding lbmain=new LocalityBinding(typeutil.getMain(), false);
110 lbmain.setGlobal(0, LOCAL);
111 lbtovisit.add(lbmain);
112 discovered.put(lbmain, lbmain);
113 if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
114 classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
115 classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
117 if (!methodtolb.containsKey(lbmain.getMethod()))
118 methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
119 methodtolb.get(lbmain.getMethod()).add(lbmain);
121 while(!lbtovisit.empty()) {
122 LocalityBinding lb=(LocalityBinding) lbtovisit.pop();
123 Integer returnglobal=lb.getGlobalReturn();
124 MethodDescriptor md=lb.getMethod();
125 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
126 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
127 computeCallsFlags(md, lb, temptable, atomictable);
128 atomictab.put(lb, atomictable);
129 temptab.put(lb, temptable);
131 if (!md.isStatic()&&!returnglobal.equals(lb.getGlobalReturn())) {
132 //return type is more precise now
133 //rerun everything that call us
134 lbtovisit.addAll(dependence.get(lb));
140 public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
141 FlatMethod fm=state.getMethodFlat(md);
142 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
143 tovisit.add(fm.getNext(0));
145 // Build table for initial node
146 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
147 temptable.put(fm, table);
148 atomictable.put(fm, lb.isAtomic()?1:0);
149 int offset=md.isStatic()?0:1;
150 if (!md.isStatic()) {
151 table.put(fm.getParameter(0), lb.getGlobalThis());
153 for(int i=offset;i<fm.numParameters();i++) {
154 TempDescriptor temp=fm.getParameter(i);
155 Integer b=lb.isGlobal(i-offset);
160 while(!tovisit.isEmpty()) {
161 FlatNode fn=tovisit.iterator().next();
163 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
165 for(int i=0;i<fn.numPrev();i++) {
166 FlatNode prevnode=fn.getPrev(i);
167 if (atomictable.containsKey(prevnode)) {
168 atomicstate=atomictable.get(prevnode).intValue();
170 if (!temptable.containsKey(prevnode))
172 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
173 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator();tempit.hasNext();) {
174 TempDescriptor temp=tempit.next();
175 Integer tmpint=prevtable.get(temp);
176 Integer oldint=currtable.containsKey(temp)?currtable.get(temp):EITHER;
177 Integer newint=merge(tmpint, oldint);
178 currtable.put(temp, newint);
181 atomictable.put(fn, atomicstate);
184 case FKind.FlatAtomicEnterNode:
185 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
189 case FKind.FlatAtomicExitNode:
190 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
193 processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn));
195 case FKind.FlatFieldNode:
196 processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
198 case FKind.FlatSetFieldNode:
199 processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
202 processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
204 case FKind.FlatOpNode:
205 processOpNode((FlatOpNode)fn, currtable);
207 case FKind.FlatCastNode:
208 processCastNode((FlatCastNode)fn, currtable);
210 case FKind.FlatLiteralNode:
211 processLiteralNode((FlatLiteralNode)fn, currtable);
213 case FKind.FlatReturnNode:
214 processReturnNode(lb, (FlatReturnNode)fn, currtable);
216 case FKind.FlatSetElementNode:
217 processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
219 case FKind.FlatElementNode:
220 processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
222 case FKind.FlatCondBranch:
223 case FKind.FlatBackEdge:
225 //No action needed for these
227 case FKind.FlatFlagActionNode:
228 case FKind.FlatCheckNode:
229 case FKind.FlatTagDeclaration:
230 throw new Error("Incompatible with tasks!");
231 case FKind.FlatMethod:
235 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
236 if (oldtable==null||!oldtable.equals(currtable)) {
237 // Update table for this node
238 temptable.put(fn, currtable);
239 for(int i=0;i<fn.numNext();i++) {
240 tovisit.add(fn.getNext(i));
246 private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
247 return atomictable.get(fn).intValue()>0;
250 private static Integer merge(Integer a, Integer b) {
251 if (a==null||a.equals(EITHER))
253 if (b==null||b.equals(EITHER))
260 void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
261 MethodDescriptor nodemd=fc.getMethod();
262 Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
263 callgraph.getMethods(nodemd, fc.getThis().getType());
264 Integer currreturnval=EITHER; //Start off with the either value
265 for(Iterator methodit=methodset.iterator();methodit.hasNext();) {
266 MethodDescriptor md=(MethodDescriptor) methodit.next();
267 boolean isnative=md.getModifiers().isNative();
269 LocalityBinding lb=new LocalityBinding(md, isatomic);
270 if (isnative&&isatomic) {
271 System.out.println("Don't call native methods in atomic blocks!");
273 for(int i=0;i<fc.numArgs();i++) {
274 TempDescriptor arg=fc.getArg(i);
275 if(isnative&&(currtable.get(arg).equals(GLOBAL)||
276 currtable.get(arg).equals(CONFLICT)))
277 throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
278 lb.setGlobal(i,currtable.get(arg));
280 if (fc.getThis()!=null) {
281 Integer thistype=currtable.get(fc.getThis());
284 if(thistype.equals(CONFLICT))
285 throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
286 if(thistype.equals(GLOBAL)&&!isatomic)
287 throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
288 if (isnative&&thistype.equals(GLOBAL))
289 throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
290 lb.setGlobalThis(thistype);
292 lb.setGlobalThis(EITHER);//default value
295 if (!discovered.containsKey(lb)) {
297 lb.setGlobalReturn(LOCAL);
299 lb.setGlobalReturn(EITHER);
300 lb.setParent(currlb);
302 discovered.put(lb, lb);
303 if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
304 classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
305 classtolb.get(lb.getMethod().getClassDesc()).add(lb);
306 if (!methodtolb.containsKey(lb.getMethod()))
307 methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
308 methodtolb.get(lb.getMethod()).add(lb);
310 lb=discovered.get(lb);
311 Integer returnval=lb.getGlobalReturn();
312 currreturnval=merge(returnval, currreturnval);
313 if (!dependence.containsKey(lb))
314 dependence.put(lb, new HashSet<LocalityBinding>());
315 dependence.get(lb).add(currlb);
317 if (fc.getReturnTemp()!=null) {
318 currtable.put(fc.getReturnTemp(), currreturnval);
322 void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
323 Integer type=currtable.get(ffn.getSrc());
324 TempDescriptor dst=ffn.getDst();
325 if (type.equals(LOCAL)) {
326 if (ffn.getField().isGlobal())
327 currtable.put(dst,GLOBAL);
329 currtable.put(dst,LOCAL);
330 } else if (type.equals(GLOBAL)) {
332 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
333 if (ffn.getField().getType().isPrimitive())
334 currtable.put(dst, LOCAL); // primitives are local
336 currtable.put(dst, GLOBAL);
337 } else if (type.equals(EITHER)) {
338 if (ffn.getField().getType().isPrimitive())
339 currtable.put(dst, LOCAL); // primitives are local
340 else if (ffn.getField().isGlobal())
341 currtable.put(dst, GLOBAL);
343 currtable.put(dst, EITHER);
344 } else if (type.equals(CONFLICT)) {
345 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
349 //need to handle primitives
350 void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
351 Integer srctype=currtable.get(fsfn.getSrc());
352 Integer dsttype=currtable.get(fsfn.getDst());
354 if (dsttype.equals(LOCAL)) {
355 if (fsfn.getField().isGlobal()) {
356 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
357 throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
359 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
360 throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
362 } else if (dsttype.equals(GLOBAL)) {
364 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
365 //okay to store primitives in global object
366 if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive())
368 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
369 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
370 } else if (dsttype.equals(EITHER)) {
371 if (srctype.equals(CONFLICT))
372 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
373 } else if (dsttype.equals(CONFLICT)) {
374 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
378 void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
379 if (fn.isGlobal()&&!transaction) {
380 throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
383 currtable.put(fn.getDst(), GLOBAL);
385 currtable.put(fn.getDst(), LOCAL);
388 void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
389 /* Just propagate value */
390 currtable.put(fon.getDest(), currtable.get(fon.getLeft()));
393 void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
394 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
397 void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
399 if (fln.getValue()==null)
400 currtable.put(fln.getDst(), EITHER);
402 currtable.put(fln.getDst(), LOCAL);
405 void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
406 if(frn.getReturnTemp()!=null) {
407 Integer returntype=currtable.get(frn.getReturnTemp());
408 lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
412 void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
413 Integer srctype=currtable.get(fsen.getSrc());
414 Integer dsttype=currtable.get(fsen.getDst());
416 if (dsttype.equals(LOCAL)) {
417 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
418 throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation());
419 } else if (dsttype.equals(GLOBAL)) {
420 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
421 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
423 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
424 } else if (dsttype.equals(EITHER)) {
425 if (srctype.equals(CONFLICT))
426 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
427 } else if (dsttype.equals(CONFLICT)) {
428 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
432 void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
433 Integer type=currtable.get(fen.getSrc());
434 TempDescriptor dst=fen.getDst();
435 if (type.equals(LOCAL)) {
436 currtable.put(dst,LOCAL);
437 } else if (type.equals(GLOBAL)) {
439 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
440 currtable.put(dst, GLOBAL);
441 } else if (type.equals(EITHER)) {
442 currtable.put(dst, EITHER);
443 } else if (type.equals(CONFLICT)) {
444 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
448 void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
449 int atomic=atomictable.get(fen).intValue();
450 atomictable.put(fen, new Integer(atomic+1));
453 void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
454 int atomic=atomictable.get(fen).intValue();
455 atomictable.put(fen, new Integer(atomic-1));
458 private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
459 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
461 Set<FlatNode> toprocess=fm.getNodeSet();
463 while(!toprocess.isEmpty()) {
464 FlatNode fn=toprocess.iterator().next();
465 toprocess.remove(fn);
467 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
468 List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
470 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
471 for(int i=0;i<fn.numNext();i++) {
472 FlatNode fnnext=fn.getNext(i);
473 if (nodetotemps.containsKey(fnnext))
474 tempset.addAll(nodetotemps.get(fnnext));
476 tempset.removeAll(writes);
477 tempset.addAll(reads);
478 if (!nodetotemps.containsKey(fn)||
479 nodetotemps.get(fn).equals(tempset)) {
480 nodetotemps.put(fn, tempset);
481 for(int i=0;i<fn.numPrev();i++)
482 toprocess.add(fn.getPrev(i));
488 private void computeTempstoSave() {
489 for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator();lbit.hasNext();) {
490 LocalityBinding lb=lbit.next();
491 computeTempstoSave(lb);
495 /* Need to checkpoint all temps that could be read from along any
496 * path that are either:
497 1) Written to by any assignment inside the transaction
498 2) Read from a global temp.
500 Generate tempstosave map from
501 localitybinding->flatatomicenternode->Set<TempDescriptors>
504 private void computeTempstoSave(LocalityBinding lb) {
507 Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
508 Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
509 MethodDescriptor md=lb.getMethod();
510 FlatMethod fm=state.getMethodFlat(md);
512 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=computeLiveTemps(fm);
513 Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
514 tempstosave.put(lb, nodetosavetemps);
516 Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
518 HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
519 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
522 while(!toprocess.isEmpty()) {
523 FlatNode fn=toprocess.iterator().next();
524 toprocess.remove(fn);
525 boolean isatomic=atomictab.get(fn).intValue()>0;
527 atomictab.get(fn.getPrev(0)).intValue()==0) {
528 assert(fn.getPrev(0).kind()==FKind.FlatAtomicEnterNode);
529 nodemap.put(fn, (FlatAtomicEnterNode)fn);
530 nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
531 } else if (isatomic) {
532 FlatAtomicEnterNode atomicnode=nodemap.get(fn);
533 Set<TempDescriptor> livetemps=nodetotemps.get(fn);
534 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
535 List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
537 for(Iterator<TempDescriptor> tempit=livetemps.iterator();tempit.hasNext();) {
538 TempDescriptor tmp=tempit.next();
539 if (writes.contains(tmp)) {
540 nodetosavetemps.get(fn).add(tmp);
541 } else if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
542 nodetosavetemps.get(fn).add(tmp);
546 for(int i=0;i<fn.numNext();i++) {
547 FlatNode fnnext=fn.getNext(i);
548 if (!discovered.contains(fnnext)) {
549 discovered.add(fnnext);
550 toprocess.add(fnnext);
552 nodemap.put(fnnext, nodemap.get(fn));