+ State state;
+ CallGraph callgraph;
+ TypeUtil typeutil;
+ LoopExit loop;
+
+ Set<FlatNode> tovisit;
+ public Hashtable<FlatNode, Hashtable<PrefetchPair, Double>> prefetch_hash; //holds all flatnodes and corresponding prefetch set
+ public Hashtable<FlatNode, Hashtable<FlatNode, PairMap>> pmap_hash; //holds all flatnodes and mappings between child prefetch pair and parent prefetch pair
+ public static final double PROB_DIFF = 0.05; //threshold for difference in probabilities during first phase of analysis
+ public static final double ANALYSIS_THRESHOLD_PROB = 0.10; //threshold for prefetches to stop propagating during first phase of analysis
+ public static final double PREFETCH_THRESHOLD_PROB = 0.30; //threshold for prefetches to stop propagating while applying prefetch rules during second phase of analysis
+ public static int prefetchsiteid = 1; //initialized to one because there is a prefetch siteid 0 for starting remote thread
+ LocalityAnalysis locality;
+
+ public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil, LocalityAnalysis locality) {
+ this.typeutil=typeutil;
+ this.state=state;
+ this.callgraph=callgraph;
+ this.locality=locality;
+ prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Double>>();
+ pmap_hash = new Hashtable<FlatNode, Hashtable<FlatNode, PairMap>>();
+ this.loop=new LoopExit(state);
+ DoPrefetch();
+ }
+
+
+ /** This function starts the prefetch analysis */
+ private void DoPrefetch() {
+ for (Iterator methodit=locality.getMethods().iterator(); methodit.hasNext(); ) {
+ MethodDescriptor md=(MethodDescriptor)methodit.next();
+ if (state.excprefetch.contains(md.getClassMethodName()))
+ continue; //Skip this method
+ Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset = new Hashtable<FlatNode, HashSet<PrefetchPair>>();
+ FlatMethod fm=state.getMethodFlat(md);
+ doFlatNodeAnalysis(fm);
+ doInsPrefetchAnalysis(fm, newprefetchset);
+ if(newprefetchset.size() > 0) {
+ addFlatPrefetchNode(newprefetchset);
+ }
+ newprefetchset = null;
+ }
+ }
+
+ /** This function calls analysis for every node in a method */
+ private void doFlatNodeAnalysis(FlatMethod fm) {
+ tovisit = fm.getNodeSet();
+ Hashtable<PrefetchPair, Double> nodehash = new Hashtable<PrefetchPair, Double>();
+ /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */
+ while(!tovisit.isEmpty()) {
+ FlatNode fn = (FlatNode)tovisit.iterator().next();
+ prefetch_hash.put(fn, nodehash);
+ tovisit.remove(fn);
+ }
+
+ /* Visit and process nodes */
+ tovisit = fm.getNodeSet();
+ while(!tovisit.isEmpty()) {
+ FlatNode fn = (FlatNode)tovisit.iterator().next();
+ tovisit.remove(fn);
+
+ doChildNodeAnalysis(fm.getMethod(),fn);
+ }
+ }
+
+ /**
+ * This function generates the prefetch sets for a given Flatnode considering the kind of node
+ * It calls severals functions based on the kind of the node and
+ * returns true: if the prefetch set has changed since last time the node was analysed
+ * returns false : otherwise
+ */
+ private void doChildNodeAnalysis(MethodDescriptor md, FlatNode curr) {
+ if (curr.kind()==FKind.FlatCondBranch) {
+ processFlatCondBranch((FlatCondBranch)curr, md);
+ } else {
+ Hashtable<PrefetchPair, Double> child_prefetch_set_copy = new Hashtable<PrefetchPair, Double>();
+ if(curr.numNext() != 0) {
+ FlatNode child_node = curr.getNext(0);
+ if(prefetch_hash.containsKey(child_node)) {
+ child_prefetch_set_copy = (Hashtable<PrefetchPair,Double>)prefetch_hash.get(child_node).clone();
+ }
+
+ }
+ switch(curr.kind()) {
+ case FKind.FlatCall:
+ processCall((FlatCall)curr,child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatBackEdge:
+ case FKind.FlatCheckNode:
+ case FKind.FlatReturnNode:
+ case FKind.FlatAtomicEnterNode:
+ case FKind.FlatAtomicExitNode:
+ case FKind.FlatFlagActionNode:
+ case FKind.FlatGlobalConvNode:
+ case FKind.FlatNop:
+ case FKind.FlatExit:
+ case FKind.FlatNew:
+ case FKind.FlatCastNode:
+ case FKind.FlatTagDeclaration:
+ case FKind.FlatInstanceOfNode:
+ processDefaultCase(curr,child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatMethod:
+ //TODO change it to take care of FlatMethod, Flatcalls
+ processFlatMethod(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatFieldNode:
+ processFlatFieldNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatElementNode:
+ processFlatElementNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatOpNode:
+ processFlatOpNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatLiteralNode:
+ processFlatLiteralNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatSetElementNode:
+ processFlatSetElementNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatSetFieldNode:
+ processFlatSetFieldNode(curr, child_prefetch_set_copy);
+ break;
+
+ case FKind.FlatOffsetNode:
+ processDefaultCase(curr,child_prefetch_set_copy);
+ break;
+
+ default:
+ throw new Error("No such Flatnode kind");
+ }
+ }
+ }
+
+ /**This function compares all the prefetch pairs in a Prefetch set hashtable and
+ * returns: true if something has changed in the new Prefetch set else
+ * returns: false
+ */
+ private boolean comparePrefetchSets(Hashtable<PrefetchPair, Double> oldPrefetchSet, Hashtable<PrefetchPair, Double> newPrefetchSet) {
+ if (oldPrefetchSet.size()!=newPrefetchSet.size())
+ return true;
+
+ for(Enumeration e = newPrefetchSet.keys(); e.hasMoreElements(); ) {
+ PrefetchPair pp = (PrefetchPair) e.nextElement();
+ double newprob = newPrefetchSet.get(pp).doubleValue();
+ if (!oldPrefetchSet.containsKey(pp))
+ return true;
+ double oldprob = oldPrefetchSet.get(pp).doubleValue();
+
+ if((newprob - oldprob) > PROB_DIFF) {
+ return true;
+ }
+ if (newprob >= PREFETCH_THRESHOLD_PROB && oldprob < PREFETCH_THRESHOLD_PROB) {
+ return true;
+ }
+ if (oldprob>newprob) {
+ System.out.println("ERROR:" + pp);
+ System.out.println(oldprob + " -> "+ newprob);
+ }
+ }
+ return false;
+ }
+
+ private void updatePairMap(FlatNode curr, PairMap pm, int index) {
+ if (index>=curr.numNext())
+ return;
+ if (!pmap_hash.containsKey(curr.getNext(index))) {
+ pmap_hash.put(curr.getNext(index), new Hashtable<FlatNode, PairMap>());
+ }
+ pmap_hash.get(curr.getNext(index)).put(curr, pm);
+ }
+
+ private void updatePrefetchSet(FlatNode curr, Hashtable<PrefetchPair, Double> newset) {
+ Hashtable<PrefetchPair, Double>oldset=prefetch_hash.get(curr);
+ if (comparePrefetchSets(oldset, newset)) {
+ for(int i=0; i<curr.numPrev(); i++) {
+ tovisit.add(curr.getPrev(i));
+ }
+ prefetch_hash.put(curr, newset);