From 37c437b109f527251a5e565b819d2530bb8f8126 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 25 Mar 2008 05:43:10 +0000 Subject: [PATCH] changes to prefetch analysis to simplify code --- .../Analysis/Prefetch/PrefetchAnalysis.java | 2464 +++++++---------- .../src/Analysis/Prefetch/PrefetchPair.java | 38 + 2 files changed, 1042 insertions(+), 1460 deletions(-) diff --git a/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java b/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java index fc9e98e6..47e297aa 100644 --- a/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java +++ b/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java @@ -24,68 +24,16 @@ public class PrefetchAnalysis { 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 PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) { - this.typeutil=typeutil; - this.state=state; - this.callgraph=callgraph; - prefetch_hash = new Hashtable>(); - pmap_hash = new Hashtable>(); - DoPrefetch(); - prefetch_hash = null; - pmap_hash = null; - } - - /** This function returns true if a tempdescriptor object is found in the array of descriptors - * for a given prefetch pair else returns false*/ - private boolean isTempDescFound(PrefetchPair pp, TempDescriptor td) { - ArrayList desc = (ArrayList) pp.getDesc(); - for(ListIterator it = desc.listIterator();it.hasNext();) { - Object o = it.next(); - if(o instanceof IndexDescriptor) { - ArrayList tdarray = (ArrayList)((IndexDescriptor)o).tddesc; - if(tdarray.contains(td)) { - return true; - } - } - } - return false; - } - - /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new - * tempdescriptors when there is a match */ - private ArrayList getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) { - ArrayList desc = (ArrayList) pp.getDesc(); - for(ListIterator it = desc.listIterator();it.hasNext();) { - Object currdesc = it.next(); - if(currdesc instanceof IndexDescriptor) { - ArrayList tdarray = (ArrayList)((IndexDescriptor)currdesc).tddesc; - if(tdarray.contains(td)) { - int index = tdarray.indexOf(td); - tdarray.set(index, newtd); - } - } - } - return desc; - } - - /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new - * tempdescriptors when there is a match for e.g FlatOpNodes if i= i+j then replace i with i+j */ - private ArrayList getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor left, TempDescriptor right) { - ArrayList desc = (ArrayList) pp.getDesc(); - for(ListIterator it = desc.listIterator();it.hasNext();) { - Object currdesc = it.next(); - if(currdesc instanceof IndexDescriptor) { - ArrayList tdarray = (ArrayList)((IndexDescriptor)currdesc).tddesc; - if(tdarray.contains(td)) { - int index = tdarray.indexOf(td); - tdarray.set(index, left); - tdarray.add(right); - } - } - } - return desc; - } - + public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) { + this.typeutil=typeutil; + this.state=state; + this.callgraph=callgraph; + prefetch_hash = new Hashtable>(); + pmap_hash = new Hashtable>(); + DoPrefetch(); + } + + /** This function starts the prefetch analysis */ private void DoPrefetch() { for(Iterator classit=state.getClassSymbolTable().getDescriptorsIterator();classit.hasNext();) { @@ -94,141 +42,124 @@ public class PrefetchAnalysis { } } - /** This function calls analysis for every method in a class */ - private void doMethodAnalysis(ClassDescriptor cn) { - for (Iterator methodit=cn.getMethods();methodit.hasNext();) { - MethodDescriptor md=(MethodDescriptor)methodit.next(); - if (state.excprefetch.contains(md.getClassMethodName())) - continue; //Skip this method - Hashtable> newprefetchset = new Hashtable>(); - FlatMethod fm=state.getMethodFlat(md); - doFlatNodeAnalysis(fm); - doInsPrefetchAnalysis(fm, newprefetchset); - if(newprefetchset.size() > 0) { - addFlatPrefetchNode(newprefetchset); - } - newprefetchset = null; + /** This function calls analysis for every method in a class */ + private void doMethodAnalysis(ClassDescriptor cn) { + for (Iterator methodit=cn.getMethods();methodit.hasNext();) { + MethodDescriptor md=(MethodDescriptor)methodit.next(); + if (state.excprefetch.contains(md.getClassMethodName())) + continue; //Skip this method + Hashtable> newprefetchset = new Hashtable>(); + 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 nodehash = new Hashtable(); - /* 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); - } - nodehash = null; - /* Visit and process nodes */ - tovisit = fm.getNodeSet(); - while(!tovisit.isEmpty()) { - FlatNode fn = (FlatNode)tovisit.iterator().next(); - doChildNodeAnalysis(fn); - tovisit.remove(fn); - } + /** This function calls analysis for every node in a method */ + private void doFlatNodeAnalysis(FlatMethod fm) { + tovisit = fm.getNodeSet(); + Hashtable nodehash = new Hashtable(); + /* 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); } - /** - * 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(FlatNode curr) { - Hashtable child_prefetch_set_copy = new Hashtable(); - Hashtable parentpmap = new Hashtable(); - FlatNode child_node = null; - if(curr.numNext() != 0) { - child_node = curr.getNext(0); - if(prefetch_hash.containsKey(child_node)) { - child_prefetch_set_copy = (Hashtable) prefetch_hash.get(child_node).clone(); - } - } - - switch(curr.kind()) { - case FKind.FlatBackEdge: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatCall: - //TODO change it to take care of FlatMethod, Flatcalls - processFlatCall(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatCheckNode: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatMethod: - //TODO change it to take care of FlatMethod, Flatcalls - processFlatMethod(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatNew: - processFlatNewNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatReturnNode: - //TODO change it to take care of FlatMethod, Flatcalls - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatFieldNode: - processFlatFieldNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatElementNode: - processFlatElementNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatCondBranch: - Hashtable branch_prefetch_set = new Hashtable(); - for (int i = 0; i < curr.numNext(); i++) { - Hashtable branchparentpmap = new Hashtable(); - child_node = curr.getNext(i); - if (prefetch_hash.containsKey(child_node)) { - child_prefetch_set_copy = (Hashtable) prefetch_hash.get(child_node).clone(); - } - processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, branchparentpmap); - } - break; - case FKind.FlatOpNode: - processFlatOpNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatLiteralNode: - processFlatLiteralNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatSetElementNode: - processFlatSetElementNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatSetFieldNode: - processFlatSetFieldNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatAtomicEnterNode: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatAtomicExitNode: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatCastNode: - processFlatCastNode(curr, child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatFlagActionNode: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatGlobalConvNode: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatNop: - processDefaultCase(curr,child_prefetch_set_copy, parentpmap); - break; - case FKind.FlatTagDeclaration: - processFlatTagDeclaration(curr, child_prefetch_set_copy, parentpmap); - break; - default: - throw new Error("No such Flatnode kind"); + /* Visit and process nodes */ + tovisit = fm.getNodeSet(); + while(!tovisit.isEmpty()) { + FlatNode fn = (FlatNode)tovisit.iterator().next(); + doChildNodeAnalysis(fn); + tovisit.remove(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(FlatNode curr) { + if (curr.kind()==FKind.FlatCondBranch) { + Hashtable child_prefetch_set_copy = new Hashtable(); + Hashtable branch_prefetch_set = new Hashtable(); + for (int i = 0; i < curr.numNext(); i++) { + FlatNode child_node = curr.getNext(i); + if (prefetch_hash.containsKey(child_node)) { + child_prefetch_set_copy = (Hashtable) prefetch_hash.get(child_node).clone(); + } + processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set); + } + } else { + Hashtable child_prefetch_set_copy = new Hashtable(); + if(curr.numNext() != 0) { + FlatNode child_node = curr.getNext(0); + if(prefetch_hash.containsKey(child_node)) { + child_prefetch_set_copy = (Hashtable) prefetch_hash.get(child_node).clone(); } + } + switch(curr.kind()) { + case FKind.FlatBackEdge: + case FKind.FlatCheckNode: + case FKind.FlatReturnNode: + case FKind.FlatAtomicEnterNode: + case FKind.FlatAtomicExitNode: + case FKind.FlatFlagActionNode: + case FKind.FlatGlobalConvNode: + case FKind.FlatNop: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatCall: + //TODO change it to take care of FlatMethod, Flatcalls + processFlatCall(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.FlatNew: + processFlatNewNode(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.FlatCastNode: + processFlatCastNode(curr, child_prefetch_set_copy); + break; + case FKind.FlatTagDeclaration: + processFlatTagDeclaration(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 - */ + } + + /**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 oldPrefetchSet, Hashtable newPrefetchSet) { if(oldPrefetchSet.size() != newPrefetchSet.size()) { return true; @@ -245,1347 +176,960 @@ public class PrefetchAnalysis { return false; } - /** This function processes the prefetch set of FlatFieldNode - * It generates a new prefetch set after comparision with its children - * Then compares it with its old prefetch set - * If old prefetch set is not same as new prefetch set then enqueue the parents - * of the current FlatFieldNode - * */ - private void processFlatFieldNode(FlatNode curr, Hashtable child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable currcopy = new Hashtable(); - Hashtable tocompare = new Hashtable(); - FlatFieldNode currffn = (FlatFieldNode) curr; - PairMap pm = new PairMap(); - - /* Do Self analysis of the current node*/ - FieldDescriptor currffn_field = currffn.getField(); - TempDescriptor currffn_src = currffn.getSrc(); - if (currffn_field.getType().isPtr()) { - PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field); - Double prob = new Double(1.0); - currcopy.put(pp, prob); - } - - /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_prefetch_set_copy.keys(); - PrefetchPair currpp = null; - PrefetchPair childpp = null; - while (ecld.hasMoreElements()) { - childpp = (PrefetchPair) ecld.nextElement(); - if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) { - if (currffn.getField().getType().isPtr()) { - ArrayList newdesc = new ArrayList(); - newdesc.add(currffn.getField()); - newdesc.addAll(childpp.desc); - PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } - } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) { - child_prefetch_set_copy.remove(childpp); - } else if(isTempDescFound(childpp, currffn.getDst())) { - child_prefetch_set_copy.remove(childpp); - } else { - continue; - } - } - /* Check if curr prefetch set and the child prefetch set have same prefetch pairs - * if so, calculate the new probability */ - ecld = child_prefetch_set_copy.keys(); - Enumeration e = null; - while(ecld.hasMoreElements()) { - childpp = (PrefetchPair) ecld.nextElement(); - for(e = currcopy.keys(); e.hasMoreElements();) { - currpp = (PrefetchPair) e.nextElement(); - if(currpp.equals(childpp)) { - pm.addPair(childpp, currpp); - child_prefetch_set_copy.remove(childpp); - break; - } - } - } - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Merge curr prefetch pairs */ - e = currcopy.keys(); - while(e.hasMoreElements()) { - currpp = (PrefetchPair) e.nextElement(); - tocompare.put(currpp, currcopy.get(currpp).doubleValue()); - currcopy.remove(currpp); - } + 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()); + } + pmap_hash.get(curr.getNext(index)).put(curr, pm); + } - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } + private void updatePrefetchSet(FlatNode curr, Hashtable newset) { + Hashtableoldset=prefetch_hash.get(curr); + if (comparePrefetchSets(oldset, newset)) { + for(int i=0;i pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + + /** This function processes the prefetch set of FlatFieldNode + * It generates a new prefetch set after comparision with its children + * Then compares it with its old prefetch set + * If old prefetch set is not same as new prefetch set then enqueue the parents + * of the current FlatFieldNode + * */ + private void processFlatFieldNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable currcopy = new Hashtable(); + Hashtable tocompare = new Hashtable(); + FlatFieldNode currffn = (FlatFieldNode) curr; + PairMap pm = new PairMap(); + + /* Do Self analysis of the current node*/ + FieldDescriptor currffn_field = currffn.getField(); + TempDescriptor currffn_src = currffn.getSrc(); + if (currffn_field.getType().isPtr()) { + PrefetchPair pp = new PrefetchPair(currffn_src, (Descriptor) currffn_field); + Double prob = new Double(1.0); + currcopy.put(pp, prob); + } + + /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ + + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if (childpp.base == currffn.getDst() && (childpp.getDesc()!= null)) { + if (currffn.getField().getType().isPtr()) { + ArrayList newdesc = new ArrayList(); + newdesc.add(currffn.getField()); + newdesc.addAll(childpp.desc); + PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - - boolean pSetHasChanged = false; - Hashtable currcopy = new Hashtable(); - Hashtable tocompare = new Hashtable(); - FlatElementNode currfen = (FlatElementNode) curr; - PairMap pm = new PairMap(); - - - /* Do Self analysis of the current node*/ - TempDescriptor currfen_index = currfen.getIndex(); - IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0); - TempDescriptor currfen_src = currfen.getSrc(); - if(currfen.getDst().getType().isPtr()) { - PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc); - Double prob = new Double(1.0); - currcopy.put(pp, prob); - } - - /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_prefetch_set_copy.keys(); - PrefetchPair currpp = null; - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) { - if (currfen.getDst().getType().isPtr()) { - ArrayList newdesc = new ArrayList(); - newdesc.add((Descriptor)idesc); - newdesc.addAll(childpp.desc); - PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } - } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) { - child_prefetch_set_copy.remove(childpp); - } else if(isTempDescFound(childpp, currfen.getDst())) { - child_prefetch_set_copy.remove(childpp); - } else { - continue; - } - } - /* Check if curr prefetch set and the child prefetch set have same prefetch pairs - * if so calculate the new probability */ - ecld = child_prefetch_set_copy.keys(); - Enumeration e = null; - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - for(e = currcopy.keys(); e.hasMoreElements();) { - currpp = (PrefetchPair) e.nextElement(); - if(currpp.equals(childpp)) { - pm.addPair(childpp, currpp); - child_prefetch_set_copy.remove(childpp); - break; - } - } - } - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Merge curr prefetch pairs */ - e = currcopy.keys(); - while(e.hasMoreElements()) { - currpp = (PrefetchPair) e.nextElement(); - tocompare.put(currpp, currcopy.get(currpp).doubleValue()); - currcopy.remove(currpp); - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + child_prefetch_set_copy.remove(childpp); + } + + /* Merge curr prefetch pairs */ + for (Enumeration e = currcopy.keys();e.hasMoreElements();) { + PrefetchPair currpp = (PrefetchPair) e.nextElement(); + tocompare.put(currpp, currcopy.get(currpp).doubleValue()); + currcopy.remove(currpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function processes the prefetch set of a FlatElementNode + * It generates a new prefetch set after comparision with its children + * It compares the old prefetch set with this new prefetch set and enqueues the parents + * of the current node if change occurs and updates the global flatnode hash table + * */ + private void processFlatElementNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + + Hashtable currcopy = new Hashtable(); + Hashtable tocompare = new Hashtable(); + FlatElementNode currfen = (FlatElementNode) curr; + PairMap pm = new PairMap(); + + + /* Do Self analysis of the current node*/ + TempDescriptor currfen_index = currfen.getIndex(); + IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0); + TempDescriptor currfen_src = currfen.getSrc(); + if(currfen.getDst().getType().isPtr()) { + PrefetchPair pp = new PrefetchPair(currfen_src, (Descriptor) idesc); + Double prob = new Double(1.0); + currcopy.put(pp, prob); + } + + /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ + PrefetchPair currpp = null; + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if (childpp.base == currfen.getDst() && (childpp.getDesc()!= null)) { + if (currfen.getDst().getType().isPtr()) { + ArrayList newdesc = new ArrayList(); + newdesc.add((Descriptor)idesc); + newdesc.addAll(childpp.desc); + PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr; - PairMap pm = new PairMap(); - - Enumeration ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if(childpp.base == currfsfn.getDst()) { - int size = childpp.desc.size(); - if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */ - if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) { - ArrayList newdesc = new ArrayList(); - for(int i = 0;i<(childpp.desc.size()-1); i++) { - newdesc.add(i,childpp.desc.get(i+1)); - } - PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs in newly generated prefetch pair - * to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } - } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */ - if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) { - child_prefetch_set_copy.remove(childpp); - } - } else { - continue; - } + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + child_prefetch_set_copy.remove(childpp); + } + + /* Merge curr prefetch pairs */ + for (Enumeration e = currcopy.keys();e.hasMoreElements();) { + currpp = (PrefetchPair) e.nextElement(); + tocompare.put(currpp, currcopy.get(currpp).doubleValue()); + currcopy.remove(currpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function processes the prefetch set of a FlatSetFieldNode + * It generates a new prefetch set after comparision with its children + * It compares the old prefetch set with this new prefetch set and enqueues the parents + * of the current node if change occurs and then updates the global flatnode hash table + * */ + private void processFlatSetFieldNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr; + PairMap pm = new PairMap(); + + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if(childpp.base == currfsfn.getDst()) { + int size = childpp.desc.size(); + if(size >=2) { /*e.g. x.f = g (with child prefetches x.f.g, x.f[0].j) */ + if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) { + ArrayList newdesc = new ArrayList(); + for(int i = 0;i<(childpp.desc.size()-1); i++) { + newdesc.add(i,childpp.desc.get(i+1)); } - } - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); + PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); child_prefetch_set_copy.remove(childpp); - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); + /* Check for independence of prefetch pairs in newly generated prefetch pair + * to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); + } else { + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); + } + child_prefetch_set_copy.remove(newpp); } + } + } else if(size==1) { /* e.g x.f = g (with child prefetch x.f) */ + if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) { + child_prefetch_set_copy.remove(childpp); + } } else { - pmap_hash.put(curr.getNext(0), parentpmap); + continue; } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatSetElementNode currfsen = (FlatSetElementNode) curr; - PairMap pm = new PairMap(); - - Enumeration ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if (childpp.base == currfsen.getDst()){ - int sizedesc = childpp.desc.size(); - if((childpp.getDescAt(0) instanceof IndexDescriptor)) { - int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size(); - if(sizetempdesc == 1) { - if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) { - /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */ - ArrayList newdesc = new ArrayList(); - for(int i = 0;i<(childpp.desc.size()-1); i++) { - newdesc.add(i,childpp.desc.get(i+1)); - } - PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1)) - /* For e.g. a[i] = g with child prefetch set a[i] */ - child_prefetch_set_copy.remove(childpp); - } else { - continue; - } + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + child_prefetch_set_copy.remove(childpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function processes the prefetch set of a FlatSetElementNode + * It generates a new prefetch set after comparision with its children + * It compares the old prefetch set with this new prefetch set and enqueues the parents + * of the current node if change occurs and then updates the global flatnode hash table + * */ + private void processFlatSetElementNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatSetElementNode currfsen = (FlatSetElementNode) curr; + PairMap pm = new PairMap(); + + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if (childpp.base == currfsen.getDst()){ + int sizedesc = childpp.desc.size(); + if((childpp.getDescAt(0) instanceof IndexDescriptor)) { + int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size(); + if(sizetempdesc == 1) { + if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) { + /* For e.g. a[i] = g with child prefetch set a[i].r or a[i].r.f */ + ArrayList newdesc = new ArrayList(); + for(int i = 0;i<(childpp.desc.size()-1); i++) { + newdesc.add(i,childpp.desc.get(i+1)); + } + PrefetchPair newpp = new PrefetchPair(currfsen.getSrc(), newdesc); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); + } else { + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); } - } - } - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); + child_prefetch_set_copy.remove(newpp); + } + } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1)) + /* For e.g. a[i] = g with child prefetch set a[i] */ + child_prefetch_set_copy.remove(childpp); + } else { + continue; + } } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - int index; - Hashtable tocompare = new Hashtable(); - FlatOpNode currfopn = (FlatOpNode) curr; - Enumeration ecld = null; - PairMap pm = new PairMap(); - - if(currfopn.getOp().getOp() == Operation.ASSIGN) { - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); - - /* For cases like x=y with child prefetch set x[i].z,x.g*/ - if(childpp.base == currfopn.getDest()) { - ArrayList newdesc = new ArrayList(); - newdesc.addAll(childpp.desc); - PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - /* For cases like x=y with child prefetch set r[x].p, r[p+x].q where x is a tempdescriptor*/ - } else if(isTempDescFound(copyofchildpp, currfopn.getDest())) { - ArrayList newdesc = new ArrayList(); - newdesc.addAll((ArrayList)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft())); - PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability*/ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - newdesc = null; - newpp = null; - } else { - continue; - } - } - //case i = i+z with child prefetch set a[i].x - } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) { - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); - - if(isTempDescFound(copyofchildpp, currfopn.getDest())) { - ArrayList newdesc = new ArrayList(); - newdesc.addAll((ArrayList)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight())); - PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability*/ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } else { - continue; - } - } - } else { - //FIXME Is not taken care of for cases like x = -y followed by a[x].i - } - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + private void processFlatOpNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + int index; + Hashtable tocompare = new Hashtable(); + FlatOpNode currfopn = (FlatOpNode) curr; + PairMap pm = new PairMap(); + + if(currfopn.getOp().getOp() == Operation.ASSIGN) { + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); + + /* For cases like x=y with child prefetch set x[i].z,x.g*/ + if(childpp.base == currfopn.getDest()) { + ArrayList newdesc = new ArrayList(); + newdesc.addAll(childpp.desc); + PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatLiteralNode currfln = (FlatLiteralNode) curr; - Enumeration ecld = null; - PairMap pm = new PairMap(); - - if(currfln.getType().isIntegerType()) { - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); - if(isTempDescFound(copyofchildpp,currfln.getDst())) { - ArrayList copychilddesc = (ArrayList) copyofchildpp.getDesc(); - int sizetempdesc = copychilddesc.size(); - for(ListIterator it = copychilddesc.listIterator();it.hasNext();) { - Object o = it.next(); - if(o instanceof IndexDescriptor) { - ArrayList td = (ArrayList)((IndexDescriptor)o).tddesc; - int sizetddesc = td.size(); - if(td.contains(currfln.getDst())) { - int index = td.indexOf(currfln.getDst()); - td.remove(index); - ((IndexDescriptor)o).offset += (Integer)currfln.getValue(); - } - } - } - ArrayList newdesc = new ArrayList(); - newdesc.addAll(copychilddesc); - PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue(); - tocompare.put(newpp, newprob); - pm.addPair(childpp, newpp); - child_prefetch_set_copy.remove(childpp); - /* Check for independence of prefetch pairs to compute new probability */ - if(child_prefetch_set_copy.containsKey(newpp)) { - newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); - pm.addPair(newpp, newpp); - } - child_prefetch_set_copy.remove(newpp); - } - } + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); } - } - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + child_prefetch_set_copy.remove(newpp); + } + /* For cases like x=y with child prefetch set r[x].p, r[p+x].q where x is a tempdescriptor*/ + } else if(copyofchildpp.containsTemp(currfopn.getDest())) { + PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft()}); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability*/ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); } + child_prefetch_set_copy.remove(newpp); + } + newpp = null; } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatMethod currfm = (FlatMethod) curr; - Enumeration ecld = null; - PairMap pm = new PairMap(); - - /* Merge child prefetch pairs */ - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); + continue; } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + } + //case i = i+z with child prefetch set a[i].x + } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) { + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); + + if(copyofchildpp.containsTemp(currfopn.getDest())) { + PrefetchPair newpp=copyofchildpp.replaceTemp(currfopn.getDest(), new TempDescriptor[] {currfopn.getLeft(), currfopn.getRight()}); + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability*/ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); } + child_prefetch_set_copy.remove(newpp); + } } else { - pmap_hash.put(curr.getNext(0), parentpmap); + continue; } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - /* Overwrite the new prefetch set to the global hash table */ - prefetch_hash.put(curr,tocompare); - } + } + } else { + //FIXME Is not taken care of for cases like x = -y followed by a[x].i } - - /** This Function processes the FlatCalls - * It currently drops the propagation of those prefetchpairs whose base is - * same as the destination of the FlatCall - */ - private void processFlatCall(FlatNode curr, Hashtable child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatCall currfcn = (FlatCall) curr; - PairMap pm = new PairMap(); - Enumeration ecld = null; - - ecld = child_prefetch_set_copy.keys(); - while(ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); - if(currfcn.getReturnTemp() != childpp.base) { - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } else { - child_prefetch_set_copy.remove(childpp); + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + child_prefetch_set_copy.remove(childpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function processes a FlatLiteralNode where cases such as + * for e.g. i = 0 with child prefetch sets a[i].r, a[j+i].r or a[j].b[i].r + * are handled */ + private void processFlatLiteralNode(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatLiteralNode currfln = (FlatLiteralNode) curr; + PairMap pm = new PairMap(); + + if(currfln.getType().isIntegerType()) { + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); + if(copyofchildpp.containsTemp(currfln.getDst())) { + ArrayList copychilddesc = (ArrayList) copyofchildpp.getDesc(); + int sizetempdesc = copychilddesc.size(); + for(ListIterator it = copychilddesc.listIterator();it.hasNext();) { + Object o = it.next(); + if(o instanceof IndexDescriptor) { + ArrayList td = (ArrayList)((IndexDescriptor)o).tddesc; + int sizetddesc = td.size(); + if(td.contains(currfln.getDst())) { + int index = td.indexOf(currfln.getDst()); + td.remove(index); + ((IndexDescriptor)o).offset += (Integer)currfln.getValue(); + } } - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); + } + ArrayList newdesc = new ArrayList(); + newdesc.addAll(copychilddesc); + PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); + Double newprob = (child_prefetch_set_copy.get(childpp)).doubleValue(); + tocompare.put(newpp, newprob); + pm.addPair(childpp, newpp); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).doubleValue()) * (1.0 - tocompare.get(newpp).doubleValue()))); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + tocompare.remove(newpp); } else { - pmap_hash.put(curr.getNext(0), parentpmap); + tocompare.put(newpp, newprob); + pm.addPair(newpp, newpp); } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); + child_prefetch_set_copy.remove(newpp); + } } - - /* Compare with the orginal prefetch pairs */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, int index, - Hashtable branch_prefetch_set, Hashtable parentpmap) { - Hashtable tocompare = new Hashtable();//temporary hash table - FlatCondBranch currfcb = (FlatCondBranch) curr; - PairMap pm = new PairMap(); - Enumeration ecld = null; - - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - /* True Edge */ - if(index == 0) { - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getTrueProb(); - tocompare.put(childpp, newprob); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } else if(index == 1) { /* False Edge */ - Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getFalseProb(); - tocompare.put(childpp, newprob); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } else { - throw new Error("processFlatCondBranch() has only two child edges"); - } - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(index)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(index), pairmapping); - } else { - pmap_hash.put(curr.getNext(index), parentpmap); - } + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + child_prefetch_set_copy.remove(childpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function processes a FlatMethod where the method propagates + * the entire prefetch set of its child node */ + private void processFlatMethod(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatMethod currfm = (FlatMethod) curr; + PairMap pm = new PairMap(); + + /* Merge child prefetch pairs */ + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This Function processes the FlatCalls + * It currently drops the propagation of those prefetchpairs whose base is + * same as the destination of the FlatCall + */ + private void processFlatCall(FlatNode curr, Hashtable child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatCall currfcn = (FlatCall) curr; + PairMap pm = new PairMap(); + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); + if(currfcn.getReturnTemp() != childpp.base) { + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + } + } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function handles the processes the FlatNode of type FlatCondBranch + * It combines prefetches of both child elements and create a new hash table called + * branch_prefetch_set to contains the entries of both its children + */ + private void processFlatCondBranch(FlatNode curr, Hashtable child_prefetch_set_copy, int index, Hashtable branch_prefetch_set) { + Hashtable tocompare = new Hashtable();//temporary hash table + FlatCondBranch currfcb = (FlatCondBranch) curr; + PairMap pm = new PairMap(); + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + /* True Edge */ + if(index == 0) { + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getTrueProb(); + tocompare.put(childpp, newprob); + pm.addPair(childpp, childpp); + } else if(index == 1) { /* False Edge */ + Double newprob = child_prefetch_set_copy.get(childpp).doubleValue() * currfcb.getFalseProb(); + tocompare.put(childpp, newprob); + pm.addPair(childpp, childpp); + } else { + throw new Error("processFlatCondBranch() has only two child edges"); + } + } + + updatePairMap(curr, pm, index); + + /* Update branch_prefetch_set (global hash table) to combine all prefetch pairs from childnodes of the + * cond branch that is currently stored in the tocompare hash table */ + if(!tocompare.isEmpty()) { + if(index == 0) { /* True Edge */ + branch_prefetch_set.putAll(tocompare); + }else if(index == 1) { /* False Edge */ + if(branch_prefetch_set.isEmpty()) { + branch_prefetch_set.putAll(tocompare); } else { - pmap_hash.put(curr.getNext(index), parentpmap); - } - - /* Update branch_prefetch_set (global hash table) to combine all prefetch pairs from childnodes of the - * cond branch that is currently stored in the tocompare hash table */ - if(!tocompare.isEmpty()) { - if(index == 0) { /* True Edge */ - branch_prefetch_set.putAll(tocompare); - }else if(index == 1) { /* False Edge */ - if(branch_prefetch_set.isEmpty()) { - branch_prefetch_set.putAll(tocompare); - } else { - Enumeration e = tocompare.keys(); - while(e.hasMoreElements()) { - PrefetchPair pp = (PrefetchPair) e.nextElement(); - if(branch_prefetch_set.containsKey(pp)) { - Double newprob = (branch_prefetch_set.get(pp).doubleValue() + tocompare.get(pp).doubleValue()); - if(newprob < ANALYSIS_THRESHOLD_PROB) { - branch_prefetch_set.remove(pp); - } else { - branch_prefetch_set.put(pp, newprob); - } - } else { - branch_prefetch_set.put(pp,tocompare.get(pp).doubleValue()); - } - tocompare.remove(pp); - } - } + for (Enumeration e = tocompare.keys();e.hasMoreElements();) { + PrefetchPair pp = (PrefetchPair) e.nextElement(); + if(branch_prefetch_set.containsKey(pp)) { + Double newprob = (branch_prefetch_set.get(pp).doubleValue() + tocompare.get(pp).doubleValue()); + if(newprob < ANALYSIS_THRESHOLD_PROB) { + branch_prefetch_set.remove(pp); + } else { + branch_prefetch_set.put(pp, newprob); + } } else { - throw new Error("processFlatCondBranch() has only two child edges"); - } - } - - /* Compare prefetch sets and enqueue parent nodes: Only possible after combining prefetch pairs of both child nodes - * into branch_prefetch_set hashtable*/ - if(index == 1) { - boolean pSetHasChanged = false; - /* Delete the prefetch pairs below threshold */ - for(Iterator it = branch_prefetch_set.keySet().iterator(); it.hasNext();) { - PrefetchPair pp = (PrefetchPair) it.next(); - if(branch_prefetch_set.get(pp).doubleValue() < ANALYSIS_THRESHOLD_PROB) { - /* Delete pair mappings of PSChild-> PSParent for these prefetch pairs */ - for(int i = 0; i pairmap = pmap_hash.get(fn); - PairMap childpm = pairmap.get(curr); - if(childpm!=null && childpm.contains(pp)) { - childpm.removePair(pp); - } - } - branch_prefetch_set.remove(pp); - it = branch_prefetch_set.keySet().iterator(); - } + branch_prefetch_set.put(pp,tocompare.get(pp).doubleValue()); } - - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set); - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - PairMap pm = new PairMap(); - Enumeration e = null; - Hashtable tocompare = new Hashtable(); - - /* Propagate all child nodes */ - for(e = child_prefetch_set_copy.keys(); e.hasMoreElements();) { - PrefetchPair childpp = (PrefetchPair) e.nextElement(); - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - - /* Check case for nodes with no children (e.g return null) and create prefetch mappings for child nodes*/ - if(curr.numNext() != 0) { - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); + + /* Compare prefetch sets and enqueue parent nodes: Only possible after combining prefetch pairs of both child nodes + * into branch_prefetch_set hashtable*/ + if(index == 1) { + /* Delete the prefetch pairs below threshold */ + for(Iterator it = branch_prefetch_set.keySet().iterator(); it.hasNext();) { + PrefetchPair pp = (PrefetchPair) it.next(); + if(branch_prefetch_set.get(pp).doubleValue() < ANALYSIS_THRESHOLD_PROB) { + /* Delete pair mappings of PSChild-> PSParent for these prefetch pairs */ + for(int i = 0; i pairmap = pmap_hash.get(fn); + PairMap childpm = pairmap.get(curr); + if(childpm!=null && childpm.contains(pp)) { + childpm.removePair(pp); } + } + branch_prefetch_set.remove(pp); + it = branch_prefetch_set.keySet().iterator(); } - - /* Compare with old Prefetch sets */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - if(pSetHasChanged){ - for(int i=0; i child_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatNew currfnn = (FlatNew) curr; - Double newprob = new Double(0.0); - PairMap pm = new PairMap(); - Enumeration ecld = null; - - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if(childpp.base == currfnn.getDst()){ - child_prefetch_set_copy.remove(childpp); - } else if(isTempDescFound(childpp, currfnn.getDst())) { - child_prefetch_set_copy.remove(childpp); - } else { - tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the old prefetch set */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy) { + PairMap pm = new PairMap(); + Hashtable tocompare = new Hashtable(); + + /* Propagate all child nodes */ + for(Enumeration e = child_prefetch_set_copy.keys(); e.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) e.nextElement(); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); } - - /** This functions processes for FlatCastNode - * for e.g x = (cast type) y followed by childnode with prefetch set x.f - * then drop the prefetches beyond this FlatCastNode */ - private void processFlatCastNode(FlatNode curr, Hashtablechild_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatCastNode currfcn = (FlatCastNode) curr; - Double newprob = new Double(0.0); - PairMap pm = new PairMap(); - Enumeration ecld = null; - - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if(childpp.base == currfcn.getDst()){ - child_prefetch_set_copy.remove(childpp); - } else if(isTempDescFound(childpp, currfcn.getDst())) { - child_prefetch_set_copy.remove(childpp); - } else { - tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the old prefetch set */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; i child_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatNew currfnn = (FlatNew) curr; + Double newprob = new Double(0.0); + PairMap pm = new PairMap(); + + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if(childpp.base != currfnn.getDst()&& + !childpp.containsTemp(currfnn.getDst())) { + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + pm.addPair(childpp, childpp); + } } - - /** This functions processes for FlatTagDeclaration - * for e.g x = (cast type) y followed by childnode with prefetch set x.f - * then drop the prefetches beyond this FlatTagDeclaration */ - private void processFlatTagDeclaration(FlatNode curr, Hashtablechild_prefetch_set_copy, - Hashtable parentpmap) { - boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); - FlatTagDeclaration currftd = (FlatTagDeclaration) curr; - Double newprob = new Double(0.0); - PairMap pm = new PairMap(); - Enumeration ecld = null; - - ecld = child_prefetch_set_copy.keys(); - while (ecld.hasMoreElements()) { - PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); - if(childpp.base == currftd.getDst()){ - child_prefetch_set_copy.remove(childpp); - } else if(isTempDescFound(childpp, currftd.getDst())) { - child_prefetch_set_copy.remove(childpp); - } else { - tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); - pm.addPair(childpp, childpp); - child_prefetch_set_copy.remove(childpp); - } - } - - /* Create prefetch mappings for child nodes */ - if(!pm.isEmpty()) { - parentpmap.put(curr, pm); - } - if(!pmap_hash.isEmpty()) { - Hashtable pairmapping = pmap_hash.get(curr.getNext(0)); - if(pairmapping != null) { - pairmapping.put(curr, pm); - pmap_hash.put(curr.getNext(0), pairmapping); - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - } else { - pmap_hash.put(curr.getNext(0), parentpmap); - } - - /* Compare with the old prefetch set */ - pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); - - /* Enqueue parent nodes */ - if(pSetHasChanged) { - for(int i=0; ichild_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatCastNode currfcn = (FlatCastNode) curr; + Double newprob = new Double(0.0); + PairMap pm = new PairMap(); + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if(childpp.base != currfcn.getDst()&& + !childpp.containsTemp(currfcn.getDst())) { + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + pm.addPair(childpp, childpp); + } } - - /** This function prints the Prefetch pairs of a given flatnode */ - private void printPrefetchPairs(FlatNode fn) { - if(prefetch_hash.containsKey(fn)) { - System.out.print("Prefetch" + "("); - Hashtable currhash = (Hashtable) prefetch_hash.get(fn); - for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) { - PrefetchPair pp = (PrefetchPair) pphash.nextElement(); - System.out.print(pp.toString() + ", "); - } - System.out.println(")"); - } else { - System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty"); - } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This functions processes for FlatTagDeclaration + * for e.g x = (cast type) y followed by childnode with prefetch set x.f + * then drop the prefetches beyond this FlatTagDeclaration */ + private void processFlatTagDeclaration(FlatNode curr, Hashtablechild_prefetch_set_copy) { + Hashtable tocompare = new Hashtable(); + FlatTagDeclaration currftd = (FlatTagDeclaration) curr; + Double newprob = new Double(0.0); + PairMap pm = new PairMap(); + + for (Enumeration ecld = child_prefetch_set_copy.keys();ecld.hasMoreElements();) { + PrefetchPair childpp = (PrefetchPair) ecld.nextElement(); + if(childpp.base != currftd.getDst()&& + !childpp.containsTemp(currftd.getDst())) { + tocompare.put(childpp, child_prefetch_set_copy.get(childpp).doubleValue()); + pm.addPair(childpp, childpp); + } } + + updatePairMap(curr, pm, 0); + updatePrefetchSet(curr, tocompare); + } + + /** This function prints the Prefetch pairs of a given flatnode */ + private void printPrefetchPairs(FlatNode fn) { + if(prefetch_hash.containsKey(fn)) { + System.out.print("Prefetch" + "("); + Hashtable currhash = (Hashtable) prefetch_hash.get(fn); + for(Enumeration pphash= currhash.keys(); pphash.hasMoreElements();) { + PrefetchPair pp = (PrefetchPair) pphash.nextElement(); + System.out.print(pp.toString() + ", "); + } + System.out.println(")"); + } else { + System.out.println("Flatnode is currently not present in the global hash: Prefetch Set is Empty"); + } + } - private void doInsPrefetchAnalysis(FlatMethod fm, Hashtable> newprefetchset) { - Hashtable> pset1_hash = new Hashtable>(); - HashSet pset1_init = new HashSet(); - LinkedList newtovisit = new LinkedList(); - LinkedList newvisited = new LinkedList(); - - newtovisit.addLast((FlatNode)fm); - while(!newtovisit.isEmpty()) { - FlatNode fn = (FlatNode) newtovisit.iterator().next(); - newtovisit.remove(0); - pset1_hash.put(fn, pset1_init); //Initialize pset1_hash - newvisited.addLast(fn); - for(int i=0; i> newprefetchset) { + Hashtable> pset1_hash = new Hashtable>(); + HashSet pset1_init = new HashSet(); + LinkedList newtovisit = new LinkedList(); + LinkedList newvisited = new LinkedList(); + + newtovisit.addLast((FlatNode)fm); + while(!newtovisit.isEmpty()) { + FlatNode fn = (FlatNode) newtovisit.iterator().next(); + newtovisit.remove(0); + pset1_hash.put(fn, pset1_init); //Initialize pset1_hash + newvisited.addLast(fn); + for(int i=0; i pplist = new Vector(); - Vector pplength = new Vector(); - Vector ppisMod = new Vector(); - while(epp.hasMoreElements()) { - PrefetchPair pp = (PrefetchPair) epp.nextElement(); - pplist.add(pp); - int length = pp.desc.size()+ 1; - pplength.add(length); - ppisMod.add(0); - } - int numpp = ((Hashtable)(prefetch_hash.get(fn))).size(); - for (int i = 0; i < numpp; i++) { - for (int j = i+1; j < numpp; j++) { - boolean ret; - int x = ((Integer) (pplength.get(i))).intValue(); - if (((Integer) (pplength.get(i))).intValue() < ((Integer)( pplength.get(j))).intValue()) { - ret = isSubSet(pplist.get(i), pplist.get(j)); - if (ret) { - ppisMod.set(i, 1); - } - } else { - ret = isSubSet(pplist.get(j), pplist.get(i)); - if (ret) { - ppisMod.set(j, 1); - } - } - } + + /* Delete redundant and subset prefetch pairs */ + delSubsetPPairs(); + + /* Start with a top down sorted order of nodes */ + while(!newvisited.isEmpty()) { + applyPrefetchInsertRules((FlatNode) newvisited.getFirst(), newvisited, pset1_hash, newprefetchset); + newvisited.remove(0); + } + } + + /** This function deletes the smaller prefetch pair subset from a list of prefetch pairs + * for e.g. if there are 2 prefetch pairs a.b.c.d and a.b.c for a given flatnode + * then this function drops a.b.c from the prefetch set of the flatnode */ + private void delSubsetPPairs() { + for (Enumeration e = prefetch_hash.keys();e.hasMoreElements();) { + FlatNode fn = (FlatNode) e.nextElement(); + Hashtable ppairs = prefetch_hash.get(fn); + Vector pplist = new Vector(); + Vector pplength = new Vector(); + Vector ppisMod = new Vector(); + for(Enumeration epp = ((Hashtable)(prefetch_hash.get(fn))).keys();epp.hasMoreElements();) { + PrefetchPair pp = (PrefetchPair) epp.nextElement(); + pplist.add(pp); + int length = pp.desc.size()+ 1; + pplength.add(length); + ppisMod.add(0); + } + int numpp = ((Hashtable)(prefetch_hash.get(fn))).size(); + for (int i = 0; i < numpp; i++) { + for (int j = i+1; j < numpp; j++) { + boolean ret; + int x = ((Integer) (pplength.get(i))).intValue(); + if (((Integer) (pplength.get(i))).intValue() < ((Integer)( pplength.get(j))).intValue()) { + ret = isSubSet(pplist.get(i), pplist.get(j)); + if (ret) { + ppisMod.set(i, 1); } - for (int i = 0; i < numpp; i++) { - if (((Integer)(ppisMod.get(i))).intValue() == 1) { - PrefetchPair pp = (PrefetchPair) pplist.get(i); - ppairs.remove(pp); - } + } else { + ret = isSubSet(pplist.get(j), pplist.get(i)); + if (ret) { + ppisMod.set(j, 1); } + } } + } + for (int i = 0; i < numpp; i++) { + if (((Integer)(ppisMod.get(i))).intValue() == 1) { + PrefetchPair pp = (PrefetchPair) pplist.get(i); + ppairs.remove(pp); + } + } } - - /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch - * pair else it returns: false */ - private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) { - if (shrt.base != lng.base) { + } + + /** This function returns: true if the shorter prefetch pair is a subset of the longer prefetch + * pair else it returns: false */ + private boolean isSubSet(PrefetchPair shrt, PrefetchPair lng) { + if (shrt.base != lng.base) { + return false; + } + for (int j = 0; j < shrt.desc.size(); j++) { + if(shrt.getDescAt(j) instanceof IndexDescriptor) { + IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j); + if(lng.getDescAt(j) instanceof IndexDescriptor){ + IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j); + if(shrtid.equals(lngid)) { + continue; + } else { return false; + } + } else { + return false; } - for (int j = 0; j < shrt.desc.size(); j++) { - if(shrt.getDescAt(j) instanceof IndexDescriptor) { - IndexDescriptor shrtid = (IndexDescriptor) shrt.getDescAt(j); - if(lng.getDescAt(j) instanceof IndexDescriptor){ - IndexDescriptor lngid = (IndexDescriptor) lng.getDescAt(j); - if(shrtid.equals(lngid)) { - continue; - } else { - return false; - } - } else { - return false; - } - } else { - if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){ - return false; - } - } + } else { + if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){ + return false; } - return true; + } } + return true; + } - /**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 comparePSet1(HashSet oldPSet, HashSetnewPSet) { - boolean hasChanged = false; - - if(oldPSet.size() != newPSet.size()) { - return true; - } else { - for(Iterator it = newPSet.iterator();it.hasNext();) { - if(!oldPSet.contains((PrefetchPair)it.next())) { - return true; - } - } + /**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 comparePSet1(HashSet oldPSet, HashSetnewPSet) { + if(oldPSet.size() != newPSet.size()) { + return true; + } else { + for(Iterator it = newPSet.iterator();it.hasNext();) { + if(!oldPSet.contains((PrefetchPair)it.next())) { + return true; } - return hasChanged; + } } - - /** This function creates a set called pset1 that contains prefetch pairs that have already - * been prefetched. While traversing the graph of a flat representation in a top down fashion, - * this function creates pset1 such that it contains prefetch pairs that have been prefetched at - * the previous nodes */ - - private void applyPrefetchInsertRules(FlatNode fn, LinkedList newvisited, Hashtable> pset1_hash, - Hashtable> newprefetchset) { - - if(fn.kind() == FKind.FlatMethod) { - HashSet pset1 = new HashSet(); - if(prefetch_hash.containsKey(fn)) { - Hashtable prefetchset = prefetch_hash.get(fn); - for(Enumeration e = prefetchset.keys();e.hasMoreElements();) { - PrefetchPair pp = (PrefetchPair) e.nextElement(); - /* Apply initial rule */ - if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) { - pset1.add(pp); - } - } - /* Enqueue child node if Pset1 has changed */ - if (comparePSet1(pset1_hash.get(fn), pset1)) { - for(int j=0; j newvisited, Hashtable> pset1_hash, Hashtable> newprefetchset) { + + if(fn.kind() == FKind.FlatMethod) { + HashSet pset1 = new HashSet(); + if(prefetch_hash.containsKey(fn)) { + Hashtable prefetchset = prefetch_hash.get(fn); + for(Enumeration e = prefetchset.keys();e.hasMoreElements();) { + PrefetchPair pp = (PrefetchPair) e.nextElement(); + /* Apply initial rule */ + if(prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB) { + pset1.add(pp); + } + } + /* Enqueue child node if Pset1 has changed */ + if (comparePSet1(pset1_hash.get(fn), pset1)) { + for(int j=0; j pset2 = new HashSet(); + HashSet newpset = new HashSet(); + if(prefetch_hash.containsKey(fn)) { + Hashtable prefetchset = prefetch_hash.get(fn); + Hashtable ppairmaphash = pmap_hash.get(fn); + for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) { + PrefetchPair pp = (PrefetchPair) epset.nextElement(); + boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB); + boolean mapprobIsLess=false; + boolean mapIsPresent=true; + for(int i=0;i pset2 = new HashSet(); - HashSet newpset = new HashSet(); - if(prefetch_hash.containsKey(fn)) { - Hashtable prefetchset = prefetch_hash.get(fn); - Hashtable ppairmaphash = pmap_hash.get(fn); - for(Enumeration epset = prefetchset.keys(); epset.hasMoreElements();) { - PrefetchPair pp = (PrefetchPair) epset.nextElement(); - boolean pprobIsGreater = (prefetchset.get(pp).doubleValue() >= PREFETCH_THRESHOLD_PROB); - boolean mapprobIsLess=false; - boolean mapIsPresent=true; - for(int i=0;i pset1 = new HashSet(); + pset1.addAll(pset2); + pset1.addAll(newpset); + /* Enqueue child node if Pset1 has changed */ + if (comparePSet1(pset1_hash.get(fn), pset1)) { + for(int i=0; i s = new HashSet(); + for(Iterator it = newpset.iterator(); it.hasNext();) { + PrefetchPair pp = (PrefetchPair) it.next(); + if(!pset2.contains(pp)) { + s.add(pp); + } + } + newprefetchset.put(fn, s); + } + } - HashSet pset1 = new HashSet(); - pset1.addAll(pset2); - pset1.addAll(newpset); - /* Enqueue child node if Pset1 has changed */ - if (comparePSet1(pset1_hash.get(fn), pset1)) { - for(int i=0; i> newprefetchset) { + boolean isFNPresent = false; /* Detects presence of FlatNew node */ + /* This modifies the Flat representation graph */ + for(Enumeration e = newprefetchset.keys();e.hasMoreElements();) { + FlatNode fn = (FlatNode) e.nextElement(); + FlatPrefetchNode fpn = new FlatPrefetchNode(); + if(newprefetchset.get(fn).size() > 0) { + fpn.insAllpp((HashSet)newprefetchset.get(fn)); + if(fn.kind() == FKind.FlatMethod) { + FlatNode nn = fn.getNext(0); + fn.setNext(0, fpn); + fpn.addNext(nn); + } else { + /* Check if previous node of this FlatNode is a NEW node + * If yes, delete this flatnode and its prefetch set from hash table + * This eliminates prefetches for NULL ptrs*/ + for(int i = 0; i< fn.numPrev(); i++) { + FlatNode nn = fn.getPrev(i); + if(nn.kind() == FKind.FlatNew) { + isFNPresent = true; } - - /* To insert prefetch, apply rule: if the newpset minus pset2 is nonempty - * then insert a new prefetch node here*/ - - HashSet s = new HashSet(); - for(Iterator it = newpset.iterator(); it.hasNext();) { - PrefetchPair pp = (PrefetchPair) it.next(); - if(!pset2.contains(pp)) { - s.add(pp); + } + if(!isFNPresent) { + while(fn.numPrev() > 0) { + FlatNode nn = fn.getPrev(0); + for(int j = 0; j> newprefetchset) { - Enumeration e = null; - e = newprefetchset.keys(); - boolean isFNPresent = false; /* Detects presence of FlatNew node */ - /* This modifies the Flat representation graph */ - while(e.hasMoreElements()) { - FlatNode fn = (FlatNode) e.nextElement(); - FlatPrefetchNode fpn = new FlatPrefetchNode(); - if(newprefetchset.get(fn).size() > 0) { - fpn.insAllpp((HashSet)newprefetchset.get(fn)); - if(fn.kind() == FKind.FlatMethod) { - FlatNode nn = fn.getNext(0); - fn.setNext(0, fpn); - fpn.addNext(nn); - } else { - /* Check if previous node of this FlatNode is a NEW node - * If yes, delete this flatnode and its prefetch set from hash table - * This eliminates prefetches for NULL ptrs*/ - for(int i = 0; i< fn.numPrev(); i++) { - FlatNode nn = fn.getPrev(i); - if(nn.kind() == FKind.FlatNew) { - isFNPresent = true; - } - } - if(!isFNPresent) { - while(fn.numPrev() > 0) { - FlatNode nn = fn.getPrev(0); - for(int j = 0; j desc = (ArrayList) getDesc(); + for(ListIterator it = desc.listIterator();it.hasNext();) { + Object o = it.next(); + if(o instanceof IndexDescriptor) { + ArrayList tdarray = (ArrayList)((IndexDescriptor)o).tddesc; + if(tdarray.contains(td)) { + return true; + } + } + } + return false; + } + + /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new + * tempdescriptors when there is a match */ + public PrefetchPair replaceTemp(TempDescriptor td, TempDescriptor[] newtd) { + PrefetchPair npp=(PrefetchPair)clone(); + ArrayList desc = (ArrayList) npp.getDesc(); + for(ListIterator it = desc.listIterator();it.hasNext();) { + Object currdesc = it.next(); + if(currdesc instanceof IndexDescriptor) { + ArrayList tdarray = (ArrayList)((IndexDescriptor)currdesc).tddesc; + if (tdarray.contains(td)) { + int index = tdarray.indexOf(td); + tdarray.set(index, newtd[0]); + for(int i=1;i