From ff0c37092456be2f3b523818d4ec1d2b285c3762 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 13 Nov 2010 06:11:43 +0000 Subject: [PATCH] BuildCode.java: removes (1) the calls to build a traverser thread (2) the calls to enqueueTR when SESE only has empty traversers. FlatSESEEnterNode.java CallGraph.java, RblockRelationAnalysis.java: maintains additional DS having a set of SESE that is the first reachable SESE from the current SESE through transitive method invocations RuntimeConflictResolver.java : add helper function that checks if the given SESE only has empty traversers. --- Robust/src/Analysis/CallGraph/CallGraph.java | 29 ++++++ .../OoOJava/RBlockRelationAnalysis.java | 95 +++++++++++++------ Robust/src/IR/Flat/BuildCode.java | 40 ++++---- Robust/src/IR/Flat/FlatSESEEnterNode.java | 17 +++- .../src/IR/Flat/RuntimeConflictResolver.java | 12 +++ 5 files changed, 140 insertions(+), 53 deletions(-) diff --git a/Robust/src/Analysis/CallGraph/CallGraph.java b/Robust/src/Analysis/CallGraph/CallGraph.java index 3573cd56..e69578ff 100644 --- a/Robust/src/Analysis/CallGraph/CallGraph.java +++ b/Robust/src/Analysis/CallGraph/CallGraph.java @@ -166,6 +166,35 @@ public class CallGraph { } return callable; } + + // Returns a set of methods containing SESEs and located at the first + // in transitive call chain starting from d + public Set getFirstReachableMethodContainingSESE(Descriptor d, + Set methodsContainingSESEs) { + HashSet tovisit = new HashSet(); + tovisit.add(d); + HashSet callable = new HashSet(); + while (!tovisit.isEmpty()) { + Descriptor md = (Descriptor) tovisit.iterator().next(); + tovisit.remove(md); + Set s = (Set) mapCaller2CalleeSet.get(md); + if (s != null) { + for (Iterator it = s.iterator(); it.hasNext();) { + MethodDescriptor md2 = (MethodDescriptor) it.next(); + if (!callable.contains(md2)) { + callable.add(md2); + if (!methodsContainingSESEs.contains(md2)) { + // if current method has sese, do not need to go down + tovisit.add(md2); + } + } + } + } + } + callable.retainAll(methodsContainingSESEs); + return callable; + } + private void buildGraph() { Iterator it=state.getClassSymbolTable().getDescriptorsIterator(); diff --git a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java index 834fcee5..694083fc 100644 --- a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java +++ b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java @@ -43,8 +43,11 @@ public class RBlockRelationAnalysis { // to support calculation of leaf SESEs (no children even // through method calls) for optimization during code gen protected Set methodsContainingSESEs; - - + + // maps method descriptor to SESE defined inside of it + // only contains top-level SESE definition in corresponding method + protected Hashtable> md2seseSet; + public RBlockRelationAnalysis( State state, TypeUtil typeUtil, CallGraph callGraph ) { @@ -59,6 +62,8 @@ public class RBlockRelationAnalysis { fm2relmap = new Hashtable< FlatMethod, Hashtable< FlatNode, Stack > >(); + + md2seseSet = new Hashtable>(); MethodDescriptor mdSourceEntry = typeUtil.getMain(); @@ -68,7 +73,7 @@ public class RBlockRelationAnalysis { mainSESE.setfmEnclosing( fmMain ); mainSESE.setmdEnclosing( fmMain.getMethod() ); mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() ); - + // add all methods transitively reachable from the // source's main to set for analysis Set descriptorsToAnalyze = @@ -176,7 +181,16 @@ public class RBlockRelationAnalysis { fsen.setfmEnclosing( fm ); fsen.setmdEnclosing( fm.getMethod() ); fsen.setcdEnclosing( fm.getMethod().getClassDesc() ); - + + if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()==null ){ + Set seseSet=md2seseSet.get(fm.getMethod()); + if(seseSet==null){ + seseSet=new HashSet(); + } + seseSet.add(fsen); + md2seseSet.put(fm.getMethod(), seseSet); + } + if( seseStack.empty() ) { rootSESEs.add( fsen ); fsen.setParent( null ); @@ -223,52 +237,71 @@ public class RBlockRelationAnalysis { } - protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) { + protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) { + + boolean hasChildrenByCall=false; // visit every flat node in SESE body, find method calls that // may transitively call methods with SESEs enclosed Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fsen ); - - Set visited = new HashSet(); + flatNodesToVisit.add(fsen); - while( !flatNodesToVisit.isEmpty() ) { + Set visited = new HashSet(); + + while (!flatNodesToVisit.isEmpty()) { Iterator fnItr = flatNodesToVisit.iterator(); FlatNode fn = fnItr.next(); - flatNodesToVisit.remove( fn ); - visited.add( fn ); + flatNodesToVisit.remove(fn); + visited.add(fn); - if( fn.kind() == FKind.FlatCall ) { - FlatCall fc = (FlatCall) fn; - MethodDescriptor mdCallee = fc.getMethod(); - Set reachable = new HashSet(); + if (fn.kind() == FKind.FlatCall) { + FlatCall fc = (FlatCall) fn; + MethodDescriptor mdCallee = fc.getMethod(); + Set reachable = new HashSet(); - reachable.add( mdCallee ); - reachable.addAll( callGraph.getAllMethods( mdCallee ) ); + reachable.add(mdCallee); + reachable.addAll(callGraph.getAllMethods(mdCallee)); + + reachable.retainAll(methodsContainingSESEs); + + if (!reachable.isEmpty()) { + hasChildrenByCall = true; + + Set reachableSESEMethodSet = + callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs); + + if (methodsContainingSESEs.contains(mdCallee)) { + reachableSESEMethodSet.add(mdCallee); + } + + for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + Set seseSet = md2seseSet.get(md); + if (seseSet != null) { + fsen.addSESEChildren(seseSet); + } + } - reachable.retainAll( methodsContainingSESEs ); - - if( !reachable.isEmpty() ) { - return true; } } - if( fn == fsen.getFlatExit() ) { + if (fn == fsen.getFlatExit()) { // don't enqueue any futher nodes continue; } - - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - - if( !visited.contains( nn ) ) { - flatNodesToVisit.add( nn ); - } + + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + + if (!visited.contains(nn)) { + flatNodesToVisit.add(nn); + } } - } + } - return false; + return hasChildrenByCall; } + } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 8295f212..cb507c0b 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -2564,9 +2564,9 @@ public class BuildCode { if( !fsen.getIsLeafSESE() ) { output.println(" runningSESE->taskRecordMemPool = poolcreate( "+ maxTaskRecSizeStr+", freshTaskRecordInitializer );"); - if (state.RCR) { - output.println(" createTR();"); - output.println(" runningSESE->allHashStructures=TRqueue->allHashStructures;"); + if (state.RCR && !rcr.hasEmptyTraversers(fsen)) { + output.println(" createTR();"); + output.println(" runningSESE->allHashStructures=TRqueue->allHashStructures;"); } } else { // make it clear we purposefully did not initialize this @@ -3161,7 +3161,7 @@ public class BuildCode { + generateTemp(fm, stalltd, null) + ";"); output.println(" stallrecord->common.classID=-" + rcr.getTraverserID(stalltd, fn) + ";"); - + output.println(" enqueueTR(TRqueue, (void *)stallrecord);"); if (state.COREPROF) { @@ -4274,7 +4274,7 @@ public class BuildCode { //////////////// // count up memory conflict dependencies, if(state.RCR) { - dispatchMEMRC(fm, lb, fsen, output); + dispatchMEMRC(fm, lb, fsen, output); } else if(state.OOOJAVA){ FlatSESEEnterNode parent = fsen.getParent(); Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(parent); @@ -4506,7 +4506,7 @@ public class BuildCode { // Enqueue Task Record if (state.RCR) { - if( fsen != oooa.getMainSESE() ){ + if( fsen != oooa.getMainSESE() && fsen.getInVarsForDynamicCoarseConflictResolution().size()>0){ output.println(" enqueueTR(TRqueue, (void *)seseToIssue);"); } } @@ -4774,25 +4774,23 @@ public class BuildCode { output.println("{"); output.println(" int idx,idx2;"); - //NEED TO FIX THIS - //XXXXXXXXX output.println(" struct rcrRecord *rec;"); - output.println(" struct Hashtable_rcr ** hashstruct=runningSESE->parent->allHashStructures;"); + output + .println(" struct Hashtable_rcr ** hashstruct=runningSESE->parent->allHashStructures;"); - for(int i=0;ircrRecords["+i+"];"); - output.println(" while(rec!=NULL) {"); - output.println(" for(idx2=0;idx2index;idx2++) {"); + for (int i = 0; i < inset.size(); i++) { + output.println(" rec=&" + paramsprefix + "->rcrRecords[" + i + "];"); + output.println(" while(rec!=NULL) {"); + output.println(" for(idx2=0;idx2index;idx2++) {"); - int weaklyConnectedComponentIndex = rcr.getWeakID(inset.get(i),fsen); + int weaklyConnectedComponentIndex = rcr.getWeakID(inset.get(i), fsen); - output.println(" rcr_RETIREHASHTABLE(hashstruct["+ - weaklyConnectedComponentIndex+ - "],&(___params___->common), rec->array[idx2], (BinItem_rcr *) rec->ptrarray[idx2]);"); + output.println(" rcr_RETIREHASHTABLE(hashstruct[" + weaklyConnectedComponentIndex + + "],&(___params___->common), rec->array[idx2], (BinItem_rcr *) rec->ptrarray[idx2]);"); - output.println(" }");// exit idx2 for loop - output.println(" rec=rec->next;"); - output.println(" }");// exit rec while loop + output.println(" }");// exit idx2 for loop + output.println(" rec=rec->next;"); + output.println(" }");// exit rec while loop } output.println("}"); } @@ -4821,7 +4819,7 @@ public class BuildCode { // destroy this task's mempool if it is not a leaf task if( !fsen.getIsLeafSESE() ) { output.println(" pooldestroy( runningSESE->taskRecordMemPool );"); - if (state.RCR) { + if (state.RCR && fsen.getInVarsForDynamicCoarseConflictResolution().size() > 0 ) { output.println(" returnTR();"); } } diff --git a/Robust/src/IR/Flat/FlatSESEEnterNode.java b/Robust/src/IR/Flat/FlatSESEEnterNode.java index 90731b34..c77a5cfe 100644 --- a/Robust/src/IR/Flat/FlatSESEEnterNode.java +++ b/Robust/src/IR/Flat/FlatSESEEnterNode.java @@ -75,7 +75,10 @@ public class FlatSESEEnterNode extends FlatNode { // records which is relevant to garbage collection protected String firstDepRecField; protected int numDepRecs; - + + // a set of sese located at the first in transitive call chain + // starting from the current sese + protected Set seseChildren; public FlatSESEEnterNode( SESENode sn ) { this.id = identifier++; @@ -92,6 +95,7 @@ public class FlatSESEEnterNode extends FlatNode { staticInVars = new HashSet(); dynamicInVars = new HashSet(); dynamicVars = new HashSet(); + seseChildren = new HashSet(); inVarsForDynamicCoarseConflictResolution = new Vector(); @@ -350,6 +354,17 @@ public class FlatSESEEnterNode extends FlatNode { return isCallerSESEplaceholder; } + public void addSESEChildren(FlatSESEEnterNode child){ + seseChildren.add(child); + } + + public void addSESEChildren(Set children){ + seseChildren.addAll(children); + } + + public Set getSESEChildren(){ + return seseChildren; + } public boolean equals( Object o ) { if( o == null ) { diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index 6393b3fd..10badb46 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -909,6 +909,18 @@ public class RuntimeConflictResolver { return null; } + // decide whether the given SESE doesn't have traversers at all + public boolean hasEmptyTraversers(FlatSESEEnterNode fsen) { + boolean hasEmpty = true; + + Set children = fsen.getSESEChildren(); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + FlatSESEEnterNode child = (FlatSESEEnterNode) iterator.next(); + hasEmpty &= child.getInVarsForDynamicCoarseConflictResolution().size() == 0; + } + return hasEmpty; + + } private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var, Hashtable> effects) { -- 2.34.1