From e800e30ed229bcbf7553a1b4b7863f78100e5542 Mon Sep 17 00:00:00 2001 From: yeom Date: Wed, 6 Jan 2010 04:31:49 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/MLP/ConflictGraph.java | 42 +++++--- Robust/src/Analysis/MLP/MLPAnalysis.java | 55 ++++++++-- .../Analysis/MLP/ParentChildConflictsMap.java | 18 +++- .../OwnershipAnalysis/HeapRegionNode.java | 4 +- Robust/src/IR/Flat/BuildCode.java | 101 +++++++++++++----- Robust/src/Runtime/mlp_runtime.c | 15 ++- Robust/src/Runtime/mlp_runtime.h | 4 +- 7 files changed, 180 insertions(+), 59 deletions(-) diff --git a/Robust/src/Analysis/MLP/ConflictGraph.java b/Robust/src/Analysis/MLP/ConflictGraph.java index 3156706d..53933c87 100644 --- a/Robust/src/Analysis/MLP/ConflictGraph.java +++ b/Robust/src/Analysis/MLP/ConflictGraph.java @@ -40,7 +40,7 @@ public class ConflictGraph { Set writeEffectsSet = nodeB.getWriteEffectsSet(); Set readEffectsSet = nodeB.getReadEffectsSet(); - + if (writeEffectsSet != null) { Iterator writeIter = writeEffectsSet.iterator(); while (writeIter.hasNext()) { @@ -74,6 +74,25 @@ public class ConflictGraph { } } + + // add for another case + if (readEffectsSet != null) { + Iterator readIter = readEffectsSet.iterator(); + while (readIter.hasNext()) { + SESEEffectsKey seseEffectsKey = (SESEEffectsKey) readIter + .next(); + String readHeapRegionID = seseEffectsKey.getHRNUniqueId(); + HashSet stallSiteHRNSet = nodeA.getHRNSet(); + for (Iterator iterator = stallSiteHRNSet.iterator(); iterator + .hasNext();) { + HeapRegionNode stallHRN = (HeapRegionNode) iterator.next(); + if (stallHRN.getGloballyUniqueIdentifier().equals( + readHeapRegionID)) { + result = result | true; + } + } + } + } } if (readEffectsSet != null) { @@ -461,9 +480,9 @@ public class ConflictGraph { return resultSet; } - public Set getAllocationSiteIDSetBySESEID(int seseID) { + public Set getAllocationSiteIDSetBySESEID(int seseID) { - HashSet allocSiteIDSet = new HashSet(); + HashSet allocSiteIDSet = new HashSet(); Set> s = id2cn.entrySet(); Iterator> i = s.iterator(); @@ -475,7 +494,6 @@ public class ConflictGraph { if (node instanceof LiveInNode) { LiveInNode liveInNode = (LiveInNode) node; if (liveInNode.getSESEIdentifier() == seseID) { - HashSet edgeSet = liveInNode.getEdgeSet(); for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { ConflictEdge conflictEdge = (ConflictEdge) iterator.next(); @@ -495,9 +513,9 @@ public class ConflictGraph { } - public Set getAllocationSiteIDSetofStallSite() { + public Set getAllocationSiteIDSetofStallSite() { - HashSet allocSiteIDSet = new HashSet(); + HashSet allocSiteIDSet = new HashSet(); Set> s = id2cn.entrySet(); Iterator> i = s.iterator(); @@ -517,9 +535,9 @@ public class ConflictGraph { } - public Set getAllocationSiteIDSet() { + public Set getAllocationSiteIDSet() { - HashSet allocSiteIDSet = new HashSet(); + HashSet allocSiteIDSet = new HashSet(); Set> s = id2cn.entrySet(); Iterator> i = s.iterator(); @@ -545,9 +563,9 @@ public class ConflictGraph { } - private HashSet getHRNIdentifierSet(ConflictNode node) { + private HashSet getHRNIdentifierSet(ConflictNode node) { - HashSet returnSet = new HashSet(); + HashSet returnSet = new HashSet(); if (node instanceof StallSiteNode) { StallSiteNode stallSiteNode = (StallSiteNode) node; @@ -555,7 +573,7 @@ public class ConflictGraph { for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) { HeapRegionNode hrn = (HeapRegionNode) iterator.next(); // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier()); - returnSet.add(new Integer(hrn + returnSet.add(new Long(hrn .getGloballyUniqueIntegerIdentifier())); } } else { @@ -564,7 +582,7 @@ public class ConflictGraph { for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) { HeapRegionNode hrn = (HeapRegionNode) iterator.next(); // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier()); - returnSet.add(new Integer(hrn + returnSet.add(new Long(hrn .getGloballyUniqueIntegerIdentifier())); } } diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 9cf47317..53cc78fb 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -38,6 +38,7 @@ import IR.State; import IR.TypeUtil; import IR.Flat.FKind; import IR.Flat.FlatCall; +import IR.Flat.FlatCondBranch; import IR.Flat.FlatEdge; import IR.Flat.FlatFieldNode; import IR.Flat.FlatLiteralNode; @@ -2033,6 +2034,7 @@ public class MLPAnalysis { Hashtable stallMap = currentConflictsMap .getStallMap(); + Set> entrySet = stallMap .entrySet(); @@ -2170,7 +2172,7 @@ public class MLPAnalysis { .hasNext();) { TempDescriptor tempDescriptor = (TempDescriptor) iterator .next(); - + // effects set SESEEffectsSet seseEffectsSet = fsen.getSeseEffectsSet(); Set readEffectsSet = seseEffectsSet @@ -2237,7 +2239,7 @@ public class MLPAnalysis { while (mcIter.hasNext()) { MethodContext mc = mcIter.next(); - Set flatNodesToVisit = new HashSet(); + LinkedList flatNodesToVisit=new LinkedList(); flatNodesToVisit.add(fm); SESESummary summary = new SESESummary(null, fm); @@ -2246,11 +2248,11 @@ public class MLPAnalysis { while (!flatNodesToVisit.isEmpty()) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); flatNodesToVisit.remove(fn); - ParentChildConflictsMap prevResult = conflictsResults .get(fn); // merge sets from control flow + Boolean prevSESE=null; ParentChildConflictsMap currentConflictsMap = new ParentChildConflictsMap(); for (int i = 0; i < fn.numPrev(); i++) { FlatNode prevFlatNode = fn.getPrev(i); @@ -2259,10 +2261,14 @@ public class MLPAnalysis { if (incoming != null) { currentConflictsMap.merge(incoming); } + + if(prevFlatNode instanceof FlatCondBranch){ + prevSESE=isAfterChildSESEIndicatorMap.get(prevFlatNode); + } } - SESESummary currentSummary = seseSummaryMap.get(fn); - if (currentSummary == null) { + //if (currentSummary == null) { + if(!(fn instanceof FlatMethod)){ FlatNode current = null; FlatNode currentParent = null; // calculate sese summary info from previous flat nodes @@ -2285,6 +2291,7 @@ public class MLPAnalysis { currentParent = prevSummary .getCurrentParent(); } + break; } } @@ -2292,17 +2299,37 @@ public class MLPAnalysis { currentSummary = new SESESummary(currentParent, current); seseSummaryMap.put(fn, currentSummary); } + + if(prevSESE!=null){ + if(fn instanceof FlatSESEEnterNode){ + isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), currentConflictsMap.isAfterSESE()); + }else{ + isAfterChildSESEIndicatorMap.put(currentSummary.getCurrentSESE(), prevSESE); + } + } + + Boolean b=isAfterChildSESEIndicatorMap.get(currentSummary.getCurrentSESE());; + if(b==null){ + currentConflictsMap.setIsAfterSESE(false); + }else{ + currentConflictsMap.setIsAfterSESE(b.booleanValue()); + } + + FlatNode tempP=currentSummary.getCurrentParent(); + FlatNode tempS=currentSummary.getCurrentSESE(); conflicts_nodeAction(mc, fn, callGraph, preeffectsSet, currentConflictsMap, currentSummary); + // if we have a new result, schedule forward nodes for // analysis if (!currentConflictsMap.equals(prevResult)) { + seseSummaryMap.put(fn, currentSummary); conflictsResults.put(fn, currentConflictsMap); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); - flatNodesToVisit.add(nn); + flatNodesToVisit.addFirst(nn); } } @@ -2334,7 +2361,7 @@ public class MLPAnalysis { FlatNode parentNode = currentSummary.getCurrentSESE(); currentSummary.setCurrentParent(parentNode); currentSummary.setCurrentSESE(fsen); - seseSummaryMap.put(fsen, currentSummary); +// seseSummaryMap.put(fsen, currentSummary); } if (!fsen.getIsCallerSESEplaceholder()) { @@ -2367,6 +2394,18 @@ public class MLPAnalysis { } break; + + case FKind.FlatCondBranch: { + boolean isAfterChildSESE = false; + FlatNode current = currentSummary.getCurrentSESE(); + Boolean isAfter = isAfterChildSESEIndicatorMap.get(current); + if (isAfter != null && isAfter.booleanValue()) { + isAfterChildSESE = true; + } + isAfterChildSESEIndicatorMap.put(fn, new Boolean(isAfterChildSESE)); + } + break; + case FKind.FlatNew: { FlatNew fnew = (FlatNew) fn; @@ -2870,7 +2909,7 @@ public class MLPAnalysis { } - seseSummaryMap.put(fn, currentSummary); +// seseSummaryMap.put(fn, currentSummary); } diff --git a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java index 25135535..0f569d47 100644 --- a/Robust/src/Analysis/MLP/ParentChildConflictsMap.java +++ b/Robust/src/Analysis/MLP/ParentChildConflictsMap.java @@ -20,12 +20,22 @@ public class ParentChildConflictsMap { private Hashtable accessibleMap; private Hashtable stallMap; private Hashtable < ReferenceEdge, HashSet > stallEdgeMap; + private boolean isAfterSESE; public ParentChildConflictsMap() { accessibleMap = new Hashtable(); stallMap = new Hashtable(); stallEdgeMap= new Hashtable < ReferenceEdge, HashSet >(); + isAfterSESE=false; + } + + public void setIsAfterSESE(boolean after){ + this.isAfterSESE=after; + } + + public boolean isAfterSESE(){ + return isAfterSESE; } public void clear(){ @@ -231,9 +241,9 @@ public class ParentChildConflictsMap { } - public Set getAllocationSiteIDSetofStallSite() { + public Set getAllocationSiteIDSetofStallSite() { - HashSet returnSet=new HashSet(); + HashSet returnSet=new HashSet(); Enumeration stallSiteEnum=stallMap.elements(); while (stallSiteEnum.hasMoreElements()) { @@ -242,7 +252,7 @@ public class ParentChildConflictsMap { for (Iterator iterator = hrnSet.iterator(); iterator.hasNext();) { HeapRegionNode hrn = (HeapRegionNode) iterator.next(); // allocSiteIDSet.add(hrn.getGloballyUniqueIdentifier()); - returnSet.add(new Integer(hrn + returnSet.add(new Long(hrn .getGloballyUniqueIntegerIdentifier())); } } @@ -263,7 +273,7 @@ public class ParentChildConflictsMap { ParentChildConflictsMap in = (ParentChildConflictsMap) o; if ( accessibleMap.equals(in.getAccessibleMap()) - && stallMap.equals(in.getStallMap())) { + && stallMap.equals(in.getStallMap()) && isAfterSESE()==in.isAfterSESE()) { return true; } else { return false; diff --git a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java index 16cc332b..8c20871b 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java +++ b/Robust/src/Analysis/OwnershipAnalysis/HeapRegionNode.java @@ -232,7 +232,7 @@ public class HeapRegionNode extends OwnershipNode { return globalIdentifier; } - public int getGloballyUniqueIntegerIdentifier() { + public long getGloballyUniqueIntegerIdentifier() { String fristpart = globalIdentifier; fristpart = fristpart.replaceAll("FN", "1"); fristpart = fristpart.replaceAll("FM", "2"); @@ -242,6 +242,6 @@ public class HeapRegionNode extends OwnershipNode { endpart = endpart.replaceAll("P", "2"); endpart = endpart.replaceAll("A", "3"); String modified = fristpart.substring(0, idx) + endpart; - return Integer.parseInt(modified); + return Long.parseLong(modified); } } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index b50f7b0a..aa242605 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -1764,18 +1764,19 @@ public class BuildCode { // set up related allocation sites's waiting queues // eom output.println(" /* set up waiting queues */"); + output.println(" int numRelatedAllocSites=0;"); ConflictGraph graph=null; graph=mlpa.getConflictGraphResults().get(fm); if(graph!=null){ - Set allocSet=graph.getAllocationSiteIDSet(); + Set allocSet=graph.getAllocationSiteIDSet(); if(allocSet.size()>0){ - output.println(" int numRelatedAllocSites="+allocSet.size()+";"); + output.println(" numRelatedAllocSites="+allocSet.size()+";"); output.println(" seseCaller->numRelatedAllocSites=numRelatedAllocSites;"); output.println(" seseCaller->allocSiteArray=mlpCreateAllocSiteArray(numRelatedAllocSites);"); int idx=0; for (Iterator iterator = allocSet.iterator(); iterator.hasNext();) { - Integer allocID = (Integer) iterator.next(); + Long allocID = (Long) iterator.next(); output.println(" seseCaller->allocSiteArray["+idx+"].id="+allocID+";"); idx++; } @@ -2062,6 +2063,37 @@ public class BuildCode { output.println(" "+type+" "+temp+";"); } } + + // set up related allocation sites's waiting queues + // eom + output.println(" /* set up waiting queues */"); + output.println(" int numRelatedAllocSites=0;"); + ConflictGraph graph=null; + graph=mlpa.getConflictGraphResults().get(fsen); + if (graph != null) { + output.println(" {"); + output.println(" SESEcommon* parentCommon = &(___params___->common);"); + Set allocSet = graph.getAllocationSiteIDSet(); + if (allocSet.size() > 0) { + output.println(" numRelatedAllocSites=" + allocSet.size() + + ";"); + output + .println(" parentCommon->numRelatedAllocSites=numRelatedAllocSites;"); + output + .println(" parentCommon->allocSiteArray=mlpCreateAllocSiteArray(numRelatedAllocSites);"); + int idx = 0; + for (Iterator iterator = allocSet.iterator(); iterator + .hasNext();) { + Long allocID = (Long) iterator.next(); + output.println(" parentCommon->allocSiteArray[" + idx + + "].id=" + allocID + ";"); + idx++; + } + output.println(); + } + output.println(" }"); + } + // copy in-set into place, ready vars were already // copied when the SESE was issued @@ -2146,6 +2178,7 @@ public class BuildCode { exitset.add(seseExit); generateCode(fsen.getNext(0), fm, null, exitset, output, true); output.println("}\n\n"); + } @@ -2675,35 +2708,33 @@ public class BuildCode { ParentChildConflictsMap conflictsMap=mlpa.getConflictsResults().get(fn); if (conflictsMap != null) { - Set allocSet = conflictsMap + Set allocSet = conflictsMap .getAllocationSiteIDSetofStallSite(); if (allocSet.size() > 0) { output.println(" /* stall on parent's stall sites */"); output.println(" {"); - output - .println(" pthread_mutex_lock( &(seseCaller->lock) );"); - + output.println(" pthread_mutex_lock( &(seseCaller->lock) );"); + output.println(" psem_init( &(seseCaller->memoryStallSiteSem) );"); + output.println(" int qIdx;"); + output.println(" int takeCount=0;"); for (Iterator iterator = allocSet.iterator(); iterator .hasNext();) { - Integer allocID = (Integer) iterator.next(); - output - .println(" if(addWaitingQueueElement(seseCaller->allocSiteArray,numRelatedAllocSites," - + allocID + ",seseCaller)!=0){"); - - output - .println(" psem_init( &(seseCaller->memoryStallSiteSem) );"); - output - .println(" psem_take( &(seseCaller->memoryStallSiteSem) );"); - output.println(" }"); + Long allocID = (Long) iterator.next(); + output.println(" qIdx=getQueueIdx(seseCaller->allocSiteArray,numRelatedAllocSites," + + allocID + ");"); + output.println(" if(qIdx!=-1 && !isEmpty(seseCaller->allocSiteArray[qIdx].waitingQueue)){"); + output.println(" addNewItemBack(seseCaller->allocSiteArray[qIdx].waitingQueue,seseCaller);"); + output.println(" takeCount++;"); + output.println(" }"); } - output - .println(" pthread_mutex_unlock( &(seseCaller->lock) );"); + output.println(" pthread_mutex_unlock( &(seseCaller->lock) );"); + output.println(" if( takeCount>0 ){"); + output.println(" psem_take( &(seseCaller->memoryStallSiteSem) );"); + output.println(" }"); output.println(" }"); } - } - } switch(fn.kind()) { @@ -3306,14 +3337,14 @@ public class BuildCode { if(parent.isCallerSESEplaceholder){ graph=mlpa.getConflictGraphResults().get(parent.getfmEnclosing()); }else{ - graph=mlpa.getConflictGraphResults().get(fsen); + graph=mlpa.getConflictGraphResults().get(parent); } } if (graph != null) { output.println(); output.println(" /*add waiting queue element*/"); - Set allocSet = graph.getAllocationSiteIDSetBySESEID(fsen + Set allocSet = graph.getAllocationSiteIDSetBySESEID(fsen .getIdentifier()); if (allocSet.size() > 0) { output.println(" {"); @@ -3322,7 +3353,7 @@ public class BuildCode { for (Iterator iterator = allocSet.iterator(); iterator .hasNext();) { - Integer allocID = (Integer) iterator.next(); + Long allocID = (Long) iterator.next(); output .println(" addWaitingQueueElement(parentCommon->allocSiteArray,numRelatedAllocSites," + allocID @@ -3338,12 +3369,17 @@ public class BuildCode { output.println(" /*decide whether it is runnable or not in regarding to memory conflicts*/"); output.println(" {"); output.println(" int idx;"); + output.println(" pthread_mutex_lock( &(parentCommon->lock) );"); output.println(" for(idx = 0 ; idx < numRelatedAllocSites ; idx++){"); - output.println(" SESEcommon* item=peekItem(seseCaller->allocSiteArray[idx].waitingQueue);"); - output.println(" if(item->classID==seseToIssue->common.classID){"); - output.println(" --(seseToIssue->common.unresolvedDependencies);"); + output.println(" struct Queue *allocQueue=parentCommon->allocSiteArray[idx].waitingQueue;"); + output.println(" if(allocQueue->head!=NULL){"); + output.println(" SESEcommon* item=peekItem(parentCommon->allocSiteArray[idx].waitingQueue);"); + output.println(" if(item->classID==seseToIssue->common.classID){"); + output.println(" --(seseToIssue->common.unresolvedDependencies);"); + output.println(" }"); output.println(" }"); output.println(" }"); + output.println(" pthread_mutex_unlock( &(parentCommon->lock) );"); output.println(" }"); output.println(); } @@ -3546,8 +3582,11 @@ public class BuildCode { output.println(); output.println(" /* check memory dependency*/"); output.println(" {"); + output.println(" pthread_mutex_lock( &(___params___->common.parent->lock) );"); output.println(" int idx;"); + output.println(" int giveCount=0;"); output.println(" for(idx = 0 ; idx < ___params___->common.parent->numRelatedAllocSites ; idx++){"); + output.println(" if(!isEmpty(___params___->common.parent->allocSiteArray[idx].waitingQueue)){"); output.println(" SESEcommon* item=peekItem(___params___->common.parent->allocSiteArray[idx].waitingQueue);"); output.println(" if( item->classID == ___params___->common.classID ){"); output.println(" struct QueueItem* qItem=findItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,item);"); @@ -3557,7 +3596,7 @@ public class BuildCode { output.println(" if(nextItem->classID==___params___->common.parent->classID){"); output.println(" struct QueueItem* stallItem=findItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,nextItem);"); output.println(" removeItem(___params___->common.parent->allocSiteArray[idx].waitingQueue,stallItem);"); - output.println(" psem_give(&(nextItem->memoryStallSiteSem));"); + output.println(" giveCount++;"); output.println(" }else{"); output.println(" pthread_mutex_lock( &(nextItem->lock) );"); output.println(" --(nextItem->unresolvedDependencies);"); @@ -3568,11 +3607,15 @@ public class BuildCode { output.println(" }"); output.println(" }"); output.println(" }"); + output.println(" }"); output.println(" }"); + output.println(" pthread_mutex_unlock( &(___params___->common.parent->lock) );"); + output.println(" if(giveCount>0){"); + output.println(" psem_give(&(___params___->common.parent->memoryStallSiteSem));"); + output.println(" }"); output.println(" }"); } - // if parent is stalling on you, let them know you're done if( fsexn.getFlatEnter() != mlpa.getMainSESE() ) { output.println(" psem_give( &("+paramsprefix+"->common.stallSem) );"); diff --git a/Robust/src/Runtime/mlp_runtime.c b/Robust/src/Runtime/mlp_runtime.c index 2101ce23..beea2f22 100644 --- a/Robust/src/Runtime/mlp_runtime.c +++ b/Robust/src/Runtime/mlp_runtime.c @@ -39,8 +39,8 @@ AllocSite* mlpCreateAllocSiteArray(int numAllocSites){ return newAllocSite; } -void addWaitingQueueElement(AllocSite* allocSiteArray, int numAllocSites, int allocID, void *seseRec){ - +void addWaitingQueueElement(AllocSite* allocSiteArray, int numAllocSites, long allocID, void *seseRec){ + int i; for(i=0;i