From 93b24ee2492a6173b3456dfe69d495effc64503b Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 5 Aug 2009 00:12:39 +0000 Subject: [PATCH] big update for forwarding lists and dependency counts, stable compile but seg faults --- Robust/src/Analysis/MLP/MLPAnalysis.java | 71 ++++++++--- Robust/src/Analysis/MLP/SESEandAgePair.java | 6 +- Robust/src/Analysis/MLP/VarSrcTokTable.java | 35 +++++- Robust/src/IR/Flat/BuildCode.java | 124 ++++++++++++++++---- Robust/src/IR/Flat/FlatSESEEnterNode.java | 58 ++++----- Robust/src/Runtime/mlp_runtime.c | 15 +-- Robust/src/Runtime/mlp_runtime.h | 17 ++- Robust/src/Tests/mlp/tinyTest/test.java | 24 +--- 8 files changed, 246 insertions(+), 104 deletions(-) diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 752de79a..82cd89a6 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -27,7 +27,7 @@ public class MLPAnalysis { private Hashtable< FlatNode, Set > notAvailableResults; private Hashtable< FlatNode, CodePlan > codePlans; - private static int maxSESEage = -1; + public static int maxSESEage = -1; // use these methods in BuildCode to have access to analysis results @@ -144,10 +144,10 @@ public class MLPAnalysis { System.out.println( "" ); //System.out.println( "\nSESE Hierarchy\n--------------\n" ); printSESEHierarchy(); //System.out.println( "\nSESE Liveness\n-------------\n" ); printSESELiveness(); - System.out.println( "\nLiveness Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) ); - System.out.println( "\nVariable Results\n----------------\n"+fmMain.printMethod( variableResults ) ); + //System.out.println( "\nLiveness Root View\n------------------\n"+fmMain.printMethod( livenessRootView ) ); + //System.out.println( "\nVariable Results\n----------------\n"+fmMain.printMethod( variableResults ) ); //System.out.println( "\nNot Available Results\n---------------------\n"+fmMain.printMethod( notAvailableResults ) ); - System.out.println( "\nCode Plans\n----------\n"+fmMain.printMethod( codePlans ) ); + //System.out.println( "\nCode Plans\n----------\n"+fmMain.printMethod( codePlans ) ); } @@ -770,6 +770,36 @@ public class MLPAnalysis { case FKind.FlatSESEEnterNode: { FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; + + // don't bother for the root SESE, there are no + // tokens for its in-set + if( fsen == rootSESE ) { + break; + } + + // track the source types of the in-var set so generated + // code at this SESE issue can compute the number of + // dependencies properly + Iterator inVarItr = fsen.getInVarSet().iterator(); + while( inVarItr.hasNext() ) { + TempDescriptor inVar = inVarItr.next(); + Integer srcType = vstTable.getRefVarSrcType( inVar, currentSESE ); + + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + //fsen.addDynamicInVar( inVar ); + + } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { + VariableSourceToken vst = vstTable.get( inVar ).iterator().next(); + fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(), + vst.getAge() + ) + ); + + } else { + assert srcType.equals( VarSrcTokTable.SrcType_READY ); + } + } + } break; case FKind.FlatSESEExitNode: { @@ -813,31 +843,28 @@ public class MLPAnalysis { continue; } - // Two cases: - Set srcs = vstTable.get( readtmp ); - assert !srcs.isEmpty(); - - // 1) Multiple token/age pairs or unknown age: Stall for - // dynamic name only. - if( srcs.size() > 1 || - srcs.iterator().next().getAge() == maxSESEage ) { + // check the source type of this variable + Integer srcType = vstTable.getRefVarSrcType( readtmp, + currentSESE.getParent() ); + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { // identify that this is a stall, and allocate an integer // pointer in the generated code that keeps a pointer to // the source SESE and the address of where to get this thing // --then the stall is just wait for that, and copy the // one thing because we're not sure if we can copy other stuff - + // NEEDS WORK! + } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { + + // 2) Single token/age pair: Stall for token/age pair, and copy + // all live variables with same token/age pair at the same + // time. This is the same stuff that the notavaialable analysis + // marks as now available. - // 2) Single token/age pair: Stall for token/age pair, and copy - // all live variables with same token/age pair at the same - // time. This is the same stuff that the notavaialable analysis - // marks as now available. - } else { - VariableSourceToken vst = srcs.iterator().next(); + VariableSourceToken vst = vstTable.get( readtmp ).iterator().next(); Iterator availItr = vstTable.get( vst.getSESE(), vst.getAge() ).iterator(); @@ -860,6 +887,12 @@ public class MLPAnalysis { plan.addStall2CopySet( vstAlsoAvail, copySet ); } } + + } else { + // the other case for srcs is READY from a parent, however + // since we are only examining variables that come from + // children tokens, this should never occur + assert false; } // assert that everything being stalled for is in the diff --git a/Robust/src/Analysis/MLP/SESEandAgePair.java b/Robust/src/Analysis/MLP/SESEandAgePair.java index bbeca275..d82a3c41 100644 --- a/Robust/src/Analysis/MLP/SESEandAgePair.java +++ b/Robust/src/Analysis/MLP/SESEandAgePair.java @@ -45,6 +45,10 @@ public class SESEandAgePair { public String toString() { - return "SESE_"+sese.getPrettyIdentifier()+"_"+age; + return "SESE_"+ + sese.getPrettyIdentifier()+ + sese.getIdentifier()+ + "_"+ + age; } } diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java index 0f118c74..b2417acb 100644 --- a/Robust/src/Analysis/MLP/VarSrcTokTable.java +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -28,7 +28,11 @@ public class VarSrcTokTable { private Hashtable< SVKey, Set > sv2vst; // maximum age from aging operation - private Integer MAX_AGE = new Integer( 2 ); + private static final Integer MAX_AGE = new Integer( 2 ); + + public static final Integer SrcType_READY = new Integer( 34 ); + public static final Integer SrcType_STATIC = new Integer( 35 ); + public static final Integer SrcType_DYNAMIC = new Integer( 36 ); public VarSrcTokTable() { @@ -482,6 +486,34 @@ public class VarSrcTokTable { } + // for some reference variable, return the type of source + // it might have in this table, which might be: + // 1. Ready -- this variable comes from your parent and is + // definitely available when you are issued. + // 2. Static -- there is definitely one SESE that will + // produce the value for this variable + // 3. Dynamic -- we don't know where the value will come + // from, so we'll track it dynamically + public Integer getRefVarSrcType( TempDescriptor refVar, + FlatSESEEnterNode parent ) { + assert refVar != null; + + Set srcs = get( refVar ); + assert !srcs.isEmpty(); + + if( srcs.size() > 1 || + srcs.iterator().next().getAge() == MLPAnalysis.maxSESEage ) { + return SrcType_DYNAMIC; + } + + if( srcs.iterator().next().getSESE() == parent ) { + return SrcType_READY; + } + + return SrcType_STATIC; + } + + // use as an aid for debugging, where true-set is checked // against the alternate mappings: assert that nothing is // missing or extra in the alternates @@ -616,7 +648,6 @@ public class VarSrcTokTable { } public String toString() { - //return "trueSet ="+trueSet.toString(); return toStringPretty(); } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 1efb476a..a7dc6644 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -1709,6 +1709,8 @@ public class BuildCode { TypeDescriptor type = temp.getType(); if( type.isPtr() ) { objectparams.addPtr( temp ); + } else { + objectparams.addPrim( temp ); } } @@ -1865,12 +1867,24 @@ public class BuildCode { output.println(" void* "+p+";"); } - // copy in-set into place + // declare local temps for in-set primitives Iterator itrInSet = fsen.getInVarSet().iterator(); + while( itrInSet.hasNext() ) { + TempDescriptor temp = itrInSet.next(); + TypeDescriptor type = temp.getType(); + if( !type.isPtr() ) { + output.println(" "+type+" "+temp+";"); + } + } + + // copy in-set into place + itrInSet = fsen.getInVarSet().iterator(); while( itrInSet.hasNext() ) { TempDescriptor temp = itrInSet.next(); TypeDescriptor type = temp.getType(); + // TODO !! make a deep copy of objects ! + if( type.isPtr() ) { output.println(" memcpy( "+ "(void*) &("+paramsprefix+"->"+temp.getSafeSymbol()+"), "+ // to @@ -1881,14 +1895,7 @@ public class BuildCode { "(void*) &("+temp.getSafeSymbol()+"), "+ // to "(void*) ("+paramsprefix+"->"+temp.getSafeSymbol()+"__srcAddr_),"+ // from " sizeof( "+paramsprefix+"->"+temp.getSafeSymbol()+" ) );"); // size - } - - // make a deep copy of objects - //if( type.isPtr() ) { - // deep copy - //} else { - // shallow copy - //} + } } // Check to see if we need to do a GC if this is a @@ -1902,6 +1909,9 @@ public class BuildCode { HashSet exitset=new HashSet(); exitset.add(seseExit); + + + generateCode(fsen.getNext(0), fm, null, exitset, output, true); output.println("}\n\n"); @@ -2693,15 +2703,24 @@ public class BuildCode { } } - public void generateFlatSESEEnterNode(FlatMethod fm, LocalityBinding lb, FlatSESEEnterNode fsen, PrintWriter output) { + public void generateFlatSESEEnterNode( FlatMethod fm, + LocalityBinding lb, + FlatSESEEnterNode fsen, + PrintWriter output + ) { if( !state.MLP ) { // SESE nodes can be parsed for normal compilation, just skip over them return; } + output.println(" {"); + + // just allocate the space for this record output.println(" "+fsen.getSESErecordName()+"* seseToIssue = ("+ fsen.getSESErecordName()+"*) mlpAllocSESErecord( sizeof( "+ fsen.getSESErecordName()+" ) );"); + + // fill in common data output.println(" seseToIssue->common.classID = "+fsen.getIdentifier()+";"); output.println(" psem_init( &(seseToIssue->common.stallSem) );"); @@ -2713,6 +2732,9 @@ public class BuildCode { TempDescriptor temp = itr.next(); output.print(" seseToIssue->"+temp.getSafeSymbol()+"__srcAddr_ = "); + // if we are root (no parent) or the temp is in the in or out + // out set, we know it is in the params structure, otherwise its + // a method local variable if( fsen.getParent() == null || fsen.getParent().getInVarSet().contains( temp ) || fsen.getParent().getOutVarSet().contains( temp ) @@ -2723,41 +2745,97 @@ public class BuildCode { } } - // for finding dynamic SESE instances from static names + // before potentially adding this SESE to other forwarding lists, + // create it's lock and take it immediately + output.println(" pthread_mutex_init( &(seseToIssue->common.lock), NULL );"); + output.println(" pthread_mutex_lock( &(seseToIssue->common.lock) );"); + + output.println(" seseToIssue->common.forwardList = createQueue();"); + output.println(" seseToIssue->common.unresolvedDependencies = 0;"); + output.println(" seseToIssue->common.doneExecuting = FALSE;"); + if( fsen != mlpa.getRootSESE() ) { + + // count up outstanding dependencies, static first, then dynamic + Iterator staticSrcsItr = fsen.getStaticInVarSrcs().iterator(); + while( staticSrcsItr.hasNext() ) { + SESEandAgePair srcPair = staticSrcsItr.next(); + output.println(" {"); + output.println(" SESEcommon* src = (SESEcommon*)"+srcPair+";"); + output.println(" pthread_mutex_lock( &(src->lock) );"); + output.println(" if( seseToIssue == peekItem( src->forwardList ) ) {"); + output.println(" printf( \"This shouldnt already be here\\n\");"); + output.println(" exit( -1 );"); + output.println(" }"); + output.println(" addNewItem( src->forwardList, seseToIssue );"); + output.println(" ++(seseToIssue->common.unresolvedDependencies);"); + output.println(" pthread_mutex_unlock( &(src->lock) );"); + output.println(" }"); + } + + /* + // maintain pointers for for finding dynamic SESE + // instances from static names SESEandAgePair p = new SESEandAgePair( fsen, 0 ); output.println(" "+p+" = seseToIssue;"); + */ } - - // submit the SESE as work - output.println(" workScheduleSubmit( (void*) seseToIssue );"); + + // if there were no outstanding dependencies, issue here + output.println(" if( seseToIssue->common.unresolvedDependencies == 0 ) {"); + output.println(" workScheduleSubmit( (void*)seseToIssue );"); + output.println(" }"); + + // release this SESE for siblings to update its dependencies or, + // eventually, for it to mark itself finished + output.println(" pthread_mutex_unlock( &(seseToIssue->common.lock) );"); output.println(" }"); + } - public void generateFlatSESEExitNode(FlatMethod fm, LocalityBinding lb, FlatSESEExitNode fsexn, PrintWriter output) { + public void generateFlatSESEExitNode( FlatMethod fm, + LocalityBinding lb, + FlatSESEExitNode fsexn, + PrintWriter output + ) { if( !state.MLP ) { // SESE nodes can be parsed for normal compilation, just skip over them return; } + String com = paramsprefix+"->common"; + // copy out-set from local temps into the sese record Iterator itr = fsexn.getFlatEnter().getOutVarSet().iterator(); while( itr.hasNext() ) { - TempDescriptor temp = itr.next(); - - output.println(" "+paramsprefix+"->"+temp.getSafeSymbol()+" = "+temp.getSafeSymbol()+";" ); - - //output.println(" printf(\" putting "+temp.getSafeSymbol()+" in out with val=%d\\n\", "+temp.getSafeSymbol()+");"); + TempDescriptor temp = itr.next(); + output.println(" "+paramsprefix+ + "->"+temp.getSafeSymbol()+ + " = "+temp.getSafeSymbol()+";" ); } + // mark yourself done, your SESE data is now read-only + output.println(" pthread_mutex_lock( &("+com+".lock) );"); + output.println(" "+com+".doneExecuting = TRUE;"); + output.println(" pthread_mutex_unlock( &("+com+".lock) );"); + + // decrement dependency count for all SESE's on your forwarding list + output.println(" while( !isEmpty( "+com+".forwardList ) ) {"); + output.println(" SESEcommon* consumer = (SESEcommon*) getItem( "+com+".forwardList );"); + output.println(" pthread_mutex_lock( &(consumer->lock) );"); + output.println(" --(consumer->unresolvedDependencies);"); + output.println(" if( consumer->unresolvedDependencies == 0 ) {"); + output.println(" workScheduleSubmit( (void*)consumer );"); + output.println(" }"); + output.println(" pthread_mutex_unlock( &(consumer->lock) );"); + output.println(" }"); + // if parent is stalling on you, let them know you're done if( fsexn.getFlatEnter() != mlpa.getRootSESE() ) { - output.println(" {"); output.println(" psem_give( &("+paramsprefix+"->common.stallSem) );"); - output.println(" }"); } } - + private void generateFlatCheckNode(FlatMethod fm, LocalityBinding lb, FlatCheckNode fcn, PrintWriter output) { if (state.CONSCHECK) { String specname=fcn.getSpec(); diff --git a/Robust/src/IR/Flat/FlatSESEEnterNode.java b/Robust/src/IR/Flat/FlatSESEEnterNode.java index a7717360..6466c33d 100644 --- a/Robust/src/IR/Flat/FlatSESEEnterNode.java +++ b/Robust/src/IR/Flat/FlatSESEEnterNode.java @@ -1,5 +1,6 @@ package IR.Flat; import Analysis.MLP.VariableSourceToken; +import Analysis.MLP.VarSrcTokTable; import Analysis.MLP.SESEandAgePair; import IR.MethodDescriptor; import IR.ClassDescriptor; @@ -13,14 +14,18 @@ public class FlatSESEEnterNode extends FlatNode { // sequentially from 0 to 1-(total # SESE's) private static int identifier=0; - private int id; - protected FlatSESEExitNode exit; - protected SESENode treeNode; + private int id; + protected FlatSESEExitNode exit; + protected SESENode treeNode; protected FlatSESEEnterNode parent; + protected Set children; - protected Set inVars; - protected Set outVars; - protected Set needStaticNameInCode; + protected Set inVars; + protected Set outVars; + protected Set needStaticNameInCode; + protected Set staticInVarSrcs; + protected Set dynamicInVars; + // scope info for this SESE protected FlatMethod fmEnclosing; @@ -41,6 +46,8 @@ public class FlatSESEEnterNode extends FlatNode { inVars = new HashSet(); outVars = new HashSet(); needStaticNameInCode = new HashSet(); + staticInVarSrcs = new HashSet(); + dynamicInVars = new HashSet(); } public void rewriteUse() { @@ -139,27 +146,6 @@ public class FlatSESEEnterNode extends FlatNode { return vecinVars.size(); } - /* - public String namespaceStructNameString() { - return "struct SESE_"+getPrettyIdentifier()+"_namespace"; - } - - public String namespaceStructDeclarationString() { - String s = "struct SESE_"+getPrettyIdentifier()+"_namespace {\n"; - for( int i = 0; i < numParameters(); ++i ) { - TempDescriptor td = getParameter( i ); - TypeDescriptor type = td.getType(); - s += " "+type.toString()+" "+td+";\n"; - } - s += "};\n"; - return s; - } - - public String namespaceStructAccessString( TempDescriptor td ) { - return "SESE_"+getPrettyIdentifier()+"_namespace."+td; - } - */ - public Set getNodeSet() { HashSet tovisit=new HashSet(); HashSet visited=new HashSet(); @@ -192,6 +178,24 @@ public class FlatSESEEnterNode extends FlatNode { return needStaticNameInCode; } + public void addStaticInVarSrc( SESEandAgePair p ) { + staticInVarSrcs.add( p ); + } + + public Set getStaticInVarSrcs() { + return staticInVarSrcs; + } + + /* + public void addDynamicInVar( TempDescriptor td ) { + dynamicInVars.add( td ); + } + + public Set getDynamicInVarSet() { + return dynamicInVars; + } + */ + public void setfmEnclosing( FlatMethod fm ) { fmEnclosing = fm; } public FlatMethod getfmEnclosing() { return fmEnclosing; } diff --git a/Robust/src/Runtime/mlp_runtime.c b/Robust/src/Runtime/mlp_runtime.c index 1070c2c9..a01e220b 100644 --- a/Robust/src/Runtime/mlp_runtime.c +++ b/Robust/src/Runtime/mlp_runtime.c @@ -10,10 +10,6 @@ #include "workschedule.h" -#define FALSE 0 -#define TRUE 1 - - void* mlpAllocSESErecord( int size ) { void* newrec = RUNMALLOC( size ); @@ -25,7 +21,7 @@ void mlpFreeSESErecord( void* seseRecord ) { RUNFREE( seseRecord ); } - +/* void mlpInit( int numProcessors, void(*workFunc)(void*), int argc, char** argv, @@ -36,13 +32,14 @@ void mlpInit( int numProcessors, //workScheduleBegin(); } - - -void mlpIssue( void* seseRecord ) { - +*/ +/* +void mlpCommonIssueActions( void* seseRecord ) { + } void mlpStall( void* seseRecord ) { } +*/ diff --git a/Robust/src/Runtime/mlp_runtime.h b/Robust/src/Runtime/mlp_runtime.h index d5b51c8c..b4b2d05e 100644 --- a/Robust/src/Runtime/mlp_runtime.h +++ b/Robust/src/Runtime/mlp_runtime.h @@ -7,6 +7,15 @@ #include "psemaphore.h" +#ifndef FALSE +#define FALSE 0 +#endif + +#ifndef TRUE +#define TRUE 1 +#endif + + // these fields are common to any SESE, and casting the // generated SESE record to this can be used, because // the common structure is always the first item in a @@ -25,6 +34,7 @@ typedef struct SESEcommon_t { // use to coordinate with one another pthread_mutex_t lock; struct Queue* forwardList; + int unresolvedDependencies; int doneExecuting; } SESEcommon; @@ -43,14 +53,15 @@ typedef struct SESEvarSrc_t { // simple mechanical allocation and // deallocation of SESE records -void* mlpCreateSESErecord( int classID, int size ); +void* mlpCreateSESErecord( int size ); void mlpDestroySESErecord( void* seseRecord ); // main library functions +/* void mlpInit(); -void mlpIssue( void* seseRecord ); +void mlpCommonIssueActions( void* seseRecord ); void mlpStall( void* seseRecord ); - +*/ #endif /* __MLP_RUNTIME__ */ diff --git a/Robust/src/Tests/mlp/tinyTest/test.java b/Robust/src/Tests/mlp/tinyTest/test.java index 9734eda2..c993e422 100644 --- a/Robust/src/Tests/mlp/tinyTest/test.java +++ b/Robust/src/Tests/mlp/tinyTest/test.java @@ -33,28 +33,12 @@ public class Test { return; } */ - - - /* - // ADD BACK IN LATER, TO TEST STALLS - // shouldn't cause a stall - int z = x; - - // stall and get values for y and z - x = x + 1; - - // all of these should proceed without stall - y = y + 1; - x = x + 1; - z = z + 1; - */ - + // see that values from sese fi are // forwarded to this sibling - //sese fo { - // expecting x=5, y=4 - System.out.println( "root: x="+x+", y="+y ); - //} + sese fo { + System.out.println( "root: x="+x+", y="+y ); + } /* float xyz = 2.0f; -- 2.34.1