1 package Analysis.Prefetch;
4 import Analysis.CallGraph.CallGraph;
5 import Analysis.Prefetch.PrefetchPair;
6 import Analysis.Prefetch.PairMap;
7 import Analysis.Prefetch.IndexDescriptor;
11 import IR.MethodDescriptor;
14 import IR.ClassDescriptor;
16 public class PrefetchAnalysis {
20 Set<FlatNode> tovisit;
21 public Hashtable<FlatNode, Hashtable<PrefetchPair, Float>> prefetch_hash;
22 public Hashtable<FlatNode, Hashtable<FlatNode, PairMap>> pmap_hash;
23 Hashtable<PrefetchPair, Float> branch_prefetch_set;
24 LinkedList<FlatNode> newvisited;
25 Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash;
26 Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset;
27 public static final int PROB_DIFF = 10;
28 public static final float ANALYSIS_THRESHOLD_PROB = (float)0.10;
29 public static final float PREFETCH_THRESHOLD_PROB = (float)0.30;
30 public static final float BRANCH_TRUE_EDGE_PROB = (float)0.5;
31 public static final float BRANCH_FALSE_EDGE_PROB = (float)0.5;
33 public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
34 this.typeutil=typeutil;
36 this.callgraph=callgraph;
37 prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Float>>();
38 pmap_hash = new Hashtable<FlatNode, Hashtable<FlatNode, PairMap>>();
44 /** This function returns true if a tempdescriptor object is found in the array of descriptors
45 * for a given prefetch pair else returns false*/
46 private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) {
47 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
48 ListIterator it = desc.listIterator();
51 if(o instanceof IndexDescriptor) {
52 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
53 if(tdarray.contains(td)) {
61 /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
62 * tempdescriptors when there is a match */
63 private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) {
64 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
65 ListIterator it = desc.listIterator();
67 Object currdesc = it.next();
68 if(currdesc instanceof IndexDescriptor) {
69 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
70 if(tdarray.contains(td)) {
71 int index = tdarray.indexOf(td);
72 tdarray.set(index, newtd);
79 /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
80 * tempdescriptors when there is a match for e.g FlatOpNodes if i= i+j then replace i with i+j */
81 private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor left, TempDescriptor right) {
82 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
83 ListIterator it = desc.listIterator();
85 Object currdesc = it.next();
86 if(currdesc instanceof IndexDescriptor) {
87 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
88 if(tdarray.contains(td)) {
89 int index = tdarray.indexOf(td);
90 tdarray.set(index, left);
98 /** This function starts the prefetch analysis */
99 private void DoPrefetch() {
100 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
101 while(classit.hasNext()) {
102 ClassDescriptor cn=(ClassDescriptor)classit.next();
103 doMethodAnalysis(cn);
107 /** This function calls analysis for every method in a class */
108 private void doMethodAnalysis(ClassDescriptor cn) {
109 Iterator methodit=cn.getMethods();
110 while(methodit.hasNext()) {
111 newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
112 pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
113 MethodDescriptor md=(MethodDescriptor)methodit.next();
114 FlatMethod fm=state.getMethodFlat(md);
115 doFlatNodeAnalysis(fm);
116 doInsPrefetchAnalysis(fm);
117 if(newprefetchset.size() > 0) {
118 addFlatPrefetchNode(newprefetchset);
120 newprefetchset = null;
125 /** This function calls analysis for every node in a method */
126 private void doFlatNodeAnalysis(FlatMethod fm) {
127 tovisit = fm.getNodeSet();
128 Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
129 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
130 while(!tovisit.isEmpty()) {
131 FlatNode fn = (FlatNode)tovisit.iterator().next();
132 prefetch_hash.put(fn, nodehash);
138 /* Visit and process nodes */
139 tovisit = fm.getNodeSet();
140 while(!tovisit.isEmpty()) {
141 FlatNode fn = (FlatNode)tovisit.iterator().next();
142 doChildNodeAnalysis(fn);
148 * This function generates the prefetch sets for a given Flatnode considering the kind of node
149 * It calls severals functions based on the kind of the node and
150 * returns true: if the prefetch set has changed since last time the node was analysed
151 * returns false : otherwise
153 private void doChildNodeAnalysis(FlatNode curr) {
154 Hashtable<PrefetchPair, Float> child_prefetch_set_copy = new Hashtable<PrefetchPair, Float>();
155 Hashtable<FlatNode, PairMap> parentpmap = new Hashtable<FlatNode, PairMap>();
156 FlatNode child_node = null;
157 if(curr.numNext() != 0) {
158 child_node = curr.getNext(0);
159 if(prefetch_hash.containsKey(child_node)) {
160 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
164 switch(curr.kind()) {
165 case FKind.FlatBackEdge:
166 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
169 //TODO change it to take care of FlatMethod, Flatcalls
170 processFlatCall(curr, child_prefetch_set_copy, parentpmap);
172 case FKind.FlatCheckNode:
173 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
175 case FKind.FlatMethod:
176 //TODO change it to take care of FlatMethod, Flatcalls
177 processFlatMethod(curr, child_prefetch_set_copy, parentpmap);
180 processFlatNewNode(curr, child_prefetch_set_copy, parentpmap);
182 case FKind.FlatReturnNode:
183 //TODO change it to take care of FlatMethod, Flatcalls
184 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
186 case FKind.FlatFieldNode:
187 processFlatFieldNode(curr, child_prefetch_set_copy, parentpmap);
189 case FKind.FlatElementNode:
190 processFlatElementNode(curr, child_prefetch_set_copy, parentpmap);
192 case FKind.FlatCondBranch:
193 branch_prefetch_set = new Hashtable<PrefetchPair,Float>();
194 for (int i = 0; i < curr.numNext(); i++) {
195 parentpmap = new Hashtable<FlatNode, PairMap>();
196 child_node = curr.getNext(i);
197 if (prefetch_hash.containsKey(child_node)) {
198 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
200 processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, parentpmap);
203 branch_prefetch_set = null;
205 case FKind.FlatOpNode:
206 processFlatOpNode(curr, child_prefetch_set_copy, parentpmap);
208 case FKind.FlatLiteralNode:
209 processFlatLiteralNode(curr, child_prefetch_set_copy, parentpmap);
211 case FKind.FlatSetElementNode:
212 processFlatSetElementNode(curr, child_prefetch_set_copy, parentpmap);
214 case FKind.FlatSetFieldNode:
215 processFlatSetFieldNode(curr, child_prefetch_set_copy, parentpmap);
217 case FKind.FlatAtomicEnterNode:
218 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
220 case FKind.FlatAtomicExitNode:
221 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
223 case FKind.FlatCastNode:
224 processFlatCastNode(curr, child_prefetch_set_copy, parentpmap);
226 case FKind.FlatFlagActionNode:
227 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
229 case FKind.FlatGlobalConvNode:
230 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
233 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
235 case FKind.FlatTagDeclaration:
236 processFlatTagDeclaration(curr, child_prefetch_set_copy, parentpmap);
239 System.out.println("NO SUCH FLATNODE");
243 /* Free Heap Memory */
244 child_prefetch_set_copy = null;
248 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
249 * returns: true if something has changed in the new Prefetch set else
252 private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
254 boolean hasChanged = false;
255 PrefetchPair oldpp = null;
256 PrefetchPair newpp = null;
258 if(oldPrefetchSet.size() != newPrefetchSet.size()) {
259 if(newPrefetchSet.size() == 0) {
264 Enumeration e = newPrefetchSet.keys();
265 while(e.hasMoreElements()) {
266 newpp = (PrefetchPair) e.nextElement();
267 float newprob = newPrefetchSet.get(newpp);
268 for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
269 oldpp = (PrefetchPair) elem.nextElement();
270 if(oldpp.equals(newpp)) {
271 /*Compare the difference in their probabilities */
272 float oldprob = oldPrefetchSet.get(oldpp);
273 int diff = (int) ((newprob - oldprob)/oldprob)*100;
274 if(diff >= PROB_DIFF) {
285 /** This function processes the prefetch set of FlatFieldNode
286 * It generates a new prefetch set after comparision with its children
287 * Then compares it with its old prefetch set
288 * If old prefetch set is not same as new prefetch set then enqueue the parents
289 * of the current FlatFieldNode
291 private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
292 Hashtable<FlatNode, PairMap> parentpmap) {
293 boolean pSetHasChanged = false;
294 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
295 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
296 FlatFieldNode currffn = (FlatFieldNode) curr;
297 PairMap pm = new PairMap();
299 /* Do Self analysis of the current node*/
300 FieldDescriptor currffn_field = currffn.getField();
301 TempDescriptor currffn_src = currffn.getSrc();
302 if (currffn_field.getType().isPtr()) {
303 PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
304 Float prob = new Float((float)1.0);
305 currcopy.put(pp, prob);
308 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
309 Enumeration ecld = child_prefetch_set_copy.keys();
310 PrefetchPair currpp = null;
311 PrefetchPair childpp = null;
312 while (ecld.hasMoreElements()) {
313 childpp = (PrefetchPair) ecld.nextElement();
314 if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
315 if (currffn.getField().getType().isPtr()) {
316 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
317 newdesc.add(currffn.getField());
318 newdesc.addAll(childpp.desc);
319 PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc);
320 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
321 tocompare.put(newpp, newprob);
322 pm.addPair(childpp, newpp);
323 child_prefetch_set_copy.remove(childpp);
324 /* Check for independence of prefetch pairs to compute new probability */
325 if(child_prefetch_set_copy.containsKey(newpp)) {
326 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
327 if(newprob < ANALYSIS_THRESHOLD_PROB) {
328 tocompare.remove(newpp);
330 tocompare.put(newpp, newprob);
331 pm.addPair(newpp, newpp);
333 child_prefetch_set_copy.remove(newpp);
336 } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
337 child_prefetch_set_copy.remove(childpp);
342 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
343 * if so, calculate the new probability */
344 ecld = child_prefetch_set_copy.keys();
345 Enumeration e = null;
346 while(ecld.hasMoreElements()) {
347 childpp = (PrefetchPair) ecld.nextElement();
348 for(e = currcopy.keys(); e.hasMoreElements();) {
349 currpp = (PrefetchPair) e.nextElement();
350 if(currpp.equals(childpp)) {
351 Float prob = currcopy.get(currpp).floatValue();
352 currcopy.put(currpp, prob);
353 pm.addPair(childpp, currpp);
354 child_prefetch_set_copy.remove(childpp);
360 /* Merge child prefetch pairs */
361 ecld = child_prefetch_set_copy.keys();
362 while(ecld.hasMoreElements()) {
363 childpp = (PrefetchPair) ecld.nextElement();
364 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
365 pm.addPair(childpp, childpp);
366 child_prefetch_set_copy.remove(childpp);
369 /* Merge curr prefetch pairs */
371 while(e.hasMoreElements()) {
372 currpp = (PrefetchPair) e.nextElement();
373 tocompare.put(currpp, currcopy.get(currpp));
374 currcopy.remove(currpp);
377 /* Create prefetch mappings for child nodes */
379 parentpmap.put(curr, pm);
381 pmap_hash.put(curr.getNext(0), parentpmap);
383 /* Compare with the orginal prefetch pairs */
384 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
385 /* Enqueue parent nodes */
387 for(int i=0; i<curr.numPrev(); i++) {
388 tovisit.add(curr.getPrev(i));
390 /* Overwrite the new prefetch set to the global hash table */
391 prefetch_hash.put(curr,tocompare);
394 /* Free Heap Memory */
400 /** This function processes the prefetch set of a FlatElementNode
401 * It generates a new prefetch set after comparision with its children
402 * It compares the old prefetch set with this new prefetch set and enqueues the parents
403 * of the current node if change occurs and updates the global flatnode hash table
405 private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
406 Hashtable<FlatNode, PairMap> parentpmap) {
408 boolean pSetHasChanged = false;
409 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
410 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
411 FlatElementNode currfen = (FlatElementNode) curr;
412 PairMap pm = new PairMap();
415 /* Do Self analysis of the current node*/
416 TempDescriptor currfen_index = currfen.getIndex();
417 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
418 TempDescriptor currfen_src = currfen.getSrc();
419 if(currfen.getDst().getType().isPtr()) {
420 PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
421 Float prob = new Float((float)1.0);
422 currcopy.put(pp, prob);
425 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
426 Enumeration ecld = child_prefetch_set_copy.keys();
427 PrefetchPair currpp = null;
428 PrefetchPair childpp = null;
429 while (ecld.hasMoreElements()) {
430 childpp = (PrefetchPair) ecld.nextElement();
431 if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
432 if (currfen.getDst().getType().isPtr()) {
433 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
434 newdesc.add((Descriptor)idesc);
435 newdesc.addAll(childpp.desc);
436 PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc);
437 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
438 tocompare.put(newpp, newprob);
439 pm.addPair(childpp, newpp);
440 child_prefetch_set_copy.remove(childpp);
441 /* Check for independence of prefetch pairs to compute new probability */
442 if(child_prefetch_set_copy.containsKey(newpp)) {
443 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
444 if(newprob < ANALYSIS_THRESHOLD_PROB) {
445 tocompare.remove(newpp);
447 tocompare.put(newpp, newprob);
448 pm.addPair(newpp, newpp);
450 child_prefetch_set_copy.remove(newpp);
453 } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
454 child_prefetch_set_copy.remove(childpp);
457 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
458 * if so calculate the new probability */
459 ecld = child_prefetch_set_copy.keys();
460 Enumeration e = null;
461 while(ecld.hasMoreElements()) {
462 childpp = (PrefetchPair) ecld.nextElement();
463 for(e = currcopy.keys(); e.hasMoreElements();) {
464 currpp = (PrefetchPair) e.nextElement();
465 if(currpp.equals(childpp)) {
466 Float prob = currcopy.get(currpp).floatValue();
467 currcopy.put(currpp, prob);
468 pm.addPair(childpp, currpp);
469 child_prefetch_set_copy.remove(childpp);
475 /* Merge child prefetch pairs */
476 ecld = child_prefetch_set_copy.keys();
477 while(ecld.hasMoreElements()) {
478 childpp = (PrefetchPair) ecld.nextElement();
479 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
480 pm.addPair(childpp, childpp);
481 child_prefetch_set_copy.remove(childpp);
484 /* Merge curr prefetch pairs */
486 while(e.hasMoreElements()) {
487 currpp = (PrefetchPair) e.nextElement();
488 tocompare.put(currpp, currcopy.get(currpp));
489 currcopy.remove(currpp);
492 /* Create prefetch mappings for child nodes */
494 parentpmap.put(curr, pm);
496 pmap_hash.put(curr.getNext(0), parentpmap);
498 /* Compare with the orginal prefetch pairs */
499 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
500 /* Enqueue parent nodes */
502 for(int i=0; i<curr.numPrev(); i++) {
503 tovisit.add(curr.getPrev(i));
505 /* Overwrite the new prefetch set to the global hash table */
506 prefetch_hash.put(curr,tocompare);
509 /* Free heap memory */
515 /** This function processes the prefetch set of a FlatSetFieldNode
516 * It generates a new prefetch set after comparision with its children
517 * It compares the old prefetch set with this new prefetch set and enqueues the parents
518 * of the current node if change occurs and then updates the global flatnode hash table
520 private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
521 Hashtable<FlatNode, PairMap> parentpmap) {
522 boolean pSetHasChanged = false;
523 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
524 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
525 PrefetchPair childpp = null;
526 PairMap pm = new PairMap();
528 Enumeration ecld = child_prefetch_set_copy.keys();
529 while (ecld.hasMoreElements()) {
530 childpp = (PrefetchPair) ecld.nextElement();
531 if(childpp.base == currfsfn.getDst()) {
532 int size = childpp.desc.size();
533 if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
534 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
535 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
536 for(int i = 0;i<(childpp.desc.size()-1); i++) {
537 newdesc.add(i,childpp.desc.get(i+1));
539 PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc);
540 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
541 tocompare.put(newpp, newprob);
542 pm.addPair(childpp, newpp);
543 child_prefetch_set_copy.remove(childpp);
544 /* Check for independence of prefetch pairs in newly generated prefetch pair
545 * to compute new probability */
546 if(child_prefetch_set_copy.containsKey(newpp)) {
547 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
548 if(newprob < ANALYSIS_THRESHOLD_PROB) {
549 tocompare.remove(newpp);
551 tocompare.put(newpp, newprob);
552 pm.addPair(newpp, newpp);
554 child_prefetch_set_copy.remove(newpp);
557 } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */
558 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
559 child_prefetch_set_copy.remove(childpp);
567 /* Merge child prefetch pairs */
568 ecld = child_prefetch_set_copy.keys();
569 while(ecld.hasMoreElements()) {
570 childpp = (PrefetchPair) ecld.nextElement();
571 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
572 pm.addPair(childpp, childpp);
573 child_prefetch_set_copy.remove(childpp);
576 /* Create prefetch mappings for child nodes */
578 parentpmap.put(curr, pm);
580 pmap_hash.put(curr.getNext(0), parentpmap);
582 /* Compare with the orginal prefetch pairs */
583 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
584 /* Enqueue parent nodes */
586 for(int i=0; i<curr.numPrev(); i++) {
587 tovisit.add(curr.getPrev(i));
589 /* Overwrite the new prefetch set to the global hash table */
590 prefetch_hash.put(curr,tocompare);
593 /* Free heap memory */
598 /** This function processes the prefetch set of a FlatSetElementNode
599 * It generates a new prefetch set after comparision with its children
600 * It compares the old prefetch set with this new prefetch set and enqueues the parents
601 * of the current node if change occurs and then updates the global flatnode hash table
603 private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
604 Hashtable<FlatNode, PairMap> parentpmap) {
605 boolean pSetHasChanged = false;
606 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
607 PrefetchPair childpp = null;
608 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
609 PairMap pm = new PairMap();
611 Enumeration ecld = child_prefetch_set_copy.keys();
612 while (ecld.hasMoreElements()) {
613 childpp = (PrefetchPair) ecld.nextElement();
614 if (childpp.base == currfsen.getDst()){
615 int sizedesc = childpp.desc.size();
616 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
617 int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
618 if(sizetempdesc == 1) {
619 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
620 /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
621 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
622 for(int i = 0;i<(childpp.desc.size()-1); i++) {
623 newdesc.add(i,childpp.desc.get(i+1));
625 PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc);
626 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
627 tocompare.put(newpp, newprob);
628 pm.addPair(childpp, newpp);
629 child_prefetch_set_copy.remove(childpp);
630 /* Check for independence of prefetch pairs to compute new probability */
631 if(child_prefetch_set_copy.containsKey(newpp)) {
632 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
633 if(newprob < ANALYSIS_THRESHOLD_PROB) {
634 tocompare.remove(newpp);
636 tocompare.put(newpp, newprob);
637 pm.addPair(newpp, newpp);
639 child_prefetch_set_copy.remove(newpp);
641 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
642 /* For e.g. a[i] = g with child prefetch set a[i] */
643 child_prefetch_set_copy.remove(childpp);
650 /* Merge child prefetch pairs */
651 ecld = child_prefetch_set_copy.keys();
652 while(ecld.hasMoreElements()) {
653 childpp = (PrefetchPair) ecld.nextElement();
654 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
655 pm.addPair(childpp, childpp);
656 child_prefetch_set_copy.remove(childpp);
659 /* Create prefetch mappings for child nodes */
661 parentpmap.put(curr, pm);
663 pmap_hash.put(curr.getNext(0), parentpmap);
665 /* Compare with the orginal prefetch pairs */
666 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
667 /* Enqueue parent nodes */
669 for(int i=0; i<curr.numPrev(); i++) {
670 tovisit.add(curr.getPrev(i));
672 /* Overwrite the new prefetch set to the global hash table */
673 prefetch_hash.put(curr,tocompare);
675 /* Free heap memory */
680 /** This function applies rules and does analysis for a FlatOpNode
681 * And updates the global prefetch hashtable
683 private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
684 Hashtable<FlatNode, PairMap> parentpmap) {
685 boolean pSetHasChanged = false;
687 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
688 FlatOpNode currfopn = (FlatOpNode) curr;
689 Enumeration ecld = null;
690 PrefetchPair childpp = null;
691 PairMap pm = new PairMap();
693 if(currfopn.getOp().getOp()== Operation.ASSIGN) {
694 ecld = child_prefetch_set_copy.keys();
695 while (ecld.hasMoreElements()) {
696 childpp = (PrefetchPair) ecld.nextElement();
697 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
699 /* For cases like x=y with child prefetch set x[i].z,x.g*/
700 if(childpp.base == currfopn.getDest()) {
701 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
702 newdesc.addAll(childpp.desc);
703 PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc);
704 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
705 tocompare.put(newpp, newprob);
706 pm.addPair(childpp, newpp);
707 child_prefetch_set_copy.remove(childpp);
708 /* Check for independence of prefetch pairs to compute new probability */
709 if(child_prefetch_set_copy.containsKey(newpp)) {
710 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
711 if(newprob < ANALYSIS_THRESHOLD_PROB) {
712 tocompare.remove(newpp);
714 tocompare.put(newpp, newprob);
715 pm.addPair(newpp, newpp);
717 child_prefetch_set_copy.remove(newpp);
721 /* For cases like x=y with child prefetch set r[i].x, r[x].p, r[p+x].q*/
722 } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
723 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
724 newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
725 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
726 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
727 tocompare.put(newpp, newprob);
728 pm.addPair(childpp, newpp);
729 child_prefetch_set_copy.remove(childpp);
730 /* Check for independence of prefetch pairs to compute new probability*/
731 if(child_prefetch_set_copy.containsKey(newpp)) {
732 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
733 if(newprob < ANALYSIS_THRESHOLD_PROB) {
734 tocompare.remove(newpp);
736 tocompare.put(newpp, newprob);
737 pm.addPair(newpp, newpp);
739 child_prefetch_set_copy.remove(newpp);
747 //case i = i+z with child prefetch set a[i].x
748 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
749 ecld = child_prefetch_set_copy.keys();
750 while (ecld.hasMoreElements()) {
751 childpp = (PrefetchPair) ecld.nextElement();
752 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
754 if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
755 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
756 newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight()));
757 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
758 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
759 tocompare.put(newpp, newprob);
760 pm.addPair(childpp, newpp);
761 child_prefetch_set_copy.remove(childpp);
762 /* Check for independence of prefetch pairs to compute new probability*/
763 if(child_prefetch_set_copy.containsKey(newpp)) {
764 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
765 if(newprob < ANALYSIS_THRESHOLD_PROB) {
766 tocompare.remove(newpp);
768 tocompare.put(newpp, newprob);
769 pm.addPair(newpp, newpp);
771 child_prefetch_set_copy.remove(newpp);
778 //FIXME Is not taken care of for cases like x = -y followed by a[x].i
781 /* Merge child prefetch pairs */
782 ecld = child_prefetch_set_copy.keys();
783 while(ecld.hasMoreElements()) {
784 childpp = (PrefetchPair) ecld.nextElement();
785 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
786 pm.addPair(childpp, childpp);
787 child_prefetch_set_copy.remove(childpp);
790 /* Create prefetch mappings for child nodes */
792 parentpmap.put(curr, pm);
794 pmap_hash.put(curr.getNext(0), parentpmap);
796 /* Compare with the orginal prefetch pairs */
797 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
798 /* Enqueue parent nodes */
800 for(int i=0; i<curr.numPrev(); i++) {
801 tovisit.add(curr.getPrev(i));
803 /* Overwrite the new prefetch set to the global hash table */
804 prefetch_hash.put(curr,tocompare);
806 /* Free heap memory */
811 /** This function processes a FlatLiteralNode where cases such as
812 * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r
814 private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
815 Hashtable<FlatNode, PairMap> parentpmap) {
816 boolean pSetHasChanged = false;
817 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
818 FlatLiteralNode currfln = (FlatLiteralNode) curr;
819 Enumeration ecld = null;
820 PrefetchPair childpp = null;
821 PairMap pm = new PairMap();
823 if(currfln.getType().isIntegerType()) {
824 ecld = child_prefetch_set_copy.keys();
825 while (ecld.hasMoreElements()) {
826 childpp = (PrefetchPair) ecld.nextElement();
827 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
828 if(isTempDescFound(copyofchildpp,currfln.getDst())) {
829 ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
830 int sizetempdesc = copychilddesc.size();
831 ListIterator it = copychilddesc.listIterator();
832 for(;it.hasNext();) {
833 Object o = it.next();
834 if(o instanceof IndexDescriptor) {
835 ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
836 int sizetddesc = td.size();
837 if(td.contains(currfln.getDst())) {
838 int index = td.indexOf(currfln.getDst());
840 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
844 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
845 newdesc.addAll(copychilddesc);
846 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
847 Float newprob = (child_prefetch_set_copy.get(childpp)).floatValue();
848 tocompare.put(newpp, newprob);
849 pm.addPair(childpp, newpp);
850 child_prefetch_set_copy.remove(childpp);
851 /* Check for independence of prefetch pairs to compute new probability */
852 if(child_prefetch_set_copy.containsKey(newpp)) {
853 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
854 if(newprob < ANALYSIS_THRESHOLD_PROB) {
855 tocompare.remove(newpp);
857 tocompare.put(newpp, newprob);
858 pm.addPair(newpp, newpp);
860 child_prefetch_set_copy.remove(newpp);
866 /* Merge child prefetch pairs */
867 ecld = child_prefetch_set_copy.keys();
868 while(ecld.hasMoreElements()) {
869 childpp = (PrefetchPair) ecld.nextElement();
870 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
871 pm.addPair(childpp, childpp);
872 child_prefetch_set_copy.remove(childpp);
875 /* Create prefetch mappings for child nodes */
877 parentpmap.put(curr, pm);
879 pmap_hash.put(curr.getNext(0), parentpmap);
881 /* Compare with the orginal prefetch pairs */
882 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
883 /* Enqueue parent nodes */
885 for(int i=0; i<curr.numPrev(); i++) {
886 tovisit.add(curr.getPrev(i));
888 /* Overwrite the new prefetch set to the global hash table */
889 prefetch_hash.put(curr,tocompare);
891 /* Free heap memory */
896 /** This function processes a FlatMethod where the method propagates
897 * the entire prefetch set of its child node */
898 private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
899 Hashtable<FlatNode, PairMap> parentpmap) {
900 boolean pSetHasChanged = false;
901 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
902 FlatMethod currfm = (FlatMethod) curr;
903 Enumeration ecld = null;
904 PrefetchPair childpp = null;
905 PairMap pm = new PairMap();
907 /* Merge child prefetch pairs */
908 ecld = child_prefetch_set_copy.keys();
909 while(ecld.hasMoreElements()) {
910 childpp = (PrefetchPair) ecld.nextElement();
911 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
912 pm.addPair(childpp, childpp);
913 child_prefetch_set_copy.remove(childpp);
916 /* Create prefetch mappings for child nodes */
918 parentpmap.put(curr, pm);
920 pmap_hash.put(curr.getNext(0), parentpmap);
922 /* Compare with the orginal prefetch pairs */
923 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
924 /* Enqueue parent nodes */
926 /* Overwrite the new prefetch set to the global hash table */
927 prefetch_hash.put(curr,tocompare);
933 /** This Function processes the FlatCalls
934 * It currently drops the propagation of those prefetchpairs whose base is
935 * same as the destination of the FlatCall
937 private void processFlatCall(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
938 Hashtable<FlatNode, PairMap> parentpmap) {
939 boolean pSetHasChanged = false;
940 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
941 FlatCall currfcn = (FlatCall) curr;
942 PairMap pm = new PairMap();
943 Enumeration ecld = null;
944 PrefetchPair childpp = null;
946 ecld = child_prefetch_set_copy.keys();
947 while(ecld.hasMoreElements()) {
948 childpp = (PrefetchPair) ecld.nextElement();
949 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
950 if(currfcn.getReturnTemp() != childpp.base) {
951 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
952 pm.addPair(childpp, childpp);
953 child_prefetch_set_copy.remove(childpp);
955 child_prefetch_set_copy.remove(childpp);
959 /* Create prefetch mappings for child nodes */
961 parentpmap.put(curr, pm);
963 pmap_hash.put(curr.getNext(0), parentpmap);
965 /* Compare with the orginal prefetch pairs */
966 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
967 /* Enqueue parent nodes */
969 for(int i=0; i<curr.numPrev(); i++) {
970 tovisit.add(curr.getPrev(i));
972 /* Overwrite the new prefetch set to the global hash table */
973 prefetch_hash.put(curr,tocompare);
975 /* Free heap memory */
980 /** This function handles the processes the FlatNode of type FlatCondBranch
981 * It combines prefetches of both child elements and create a new hash table called
982 * branch_prefetch_set to contains the entries of both its children
984 private void processFlatCondBranch(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy, int index,
985 Hashtable<PrefetchPair,Float> branch_prefetch_set, Hashtable<FlatNode, PairMap> parentpmap) {
986 boolean pSetHasChanged = false;
987 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();//temporary hash table
988 FlatCondBranch currfcb = (FlatCondBranch) curr;
989 Float newprob = new Float((float)0.0);
990 PairMap pm = new PairMap();
991 PrefetchPair childpp = null;
992 PrefetchPair pp = null;
993 Enumeration ecld = null;
995 ecld = child_prefetch_set_copy.keys();
996 while (ecld.hasMoreElements()) {
997 childpp = (PrefetchPair) ecld.nextElement();
1000 newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_TRUE_EDGE_PROB;
1001 if(newprob >= ANALYSIS_THRESHOLD_PROB) {
1002 tocompare.put(childpp, newprob);
1003 pm.addPair(childpp, childpp);
1005 child_prefetch_set_copy.remove(childpp);
1006 } else if(index == 1) { /* False Edge */
1007 newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_FALSE_EDGE_PROB;
1008 if(newprob >= ANALYSIS_THRESHOLD_PROB) {
1009 tocompare.put(childpp, newprob);
1010 pm.addPair(childpp, childpp);
1012 child_prefetch_set_copy.remove(childpp);
1014 System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
1018 /* Create prefetch mappings for child nodes */
1020 parentpmap.put(curr, pm);
1022 pmap_hash.put(curr.getNext(index), parentpmap);
1024 /* Update branch_prefetch_set (global hash table) to combine all prefetch pairs from childnodes of the
1025 * cond branch that is currently stored in the tocompare hash table */
1026 if(!tocompare.isEmpty()) {
1028 branch_prefetch_set.putAll(tocompare);
1029 }else if(index == 1) {
1030 if(branch_prefetch_set.isEmpty()) {
1031 branch_prefetch_set.putAll(tocompare);
1033 Enumeration e = tocompare.keys();
1034 while(e.hasMoreElements()) {
1035 pp = (PrefetchPair) e.nextElement();
1036 if(branch_prefetch_set.containsKey(pp)) {
1037 newprob = (float)(branch_prefetch_set.get(pp).floatValue() + tocompare.get(pp).floatValue());
1038 if(newprob < ANALYSIS_THRESHOLD_PROB) {
1039 branch_prefetch_set.remove(pp);
1041 branch_prefetch_set.put(pp, newprob);
1043 tocompare.remove(pp);
1046 e = tocompare.keys();
1047 while(e.hasMoreElements()) {
1048 pp = (PrefetchPair) e.nextElement();
1049 branch_prefetch_set.put(pp,tocompare.get(pp));
1050 tocompare.remove(pp);
1054 System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
1058 /* Compare prefetch sets and enqueue parent nodes: Only possible after combining prefetch pairs of both child nodes
1059 * into branch_prefetch_set hashtable*/
1061 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set);
1062 if(pSetHasChanged) {
1063 for(int i=0; i<curr.numPrev(); i++) {
1064 tovisit.add(curr.getPrev(i));
1066 /* Overwrite the new prefetch set to the global hash table */
1067 prefetch_hash.put(curr,branch_prefetch_set);
1070 /* Free heap memory */
1075 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
1076 * prefetches up the FlatNode*/
1077 private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
1078 Hashtable<FlatNode, PairMap> parentpmap) {
1079 boolean pSetHasChanged = false;
1080 PairMap pm = new PairMap();
1081 Enumeration e = null;
1082 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1084 /* Propagate all child nodes */
1085 for(e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
1086 PrefetchPair childpp = (PrefetchPair) e.nextElement();
1087 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1088 pm.addPair(childpp, childpp);
1089 child_prefetch_set_copy.remove(childpp);
1092 /* Check case for nodes with no children (e.g return null) and create prefetch mappings for child nodes*/
1093 if(curr.numNext() != 0) {
1095 parentpmap.put(curr, pm);
1097 pmap_hash.put(curr.getNext(0), parentpmap);
1100 /* Compare with old Prefetch sets */
1101 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1103 for(int i=0; i<curr.numPrev(); i++) {
1104 tovisit.add(curr.getPrev(i));
1106 /* Overwrite the new prefetch set to the global hash table */
1107 prefetch_hash.put(curr,tocompare);
1109 /* Free heap memory */
1114 /** This functions processes for FlatNewNode
1115 * for e.g x = NEW(foo) followed by childnode with prefetch set x.f
1116 * then drop the prefetches beyond this FlatNewNode */
1117 private void processFlatNewNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
1118 Hashtable<FlatNode, PairMap> parentpmap) {
1119 boolean pSetHasChanged = false;
1120 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1121 FlatNew currfnn = (FlatNew) curr;
1122 Float newprob = new Float((float)0.0);
1123 PairMap pm = new PairMap();
1124 PrefetchPair childpp = null;
1125 Enumeration ecld = null;
1127 ecld = child_prefetch_set_copy.keys();
1128 while (ecld.hasMoreElements()) {
1129 childpp = (PrefetchPair) ecld.nextElement();
1130 if(childpp.base == currfnn.getDst()){
1131 child_prefetch_set_copy.remove(childpp);
1133 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1134 pm.addPair(childpp, childpp);
1135 child_prefetch_set_copy.remove(childpp);
1139 /* Create prefetch mappings for child nodes */
1141 parentpmap.put(curr, pm);
1143 pmap_hash.put(curr.getNext(0), parentpmap);
1145 /* Compare with the old prefetch set */
1146 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1148 /* Enqueue parent nodes */
1149 if(pSetHasChanged) {
1150 for(int i=0; i<curr.numPrev(); i++) {
1151 tovisit.add(curr.getPrev(i));
1153 /* Overwrite the new prefetch set to the global hash table */
1154 prefetch_hash.put(curr,tocompare);
1158 /** This functions processes for FlatCastNode
1159 * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1160 * then drop the prefetches beyond this FlatCastNode */
1161 private void processFlatCastNode(FlatNode curr, Hashtable<PrefetchPair, Float>child_prefetch_set_copy,
1162 Hashtable<FlatNode, PairMap> parentpmap) {
1163 boolean pSetHasChanged = false;
1164 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1165 FlatCastNode currfcn = (FlatCastNode) curr;
1166 Float newprob = new Float((float)0.0);
1167 PairMap pm = new PairMap();
1168 PrefetchPair childpp = null;
1169 Enumeration ecld = null;
1171 ecld = child_prefetch_set_copy.keys();
1172 while (ecld.hasMoreElements()) {
1173 childpp = (PrefetchPair) ecld.nextElement();
1174 if(childpp.base == currfcn.getDst()){
1175 child_prefetch_set_copy.remove(childpp);
1177 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1178 pm.addPair(childpp, childpp);
1179 child_prefetch_set_copy.remove(childpp);
1183 /* Create prefetch mappings for child nodes */
1185 parentpmap.put(curr, pm);
1187 pmap_hash.put(curr.getNext(0), parentpmap);
1189 /* Compare with the old prefetch set */
1190 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1192 /* Enqueue parent nodes */
1193 if(pSetHasChanged) {
1194 for(int i=0; i<curr.numPrev(); i++) {
1195 tovisit.add(curr.getPrev(i));
1197 /* Overwrite the new prefetch set to the global hash table */
1198 prefetch_hash.put(curr,tocompare);
1200 /* Free heap memory */
1205 /** This functions processes for FlatTagDeclaration
1206 * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1207 * then drop the prefetches beyond this FlatTagDeclaration */
1208 private void processFlatTagDeclaration(FlatNode curr, Hashtable<PrefetchPair, Float>child_prefetch_set_copy,
1209 Hashtable<FlatNode, PairMap> parentpmap) {
1210 boolean pSetHasChanged = false;
1211 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1212 FlatTagDeclaration currftd = (FlatTagDeclaration) curr;
1213 Float newprob = new Float((float)0.0);
1214 PairMap pm = new PairMap();
1215 PrefetchPair childpp = null;
1216 Enumeration ecld = null;
1218 ecld = child_prefetch_set_copy.keys();
1219 while (ecld.hasMoreElements()) {
1220 childpp = (PrefetchPair) ecld.nextElement();
1221 if(childpp.base == currftd.getDst()){
1222 child_prefetch_set_copy.remove(childpp);
1224 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1225 pm.addPair(childpp, childpp);
1226 child_prefetch_set_copy.remove(childpp);
1230 /* Create prefetch mappings for child nodes */
1232 parentpmap.put(curr, pm);
1234 pmap_hash.put(curr.getNext(0), parentpmap);
1236 /* Compare with the old prefetch set */
1237 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1239 /* Enqueue parent nodes */
1240 if(pSetHasChanged) {
1241 for(int i=0; i<curr.numPrev(); i++) {
1242 tovisit.add(curr.getPrev(i));
1244 /* Overwrite the new prefetch set to the global hash table */
1245 prefetch_hash.put(curr,tocompare);
1248 /* Free heap memory */
1253 /** This function prints the Prefetch pairs of a given flatnode */
1254 private void printPrefetchPairs(FlatNode fn) {
1255 if(prefetch_hash.containsKey(fn)) {
1256 System.out.print("Prefetch" + "(");
1257 Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
1258 for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
1259 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
1260 System.out.print(pp.toString() + ", ");
1262 System.out.println(")");
1264 System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
1268 private void doInsPrefetchAnalysis(FlatMethod fm) {
1269 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
1270 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
1271 newvisited = new LinkedList<FlatNode>();
1273 newtovisit.addLast((FlatNode)fm);
1274 while(!newtovisit.isEmpty()) {
1275 FlatNode fn = (FlatNode) newtovisit.iterator().next();
1276 newtovisit.remove(0);
1277 pset1_hash.put(fn, pset1_init);
1278 newvisited.addLast(fn);
1279 for(int i=0; i<fn.numNext(); i++) {
1280 FlatNode nn = fn.getNext(i);
1281 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
1282 newtovisit.addLast(nn);
1287 /* Free Heap Memory */
1291 /* Delete redundant and subset prefetch pairs */
1294 /* Start with a top down sorted order of nodes */
1295 while(!newvisited.isEmpty()) {
1296 applyPrefetchInsertRules((FlatNode) newvisited.getFirst());
1297 newvisited.remove(0);
1301 /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
1302 * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
1303 * then this function drops a.b.c from the prefetch set of the flatnode */
1304 private void delSubsetPPairs() {
1305 Enumeration e = prefetch_hash.keys();
1306 while(e.hasMoreElements()) {
1307 FlatNode fn = (FlatNode) e.nextElement();
1308 Hashtable ppairs = prefetch_hash.get(fn);
1309 Enumeration epp = ((Hashtable)(prefetch_hash.get(fn))).keys();
1310 Vector<PrefetchPair> pplist = new Vector<PrefetchPair>();
1311 Vector pplength = new Vector();
1312 Vector ppisMod = new Vector();
1313 while(epp.hasMoreElements()) {
1314 PrefetchPair pp = (PrefetchPair) epp.nextElement();
1316 int length = pp.desc.size()+ 1;
1317 pplength.add(length);
1320 int numpp = ((Hashtable)(prefetch_hash.get(fn))).size();
1321 for (int i = 0; i < numpp; i++) {
1322 for (int j = i+1; j < numpp; j++) {
1324 int x = ((Integer) (pplength.get(i))).intValue();
1325 if (((Integer) (pplength.get(i))).intValue() < ((Integer)( pplength.get(j))).intValue()) {
1326 ret = isSubSet(pplist.get(i), pplist.get(j));
1331 ret = isSubSet(pplist.get(j), pplist.get(i));
1338 for (int i = 0; i < numpp; i++) {
1339 if (((Integer)(ppisMod.get(i))).intValue() == 1) {
1340 PrefetchPair pp = (PrefetchPair) pplist.get(i);
1345 /* Free heap memory */
1352 /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
1353 * pair else it returns: false */
1354 private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
1355 if (shrt.base != lng.base) {
1358 for (int j = 0; j < shrt.desc.size(); j++) {
1359 if(shrt.getDescAt(j) instanceof IndexDescriptor) {
1360 IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
1361 if(lng.getDescAt(j) instanceof IndexDescriptor){
1362 IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
1363 if(shrtid.equals(lngid)) {
1372 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
1380 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
1381 * returns: true if something has changed in the new Prefetch set else
1384 private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
1385 boolean hasChanged = false;
1387 if(oldPSet.size() != newPSet.size()) {
1390 for(Iterator it = newPSet.iterator();it.hasNext();) {
1391 if(!oldPSet.contains((PrefetchPair)it.next())) {
1399 /** This function creates a set called pset1 that contains prefetch pairs that have already
1400 * been prefetched. While traversing the graph of a flat representation in a top down fashion,
1401 * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
1402 * the previous nodes */
1404 private void applyPrefetchInsertRules(FlatNode fn) {
1405 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
1406 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
1407 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
1408 Hashtable<PrefetchPair, Float> prefetchset = new Hashtable<PrefetchPair, Float>();
1409 boolean ppairIsPresent = false;
1410 boolean mapIsPresent = true;
1411 boolean pprobIsGreater = false;
1412 boolean mapprobIsLess = false;
1413 boolean probIsLess = false;
1414 boolean pSet1HasChanged = false;
1415 Enumeration e = null;
1417 if(fn.kind() == FKind.FlatMethod) {
1418 if(prefetch_hash.containsKey(fn)) {
1419 prefetchset = prefetch_hash.get(fn);
1420 e = prefetchset.keys();
1421 while(e.hasMoreElements()) {
1422 PrefetchPair pp = (PrefetchPair) e.nextElement();
1423 /* Apply initial rule */
1424 if(((float)prefetchset.get(pp).floatValue()) > PREFETCH_THRESHOLD_PROB) {
1428 /* Enqueue child node is Pset1 has changed */
1429 pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1430 if(pSet1HasChanged) {
1431 for(int j=0; j<fn.numNext(); j++) {
1432 FlatNode nn = fn.getNext(j);
1433 newvisited.addLast((FlatNode)nn);
1436 pset1_hash.put(fn, pset1);
1437 if(pset1.size() > 0) {
1438 newprefetchset.put(fn, pset1);
1442 if(prefetch_hash.containsKey(fn)) {
1443 prefetchset = prefetch_hash.get(fn);
1444 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
1445 PrefetchPair pp = (PrefetchPair) epset.nextElement();
1447 Hashtable<FlatNode, PairMap> ppairmaphash = new Hashtable<FlatNode, PairMap>();
1448 ppairmaphash = pmap_hash.get(fn);
1449 if(!ppairmaphash.isEmpty()) {
1450 e = ppairmaphash.keys();
1451 while(e.hasMoreElements()) {
1452 FlatNode parentnode = (FlatNode) e.nextElement();
1453 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1454 if(pset1_hash.containsKey(parentnode)) {
1455 HashSet pset = pset1_hash.get(parentnode);
1456 if(!pset.isEmpty()) {
1457 if(ppairIsPresent = (pset.contains((PrefetchPair) pm.getPair(pp)))) {
1458 mapIsPresent = ppairIsPresent && mapIsPresent;
1461 mapIsPresent = false;
1470 /* Create newprefetchset */
1471 if(pprobIsGreater = (prefetchset.get(pp).floatValue() > PREFETCH_THRESHOLD_PROB)) {
1472 ppairmaphash = pmap_hash.get(fn);
1473 if(!ppairmaphash.isEmpty()) {
1474 e = ppairmaphash.keys();
1475 while(e.hasMoreElements()) {
1476 FlatNode parentnode = (FlatNode) e.nextElement();
1477 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1478 PrefetchPair mappedpp = pm.getPair(pp);
1479 if(mappedpp != null) {
1480 if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
1481 float prob = (float)prefetch_hash.get(parentnode).get(mappedpp).floatValue();
1482 if(probIsLess = (prob < PREFETCH_THRESHOLD_PROB))
1483 mapprobIsLess = mapprobIsLess || probIsLess;
1486 mapprobIsLess = false;
1490 mapprobIsLess = true;
1493 if(pprobIsGreater && mapprobIsLess) {
1498 if(!pset2.isEmpty())
1499 pset1.addAll(pset2);
1500 if(!newpset.isEmpty())
1501 pset1.addAll(newpset);
1502 /* Enqueue child node if Pset1 has changed */
1503 pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1504 if(pSet1HasChanged) {
1505 for(int i=0; i<fn.numNext(); i++) {
1506 FlatNode nn = fn.getNext(i);
1507 newvisited.addLast((FlatNode)nn);
1510 pset1_hash.put(fn, pset1);
1513 /* To insert prefetch apply rule: if the newpset intersection pset2 is nonempty
1514 * then insert a new prefetch node here*/
1515 HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
1516 if(!newpset.isEmpty()) {
1517 if(!pset2.isEmpty()) {
1518 for(Iterator it = newpset.iterator(); it.hasNext();) {
1519 PrefetchPair pp = (PrefetchPair) it.next();
1520 if(!pset2.contains(pp)) {
1525 for(Iterator it = newpset.iterator(); it.hasNext();) {
1526 PrefetchPair pp = (PrefetchPair) it.next();
1532 newprefetchset.put(fn, s);
1536 /* Free heap memory */
1543 private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1545 Enumeration e = null;
1546 e = newprefetchset.keys();
1547 boolean isFNPresent = false; /* Detects presence of FlatNew node */
1548 /* This modifies the graph */
1549 while(e.hasMoreElements()) {
1550 FlatNode fn = (FlatNode) e.nextElement();
1551 FlatPrefetchNode fpn = new FlatPrefetchNode();
1552 for(i = 0; i< newprefetchset.get(fn).size(); i++) {
1553 fpn.insAllpp((HashSet)newprefetchset.get(fn));
1555 if(fn.kind() == FKind.FlatMethod) {
1556 FlatNode nn = fn.getNext(0);
1560 /* Check if previous node of this FlatNode is a NEW node
1561 * If yes, delete this flatnode and its prefetch set from hash table
1562 * This eliminates prefetches for NULL ptrs*/
1563 for(i = 0; i< fn.numPrev(); i++) {
1564 FlatNode nn = fn.getPrev(i);
1565 if(nn.kind() == FKind.FlatNew) {
1570 while(fn.numPrev() > 0) {
1571 FlatNode nn = fn.getPrev(0);
1572 for(int j = 0; j<nn.numNext(); j++) {
1573 if(nn.getNext(j) == fn) {
1584 private void doAnalysis() {
1585 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
1586 while(classit.hasNext()) {
1587 ClassDescriptor cn=(ClassDescriptor)classit.next();
1588 Iterator methodit=cn.getMethods();
1589 while(methodit.hasNext()) {
1590 /* Classify parameters */
1591 MethodDescriptor md=(MethodDescriptor)methodit.next();
1592 FlatMethod fm=state.getMethodFlat(md);
1598 private void printMethod(FlatMethod fm) {
1599 System.out.println(fm.getMethod()+" {");
1600 HashSet tovisit=new HashSet();
1601 HashSet visited=new HashSet();
1603 Hashtable nodetolabel=new Hashtable();
1605 FlatNode current_node=null;
1607 //Node needs a label if it is
1608 while(!tovisit.isEmpty()) {
1609 FlatNode fn=(FlatNode)tovisit.iterator().next();
1613 for(int i=0;i<fn.numNext();i++) {
1614 FlatNode nn=fn.getNext(i);
1616 //1) Edge >1 of node
1617 nodetolabel.put(nn,new Integer(labelindex++));
1619 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
1623 nodetolabel.put(nn,new Integer(labelindex++));
1627 //Do the actual printing
1628 tovisit=new HashSet();
1629 visited=new HashSet();
1631 while(current_node!=null||!tovisit.isEmpty()) {
1632 if (current_node==null) {
1633 current_node=(FlatNode)tovisit.iterator().next();
1634 tovisit.remove(current_node);
1636 visited.add(current_node);
1637 if (nodetolabel.containsKey(current_node))
1638 System.out.println("L"+nodetolabel.get(current_node)+":");
1639 if (current_node.numNext()==0) {
1640 System.out.println(" "+current_node.toString());
1642 } else if(current_node.numNext()==1) {
1643 System.out.println(" "+current_node.toString());
1644 FlatNode nextnode=current_node.getNext(0);
1645 if (visited.contains(nextnode)) {
1646 System.out.println("goto L"+nodetolabel.get(nextnode));
1649 current_node=nextnode;
1650 } else if (current_node.numNext()==2) {
1652 System.out.println(" "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
1653 if (!visited.contains(current_node.getNext(1)))
1654 tovisit.add(current_node.getNext(1));
1655 if (visited.contains(current_node.getNext(0))) {
1656 System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
1659 current_node=current_node.getNext(0);
1660 } else throw new Error();
1662 System.out.println("}");