public static final float PREFETCH_THRESHOLD_PROB = (float)0.30;
public static final float BRANCH_TRUE_EDGE_PROB = (float)0.5;
public static final float BRANCH_FALSE_EDGE_PROB = (float)0.5;
-
+
public PrefetchAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
this.typeutil=typeutil;
this.state=state;
prefetch_hash = new Hashtable<FlatNode, Hashtable<PrefetchPair,Float>>();
pmap_hash = new Hashtable<FlatNode, Hashtable<FlatNode, PairMap>>();
DoPrefetch();
+ prefetch_hash = null;
+ pmap_hash = null;
}
/** This function returns true if a tempdescriptor object is found in the array of descriptors
if(newprefetchset.size() > 0) {
addFlatPrefetchNode(newprefetchset);
}
+ newprefetchset = null;
+ pset1_hash = null;
}
}
prefetch_hash.put(fn, nodehash);
tovisit.remove(fn);
}
+
+ nodehash = null;
+
/* Visit and process nodes */
tovisit = fm.getNodeSet();
while(!tovisit.isEmpty()) {
child_prefetch_set_copy = (Hashtable<PrefetchPair,Float>) prefetch_hash.get(child_node).clone();
}
processFlatCondBranch(curr, child_prefetch_set_copy, i, branch_prefetch_set, parentpmap);
+ parentpmap = null;
}
+ branch_prefetch_set = null;
break;
case FKind.FlatOpNode:
processFlatOpNode(curr, child_prefetch_set_copy, parentpmap);
System.out.println("NO SUCH FLATNODE");
break;
}
+
+ /* Free Heap Memory */
+ child_prefetch_set_copy = null;
+ parentpmap = null;
}
/**This function compares all the prefetch pairs in a Prefetch set hashtable and
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+
+ /* Free Heap Memory */
+ currcopy = null;
+ tocompare = null;
+ pm = null;
}
/** This function processes the prefetch set of a FlatElementNode
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+
+ /* Free heap memory */
+ currcopy = null;
+ tocompare = null;
+ pm = null;
}
/** This function processes the prefetch set of a FlatSetFieldNode
childpp = (PrefetchPair) ecld.nextElement();
if(childpp.base == currfsfn.getDst()) {
int size = childpp.desc.size();
- if(size >=2) {
+ 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<Descriptor> newdesc = new ArrayList<Descriptor>();
for(int i = 0;i<(childpp.desc.size()-1); i++) {
child_prefetch_set_copy.remove(newpp);
}
}
- } else if(size==1) {
+ } 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);
}
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
- /** This function processes the prefetch set of a FlatSeElementNode
+ /** 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
int sizedesc = childpp.desc.size();
if((childpp.getDescAt(0) instanceof IndexDescriptor)) {
int sizetempdesc = ((IndexDescriptor)(childpp.getDescAt(0))).tddesc.size();
- if(sizetempdesc == 1) {
+ 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<Descriptor> newdesc = new ArrayList<Descriptor>();
for(int i = 0;i<(childpp.desc.size()-1); i++) {
newdesc.add(i,childpp.desc.get(i+1));
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;
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This function applies rules and does analysis for a FlatOpNode
childpp = (PrefetchPair) ecld.nextElement();
PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
- /* For cases like x=y followed by childnode t=x[i].z or t=x.g*/
+ /* For cases like x=y with child prefetch set x[i].z,x.g*/
if(childpp.base == currfopn.getDest()) {
ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
newdesc.addAll(childpp.desc);
}
child_prefetch_set_copy.remove(newpp);
}
- /* For cases like x=y followed by t = r[i].x or t =r[x].p or t = r[p+x].q*/
+ newdesc = null;
+ newpp = null;
+ /* For cases like x=y with child prefetch set r[i].x, r[x].p, r[p+x].q*/
} else if(isTempDescFound(copyofchildpp, currfopn.getDest())) {
ArrayList<Descriptor> newdesc = new ArrayList<Descriptor>();
newdesc.addAll((ArrayList<Descriptor>)getNewDesc(copyofchildpp, currfopn.getDest(), currfopn.getLeft()));
}
child_prefetch_set_copy.remove(newpp);
}
+ newdesc = null;
+ newpp = null;
}else {
continue;
}
}
- //case i = i+z followed by a[i].x
+ //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()) {
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** 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
+ * 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<PrefetchPair, Float> child_prefetch_set_copy,
Hashtable<FlatNode, PairMap> parentpmap) {
while (ecld.hasMoreElements()) {
childpp = (PrefetchPair) ecld.nextElement();
PrefetchPair copyofchildpp = (PrefetchPair) childpp.clone();
- /* 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<Descriptor> copychilddesc = (ArrayList<Descriptor>) copyofchildpp.getDesc();
int sizetempdesc = copychilddesc.size();
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This function processes a FlatMethod where the method propagates
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ tocompare = null;
+ pm = null;
}
/** This Function processes the FlatCalls
- * It currently drops the propagation of those prefetchpairs that are passed as
- * arguments in the FlatCall
+ * It currently drops the propagation of those prefetchpairs whose base is
+ * same as the destination of the FlatCall
*/
private void processFlatCall(FlatNode curr, Hashtable<PrefetchPair, Float> child_prefetch_set_copy,
Hashtable<FlatNode, PairMap> parentpmap) {
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This function handles the processes the FlatNode of type FlatCondBranch
prefetch_hash.put(curr,branch_prefetch_set);
}
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** If FlatNode is not concerned with the prefetch set of its Child then propagate
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This functions processes for FlatNewNode
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This functions processes for FlatTagDeclaration
/* Overwrite the new prefetch set to the global hash table */
prefetch_hash.put(curr,tocompare);
}
+
+ /* Free heap memory */
+ tocompare = null;
+ pm = null;
}
/** This function prints the Prefetch pairs of a given flatnode */
}
}
+ /* Free Heap Memory */
+ pset1_init = null;
+ newtovisit = null;
+
+ /* Delete redundant and subset prefetch pairs */
+ delSubsetPPairs();
+
+ /* Start with a top down sorted order of nodes */
while(!newvisited.isEmpty()) {
applyPrefetchInsertRules((FlatNode) newvisited.getFirst());
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() {
+ Enumeration e = prefetch_hash.keys();
+ while(e.hasMoreElements()) {
+ FlatNode fn = (FlatNode) e.nextElement();
+ Hashtable ppairs = prefetch_hash.get(fn);
+ Enumeration epp = ((Hashtable)(prefetch_hash.get(fn))).keys();
+ Vector<PrefetchPair> pplist = new Vector<PrefetchPair>();
+ 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);
+ }
+ }
+ }
+ }
+ for (int i = 0; i < numpp; i++) {
+ if (((Integer)(ppisMod.get(i))).intValue() == 1) {
+ PrefetchPair pp = (PrefetchPair) pplist.get(i);
+ ppairs.remove(pp);
+ }
+ }
+
+ /* Free heap memory */
+ pplist = null;
+ pplength = null;
+ ppisMod = null;
+ }
+ }
+ /** 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;
+ }
+ } else {
+ if ((Descriptor)shrt.getDescAt(j) != (Descriptor)lng.getDescAt(j)){
+ return false;
+ }
+ }
+ }
+ 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
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) {
HashSet<PrefetchPair> pset1 = new HashSet<PrefetchPair>();
HashSet<PrefetchPair> pset2 = new HashSet<PrefetchPair>();
}
pset1_hash.put(fn, pset1);
- /* To insert prefetch apply rule */
+
+ /* To insert prefetch apply rule: if the newpset intersection pset2 is nonempty
+ * then insert a new prefetch node here*/
HashSet<PrefetchPair> s = new HashSet<PrefetchPair>();
- //if(!newpset.isEmpty() && !pset2.isEmpty()) {
if(!newpset.isEmpty()) {
if(!pset2.isEmpty()) {
for(Iterator it = newpset.iterator(); it.hasNext();) {
newprefetchset.put(fn, s);
}
}
- }
+ /* Free heap memory */
+ pset1 = null;
+ pset2 = null;
+ newpset = null;
+ prefetchset = null;
+ }
private void addFlatPrefetchNode(Hashtable<FlatNode, HashSet<PrefetchPair>> newprefetchset) {
int i;
Enumeration e = null;
e = newprefetchset.keys();
+ boolean isFNPresent = false; /* Detects presence of FlatNew node */
/* This modifies the graph */
while(e.hasMoreElements()) {
FlatNode fn = (FlatNode) e.nextElement();
for(i = 0; i< newprefetchset.get(fn).size(); i++) {
fpn.insAllpp((HashSet)newprefetchset.get(fn));
}
- //System.out.println("The HashSet of prefetch pairs are "+ fpn.getPrefetchPairs());
if(fn.kind() == FKind.FlatMethod) {
FlatNode nn = fn.getNext(0);
fn.setNext(0, fpn);
fpn.addNext(nn);
} else {
- while(fn.numPrev() > 0) {
- FlatNode nn = fn.getPrev(0);
- for(int j = 0; j<nn.numNext(); j++) {
- if(nn.getNext(j) == fn) {
- nn.setNext(j, fpn);
+ /* 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(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<nn.numNext(); j++) {
+ if(nn.getNext(j) == fn) {
+ nn.setNext(j, fpn);
+ }
}
}
+ fpn.addNext(fn);
}
- fpn.addNext(fn);
}
}
}
projects / IRC.git / blobdiff