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();
76 doChildNodeAnalysis(fm.getMethod(),fn);
82 * This function generates the prefetch sets for a given Flatnode considering the kind of node
83 * It calls severals functions based on the kind of the node and
84 * returns true: if the prefetch set has changed since last time the node was analysed
85 * returns false : otherwise
87 private void doChildNodeAnalysis(MethodDescriptor md, FlatNode curr) {
88 if (curr.kind()==FKind.FlatCondBranch) {
89 processFlatCondBranch((FlatCondBranch)curr, md);
91 Hashtable<PrefetchPair, Double> child_prefetch_set_copy = new Hashtable<PrefetchPair, Double>();
92 if(curr.numNext() != 0) {
93 FlatNode child_node = curr.getNext(0);
94 if(prefetch_hash.containsKey(child_node)) {
95 child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>) prefetch_hash.get(child_node).clone();
101 processCall((FlatCall)curr,child_prefetch_set_copy);
104 case FKind.FlatBackEdge:
105 case FKind.FlatCheckNode:
106 case FKind.FlatReturnNode:
107 case FKind.FlatAtomicEnterNode:
108 case FKind.FlatAtomicExitNode:
109 case FKind.FlatFlagActionNode:
110 case FKind.FlatGlobalConvNode:
113 case FKind.FlatCastNode:
114 case FKind.FlatTagDeclaration:
115 processDefaultCase(curr,child_prefetch_set_copy);
117 case FKind.FlatMethod:
118 //TODO change it to take care of FlatMethod, Flatcalls
119 processFlatMethod(curr, child_prefetch_set_copy);
121 case FKind.FlatFieldNode:
122 processFlatFieldNode(curr, child_prefetch_set_copy);
124 case FKind.FlatElementNode:
125 processFlatElementNode(curr, child_prefetch_set_copy);
127 case FKind.FlatOpNode:
128 processFlatOpNode(curr, child_prefetch_set_copy);
130 case FKind.FlatLiteralNode:
131 processFlatLiteralNode(curr, child_prefetch_set_copy);
133 case FKind.FlatSetElementNode:
134 processFlatSetElementNode(curr, child_prefetch_set_copy);
136 case FKind.FlatSetFieldNode:
137 processFlatSetFieldNode(curr, child_prefetch_set_copy);
140 throw new Error("No such Flatnode kind");
145 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
146 * returns: true if something has changed in the new Prefetch set else
149 private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double> newPrefetchSet) {
150 if (oldPrefetchSet.size()!=newPrefetchSet.size())
153 for(Enumeration e = newPrefetchSet.keys();e.hasMoreElements();) {
154 PrefetchPair pp = (PrefetchPair) e.nextElement();
155 double newprob = newPrefetchSet.get(pp).doubleValue();
156 if (!oldPrefetchSet.containsKey(pp))
158 double oldprob = oldPrefetchSet.get(pp).doubleValue();
160 if((newprob - oldprob) > PROB_DIFF) {
163 if (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB) {
166 if (oldprob>newprob) {
167 System.out.println("ERROR:" + pp);
168 System.out.println(oldprob + " -> "+ newprob);
174 private void updatePairMap(FlatNode curr, PairMap pm, int index) {
175 if (index>=curr.numNext())
177 if (!pmap_hash.containsKey(curr.getNext(index))) {
178 pmap_hash.put(curr.getNext(index), new Hashtable<FlatNode, PairMap>());
180 pmap_hash.get(curr.getNext(index)).put(curr, pm);
183 private void updatePrefetchSet(FlatNode curr, Hashtable<PrefetchPair, Double> newset) {
184 Hashtable<PrefetchPair, Double>oldset=prefetch_hash.get(curr);
185 if (comparePrefetchSets(oldset, newset)) {
186 for(int i=0;i<curr.numPrev();i++) {
187 tovisit.add(curr.getPrev(i));
189 prefetch_hash.put(curr, newset);
194 /** This function processes the prefetch set of FlatFieldNode
195 * It generates a new prefetch set after comparision with its children
196 * Then compares it with its old prefetch set
197 * If old prefetch set is not same as new prefetch set then enqueue the parents
198 * of the current FlatFieldNode
200 private void processFlatFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
201 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
202 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
203 FlatFieldNode currffn = (FlatFieldNode) curr;
204 PairMap pm = new PairMap();
206 /* Do Self analysis of the current node*/
207 FieldDescriptor currffn_field = currffn.getField();
208 TempDescriptor currffn_src = currffn.getSrc();
209 if (currffn_field.getType().isPtr()) {
210 PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field);
211 Double prob = new Double(1.0);
212 tocompare.put(pp, prob);
215 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
217 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
218 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
219 if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) {
220 if (currffn.getField().getType().isPtr()) {
221 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
222 newdesc.add(currffn.getField());
223 newdesc.addAll(childpp.desc);
224 PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc);
225 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
226 if (tocompare.containsKey(newpp)) {
227 Double oldprob=tocompare.get(newpp);
228 newprob=1.0-(1.0-oldprob)*(1.0-newprob);
230 tocompare.put(newpp, newprob);
231 pm.addPair(childpp, newpp);
234 } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
235 //covered by current prefetch
236 child_prefetch_set_copy.remove(childpp);
237 } else if(childpp.containsTemp(currffn.getDst())) {
238 child_prefetch_set_copy.remove(childpp);
240 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
241 if (tocompare.containsKey(childpp)) {
242 Double oldprob=tocompare.get(childpp);
243 newprob=1.0-(1.0-oldprob)*(1.0-newprob);
245 tocompare.put(childpp, newprob);
246 pm.addPair(childpp, childpp);
250 for(Iterator<PrefetchPair> it=tocompare.keySet().iterator();it.hasNext();) {
251 PrefetchPair pp=it.next();
252 if (tocompare.get(pp)<ANALYSIS_THRESHOLD_PROB)
257 updatePairMap(curr, pm, 0);
258 updatePrefetchSet(curr, tocompare);
261 /** This function processes the prefetch set of a FlatElementNode
262 * It generates a new prefetch set after comparision with its children
263 * It compares the old prefetch set with this new prefetch set and enqueues the parents
264 * of the current node if change occurs and updates the global flatnode hash table
266 private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
268 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
269 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
270 FlatElementNode currfen = (FlatElementNode) curr;
271 PairMap pm = new PairMap();
274 /* Do Self analysis of the current node*/
275 TempDescriptor currfen_index = currfen.getIndex();
276 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
277 TempDescriptor currfen_src = currfen.getSrc();
278 if(currfen.getDst().getType().isPtr()) {
279 PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
280 Double prob = new Double(1.0);
281 currcopy.put(pp, prob);
284 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
285 PrefetchPair currpp = null;
286 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
287 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
288 if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
289 if (currfen.getDst().getType().isPtr()) {
290 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
291 newdesc.add((Descriptor)idesc);
292 newdesc.addAll(childpp.desc);
293 PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc);
294 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
295 tocompare.put(newpp, newprob);
296 pm.addPair(childpp, newpp);
297 child_prefetch_set_copy.remove(childpp);
298 /* Check for independence of prefetch pairs to compute new probability */
299 if(child_prefetch_set_copy.containsKey(newpp)) {
300 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
301 if(newprob < ANALYSIS_THRESHOLD_PROB) {
302 tocompare.remove(newpp);
304 tocompare.put(newpp, newprob);
305 pm.addPair(newpp, newpp);
307 child_prefetch_set_copy.remove(newpp);
310 } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
311 child_prefetch_set_copy.remove(childpp);
312 } else if(childpp.containsTemp(currfen.getDst())) {
313 child_prefetch_set_copy.remove(childpp);
318 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
319 * if so calculate the new probability */
320 for(Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
321 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
322 for(Enumeration e = currcopy.keys(); e.hasMoreElements();) {
323 currpp = (PrefetchPair) e.nextElement();
324 if(currpp.equals(childpp)) {
325 pm.addPair(childpp, currpp);
326 child_prefetch_set_copy.remove(childpp);
332 /* Merge child prefetch pairs */
333 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
334 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
335 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
336 pm.addPair(childpp, childpp);
337 child_prefetch_set_copy.remove(childpp);
340 /* Merge curr prefetch pairs */
341 for (Enumeration e = currcopy.keys();e.hasMoreElements();) {
342 currpp = (PrefetchPair) e.nextElement();
343 tocompare.put(currpp, currcopy.get(currpp).doubleValue());
344 currcopy.remove(currpp);
347 updatePairMap(curr, pm, 0);
348 updatePrefetchSet(curr, tocompare);
351 /** This function processes the prefetch set of a FlatSetFieldNode
352 * It generates a new prefetch set after comparision with its children
353 * It compares the old prefetch set with this new prefetch set and enqueues the parents
354 * of the current node if change occurs and then updates the global flatnode hash table
356 private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
357 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
358 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
359 PairMap pm = new PairMap();
361 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
362 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
363 if(childpp.base == currfsfn.getDst()) {
364 int size = childpp.desc.size();
365 if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
366 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
367 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
368 for(int i = 0;i<(childpp.desc.size()-1); i++) {
369 newdesc.add(i,childpp.desc.get(i+1));
371 PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc);
372 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
373 tocompare.put(newpp, newprob);
374 pm.addPair(childpp, newpp);
375 child_prefetch_set_copy.remove(childpp);
376 /* Check for independence of prefetch pairs in newly generated prefetch pair
377 * to compute new probability */
378 if(child_prefetch_set_copy.containsKey(newpp)) {
379 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
380 if(newprob < ANALYSIS_THRESHOLD_PROB) {
381 tocompare.remove(newpp);
383 tocompare.put(newpp, newprob);
384 pm.addPair(newpp, newpp);
386 child_prefetch_set_copy.remove(newpp);
389 } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */
390 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
391 child_prefetch_set_copy.remove(childpp);
399 /* Merge child prefetch pairs */
400 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
401 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
402 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
403 pm.addPair(childpp, childpp);
404 child_prefetch_set_copy.remove(childpp);
407 updatePairMap(curr, pm, 0);
408 updatePrefetchSet(curr, tocompare);
411 /** This function processes the prefetch set of a FlatSetElementNode
412 * It generates a new prefetch set after comparision with its children
413 * It compares the old prefetch set with this new prefetch set and enqueues the parents
414 * of the current node if change occurs and then updates the global flatnode hash table
416 private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
417 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
418 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
419 PairMap pm = new PairMap();
421 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
422 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
423 if (childpp.base == currfsen.getDst()){
424 int sizedesc = childpp.desc.size();
425 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
426 int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
427 if(sizetempdesc == 1) {
428 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
429 /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
430 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
431 for(int i = 0;i<(childpp.desc.size()-1); i++) {
432 newdesc.add(i,childpp.desc.get(i+1));
434 PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc);
435 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
436 tocompare.put(newpp, newprob);
437 pm.addPair(childpp, newpp);
438 child_prefetch_set_copy.remove(childpp);
439 /* Check for independence of prefetch pairs to compute new probability */
440 if(child_prefetch_set_copy.containsKey(newpp)) {
441 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
442 if(newprob < ANALYSIS_THRESHOLD_PROB) {
443 tocompare.remove(newpp);
445 tocompare.put(newpp, newprob);
446 pm.addPair(newpp, newpp);
448 child_prefetch_set_copy.remove(newpp);
450 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
451 /* For e.g. a[i] = g with child prefetch set a[i] */
452 child_prefetch_set_copy.remove(childpp);
459 /* Merge child prefetch pairs */
460 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
461 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
462 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
463 pm.addPair(childpp, childpp);
464 child_prefetch_set_copy.remove(childpp);
467 updatePairMap(curr, pm, 0);
468 updatePrefetchSet(curr, tocompare);
471 /** This function applies rules and does analysis for a FlatOpNode
472 * And updates the global prefetch hashtable
474 private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
476 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
477 FlatOpNode currfopn = (FlatOpNode) curr;
478 PairMap pm = new PairMap();
480 if(currfopn.getOp().getOp() == Operation.ASSIGN) {
481 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
482 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
483 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
485 /* For cases like x=y with child prefetch set x[i].z,x.g*/
486 if(childpp.base == currfopn.getDest()) {
487 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
488 newdesc.addAll(childpp.desc);
489 PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc);
490 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
491 tocompare.put(newpp, newprob);
492 pm.addPair(childpp, newpp);
493 child_prefetch_set_copy.remove(childpp);
494 /* Check for independence of prefetch pairs to compute new probability */
495 if(child_prefetch_set_copy.containsKey(newpp)) {
496 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
497 if(newprob < ANALYSIS_THRESHOLD_PROB) {
498 tocompare.remove(newpp);
500 tocompare.put(newpp, newprob);
501 pm.addPair(newpp, newpp);
503 child_prefetch_set_copy.remove(newpp);
505 /* For cases like x=y with child prefetch set r[x].p, r[p+x].q where x is a tempdescriptor*/
506 } else if(copyofchildpp.containsTemp(currfopn.getDest())) {
507 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft()});
508 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
509 tocompare.put(newpp, newprob);
510 pm.addPair(childpp, newpp);
511 child_prefetch_set_copy.remove(childpp);
512 /* Check for independence of prefetch pairs to compute new probability*/
513 if(child_prefetch_set_copy.containsKey(newpp)) {
514 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
515 if(newprob < ANALYSIS_THRESHOLD_PROB) {
516 tocompare.remove(newpp);
518 tocompare.put(newpp, newprob);
519 pm.addPair(newpp, newpp);
521 child_prefetch_set_copy.remove(newpp);
528 //case i = i+z with child prefetch set a[i].x
529 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
530 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
531 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
532 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
534 if(copyofchildpp.containsTemp(currfopn.getDest())) {
535 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft(), currfopn.getRight()});
536 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
537 tocompare.put(newpp, newprob);
538 pm.addPair(childpp, newpp);
539 child_prefetch_set_copy.remove(childpp);
540 /* Check for independence of prefetch pairs to compute new probability*/
541 if(child_prefetch_set_copy.containsKey(newpp)) {
542 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
543 if(newprob < ANALYSIS_THRESHOLD_PROB) {
544 tocompare.remove(newpp);
546 tocompare.put(newpp, newprob);
547 pm.addPair(newpp, newpp);
549 child_prefetch_set_copy.remove(newpp);
555 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.SUB)) {
556 for(Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
557 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
558 if(childpp.containsTemp(currfopn.getDest())) {
559 child_prefetch_set_copy.remove(childpp);
563 //FIXME Is not taken care of for cases like x = -y followed by a[x].i
566 /* Merge child prefetch pairs */
567 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
568 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
569 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
570 pm.addPair(childpp, childpp);
571 child_prefetch_set_copy.remove(childpp);
574 updatePairMap(curr, pm, 0);
575 updatePrefetchSet(curr, tocompare);
578 /** This function processes a FlatLiteralNode where cases such as
579 * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r
581 private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
582 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
583 FlatLiteralNode currfln = (FlatLiteralNode) curr;
584 PairMap pm = new PairMap();
586 if(currfln.getType().isIntegerType()) {
587 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
588 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
589 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
590 if(copyofchildpp.containsTemp(currfln.getDst())) {
591 ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
592 int sizetempdesc = copychilddesc.size();
593 for(ListIterator it = copychilddesc.listIterator();it.hasNext();) {
594 Object o = it.next();
595 if(o instanceof IndexDescriptor) {
596 ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
597 int sizetddesc = td.size();
598 if(td.contains(currfln.getDst())) {
599 int index = td.indexOf(currfln.getDst());
601 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
605 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
606 newdesc.addAll(copychilddesc);
607 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
608 Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue();
609 tocompare.put(newpp, newprob);
610 pm.addPair(childpp, newpp);
611 child_prefetch_set_copy.remove(childpp);
612 /* Check for independence of prefetch pairs to compute new probability */
613 if(child_prefetch_set_copy.containsKey(newpp)) {
614 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
615 if(newprob < ANALYSIS_THRESHOLD_PROB) {
616 tocompare.remove(newpp);
618 tocompare.put(newpp, newprob);
619 pm.addPair(newpp, newpp);
621 child_prefetch_set_copy.remove(newpp);
627 /* Merge child prefetch pairs */
628 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
629 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
630 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
631 pm.addPair(childpp, childpp);
632 child_prefetch_set_copy.remove(childpp);
635 updatePairMap(curr, pm, 0);
636 updatePrefetchSet(curr, tocompare);
639 /** This function processes a FlatMethod where the method propagates
640 * the entire prefetch set of its child node */
641 private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
642 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
643 FlatMethod currfm = (FlatMethod) curr;
644 PairMap pm = new PairMap();
646 /* Merge child prefetch pairs */
647 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
648 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
649 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
650 pm.addPair(childpp, childpp);
653 updatePairMap(curr, pm, 0);
654 updatePrefetchSet(curr, tocompare);
657 /** This function handles the processes the FlatNode of type FlatCondBranch
658 * It combines prefetches of both child elements and create a new hash table called
659 * branch_prefetch_set to contains the entries of both its children
661 private void processFlatCondBranch(FlatCondBranch fcb, MethodDescriptor md) {
662 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();//temporary hash table
663 PairMap truepm = new PairMap();
664 PairMap falsepm = new PairMap();
665 Hashtable<PrefetchPair, Double> truechild=prefetch_hash.get(fcb.getNext(0));
666 Hashtable<PrefetchPair, Double> falsechild=prefetch_hash.get(fcb.getNext(1));
668 HashSet<PrefetchPair> allpp=new HashSet<PrefetchPair>();
669 allpp.addAll(truechild.keySet());
670 allpp.addAll(falsechild.keySet());
672 for(Iterator<PrefetchPair> ppit=allpp.iterator();ppit.hasNext();) {
673 PrefetchPair pp=ppit.next();
674 double trueprob=0,falseprob=0;
675 if (truechild.containsKey(pp))
676 trueprob=truechild.get(pp).doubleValue();
677 if (falsechild.containsKey(pp))
678 falseprob=falsechild.get(pp).doubleValue();
680 double newprob=trueprob*fcb.getTrueProb()+falseprob*fcb.getFalseProb();
681 if (loop.isLoopingBranch(md,fcb)&&
686 if(newprob < ANALYSIS_THRESHOLD_PROB) //Skip pp that are below threshold
689 tocompare.put(pp, newprob);
690 if (truechild.containsKey(pp))
691 truepm.addPair(pp, pp);
693 if (falsechild.containsKey(pp))
694 falsepm.addPair(pp, pp);
698 updatePairMap(fcb, truepm, 0);
699 updatePairMap(fcb, falsepm, 1);
700 updatePrefetchSet(fcb, tocompare);
703 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
704 * prefetches up the FlatNode*/
705 private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
706 PairMap pm = new PairMap();
707 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
709 /* Propagate all child nodes */
711 for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
712 PrefetchPair childpp = (PrefetchPair) e.nextElement();
713 TempDescriptor[] writearray=curr.writesTemps();
714 for(int i=0;i<writearray.length;i++) {
715 TempDescriptor wtd=writearray[i];
716 if(childpp.base == wtd||
717 childpp.containsTemp(wtd))
720 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
721 pm.addPair(childpp, childpp);
724 updatePairMap(curr, pm, 0);
725 updatePrefetchSet(curr, tocompare);
728 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
729 * prefetches up the FlatNode*/
730 private void processCall(FlatCall curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
731 PairMap pm = new PairMap();
732 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
734 /* Don't propagate prefetches across cache clear */
735 if (!curr.getMethod().getClassMethodName().equals("System.clearPrefetchCache")) {
736 /* Propagate all child nodes */
738 for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
739 PrefetchPair childpp = (PrefetchPair) e.nextElement();
740 TempDescriptor[] writearray=curr.writesTemps();
741 for(int i=0;i<writearray.length;i++) {
742 TempDescriptor wtd=writearray[i];
743 if(childpp.base == wtd||
744 childpp.containsTemp(wtd))
747 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
748 pm.addPair(childpp, childpp);
752 updatePairMap(curr, pm, 0);
753 updatePrefetchSet(curr, tocompare);
756 /** This function prints the Prefetch pairs of a given flatnode */
757 private void printPrefetchPairs(FlatNode fn) {
758 System.out.println(fn);
759 if(prefetch_hash.containsKey(fn)) {
760 System.out.print("Prefetch" + "(");
761 Hashtable<PrefetchPair, Double> currhash = (Hashtable) prefetch_hash.get(fn);
762 for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
763 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
764 System.out.print(pp.toString() + ", ");
766 System.out.println(")");
768 System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
772 private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
773 Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
774 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
775 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
776 LinkedList<FlatNode> newvisited = new LinkedList<FlatNode>();
778 newtovisit.addLast((FlatNode)fm);
779 while(!newtovisit.isEmpty()) {
780 FlatNode fn = (FlatNode) newtovisit.iterator().next();
781 newtovisit.remove(0);
782 pset1_hash.put(fn, pset1_init); //Initialize pset1_hash
783 newvisited.addLast(fn);
784 for(int i=0; i<fn.numNext(); i++) {
785 FlatNode nn = fn.getNext(i);
786 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
787 newtovisit.addLast(nn);
792 /* Start with a top down sorted order of nodes */
793 while(!newvisited.isEmpty()) {
794 applyPrefetchInsertRules((FlatNode) newvisited.getFirst(), newvisited, pset1_hash, newprefetchset);
795 newvisited.remove(0);
797 delSubsetPPairs(newprefetchset);
800 /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
801 * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
802 * then this function drops a.b.c from the prefetch set of the flatnode */
803 private void delSubsetPPairs(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
804 for (Enumeration e = newprefetchset.keys();e.hasMoreElements();) {
805 FlatNode fn = (FlatNode) e.nextElement();
806 Set<PrefetchPair> ppairs = newprefetchset.get(fn);
807 Set<PrefetchPair> toremove=new HashSet<PrefetchPair>();
809 for(Iterator<PrefetchPair> it1=ppairs.iterator();it1.hasNext();) {
810 PrefetchPair pp1=it1.next();
811 if (toremove.contains(pp1))
813 int l1=pp1.desc.size()+1;
814 for(Iterator<PrefetchPair> it2=ppairs.iterator();it2.hasNext();) {
815 PrefetchPair pp2=it2.next();
816 int l2=pp2.desc.size()+1;
818 if (l1<l2&&isSubSet(pp1,pp2))
821 if (l2>l1&&isSubSet(pp2,pp1))
826 ppairs.removeAll(toremove);
830 /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
831 * pair else it returns: false */
832 private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
833 if (shrt.base != lng.base) {
836 for (int j = 0; j < shrt.desc.size(); j++) {
837 if(shrt.getDescAt(j) instanceof IndexDescriptor) {
838 IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
839 if(lng.getDescAt(j) instanceof IndexDescriptor){
840 IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
841 if(shrtid.equals(lngid)) {
850 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
858 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
859 * returns: true if something has changed in the new Prefetch set else
862 private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
863 if(oldPSet.size() != newPSet.size()) {
866 for(Iterator it = newPSet.iterator();it.hasNext();) {
867 if(!oldPSet.contains((PrefetchPair)it.next())) {
875 /** This function creates a set called pset1 that contains prefetch pairs that have already
876 * been prefetched. While traversing the graph of a flat representation in a top down fashion,
877 * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
878 * the previous nodes */
880 private void applyPrefetchInsertRules(FlatNode fn, LinkedList<FlatNode> newvisited, Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
881 if(fn.kind() == FKind.FlatMethod) {
882 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
883 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
884 for(Enumeration e = prefetchset.keys();e.hasMoreElements();) {
885 PrefetchPair pp = (PrefetchPair) e.nextElement();
886 /* Apply initial rule */
887 if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) {
891 /* Enqueue child node if Pset1 has changed */
892 if (comparePSet1(pset1_hash.get(fn), pset1)) {
893 for(int j=0; j<fn.numNext(); j++) {
894 FlatNode nn = fn.getNext(j);
895 newvisited.addLast((FlatNode)nn);
897 pset1_hash.put(fn, pset1);
899 newprefetchset.put(fn, pset1);
900 } else { /* Nodes other than Flat Method Node */
901 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
902 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
903 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
904 Hashtable<FlatNode, PairMap> ppairmaphash = pmap_hash.get(fn);
905 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
906 PrefetchPair pp = (PrefetchPair) epset.nextElement();
907 boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB);
908 boolean mapprobIsLess=false;
909 boolean mapIsPresent=true;
910 for(int i=0;i<fn.numPrev();i++) {
911 FlatNode parentnode=fn.getPrev(i);
912 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
913 //Find if probability is less for previous node
914 if(pm!=null&&pm.getPair(pp) != null) {
915 PrefetchPair mappedpp = pm.getPair(pp);
916 if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
917 double prob = prefetch_hash.get(parentnode).get(mappedpp).doubleValue();
918 if(prob < PREFETCH_THRESHOLD_PROB)
919 mapprobIsLess = true;
921 mapprobIsLess = true;
923 mapprobIsLess = true;
927 HashSet pset = pset1_hash.get(parentnode);
928 if(pset.isEmpty()||!pset.contains((PrefetchPair) pm.getPair(pp)))
929 mapIsPresent = false;
937 if(pprobIsGreater && mapprobIsLess)
941 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
943 pset1.addAll(newpset);
944 /* Enqueue child node if Pset1 has changed */
945 if (comparePSet1(pset1_hash.get(fn), pset1)) {
946 for(int i=0; i<fn.numNext(); i++) {
947 FlatNode nn = fn.getNext(i);
948 newvisited.addLast((FlatNode)nn);
950 pset1_hash.put(fn, pset1);
953 /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
954 * then insert a new prefetch node here*/
956 HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
959 newprefetchset.put(fn, s);
963 private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
964 boolean isFNPresent = false; /* Detects presence of FlatNew node */
965 /* This modifies the Flat representation graph */
966 for(Enumeration e = newprefetchset.keys();e.hasMoreElements();) {
967 FlatNode fn = (FlatNode) e.nextElement();
968 FlatPrefetchNode fpn = new FlatPrefetchNode();
969 if(newprefetchset.get(fn).size() > 0) {
970 fpn.insAllpp((HashSet)newprefetchset.get(fn));
971 if(fn.kind() == FKind.FlatMethod) {
972 FlatNode nn = fn.getNext(0);
975 fpn.siteid = prefetchsiteid++;
977 /* Check if previous node of this FlatNode is a NEW node
978 * If yes, delete this flatnode and its prefetch set from hash table
979 * This eliminates prefetches for NULL ptrs*/
980 for(int i = 0; i< fn.numPrev(); i++) {
981 FlatNode nn = fn.getPrev(i);
982 if(nn.kind() == FKind.FlatNew) {
987 while(fn.numPrev() > 0) {
988 FlatNode nn = fn.getPrev(0);
989 for(int j = 0; j<nn.numNext(); j++) {
990 if(nn.getNext(j) == fn) {
996 fpn.siteid = prefetchsiteid++;