From 6bcced9a402a086b7b9a6f3001e5fba4cf88b6dc Mon Sep 17 00:00:00 2001 From: jjenista Date: Tue, 5 Apr 2011 17:40:14 +0000 Subject: [PATCH] at task exit, a task should acquire any out-set variables that arent already it the task record. These could be from static or dynamic sources, so some extra analysis info should be saved to generate the correct copy statements. make sure static and dynamic tracking variables are generated too --- .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 170 ++++++-- .../src/Analysis/OoOJava/VarSrcTokTable.java | 23 +- .../SerialDelaunayRefinement.java | 365 +++++++++--------- Robust/src/Benchmarks/oooJava/master-makefile | 4 +- Robust/src/IR/Flat/BuildOoOJavaCode.java | 79 +++- Robust/src/IR/Flat/FlatSESEEnterNode.java | 69 +++- 6 files changed, 458 insertions(+), 252 deletions(-) diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index b98e8367..14102103 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -16,6 +16,7 @@ public class OoOJavaAnalysis { private State state; private TypeUtil typeUtil; private CallGraph callGraph; + private Liveness liveness; private RBlockRelationAnalysis rblockRel; private HeapAnalysis disjointAnalysisTaints; private DisjointAnalysis disjointAnalysisReach; @@ -98,9 +99,10 @@ public class OoOJavaAnalysis { ArrayReferencees arrayReferencees ) { State.logEvent("Starting OoOJavaAnalysis"); - this.state = state; - this.typeUtil = typeUtil; - this.callGraph = callGraph; + this.state = state; + this.typeUtil = typeUtil; + this.callGraph = callGraph; + this.liveness = liveness; this.maxSESEage = state.OOO_MAXSESEAGE; livenessGlobalView = new Hashtable>(); @@ -152,7 +154,7 @@ public class OoOJavaAnalysis { Iterator seseItr = rblockRel.getLocalRootSESEs().iterator(); while (seseItr.hasNext()) { FlatSESEEnterNode sese = seseItr.next(); - livenessAnalysisBackward(sese,liveness); + livenessAnalysisBackward(sese); } @@ -175,7 +177,7 @@ public class OoOJavaAnalysis { seseItr = rblockRel.getLocalRootSESEs().iterator(); while (seseItr.hasNext()) { FlatSESEEnterNode sese = seseItr.next(); - livenessAnalysisBackward(sese,liveness); + livenessAnalysisBackward(sese); } State.logEvent("OoOJavaAnalysis 4th pass completed"); @@ -249,7 +251,7 @@ public class OoOJavaAnalysis { while (methItr.hasNext()) { Descriptor d = methItr.next(); FlatMethod fm = state.getMethodFlat(d); - codePlansForward(fm,liveness); + codePlansForward(fm); } State.logEvent("OoOJavaAnalysis 12th pass completed"); @@ -332,7 +334,7 @@ public class OoOJavaAnalysis { } - private void livenessAnalysisBackward(FlatSESEEnterNode fsen,Liveness liveness) { + private void livenessAnalysisBackward(FlatSESEEnterNode fsen) { // flow backward across nodes to compute liveness, and // take special care with sese enter/exit nodes that @@ -357,7 +359,7 @@ public class OoOJavaAnalysis { } } - Set curr = liveness_nodeActions( fn, livein, liveness ); + Set curr = liveness_nodeActions( fn, livein ); // if a new result, schedule backward nodes for analysis if( !curr.equals( prev ) ) { @@ -374,7 +376,7 @@ public class OoOJavaAnalysis { } private Set liveness_nodeActions( FlatNode fn, - Set liveIn, Liveness liveness + Set liveIn ) { switch( fn.kind() ) { @@ -403,7 +405,6 @@ public class OoOJavaAnalysis { FlatSESEExitNode fsexn = fsen.getFlatExit(); //note: liveness analysis can have corresponding decisions Set livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn); -// Set livetemps = livenessGlobalView.get( fsexn ); if( livetemps != null && livetemps.contains( writeTemps[i] ) ) { fsen.addOutVar( writeTemps[i] ); } @@ -495,7 +496,9 @@ public class OoOJavaAnalysis { // written by an SESE and should be added to the in-set // anything virtually read by this SESE should be pruned // of parent or sibling sources - Set liveVars = livenessGlobalView.get(fn); + Set liveVars = liveness.getLiveInTemps(fsen.getfmEnclosing(), + fn); + Set fsenVirtReads = vstTable.calcVirtReadsAndPruneParentAndSiblingTokens(fsen, liveVars); @@ -506,6 +509,10 @@ public class OoOJavaAnalysis { } livenessVirtualReads.put(fn, fsenVirtReads); + // virtual reads are forced in-vars! + fsen.addInVarSet( fsenVirtReads ); + + // then all child out-set tokens are guaranteed // to be filled in, so clobber those entries with // the latest, clean sources @@ -765,7 +772,7 @@ public class OoOJavaAnalysis { } - private void codePlansForward(FlatMethod fm, Liveness liveness) { + private void codePlansForward(FlatMethod fm) { // start from flat method top, visit every node in // method exactly once @@ -807,7 +814,7 @@ public class OoOJavaAnalysis { } codePlans_nodeActions(fm, fn, - /*dotSTlive*/liveness, dotSTtable, dotSTnotAvailSet, + dotSTtable, dotSTnotAvailSet, currentSESE); for (int i = 0; i < fn.numNext(); i++) { @@ -822,8 +829,6 @@ public class OoOJavaAnalysis { private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, -// Set liveSetIn, - Liveness liveness, VarSrcTokTable vstTableIn, Set notAvailSetIn, FlatSESEEnterNode currentSESE) { @@ -860,13 +865,14 @@ public class OoOJavaAnalysis { // variable and the child needs space in its SESE record if (srcType.equals(VarSrcTokTable.SrcType_DYNAMIC)) { fsen.addDynamicInVar(inVar); - addDynamicVar( fsen, fm, inVar ); + addDynamicVar( parent, fm, inVar ); } else if (srcType.equals(VarSrcTokTable.SrcType_STATIC)) { fsen.addStaticInVar(inVar); VariableSourceToken vst = vstIfStatic.vst; fsen.putStaticInVar2src(inVar, vst); fsen.addStaticInVarSrc(new SESEandAgePair(vst.getSESE(), vst.getAge())); + } else { assert srcType.equals(VarSrcTokTable.SrcType_READY); fsen.addReadyInVar(inVar); @@ -876,11 +882,40 @@ public class OoOJavaAnalysis { case FKind.FlatSESEExitNode: { FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - //TODO! Shouldn't there be a code plan for task exit - // where the exiting task calculates whether its own - // siblings need variables from its children, so the - // exiter should copy those variables into its own out-set - // and make the available? + + // Classify the sources of out-set variables so code + // gen can acquire them from children if necessary + // before this task exits + FlatSESEEnterNode exiter = fsexn.getFlatEnter(); + + Iterator outVarItr = exiter.getOutVarSet().iterator(); + while( outVarItr.hasNext() ) { + TempDescriptor outVar = outVarItr.next(); + + VSTWrapper vstIfStatic = new VSTWrapper(); + Integer srcType = vstTableIn.getRefVarSrcType( outVar, + exiter, + vstIfStatic + ); + + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + // if the out-var is dynamic, put it in the set of dyn out vars + // so exiting code gen knows to look for the value, but also put + // it in the set of dynamic vars the exiter must track! + exiter.addDynamicOutVar( outVar ); + addDynamicVar( exiter, fm, outVar ); + + } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { + exiter.addStaticOutVar( outVar ); + VariableSourceToken vst = vstIfStatic.vst; + exiter.putStaticOutVar2src( outVar, vst ); + exiter.addStaticOutVarSrc( new SESEandAgePair( vst.getSESE(), vst.getAge() ) ); + + } else { + assert srcType.equals( VarSrcTokTable.SrcType_READY ); + exiter.addReadyOutVar( outVar ); + } + } } break; case FKind.FlatOpNode: { @@ -970,12 +1005,9 @@ public class OoOJavaAnalysis { while (refVarItr.hasNext()) { TempDescriptor refVar = refVarItr.next(); //note: this should just use normal liveness in...only want to copy live variables... -// if (liveSetIn.contains(refVar)) { -// copySet.add(refVar); -// } - if(liveness.getLiveInTemps(fm, fn).contains(refVar)){ - copySet.add(refVar); - } + if(liveness.getLiveInTemps(fm, fn).contains(refVar)){ + copySet.add(refVar); + } } if (!copySet.isEmpty()) { @@ -1026,16 +1058,48 @@ public class OoOJavaAnalysis { codePlans.put(fn, plan); - // if any variables at this-node-*dot* have a static source (exactly one - // vst) + + + + // if any variables at this-node-*dot* have a static source (exactly one vst) // but go to a dynamic source at next-node-*dot*, create a new IR graph // node on that edge to track the sources dynamically + // NOTE: for this calculation use the currentSESE variable, except when the + // FlatNode fn is an Exit--in that case currentSESE is for the exiting task, + // be we want to consider that the parent is tracking a variable coming out + // of the exiting task + FlatSESEEnterNode fsenDoingTracking; + if( fn instanceof FlatSESEExitNode ) { + fsenDoingTracking = currentSESE.getLocalParent(); + + if( fsenDoingTracking == null ) { + // if there is no local parent, there are one of two cases + // 1) the current task is main, in which case this FlatNode + // is the main's exit, and doesn't need to do any of the + // following dynamic tracking + // 2) the current task is defined in a method, so use the + // caller proxy in the variable source calcs below + if( currentSESE.equals( rblockRel.getMainSESE() ) ) { + return; + } else { + fsenDoingTracking = rblockRel.getCallerProxySESE(); + } + } + } else { + fsenDoingTracking = currentSESE; + } + + + if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) { + System.out.println( "\n\nWriteDyn for "+fsenDoingTracking+" at "+fn ); + } + + VarSrcTokTable thisVstTable = variableResults.get(fn); for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); VarSrcTokTable nextVstTable = variableResults.get(nn); // note: using the result of liveness analysis regardless of task structures - // Set nextLiveIn = livenessGlobalView.get(nn); Set nextLiveIn=liveness.getLiveInTemps(fm, nn); // the table can be null if it is one of the few IR nodes @@ -1043,17 +1107,24 @@ public class OoOJavaAnalysis { if (nextVstTable != null && nextLiveIn != null) { Hashtable readyOrStatic2dynamicSet = - thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, currentSESE); + thisVstTable.getReadyOrStatic2DynamicSet(nextVstTable, nextLiveIn, fsenDoingTracking); if (!readyOrStatic2dynamicSet.isEmpty()) { + + + if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) { + System.out.println( " found newly dyn vars: "+readyOrStatic2dynamicSet ); + } + + // either add these results to partial fixed-point result // or make a new one if we haven't made any here yet FlatEdge fe = new FlatEdge(fn, nn); FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get(fe); if (fwdvn == null) { - fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, currentSESE); + fwdvn = new FlatWriteDynamicVarNode(fn, nn, readyOrStatic2dynamicSet, fsenDoingTracking); wdvNodesToSpliceIn.put(fe, fwdvn); } else { fwdvn.addMoreVar2Src(readyOrStatic2dynamicSet); @@ -1061,6 +1132,10 @@ public class OoOJavaAnalysis { } } } + + if( fsenDoingTracking.getPrettyIdentifier().equals( "workLoop" ) ) { + System.out.println( "WriteDyn for "+fsenDoingTracking+" at "+fn+" is done\n\n" ); + } } private void addDynamicVar( FlatSESEEnterNode fsen, @@ -1070,15 +1145,15 @@ public class OoOJavaAnalysis { // note: dynamic variable declarations are always located in the flat method that encloses task block // there is no need to set fnContext to fsen -// if( fsen.getIsCallerProxySESE() ) { -// // attach the dynamic variable to track to -// // the flat method, so it can be declared at entry -// fnContext = fm; -// } else { -// // otherwise the code context is a task body -// fnContext = fsen; -// } - fnContext=fm; + if( fsen.getIsCallerProxySESE() ) { + // attach the dynamic variable to track to + // the flat method, so it can be declared at entry + fnContext = fm; + } else { + // otherwise the code context is a task body + fnContext = fsen; + } + //fnContext=fm; ContextTaskNames ctn = fn2contextTaskNames.get( fnContext ); if( ctn == null ) { @@ -1721,6 +1796,19 @@ public class OoOJavaAnalysis { bw.write(" Dynamic vars to manage: " + getContextTaskNames( fsen ).getDynamicVarSet() + "\n"); bw.write(" out-set: " + fsen.getOutVarSet() + "\n"); + tItr = fsen.getOutVarSet().iterator(); + while (tItr.hasNext()) { + TempDescriptor outVar = tItr.next(); + if (fsen.getReadyOutVarSet().contains(outVar)) { + bw.write(" (ready) " + outVar + "\n"); + } + if (fsen.getStaticOutVarSet().contains(outVar)) { + bw.write(" (static) " + outVar + " from " + fsen.getStaticOutVarSrc(outVar) + "\n"); + } + if (fsen.getDynamicOutVarSet().contains(outVar)) { + bw.write(" (dynamic)" + outVar + "\n"); + } + } bw.write(" local parent: " + fsen.getLocalParent() + "\n"); bw.write(" local children: " + fsen.getLocalChildren() + "\n"); diff --git a/Robust/src/Analysis/OoOJava/VarSrcTokTable.java b/Robust/src/Analysis/OoOJava/VarSrcTokTable.java index c51517ff..c799ca64 100644 --- a/Robust/src/Analysis/OoOJava/VarSrcTokTable.java +++ b/Robust/src/Analysis/OoOJava/VarSrcTokTable.java @@ -385,23 +385,25 @@ public class VarSrcTokTable { public void remapChildTokens( FlatSESEEnterNode curr ) { Iterator childItr = curr.getLocalChildren().iterator(); - if( childItr.hasNext() ) { + while( childItr.hasNext() ) { FlatSESEEnterNode child = childItr.next(); // set of VSTs for removal HashSet removalSet=new HashSet(); // set of VSTs for additon HashSet additionSet=new HashSet(); - + Iterator vstItr = get( child ).iterator(); while( vstItr.hasNext() ) { VariableSourceToken vst = vstItr.next(); removalSet.add(vst); - additionSet.add(new VariableSourceToken( vst.getRefVars(), - curr, - new Integer( 0 ), - vst.getAddrVar() - )); + + additionSet.add( new VariableSourceToken( vst.getRefVars(), + curr, + new Integer( 0 ), + vst.getAddrVar() + ) + ); } // remove( eah item in forremoval ) @@ -466,8 +468,6 @@ public class VarSrcTokTable { alternateSESEs.add( sibling ); } } - - // VSTs to remove if they are alternate sources for exiter VSTs // whose variables will become virtual reads @@ -512,8 +512,9 @@ public class VarSrcTokTable { forRemoval.add( vstPossibleOtherSrc ); } else { - if( !vstPossibleOtherSrc.getSESE().equals( exiter ) || - !vstPossibleOtherSrc.getAge().equals( 0 ) + if( !(vstPossibleOtherSrc.getSESE().equals( exiter ) && + vstPossibleOtherSrc.getAge().equals( 0 ) + ) ) { System.out.println( "For refVar="+refVar+" at exit of "+exiter+ ", unexpected possible variable source "+vstPossibleOtherSrc ); diff --git a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java index c4cb1d6a..5f2672df 100644 --- a/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java +++ b/Robust/src/Benchmarks/oooJava/DelaunayRefinement/SerialDelaunayRefinement.java @@ -100,247 +100,256 @@ public class SerialDelaunayRefinement { System.out.println( "done gc" ); - Node [] nodesForBadTris = new Node [numWorkers]; - Cavity[] cavities = new Cavity[numWorkers]; - Cavity lastAppliedCavity = null; + //int zzz = 0; - int zzz = 0; + long startTime = System.currentTimeMillis(); - long startTime = System.currentTimeMillis(); - while (!worklist.isEmpty()) { - - // Phase 1, grab enough work from list for - // each worker in the parent - for(int i=0;i itr = fsen.getOutVarSet().iterator(); + + //////////////////////////////////////// + // go through all out-vars and determine where to get them + //////////////////////////////////////// + output.println(" // copy ready out-set primitive variables from locals into record"); + Iterator itr = fsen.getReadyOutVarSet().iterator(); while( itr.hasNext() ) { TempDescriptor temp = itr.next(); - // only have to do this for primitives non-arrays + // only have to do this for primitives, non-arrays if( !( temp.getType().isPrimitive() && !temp.getType().isArray() - ) - ) { + ) + ) { continue; } - String from; - - // determine whether this new task instance is in a method context, - // or within the body of another task - assert !fsen.getIsCallerProxySESE(); - FlatSESEEnterNode parent = fsen.getLocalParent(); - if( parent != null && !parent.getIsCallerProxySESE() ) { - from = generateTemp( parent.getfmBogus(), temp ); - } else { - from = generateTemp( fsen.getfmEnclosing(), temp ); - } + String from = generateTemp( fsen.getfmBogus(), temp ); output.println(" "+paramsprefix+ "->"+temp.getSafeSymbol()+ " = "+from+";"); - } + } + + // static vars are from a known SESE + Iterator tempItr; + output.println(" // copy out-set from static sources"); + tempItr = fsen.getStaticOutVarSet().iterator(); + while( tempItr.hasNext() ) { + TempDescriptor temp = tempItr.next(); + VariableSourceToken vst = fsen.getStaticOutVarSrc( temp ); + SESEandAgePair srcPair = new SESEandAgePair( vst.getSESE(), vst.getAge() ); + output.println(" "+paramsprefix+ + "->"+temp.getSafeSymbol()+ + " = "+paramsprefix+"->"+srcPair+"->"+vst.getAddrVar()+";"); + } + + //output.println(" // decrement references to static sources"); + //for( Iterator pairItr = fsen.getStaticOutVarSrcs().iterator(); pairItr.hasNext(); ) { + // SESEandAgePair srcPair = pairItr.next(); + // output.println("#ifndef OOO_DISABLE_TASKMEMPOOL" ); + // output.println(" {"); + // output.println(" SESEcommon* src = &("+paramsprefix+"->"+srcPair+"->common);"); + // output.println(" RELEASE_REFERENCE_TO( src );"); + // output.println(" }"); + // output.println("#endif // OOO_DISABLE_TASKMEMPOOL" ); + //} + + output.println(" // copy out-set from dynamic sources"); + tempItr = fsen.getDynamicOutVarSet().iterator(); + while( tempItr.hasNext() ) { + TempDescriptor temp = tempItr.next(); + TypeDescriptor type = temp.getType(); + + // go grab it from the SESE source, when the source is NULL it is + // this exiting task, so nothing to do! + output.println(" if( "+temp+"_srcSESE != NULL ) {"); + + output.println(" "+paramsprefix+ + "->"+temp.getSafeSymbol()+ + " = (void*)"+ + temp+"_srcSESE + "+ + temp+"_srcOffset;"); + + //output.println("#ifndef OOO_DISABLE_TASKMEMPOOL" ); + //output.println(" SESEcommon* src = "+paramsprefix+"->"+temp+"_srcSESE;"); + //output.println(" RELEASE_REFERENCE_TO( src );"); + //output.println("#endif // OOO_DISABLE_TASKMEMPOOL" ); + + output.println(" }"); + } + + + // mark yourself done, your task data is now read-only output.println(" runningSESE->doneExecuting = TRUE;"); diff --git a/Robust/src/IR/Flat/FlatSESEEnterNode.java b/Robust/src/IR/Flat/FlatSESEEnterNode.java index a4fc7753..688f23d1 100644 --- a/Robust/src/IR/Flat/FlatSESEEnterNode.java +++ b/Robust/src/IR/Flat/FlatSESEEnterNode.java @@ -56,14 +56,27 @@ public class FlatSESEEnterNode extends FlatNode { protected Set inVars; protected Set outVars; + + // for in-vars, classify them by source type to drive + // code gen for issuing this task protected Set readyInVars; protected Set staticInVars; protected Set dynamicInVars; - protected Set staticInVarSrcs; - protected Hashtable staticInVar2src; + // for out-vars, classify them by source type to drive + // code gen for when this task exits: if the exiting task + // has to assume the values from any of its children, it needs + // to know how to acquire those values before it can truly exit + protected Set readyOutVars; + protected Set staticOutVars; + protected Set dynamicOutVars; + protected Set staticOutVarSrcs; + protected Hashtable staticOutVar2src; + + + // get the oldest age of this task that other contexts // have a static name for when tracking variables protected Integer oldestAgeToTrack; @@ -106,9 +119,14 @@ public class FlatSESEEnterNode extends FlatNode { staticInVars = new HashSet(); dynamicInVars = new HashSet(); staticInVarSrcs = new HashSet(); + readyOutVars = new HashSet(); + staticOutVars = new HashSet(); + dynamicOutVars = new HashSet(); + staticOutVarSrcs = new HashSet(); oldestAgeToTrack = new Integer( 0 ); - staticInVar2src = new Hashtable(); + staticInVar2src = new Hashtable(); + staticOutVar2src = new Hashtable(); inVarsForDynamicCoarseConflictResolution = new Vector(); @@ -346,6 +364,51 @@ public class FlatSESEEnterNode extends FlatNode { } + + public void addReadyOutVar( TempDescriptor td ) { + readyOutVars.add( td ); + } + + public Set getReadyOutVarSet() { + return readyOutVars; + } + + public void addStaticOutVarSrc( SESEandAgePair p ) { + staticOutVarSrcs.add( p ); + } + + public Set getStaticOutVarSrcs() { + return staticOutVarSrcs; + } + + public void addStaticOutVar( TempDescriptor td ) { + staticOutVars.add( td ); + } + + public Set getStaticOutVarSet() { + return staticOutVars; + } + + public void putStaticOutVar2src( TempDescriptor staticOutVar, + VariableSourceToken vst ) { + staticOutVar2src.put( staticOutVar, vst ); + } + + public VariableSourceToken getStaticOutVarSrc( TempDescriptor staticOutVar ) { + return staticOutVar2src.get( staticOutVar ); + } + + public void addDynamicOutVar( TempDescriptor td ) { + dynamicOutVars.add( td ); + } + + public Set getDynamicOutVarSet() { + return dynamicOutVars; + } + + + + public void setfmEnclosing( FlatMethod fm ) { fmEnclosing = fm; } public FlatMethod getfmEnclosing() { return fmEnclosing; } -- 2.34.1