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>>();
42 /** This function returns true if a tempdescriptor object is found in the array of descriptors
43 * for a given prefetch pair else returns false*/
44 private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) {
45 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
46 ListIterator it = desc.listIterator();
49 if(o instanceof IndexDescriptor) {
50 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
51 if(tdarray.contains(td)) {
59 /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
60 * tempdescriptors when there is a match */
61 private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) {
62 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
63 ListIterator it = desc.listIterator();
65 Object currdesc = it.next();
66 if(currdesc instanceof IndexDescriptor) {
67 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
68 if(tdarray.contains(td)) {
69 int index = tdarray.indexOf(td);
70 tdarray.set(index, newtd);
77 /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new
78 * tempdescriptors when there is a match for e.g FlatOpNodes if i= i+j then replace i with i+j */
79 private ArrayList<Descriptor> getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor left, TempDescriptor right) {
80 ArrayList<Descriptor> desc = (ArrayList<Descriptor>) pp.getDesc();
81 ListIterator it = desc.listIterator();
83 Object currdesc = it.next();
84 if(currdesc instanceof IndexDescriptor) {
85 ArrayList<TempDescriptor> tdarray = (ArrayList<TempDescriptor>)((IndexDescriptor)currdesc).tddesc;
86 if(tdarray.contains(td)) {
87 int index = tdarray.indexOf(td);
88 tdarray.set(index, left);
96 /** This function starts the prefetch analysis */
97 private void DoPrefetch() {
98 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
99 while(classit.hasNext()) {
100 ClassDescriptor cn=(ClassDescriptor)classit.next();
101 doMethodAnalysis(cn);
105 /** This function calls analysis for every method in a class */
106 private void doMethodAnalysis(ClassDescriptor cn) {
107 Iterator methodit=cn.getMethods();
108 while(methodit.hasNext()) {
109 newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
110 pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
111 MethodDescriptor md=(MethodDescriptor)methodit.next();
112 FlatMethod fm=state.getMethodFlat(md);
113 doFlatNodeAnalysis(fm);
114 doInsPrefetchAnalysis(fm);
115 if(newprefetchset.size() > 0) {
116 addFlatPrefetchNode(newprefetchset);
121 /** This function calls analysis for every node in a method */
122 private void doFlatNodeAnalysis(FlatMethod fm) {
123 tovisit = fm.getNodeSet();
124 Hashtable<PrefetchPair, Float> nodehash = new Hashtable<PrefetchPair, Float>();
125 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
126 while(!tovisit.isEmpty()) {
127 FlatNode fn = (FlatNode)tovisit.iterator().next();
128 prefetch_hash.put(fn, nodehash);
131 /* Visit and process nodes */
132 tovisit = fm.getNodeSet();
133 while(!tovisit.isEmpty()) {
134 FlatNode fn = (FlatNode)tovisit.iterator().next();
135 doChildNodeAnalysis(fn);
141 * This function generates the prefetch sets for a given Flatnode considering the kind of node
142 * It calls severals functions based on the kind of the node and
143 * returns true: if the prefetch set has changed since last time the node was analysed
144 * returns false : otherwise
146 private void doChildNodeAnalysis(FlatNode curr) {
147 Hashtable<PrefetchPair, Float> child_prefetch_set_copy = new Hashtable<PrefetchPair, Float>();
148 Hashtable<FlatNode, PairMap> parentpmap = new Hashtable<FlatNode, PairMap>();
149 FlatNode child_node = null;
150 if(curr.numNext() != 0) {
151 child_node = curr.getNext(0);
152 if(prefetch_hash.containsKey(child_node)) {
153 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
157 switch(curr.kind()) {
158 case FKind.FlatBackEdge:
159 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
162 //TODO change it to take care of FlatMethod, Flatcalls
163 processFlatCall(curr, child_prefetch_set_copy, parentpmap);
165 case FKind.FlatCheckNode:
166 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
168 case FKind.FlatMethod:
169 //TODO change it to take care of FlatMethod, Flatcalls
170 processFlatMethod(curr, child_prefetch_set_copy, parentpmap);
173 processFlatNewNode(curr, child_prefetch_set_copy, parentpmap);
175 case FKind.FlatReturnNode:
176 //TODO change it to take care of FlatMethod, Flatcalls
177 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
179 case FKind.FlatFieldNode:
180 processFlatFieldNode(curr, child_prefetch_set_copy, parentpmap);
182 case FKind.FlatElementNode:
183 processFlatElementNode(curr, child_prefetch_set_copy, parentpmap);
185 case FKind.FlatCondBranch:
186 branch_prefetch_set = new Hashtable<PrefetchPair,Float>();
187 for (int i = 0; i < curr.numNext(); i++) {
188 parentpmap = new Hashtable<FlatNode, PairMap>();
189 child_node = curr.getNext(i);
190 if (prefetch_hash.containsKey(child_node)) {
191 child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
193 processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, parentpmap);
196 case FKind.FlatOpNode:
197 processFlatOpNode(curr, child_prefetch_set_copy, parentpmap);
199 case FKind.FlatLiteralNode:
200 processFlatLiteralNode(curr, child_prefetch_set_copy, parentpmap);
202 case FKind.FlatSetElementNode:
203 processFlatSetElementNode(curr, child_prefetch_set_copy, parentpmap);
205 case FKind.FlatSetFieldNode:
206 processFlatSetFieldNode(curr, child_prefetch_set_copy, parentpmap);
208 case FKind.FlatAtomicEnterNode:
209 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
211 case FKind.FlatAtomicExitNode:
212 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
214 case FKind.FlatCastNode:
215 processFlatCastNode(curr, child_prefetch_set_copy, parentpmap);
217 case FKind.FlatFlagActionNode:
218 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
220 case FKind.FlatGlobalConvNode:
221 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
224 processDefaultCase(curr,child_prefetch_set_copy, parentpmap);
226 case FKind.FlatTagDeclaration:
227 processFlatTagDeclaration(curr, child_prefetch_set_copy, parentpmap);
230 System.out.println("NO SUCH FLATNODE");
235 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
236 * returns: true if something has changed in the new Prefetch set else
239 private boolean comparePrefetchSets(Hashtable<PrefetchPair, Float> oldPrefetchSet, Hashtable<PrefetchPair, Float>
241 boolean hasChanged = false;
242 PrefetchPair oldpp = null;
243 PrefetchPair newpp = null;
245 if(oldPrefetchSet.size() != newPrefetchSet.size()) {
246 if(newPrefetchSet.size() == 0) {
251 Enumeration e = newPrefetchSet.keys();
252 while(e.hasMoreElements()) {
253 newpp = (PrefetchPair) e.nextElement();
254 float newprob = newPrefetchSet.get(newpp);
255 for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) {
256 oldpp = (PrefetchPair) elem.nextElement();
257 if(oldpp.equals(newpp)) {
258 /*Compare the difference in their probabilities */
259 float oldprob = oldPrefetchSet.get(oldpp);
260 int diff = (int) ((newprob - oldprob)/oldprob)*100;
261 if(diff >= PROB_DIFF) {
272 /** This function processes the prefetch set of FlatFieldNode
273 * It generates a new prefetch set after comparision with its children
274 * Then compares it with its old prefetch set
275 * If old prefetch set is not same as new prefetch set then enqueue the parents
276 * of the current FlatFieldNode
278 private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
279 Hashtable<FlatNode, PairMap> parentpmap) {
280 boolean pSetHasChanged = false;
281 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
282 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
283 FlatFieldNode currffn = (FlatFieldNode) curr;
284 PairMap pm = new PairMap();
286 /* Do Self analysis of the current node*/
287 FieldDescriptor currffn_field = currffn.getField();
288 TempDescriptor currffn_src = currffn.getSrc();
289 if (currffn_field.getType().isPtr()) {
290 PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
291 Float prob = new Float((float)1.0);
292 currcopy.put(pp, prob);
295 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
296 Enumeration ecld = child_prefetch_set_copy.keys();
297 PrefetchPair currpp = null;
298 PrefetchPair childpp = null;
299 while (ecld.hasMoreElements()) {
300 childpp = (PrefetchPair) ecld.nextElement();
301 if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
302 if (currffn.getField().getType().isPtr()) {
303 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
304 newdesc.add(currffn.getField());
305 newdesc.addAll(childpp.desc);
306 PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc);
307 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
308 tocompare.put(newpp, newprob);
309 pm.addPair(childpp, newpp);
310 child_prefetch_set_copy.remove(childpp);
311 /* Check for independence of prefetch pairs to compute new probability */
312 if(child_prefetch_set_copy.containsKey(newpp)) {
313 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
314 if(newprob < ANALYSIS_THRESHOLD_PROB) {
315 tocompare.remove(newpp);
317 tocompare.put(newpp, newprob);
318 pm.addPair(newpp, newpp);
320 child_prefetch_set_copy.remove(newpp);
323 } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
324 child_prefetch_set_copy.remove(childpp);
329 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
330 * if so, calculate the new probability */
331 ecld = child_prefetch_set_copy.keys();
332 Enumeration e = null;
333 while(ecld.hasMoreElements()) {
334 childpp = (PrefetchPair) ecld.nextElement();
335 for(e = currcopy.keys(); e.hasMoreElements();) {
336 currpp = (PrefetchPair) e.nextElement();
337 if(currpp.equals(childpp)) {
338 Float prob = currcopy.get(currpp).floatValue();
339 currcopy.put(currpp, prob);
340 pm.addPair(childpp, currpp);
341 child_prefetch_set_copy.remove(childpp);
347 /* Merge child prefetch pairs */
348 ecld = child_prefetch_set_copy.keys();
349 while(ecld.hasMoreElements()) {
350 childpp = (PrefetchPair) ecld.nextElement();
351 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
352 pm.addPair(childpp, childpp);
353 child_prefetch_set_copy.remove(childpp);
356 /* Merge curr prefetch pairs */
358 while(e.hasMoreElements()) {
359 currpp = (PrefetchPair) e.nextElement();
360 tocompare.put(currpp, currcopy.get(currpp));
361 currcopy.remove(currpp);
364 /* Create prefetch mappings for child nodes */
366 parentpmap.put(curr, pm);
368 pmap_hash.put(curr.getNext(0), parentpmap);
370 /* Compare with the orginal prefetch pairs */
371 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
372 /* Enqueue parent nodes */
374 for(int i=0; i<curr.numPrev(); i++) {
375 tovisit.add(curr.getPrev(i));
377 /* Overwrite the new prefetch set to the global hash table */
378 prefetch_hash.put(curr,tocompare);
382 /** This function processes the prefetch set of a FlatElementNode
383 * It generates a new prefetch set after comparision with its children
384 * It compares the old prefetch set with this new prefetch set and enqueues the parents
385 * of the current node if change occurs and updates the global flatnode hash table
387 private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
388 Hashtable<FlatNode, PairMap> parentpmap) {
390 boolean pSetHasChanged = false;
391 Hashtable<PrefetchPair, Float> currcopy = new Hashtable<PrefetchPair, Float>();
392 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
393 FlatElementNode currfen = (FlatElementNode) curr;
394 PairMap pm = new PairMap();
397 /* Do Self analysis of the current node*/
398 TempDescriptor currfen_index = currfen.getIndex();
399 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
400 TempDescriptor currfen_src = currfen.getSrc();
401 if(currfen.getDst().getType().isPtr()) {
402 PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
403 Float prob = new Float((float)1.0);
404 currcopy.put(pp, prob);
407 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
408 Enumeration ecld = child_prefetch_set_copy.keys();
409 PrefetchPair currpp = null;
410 PrefetchPair childpp = null;
411 while (ecld.hasMoreElements()) {
412 childpp = (PrefetchPair) ecld.nextElement();
413 if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
414 if (currfen.getDst().getType().isPtr()) {
415 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
416 newdesc.add((Descriptor)idesc);
417 newdesc.addAll(childpp.desc);
418 PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc);
419 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
420 tocompare.put(newpp, newprob);
421 pm.addPair(childpp, newpp);
422 child_prefetch_set_copy.remove(childpp);
423 /* Check for independence of prefetch pairs to compute new probability */
424 if(child_prefetch_set_copy.containsKey(newpp)) {
425 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
426 if(newprob < ANALYSIS_THRESHOLD_PROB) {
427 tocompare.remove(newpp);
429 tocompare.put(newpp, newprob);
430 pm.addPair(newpp, newpp);
432 child_prefetch_set_copy.remove(newpp);
435 } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
436 child_prefetch_set_copy.remove(childpp);
439 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
440 * if so calculate the new probability */
441 ecld = child_prefetch_set_copy.keys();
442 Enumeration e = null;
443 while(ecld.hasMoreElements()) {
444 childpp = (PrefetchPair) ecld.nextElement();
445 for(e = currcopy.keys(); e.hasMoreElements();) {
446 currpp = (PrefetchPair) e.nextElement();
447 if(currpp.equals(childpp)) {
448 Float prob = currcopy.get(currpp).floatValue();
449 currcopy.put(currpp, prob);
450 pm.addPair(childpp, currpp);
451 child_prefetch_set_copy.remove(childpp);
457 /* Merge child prefetch pairs */
458 ecld = child_prefetch_set_copy.keys();
459 while(ecld.hasMoreElements()) {
460 childpp = (PrefetchPair) ecld.nextElement();
461 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
462 pm.addPair(childpp, childpp);
463 child_prefetch_set_copy.remove(childpp);
466 /* Merge curr prefetch pairs */
468 while(e.hasMoreElements()) {
469 currpp = (PrefetchPair) e.nextElement();
470 tocompare.put(currpp, currcopy.get(currpp));
471 currcopy.remove(currpp);
474 /* Create prefetch mappings for child nodes */
476 parentpmap.put(curr, pm);
478 pmap_hash.put(curr.getNext(0), parentpmap);
480 /* Compare with the orginal prefetch pairs */
481 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
482 /* Enqueue parent nodes */
484 for(int i=0; i<curr.numPrev(); i++) {
485 tovisit.add(curr.getPrev(i));
487 /* Overwrite the new prefetch set to the global hash table */
488 prefetch_hash.put(curr,tocompare);
492 /** This function processes the prefetch set of a FlatSetFieldNode
493 * It generates a new prefetch set after comparision with its children
494 * It compares the old prefetch set with this new prefetch set and enqueues the parents
495 * of the current node if change occurs and then updates the global flatnode hash table
497 private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
498 Hashtable<FlatNode, PairMap> parentpmap) {
499 boolean pSetHasChanged = false;
500 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
501 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
502 PrefetchPair childpp = null;
503 PairMap pm = new PairMap();
505 Enumeration ecld = child_prefetch_set_copy.keys();
506 while (ecld.hasMoreElements()) {
507 childpp = (PrefetchPair) ecld.nextElement();
508 if(childpp.base == currfsfn.getDst()) {
509 int size = childpp.desc.size();
511 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
512 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
513 for(int i = 0;i<(childpp.desc.size()-1); i++) {
514 newdesc.add(i,childpp.desc.get(i+1));
516 PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc);
517 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
518 tocompare.put(newpp, newprob);
519 pm.addPair(childpp, newpp);
520 child_prefetch_set_copy.remove(childpp);
521 /* Check for independence of prefetch pairs in newly generated prefetch pair
522 * to compute new probability */
523 if(child_prefetch_set_copy.containsKey(newpp)) {
524 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
525 if(newprob < ANALYSIS_THRESHOLD_PROB) {
526 tocompare.remove(newpp);
528 tocompare.put(newpp, newprob);
529 pm.addPair(newpp, newpp);
531 child_prefetch_set_copy.remove(newpp);
535 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
536 child_prefetch_set_copy.remove(childpp);
544 /* Merge child prefetch pairs */
545 ecld = child_prefetch_set_copy.keys();
546 while(ecld.hasMoreElements()) {
547 childpp = (PrefetchPair) ecld.nextElement();
548 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
549 pm.addPair(childpp, childpp);
550 child_prefetch_set_copy.remove(childpp);
553 /* Create prefetch mappings for child nodes */
555 parentpmap.put(curr, pm);
557 pmap_hash.put(curr.getNext(0), parentpmap);
559 /* Compare with the orginal prefetch pairs */
560 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
561 /* Enqueue parent nodes */
563 for(int i=0; i<curr.numPrev(); i++) {
564 tovisit.add(curr.getPrev(i));
566 /* Overwrite the new prefetch set to the global hash table */
567 prefetch_hash.put(curr,tocompare);
571 /** This function processes the prefetch set of a FlatSeElementNode
572 * It generates a new prefetch set after comparision with its children
573 * It compares the old prefetch set with this new prefetch set and enqueues the parents
574 * of the current node if change occurs and then updates the global flatnode hash table
576 private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
577 Hashtable<FlatNode, PairMap> parentpmap) {
578 boolean pSetHasChanged = false;
579 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
580 PrefetchPair childpp = null;
581 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
582 PairMap pm = new PairMap();
584 Enumeration ecld = child_prefetch_set_copy.keys();
585 while (ecld.hasMoreElements()) {
586 childpp = (PrefetchPair) ecld.nextElement();
587 if (childpp.base == currfsen.getDst()){
588 int sizedesc = childpp.desc.size();
589 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
590 int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
591 if(sizetempdesc == 1) {
592 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
593 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
594 for(int i = 0;i<(childpp.desc.size()-1); i++) {
595 newdesc.add(i,childpp.desc.get(i+1));
597 PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc);
598 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
599 tocompare.put(newpp, newprob);
600 pm.addPair(childpp, newpp);
601 child_prefetch_set_copy.remove(childpp);
602 /* Check for independence of prefetch pairs to compute new probability */
603 if(child_prefetch_set_copy.containsKey(newpp)) {
604 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
605 if(newprob < ANALYSIS_THRESHOLD_PROB) {
606 tocompare.remove(newpp);
608 tocompare.put(newpp, newprob);
609 pm.addPair(newpp, newpp);
611 child_prefetch_set_copy.remove(newpp);
613 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
614 child_prefetch_set_copy.remove(childpp);
621 /* Merge child prefetch pairs */
622 ecld = child_prefetch_set_copy.keys();
623 while(ecld.hasMoreElements()) {
624 childpp = (PrefetchPair) ecld.nextElement();
625 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
626 pm.addPair(childpp, childpp);
627 child_prefetch_set_copy.remove(childpp);
630 /* Create prefetch mappings for child nodes */
632 parentpmap.put(curr, pm);
634 pmap_hash.put(curr.getNext(0), parentpmap);
636 /* Compare with the orginal prefetch pairs */
637 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
638 /* Enqueue parent nodes */
640 for(int i=0; i<curr.numPrev(); i++) {
641 tovisit.add(curr.getPrev(i));
643 /* Overwrite the new prefetch set to the global hash table */
644 prefetch_hash.put(curr,tocompare);
648 /** This function applies rules and does analysis for a FlatOpNode
649 * And updates the global prefetch hashtable
651 private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
652 Hashtable<FlatNode, PairMap> parentpmap) {
653 boolean pSetHasChanged = false;
655 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
656 FlatOpNode currfopn = (FlatOpNode) curr;
657 Enumeration ecld = null;
658 PrefetchPair childpp = null;
659 PairMap pm = new PairMap();
661 if(currfopn.getOp().getOp()== Operation.ASSIGN) {
662 ecld = child_prefetch_set_copy.keys();
663 while (ecld.hasMoreElements()) {
664 childpp = (PrefetchPair) ecld.nextElement();
665 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
667 /* For cases like x=y followed by childnode t=x[i].z or t=x.g*/
668 if(childpp.base == currfopn.getDest()) {
669 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
670 newdesc.addAll(childpp.desc);
671 PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc);
672 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
673 tocompare.put(newpp, newprob);
674 pm.addPair(childpp, newpp);
675 child_prefetch_set_copy.remove(childpp);
676 /* Check for independence of prefetch pairs to compute new probability */
677 if(child_prefetch_set_copy.containsKey(newpp)) {
678 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
679 if(newprob < ANALYSIS_THRESHOLD_PROB) {
680 tocompare.remove(newpp);
682 tocompare.put(newpp, newprob);
683 pm.addPair(newpp, newpp);
685 child_prefetch_set_copy.remove(newpp);
687 /* For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/
688 } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
689 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
690 newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
691 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
692 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
693 tocompare.put(newpp, newprob);
694 pm.addPair(childpp, newpp);
695 child_prefetch_set_copy.remove(childpp);
696 /* Check for independence of prefetch pairs to compute new probability*/
697 if(child_prefetch_set_copy.containsKey(newpp)) {
698 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
699 if(newprob < ANALYSIS_THRESHOLD_PROB) {
700 tocompare.remove(newpp);
702 tocompare.put(newpp, newprob);
703 pm.addPair(newpp, newpp);
705 child_prefetch_set_copy.remove(newpp);
711 //case i = i+z followed by a[i].x
712 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
713 ecld = child_prefetch_set_copy.keys();
714 while (ecld.hasMoreElements()) {
715 childpp = (PrefetchPair) ecld.nextElement();
716 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
718 if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
719 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
720 newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight()));
721 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
722 Float newprob = child_prefetch_set_copy.get(childpp).floatValue();
723 tocompare.put(newpp, newprob);
724 pm.addPair(childpp, newpp);
725 child_prefetch_set_copy.remove(childpp);
726 /* Check for independence of prefetch pairs to compute new probability*/
727 if(child_prefetch_set_copy.containsKey(newpp)) {
728 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
729 if(newprob < ANALYSIS_THRESHOLD_PROB) {
730 tocompare.remove(newpp);
732 tocompare.put(newpp, newprob);
733 pm.addPair(newpp, newpp);
735 child_prefetch_set_copy.remove(newpp);
742 //FIXME Is not taken care of for cases like x = -y followed by a[x].i
745 /* Merge child prefetch pairs */
746 ecld = child_prefetch_set_copy.keys();
747 while(ecld.hasMoreElements()) {
748 childpp = (PrefetchPair) ecld.nextElement();
749 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
750 pm.addPair(childpp, childpp);
751 child_prefetch_set_copy.remove(childpp);
754 /* Create prefetch mappings for child nodes */
756 parentpmap.put(curr, pm);
758 pmap_hash.put(curr.getNext(0), parentpmap);
760 /* Compare with the orginal prefetch pairs */
761 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
762 /* Enqueue parent nodes */
764 for(int i=0; i<curr.numPrev(); i++) {
765 tovisit.add(curr.getPrev(i));
767 /* Overwrite the new prefetch set to the global hash table */
768 prefetch_hash.put(curr,tocompare);
772 /** This function processes a FlatLiteralNode where cases such as
773 * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r
775 private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
776 Hashtable<FlatNode, PairMap> parentpmap) {
777 boolean pSetHasChanged = false;
778 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
779 FlatLiteralNode currfln = (FlatLiteralNode) curr;
780 Enumeration ecld = null;
781 PrefetchPair childpp = null;
782 PairMap pm = new PairMap();
784 if(currfln.getType().isIntegerType()) {
785 ecld = child_prefetch_set_copy.keys();
786 while (ecld.hasMoreElements()) {
787 childpp = (PrefetchPair) ecld.nextElement();
788 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
789 /* For cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r*/
790 if(isTempDescFound(copyofchildpp,currfln.getDst())) {
791 ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
792 int sizetempdesc = copychilddesc.size();
793 ListIterator it = copychilddesc.listIterator();
794 for(;it.hasNext();) {
795 Object o = it.next();
796 if(o instanceof IndexDescriptor) {
797 ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
798 int sizetddesc = td.size();
799 if(td.contains(currfln.getDst())) {
800 int index = td.indexOf(currfln.getDst());
802 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
806 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
807 newdesc.addAll(copychilddesc);
808 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
809 Float newprob = (child_prefetch_set_copy.get(childpp)).floatValue();
810 tocompare.put(newpp, newprob);
811 pm.addPair(childpp, newpp);
812 child_prefetch_set_copy.remove(childpp);
813 /* Check for independence of prefetch pairs to compute new probability */
814 if(child_prefetch_set_copy.containsKey(newpp)) {
815 newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue())));
816 if(newprob < ANALYSIS_THRESHOLD_PROB) {
817 tocompare.remove(newpp);
819 tocompare.put(newpp, newprob);
820 pm.addPair(newpp, newpp);
822 child_prefetch_set_copy.remove(newpp);
828 /* Merge child prefetch pairs */
829 ecld = child_prefetch_set_copy.keys();
830 while(ecld.hasMoreElements()) {
831 childpp = (PrefetchPair) ecld.nextElement();
832 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
833 pm.addPair(childpp, childpp);
834 child_prefetch_set_copy.remove(childpp);
837 /* Create prefetch mappings for child nodes */
839 parentpmap.put(curr, pm);
841 pmap_hash.put(curr.getNext(0), parentpmap);
843 /* Compare with the orginal prefetch pairs */
844 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
845 /* Enqueue parent nodes */
847 for(int i=0; i<curr.numPrev(); i++) {
848 tovisit.add(curr.getPrev(i));
850 /* Overwrite the new prefetch set to the global hash table */
851 prefetch_hash.put(curr,tocompare);
855 /** This function processes a FlatMethod where the method propagates
856 * the entire prefetch set of its child node */
857 private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
858 Hashtable<FlatNode, PairMap> parentpmap) {
859 boolean pSetHasChanged = false;
860 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
861 FlatMethod currfm = (FlatMethod) curr;
862 Enumeration ecld = null;
863 PrefetchPair childpp = null;
864 PairMap pm = new PairMap();
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 /* Overwrite the new prefetch set to the global hash table */
886 prefetch_hash.put(curr,tocompare);
890 /** This Function processes the FlatCalls
891 * It currently drops the propagation of those prefetchpairs that are passed as
892 * arguments in the FlatCall
894 private void processFlatCall(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
895 Hashtable<FlatNode, PairMap> parentpmap) {
896 boolean pSetHasChanged = false;
897 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
898 FlatCall currfcn = (FlatCall) curr;
899 PairMap pm = new PairMap();
900 Enumeration ecld = null;
901 PrefetchPair childpp = null;
903 ecld = child_prefetch_set_copy.keys();
904 while(ecld.hasMoreElements()) {
905 childpp = (PrefetchPair) ecld.nextElement();
906 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
907 if(currfcn.getReturnTemp() != childpp.base) {
908 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
909 pm.addPair(childpp, childpp);
910 child_prefetch_set_copy.remove(childpp);
912 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 for(int i=0; i<curr.numPrev(); i++) {
927 tovisit.add(curr.getPrev(i));
929 /* Overwrite the new prefetch set to the global hash table */
930 prefetch_hash.put(curr,tocompare);
934 /** This function handles the processes the FlatNode of type FlatCondBranch
935 * It combines prefetches of both child elements and create a new hash table called
936 * branch_prefetch_set to contains the entries of both its children
938 private void processFlatCondBranch(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy, int index,
939 Hashtable<PrefetchPair,Float> branch_prefetch_set, Hashtable<FlatNode, PairMap> parentpmap) {
940 boolean pSetHasChanged = false;
941 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();//temporary hash table
942 FlatCondBranch currfcb = (FlatCondBranch) curr;
943 Float newprob = new Float((float)0.0);
944 PairMap pm = new PairMap();
945 PrefetchPair childpp = null;
946 PrefetchPair pp = null;
947 Enumeration ecld = null;
949 ecld = child_prefetch_set_copy.keys();
950 while (ecld.hasMoreElements()) {
951 childpp = (PrefetchPair) ecld.nextElement();
954 newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_TRUE_EDGE_PROB;
955 if(newprob >= ANALYSIS_THRESHOLD_PROB) {
956 tocompare.put(childpp, newprob);
957 pm.addPair(childpp, childpp);
959 child_prefetch_set_copy.remove(childpp);
960 } else if(index == 1) { /* False Edge */
961 newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_FALSE_EDGE_PROB;
962 if(newprob >= ANALYSIS_THRESHOLD_PROB) {
963 tocompare.put(childpp, newprob);
964 pm.addPair(childpp, childpp);
966 child_prefetch_set_copy.remove(childpp);
968 System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
972 /* Create prefetch mappings for child nodes */
974 parentpmap.put(curr, pm);
976 pmap_hash.put(curr.getNext(index), parentpmap);
978 /* Update branch_prefetch_set (global hash table) to combine all prefetch pairs from childnodes of the
979 * cond branch that is currently stored in the tocompare hash table */
980 if(!tocompare.isEmpty()) {
982 branch_prefetch_set.putAll(tocompare);
983 }else if(index == 1) {
984 if(branch_prefetch_set.isEmpty()) {
985 branch_prefetch_set.putAll(tocompare);
987 Enumeration e = tocompare.keys();
988 while(e.hasMoreElements()) {
989 pp = (PrefetchPair) e.nextElement();
990 if(branch_prefetch_set.containsKey(pp)) {
991 newprob = (float)(branch_prefetch_set.get(pp).floatValue() + tocompare.get(pp).floatValue());
992 if(newprob < ANALYSIS_THRESHOLD_PROB) {
993 branch_prefetch_set.remove(pp);
995 branch_prefetch_set.put(pp, newprob);
997 tocompare.remove(pp);
1000 e = tocompare.keys();
1001 while(e.hasMoreElements()) {
1002 pp = (PrefetchPair) e.nextElement();
1003 branch_prefetch_set.put(pp,tocompare.get(pp));
1004 tocompare.remove(pp);
1008 System.out.println("DEBUG-> No more children of the FlatCondBranchNode present");
1012 /* Compare prefetch sets and enqueue parent nodes: Only possible after combining prefetch pairs of both child nodes
1013 * into branch_prefetch_set hashtable*/
1015 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set);
1016 if(pSetHasChanged) {
1017 for(int i=0; i<curr.numPrev(); i++) {
1018 tovisit.add(curr.getPrev(i));
1020 /* Overwrite the new prefetch set to the global hash table */
1021 prefetch_hash.put(curr,branch_prefetch_set);
1026 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
1027 * prefetches up the FlatNode*/
1028 private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
1029 Hashtable<FlatNode, PairMap> parentpmap) {
1030 boolean pSetHasChanged = false;
1031 PairMap pm = new PairMap();
1032 Enumeration e = null;
1033 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1035 /* Propagate all child nodes */
1036 for(e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
1037 PrefetchPair childpp = (PrefetchPair) e.nextElement();
1038 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1039 pm.addPair(childpp, childpp);
1040 child_prefetch_set_copy.remove(childpp);
1043 /* Check case for nodes with no children (e.g return null) and create prefetch mappings for child nodes*/
1044 if(curr.numNext() != 0) {
1046 parentpmap.put(curr, pm);
1048 pmap_hash.put(curr.getNext(0), parentpmap);
1051 /* Compare with old Prefetch sets */
1052 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1054 for(int i=0; i<curr.numPrev(); i++) {
1055 tovisit.add(curr.getPrev(i));
1057 /* Overwrite the new prefetch set to the global hash table */
1058 prefetch_hash.put(curr,tocompare);
1062 /** This functions processes for FlatNewNode
1063 * for e.g x = NEW(foo) followed by childnode with prefetch set x.f
1064 * then drop the prefetches beyond this FlatNewNode */
1065 private void processFlatNewNode(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
1066 Hashtable<FlatNode, PairMap> parentpmap) {
1067 boolean pSetHasChanged = false;
1068 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1069 FlatNew currfnn = (FlatNew) curr;
1070 Float newprob = new Float((float)0.0);
1071 PairMap pm = new PairMap();
1072 PrefetchPair childpp = null;
1073 Enumeration ecld = null;
1075 ecld = child_prefetch_set_copy.keys();
1076 while (ecld.hasMoreElements()) {
1077 childpp = (PrefetchPair) ecld.nextElement();
1078 if(childpp.base == currfnn.getDst()){
1079 child_prefetch_set_copy.remove(childpp);
1081 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1082 pm.addPair(childpp, childpp);
1083 child_prefetch_set_copy.remove(childpp);
1087 /* Create prefetch mappings for child nodes */
1089 parentpmap.put(curr, pm);
1091 pmap_hash.put(curr.getNext(0), parentpmap);
1093 /* Compare with the old prefetch set */
1094 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1096 /* Enqueue parent nodes */
1097 if(pSetHasChanged) {
1098 for(int i=0; i<curr.numPrev(); i++) {
1099 tovisit.add(curr.getPrev(i));
1101 /* Overwrite the new prefetch set to the global hash table */
1102 prefetch_hash.put(curr,tocompare);
1106 /** This functions processes for FlatCastNode
1107 * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1108 * then drop the prefetches beyond this FlatCastNode */
1109 private void processFlatCastNode(FlatNode curr, Hashtable<PrefetchPair, Float>child_prefetch_set_copy,
1110 Hashtable<FlatNode, PairMap> parentpmap) {
1111 boolean pSetHasChanged = false;
1112 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1113 FlatCastNode currfcn = (FlatCastNode) curr;
1114 Float newprob = new Float((float)0.0);
1115 PairMap pm = new PairMap();
1116 PrefetchPair childpp = null;
1117 Enumeration ecld = null;
1119 ecld = child_prefetch_set_copy.keys();
1120 while (ecld.hasMoreElements()) {
1121 childpp = (PrefetchPair) ecld.nextElement();
1122 if(childpp.base == currfcn.getDst()){
1123 child_prefetch_set_copy.remove(childpp);
1125 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1126 pm.addPair(childpp, childpp);
1127 child_prefetch_set_copy.remove(childpp);
1131 /* Create prefetch mappings for child nodes */
1133 parentpmap.put(curr, pm);
1135 pmap_hash.put(curr.getNext(0), parentpmap);
1137 /* Compare with the old prefetch set */
1138 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1140 /* Enqueue parent nodes */
1141 if(pSetHasChanged) {
1142 for(int i=0; i<curr.numPrev(); i++) {
1143 tovisit.add(curr.getPrev(i));
1145 /* Overwrite the new prefetch set to the global hash table */
1146 prefetch_hash.put(curr,tocompare);
1150 /** This functions processes for FlatTagDeclaration
1151 * for e.g x = (cast type) y followed by childnode with prefetch set x.f
1152 * then drop the prefetches beyond this FlatTagDeclaration */
1153 private void processFlatTagDeclaration(FlatNode curr, Hashtable<PrefetchPair, Float>child_prefetch_set_copy,
1154 Hashtable<FlatNode, PairMap> parentpmap) {
1155 boolean pSetHasChanged = false;
1156 Hashtable<PrefetchPair, Float> tocompare = new Hashtable<PrefetchPair, Float>();
1157 FlatTagDeclaration currftd = (FlatTagDeclaration) curr;
1158 Float newprob = new Float((float)0.0);
1159 PairMap pm = new PairMap();
1160 PrefetchPair childpp = null;
1161 Enumeration ecld = null;
1163 ecld = child_prefetch_set_copy.keys();
1164 while (ecld.hasMoreElements()) {
1165 childpp = (PrefetchPair) ecld.nextElement();
1166 if(childpp.base == currftd.getDst()){
1167 child_prefetch_set_copy.remove(childpp);
1169 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
1170 pm.addPair(childpp, childpp);
1171 child_prefetch_set_copy.remove(childpp);
1175 /* Create prefetch mappings for child nodes */
1177 parentpmap.put(curr, pm);
1179 pmap_hash.put(curr.getNext(0), parentpmap);
1181 /* Compare with the old prefetch set */
1182 pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare);
1184 /* Enqueue parent nodes */
1185 if(pSetHasChanged) {
1186 for(int i=0; i<curr.numPrev(); i++) {
1187 tovisit.add(curr.getPrev(i));
1189 /* Overwrite the new prefetch set to the global hash table */
1190 prefetch_hash.put(curr,tocompare);
1194 /** This function prints the Prefetch pairs of a given flatnode */
1195 private void printPrefetchPairs(FlatNode fn) {
1196 if(prefetch_hash.containsKey(fn)) {
1197 System.out.print("Prefetch" + "(");
1198 Hashtable<PrefetchPair, Float> currhash = (Hashtable) prefetch_hash.get(fn);
1199 for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
1200 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
1201 System.out.print(pp.toString() + ", ");
1203 System.out.println(")");
1205 System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
1209 private void doInsPrefetchAnalysis(FlatMethod fm) {
1210 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
1211 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
1212 newvisited = new LinkedList<FlatNode>();
1214 newtovisit.addLast((FlatNode)fm);
1215 while(!newtovisit.isEmpty()) {
1216 FlatNode fn = (FlatNode) newtovisit.iterator().next();
1217 newtovisit.remove(0);
1218 pset1_hash.put(fn, pset1_init);
1219 newvisited.addLast(fn);
1220 for(int i=0; i<fn.numNext(); i++) {
1221 FlatNode nn = fn.getNext(i);
1222 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
1223 newtovisit.addLast(nn);
1228 while(!newvisited.isEmpty()) {
1229 applyPrefetchInsertRules((FlatNode) newvisited.getFirst());
1230 newvisited.remove(0);
1236 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
1237 * returns: true if something has changed in the new Prefetch set else
1240 private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
1241 boolean hasChanged = false;
1243 if(oldPSet.size() != newPSet.size()) {
1246 for(Iterator it = newPSet.iterator();it.hasNext();) {
1247 if(!oldPSet.contains((PrefetchPair)it.next())) {
1255 private void applyPrefetchInsertRules(FlatNode fn) {
1256 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
1257 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
1258 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
1259 Hashtable<PrefetchPair, Float> prefetchset = new Hashtable<PrefetchPair, Float>();
1260 boolean ppairIsPresent = false;
1261 boolean mapIsPresent = true;
1262 boolean pprobIsGreater = false;
1263 boolean mapprobIsLess = false;
1264 boolean probIsLess = false;
1265 boolean pSet1HasChanged = false;
1266 Enumeration e = null;
1268 if(fn.kind() == FKind.FlatMethod) {
1269 if(prefetch_hash.containsKey(fn)) {
1270 prefetchset = prefetch_hash.get(fn);
1271 e = prefetchset.keys();
1272 while(e.hasMoreElements()) {
1273 PrefetchPair pp = (PrefetchPair) e.nextElement();
1274 /* Apply initial rule */
1275 if(((float)prefetchset.get(pp).floatValue()) > PREFETCH_THRESHOLD_PROB) {
1279 /* Enqueue child node is Pset1 has changed */
1280 pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1281 if(pSet1HasChanged) {
1282 for(int j=0; j<fn.numNext(); j++) {
1283 FlatNode nn = fn.getNext(j);
1284 newvisited.addLast((FlatNode)nn);
1287 pset1_hash.put(fn, pset1);
1288 if(pset1.size() > 0) {
1289 newprefetchset.put(fn, pset1);
1293 if(prefetch_hash.containsKey(fn)) {
1294 prefetchset = prefetch_hash.get(fn);
1295 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
1296 PrefetchPair pp = (PrefetchPair) epset.nextElement();
1298 Hashtable<FlatNode, PairMap> ppairmaphash = new Hashtable<FlatNode, PairMap>();
1299 ppairmaphash = pmap_hash.get(fn);
1300 if(!ppairmaphash.isEmpty()) {
1301 e = ppairmaphash.keys();
1302 while(e.hasMoreElements()) {
1303 FlatNode parentnode = (FlatNode) e.nextElement();
1304 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1305 if(pset1_hash.containsKey(parentnode)) {
1306 HashSet pset = pset1_hash.get(parentnode);
1307 if(!pset.isEmpty()) {
1308 if(ppairIsPresent = (pset.contains((PrefetchPair) pm.getPair(pp)))) {
1309 mapIsPresent = ppairIsPresent && mapIsPresent;
1312 mapIsPresent = false;
1321 /* Create newprefetchset */
1322 if(pprobIsGreater = (prefetchset.get(pp).floatValue() > PREFETCH_THRESHOLD_PROB)) {
1323 ppairmaphash = pmap_hash.get(fn);
1324 if(!ppairmaphash.isEmpty()) {
1325 e = ppairmaphash.keys();
1326 while(e.hasMoreElements()) {
1327 FlatNode parentnode = (FlatNode) e.nextElement();
1328 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
1329 PrefetchPair mappedpp = pm.getPair(pp);
1330 if(mappedpp != null) {
1331 if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
1332 float prob = (float)prefetch_hash.get(parentnode).get(mappedpp).floatValue();
1333 if(probIsLess = (prob < PREFETCH_THRESHOLD_PROB))
1334 mapprobIsLess = mapprobIsLess || probIsLess;
1337 mapprobIsLess = false;
1341 mapprobIsLess = true;
1344 if(pprobIsGreater && mapprobIsLess) {
1349 if(!pset2.isEmpty())
1350 pset1.addAll(pset2);
1351 if(!newpset.isEmpty())
1352 pset1.addAll(newpset);
1353 /* Enqueue child node if Pset1 has changed */
1354 pSet1HasChanged = comparePSet1(pset1_hash.get(fn), pset1);
1355 if(pSet1HasChanged) {
1356 for(int i=0; i<fn.numNext(); i++) {
1357 FlatNode nn = fn.getNext(i);
1358 newvisited.addLast((FlatNode)nn);
1361 pset1_hash.put(fn, pset1);
1363 /* To insert prefetch apply rule */
1364 HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
1365 //if(!newpset.isEmpty() && !pset2.isEmpty()) {
1366 if(!newpset.isEmpty()) {
1367 if(!pset2.isEmpty()) {
1368 for(Iterator it = newpset.iterator(); it.hasNext();) {
1369 PrefetchPair pp = (PrefetchPair) it.next();
1370 if(!pset2.contains(pp)) {
1375 for(Iterator it = newpset.iterator(); it.hasNext();) {
1376 PrefetchPair pp = (PrefetchPair) it.next();
1382 newprefetchset.put(fn, s);
1388 private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
1390 Enumeration e = null;
1391 e = newprefetchset.keys();
1392 /* This modifies the graph */
1393 while(e.hasMoreElements()) {
1394 FlatNode fn = (FlatNode) e.nextElement();
1395 FlatPrefetchNode fpn = new FlatPrefetchNode();
1396 for(i = 0; i< newprefetchset.get(fn).size(); i++) {
1397 fpn.insAllpp((HashSet)newprefetchset.get(fn));
1399 //System.out.println("The HashSet of prefetch pairs are "+ fpn.getPrefetchPairs());
1400 if(fn.kind() == FKind.FlatMethod) {
1401 FlatNode nn = fn.getNext(0);
1405 while(fn.numPrev() > 0) {
1406 FlatNode nn = fn.getPrev(0);
1407 for(int j = 0; j<nn.numNext(); j++) {
1408 if(nn.getNext(j) == fn) {
1418 private void doAnalysis() {
1419 Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();
1420 while(classit.hasNext()) {
1421 ClassDescriptor cn=(ClassDescriptor)classit.next();
1422 Iterator methodit=cn.getMethods();
1423 while(methodit.hasNext()) {
1424 /* Classify parameters */
1425 MethodDescriptor md=(MethodDescriptor)methodit.next();
1426 FlatMethod fm=state.getMethodFlat(md);
1432 private void printMethod(FlatMethod fm) {
1433 System.out.println(fm.getMethod()+" {");
1434 HashSet tovisit=new HashSet();
1435 HashSet visited=new HashSet();
1437 Hashtable nodetolabel=new Hashtable();
1439 FlatNode current_node=null;
1441 //Node needs a label if it is
1442 while(!tovisit.isEmpty()) {
1443 FlatNode fn=(FlatNode)tovisit.iterator().next();
1447 for(int i=0;i<fn.numNext();i++) {
1448 FlatNode nn=fn.getNext(i);
1450 //1) Edge >1 of node
1451 nodetolabel.put(nn,new Integer(labelindex++));
1453 if (!visited.contains(nn)&&!tovisit.contains(nn)) {
1457 nodetolabel.put(nn,new Integer(labelindex++));
1461 //Do the actual printing
1462 tovisit=new HashSet();
1463 visited=new HashSet();
1465 while(current_node!=null||!tovisit.isEmpty()) {
1466 if (current_node==null) {
1467 current_node=(FlatNode)tovisit.iterator().next();
1468 tovisit.remove(current_node);
1470 visited.add(current_node);
1471 if (nodetolabel.containsKey(current_node))
1472 System.out.println("L"+nodetolabel.get(current_node)+":");
1473 if (current_node.numNext()==0) {
1474 System.out.println(" "+current_node.toString());
1476 } else if(current_node.numNext()==1) {
1477 System.out.println(" "+current_node.toString());
1478 FlatNode nextnode=current_node.getNext(0);
1479 if (visited.contains(nextnode)) {
1480 System.out.println("goto L"+nodetolabel.get(nextnode));
1483 current_node=nextnode;
1484 } else if (current_node.numNext()==2) {
1486 System.out.println(" "+((FlatCondBranch)current_node).toString("L"+nodetolabel.get(current_node.getNext(1))));
1487 if (!visited.contains(current_node.getNext(1)))
1488 tovisit.add(current_node.getNext(1));
1489 if (visited.contains(current_node.getNext(0))) {
1490 System.out.println("goto L"+nodetolabel.get(current_node.getNext(0)));
1493 current_node=current_node.getNext(0);
1494 } else throw new Error();
1496 System.out.println("}");