1 package Analysis.Locality;
3 import Analysis.Liveness;
5 import Analysis.CallGraph.CallGraph;
9 import IR.MethodDescriptor;
11 import Analysis.Liveness;
12 import IR.ClassDescriptor;
14 public class LocalityAnalysis {
17 Hashtable<LocalityBinding,LocalityBinding> discovered;
18 Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
19 Hashtable<LocalityBinding, Set<LocalityBinding>> calldep;
20 Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
21 Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
22 Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
23 Hashtable<ClassDescriptor, Set<LocalityBinding>> classtolb;
24 Hashtable<MethodDescriptor, Set<LocalityBinding>> methodtolb;
25 private LocalityBinding lbmain;
26 private LocalityBinding lbrun;
27 private LocalityBinding lbexecute;
31 public static final Integer LOCAL=new Integer(0);
32 public static final Integer GLOBAL=new Integer(1);
33 public static final Integer EITHER=new Integer(2);
34 public static final Integer CONFLICT=new Integer(3);
36 public static final Integer STMEITHER=new Integer(0);
37 public static final Integer SCRATCH=new Integer(4);
38 public static final Integer NORMAL=new Integer(8);
39 public static final Integer STMCONFLICT=new Integer(12);
41 public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
42 this.typeutil=typeutil;
44 this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
45 this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
46 this.calldep=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
47 this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
48 this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
49 this.lbtovisit=new HashSet();
50 this.callgraph=callgraph;
51 this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
52 this.classtolb=new Hashtable<ClassDescriptor, Set<LocalityBinding>>();
53 this.methodtolb=new Hashtable<MethodDescriptor, Set<LocalityBinding>>();
57 public LocalityBinding getMain() {
61 /** This method returns the set of LocalityBindings that a given
62 * flatcall could invoke */
64 public LocalityBinding getBinding(LocalityBinding currlb, FlatCall fc) {
65 boolean isatomic=getAtomic(currlb).get(fc).intValue()>0;
66 Hashtable<TempDescriptor, Integer> currtable=getNodePreTempInfo(currlb,fc);
67 MethodDescriptor md=fc.getMethod();
69 boolean isnative=md.getModifiers().isNative();
71 LocalityBinding lb=new LocalityBinding(md, isatomic);
73 for(int i=0; i<fc.numArgs(); i++) {
74 TempDescriptor arg=fc.getArg(i);
75 lb.setGlobal(i,currtable.get(arg));
78 if (state.DSM&&fc.getThis()!=null) {
79 Integer thistype=currtable.get(fc.getThis());
82 lb.setGlobalThis(thistype);
83 } else if (state.SINGLETM&&fc.getThis()!=null) {
84 Integer thistype=currtable.get(fc.getThis());
87 lb.setGlobalThis(thistype);
90 // lb.setGlobalThis(EITHER);//default value
91 if (discovered.containsKey(lb))
92 lb=discovered.get(lb);
93 else throw new Error();
98 /** This method returns a set of LocalityBindings for the parameter class. */
99 public Set<LocalityBinding> getClassBindings(ClassDescriptor cd) {
100 return classtolb.get(cd);
103 /** This method returns a set of LocalityBindings for the parameter method. */
105 public Set<LocalityBinding> getMethodBindings(MethodDescriptor md) {
106 return methodtolb.get(md);
109 public Set<MethodDescriptor> getMethods() {
110 return methodtolb.keySet();
113 /** This method returns a set of LocalityBindings. A
114 * LocalityBinding specifies a context a method can be invoked in.
115 * It specifies whether the method is in a transaction and whether
116 * its parameter objects are locals or globals. */
118 public Set<LocalityBinding> getLocalityBindings() {
119 return discovered.keySet();
122 /** This method returns a hashtable for a given LocalityBinding
123 * that tells the current local/global status of temps at the each
124 * node in the flat representation. */
126 public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
127 return temptab.get(lb);
130 /** This method returns a hashtable for a given LocalityBinding
131 * that tells the current local/global status of temps at the
132 * beginning of each node in the flat representation. */
134 public Hashtable<TempDescriptor, Integer> getNodePreTempInfo(LocalityBinding lb, FlatNode fn) {
135 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
136 Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable=getNodeTempInfo(lb);
138 for(int i=0; i<fn.numPrev(); i++) {
139 FlatNode prevnode=fn.getPrev(i);
140 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
141 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
142 TempDescriptor temp=tempit.next();
143 Integer tmpint=prevtable.get(temp);
144 Integer oldint=currtable.containsKey(temp)?currtable.get(temp):(state.DSM?EITHER:STMEITHER);
145 Integer newint=state.DSM?merge(tmpint, oldint):mergestm(tmpint, oldint);
146 currtable.put(temp, newint);
152 /** This method returns an hashtable for a given LocalitBinding
153 * that tells whether a node in the flat represenation is in a
154 * transaction or not. Integer values greater than 0 indicate
155 * that the node is in a transaction and give the nesting depth.
156 * The outermost AtomicEnterNode will have a value of 1 and the
157 * outermost AtomicExitNode will have a value of 0. */
159 public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
160 return atomictab.get(lb);
163 /** This methods returns a hashtable for a given LocalityBinding
164 * that tells which temps needs to be saved for each
165 * AtomicEnterNode. */
167 public Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> getTemps(LocalityBinding lb) {
168 return tempstosave.get(lb);
171 public Set<TempDescriptor> getTempSet(LocalityBinding lb) {
172 HashSet<TempDescriptor> set=new HashSet<TempDescriptor>();
173 Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> table=getTemps(lb);
175 for(Iterator<FlatAtomicEnterNode> faenit=table.keySet().iterator(); faenit.hasNext(); ) {
176 FlatAtomicEnterNode faen=faenit.next();
177 set.addAll(table.get(faen));
182 private void doAnalysis() {
184 computeLocalityBindingsSTM();
186 computeLocalityBindings();
187 computeTempstoSave();
191 private void cleanSets() {
192 HashSet<LocalityBinding> lbset=new HashSet<LocalityBinding>();
193 Stack<LocalityBinding> lbstack=new Stack<LocalityBinding>();
200 if(state.DSMTASK) { // when Task.java is used
201 lbstack.add(lbexecute);
202 lbset.add(lbexecute);
204 while(!lbstack.isEmpty()) {
205 LocalityBinding lb=lbstack.pop();
206 if (calldep.containsKey(lb)) {
207 Set<LocalityBinding> set=new HashSet<LocalityBinding>();
208 set.addAll(calldep.get(lb));
209 set.removeAll(lbset);
214 for(Iterator<LocalityBinding> lbit=discovered.keySet().iterator(); lbit.hasNext(); ) {
215 LocalityBinding lb=lbit.next();
216 if (!lbset.contains(lb)) {
218 classtolb.get(lb.getMethod().getClassDesc()).remove(lb);
219 methodtolb.get(lb.getMethod()).remove(lb);
224 public MethodDescriptor getStart() {
225 ClassDescriptor cd=typeutil.getClass(TypeUtil.ThreadClass);
226 for(Iterator methodit=cd.getMethodTable().getSet("staticStart").iterator(); methodit
228 MethodDescriptor md=(MethodDescriptor) methodit.next();
229 if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
233 throw new Error("Can't find Thread.run");
237 private void computeLocalityBindingsSTM() {
238 lbmain=new LocalityBinding(typeutil.getMain(), false);
239 lbmain.setGlobalReturn(STMEITHER);
240 lbmain.setGlobal(0, NORMAL);
241 lbtovisit.add(lbmain);
242 discovered.put(lbmain, lbmain);
243 if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
244 classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
245 classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
247 if (!methodtolb.containsKey(lbmain.getMethod()))
248 methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
249 methodtolb.get(lbmain.getMethod()).add(lbmain);
251 //Do this to force a virtual table number for the run method
252 lbrun=new LocalityBinding(getStart(), false);
253 lbrun.setGlobalReturn(STMEITHER);
254 lbrun.setGlobal(0,NORMAL);
255 lbtovisit.add(lbrun);
256 discovered.put(lbrun, lbrun);
257 if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
258 classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
259 classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
261 if (!methodtolb.containsKey(lbrun.getMethod()))
262 methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
263 methodtolb.get(lbrun.getMethod()).add(lbrun);
265 while(!lbtovisit.isEmpty()) {
266 LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
267 lbtovisit.remove(lb);
269 System.out.println("Analyzing "+lb);
271 Integer returnglobal=lb.getGlobalReturn();
272 MethodDescriptor md=lb.getMethod();
273 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
274 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
277 computeCallsFlagsSTM(md, lb, temptable, atomictable);
279 System.out.println("Error in "+md+" context "+lb);
283 temptab.put(lb, temptable);
284 atomictab.put(lb, atomictable);
286 if (md.getReturnType()!=null&&md.getReturnType().isPtr()&&!returnglobal.equals(lb.getGlobalReturn())) {
287 //return type is more precise now
288 //rerun everything that call us
289 lbtovisit.addAll(dependence.get(lb));
294 private static Integer mergestm(Integer a, Integer b) {
295 if (a==null||a.equals(STMEITHER))
297 if (b==null||b.equals(STMEITHER))
304 public void computeCallsFlagsSTM(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
305 FlatMethod fm=state.getMethodFlat(md);
306 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
307 tovisit.add(fm.getNext(0));
310 // Build table for initial node
311 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
312 temptable.put(fm, table);
313 atomictable.put(fm, lb.isAtomic()?1:0);
314 int offset=md.isStatic()?0:1;
315 if (!md.isStatic()) {
316 table.put(fm.getParameter(0), lb.getGlobalThis());
318 for(int i=offset; i<fm.numParameters(); i++) {
319 TempDescriptor temp=fm.getParameter(i);
320 Integer b=lb.isGlobal(i-offset);
326 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm,-1);
328 while(!tovisit.isEmpty()) {
329 FlatNode fn=tovisit.iterator().next();
331 Set<TempDescriptor> liveset=livemap.get(fn);
332 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
334 for(int i=0; i<fn.numPrev(); i++) {
335 FlatNode prevnode=fn.getPrev(i);
336 if (atomictable.containsKey(prevnode)) {
337 atomicstate=atomictable.get(prevnode).intValue();
339 if (!temptable.containsKey(prevnode))
341 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
342 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
343 TempDescriptor temp=tempit.next();
344 if (!liveset.contains(temp))
346 Integer tmpint=prevtable.get(temp);
347 Integer oldint=currtable.containsKey(temp)?currtable.get(temp):STMEITHER;
348 Integer newint=mergestm(tmpint, oldint);
349 currtable.put(temp, newint);
352 atomictable.put(fn, atomicstate);
356 case FKind.FlatAtomicEnterNode:
357 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
362 case FKind.FlatAtomicExitNode:
363 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
367 processCallNodeSTM(lb, (FlatCall)fn, isAtomic(atomictable, fn), currtable, temptable.get(fn));
371 processNewSTM(lb, (FlatNew) fn, currtable);
374 case FKind.FlatFieldNode:
375 processFieldNodeSTM(lb, (FlatFieldNode) fn, currtable);
378 case FKind.FlatSetFieldNode:
379 processSetFieldNodeSTM(lb, (FlatSetFieldNode) fn, currtable);
382 case FKind.FlatSetElementNode:
383 processSetElementNodeSTM(lb, (FlatSetElementNode) fn, currtable);
386 case FKind.FlatElementNode:
387 processElementNodeSTM(lb, (FlatElementNode) fn, currtable);
390 case FKind.FlatOpNode:
391 processOpNodeSTM(lb, (FlatOpNode)fn, currtable);
394 case FKind.FlatCastNode:
395 processCastNodeSTM((FlatCastNode)fn, currtable);
398 case FKind.FlatReturnNode:
399 processReturnNodeSTM(lb, (FlatReturnNode)fn, currtable);
402 case FKind.FlatLiteralNode:
403 processLiteralNodeSTM((FlatLiteralNode)fn, currtable);
406 case FKind.FlatMethod:
407 case FKind.FlatOffsetNode:
408 case FKind.FlatInstanceOfNode:
409 case FKind.FlatCondBranch:
410 case FKind.FlatBackEdge:
412 case FKind.FlatPrefetchNode:
414 //No action needed for these
417 case FKind.FlatFlagActionNode:
418 case FKind.FlatCheckNode:
419 case FKind.FlatTagDeclaration:
420 throw new Error("Incompatible with tasks!");
423 throw new Error("In finding fn.kind()= " + fn.kind());
428 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
429 if (oldtable==null||!oldtable.equals(currtable)) {
430 // Update table for this node
431 temptable.put(fn, currtable);
432 for(int i=0; i<fn.numNext(); i++) {
433 tovisit.add(fn.getNext(i));
439 void processNewSTM(LocalityBinding lb, FlatNew fn, Hashtable<TempDescriptor, Integer> currtable) {
441 currtable.put(fn.getDst(), SCRATCH);
443 currtable.put(fn.getDst(), NORMAL);
446 void processCallNodeSTM(LocalityBinding currlb, FlatCall fc, boolean isatomic, Hashtable<TempDescriptor, Integer> currtable, Hashtable<TempDescriptor, Integer> oldtable) {
447 MethodDescriptor nodemd=fc.getMethod();
449 Set runmethodset=null;
451 if (nodemd.isStatic()||nodemd.getReturnType()==null) {
452 methodset=new HashSet();
453 methodset.add(nodemd);
455 methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
456 // Build start -> run link
457 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
458 nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
459 nodemd.numParameters()==0) {
460 assert(nodemd.getModifiers().isNative());
462 MethodDescriptor runmd=null;
463 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("staticStart").iterator(); methodit.hasNext(); ) {
464 MethodDescriptor md=(MethodDescriptor) methodit.next();
465 if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
471 runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
472 methodset.addAll(runmethodset);
473 } else throw new Error("Can't find run method");
477 Integer currreturnval=STMEITHER; //Start off with the either value
478 if (oldtable!=null&&fc.getReturnTemp()!=null&&
479 oldtable.get(fc.getReturnTemp())!=null) {
481 currreturnval=mergestm(currreturnval, oldtable.get(fc.getReturnTemp()));
484 for(Iterator methodit=methodset.iterator(); methodit.hasNext(); ) {
485 MethodDescriptor md=(MethodDescriptor) methodit.next();
487 boolean isnative=md.getModifiers().isNative();
488 boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
489 boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
490 boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
492 LocalityBinding lb=new LocalityBinding(md, isatomic);
493 if (isnative&&isatomic) {
494 System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
497 if (runmethodset==null||!runmethodset.contains(md)) {
498 for(int i=0; i<fc.numArgs(); i++) {
499 TempDescriptor arg=fc.getArg(i);
500 if (currtable.containsKey(arg))
501 lb.setGlobal(i,currtable.get(arg));
503 if (fc.getThis()!=null) {
504 Integer thistype=currtable.get(fc.getThis());
508 if(thistype.equals(STMCONFLICT))
509 throw new Error("Using type that can be either normal or scratch in context:\n"+currlb.getExplanation());
510 lb.setGlobalThis(thistype);
513 Integer thistype=currtable.get(fc.getThis());
514 if (!thistype.equals(NORMAL)&&!thistype.equals(STMEITHER)) {
515 throw new Error("Called start on possible scratch object"+thistype);
517 lb.setGlobal(0,currtable.get(fc.getThis()));
520 if (!discovered.containsKey(lb)) {
522 if (nodemd.getReturnType()!=null&&nodemd.getReturnType().isPtr())
523 lb.setGlobalReturn(NORMAL);
525 lb.setGlobalReturn(STMEITHER);
527 lb.setParent(currlb);
529 System.out.println("New lb:"+lb);
530 discovered.put(lb, lb);
531 if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
532 classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
533 classtolb.get(lb.getMethod().getClassDesc()).add(lb);
534 if (!methodtolb.containsKey(lb.getMethod()))
535 methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
536 methodtolb.get(lb.getMethod()).add(lb);
538 lb=discovered.get(lb);
539 Integer returnval=lb.getGlobalReturn();
540 currreturnval=mergestm(returnval, currreturnval);
541 if (!dependence.containsKey(lb))
542 dependence.put(lb, new HashSet<LocalityBinding>());
543 dependence.get(lb).add(currlb);
545 if (!calldep.containsKey(currlb))
546 calldep.put(currlb, new HashSet<LocalityBinding>());
547 calldep.get(currlb).add(lb);
549 if (fc.getReturnTemp()!=null&&fc.getReturnTemp().getType().isPtr()) {
550 currtable.put(fc.getReturnTemp(), currreturnval);
554 void processFieldNodeSTM(LocalityBinding lb, FlatFieldNode ffn, Hashtable<TempDescriptor, Integer> currtable) {
555 Integer type=currtable.get(ffn.getSrc());
556 TempDescriptor dst=ffn.getDst();
557 if (!ffn.getDst().getType().isPtr())
560 if (type.equals(SCRATCH)) {
561 currtable.put(dst,SCRATCH);
562 } else if (type.equals(NORMAL)) {
563 currtable.put(dst, NORMAL);
564 } else if (type.equals(STMEITHER)) {
565 currtable.put(dst, STMEITHER);
566 } else if (type.equals(STMCONFLICT)) {
567 throw new Error("Access to object that could be either normal or scratch in context:\n"+ffn+" "+lb.getExplanation());
571 //need to handle primitives
572 void processSetFieldNodeSTM(LocalityBinding lb, FlatSetFieldNode fsfn, Hashtable<TempDescriptor, Integer> currtable) {
573 Integer srctype=currtable.get(fsfn.getSrc());
574 Integer dsttype=currtable.get(fsfn.getDst());
575 if (!fsfn.getSrc().getType().isPtr())
579 System.out.println(fsfn);
580 if (dsttype.equals(SCRATCH)) {
581 if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
582 throw new Error("Writing possible normal reference to scratch object in context: \n"+lb.getExplanation());
583 } else if (dsttype.equals(NORMAL)) {
584 //okay to store primitives in global object
585 if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
586 throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
587 } else if (dsttype.equals(STMEITHER)) {
588 if (srctype.equals(STMCONFLICT))
589 throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
590 } else if (dsttype.equals(STMCONFLICT)) {
591 throw new Error("Access to object that could be either scratch or normal in context:\n"+lb.getExplanation());
595 void processSetElementNodeSTM(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable) {
596 Integer srctype=currtable.get(fsen.getSrc());
597 Integer dsttype=currtable.get(fsen.getDst());
598 if (!fsen.getSrc().getType().isPtr())
601 if (dsttype.equals(SCRATCH)) {
602 if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
603 throw new Error("Writing possible normal reference to scratch object in context:\n"+lb.getExplanation()+fsen);
604 } else if (dsttype.equals(NORMAL)) {
605 if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
606 throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation());
607 } else if (dsttype.equals(STMEITHER)) {
608 if (srctype.equals(STMCONFLICT))
609 throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
610 } else if (dsttype.equals(STMCONFLICT)) {
611 throw new Error("Access to object that could be either normal or scratch in context:\n"+lb.getExplanation());
615 void processOpNodeSTM(LocalityBinding lb, FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
616 /* Just propagate value */
617 if (!fon.getLeft().getType().isPtr())
620 Integer srcvalue=currtable.get(fon.getLeft());
622 if (srcvalue==null) {
623 System.out.println(fon);
624 MethodDescriptor md=lb.getMethod();
625 FlatMethod fm=state.getMethodFlat(md);
626 System.out.println(fm.printMethod());
627 throw new Error(fon.getLeft()+" is undefined!");
629 currtable.put(fon.getDest(), srcvalue);
632 void processCastNodeSTM(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
633 if (currtable.containsKey(fcn.getSrc()))
634 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
637 void processReturnNodeSTM(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
638 if(frn.getReturnTemp()!=null&&frn.getReturnTemp().getType().isPtr()) {
639 Integer returntype=currtable.get(frn.getReturnTemp());
640 lb.setGlobalReturn(mergestm(returntype, lb.getGlobalReturn()));
644 void processLiteralNodeSTM(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
646 if (fln.getType().isNull())
647 currtable.put(fln.getDst(), STMEITHER);
648 else if (fln.getType().isPtr())
649 currtable.put(fln.getDst(), NORMAL);
652 void processElementNodeSTM(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable) {
653 Integer type=currtable.get(fen.getSrc());
654 TempDescriptor dst=fen.getDst();
655 if (!fen.getDst().getType().isPtr())
659 System.out.println(fen +" in "+lb+" may access undefined variable");
660 MethodDescriptor md=lb.getMethod();
661 FlatMethod fm=state.getMethodFlat(md);
662 System.out.println(fm.printMethod());
664 } else if (type.equals(SCRATCH)) {
665 currtable.put(dst,SCRATCH);
666 } else if (type.equals(NORMAL)) {
667 currtable.put(dst, NORMAL);
668 } else if (type.equals(STMEITHER)) {
669 currtable.put(dst, STMEITHER);
670 } else if (type.equals(STMCONFLICT)) {
671 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
675 private void computeLocalityBindings() {
676 lbmain=new LocalityBinding(typeutil.getMain(), false);
677 lbmain.setGlobalReturn(EITHER);
678 lbmain.setGlobal(0, LOCAL);
679 lbtovisit.add(lbmain);
680 discovered.put(lbmain, lbmain);
681 if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
682 classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
683 classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
685 if (!methodtolb.containsKey(lbmain.getMethod()))
686 methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
687 methodtolb.get(lbmain.getMethod()).add(lbmain);
689 //Do this to force a virtual table number for the run method
690 lbrun=new LocalityBinding(typeutil.getRun(), false);
691 lbrun.setGlobalReturn(EITHER);
692 lbrun.setGlobalThis(GLOBAL);
693 lbtovisit.add(lbrun);
694 discovered.put(lbrun, lbrun);
695 if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
696 classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
697 classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
699 if (!methodtolb.containsKey(lbrun.getMethod()))
700 methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
701 methodtolb.get(lbrun.getMethod()).add(lbrun);
704 lbexecute = new LocalityBinding(typeutil.getExecute(), false);
705 lbexecute.setGlobalReturn(EITHER);
706 lbexecute.setGlobalThis(GLOBAL);
707 lbtovisit.add(lbexecute);
708 discovered.put(lbexecute, lbexecute);
709 if (!classtolb.containsKey(lbexecute.getMethod().getClassDesc()))
710 classtolb.put(lbexecute.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
711 classtolb.get(lbexecute.getMethod().getClassDesc()).add(lbexecute);
713 if (!methodtolb.containsKey(lbexecute.getMethod()))
714 methodtolb.put(lbexecute.getMethod(), new HashSet<LocalityBinding>());
715 methodtolb.get(lbexecute.getMethod()).add(lbexecute);
718 while(!lbtovisit.isEmpty()) {
719 LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
720 lbtovisit.remove(lb);
722 System.out.println("Analyzing "+lb);
723 Integer returnglobal=lb.getGlobalReturn();
724 MethodDescriptor md=lb.getMethod();
725 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
726 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
729 computeCallsFlags(md, lb, temptable, atomictable);
731 System.out.println("Error in "+md+" context "+lb);
735 temptab.put(lb, temptable);
736 atomictab.put(lb, atomictable);
738 if (md.getReturnType()!=null&&!returnglobal.equals(lb.getGlobalReturn())) {
739 //return type is more precise now
740 //rerun everything that call us
741 lbtovisit.addAll(dependence.get(lb));
749 public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
750 FlatMethod fm=state.getMethodFlat(md);
751 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
752 tovisit.add(fm.getNext(0));
754 // Build table for initial node
755 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
756 temptable.put(fm, table);
757 atomictable.put(fm, lb.isAtomic()?1:0);
758 int offset=md.isStatic()?0:1;
759 if (!md.isStatic()) {
760 table.put(fm.getParameter(0), lb.getGlobalThis());
762 for(int i=offset; i<fm.numParameters(); i++) {
763 TempDescriptor temp=fm.getParameter(i);
764 Integer b=lb.isGlobal(i-offset);
769 while(!tovisit.isEmpty()) {
770 FlatNode fn=tovisit.iterator().next();
772 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
774 for(int i=0; i<fn.numPrev(); i++) {
775 FlatNode prevnode=fn.getPrev(i);
776 if (atomictable.containsKey(prevnode)) {
777 atomicstate=atomictable.get(prevnode).intValue();
779 if (!temptable.containsKey(prevnode))
781 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
782 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
783 TempDescriptor temp=tempit.next();
784 Integer tmpint=prevtable.get(temp);
785 Integer oldint=currtable.containsKey(temp)?currtable.get(temp):EITHER;
786 Integer newint=merge(tmpint, oldint);
787 currtable.put(temp, newint);
790 atomictable.put(fn, atomicstate);
794 case FKind.FlatAtomicEnterNode:
795 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
800 case FKind.FlatAtomicExitNode:
801 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
805 processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn), temptable.get(fn));
808 case FKind.FlatFieldNode:
809 processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
812 case FKind.FlatSetFieldNode:
813 processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
817 processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
820 case FKind.FlatOpNode:
821 processOpNode((FlatOpNode)fn, currtable);
824 case FKind.FlatCastNode:
825 processCastNode((FlatCastNode)fn, currtable);
828 case FKind.FlatLiteralNode:
829 processLiteralNode((FlatLiteralNode)fn, currtable);
832 case FKind.FlatReturnNode:
833 processReturnNode(lb, (FlatReturnNode)fn, currtable);
836 case FKind.FlatSetElementNode:
837 processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
840 case FKind.FlatElementNode:
841 processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
844 case FKind.FlatInstanceOfNode:
845 case FKind.FlatCondBranch:
846 case FKind.FlatBackEdge:
849 case FKind.FlatPrefetchNode:
850 //No action needed for these
853 case FKind.FlatFlagActionNode:
854 case FKind.FlatCheckNode:
855 case FKind.FlatTagDeclaration:
856 throw new Error("Incompatible with tasks!");
858 case FKind.FlatMethod:
861 case FKind.FlatOffsetNode:
862 processOffsetNode((FlatOffsetNode)fn, currtable);
866 throw new Error("In finding fn.kind()= " + fn.kind());
868 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
869 if (oldtable==null||!oldtable.equals(currtable)) {
870 // Update table for this node
871 temptable.put(fn, currtable);
872 for(int i=0; i<fn.numNext(); i++) {
873 tovisit.add(fn.getNext(i));
879 private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
880 return atomictable.get(fn).intValue()>0;
883 private static Integer merge(Integer a, Integer b) {
884 if (a==null||a.equals(EITHER))
886 if (b==null||b.equals(EITHER))
893 void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic, Hashtable<TempDescriptor,Integer> oldtable) {
894 MethodDescriptor nodemd=fc.getMethod();
896 Set runmethodset=null;
897 Set executemethodset=null;
899 if (nodemd.isStatic()||nodemd.getReturnType()==null) {
900 methodset=new HashSet();
901 methodset.add(nodemd);
903 methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
904 // Build start -> run link
905 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
906 nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
907 nodemd.numParameters()==1&&nodemd.getParamType(0).isInt()) {
908 assert(nodemd.getModifiers().isNative());
910 MethodDescriptor runmd=null;
912 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext(); ) {
913 MethodDescriptor md=(MethodDescriptor) methodit.next();
915 if (md.numParameters()!=0||md.getModifiers().isStatic())
921 runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
922 methodset.addAll(runmethodset);
923 } else throw new Error("Can't find run method");
927 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.TaskClass) &&
928 nodemd.getSymbol().equals("execution") && !nodemd.getModifiers().isStatic() &&
929 nodemd.numParameters() == 0) {
931 assert(nodemd.getModifiers().isNative());
932 MethodDescriptor exemd = null;
934 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("execute").iterator(); methodit.hasNext(); ) {
935 MethodDescriptor md = (MethodDescriptor) methodit.next();
937 if (md.numParameters() != 0 || md.getModifiers().isStatic())
944 executemethodset = callgraph.getMethods(exemd, fc.getThis().getType());
945 methodset.addAll(executemethodset);
946 } else throw new Error("Can't find execute method");
951 Integer currreturnval=EITHER; //Start off with the either value
952 if (oldtable!=null&&fc.getReturnTemp()!=null&&
953 oldtable.get(fc.getReturnTemp())!=null) {
955 currreturnval=merge(currreturnval, oldtable.get(fc.getReturnTemp()));
958 for(Iterator methodit=methodset.iterator(); methodit.hasNext(); ) {
959 MethodDescriptor md=(MethodDescriptor) methodit.next();
961 boolean isnative=md.getModifiers().isNative();
962 boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
963 boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
964 boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
966 LocalityBinding lb=new LocalityBinding(md, isatomic);
967 if (isnative&&isatomic) {
968 System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
971 if ((runmethodset==null||!runmethodset.contains(md)) &&( executemethodset == null || !executemethodset.contains(md))) {
972 //Skip this part if it is a run method or execute method
973 for(int i=0; i<fc.numArgs(); i++) {
974 TempDescriptor arg=fc.getArg(i);
975 if(isnative&&(currtable.get(arg).equals(GLOBAL)||
976 currtable.get(arg).equals(CONFLICT))&& !(nodemd.getSymbol().equals("rangePrefetch"))) {
977 throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
979 lb.setGlobal(i,currtable.get(arg));
983 if (fc.getThis()!=null) {
984 Integer thistype=currtable.get(fc.getThis());
988 if(runmethodset!=null&&runmethodset.contains(md)&&thistype.equals(LOCAL) && executemethodset != null && executemethodset.contains(md))
989 throw new Error("Starting thread on local object not allowed in context:\n"+currlb.getExplanation());
990 if(isjoin&&thistype.equals(LOCAL))
991 throw new Error("Joining thread on local object not allowed in context:\n"+currlb.getExplanation());
992 if(thistype.equals(CONFLICT))
993 throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
994 if(runmethodset==null&&thistype.equals(GLOBAL)&&!isatomic && !isjoin && executemethodset == null) {
995 throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
997 if (runmethodset==null&&isnative&&thistype.equals(GLOBAL) && !isjoin && executemethodset == null && !isObjectgetType && !isObjecthashCode)
998 throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
999 lb.setGlobalThis(thistype);
1002 if (!discovered.containsKey(lb)) {
1004 lb.setGlobalReturn(LOCAL);
1006 lb.setGlobalReturn(EITHER);
1007 lb.setParent(currlb);
1009 discovered.put(lb, lb);
1010 if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
1011 classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
1012 classtolb.get(lb.getMethod().getClassDesc()).add(lb);
1013 if (!methodtolb.containsKey(lb.getMethod()))
1014 methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
1015 methodtolb.get(lb.getMethod()).add(lb);
1017 lb=discovered.get(lb);
1018 Integer returnval=lb.getGlobalReturn();
1019 currreturnval=merge(returnval, currreturnval);
1020 if (!dependence.containsKey(lb))
1021 dependence.put(lb, new HashSet<LocalityBinding>());
1022 dependence.get(lb).add(currlb);
1024 if (!calldep.containsKey(currlb))
1025 calldep.put(currlb, new HashSet<LocalityBinding>());
1026 calldep.get(currlb).add(lb);
1028 if (fc.getReturnTemp()!=null) {
1029 currtable.put(fc.getReturnTemp(), currreturnval);
1033 void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1034 Integer type=currtable.get(ffn.getSrc());
1035 TempDescriptor dst=ffn.getDst();
1036 if (type.equals(LOCAL)) {
1037 if (ffn.getField().isGlobal())
1038 currtable.put(dst,GLOBAL);
1040 currtable.put(dst,LOCAL);
1041 } else if (type.equals(GLOBAL)) {
1043 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1044 if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1045 currtable.put(dst, LOCAL); // primitives are local
1047 currtable.put(dst, GLOBAL);
1048 } else if (type.equals(EITHER)) {
1049 if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1050 currtable.put(dst, LOCAL); // primitives are local
1051 else if (ffn.getField().isGlobal())
1052 currtable.put(dst, GLOBAL);
1054 currtable.put(dst, EITHER);
1055 } else if (type.equals(CONFLICT)) {
1056 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1060 //need to handle primitives
1061 void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1062 Integer srctype=currtable.get(fsfn.getSrc());
1063 Integer dsttype=currtable.get(fsfn.getDst());
1065 if (dsttype.equals(LOCAL)) {
1066 if (fsfn.getField().isGlobal()) {
1067 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1068 throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
1070 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER))) {
1071 throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
1074 } else if (dsttype.equals(GLOBAL)) {
1076 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1077 //okay to store primitives in global object
1078 if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive() && !fsfn.getField().getType().isArray())
1080 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1081 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
1082 } else if (dsttype.equals(EITHER)) {
1083 if (srctype.equals(CONFLICT))
1084 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1085 } else if (dsttype.equals(CONFLICT)) {
1086 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1090 void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1091 if (fn.isGlobal()&&!transaction) {
1092 throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
1095 currtable.put(fn.getDst(), GLOBAL);
1097 currtable.put(fn.getDst(), LOCAL);
1100 void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
1101 /* Just propagate value */
1102 Integer srcvalue=currtable.get(fon.getLeft());
1104 if (srcvalue==null) {
1105 if (!fon.getLeft().getType().isPtr()) {
1108 throw new Error(fon.getLeft()+" is undefined!");
1110 currtable.put(fon.getDest(), srcvalue);
1113 void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
1114 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
1117 void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1119 if (fln.getValue()==null)
1120 currtable.put(fln.getDst(), EITHER);
1122 currtable.put(fln.getDst(), LOCAL);
1125 void processOffsetNode(FlatOffsetNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1126 currtable.put(fln.getDst(), LOCAL);
1129 void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
1130 if(frn.getReturnTemp()!=null) {
1131 Integer returntype=currtable.get(frn.getReturnTemp());
1132 lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
1136 void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1137 Integer srctype=currtable.get(fsen.getSrc());
1138 Integer dsttype=currtable.get(fsen.getDst());
1140 if (dsttype.equals(LOCAL)) {
1141 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER))) {
1142 throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation()+fsen);
1144 } else if (dsttype.equals(GLOBAL)) {
1145 if (srctype.equals(LOCAL) && fsen.getDst().getType().dereference().isPrimitive() && !fsen.getDst().getType().dereference().isArray())
1147 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1148 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
1150 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1151 } else if (dsttype.equals(EITHER)) {
1152 if (srctype.equals(CONFLICT))
1153 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1154 } else if (dsttype.equals(CONFLICT)) {
1155 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1159 void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1160 Integer type=currtable.get(fen.getSrc());
1161 TempDescriptor dst=fen.getDst();
1162 if (type.equals(LOCAL)) {
1163 currtable.put(dst,LOCAL);
1164 } else if (type.equals(GLOBAL)) {
1166 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1167 if(fen.getSrc().getType().dereference().isPrimitive()&&
1168 !fen.getSrc().getType().dereference().isArray())
1169 currtable.put(dst, LOCAL);
1171 currtable.put(dst, GLOBAL);
1172 } else if (type.equals(EITHER)) {
1173 if(fen.getSrc().getType().dereference().isPrimitive()&&
1174 !fen.getSrc().getType().dereference().isArray())
1175 currtable.put(dst, LOCAL);
1177 currtable.put(dst, EITHER);
1178 } else if (type.equals(CONFLICT)) {
1179 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1183 void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
1184 int atomic=atomictable.get(fen).intValue();
1185 atomictable.put(fen, new Integer(atomic+1));
1188 void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
1189 int atomic=atomictable.get(fen).intValue();
1190 atomictable.put(fen, new Integer(atomic-1));
1193 private void computeTempstoSave() {
1194 for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator(); lbit.hasNext(); ) {
1195 LocalityBinding lb=lbit.next();
1196 computeTempstoSave(lb);
1200 /* Need to checkpoint all temps that could be read from along any
1201 * path that are either:
1202 1) Written to by any assignment inside the transaction
1203 2) Read from a global temp.
1205 Generate tempstosave map from
1206 localitybinding->flatatomicenternode->Set<TempDescriptors>
1209 private void computeTempstoSave(LocalityBinding lb) {
1212 Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
1213 Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
1214 MethodDescriptor md=lb.getMethod();
1215 FlatMethod fm=state.getMethodFlat(md);
1216 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=Liveness.computeLiveTemps(fm,-1);
1217 Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
1218 tempstosave.put(lb, nodetosavetemps);
1219 Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
1220 HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
1221 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
1224 while(!toprocess.isEmpty()) {
1225 FlatNode fn=toprocess.iterator().next();
1226 toprocess.remove(fn);
1227 boolean isatomic=atomictab.get(fn).intValue()>0;
1229 atomictab.get(fn.getPrev(0)).intValue()==0) {
1230 assert(fn.kind()==FKind.FlatAtomicEnterNode);
1231 nodemap.put(fn, (FlatAtomicEnterNode)fn);
1232 nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
1233 } else if (isatomic) {
1234 FlatAtomicEnterNode atomicnode=nodemap.get(fn);
1235 Set<TempDescriptor> livetemps=nodetotemps.get(atomicnode);
1236 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
1237 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
1239 for(Iterator<TempDescriptor> tempit=livetemps.iterator(); tempit.hasNext(); ) {
1240 TempDescriptor tmp=tempit.next();
1241 if (writes.contains(tmp)) {
1242 nodetosavetemps.get(atomicnode).add(tmp);
1243 } else if (state.DSM) {
1244 if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
1245 nodetosavetemps.get(atomicnode).add(tmp);
1247 } else if (state.SINGLETM) {
1248 if (reads.contains(tmp)&&tmp.getType().isPtr()&&temptab.get(fn).get(tmp)==NORMAL) {
1249 nodetosavetemps.get(atomicnode).add(tmp);
1254 for(int i=0; i<fn.numNext(); i++) {
1255 FlatNode fnnext=fn.getNext(i);
1256 if (!discovered.contains(fnnext)) {
1257 discovered.add(fnnext);
1258 toprocess.add(fnnext);
1260 nodemap.put(fnnext, nodemap.get(fn));