Changes for dynamic prefetch enabling
[IRC.git] / Robust / src / Analysis / Prefetch / PrefetchAnalysis.java
1 package Analysis.Prefetch;
2
3 import java.util.*;
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;
9 import IR.SymbolTable;
10 import IR.State;
11 import IR.TypeUtil;
12 import IR.MethodDescriptor;
13 import IR.Flat.*;
14 import IR.*;
15 import IR.ClassDescriptor;
16
17 public class PrefetchAnalysis {
18     State state;
19     CallGraph callgraph;
20     TypeUtil typeutil;
21     LoopExit loop;
22     
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;
31
32     public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil, LocalityAnalysis locality) {
33         this.typeutil=typeutil;
34         this.state=state;
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);
40         DoPrefetch();
41     }
42     
43     
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);
56             }
57             newprefetchset = null;
58         }
59     }
60     
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);
69             tovisit.remove(fn);
70         }
71
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);
77             tovisit.remove(fn);
78         }
79     }
80     
81     /**
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 
86      */ 
87     private void doChildNodeAnalysis(MethodDescriptor md, FlatNode curr) {
88         if (curr.kind()==FKind.FlatCondBranch) {
89             processFlatCondBranch((FlatCondBranch)curr, md);
90         } else {
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();
96                 }
97
98             }
99             switch(curr.kind()) {
100             case FKind.FlatCall:
101                 processCall((FlatCall)curr,child_prefetch_set_copy);
102                 break;
103
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:
111             case FKind.FlatNop:
112             case FKind.FlatNew:
113             case FKind.FlatCastNode:
114             case FKind.FlatTagDeclaration:
115                 processDefaultCase(curr,child_prefetch_set_copy);
116                 break;
117             case FKind.FlatMethod:
118                 //TODO change it to take care of FlatMethod, Flatcalls 
119                 processFlatMethod(curr, child_prefetch_set_copy);
120                 break;
121             case FKind.FlatFieldNode:
122                 processFlatFieldNode(curr, child_prefetch_set_copy);
123                 break;
124             case FKind.FlatElementNode:
125                 processFlatElementNode(curr, child_prefetch_set_copy);
126                 break;
127             case FKind.FlatOpNode:
128                 processFlatOpNode(curr, child_prefetch_set_copy);
129                 break;
130             case FKind.FlatLiteralNode:
131                 processFlatLiteralNode(curr, child_prefetch_set_copy);
132                 break;
133             case FKind.FlatSetElementNode:
134                 processFlatSetElementNode(curr, child_prefetch_set_copy);
135                 break;
136             case FKind.FlatSetFieldNode:
137                 processFlatSetFieldNode(curr, child_prefetch_set_copy);
138                 break;
139             default:
140                 throw new Error("No such Flatnode kind");
141             }
142         }
143     }
144     
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
147      * returns: false
148      */
149     private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double> newPrefetchSet) {
150         if (oldPrefetchSet.size()!=newPrefetchSet.size())
151             return true;
152
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))
157                 return true;
158             double oldprob = oldPrefetchSet.get(pp).doubleValue();
159             
160             if((newprob - oldprob) > PROB_DIFF) {
161                 return true;
162             }
163             if (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB) {
164                 return true;
165             }
166             if (oldprob>newprob) {
167                 System.out.println("ERROR:" + pp);
168                 System.out.println(oldprob + " -> "+ newprob);
169             }
170         }
171         return false;
172     }
173
174     private void updatePairMap(FlatNode curr, PairMap pm, int index) {
175         if (index>=curr.numNext())
176             return;
177         if (!pmap_hash.containsKey(curr.getNext(index))) {
178             pmap_hash.put(curr.getNext(index), new Hashtable<FlatNode, PairMap>());
179         }
180         pmap_hash.get(curr.getNext(index)).put(curr, pm);
181     }
182
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));
188             }
189             prefetch_hash.put(curr, newset);
190         }
191     }
192
193     
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
199      * */
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();
205         
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);
213         }
214         
215         /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */
216
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);
229                     }
230                     tocompare.put(newpp, newprob); 
231                     pm.addPair(childpp, newpp);
232                 }
233                 //drop if not ptr
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);
239             } else {
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);
244                 }
245                 tocompare.put(childpp, newprob); 
246                 pm.addPair(childpp, childpp);
247             }
248         }
249
250         for(Iterator<PrefetchPair> it=tocompare.keySet().iterator();it.hasNext();) {
251             PrefetchPair pp=it.next();
252             if (tocompare.get(pp)<ANALYSIS_THRESHOLD_PROB)
253                 it.remove();
254             
255         }
256         
257         updatePairMap(curr, pm, 0);
258         updatePrefetchSet(curr, tocompare);
259     }
260     
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
265      * */
266     private void processFlatElementNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
267         
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();
272         
273         
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);
282         }
283         
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);
303                         } else {
304                             tocompare.put(newpp, newprob); 
305                             pm.addPair(newpp, newpp);
306                         }
307                         child_prefetch_set_copy.remove(newpp);
308                     }
309                 }
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);
314             } else {
315                 continue;
316             }
317         }
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);
327                     break;
328                 } 
329             }
330         }
331         
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);
338         }
339         
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);
345         }
346         
347         updatePairMap(curr, pm, 0);
348         updatePrefetchSet(curr, tocompare);
349     }
350     
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
355      * */
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();
360         
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));
370                         }
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);
382                             } else {
383                                 tocompare.put(newpp, newprob); 
384                                 pm.addPair(newpp, newpp);
385                             }
386                             child_prefetch_set_copy.remove(newpp);
387                         }
388                     }
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);
392                     }
393                 } else {
394                     continue;
395                 }
396             }
397         }
398         
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);
405         }
406         
407         updatePairMap(curr, pm, 0);
408         updatePrefetchSet(curr, tocompare);
409     }
410     
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
415      * */
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();
420         
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));
433                             }
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);
444                                 } else {
445                                     tocompare.put(newpp, newprob); 
446                                     pm.addPair(newpp, newpp);
447                                 }
448                                 child_prefetch_set_copy.remove(newpp);
449                             }
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);
453                     } else {
454                         continue;
455                     }
456                 }
457             }
458         }
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);
465         }
466         
467         updatePairMap(curr, pm, 0);
468         updatePrefetchSet(curr, tocompare);
469     }
470
471         /** This function applies rules and does analysis for a FlatOpNode 
472          *  And updates the global prefetch hashtable
473          * */
474     private void processFlatOpNode(FlatNode curr, Hashtable<PrefetchPair, Double> child_prefetch_set_copy) {
475         int index;
476         Hashtable<PrefetchPair, Double> tocompare = new Hashtable<PrefetchPair, Double>();
477         FlatOpNode currfopn = (FlatOpNode) curr;
478         PairMap pm = new PairMap();
479         
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();
484                 
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);
499                         } else {
500                             tocompare.put(newpp, newprob); 
501                             pm.addPair(newpp, newpp);
502                         }
503                         child_prefetch_set_copy.remove(newpp);
504                     }
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);
517                         } else {
518                             tocompare.put(newpp, newprob); 
519                             pm.addPair(newpp, newpp);
520                         }
521                         child_prefetch_set_copy.remove(newpp);
522                     }
523                     newpp = null;
524                 } else {
525                     continue;
526                 }
527             }
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();
533                 
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);
545                         } else {
546                             tocompare.put(newpp, newprob); 
547                             pm.addPair(newpp, newpp);
548                         }
549                         child_prefetch_set_copy.remove(newpp);
550                     }
551                 } else {
552                     continue;
553                 }
554             }
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);
560             }
561         }
562     } else {
563             //FIXME Is not taken care of for cases like x = -y followed by a[x].i
564         }
565         
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);
572         }
573         
574         updatePairMap(curr, pm, 0);
575         updatePrefetchSet(curr, tocompare);
576     }
577     
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
580      * are handled */
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();
585         
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());
600                                 td.remove(index);
601                                 ((IndexDescriptor)o).offset += (Integer)currfln.getValue();
602                             }
603                         }
604                     }
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);
617                         } else {
618                             tocompare.put(newpp, newprob); 
619                             pm.addPair(newpp, newpp);
620                         }
621                         child_prefetch_set_copy.remove(newpp);
622                     }
623                 }
624             }
625         }
626         
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);
633         }
634         
635         updatePairMap(curr, pm, 0);
636         updatePrefetchSet(curr, tocompare);
637     }
638     
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();
645         
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);
651         }
652         
653         updatePairMap(curr, pm, 0);
654         updatePrefetchSet(curr, tocompare);
655     }
656     
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
660      */
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));
667         
668         HashSet<PrefetchPair> allpp=new HashSet<PrefetchPair>();
669         allpp.addAll(truechild.keySet());
670         allpp.addAll(falsechild.keySet());
671         
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();
679
680             double newprob=trueprob*fcb.getTrueProb()+falseprob*fcb.getFalseProb();
681             if (loop.isLoopingBranch(md,fcb)&&
682                 newprob<falseprob) {
683                 newprob=falseprob;
684             }
685             
686             if(newprob < ANALYSIS_THRESHOLD_PROB) //Skip pp that are below threshold
687                 continue;
688
689             tocompare.put(pp, newprob);
690             if (truechild.containsKey(pp))
691                 truepm.addPair(pp, pp);
692
693             if (falsechild.containsKey(pp))
694                 falsepm.addPair(pp, pp);
695
696         }
697         
698         updatePairMap(fcb, truepm, 0);
699         updatePairMap(fcb, falsepm, 1);
700         updatePrefetchSet(fcb, tocompare);
701     }
702     
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>();
708         
709         /* Propagate all child nodes */
710         nexttemp:
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))
718                     continue nexttemp;
719             }
720             tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
721             pm.addPair(childpp, childpp);
722         }
723         
724         updatePairMap(curr, pm, 0);
725         updatePrefetchSet(curr, tocompare);
726     }
727
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>();
733         
734         /* Don't propagate prefetches across cache clear */
735         if (!curr.getMethod().getClassMethodName().equals("System.clearPrefetchCache")) {
736         /* Propagate all child nodes */
737         nexttemp:
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))
745                     continue nexttemp;
746             }
747             tocompare.put(childpp, child_prefetch_set_copy.get(childpp));
748             pm.addPair(childpp, childpp);
749         }
750         
751         }
752         updatePairMap(curr, pm, 0);
753         updatePrefetchSet(curr, tocompare);
754     }
755     
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() + ", ");
765             }
766             System.out.println(")");
767         } else {
768             System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty");
769         }
770     }
771
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>();  
777         
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);
788                 }
789             }
790         }
791         
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);
796         }
797         delSubsetPPairs(newprefetchset);
798     }
799     
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>();
808
809             for(Iterator<PrefetchPair> it1=ppairs.iterator();it1.hasNext();) {
810                 PrefetchPair pp1=it1.next();
811                 if (toremove.contains(pp1))
812                     continue;
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;
817
818                     if (l1<l2&&isSubSet(pp1,pp2))
819                         toremove.add(pp1);
820                     else
821                         if (l2>l1&&isSubSet(pp2,pp1))
822                             toremove.add(pp2);
823                 }
824             }
825             
826             ppairs.removeAll(toremove);
827         }
828     }
829     
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) {
834             return false;
835         }
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)) {
842                         continue;
843                     } else {
844                         return false;
845                     }
846                 } else {
847                     return false;
848                 }
849             } else  {
850                 if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
851                     return false;
852                 }
853             }
854         }
855         return true;
856     }
857
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
860      * returns: false
861      */
862     private boolean comparePSet1(HashSet<PrefetchPair> oldPSet, HashSet<PrefetchPair>newPSet) {
863         if(oldPSet.size() != newPSet.size()) {
864             return true;
865         } else {
866             for(Iterator it = newPSet.iterator();it.hasNext();) {
867                 if(!oldPSet.contains((PrefetchPair)it.next())) {
868                     return true;
869                 }
870             }
871         }
872         return false;
873     }
874     
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 */
879     
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) {
888                     pset1.add(pp);
889                 }
890             }
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);
896                 }
897                 pset1_hash.put(fn, pset1);
898             }
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;
920                         } else
921                             mapprobIsLess = true;
922                     } else {
923                         mapprobIsLess = true;
924                     }
925                     /* Build pset2 */
926                     if(pm !=null) {
927                         HashSet pset = pset1_hash.get(parentnode);
928                         if(pset.isEmpty()||!pset.contains((PrefetchPair) pm.getPair(pp)))
929                             mapIsPresent = false;
930                     } else
931                         mapIsPresent=false;
932                 }
933                 
934                 if(mapIsPresent)
935                     pset2.add(pp);
936                 
937                 if(pprobIsGreater && mapprobIsLess)
938                     newpset.add(pp);
939             }
940             
941             HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
942             pset1.addAll(pset2);
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);
949                 }
950                 pset1_hash.put(fn, pset1);
951             }
952             
953             /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty
954              * then insert a new prefetch node here*/
955
956             HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
957             s.addAll(newpset);
958             s.removeAll(pset2);
959             newprefetchset.put(fn, s); 
960         }
961     }
962
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);
973             fn.setNext(0, fpn);
974             fpn.addNext(nn);
975             fpn.siteid = prefetchsiteid++;
976           } else {
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) {
983                 isFNPresent = true;
984               }
985             }
986             if(!isFNPresent) {
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) {
991                     nn.setNext(j, fpn);
992                   }
993                 }
994               }
995               fpn.addNext(fn);
996               fpn.siteid = prefetchsiteid++;
997             }
998           } //end of else
999             } //End of if
1000         } //end of for
1001     }
1002 }