From cab1f1ed7349c9224407156a6e0ab7eab3581ac1 Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 15 Nov 2007 10:13:01 +0000 Subject: [PATCH] Bug fixes for termination in loops, make CondBranch code more readable --- .../Analysis/Prefetch/PrefetchAnalysis.java | 555 +++++++++--------- 1 file changed, 277 insertions(+), 278 deletions(-) diff --git a/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java b/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java index 145073b9..29a85210 100644 --- a/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java +++ b/Robust/src/Analysis/Prefetch/PrefetchAnalysis.java @@ -20,7 +20,7 @@ public class PrefetchAnalysis { Hashtable> prefetch_hash; Hashtable branch_prefetch_set; public static final int ROUNDED_MODE = 30; - public static final float THRESHOLD_PROB = (float)0.30; + public static final float THRESHOLD_PROB = (float)0.2; public static final float BRANCH_TRUE_EDGE_PROB = (float)0.5; public static final float BRANCH_FALSE_EDGE_PROB = (float)0.5; @@ -43,7 +43,6 @@ public class PrefetchAnalysis { /** This function creates a new Arraylist of Descriptors by replacing old tempdescriptors with new * tempdescriptors when there is a match for FlatOpNodes or FlatLiteralNodes */ - private ArrayList getNewDesc(PrefetchPair pp, TempDescriptor td, TempDescriptor newtd) { ArrayList desc = (ArrayList) pp.getDesc(); ListIterator it = desc.listIterator(); @@ -109,7 +108,7 @@ public class PrefetchAnalysis { /** This function calls analysis for every node in a method */ private void doFlatNodeAnalysis(FlatMethod fm) { - tovisit = fm.getNodeSet(); //Flat nodes to process + tovisit = fm.getNodeSet(); Hashtable nodehash = new Hashtable(); /* Create Empty Prefetch Sets for all flat nodes in the global hashtable */ while(!tovisit.isEmpty()) { @@ -117,7 +116,8 @@ public class PrefetchAnalysis { prefetch_hash.put(fn, nodehash); tovisit.remove(fn); } - tovisit = fm.getNodeSet(); //Flat nodes to process + /* Visit and process nodes */ + tovisit = fm.getNodeSet(); while(!tovisit.isEmpty()) { FlatNode fn = (FlatNode)tovisit.iterator().next(); /* Generate prefetch pairs after the child node analysis */ @@ -133,132 +133,140 @@ public class PrefetchAnalysis { * returns false : otherwise */ private void doChildNodeAnalysis(FlatNode curr) { - Hashtable child_hash = new Hashtable(); - if(curr.kind()==FKind.FlatCondBranch) { - 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_hash = (Hashtable) prefetch_hash.get(child_node).clone(); - } - switch(curr.kind()) { - case FKind.FlatBackEdge: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatCall: - //TODO change it to take care of FlatMethod, Flatcalls - processFlatCall(curr, child_hash); - break; - case FKind.FlatCheckNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatMethod: - //TODO change it to take care of FlatMethod, Flatcalls - processFlatMethod(curr, child_hash); - break; - case FKind.FlatNew: - processFlatNewNode(curr, child_hash); - break; - case FKind.FlatReturnNode: - //TODO change it to take care of FlatMethod, Flatcalls - processDefaultCase(curr,child_hash); - break; - case FKind.FlatFieldNode: - processFlatFieldNode(curr, child_hash); - break; - case FKind.FlatElementNode: - processFlatElementNode(curr, child_hash); - break; - case FKind.FlatCondBranch: - processFlatCondBranch(curr, child_hash, i, branch_prefetch_set); - break; - case FKind.FlatOpNode: - processFlatOpNode(curr, child_hash); - break; - case FKind.FlatLiteralNode: - processFlatLiteralNode(curr, child_hash); - break; - case FKind.FlatSetElementNode: - processFlatSetElementNode(curr, child_hash); - break; - case FKind.FlatSetFieldNode: - processFlatSetFieldNode(curr, child_hash); - break; - case FKind.FlatAtomicEnterNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatAtomicExitNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatCastNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatFlagActionNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatGlobalConvNode: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatNop: - processDefaultCase(curr,child_hash); - break; - case FKind.FlatTagDeclaration: - processDefaultCase(curr,child_hash); - break; - default: - System.out.println("NO SUCH FLATNODE"); - break; + Hashtable child_prefetch_set_copy = 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(); } - } - } - - /**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) { - boolean hasChanged = false; - PrefetchPair oldpp = null; - PrefetchPair newpp = null; - - if(oldPrefetchSet.size() != newPrefetchSet.size()) { - return true; - } else { - Enumeration e = newPrefetchSet.keys(); - while(e.hasMoreElements()) { - newpp = (PrefetchPair) e.nextElement(); - float newprob = newPrefetchSet.get(newpp); - for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) { - oldpp = (PrefetchPair) elem.nextElement(); - if(oldpp.equals(newpp)) { - /*Compare the difference in their probabilities */ - float oldprob = oldPrefetchSet.get(oldpp); - int diff = (int) ((newprob - oldprob)/oldprob)*100; - if(diff >= ROUNDED_MODE) { - return true; - }else { - } - break; + } + switch(curr.kind()) { + case FKind.FlatBackEdge: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatCall: + //TODO change it to take care of FlatMethod, Flatcalls + //processDefaultCase(curr,child_prefetch_set_copy); + processFlatCall(curr, child_prefetch_set_copy); + break; + case FKind.FlatCheckNode: + 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.FlatNew: + processFlatNewNode(curr, child_prefetch_set_copy); + break; + case FKind.FlatReturnNode: + //TODO change it to take care of FlatMethod, Flatcalls + processDefaultCase(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.FlatCondBranch: + branch_prefetch_set = new Hashtable(); + for (int i = 0; i < curr.numNext(); i++) { + 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); } - } + 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.FlatAtomicEnterNode: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatAtomicExitNode: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatCastNode: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatFlagActionNode: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatGlobalConvNode: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatNop: + processDefaultCase(curr,child_prefetch_set_copy); + break; + case FKind.FlatTagDeclaration: + processDefaultCase(curr,child_prefetch_set_copy); + break; + default: + System.out.println("NO SUCH FLATNODE"); + break; } - return hasChanged; - } +} - /** 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_hash) { - boolean pSetHasChanged = false; - Hashtable currcopy = new Hashtable(); - Hashtable tocompare = new Hashtable(); - FlatFieldNode currffn = (FlatFieldNode) curr; +/**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) { + boolean hasChanged = false; + PrefetchPair oldpp = null; + PrefetchPair newpp = null; + + if(oldPrefetchSet.size() != newPrefetchSet.size()) { + if(newPrefetchSet.size() == 0) { + return false; + } + return true; + } else { + Enumeration e = newPrefetchSet.keys(); + while(e.hasMoreElements()) { + newpp = (PrefetchPair) e.nextElement(); + float newprob = newPrefetchSet.get(newpp); + for(Enumeration elem = oldPrefetchSet.keys(); elem.hasMoreElements();) { + oldpp = (PrefetchPair) elem.nextElement(); + if(oldpp.equals(newpp)) { + /*Compare the difference in their probabilities */ + float oldprob = oldPrefetchSet.get(oldpp); + int diff = (int) ((newprob - oldprob)/oldprob)*100; + if(diff >= ROUNDED_MODE) { + return true; + } + break; + } + } + } + } + return hasChanged; +} + +/** 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) { + boolean pSetHasChanged = false; + Hashtable currcopy = new Hashtable(); + Hashtable tocompare = new Hashtable(); + FlatFieldNode currffn = (FlatFieldNode) curr; /* Do Self analysis of the current node*/ FieldDescriptor currffn_field = currffn.getField(); @@ -270,7 +278,7 @@ public class PrefetchAnalysis { } /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_hash.keys(); + Enumeration ecld = child_prefetch_set_copy.keys(); PrefetchPair currpp = null; PrefetchPair childpp = null; while (ecld.hasMoreElements()) { @@ -282,30 +290,30 @@ public class PrefetchAnalysis { newdesc.add(currffn.getField()); newdesc.addAll(childpp.desc); PrefetchPair newpp = new PrefetchPair(currffn.getSrc(), newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } } } else if(childpp.base == currffn.getDst() && (childpp.getDesc() == null)) { - child_hash.remove(childpp); + 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 and then remove the common one from the child prefetch set */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); Enumeration e = null; while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); @@ -315,18 +323,18 @@ public class PrefetchAnalysis { /* Probability of the incoming edge for a FlatFieldNode is always 100% */ Float prob = currcopy.get(currpp).floatValue(); currcopy.put(currpp, prob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); break; } } } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Merge curr prefetch pairs */ @@ -354,14 +362,13 @@ public class PrefetchAnalysis { * 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_hash) { + private void processFlatElementNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable currcopy = new Hashtable(); Hashtable tocompare = new Hashtable(); FlatElementNode currfen = (FlatElementNode) curr; - /* Do Self analysis of the current node*/ TempDescriptor currfen_index = currfen.getIndex(); IndexDescriptor idesc = new IndexDescriptor(currfen_index, 0); @@ -373,7 +380,7 @@ public class PrefetchAnalysis { } /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_hash.keys(); + Enumeration ecld = child_prefetch_set_copy.keys(); PrefetchPair currpp = null; PrefetchPair childpp = null; while (ecld.hasMoreElements()) { @@ -385,28 +392,28 @@ public class PrefetchAnalysis { newdesc.add((Descriptor)idesc); newdesc.addAll(childpp.desc); PrefetchPair newpp = new PrefetchPair(currfen.getSrc(), newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } } } else if(childpp.base == currfen.getDst() && (childpp.getDesc() == null)) { - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); } } /* Check if curr prefetch set and the child prefetch set have same prefetch pairs * if so calculate the new probability and then remove the common one from the child prefetch set */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); Enumeration e = null; while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); @@ -416,18 +423,18 @@ public class PrefetchAnalysis { /* Probability of the incoming edge for a FlatElementNode is always 100% */ Float prob = currcopy.get(currpp).floatValue(); currcopy.put(currpp, prob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); break; } } } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Merge curr prefetch pairs */ @@ -455,14 +462,14 @@ public class PrefetchAnalysis { * 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_hash) { + private void processFlatSetFieldNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); FlatSetFieldNode currfsfn = (FlatSetFieldNode) curr; PrefetchPair childpp = null; /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_hash.keys(); + Enumeration ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); if(childpp.base == currfsfn.getDst()) { @@ -474,24 +481,24 @@ public class PrefetchAnalysis { newdesc.add(i,childpp.desc.get(i+1)); } PrefetchPair newpp = new PrefetchPair(currfsfn.getSrc(), newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); - /* Check for independence of prefetch pairs in newly generated and child_hash prefetch pairs + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs in newly generated and child_prefetch_set_copy prefetch pairs * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } } } else if(size==1) { if((childpp.getDescAt(0) instanceof FieldDescriptor) && (childpp.getDescAt(0) == currfsfn.getField())) { - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); } } else { continue; @@ -500,11 +507,11 @@ public class PrefetchAnalysis { } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Compare with the orginal prefetch pairs */ @@ -524,55 +531,56 @@ public class PrefetchAnalysis { * 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_hash) { + private void processFlatSetElementNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); PrefetchPair childpp = null; FlatSetElementNode currfsen = (FlatSetElementNode) curr; /* Get each prefetch pair of the child and match it with the destination temp descriptor of curr FlatFieldNode */ - Enumeration ecld = child_hash.keys(); + Enumeration ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { 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((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizetempdesc==1) && (sizedesc>=2)) { - //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table - 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); - Float newprob = child_hash.get(childpp).floatValue(); - tocompare.put(newpp, newprob); - child_hash.remove(childpp); - /* Check for independence of prefetch pairs if any in the child prefetch set - * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); - if(newprob < THRESHOLD_PROB) { - tocompare.remove(newpp); - } else { - tocompare.put(newpp, newprob); + if(sizetempdesc == 1) { + if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc>=2)) { + //if match exists then create a new Prefetch set with the new prefetch pair in a new hash table + 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); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); + tocompare.put(newpp, newprob); + child_prefetch_set_copy.remove(childpp); + /* Check for independence of prefetch pairs if any in the child prefetch set + * to compute new probability */ + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(newprob < THRESHOLD_PROB) { + tocompare.remove(newpp); + } else { + tocompare.put(newpp, newprob); + } + child_prefetch_set_copy.remove(newpp); } - child_hash.remove(newpp); + } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizedesc==1)) + child_prefetch_set_copy.remove(childpp); + } else { + continue; } - } else if((((IndexDescriptor)childpp.getDescAt(0)).tddesc.get(0) == currfsen.getIndex()) && (sizetempdesc==1) && (sizedesc==1)) { - child_hash.remove(childpp); - } else { - continue; } } - } } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Compare with the orginal prefetch pairs */ pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), tocompare); @@ -589,7 +597,7 @@ public class PrefetchAnalysis { /** This function applies rules and does analysis for a FlatOpNode * And updates the global prefetch hashtable * */ - private void processFlatOpNode(FlatNode curr, Hashtable child_hash) { + private void processFlatOpNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; int index; Hashtable tocompare = new Hashtable(); @@ -599,7 +607,7 @@ public class PrefetchAnalysis { /* Check the Operation type of flatOpNode */ if(currfopn.getOp().getOp()== Operation.ASSIGN) { - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); @@ -610,19 +618,19 @@ public class PrefetchAnalysis { ArrayList newdesc = new ArrayList(); newdesc.addAll(childpp.desc); PrefetchPair newpp = new PrefetchPair(currfopn.getLeft(), newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } /* Any member of the desc of child prefetch pair is same as destination of the current FlatOpNode * For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/ @@ -630,19 +638,19 @@ public class PrefetchAnalysis { ArrayList newdesc = new ArrayList(); newdesc.addAll((ArrayList)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft())); PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability*/ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } }else { continue; @@ -650,7 +658,7 @@ public class PrefetchAnalysis { } } else if(currfopn.getRight()!=null && (currfopn.getOp().getOp() == Operation.ADD)) { //case i = i+z followed by a[i].x - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); @@ -659,19 +667,19 @@ public class PrefetchAnalysis { ArrayList newdesc = new ArrayList(); newdesc.addAll((ArrayList)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft(), currfopn.getRight())); PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Float newprob = child_hash.get(childpp).floatValue(); + Float newprob = child_prefetch_set_copy.get(childpp).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability*/ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } }else { continue; @@ -682,11 +690,11 @@ public class PrefetchAnalysis { } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Compare with the orginal prefetch pairs */ @@ -700,8 +708,11 @@ public class PrefetchAnalysis { prefetch_hash.put(curr,tocompare); } } - - private void processFlatLiteralNode(FlatNode curr, Hashtable child_hash) { + + /** This function processes a FlatLiteralNode where cases such as + * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r + * are handled */ + private void processFlatLiteralNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); FlatLiteralNode currfln = (FlatLiteralNode) curr; @@ -709,7 +720,7 @@ public class PrefetchAnalysis { PrefetchPair childpp = null; if(currfln.getType().isIntegerType()) { - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone(); @@ -717,45 +728,49 @@ public class PrefetchAnalysis { * for cases like i = 0 followed by t = a[i].r or t = a[j+i].r or t = a[j].b[i].r*/ if(isTempDescFound(copyofchildpp,currfln.getDst())) { ArrayList copychilddesc = (ArrayList) copyofchildpp.getDesc(); + int sizetempdesc = copychilddesc.size(); ListIterator it = copychilddesc.listIterator(); for(;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()); - ((IndexDescriptor)o).offset = (Integer)currfln.getValue(); td.remove(index); + if((Integer)(currfln.getValue()) != 0) { + ((IndexDescriptor)o).offset = (Integer)currfln.getValue(); + } } } } ArrayList newdesc = new ArrayList(); newdesc.addAll(copychilddesc); PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); - Float newprob = (child_hash.get(childpp)).floatValue(); + Float newprob = (child_prefetch_set_copy.get(childpp)).floatValue(); tocompare.put(newpp, newprob); - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); /* Check for independence of prefetch pairs if any in the child prefetch set * to compute new probability */ - if(child_hash.containsKey(newpp)) { - newprob = (float)(1.0 - ((1.0 - child_hash.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); + if(child_prefetch_set_copy.containsKey(newpp)) { + newprob = (float)(1.0 - ((1.0 - child_prefetch_set_copy.get(newpp).floatValue()) * (1.0 - tocompare.get(newpp).floatValue()))); if(newprob < THRESHOLD_PROB) { tocompare.remove(newpp); } else { tocompare.put(newpp, newprob); } - child_hash.remove(newpp); + child_prefetch_set_copy.remove(newpp); } } } } /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Compare with the orginal prefetch pairs */ @@ -771,7 +786,9 @@ public class PrefetchAnalysis { } - private void processFlatMethod(FlatNode curr, Hashtable child_hash) { + /** 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) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); FlatMethod currfm = (FlatMethod) curr; @@ -779,11 +796,11 @@ public class PrefetchAnalysis { PrefetchPair childpp = null; /* Merge child prefetch pairs */ - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while(ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } /* Compare with the orginal prefetch pairs */ @@ -799,8 +816,7 @@ public class PrefetchAnalysis { * It currently drops the propagation of those prefetchpairs that are passed as * arguments in the FlatCall */ - - private void processFlatCall(FlatNode curr, Hashtable child_hash) { + private void processFlatCall(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); FlatCall currfcn = (FlatCall) curr; @@ -808,24 +824,15 @@ public class PrefetchAnalysis { PrefetchPair childpp = null; boolean isSameArg = false; - for(int i= 0; i child_hash, int index, + private void processFlatCondBranch(FlatNode curr, Hashtable child_prefetch_set_copy, int index, Hashtable branch_prefetch_set) { boolean pSetHasChanged = false; - Hashtable tocompare = new Hashtable(); + Hashtable tocompare = new Hashtable();//temporary hash table FlatCondBranch currfcb = (FlatCondBranch) curr; Float newprob = new Float((float)0.0); PrefetchPair childpp = null; PrefetchPair pp = null; Enumeration ecld = null; - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); - /* Create a new Prefetch set*/ - ArrayList newdesc = new ArrayList(); - newdesc.addAll(childpp.desc); - PrefetchPair newpp = new PrefetchPair(childpp.base, newdesc); /* True Edge */ if(index == 0) { - newprob = child_hash.get(childpp).floatValue() * BRANCH_TRUE_EDGE_PROB; + newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_TRUE_EDGE_PROB; if(newprob >= THRESHOLD_PROB) { - tocompare.put(newpp, newprob); - child_hash.remove(newpp); + tocompare.put(childpp, newprob); } + child_prefetch_set_copy.remove(childpp); } else if(index == 1) { /* False Edge */ - newprob = child_hash.get(childpp).floatValue() * BRANCH_FALSE_EDGE_PROB; + newprob = child_prefetch_set_copy.get(childpp).floatValue() * BRANCH_FALSE_EDGE_PROB; if(newprob >= THRESHOLD_PROB) { - tocompare.put(newpp, newprob); - child_hash.remove(newpp); + tocompare.put(childpp, newprob); } + child_prefetch_set_copy.remove(childpp); } else { System.out.println("DEBUG-> No more children of the FlatCondBranchNode present"); } } - /* Merge child prefetch pairs */ - ecld = child_hash.keys(); - while(ecld.hasMoreElements()) { - childpp = (PrefetchPair) ecld.nextElement(); - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); - } - - /* Update the new branch_prefetch_hashtable to store all new prefetch pairs */ + /* 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) { branch_prefetch_set.putAll(tocompare); @@ -921,7 +917,9 @@ public class PrefetchAnalysis { } } - /* Enqueue parent nodes */ + /* Enqueue parent nodes only after the prefetch sets of both child node have been evaluated + * and the branch_prefetch_set (hashtable) has been built containing the prefetch pairs for the + * incoming edge of the current node */ if(index == 1) { pSetHasChanged = comparePrefetchSets(prefetch_hash.get(curr), branch_prefetch_set); if(pSetHasChanged) { @@ -931,21 +929,19 @@ public class PrefetchAnalysis { /* Overwrite the new prefetch set to the global hash table */ prefetch_hash.put(curr,branch_prefetch_set); } - } } - /** If FlatNode is not concerned with the prefetch set of its Child then propagate * prefetches up the FlatNode*/ - private void processDefaultCase(FlatNode curr, Hashtable child_hash) { + private void processDefaultCase(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Enumeration e = null; Hashtable tocompare = new Hashtable(); - for(e = child_hash.keys(); e.hasMoreElements();) { + for(e = child_prefetch_set_copy.keys(); e.hasMoreElements();) { PrefetchPair newpp = (PrefetchPair) e.nextElement(); - tocompare.put(newpp, child_hash.get(newpp)); + tocompare.put(newpp, child_prefetch_set_copy.get(newpp)); } /* Compare with old Prefetch sets */ @@ -959,7 +955,10 @@ public class PrefetchAnalysis { } } - private void processFlatNewNode(FlatNode curr, Hashtable child_hash) { + /** This function processes for FlatNewNode + * for e.g x = NEW(foo) followed by childnode with prefetch set x.f + * then drop the prefetches beyond this FlatNewNode */ + private void processFlatNewNode(FlatNode curr, Hashtable child_prefetch_set_copy) { boolean pSetHasChanged = false; Hashtable tocompare = new Hashtable(); FlatNew currfnn = (FlatNew) curr; @@ -967,14 +966,14 @@ public class PrefetchAnalysis { PrefetchPair childpp = null; Enumeration ecld = null; - ecld = child_hash.keys(); + ecld = child_prefetch_set_copy.keys(); while (ecld.hasMoreElements()) { childpp = (PrefetchPair) ecld.nextElement(); if(childpp.base == currfnn.getDst()){ - child_hash.remove(childpp); + child_prefetch_set_copy.remove(childpp); } else { - tocompare.put(childpp, child_hash.get(childpp)); - child_hash.remove(childpp); + tocompare.put(childpp, child_prefetch_set_copy.get(childpp)); + child_prefetch_set_copy.remove(childpp); } } -- 2.34.1