1 package Analysis.Prefetch;
4 import Analysis.CallGraph.CallGraph;
5 import Analysis.Locality.LocalityAnalysis;
6 import Analysis.Prefetch.PrefetchPair;
7 import Analysis.Prefetch.PairMap;
8 import Analysis.Prefetch.IndexDescriptor;
12 import IR.MethodDescriptor;
15 import IR.ClassDescriptor;
17 public class PrefetchAnalysis {
23 Set<FlatNode> tovisit;
24 public Hashtable<FlatNode, Hashtable<PrefetchPair, Double>> prefetch_hash; //holds all flatnodes and corresponding prefetch set
25 public Hashtable<FlatNode, Hashtable<FlatNode, PairMap>> pmap_hash; //holds all flatnodes and mappings between child prefetch pair and parent prefetch pair
26 public static final double PROB_DIFF = 0.05; //threshold for difference in probabilities during first phase of analysis
27 public static final double ANALYSIS_THRESHOLD_PROB = 0.10; //threshold for prefetches to stop propagating during first phase of analysis
28 public static final double PREFETCH_THRESHOLD_PROB = 0.30; //threshold for prefetches to stop propagating while applying prefetch rules during second phase of analysis
29 public static int prefetchsiteid = 1; //initialized to one because there is a prefetch siteid 0 for starting remote thread
30 LocalityAnalysis locality;
32 public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil, LocalityAnalysis locality) {
33 this.typeutil=typeutil;
35 this.callgraph=callgraph;
36 this.locality=locality;
37 prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Double>>();
38 pmap_hash = new Hashtable<FlatNode, Hashtable<FlatNode, PairMap>>();
39 this.loop=new LoopExit(state);
44 /** This function starts the prefetch analysis */
45 private void DoPrefetch() {
46 for (Iterator methodit=locality.getMethods().iterator(); methodit.hasNext();) {
47 MethodDescriptor md=(MethodDescriptor)methodit.next();
48 if (state.excprefetch.contains(md.getClassMethodName()))
49 continue; //Skip this method
50 Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
51 FlatMethod fm=state.getMethodFlat(md);
52 doFlatNodeAnalysis(fm);
53 doInsPrefetchAnalysis(fm, newprefetchset);
54 if(newprefetchset.size() > 0) {
55 addFlatPrefetchNode(newprefetchset);
57 newprefetchset = null;
61 /** This function calls analysis for every node in a method */
62 private void doFlatNodeAnalysis(FlatMethod fm) {
63 tovisit = fm.getNodeSet();
64 Hashtable<PrefetchPair, Double> nodehash = new Hashtable<PrefetchPair, Double>();
65 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
66 while(!tovisit.isEmpty()) {
67 FlatNode fn = (FlatNode)tovisit.iterator().next();
68 prefetch_hash.put(fn, nodehash);
72 /* Visit and process nodes */
73 tovisit = fm.getNodeSet();
74 while(!tovisit.isEmpty()) {
75 FlatNode fn = (FlatNode)tovisit.iterator().next();
78 doChildNodeAnalysis(fm.getMethod(),fn);
83 * This function generates the prefetch sets for a given Flatnode considering the kind of node
84 * It calls severals functions based on the kind of the node and
85 * returns true: if the prefetch set has changed since last time the node was analysed
86 * returns false : otherwise
88 private void doChildNodeAnalysis(MethodDescriptor md, FlatNode curr) {
89 if (curr.kind()==FKind.FlatCondBranch) {
90 processFlatCondBranch((FlatCondBranch)curr, md);
92 Hashtable<PrefetchPair, Double> child_prefetch_set_copy = new Hashtable<PrefetchPair, Double>();
93 if(curr.numNext() != 0) {
94 FlatNode child_node = curr.getNext(0);
95 if(prefetch_hash.containsKey(child_node)) {
96 child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>)prefetch_hash.get(child_node).clone();
100 switch(curr.kind()) {
102 processCall((FlatCall)curr,child_prefetch_set_copy);
105 case FKind.FlatBackEdge:
106 case FKind.FlatCheckNode:
107 case FKind.FlatReturnNode:
108 case FKind.FlatAtomicEnterNode:
109 case FKind.FlatAtomicExitNode:
110 case FKind.FlatFlagActionNode:
111 case FKind.FlatGlobalConvNode:
115 case FKind.FlatCastNode:
116 case FKind.FlatTagDeclaration:
117 case FKind.FlatInstanceOfNode:
118 processDefaultCase(curr,child_prefetch_set_copy);
121 case FKind.FlatMethod:
122 //TODO change it to take care of FlatMethod, Flatcalls
123 processFlatMethod(curr, child_prefetch_set_copy);
126 case FKind.FlatFieldNode:
127 processFlatFieldNode(curr, child_prefetch_set_copy);
130 case FKind.FlatElementNode:
131 processFlatElementNode(curr, child_prefetch_set_copy);
134 case FKind.FlatOpNode:
135 processFlatOpNode(curr, child_prefetch_set_copy);
138 case FKind.FlatLiteralNode:
139 processFlatLiteralNode(curr, child_prefetch_set_copy);
142 case FKind.FlatSetElementNode:
143 processFlatSetElementNode(curr, child_prefetch_set_copy);
146 case FKind.FlatSetFieldNode:
147 processFlatSetFieldNode(curr, child_prefetch_set_copy);
150 case FKind.FlatOffsetNode:
151 processDefaultCase(curr,child_prefetch_set_copy);
155 throw new Error("No such Flatnode kind");
160 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
161 * returns: true if something has changed in the new Prefetch set else
164 private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double> newPrefetchSet) {
165 if (oldPrefetchSet.size()!=newPrefetchSet.size())
168 for(Enumeration e = newPrefetchSet.keys(); e.hasMoreElements();) {
169 PrefetchPair pp = (PrefetchPair) e.nextElement();
170 double newprob = newPrefetchSet.get(pp).doubleValue();
171 if (!oldPrefetchSet.containsKey(pp))
173 double oldprob = oldPrefetchSet.get(pp).doubleValue();
175 if((newprob - oldprob) > PROB_DIFF) {
178 if (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB) {
181 if (oldprob>newprob) {
182 System.out.println("ERROR:" + pp);
183 System.out.println(oldprob + " -> "+ newprob);
189 private void updatePairMap(FlatNode curr, PairMap pm, int index) {
190 if (index>=curr.numNext())
192 if (!pmap_hash.containsKey(curr.getNext(index))) {
193 pmap_hash.put(curr.getNext(index), new Hashtable<FlatNode, PairMap>());
195 pmap_hash.get(curr.getNext(index)).put(curr, pm);
198 private void updatePrefetchSet(FlatNode curr, Hashtable<PrefetchPair, Double> newset) {
199 Hashtable<PrefetchPair, Double>oldset=prefetch_hash.get(curr);
200 if (comparePrefetchSets(oldset, newset)) {
201 for(int i=0; i<curr.numPrev(); i++) {
202 tovisit.add(curr.getPrev(i));
204 prefetch_hash.put(curr, newset);
209 /** This function processes the prefetch set of FlatFieldNode
210 * It generates a new prefetch set after comparision with its children
211 * Then compares it with its old prefetch set
212 * If old prefetch set is not same as new prefetch set then enqueue the parents
213 * of the current FlatFieldNode
215 private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
216 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
217 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
218 FlatFieldNode currffn = (FlatFieldNode) curr;
219 PairMap pm = new PairMap();
221 /* Do Self analysis of the current node*/
222 FieldDescriptor currffn_field = currffn.getField();
223 TempDescriptor currffn_src = currffn.getSrc();
224 if (currffn_field.getType().isPtr()) {
225 PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
226 Double prob = new Double(1.0);
227 tocompare.put(pp, prob);
230 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
232 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
233 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
234 if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
235 if (currffn.getField().getType().isPtr()) {
236 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
237 newdesc.add(currffn.getField());
238 newdesc.addAll(childpp.desc);
239 PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc);
240 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
241 if (tocompare.containsKey(newpp)) {
242 Double oldprob=tocompare.get(newpp);
243 newprob=1.0-(1.0-oldprob)*(1.0-newprob);
245 tocompare.put(newpp, newprob);
246 pm.addPair(childpp, newpp);
249 } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
250 //covered by current prefetch
251 child_prefetch_set_copy.remove(childpp);
252 } else if(childpp.containsTemp(currffn.getDst())) {
253 child_prefetch_set_copy.remove(childpp);
255 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
256 if (tocompare.containsKey(childpp)) {
257 Double oldprob=tocompare.get(childpp);
258 newprob=1.0-(1.0-oldprob)*(1.0-newprob);
260 tocompare.put(childpp, newprob);
261 pm.addPair(childpp, childpp);
265 for(Iterator<PrefetchPair> it=tocompare.keySet().iterator(); it.hasNext();) {
266 PrefetchPair pp=it.next();
267 if (tocompare.get(pp)<ANALYSIS_THRESHOLD_PROB)
272 updatePairMap(curr, pm, 0);
273 updatePrefetchSet(curr, tocompare);
276 /** This function processes the prefetch set of a FlatElementNode
277 * It generates a new prefetch set after comparision with its children
278 * It compares the old prefetch set with this new prefetch set and enqueues the parents
279 * of the current node if change occurs and updates the global flatnode hash table
281 private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
283 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
284 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
285 FlatElementNode currfen = (FlatElementNode) curr;
286 PairMap pm = new PairMap();
289 /* Do Self analysis of the current node*/
290 TempDescriptor currfen_index = currfen.getIndex();
291 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
292 TempDescriptor currfen_src = currfen.getSrc();
293 if(currfen.getDst().getType().isPtr()) {
294 PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
295 Double prob = new Double(1.0);
296 currcopy.put(pp, prob);
299 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
300 PrefetchPair currpp = null;
301 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
302 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
303 if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
304 if (currfen.getDst().getType().isPtr()) {
305 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
306 newdesc.add((Descriptor)idesc);
307 newdesc.addAll(childpp.desc);
308 PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc);
309 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
310 tocompare.put(newpp, newprob);
311 pm.addPair(childpp, newpp);
312 child_prefetch_set_copy.remove(childpp);
313 /* Check for independence of prefetch pairs to compute new probability */
314 if(child_prefetch_set_copy.containsKey(newpp)) {
315 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
316 if(newprob < ANALYSIS_THRESHOLD_PROB) {
317 tocompare.remove(newpp);
319 tocompare.put(newpp, newprob);
320 pm.addPair(newpp, newpp);
322 child_prefetch_set_copy.remove(newpp);
325 } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
326 child_prefetch_set_copy.remove(childpp);
327 } else if(childpp.containsTemp(currfen.getDst())) {
328 child_prefetch_set_copy.remove(childpp);
333 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
334 * if so calculate the new probability */
335 for(Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
336 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
337 for(Enumeration e = currcopy.keys(); e.hasMoreElements();) {
338 currpp = (PrefetchPair) e.nextElement();
339 if(currpp.equals(childpp)) {
340 pm.addPair(childpp, currpp);
341 child_prefetch_set_copy.remove(childpp);
347 /* Merge child prefetch pairs */
348 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
349 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
350 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
351 pm.addPair(childpp, childpp);
352 child_prefetch_set_copy.remove(childpp);
355 /* Merge curr prefetch pairs */
356 for (Enumeration e = currcopy.keys(); e.hasMoreElements();) {
357 currpp = (PrefetchPair) e.nextElement();
358 tocompare.put(currpp, currcopy.get(currpp).doubleValue());
359 currcopy.remove(currpp);
362 updatePairMap(curr, pm, 0);
363 updatePrefetchSet(curr, tocompare);
366 /** This function processes the prefetch set of a FlatSetFieldNode
367 * It generates a new prefetch set after comparision with its children
368 * It compares the old prefetch set with this new prefetch set and enqueues the parents
369 * of the current node if change occurs and then updates the global flatnode hash table
371 private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
372 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
373 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
374 PairMap pm = new PairMap();
376 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
377 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
378 if(childpp.base == currfsfn.getDst()) {
379 int size = childpp.desc.size();
380 if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
381 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
382 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
383 for(int i = 0; i<(childpp.desc.size()-1); i++) {
384 newdesc.add(i,childpp.desc.get(i+1));
386 PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc);
387 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
388 tocompare.put(newpp, newprob);
389 pm.addPair(childpp, newpp);
390 child_prefetch_set_copy.remove(childpp);
391 /* Check for independence of prefetch pairs in newly generated prefetch pair
392 * to compute new probability */
393 if(child_prefetch_set_copy.containsKey(newpp)) {
394 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
395 if(newprob < ANALYSIS_THRESHOLD_PROB) {
396 tocompare.remove(newpp);
398 tocompare.put(newpp, newprob);
399 pm.addPair(newpp, newpp);
401 child_prefetch_set_copy.remove(newpp);
404 } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */
405 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
406 child_prefetch_set_copy.remove(childpp);
414 /* Merge child prefetch pairs */
415 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
416 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
417 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
418 pm.addPair(childpp, childpp);
419 child_prefetch_set_copy.remove(childpp);
422 updatePairMap(curr, pm, 0);
423 updatePrefetchSet(curr, tocompare);
426 /** This function processes the prefetch set of a FlatSetElementNode
427 * It generates a new prefetch set after comparision with its children
428 * It compares the old prefetch set with this new prefetch set and enqueues the parents
429 * of the current node if change occurs and then updates the global flatnode hash table
431 private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
432 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
433 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
434 PairMap pm = new PairMap();
436 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
437 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
438 if (childpp.base == currfsen.getDst()) {
439 int sizedesc = childpp.desc.size();
440 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
441 int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
442 if(sizetempdesc == 1) {
443 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
444 /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
445 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
446 for(int i = 0; i<(childpp.desc.size()-1); i++) {
447 newdesc.add(i,childpp.desc.get(i+1));
449 PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc);
450 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
451 tocompare.put(newpp, newprob);
452 pm.addPair(childpp, newpp);
453 child_prefetch_set_copy.remove(childpp);
454 /* Check for independence of prefetch pairs to compute new probability */
455 if(child_prefetch_set_copy.containsKey(newpp)) {
456 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
457 if(newprob < ANALYSIS_THRESHOLD_PROB) {
458 tocompare.remove(newpp);
460 tocompare.put(newpp, newprob);
461 pm.addPair(newpp, newpp);
463 child_prefetch_set_copy.remove(newpp);
465 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
466 /* For e.g. a[i] = g with child prefetch set a[i] */
467 child_prefetch_set_copy.remove(childpp);
474 /* Merge child prefetch pairs */
475 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
476 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
477 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
478 pm.addPair(childpp, childpp);
479 child_prefetch_set_copy.remove(childpp);
482 updatePairMap(curr, pm, 0);
483 updatePrefetchSet(curr, tocompare);
486 /** This function applies rules and does analysis for a FlatOpNode
487 * And updates the global prefetch hashtable
489 private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
491 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
492 FlatOpNode currfopn = (FlatOpNode) curr;
493 PairMap pm = new PairMap();
495 if(currfopn.getOp().getOp() == Operation.ASSIGN) {
496 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
497 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
498 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
500 /* For cases like x=y with child prefetch set x[i].z,x.g*/
501 if(childpp.base == currfopn.getDest()) {
502 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
503 newdesc.addAll(childpp.desc);
504 PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc);
505 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
506 tocompare.put(newpp, newprob);
507 pm.addPair(childpp, newpp);
508 child_prefetch_set_copy.remove(childpp);
509 /* Check for independence of prefetch pairs to compute new probability */
510 if(child_prefetch_set_copy.containsKey(newpp)) {
511 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
512 if(newprob < ANALYSIS_THRESHOLD_PROB) {
513 tocompare.remove(newpp);
515 tocompare.put(newpp, newprob);
516 pm.addPair(newpp, newpp);
518 child_prefetch_set_copy.remove(newpp);
520 /* For cases like x=y with child prefetch set r[x].p, r[p+x].q where x is a tempdescriptor*/
521 } else if(copyofchildpp.containsTemp(currfopn.getDest())) {
522 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft()});
523 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
524 tocompare.put(newpp, newprob);
525 pm.addPair(childpp, newpp);
526 child_prefetch_set_copy.remove(childpp);
527 /* Check for independence of prefetch pairs to compute new probability*/
528 if(child_prefetch_set_copy.containsKey(newpp)) {
529 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
530 if(newprob < ANALYSIS_THRESHOLD_PROB) {
531 tocompare.remove(newpp);
533 tocompare.put(newpp, newprob);
534 pm.addPair(newpp, newpp);
536 child_prefetch_set_copy.remove(newpp);
543 //case i = i+z with child prefetch set a[i].x
544 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
545 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
546 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
547 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
549 if(copyofchildpp.containsTemp(currfopn.getDest())) {
550 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft(), currfopn.getRight()});
551 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
552 tocompare.put(newpp, newprob);
553 pm.addPair(childpp, newpp);
554 child_prefetch_set_copy.remove(childpp);
555 /* Check for independence of prefetch pairs to compute new probability*/
556 if(child_prefetch_set_copy.containsKey(newpp)) {
557 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
558 if(newprob < ANALYSIS_THRESHOLD_PROB) {
559 tocompare.remove(newpp);
561 tocompare.put(newpp, newprob);
562 pm.addPair(newpp, newpp);
564 child_prefetch_set_copy.remove(newpp);
570 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.SUB)) {
571 for(Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
572 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
573 if(childpp.containsTemp(currfopn.getDest())) {
574 child_prefetch_set_copy.remove(childpp);
578 //FIXME Is not taken care of for cases like x = -y followed by a[x].i
581 /* Merge child prefetch pairs */
582 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
583 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
584 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
585 pm.addPair(childpp, childpp);
586 child_prefetch_set_copy.remove(childpp);
589 updatePairMap(curr, pm, 0);
590 updatePrefetchSet(curr, tocompare);
593 /** This function processes a FlatLiteralNode where cases such as
594 * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r
596 private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
597 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
598 FlatLiteralNode currfln = (FlatLiteralNode) curr;
599 PairMap pm = new PairMap();
601 if(currfln.getType().isIntegerType()) {
602 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
603 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
604 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
605 if(copyofchildpp.containsTemp(currfln.getDst())) {
606 ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>)copyofchildpp.getDesc();
607 int sizetempdesc = copychilddesc.size();
608 for(ListIterator it = copychilddesc.listIterator(); it.hasNext();) {
609 Object o = it.next();
610 if(o instanceof IndexDescriptor) {
611 ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
612 int sizetddesc = td.size();
613 if(td.contains(currfln.getDst())) {
614 int index = td.indexOf(currfln.getDst());
616 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
620 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
621 newdesc.addAll(copychilddesc);
622 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
623 Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue();
624 tocompare.put(newpp, newprob);
625 pm.addPair(childpp, newpp);
626 child_prefetch_set_copy.remove(childpp);
627 /* Check for independence of prefetch pairs to compute new probability */
628 if(child_prefetch_set_copy.containsKey(newpp)) {
629 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
630 if(newprob < ANALYSIS_THRESHOLD_PROB) {
631 tocompare.remove(newpp);
633 tocompare.put(newpp, newprob);
634 pm.addPair(newpp, newpp);
636 child_prefetch_set_copy.remove(newpp);
642 /* Merge child prefetch pairs */
643 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
644 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
645 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
646 pm.addPair(childpp, childpp);
647 child_prefetch_set_copy.remove(childpp);
650 updatePairMap(curr, pm, 0);
651 updatePrefetchSet(curr, tocompare);
654 /** This function processes a FlatMethod where the method propagates
655 * the entire prefetch set of its child node */
656 private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
657 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
658 FlatMethod currfm = (FlatMethod) curr;
659 PairMap pm = new PairMap();
661 /* Merge child prefetch pairs */
662 for (Enumeration ecld = child_prefetch_set_copy.keys(); ecld.hasMoreElements();) {
663 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
664 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
665 pm.addPair(childpp, childpp);
668 updatePairMap(curr, pm, 0);
669 updatePrefetchSet(curr, tocompare);
672 /** This function handles the processes the FlatNode of type FlatCondBranch
673 * It combines prefetches of both child elements and create a new hash table called
674 * branch_prefetch_set to contains the entries of both its children
676 private void processFlatCondBranch(FlatCondBranch fcb, MethodDescriptor md) {
677 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>(); //temporary hash table
678 PairMap truepm = new PairMap();
679 PairMap falsepm = new PairMap();
680 Hashtable<PrefetchPair, Double> truechild=prefetch_hash.get(fcb.getNext(0));
681 Hashtable<PrefetchPair, Double> falsechild=prefetch_hash.get(fcb.getNext(1));
683 HashSet<PrefetchPair> allpp=new HashSet<PrefetchPair>();
684 allpp.addAll(truechild.keySet());
685 allpp.addAll(falsechild.keySet());
687 for(Iterator<PrefetchPair> ppit=allpp.iterator(); ppit.hasNext();) {
688 PrefetchPair pp=ppit.next();
689 double trueprob=0,falseprob=0;
690 if (truechild.containsKey(pp))
691 trueprob=truechild.get(pp).doubleValue();
692 if (falsechild.containsKey(pp))
693 falseprob=falsechild.get(pp).doubleValue();
695 double newprob=trueprob*fcb.getTrueProb()+falseprob*fcb.getFalseProb();
696 if (loop.isLoopingBranch(md,fcb)&&
701 if(newprob < ANALYSIS_THRESHOLD_PROB) //Skip pp that are below threshold
704 tocompare.put(pp, newprob);
705 if (truechild.containsKey(pp))
706 truepm.addPair(pp, pp);
708 if (falsechild.containsKey(pp))
709 falsepm.addPair(pp, pp);
713 updatePairMap(fcb, truepm, 0);
714 updatePairMap(fcb, falsepm, 1);
715 updatePrefetchSet(fcb, tocompare);
718 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
719 * prefetches up the FlatNode*/
720 private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
721 PairMap pm = new PairMap();
722 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
724 /* Propagate all child nodes */
726 for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
727 PrefetchPair childpp = (PrefetchPair) e.nextElement();
728 TempDescriptor[] writearray=curr.writesTemps();
729 for(int i=0; i<writearray.length; i++) {
730 TempDescriptor wtd=writearray[i];
731 if(childpp.base == wtd||
732 childpp.containsTemp(wtd))
735 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
736 pm.addPair(childpp, childpp);
739 updatePairMap(curr, pm, 0);
740 updatePrefetchSet(curr, tocompare);
743 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
744 * prefetches up the FlatNode*/
745 private void processCall(FlatCall curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
746 PairMap pm = new PairMap();
747 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
749 /* Don't propagate prefetches across cache clear */
750 if (!(curr.getMethod().getClassMethodName().equals("System.clearPrefetchCache")||
751 curr.getMethod().getClassMethodName().equals("Barrier.enterBarrier"))) {
752 /* Propagate all child nodes */
754 for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
755 PrefetchPair childpp = (PrefetchPair) e.nextElement();
756 TempDescriptor[] writearray=curr.writesTemps();
757 for(int i=0; i<writearray.length; i++) {
758 TempDescriptor wtd=writearray[i];
759 if(childpp.base == wtd||
760 childpp.containsTemp(wtd))
763 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
764 pm.addPair(childpp, childpp);
768 updatePairMap(curr, pm, 0);
769 updatePrefetchSet(curr, tocompare);
772 /** This function prints the Prefetch pairs of a given flatnode */
773 private void printPrefetchPairs(FlatNode fn) {
774 System.out.println(fn);
775 if(prefetch_hash.containsKey(fn)) {
776 System.out.print("Prefetch" + "(");
777 Hashtable<PrefetchPair, Double> currhash = (Hashtable) prefetch_hash.get(fn);
778 for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
779 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
780 double v=currhash.get(pp).doubleValue();
782 System.out.print(pp.toString() +"-"+v + ", ");
784 System.out.println(")");
786 System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
790 private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
791 Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
793 Set visitset=fm.getNodeSet();
794 while(!visitset.isEmpty()) {
795 FlatNode fn = (FlatNode) visitset.iterator().next();
797 pset1_hash.put(fn, new HashSet<PrefetchPair>());
800 Set tovisit=fm.getNodeSet();
801 /* Start with a top down sorted order of nodes */
802 while(!tovisit.isEmpty()) {
803 FlatNode fn=(FlatNode)tovisit.iterator().next();
805 applyPrefetchInsertRules(fn, tovisit, pset1_hash, newprefetchset);
807 delSubsetPPairs(newprefetchset);
810 /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
811 * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
812 * then this function drops a.b.c from the prefetch set of the flatnode */
813 private void delSubsetPPairs(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
814 for (Enumeration e = newprefetchset.keys(); e.hasMoreElements();) {
815 FlatNode fn = (FlatNode) e.nextElement();
816 Set<PrefetchPair> ppairs = newprefetchset.get(fn);
817 Set<PrefetchPair> toremove=new HashSet<PrefetchPair>();
819 for(Iterator<PrefetchPair> it1=ppairs.iterator(); it1.hasNext();) {
820 PrefetchPair pp1=it1.next();
821 if (toremove.contains(pp1))
823 int l1=pp1.desc.size()+1;
824 for(Iterator<PrefetchPair> it2=ppairs.iterator(); it2.hasNext();) {
825 PrefetchPair pp2=it2.next();
826 int l2=pp2.desc.size()+1;
828 if (l1<l2&&isSubSet(pp1,pp2))
831 if (l2>l1&&isSubSet(pp2,pp1))
836 ppairs.removeAll(toremove);
840 /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
841 * pair else it returns: false */
842 private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
843 if (shrt.base != lng.base) {
846 for (int j = 0; j < shrt.desc.size(); j++) {
847 if(shrt.getDescAt(j) instanceof IndexDescriptor) {
848 IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
849 if(lng.getDescAt(j) instanceof IndexDescriptor) {
850 IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
851 if(shrtid.equals(lngid)) {
860 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)) {
868 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
869 * returns: true if something has changed in the new Prefetch set else
872 private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
873 if(oldPSet.size() != newPSet.size()) {
876 for(Iterator it = newPSet.iterator(); it.hasNext();) {
877 if(!oldPSet.contains((PrefetchPair)it.next())) {
885 /** This function creates a set called pset1 that contains prefetch pairs that have already
886 * been prefetched. While traversing the graph of a flat representation in a top down fashion,
887 * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
888 * the previous nodes */
890 private void applyPrefetchInsertRules(FlatNode fn, Set tovisit, Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
891 if(fn.kind() == FKind.FlatMethod) {
892 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
893 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
894 for(Enumeration e = prefetchset.keys(); e.hasMoreElements();) {
895 PrefetchPair pp = (PrefetchPair) e.nextElement();
896 /* Apply initial rule */
897 if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) {
901 /* Enqueue child node if Pset1 has changed */
902 if (comparePSet1(pset1_hash.get(fn), pset1)) {
903 for(int j=0; j<fn.numNext(); j++) {
904 FlatNode nn = fn.getNext(j);
907 pset1_hash.put(fn, pset1);
909 newprefetchset.put(fn, pset1);
910 } else { /* Nodes other than Flat Method Node */
911 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
912 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
913 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
914 Hashtable<FlatNode, PairMap> ppairmaphash = pmap_hash.get(fn);
915 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
916 PrefetchPair pp = (PrefetchPair) epset.nextElement();
917 boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB);
918 boolean mapprobIsLess=false;
919 boolean mapIsPresent=true;
920 for(int i=0; i<fn.numPrev(); i++) {
921 FlatNode parentnode=fn.getPrev(i);
922 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
923 //Find if probability is less for previous node
924 if(pm!=null&&pm.getPair(pp) != null) {
925 PrefetchPair mappedpp = pm.getPair(pp);
926 if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
927 double prob = prefetch_hash.get(parentnode).get(mappedpp).doubleValue();
928 if(prob < PREFETCH_THRESHOLD_PROB)
929 mapprobIsLess = true;
931 mapprobIsLess = true;
933 mapprobIsLess = true;
937 HashSet pset = pset1_hash.get(parentnode);
938 if(!pset.contains((PrefetchPair) pm.getPair(pp)))
939 mapIsPresent = false;
947 if(pprobIsGreater && mapprobIsLess)
951 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
953 pset1.addAll(newpset);
955 /* Enqueue child node if Pset1 has changed */
956 if (comparePSet1(pset1_hash.get(fn), pset1)) {
957 for(int i=0; i<fn.numNext(); i++) {
958 FlatNode nn = fn.getNext(i);
961 pset1_hash.put(fn, pset1);
964 /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
965 * then insert a new prefetch node here*/
967 HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
970 newprefetchset.put(fn, s);
974 private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
975 /* This modifies the Flat representation graph */
976 for(Enumeration e = newprefetchset.keys(); e.hasMoreElements();) {
977 FlatNode fn = (FlatNode) e.nextElement();
978 FlatPrefetchNode fpn = new FlatPrefetchNode();
979 if(newprefetchset.get(fn).size() > 0) {
980 fpn.insAllpp((HashSet)newprefetchset.get(fn));
981 if(fn.kind() == FKind.FlatMethod) {
982 FlatNode nn = fn.getNext(0);
985 fpn.siteid = prefetchsiteid++;
987 /* Check if previous node of this FlatNode is a NEW node
988 * If yes, delete this flatnode and its prefetch set from hash table
989 * This eliminates prefetches for NULL ptrs*/
990 while(fn.numPrev() > 0) {
991 FlatNode nn = fn.getPrev(0);
992 for(int j = 0; j<nn.numNext(); j++) {
993 if(nn.getNext(j) == fn) {
999 fpn.siteid = prefetchsiteid++;