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>();
196 lbstack.add(lbexecute);
199 lbset.add(lbexecute);
200 while(!lbstack.isEmpty()) {
201 LocalityBinding lb=lbstack.pop();
202 if (calldep.containsKey(lb)) {
203 Set<LocalityBinding> set=new HashSet<LocalityBinding>();
204 set.addAll(calldep.get(lb));
205 set.removeAll(lbset);
210 for(Iterator<LocalityBinding> lbit=discovered.keySet().iterator(); lbit.hasNext();) {
211 LocalityBinding lb=lbit.next();
212 if (!lbset.contains(lb)) {
214 classtolb.get(lb.getMethod().getClassDesc()).remove(lb);
215 methodtolb.get(lb.getMethod()).remove(lb);
220 public MethodDescriptor getStart() {
221 ClassDescriptor cd=typeutil.getClass(TypeUtil.ThreadClass);
222 for(Iterator methodit=cd.getMethodTable().getSet("staticStart").iterator(); methodit
224 MethodDescriptor md=(MethodDescriptor) methodit.next();
225 if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
229 throw new Error("Can't find Thread.run");
233 private void computeLocalityBindingsSTM() {
234 lbmain=new LocalityBinding(typeutil.getMain(), false);
235 lbmain.setGlobalReturn(STMEITHER);
236 lbmain.setGlobal(0, NORMAL);
237 lbtovisit.add(lbmain);
238 discovered.put(lbmain, lbmain);
239 if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
240 classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
241 classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
243 if (!methodtolb.containsKey(lbmain.getMethod()))
244 methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
245 methodtolb.get(lbmain.getMethod()).add(lbmain);
247 //Do this to force a virtual table number for the run method
248 lbrun=new LocalityBinding(getStart(), false);
249 lbrun.setGlobalReturn(STMEITHER);
250 lbrun.setGlobal(0,NORMAL);
251 lbtovisit.add(lbrun);
252 discovered.put(lbrun, lbrun);
253 if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
254 classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
255 classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
257 if (!methodtolb.containsKey(lbrun.getMethod()))
258 methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
259 methodtolb.get(lbrun.getMethod()).add(lbrun);
261 while(!lbtovisit.isEmpty()) {
262 LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
263 lbtovisit.remove(lb);
265 System.out.println("Analyzing "+lb);
267 Integer returnglobal=lb.getGlobalReturn();
268 MethodDescriptor md=lb.getMethod();
269 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
270 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
273 computeCallsFlagsSTM(md, lb, temptable, atomictable);
275 System.out.println("Error in "+md+" context "+lb);
279 temptab.put(lb, temptable);
280 atomictab.put(lb, atomictable);
282 if (md.getReturnType()!=null&&md.getReturnType().isPtr()&&!returnglobal.equals(lb.getGlobalReturn())) {
283 //return type is more precise now
284 //rerun everything that call us
285 lbtovisit.addAll(dependence.get(lb));
290 private static Integer mergestm(Integer a, Integer b) {
291 if (a==null||a.equals(STMEITHER))
293 if (b==null||b.equals(STMEITHER))
300 public void computeCallsFlagsSTM(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
301 FlatMethod fm=state.getMethodFlat(md);
302 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
303 tovisit.add(fm.getNext(0));
306 // Build table for initial node
307 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
308 temptable.put(fm, table);
309 atomictable.put(fm, lb.isAtomic() ? 1 : 0);
310 int offset=md.isStatic() ? 0 : 1;
311 if (!md.isStatic()) {
312 table.put(fm.getParameter(0), lb.getGlobalThis());
314 for(int i=offset; i<fm.numParameters(); i++) {
315 TempDescriptor temp=fm.getParameter(i);
316 Integer b=lb.isGlobal(i-offset);
322 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
324 while(!tovisit.isEmpty()) {
325 FlatNode fn=tovisit.iterator().next();
327 Set<TempDescriptor> liveset=livemap.get(fn);
328 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
330 for(int i=0; i<fn.numPrev(); i++) {
331 FlatNode prevnode=fn.getPrev(i);
332 if (atomictable.containsKey(prevnode)) {
333 atomicstate=atomictable.get(prevnode).intValue();
335 if (!temptable.containsKey(prevnode))
337 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
338 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext();) {
339 TempDescriptor temp=tempit.next();
340 if (!liveset.contains(temp))
342 Integer tmpint=prevtable.get(temp);
343 Integer oldint=currtable.containsKey(temp) ? currtable.get(temp) : STMEITHER;
344 Integer newint=mergestm(tmpint, oldint);
345 currtable.put(temp, newint);
348 atomictable.put(fn, atomicstate);
352 case FKind.FlatAtomicEnterNode:
353 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
358 case FKind.FlatAtomicExitNode:
359 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
363 processCallNodeSTM(lb, (FlatCall)fn, isAtomic(atomictable, fn), currtable, temptable.get(fn));
367 processNewSTM(lb, (FlatNew) fn, currtable);
370 case FKind.FlatFieldNode:
371 processFieldNodeSTM(lb, (FlatFieldNode) fn, currtable);
374 case FKind.FlatSetFieldNode:
375 processSetFieldNodeSTM(lb, (FlatSetFieldNode) fn, currtable);
378 case FKind.FlatSetElementNode:
379 processSetElementNodeSTM(lb, (FlatSetElementNode) fn, currtable);
382 case FKind.FlatElementNode:
383 processElementNodeSTM(lb, (FlatElementNode) fn, currtable);
386 case FKind.FlatOpNode:
387 processOpNodeSTM(lb, (FlatOpNode)fn, currtable);
390 case FKind.FlatCastNode:
391 processCastNodeSTM((FlatCastNode)fn, currtable);
394 case FKind.FlatReturnNode:
395 processReturnNodeSTM(lb, (FlatReturnNode)fn, currtable);
398 case FKind.FlatLiteralNode:
399 processLiteralNodeSTM((FlatLiteralNode)fn, currtable);
402 case FKind.FlatMethod:
403 case FKind.FlatOffsetNode:
404 case FKind.FlatInstanceOfNode:
405 case FKind.FlatCondBranch:
406 case FKind.FlatBackEdge:
408 case FKind.FlatPrefetchNode:
410 //No action needed for these
413 case FKind.FlatFlagActionNode:
414 case FKind.FlatCheckNode:
415 case FKind.FlatTagDeclaration:
416 throw new Error("Incompatible with tasks!");
419 throw new Error("In finding fn.kind()= " + fn.kind());
424 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
425 if (oldtable==null||!oldtable.equals(currtable)) {
426 // Update table for this node
427 temptable.put(fn, currtable);
428 for(int i=0; i<fn.numNext(); i++) {
429 tovisit.add(fn.getNext(i));
435 void processNewSTM(LocalityBinding lb, FlatNew fn, Hashtable<TempDescriptor, Integer> currtable) {
437 currtable.put(fn.getDst(), SCRATCH);
439 currtable.put(fn.getDst(), NORMAL);
442 void processCallNodeSTM(LocalityBinding currlb, FlatCall fc, boolean isatomic, Hashtable<TempDescriptor, Integer> currtable, Hashtable<TempDescriptor, Integer> oldtable) {
443 MethodDescriptor nodemd=fc.getMethod();
445 Set runmethodset=null;
447 if (nodemd.isStatic()||nodemd.getReturnType()==null) {
448 methodset=new HashSet();
449 methodset.add(nodemd);
451 methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
452 // Build start -> run link
453 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
454 nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
455 nodemd.numParameters()==0) {
456 assert(nodemd.getModifiers().isNative());
458 MethodDescriptor runmd=null;
459 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("staticStart").iterator(); methodit.hasNext();) {
460 MethodDescriptor md=(MethodDescriptor) methodit.next();
461 if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
467 runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
468 methodset.addAll(runmethodset);
469 } else throw new Error("Can't find run method");
473 Integer currreturnval=STMEITHER; //Start off with the either value
474 if (oldtable!=null&&fc.getReturnTemp()!=null&&
475 oldtable.get(fc.getReturnTemp())!=null) {
477 currreturnval=mergestm(currreturnval, oldtable.get(fc.getReturnTemp()));
480 for(Iterator methodit=methodset.iterator(); methodit.hasNext();) {
481 MethodDescriptor md=(MethodDescriptor) methodit.next();
483 boolean isnative=md.getModifiers().isNative();
484 boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
485 boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
486 boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
488 LocalityBinding lb=new LocalityBinding(md, isatomic);
489 if (isnative&&isatomic) {
490 System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
493 if (runmethodset==null||!runmethodset.contains(md)) {
494 for(int i=0; i<fc.numArgs(); i++) {
495 TempDescriptor arg=fc.getArg(i);
496 if (currtable.containsKey(arg))
497 lb.setGlobal(i,currtable.get(arg));
499 if (fc.getThis()!=null) {
500 Integer thistype=currtable.get(fc.getThis());
504 if(thistype.equals(STMCONFLICT))
505 throw new Error("Using type that can be either normal or scratch in context:\n"+currlb.getExplanation());
506 lb.setGlobalThis(thistype);
509 Integer thistype=currtable.get(fc.getThis());
510 if (!thistype.equals(NORMAL)&&!thistype.equals(STMEITHER)) {
511 throw new Error("Called start on possible scratch object"+thistype);
513 lb.setGlobal(0,currtable.get(fc.getThis()));
516 if (!discovered.containsKey(lb)) {
518 if (nodemd.getReturnType()!=null&&nodemd.getReturnType().isPtr())
519 lb.setGlobalReturn(NORMAL);
521 lb.setGlobalReturn(STMEITHER);
523 lb.setParent(currlb);
525 System.out.println("New lb:"+lb);
526 discovered.put(lb, lb);
527 if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
528 classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
529 classtolb.get(lb.getMethod().getClassDesc()).add(lb);
530 if (!methodtolb.containsKey(lb.getMethod()))
531 methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
532 methodtolb.get(lb.getMethod()).add(lb);
534 lb=discovered.get(lb);
535 Integer returnval=lb.getGlobalReturn();
536 currreturnval=mergestm(returnval, currreturnval);
537 if (!dependence.containsKey(lb))
538 dependence.put(lb, new HashSet<LocalityBinding>());
539 dependence.get(lb).add(currlb);
541 if (!calldep.containsKey(currlb))
542 calldep.put(currlb, new HashSet<LocalityBinding>());
543 calldep.get(currlb).add(lb);
545 if (fc.getReturnTemp()!=null&&fc.getReturnTemp().getType().isPtr()) {
546 currtable.put(fc.getReturnTemp(), currreturnval);
550 void processFieldNodeSTM(LocalityBinding lb, FlatFieldNode ffn, Hashtable<TempDescriptor, Integer> currtable) {
551 Integer type=currtable.get(ffn.getSrc());
552 TempDescriptor dst=ffn.getDst();
553 if (!ffn.getDst().getType().isPtr())
556 if (type.equals(SCRATCH)) {
557 currtable.put(dst,SCRATCH);
558 } else if (type.equals(NORMAL)) {
559 currtable.put(dst, NORMAL);
560 } else if (type.equals(STMEITHER)) {
561 currtable.put(dst, STMEITHER);
562 } else if (type.equals(STMCONFLICT)) {
563 throw new Error("Access to object that could be either normal or scratch in context:\n"+ffn+" "+lb.getExplanation());
567 //need to handle primitives
568 void processSetFieldNodeSTM(LocalityBinding lb, FlatSetFieldNode fsfn, Hashtable<TempDescriptor, Integer> currtable) {
569 Integer srctype=currtable.get(fsfn.getSrc());
570 Integer dsttype=currtable.get(fsfn.getDst());
571 if (!fsfn.getSrc().getType().isPtr())
575 System.out.println(fsfn);
576 if (dsttype.equals(SCRATCH)) {
577 if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
578 throw new Error("Writing possible normal reference to scratch object in context: \n"+lb.getExplanation());
579 } else if (dsttype.equals(NORMAL)) {
580 //okay to store primitives in global object
581 if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
582 throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
583 } else if (dsttype.equals(STMEITHER)) {
584 if (srctype.equals(STMCONFLICT))
585 throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
586 } else if (dsttype.equals(STMCONFLICT)) {
587 throw new Error("Access to object that could be either scratch or normal in context:\n"+lb.getExplanation());
591 void processSetElementNodeSTM(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable) {
592 Integer srctype=currtable.get(fsen.getSrc());
593 Integer dsttype=currtable.get(fsen.getDst());
594 if (!fsen.getSrc().getType().isPtr())
597 if (dsttype.equals(SCRATCH)) {
598 if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
599 throw new Error("Writing possible normal reference to scratch object in context:\n"+lb.getExplanation()+fsen);
600 } else if (dsttype.equals(NORMAL)) {
601 if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
602 throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation());
603 } else if (dsttype.equals(STMEITHER)) {
604 if (srctype.equals(STMCONFLICT))
605 throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
606 } else if (dsttype.equals(STMCONFLICT)) {
607 throw new Error("Access to object that could be either normal or scratch in context:\n"+lb.getExplanation());
611 void processOpNodeSTM(LocalityBinding lb, FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
612 /* Just propagate value */
613 if (!fon.getLeft().getType().isPtr())
616 Integer srcvalue=currtable.get(fon.getLeft());
618 if (srcvalue==null) {
619 System.out.println(fon);
620 MethodDescriptor md=lb.getMethod();
621 FlatMethod fm=state.getMethodFlat(md);
622 System.out.println(fm.printMethod());
623 throw new Error(fon.getLeft()+" is undefined!");
625 currtable.put(fon.getDest(), srcvalue);
628 void processCastNodeSTM(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
629 if (currtable.containsKey(fcn.getSrc()))
630 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
633 void processReturnNodeSTM(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
634 if(frn.getReturnTemp()!=null&&frn.getReturnTemp().getType().isPtr()) {
635 Integer returntype=currtable.get(frn.getReturnTemp());
636 lb.setGlobalReturn(mergestm(returntype, lb.getGlobalReturn()));
640 void processLiteralNodeSTM(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
642 if (fln.getType().isNull())
643 currtable.put(fln.getDst(), STMEITHER);
644 else if (fln.getType().isPtr())
645 currtable.put(fln.getDst(), NORMAL);
648 void processElementNodeSTM(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable) {
649 Integer type=currtable.get(fen.getSrc());
650 TempDescriptor dst=fen.getDst();
651 if (!fen.getDst().getType().isPtr())
655 System.out.println(fen +" in "+lb+" may access undefined variable");
656 MethodDescriptor md=lb.getMethod();
657 FlatMethod fm=state.getMethodFlat(md);
658 System.out.println(fm.printMethod());
660 } else if (type.equals(SCRATCH)) {
661 currtable.put(dst,SCRATCH);
662 } else if (type.equals(NORMAL)) {
663 currtable.put(dst, NORMAL);
664 } else if (type.equals(STMEITHER)) {
665 currtable.put(dst, STMEITHER);
666 } else if (type.equals(STMCONFLICT)) {
667 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
671 private void computeLocalityBindings() {
672 lbmain=new LocalityBinding(typeutil.getMain(), false);
673 lbmain.setGlobalReturn(EITHER);
674 lbmain.setGlobal(0, LOCAL);
675 lbtovisit.add(lbmain);
676 discovered.put(lbmain, lbmain);
677 if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
678 classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
679 classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
681 if (!methodtolb.containsKey(lbmain.getMethod()))
682 methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
683 methodtolb.get(lbmain.getMethod()).add(lbmain);
685 //Do this to force a virtual table number for the run method
686 lbrun=new LocalityBinding(typeutil.getRun(), false);
687 lbrun.setGlobalReturn(EITHER);
688 lbrun.setGlobalThis(GLOBAL);
689 lbtovisit.add(lbrun);
690 discovered.put(lbrun, lbrun);
691 if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
692 classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
693 classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
695 if (!methodtolb.containsKey(lbrun.getMethod()))
696 methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
697 methodtolb.get(lbrun.getMethod()).add(lbrun);
699 lbexecute = new LocalityBinding(typeutil.getExecute(), false);
700 lbexecute.setGlobalReturn(EITHER);
701 lbexecute.setGlobalThis(GLOBAL);
702 lbtovisit.add(lbexecute);
703 discovered.put(lbexecute, lbexecute);
704 if (!classtolb.containsKey(lbexecute.getMethod().getClassDesc()))
705 classtolb.put(lbexecute.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
706 classtolb.get(lbexecute.getMethod().getClassDesc()).add(lbexecute);
708 if (!methodtolb.containsKey(lbexecute.getMethod()))
709 methodtolb.put(lbexecute.getMethod(), new HashSet<LocalityBinding>());
710 methodtolb.get(lbexecute.getMethod()).add(lbexecute);
712 while(!lbtovisit.isEmpty()) {
713 LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
714 lbtovisit.remove(lb);
716 System.out.println("Analyzing "+lb);
717 Integer returnglobal=lb.getGlobalReturn();
718 MethodDescriptor md=lb.getMethod();
719 Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
720 Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
723 computeCallsFlags(md, lb, temptable, atomictable);
725 System.out.println("Error in "+md+" context "+lb);
729 temptab.put(lb, temptable);
730 atomictab.put(lb, atomictable);
732 if (md.getReturnType()!=null&&!returnglobal.equals(lb.getGlobalReturn())) {
733 //return type is more precise now
734 //rerun everything that call us
735 lbtovisit.addAll(dependence.get(lb));
743 public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
744 FlatMethod fm=state.getMethodFlat(md);
745 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
746 tovisit.add(fm.getNext(0));
748 // Build table for initial node
749 Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
750 temptable.put(fm, table);
751 atomictable.put(fm, lb.isAtomic() ? 1 : 0);
752 int offset=md.isStatic() ? 0 : 1;
753 if (!md.isStatic()) {
754 table.put(fm.getParameter(0), lb.getGlobalThis());
756 for(int i=offset; i<fm.numParameters(); i++) {
757 TempDescriptor temp=fm.getParameter(i);
758 Integer b=lb.isGlobal(i-offset);
763 while(!tovisit.isEmpty()) {
764 FlatNode fn=tovisit.iterator().next();
766 Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
768 for(int i=0; i<fn.numPrev(); i++) {
769 FlatNode prevnode=fn.getPrev(i);
770 if (atomictable.containsKey(prevnode)) {
771 atomicstate=atomictable.get(prevnode).intValue();
773 if (!temptable.containsKey(prevnode))
775 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
776 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext();) {
777 TempDescriptor temp=tempit.next();
778 Integer tmpint=prevtable.get(temp);
779 Integer oldint=currtable.containsKey(temp) ? currtable.get(temp) : EITHER;
780 Integer newint=merge(tmpint, oldint);
781 currtable.put(temp, newint);
784 atomictable.put(fn, atomicstate);
788 case FKind.FlatAtomicEnterNode:
789 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
794 case FKind.FlatAtomicExitNode:
795 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
799 processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn), temptable.get(fn));
802 case FKind.FlatFieldNode:
803 processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
806 case FKind.FlatSetFieldNode:
807 processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
811 processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
814 case FKind.FlatOpNode:
815 processOpNode((FlatOpNode)fn, currtable);
818 case FKind.FlatCastNode:
819 processCastNode((FlatCastNode)fn, currtable);
822 case FKind.FlatLiteralNode:
823 processLiteralNode((FlatLiteralNode)fn, currtable);
826 case FKind.FlatReturnNode:
827 processReturnNode(lb, (FlatReturnNode)fn, currtable);
830 case FKind.FlatSetElementNode:
831 processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
834 case FKind.FlatElementNode:
835 processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
838 case FKind.FlatInstanceOfNode:
839 case FKind.FlatCondBranch:
840 case FKind.FlatBackEdge:
843 case FKind.FlatPrefetchNode:
844 //No action needed for these
847 case FKind.FlatFlagActionNode:
848 case FKind.FlatCheckNode:
849 case FKind.FlatTagDeclaration:
850 throw new Error("Incompatible with tasks!");
852 case FKind.FlatMethod:
855 case FKind.FlatOffsetNode:
856 processOffsetNode((FlatOffsetNode)fn, currtable);
860 throw new Error("In finding fn.kind()= " + fn.kind());
862 Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
863 if (oldtable==null||!oldtable.equals(currtable)) {
864 // Update table for this node
865 temptable.put(fn, currtable);
866 for(int i=0; i<fn.numNext(); i++) {
867 tovisit.add(fn.getNext(i));
873 private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
874 return atomictable.get(fn).intValue()>0;
877 private static Integer merge(Integer a, Integer b) {
878 if (a==null||a.equals(EITHER))
880 if (b==null||b.equals(EITHER))
887 void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic, Hashtable<TempDescriptor,Integer> oldtable) {
888 MethodDescriptor nodemd=fc.getMethod();
890 Set runmethodset=null;
891 Set executemethodset=null;
893 if (nodemd.isStatic()||nodemd.getReturnType()==null) {
894 methodset=new HashSet();
895 methodset.add(nodemd);
897 methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
898 // Build start -> run link
899 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
900 nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
901 nodemd.numParameters()==1&&nodemd.getParamType(0).isInt()) {
902 assert(nodemd.getModifiers().isNative());
904 MethodDescriptor runmd=null;
906 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext();) {
907 MethodDescriptor md=(MethodDescriptor) methodit.next();
909 if (md.numParameters()!=0||md.getModifiers().isStatic())
915 runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
916 methodset.addAll(runmethodset);
917 } else throw new Error("Can't find run method");
920 if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.TaskClass) &&
921 nodemd.getSymbol().equals("execution") && !nodemd.getModifiers().isStatic() &&
922 nodemd.numParameters() == 0) {
923 assert(nodemd.getModifiers().isNative());
925 MethodDescriptor exemd = null;
927 for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("execute").iterator(); methodit.hasNext();) {
928 MethodDescriptor md = (MethodDescriptor) methodit.next();
930 if (md.numParameters() != 0 || md.getModifiers().isStatic())
937 executemethodset = callgraph.getMethods(exemd, fc.getThis().getType());
938 methodset.addAll(executemethodset);
939 } else throw new Error("Can't find execute method");
943 Integer currreturnval=EITHER; //Start off with the either value
944 if (oldtable!=null&&fc.getReturnTemp()!=null&&
945 oldtable.get(fc.getReturnTemp())!=null) {
947 currreturnval=merge(currreturnval, oldtable.get(fc.getReturnTemp()));
950 for(Iterator methodit=methodset.iterator(); methodit.hasNext();) {
951 MethodDescriptor md=(MethodDescriptor) methodit.next();
953 boolean isnative=md.getModifiers().isNative();
954 boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
955 boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
956 boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
958 LocalityBinding lb=new LocalityBinding(md, isatomic);
959 if (isnative&&isatomic) {
960 System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
963 if ((runmethodset==null||!runmethodset.contains(md)) &&( executemethodset == null || !executemethodset.contains(md))) {
964 //Skip this part if it is a run method or execute method
965 for(int i=0; i<fc.numArgs(); i++) {
966 TempDescriptor arg=fc.getArg(i);
967 if(isnative&&(currtable.get(arg).equals(GLOBAL)||
968 currtable.get(arg).equals(CONFLICT))&& !(nodemd.getSymbol().equals("rangePrefetch"))) {
969 throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
971 lb.setGlobal(i,currtable.get(arg));
975 if (fc.getThis()!=null) {
976 Integer thistype=currtable.get(fc.getThis());
980 if(runmethodset!=null&&runmethodset.contains(md)&&thistype.equals(LOCAL) && executemethodset != null && executemethodset.contains(md))
981 throw new Error("Starting thread on local object not allowed in context:\n"+currlb.getExplanation());
982 if(isjoin&&thistype.equals(LOCAL))
983 throw new Error("Joining thread on local object not allowed in context:\n"+currlb.getExplanation());
984 if(thistype.equals(CONFLICT))
985 throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
986 if(runmethodset==null&&thistype.equals(GLOBAL)&&!isatomic && !isjoin && executemethodset == null)
987 throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
988 if (runmethodset==null&&isnative&&thistype.equals(GLOBAL) && !isjoin && executemethodset == null && !isObjectgetType && !isObjecthashCode)
989 throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
990 lb.setGlobalThis(thistype);
993 if (!discovered.containsKey(lb)) {
995 lb.setGlobalReturn(LOCAL);
997 lb.setGlobalReturn(EITHER);
998 lb.setParent(currlb);
1000 discovered.put(lb, lb);
1001 if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
1002 classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
1003 classtolb.get(lb.getMethod().getClassDesc()).add(lb);
1004 if (!methodtolb.containsKey(lb.getMethod()))
1005 methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
1006 methodtolb.get(lb.getMethod()).add(lb);
1008 lb=discovered.get(lb);
1009 Integer returnval=lb.getGlobalReturn();
1010 currreturnval=merge(returnval, currreturnval);
1011 if (!dependence.containsKey(lb))
1012 dependence.put(lb, new HashSet<LocalityBinding>());
1013 dependence.get(lb).add(currlb);
1015 if (!calldep.containsKey(currlb))
1016 calldep.put(currlb, new HashSet<LocalityBinding>());
1017 calldep.get(currlb).add(lb);
1019 if (fc.getReturnTemp()!=null) {
1020 currtable.put(fc.getReturnTemp(), currreturnval);
1024 void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1025 Integer type=currtable.get(ffn.getSrc());
1026 TempDescriptor dst=ffn.getDst();
1027 if (type.equals(LOCAL)) {
1028 if (ffn.getField().isGlobal())
1029 currtable.put(dst,GLOBAL);
1031 currtable.put(dst,LOCAL);
1032 } else if (type.equals(GLOBAL)) {
1034 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1035 if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1036 currtable.put(dst, LOCAL); // primitives are local
1038 currtable.put(dst, GLOBAL);
1039 } else if (type.equals(EITHER)) {
1040 if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1041 currtable.put(dst, LOCAL); // primitives are local
1042 else if (ffn.getField().isGlobal())
1043 currtable.put(dst, GLOBAL);
1045 currtable.put(dst, EITHER);
1046 } else if (type.equals(CONFLICT)) {
1047 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1051 //need to handle primitives
1052 void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1053 Integer srctype=currtable.get(fsfn.getSrc());
1054 Integer dsttype=currtable.get(fsfn.getDst());
1056 if (dsttype.equals(LOCAL)) {
1057 if (fsfn.getField().isGlobal()) {
1058 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1059 throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
1061 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
1062 throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
1064 } else if (dsttype.equals(GLOBAL)) {
1066 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1067 //okay to store primitives in global object
1068 if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive() && !fsfn.getField().getType().isArray())
1070 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1071 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
1072 } else if (dsttype.equals(EITHER)) {
1073 if (srctype.equals(CONFLICT))
1074 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1075 } else if (dsttype.equals(CONFLICT)) {
1076 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1080 void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1081 if (fn.isGlobal()&&!transaction) {
1082 throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
1085 currtable.put(fn.getDst(), GLOBAL);
1087 currtable.put(fn.getDst(), LOCAL);
1090 void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
1091 /* Just propagate value */
1092 Integer srcvalue=currtable.get(fon.getLeft());
1094 if (srcvalue==null) {
1095 if (!fon.getLeft().getType().isPtr()) {
1098 throw new Error(fon.getLeft()+" is undefined!");
1100 currtable.put(fon.getDest(), srcvalue);
1103 void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
1104 currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
1107 void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1109 if (fln.getValue()==null)
1110 currtable.put(fln.getDst(), EITHER);
1112 currtable.put(fln.getDst(), LOCAL);
1115 void processOffsetNode(FlatOffsetNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1116 currtable.put(fln.getDst(), LOCAL);
1119 void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
1120 if(frn.getReturnTemp()!=null) {
1121 Integer returntype=currtable.get(frn.getReturnTemp());
1122 lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
1126 void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1127 Integer srctype=currtable.get(fsen.getSrc());
1128 Integer dsttype=currtable.get(fsen.getDst());
1130 if (dsttype.equals(LOCAL)) {
1131 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
1132 throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation()+fsen);
1133 } else if (dsttype.equals(GLOBAL)) {
1134 if (srctype.equals(LOCAL) && fsen.getDst().getType().dereference().isPrimitive() && !fsen.getDst().getType().dereference().isArray())
1136 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1137 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
1139 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1140 } else if (dsttype.equals(EITHER)) {
1141 if (srctype.equals(CONFLICT))
1142 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1143 } else if (dsttype.equals(CONFLICT)) {
1144 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1148 void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1149 Integer type=currtable.get(fen.getSrc());
1150 TempDescriptor dst=fen.getDst();
1151 if (type.equals(LOCAL)) {
1152 currtable.put(dst,LOCAL);
1153 } else if (type.equals(GLOBAL)) {
1155 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1156 if(fen.getSrc().getType().dereference().isPrimitive()&&
1157 !fen.getSrc().getType().dereference().isArray())
1158 currtable.put(dst, LOCAL);
1160 currtable.put(dst, GLOBAL);
1161 } else if (type.equals(EITHER)) {
1162 if(fen.getSrc().getType().dereference().isPrimitive()&&
1163 !fen.getSrc().getType().dereference().isArray())
1164 currtable.put(dst, LOCAL);
1166 currtable.put(dst, EITHER);
1167 } else if (type.equals(CONFLICT)) {
1168 throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1172 void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
1173 int atomic=atomictable.get(fen).intValue();
1174 atomictable.put(fen, new Integer(atomic+1));
1177 void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
1178 int atomic=atomictable.get(fen).intValue();
1179 atomictable.put(fen, new Integer(atomic-1));
1182 private void computeTempstoSave() {
1183 for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator(); lbit.hasNext();) {
1184 LocalityBinding lb=lbit.next();
1185 computeTempstoSave(lb);
1189 /* Need to checkpoint all temps that could be read from along any
1190 * path that are either:
1191 1) Written to by any assignment inside the transaction
1192 2) Read from a global temp.
1194 Generate tempstosave map from
1195 localitybinding->flatatomicenternode->Set<TempDescriptors>
1198 private void computeTempstoSave(LocalityBinding lb) {
1201 Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
1202 Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
1203 MethodDescriptor md=lb.getMethod();
1204 FlatMethod fm=state.getMethodFlat(md);
1205 Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=Liveness.computeLiveTemps(fm);
1206 Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
1207 tempstosave.put(lb, nodetosavetemps);
1208 Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
1209 HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
1210 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
1213 while(!toprocess.isEmpty()) {
1214 FlatNode fn=toprocess.iterator().next();
1215 toprocess.remove(fn);
1216 boolean isatomic=atomictab.get(fn).intValue()>0;
1218 atomictab.get(fn.getPrev(0)).intValue()==0) {
1219 assert(fn.getPrev(0).kind()==FKind.FlatAtomicEnterNode);
1220 nodemap.put(fn, (FlatAtomicEnterNode)fn);
1221 nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
1222 } else if (isatomic) {
1223 FlatAtomicEnterNode atomicnode=nodemap.get(fn);
1224 Set<TempDescriptor> livetemps=nodetotemps.get(atomicnode);
1225 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
1226 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
1228 for(Iterator<TempDescriptor> tempit=livetemps.iterator(); tempit.hasNext();) {
1229 TempDescriptor tmp=tempit.next();
1230 if (writes.contains(tmp)) {
1231 nodetosavetemps.get(atomicnode).add(tmp);
1232 } else if (state.DSM) {
1233 if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
1234 nodetosavetemps.get(atomicnode).add(tmp);
1236 } else if (state.SINGLETM) {
1237 if (reads.contains(tmp)&&tmp.getType().isPtr()&&temptab.get(fn).get(tmp)==NORMAL) {
1238 nodetosavetemps.get(atomicnode).add(tmp);
1243 for(int i=0; i<fn.numNext(); i++) {
1244 FlatNode fnnext=fn.getNext(i);
1245 if (!discovered.contains(fnnext)) {
1246 discovered.add(fnnext);
1247 toprocess.add(fnnext);
1249 nodemap.put(fnnext, nodemap.get(fn));