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 {
22 Set<FlatNode> tovisit;
23 public Hashtable<FlatNode, Hashtable<PrefetchPair, Double>> prefetch_hash;//holds all flatnodes and corresponding prefetch set
24 public Hashtable<FlatNode, Hashtable<FlatNode, PairMap>> pmap_hash;//holds all flatnodes and mappings between child prefetch pair and parent prefetch pair
25 public static final double PROB_DIFF = 0.05; //threshold for difference in probabilities during first phase of analysis
26 public static final double ANALYSIS_THRESHOLD_PROB = 0.10; //threshold for prefetches to stop propagating during first phase of analysis
27 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 PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
30 this.typeutil=typeutil;
32 this.callgraph=callgraph;
33 prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Double>>();
34 pmap_hash = new Hashtable<FlatNode, Hashtable<FlatNode, PairMap>>();
35 this.loop=new LoopExit(state);
40 /** This function starts the prefetch analysis */
41 private void DoPrefetch() {
42 for(Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();classit.hasNext();) {
43 ClassDescriptor cn=(ClassDescriptor)classit.next();
48 /** This function calls analysis for every method in a class */
49 private void doMethodAnalysis(ClassDescriptor cn) {
50 for (Iterator methodit=cn.getMethods();methodit.hasNext();) {
51 MethodDescriptor md=(MethodDescriptor)methodit.next();
52 if (state.excprefetch.contains(md.getClassMethodName()))
53 continue; //Skip this method
54 Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
55 FlatMethod fm=state.getMethodFlat(md);
56 doFlatNodeAnalysis(fm);
57 doInsPrefetchAnalysis(fm, newprefetchset);
58 if(newprefetchset.size() > 0) {
59 addFlatPrefetchNode(newprefetchset);
61 newprefetchset = null;
65 /** This function calls analysis for every node in a method */
66 private void doFlatNodeAnalysis(FlatMethod fm) {
67 tovisit = fm.getNodeSet();
68 Hashtable<PrefetchPair, Double> nodehash = new Hashtable<PrefetchPair, Double>();
69 /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
70 while(!tovisit.isEmpty()) {
71 FlatNode fn = (FlatNode)tovisit.iterator().next();
72 prefetch_hash.put(fn, nodehash);
76 /* Visit and process nodes */
77 tovisit = fm.getNodeSet();
78 while(!tovisit.isEmpty()) {
79 FlatNode fn = (FlatNode)tovisit.iterator().next();
80 doChildNodeAnalysis(fm.getMethod(),fn);
86 * This function generates the prefetch sets for a given Flatnode considering the kind of node
87 * It calls severals functions based on the kind of the node and
88 * returns true: if the prefetch set has changed since last time the node was analysed
89 * returns false : otherwise
91 private void doChildNodeAnalysis(MethodDescriptor md, FlatNode curr) {
92 if (curr.kind()==FKind.FlatCondBranch) {
93 processFlatCondBranch((FlatCondBranch)curr, md);
95 Hashtable<PrefetchPair, Double> child_prefetch_set_copy = new Hashtable<PrefetchPair, Double>();
96 if(curr.numNext() != 0) {
97 FlatNode child_node = curr.getNext(0);
98 if(prefetch_hash.containsKey(child_node)) {
99 child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>) prefetch_hash.get(child_node).clone();
102 switch(curr.kind()) {
103 case FKind.FlatBackEdge:
104 case FKind.FlatCheckNode:
105 case FKind.FlatReturnNode:
106 case FKind.FlatAtomicEnterNode:
107 case FKind.FlatAtomicExitNode:
108 case FKind.FlatFlagActionNode:
109 case FKind.FlatGlobalConvNode:
112 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 currcopy.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 tocompare.put(newpp, newprob);
227 pm.addPair(childpp, newpp);
228 child_prefetch_set_copy.remove(childpp);
229 /* Check for independence of prefetch pairs to compute new probability */
230 if(child_prefetch_set_copy.containsKey(newpp)) {
231 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
232 if(newprob < ANALYSIS_THRESHOLD_PROB) {
233 tocompare.remove(newpp);
235 tocompare.put(newpp, newprob);
236 pm.addPair(newpp, newpp);
238 child_prefetch_set_copy.remove(newpp);
241 } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) {
242 child_prefetch_set_copy.remove(childpp);
243 } else if(childpp.containsTemp(currffn.getDst())) {
244 child_prefetch_set_copy.remove(childpp);
249 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
250 * if so, calculate the new probability */
251 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
252 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
253 for(Enumeration e = currcopy.keys(); e.hasMoreElements();) {
254 PrefetchPair currpp = (PrefetchPair) e.nextElement();
255 if(currpp.equals(childpp)) {
256 pm.addPair(childpp, currpp);
257 child_prefetch_set_copy.remove(childpp);
263 /* Merge child prefetch pairs */
264 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
265 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
266 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
267 pm.addPair(childpp, childpp);
268 child_prefetch_set_copy.remove(childpp);
271 /* Merge curr prefetch pairs */
272 for (Enumeration e = currcopy.keys();e.hasMoreElements();) {
273 PrefetchPair currpp = (PrefetchPair) e.nextElement();
274 tocompare.put(currpp, currcopy.get(currpp).doubleValue());
275 currcopy.remove(currpp);
278 updatePairMap(curr, pm, 0);
279 updatePrefetchSet(curr, tocompare);
282 /** This function processes the prefetch set of a FlatElementNode
283 * It generates a new prefetch set after comparision with its children
284 * It compares the old prefetch set with this new prefetch set and enqueues the parents
285 * of the current node if change occurs and updates the global flatnode hash table
287 private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
289 Hashtable<PrefetchPair, Double> currcopy = new Hashtable<PrefetchPair, Double>();
290 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
291 FlatElementNode currfen = (FlatElementNode) curr;
292 PairMap pm = new PairMap();
295 /* Do Self analysis of the current node*/
296 TempDescriptor currfen_index = currfen.getIndex();
297 IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0);
298 TempDescriptor currfen_src = currfen.getSrc();
299 if(currfen.getDst().getType().isPtr()) {
300 PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc);
301 Double prob = new Double(1.0);
302 currcopy.put(pp, prob);
305 /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
306 PrefetchPair currpp = null;
307 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
308 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
309 if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) {
310 if (currfen.getDst().getType().isPtr()) {
311 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
312 newdesc.add((Descriptor)idesc);
313 newdesc.addAll(childpp.desc);
314 PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc);
315 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
316 tocompare.put(newpp, newprob);
317 pm.addPair(childpp, newpp);
318 child_prefetch_set_copy.remove(childpp);
319 /* Check for independence of prefetch pairs to compute new probability */
320 if(child_prefetch_set_copy.containsKey(newpp)) {
321 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
322 if(newprob < ANALYSIS_THRESHOLD_PROB) {
323 tocompare.remove(newpp);
325 tocompare.put(newpp, newprob);
326 pm.addPair(newpp, newpp);
328 child_prefetch_set_copy.remove(newpp);
331 } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) {
332 child_prefetch_set_copy.remove(childpp);
333 } else if(childpp.containsTemp(currfen.getDst())) {
334 child_prefetch_set_copy.remove(childpp);
339 /* Check if curr prefetch set and the child prefetch set have same prefetch pairs
340 * if so calculate the new probability */
341 for(Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
342 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
343 for(Enumeration e = currcopy.keys(); e.hasMoreElements();) {
344 currpp = (PrefetchPair) e.nextElement();
345 if(currpp.equals(childpp)) {
346 pm.addPair(childpp, currpp);
347 child_prefetch_set_copy.remove(childpp);
353 /* Merge child prefetch pairs */
354 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
355 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
356 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
357 pm.addPair(childpp, childpp);
358 child_prefetch_set_copy.remove(childpp);
361 /* Merge curr prefetch pairs */
362 for (Enumeration e = currcopy.keys();e.hasMoreElements();) {
363 currpp = (PrefetchPair) e.nextElement();
364 tocompare.put(currpp, currcopy.get(currpp).doubleValue());
365 currcopy.remove(currpp);
368 updatePairMap(curr, pm, 0);
369 updatePrefetchSet(curr, tocompare);
372 /** This function processes the prefetch set of a FlatSetFieldNode
373 * It generates a new prefetch set after comparision with its children
374 * It compares the old prefetch set with this new prefetch set and enqueues the parents
375 * of the current node if change occurs and then updates the global flatnode hash table
377 private void processFlatSetFieldNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
378 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
379 FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr;
380 PairMap pm = new PairMap();
382 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
383 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
384 if(childpp.base == currfsfn.getDst()) {
385 int size = childpp.desc.size();
386 if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */
387 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
388 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
389 for(int i = 0;i<(childpp.desc.size()-1); i++) {
390 newdesc.add(i,childpp.desc.get(i+1));
392 PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc);
393 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
394 tocompare.put(newpp, newprob);
395 pm.addPair(childpp, newpp);
396 child_prefetch_set_copy.remove(childpp);
397 /* Check for independence of prefetch pairs in newly generated prefetch pair
398 * to compute new probability */
399 if(child_prefetch_set_copy.containsKey(newpp)) {
400 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
401 if(newprob < ANALYSIS_THRESHOLD_PROB) {
402 tocompare.remove(newpp);
404 tocompare.put(newpp, newprob);
405 pm.addPair(newpp, newpp);
407 child_prefetch_set_copy.remove(newpp);
410 } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */
411 if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) {
412 child_prefetch_set_copy.remove(childpp);
420 /* Merge child prefetch pairs */
421 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
422 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
423 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
424 pm.addPair(childpp, childpp);
425 child_prefetch_set_copy.remove(childpp);
428 updatePairMap(curr, pm, 0);
429 updatePrefetchSet(curr, tocompare);
432 /** This function processes the prefetch set of a FlatSetElementNode
433 * It generates a new prefetch set after comparision with its children
434 * It compares the old prefetch set with this new prefetch set and enqueues the parents
435 * of the current node if change occurs and then updates the global flatnode hash table
437 private void processFlatSetElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
438 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
439 FlatSetElementNode currfsen = (FlatSetElementNode) curr;
440 PairMap pm = new PairMap();
442 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
443 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
444 if (childpp.base == currfsen.getDst()){
445 int sizedesc = childpp.desc.size();
446 if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
447 int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
448 if(sizetempdesc == 1) {
449 if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) {
450 /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */
451 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
452 for(int i = 0;i<(childpp.desc.size()-1); i++) {
453 newdesc.add(i,childpp.desc.get(i+1));
455 PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc);
456 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
457 tocompare.put(newpp, newprob);
458 pm.addPair(childpp, newpp);
459 child_prefetch_set_copy.remove(childpp);
460 /* Check for independence of prefetch pairs to compute new probability */
461 if(child_prefetch_set_copy.containsKey(newpp)) {
462 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
463 if(newprob < ANALYSIS_THRESHOLD_PROB) {
464 tocompare.remove(newpp);
466 tocompare.put(newpp, newprob);
467 pm.addPair(newpp, newpp);
469 child_prefetch_set_copy.remove(newpp);
471 } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1))
472 /* For e.g. a[i] = g with child prefetch set a[i] */
473 child_prefetch_set_copy.remove(childpp);
480 /* Merge child prefetch pairs */
481 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
482 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
483 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
484 pm.addPair(childpp, childpp);
485 child_prefetch_set_copy.remove(childpp);
488 updatePairMap(curr, pm, 0);
489 updatePrefetchSet(curr, tocompare);
492 /** This function applies rules and does analysis for a FlatOpNode
493 * And updates the global prefetch hashtable
495 private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
497 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
498 FlatOpNode currfopn = (FlatOpNode) curr;
499 PairMap pm = new PairMap();
501 if(currfopn.getOp().getOp() == Operation.ASSIGN) {
502 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
503 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
504 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
506 /* For cases like x=y with child prefetch set x[i].z,x.g*/
507 if(childpp.base == currfopn.getDest()) {
508 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
509 newdesc.addAll(childpp.desc);
510 PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc);
511 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
512 tocompare.put(newpp, newprob);
513 pm.addPair(childpp, newpp);
514 child_prefetch_set_copy.remove(childpp);
515 /* Check for independence of prefetch pairs to compute new probability */
516 if(child_prefetch_set_copy.containsKey(newpp)) {
517 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
518 if(newprob < ANALYSIS_THRESHOLD_PROB) {
519 tocompare.remove(newpp);
521 tocompare.put(newpp, newprob);
522 pm.addPair(newpp, newpp);
524 child_prefetch_set_copy.remove(newpp);
526 /* For cases like x=y with child prefetch set r[x].p, r[p+x].q where x is a tempdescriptor*/
527 } else if(copyofchildpp.containsTemp(currfopn.getDest())) {
528 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft()});
529 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
530 tocompare.put(newpp, newprob);
531 pm.addPair(childpp, newpp);
532 child_prefetch_set_copy.remove(childpp);
533 /* Check for independence of prefetch pairs to compute new probability*/
534 if(child_prefetch_set_copy.containsKey(newpp)) {
535 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
536 if(newprob < ANALYSIS_THRESHOLD_PROB) {
537 tocompare.remove(newpp);
539 tocompare.put(newpp, newprob);
540 pm.addPair(newpp, newpp);
542 child_prefetch_set_copy.remove(newpp);
549 //case i = i+z with child prefetch set a[i].x
550 } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) {
551 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
552 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
553 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
555 if(copyofchildpp.containsTemp(currfopn.getDest())) {
556 PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft(), currfopn.getRight()});
557 Double newprob = child_prefetch_set_copy.get(childpp).doubleValue();
558 tocompare.put(newpp, newprob);
559 pm.addPair(childpp, newpp);
560 child_prefetch_set_copy.remove(childpp);
561 /* Check for independence of prefetch pairs to compute new probability*/
562 if(child_prefetch_set_copy.containsKey(newpp)) {
563 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
564 if(newprob < ANALYSIS_THRESHOLD_PROB) {
565 tocompare.remove(newpp);
567 tocompare.put(newpp, newprob);
568 pm.addPair(newpp, newpp);
570 child_prefetch_set_copy.remove(newpp);
577 //FIXME Is not taken care of for cases like x = -y followed by a[x].i
580 /* Merge child prefetch pairs */
581 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
582 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
583 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
584 pm.addPair(childpp, childpp);
585 child_prefetch_set_copy.remove(childpp);
588 updatePairMap(curr, pm, 0);
589 updatePrefetchSet(curr, tocompare);
592 /** This function processes a FlatLiteralNode where cases such as
593 * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r
595 private void processFlatLiteralNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
596 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
597 FlatLiteralNode currfln = (FlatLiteralNode) curr;
598 PairMap pm = new PairMap();
600 if(currfln.getType().isIntegerType()) {
601 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
602 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
603 PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
604 if(copyofchildpp.containsTemp(currfln.getDst())) {
605 ArrayList<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
606 int sizetempdesc = copychilddesc.size();
607 for(ListIterator it = copychilddesc.listIterator();it.hasNext();) {
608 Object o = it.next();
609 if(o instanceof IndexDescriptor) {
610 ArrayList<TempDescriptor> td = (ArrayList<TempDescriptor>)((IndexDescriptor)o).tddesc;
611 int sizetddesc = td.size();
612 if(td.contains(currfln.getDst())) {
613 int index = td.indexOf(currfln.getDst());
615 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
619 ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
620 newdesc.addAll(copychilddesc);
621 PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc);
622 Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue();
623 tocompare.put(newpp, newprob);
624 pm.addPair(childpp, newpp);
625 child_prefetch_set_copy.remove(childpp);
626 /* Check for independence of prefetch pairs to compute new probability */
627 if(child_prefetch_set_copy.containsKey(newpp)) {
628 newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue())));
629 if(newprob < ANALYSIS_THRESHOLD_PROB) {
630 tocompare.remove(newpp);
632 tocompare.put(newpp, newprob);
633 pm.addPair(newpp, newpp);
635 child_prefetch_set_copy.remove(newpp);
641 /* Merge child prefetch pairs */
642 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
643 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
644 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
645 pm.addPair(childpp, childpp);
646 child_prefetch_set_copy.remove(childpp);
649 updatePairMap(curr, pm, 0);
650 updatePrefetchSet(curr, tocompare);
653 /** This function processes a FlatMethod where the method propagates
654 * the entire prefetch set of its child node */
655 private void processFlatMethod(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
656 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
657 FlatMethod currfm = (FlatMethod) curr;
658 PairMap pm = new PairMap();
660 /* Merge child prefetch pairs */
661 for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) {
662 PrefetchPair childpp = (PrefetchPair) ecld.nextElement();
663 tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue());
664 pm.addPair(childpp, childpp);
667 updatePairMap(curr, pm, 0);
668 updatePrefetchSet(curr, tocompare);
671 /** This function handles the processes the FlatNode of type FlatCondBranch
672 * It combines prefetches of both child elements and create a new hash table called
673 * branch_prefetch_set to contains the entries of both its children
675 private void processFlatCondBranch(FlatCondBranch fcb, MethodDescriptor md) {
676 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();//temporary hash table
677 PairMap truepm = new PairMap();
678 PairMap falsepm = new PairMap();
679 Hashtable<PrefetchPair, Double> truechild=prefetch_hash.get(fcb.getNext(0));
680 Hashtable<PrefetchPair, Double> falsechild=prefetch_hash.get(fcb.getNext(1));
682 HashSet<PrefetchPair> allpp=new HashSet<PrefetchPair>();
683 allpp.addAll(truechild.keySet());
684 allpp.addAll(falsechild.keySet());
686 for(Iterator<PrefetchPair> ppit=allpp.iterator();ppit.hasNext();) {
687 PrefetchPair pp=ppit.next();
688 double trueprob=0,falseprob=0;
689 if (truechild.containsKey(pp))
690 trueprob=truechild.get(pp).doubleValue();
691 if (falsechild.containsKey(pp))
692 falseprob=falsechild.get(pp).doubleValue();
694 double newprob=trueprob*fcb.getTrueProb()+falseprob*fcb.getFalseProb();
695 if (loop.isLoopingBranch(md,fcb)&&
700 if(newprob < ANALYSIS_THRESHOLD_PROB) //Skip pp that are below threshold
703 tocompare.put(pp, newprob);
704 if (truechild.containsKey(pp))
705 truepm.addPair(pp, pp);
707 if (falsechild.containsKey(pp))
708 falsepm.addPair(pp, pp);
712 updatePairMap(fcb, truepm, 0);
713 updatePairMap(fcb, falsepm, 1);
714 updatePrefetchSet(fcb, tocompare);
717 /** If FlatNode is not concerned with the prefetch set of its Child then propagate
718 * prefetches up the FlatNode*/
719 private void processDefaultCase(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
720 PairMap pm = new PairMap();
721 Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
723 /* Propagate all child nodes */
725 for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) {
726 PrefetchPair childpp = (PrefetchPair) e.nextElement();
727 TempDescriptor[] writearray=curr.writesTemps();
728 for(int i=0;i<writearray.length;i++) {
729 TempDescriptor wtd=writearray[i];
730 if(childpp.base == wtd||
731 childpp.containsTemp(wtd))
734 tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
735 pm.addPair(childpp, childpp);
738 updatePairMap(curr, pm, 0);
739 updatePrefetchSet(curr, tocompare);
742 /** This function prints the Prefetch pairs of a given flatnode */
743 private void printPrefetchPairs(FlatNode fn) {
744 if(prefetch_hash.containsKey(fn)) {
745 System.out.print("Prefetch" + "(");
746 Hashtable<PrefetchPair, Double> currhash = (Hashtable) prefetch_hash.get(fn);
747 for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) {
748 PrefetchPair pp = (PrefetchPair) pphash.nextElement();
749 System.out.print(pp.toString() + ", ");
751 System.out.println(")");
753 System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
757 private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
758 Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
759 HashSet<PrefetchPair> pset1_init = new HashSet<PrefetchPair>();
760 LinkedList<FlatNode> newtovisit = new LinkedList<FlatNode>();
761 LinkedList<FlatNode> newvisited = new LinkedList<FlatNode>();
763 newtovisit.addLast((FlatNode)fm);
764 while(!newtovisit.isEmpty()) {
765 FlatNode fn = (FlatNode) newtovisit.iterator().next();
766 newtovisit.remove(0);
767 pset1_hash.put(fn, pset1_init); //Initialize pset1_hash
768 newvisited.addLast(fn);
769 for(int i=0; i<fn.numNext(); i++) {
770 FlatNode nn = fn.getNext(i);
771 if(!newtovisit.contains(nn) && !newvisited.contains(nn)){
772 newtovisit.addLast(nn);
777 /* Delete redundant and subset prefetch pairs */
780 /* Start with a top down sorted order of nodes */
781 while(!newvisited.isEmpty()) {
782 applyPrefetchInsertRules((FlatNode) newvisited.getFirst(), newvisited, pset1_hash, newprefetchset);
783 newvisited.remove(0);
787 /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs
788 * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode
789 * then this function drops a.b.c from the prefetch set of the flatnode */
790 private void delSubsetPPairs() {
791 for (Enumeration e = prefetch_hash.keys();e.hasMoreElements();) {
792 FlatNode fn = (FlatNode) e.nextElement();
793 Hashtable ppairs = prefetch_hash.get(fn);
794 Vector<PrefetchPair> pplist = new Vector<PrefetchPair>();
795 Vector pplength = new Vector();
796 Vector ppisMod = new Vector();
797 for(Enumeration epp = ((Hashtable)(prefetch_hash.get(fn))).keys();epp.hasMoreElements();) {
798 PrefetchPair pp = (PrefetchPair) epp.nextElement();
800 int length = pp.desc.size()+ 1;
801 pplength.add(length);
804 int numpp = ((Hashtable)(prefetch_hash.get(fn))).size();
805 for (int i = 0; i < numpp; i++) {
806 for (int j = i+1; j < numpp; j++) {
808 int x = ((Integer) (pplength.get(i))).intValue();
809 if (((Integer) (pplength.get(i))).intValue() < ((Integer)( pplength.get(j))).intValue()) {
810 ret = isSubSet(pplist.get(i), pplist.get(j));
815 ret = isSubSet(pplist.get(j), pplist.get(i));
822 for (int i = 0; i < numpp; i++) {
823 if (((Integer)(ppisMod.get(i))).intValue() == 1) {
824 PrefetchPair pp = (PrefetchPair) pplist.get(i);
831 /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch
832 * pair else it returns: false */
833 private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) {
834 if (shrt.base != lng.base) {
837 for (int j = 0; j < shrt.desc.size(); j++) {
838 if(shrt.getDescAt(j) instanceof IndexDescriptor) {
839 IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j);
840 if(lng.getDescAt(j) instanceof IndexDescriptor){
841 IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j);
842 if(shrtid.equals(lngid)) {
851 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
859 /**This function compares all the prefetch pairs in a Prefetch set hashtable and
860 * returns: true if something has changed in the new Prefetch set else
863 private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
864 if(oldPSet.size() != newPSet.size()) {
867 for(Iterator it = newPSet.iterator();it.hasNext();) {
868 if(!oldPSet.contains((PrefetchPair)it.next())) {
876 /** This function creates a set called pset1 that contains prefetch pairs that have already
877 * been prefetched. While traversing the graph of a flat representation in a top down fashion,
878 * this function creates pset1 such that it contains prefetch pairs that have been prefetched at
879 * the previous nodes */
881 private void applyPrefetchInsertRules(FlatNode fn, LinkedList<FlatNode> newvisited, Hashtable<FlatNode, HashSet<PrefetchPair>> pset1_hash, Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
883 if(fn.kind() == FKind.FlatMethod) {
884 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
885 if(prefetch_hash.containsKey(fn)) {
886 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
887 for(Enumeration e = prefetchset.keys();e.hasMoreElements();) {
888 PrefetchPair pp = (PrefetchPair) e.nextElement();
889 /* Apply initial rule */
890 if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) {
894 /* Enqueue child node if Pset1 has changed */
895 if (comparePSet1(pset1_hash.get(fn), pset1)) {
896 for(int j=0; j<fn.numNext(); j++) {
897 FlatNode nn = fn.getNext(j);
898 newvisited.addLast((FlatNode)nn);
900 pset1_hash.put(fn, pset1);
902 newprefetchset.put(fn, pset1);
904 } else { /* Nodes other than Flat Method Node */
905 HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
906 HashSet<PrefetchPair> newpset = new HashSet<PrefetchPair>();
907 if(prefetch_hash.containsKey(fn)) {
908 Hashtable<PrefetchPair, Double> prefetchset = prefetch_hash.get(fn);
909 Hashtable<FlatNode, PairMap> ppairmaphash = pmap_hash.get(fn);
910 for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) {
911 PrefetchPair pp = (PrefetchPair) epset.nextElement();
912 boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB);
913 boolean mapprobIsLess=false;
914 boolean mapIsPresent=true;
915 for(int i=0;i<fn.numPrev();i++) {
916 FlatNode parentnode=fn.getPrev(i);
917 PairMap pm = (PairMap) ppairmaphash.get(parentnode);
919 if(pm!=null&&pm.getPair(pp) != null) {
920 PrefetchPair mappedpp = pm.getPair(pp);
921 if(prefetch_hash.get(parentnode).containsKey(mappedpp)) {
922 double prob = prefetch_hash.get(parentnode).get(mappedpp).doubleValue();
923 if(prob < PREFETCH_THRESHOLD_PROB)
924 mapprobIsLess = true;
927 mapprobIsLess = true;
930 if(pset1_hash.containsKey(parentnode)) {
932 HashSet pset = pset1_hash.get(parentnode);
936 if(!pset.contains((PrefetchPair) pm.getPair(pp)))
937 mapIsPresent = false;
941 throw new Error("applyPrefetchInsertRules() Parent node not present in pset1_hash: Not Possible");
948 if(pprobIsGreater && mapprobIsLess)
952 throw new Error("applyPrefetchInsertRules() fn: " +fn+ "not found");
955 HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
957 pset1.addAll(newpset);
958 /* Enqueue child node if Pset1 has changed */
959 if (comparePSet1(pset1_hash.get(fn), pset1)) {
960 for(int i=0; i<fn.numNext(); i++) {
961 FlatNode nn = fn.getNext(i);
962 newvisited.addLast((FlatNode)nn);
964 pset1_hash.put(fn, pset1);
967 /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
968 * then insert a new prefetch node here*/
970 HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
971 for(Iterator it = newpset.iterator(); it.hasNext();) {
972 PrefetchPair pp = (PrefetchPair) it.next();
973 if(!pset2.contains(pp)) {
977 newprefetchset.put(fn, s);
981 private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
982 boolean isFNPresent = false; /* Detects presence of FlatNew node */
983 /* This modifies the Flat representation graph */
984 for(Enumeration e = newprefetchset.keys();e.hasMoreElements();) {
985 FlatNode fn = (FlatNode) e.nextElement();
986 FlatPrefetchNode fpn = new FlatPrefetchNode();
987 if(newprefetchset.get(fn).size() > 0) {
988 fpn.insAllpp((HashSet)newprefetchset.get(fn));
989 if(fn.kind() == FKind.FlatMethod) {
990 FlatNode nn = fn.getNext(0);
994 /* Check if previous node of this FlatNode is a NEW node
995 * If yes, delete this flatnode and its prefetch set from hash table
996 * This eliminates prefetches for NULL ptrs*/
997 for(int i = 0; i< fn.numPrev(); i++) {
998 FlatNode nn = fn.getPrev(i);
999 if(nn.kind() == FKind.FlatNew) {
1004 while(fn.numPrev() > 0) {
1005 FlatNode nn = fn.getPrev(0);
1006 for(int j = 0; j<nn.numNext(); j++) {
1007 if(nn.getNext(j) == fn) {