From 88692360e288319379f941c7c087205597e95525 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 13 Aug 2009 19:16:41 +0000 Subject: [PATCH] primitive dynamic variables are working --- Robust/src/Analysis/MLP/CodePlan.java | 28 +++++-- Robust/src/Analysis/MLP/MLPAnalysis.java | 78 +++++++++++++------ Robust/src/Analysis/MLP/VarSrcTokTable.java | 30 ++++--- Robust/src/IR/Flat/BuildCode.java | 72 ++++++++++------- Robust/src/IR/Flat/FlatSESEEnterNode.java | 12 +-- .../src/IR/Flat/FlatWriteDynamicVarNode.java | 22 ++++-- Robust/src/Tests/mlp/tinyTest/test.java | 10 +-- 7 files changed, 167 insertions(+), 85 deletions(-) diff --git a/Robust/src/Analysis/MLP/CodePlan.java b/Robust/src/Analysis/MLP/CodePlan.java index d71626e8..28b08f8c 100644 --- a/Robust/src/Analysis/MLP/CodePlan.java +++ b/Robust/src/Analysis/MLP/CodePlan.java @@ -11,12 +11,13 @@ import java.io.*; public class CodePlan { private Hashtable< VariableSourceToken, Set > stall2copySet; - private Set dynamicStallSet; - + private Set dynamicStallSet; + private Hashtable dynAssign_lhs2rhs; public CodePlan() { - stall2copySet = new Hashtable< VariableSourceToken, Set >(); - dynamicStallSet = new HashSet(); + stall2copySet = new Hashtable< VariableSourceToken, Set >(); + dynamicStallSet = new HashSet(); + dynAssign_lhs2rhs = new Hashtable(); } @@ -48,6 +49,14 @@ public class CodePlan { return dynamicStallSet; } + public void addDynAssign( TempDescriptor lhs, + TempDescriptor rhs ) { + dynAssign_lhs2rhs.put( lhs, rhs ); + } + + public Hashtable getDynAssigns() { + return dynAssign_lhs2rhs; + } public boolean equals( Object o ) { if( o == null ) { @@ -63,8 +72,10 @@ public class CodePlan { boolean copySetsEq = (stall2copySet.equals( cp.stall2copySet )); boolean dynStallSetEq = (dynamicStallSet.equals( cp.dynamicStallSet )); + + boolean dynAssignEq = (dynAssign_lhs2rhs.equals( cp.dynAssign_lhs2rhs )); - return copySetsEq && dynStallSetEq; + return copySetsEq && dynStallSetEq && dynAssignEq; } public int hashCode() { @@ -73,9 +84,12 @@ public class CodePlan { int dynStallSetHC = dynamicStallSet.hashCode(); + int dynAssignHC = dynAssign_lhs2rhs.hashCode(); + int hash = 7; hash = 31*hash + copySetsHC; hash = 31*hash + dynStallSetHC; + hash = 31*hash + dynAssignHC; return hash; } @@ -101,6 +115,10 @@ public class CodePlan { s += "[DYN STALLS:"+dynamicStallSet+"]"; } + if( !dynAssign_lhs2rhs.isEmpty() ) { + s += "[DYN ASSIGNS:"+dynAssign_lhs2rhs+"]"; + } + return s; } } diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index ed72c5ac..6faa8829 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -143,7 +143,7 @@ public class MLPAnalysis { pruneVariableResultsWithLiveness( fm ); } if( state.MLPDEBUG ) { - System.out.println( "\nVariable Results-Out\n----------------\n"+fmMain.printMethod( variableResults ) ); + //System.out.println( "\nVariable Results-Out\n----------------\n"+fmMain.printMethod( variableResults ) ); } @@ -158,7 +158,7 @@ public class MLPAnalysis { notAvailableForward( fm ); } if( state.MLPDEBUG ) { - System.out.println( "\nNot Available Results-Out\n---------------------\n"+fmMain.printMethod( notAvailableResults ) ); + //System.out.println( "\nNot Available Results-Out\n---------------------\n"+fmMain.printMethod( notAvailableResults ) ); } @@ -823,8 +823,15 @@ public class MLPAnalysis { } } + Set dotSTlive = livenessRootView.get( fn ); + if( !seseStack.empty() ) { - computeStalls_nodeActions( fn, dotSTtable, dotSTnotAvailSet, seseStack.peek() ); + computeStalls_nodeActions( fn, + dotSTlive, + dotSTtable, + dotSTnotAvailSet, + seseStack.peek() + ); } for( int i = 0; i < fn.numNext(); i++ ) { @@ -838,8 +845,9 @@ public class MLPAnalysis { } private void computeStalls_nodeActions( FlatNode fn, - VarSrcTokTable vstTable, - Set notAvailSet, + Set liveSetIn, + VarSrcTokTable vstTableIn, + Set notAvailSetIn, FlatSESEEnterNode currentSESE ) { CodePlan plan = new CodePlan(); @@ -856,7 +864,7 @@ public class MLPAnalysis { while( inVarItr.hasNext() ) { TempDescriptor inVar = inVarItr.next(); Integer srcType = - vstTable.getRefVarSrcType( inVar, + vstTableIn.getRefVarSrcType( inVar, fsen, fsen.getParent() ); @@ -865,7 +873,7 @@ public class MLPAnalysis { } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { fsen.addStaticInVar( inVar ); - VariableSourceToken vst = vstTable.get( inVar ).iterator().next(); + VariableSourceToken vst = vstTableIn.get( inVar ).iterator().next(); fsen.putStaticInVar2src( inVar, vst ); fsen.addStaticInVarSrc( new SESEandAgePair( vst.getSESE(), vst.getAge() @@ -888,9 +896,26 @@ public class MLPAnalysis { FlatOpNode fon = (FlatOpNode) fn; if( fon.getOp().getOp() == Operation.ASSIGN ) { + TempDescriptor lhs = fon.getDest(); + TempDescriptor rhs = fon.getLeft(); + // if this is an op node, don't stall, copy // source and delay until we need to use value + // but check the source type of rhs variable + // and if dynamic, lhs becomes dynamic, too, + // and we need to keep dynamic sources during + Integer srcType + = vstTableIn.getRefVarSrcType( rhs, + currentSESE, + currentSESE.getParent() ); + + if( srcType.equals( VarSrcTokTable.SrcType_DYNAMIC ) ) { + plan.addDynAssign( lhs, rhs ); + currentSESE.addDynamicVar( lhs ); + currentSESE.addDynamicVar( rhs ); + } + // only break if this is an ASSIGN op node, // otherwise fall through to default case break; @@ -902,8 +927,7 @@ public class MLPAnalysis { default: { // a node with no live set has nothing to stall for - Set liveSet = livenessRootView.get( fn ); - if( liveSet == null ) { + if( liveSetIn == null ) { break; } @@ -913,13 +937,13 @@ public class MLPAnalysis { // ignore temps that are definitely available // when considering to stall on it - if( !notAvailSet.contains( readtmp ) ) { + if( !notAvailSetIn.contains( readtmp ) ) { continue; } // check the source type of this variable Integer srcType - = vstTable.getRefVarSrcType( readtmp, + = vstTableIn.getRefVarSrcType( readtmp, currentSESE, currentSESE.getParent() ); @@ -929,7 +953,7 @@ public class MLPAnalysis { // along various control paths, and therefore when we stall, // just stall for the exact thing we need and move on plan.addDynamicStall( readtmp ); - currentSESE.addDynamicStallVar( readtmp ); + currentSESE.addDynamicVar( readtmp ); } else if( srcType.equals( VarSrcTokTable.SrcType_STATIC ) ) { // 2) Single token/age pair: Stall for token/age pair, and copy @@ -937,10 +961,10 @@ public class MLPAnalysis { // time. This is the same stuff that the notavaialable analysis // marks as now available. - VariableSourceToken vst = vstTable.get( readtmp ).iterator().next(); + VariableSourceToken vst = vstTableIn.get( readtmp ).iterator().next(); Iterator availItr = - vstTable.get( vst.getSESE(), vst.getAge() ).iterator(); + vstTableIn.get( vst.getSESE(), vst.getAge() ).iterator(); while( availItr.hasNext() ) { VariableSourceToken vstAlsoAvail = availItr.next(); @@ -951,7 +975,7 @@ public class MLPAnalysis { Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); while( refVarItr.hasNext() ) { TempDescriptor refVar = refVarItr.next(); - if( liveSet.contains( refVar ) ) { + if( liveSetIn.contains( refVar ) ) { copySet.add( refVar ); } } @@ -975,13 +999,13 @@ public class MLPAnalysis { } } break; - + } // end switch // identify sese-age pairs that are statically useful // and should have an associated SESE variable in code - Set staticSet = vstTable.getStaticSet(); + Set staticSet = vstTableIn.getStaticSet(); Iterator vstItr = staticSet.iterator(); while( vstItr.hasNext() ) { VariableSourceToken vst = vstItr.next(); @@ -995,19 +1019,21 @@ public class MLPAnalysis { codePlans.put( fn, plan ); - // if any variables at this node have a static source (exactly one vst) - // but go to a dynamic source at a next node, create a new IR graph + // 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 + VarSrcTokTable thisVstTable = variableResults.get( fn ); for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - VarSrcTokTable nextVstTable = variableResults.get( nn ); + FlatNode nn = fn.getNext( i ); + VarSrcTokTable nextVstTable = variableResults.get( nn ); + Set nextLiveIn = livenessRootView.get( nn ); // the table can be null if it is one of the few IR nodes // completely outside of the root SESE scope - if( nextVstTable != null ) { + if( nextVstTable != null && nextLiveIn != null ) { Hashtable static2dynamicSet = - vstTable.getStatic2DynamicSet( nextVstTable ); + thisVstTable.getStatic2DynamicSet( nextVstTable, nextLiveIn ); if( !static2dynamicSet.isEmpty() ) { @@ -1017,7 +1043,11 @@ public class MLPAnalysis { FlatWriteDynamicVarNode fwdvn = wdvNodesToSpliceIn.get( fe ); if( fwdvn == null ) { - fwdvn = new FlatWriteDynamicVarNode( fn, nn, static2dynamicSet ); + fwdvn = new FlatWriteDynamicVarNode( fn, + nn, + static2dynamicSet, + currentSESE + ); wdvNodesToSpliceIn.put( fe, fwdvn ); } else { fwdvn.addMoreVar2Src( static2dynamicSet ); diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java index 0b07adbe..bb48bc5b 100644 --- a/Robust/src/Analysis/MLP/VarSrcTokTable.java +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -484,7 +484,9 @@ public class VarSrcTokTable { // given a table from a subsequent program point, decide // which variables are going from a static source to a // dynamic source and return them - public Hashtable getStatic2DynamicSet( VarSrcTokTable next ) { + public Hashtable + getStatic2DynamicSet( VarSrcTokTable nextTable, + Set nextLiveIn ) { Hashtable out = new Hashtable(); @@ -495,19 +497,23 @@ public class VarSrcTokTable { TempDescriptor var = (TempDescriptor) me.getKey(); HashSet s1 = (HashSet) me.getValue(); - // this is a variable with a static source if it - // currently has one vst - if( s1.size() == 1 ) { - Set s2 = next.get( var ); + // only worth tracking if live + if( nextLiveIn.contains( var ) ) { - // and if in the next table, it is dynamic, then - // this is a transition point, so - if( s2.size() > 1 ) { + // this is a variable with a static source if it + // currently has one vst + if( s1.size() == 1 ) { + Set s2 = nextTable.get( var ); - // remember the variable and the only source - // it had before crossing the transition - out.put( var, s1.iterator().next() ); - } + // and if in the next table, it is dynamic, then + // this is a transition point, so + if( s2.size() > 1 ) { + + // remember the variable and the only source + // it had before crossing the transition + out.put( var, s1.iterator().next() ); + } + } } } diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index fa56edcf..fa42b1f0 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -1873,20 +1873,12 @@ public class BuildCode { } // declare variables for tracking dynamic sources - Set dynSrcVars = new HashSet(); - dynSrcVars.addAll( fsen.getDynamicStallVarSet() ); - Iterator childItr = fsen.getChildren().iterator(); - while( childItr.hasNext() ) { - FlatSESEEnterNode child = childItr.next(); - dynSrcVars.addAll( child.getDynamicInVarSet() ); - } - Iterator dynItr = dynSrcVars.iterator(); - while( dynItr.hasNext() ) { - TempDescriptor dynVar = dynItr.next(); - output.println(" void* "+dynVar+"_srcSESE;"); - output.println(" INTPTR "+dynVar+"_srcAddr;"); - } - + Iterator dynSrcItr = fsen.getDynamicVarSet().iterator(); + while( dynSrcItr.hasNext() ) { + TempDescriptor dynSrcVar = dynSrcItr.next(); + output.println(" void* "+dynSrcVar+"_srcSESE;"); + output.println(" int "+dynSrcVar+"_srcOffset;"); + } // declare local temps for in-set primitives, and if it is // a ready-source variable, get the value from the record @@ -2280,14 +2272,33 @@ public class BuildCode { output.println(" }"); } - - // for each variable with a dynamic source, stall just - // for that variable + // for each variable with a dynamic source, stall just for that variable Iterator dynItr = cp.getDynamicStallSet().iterator(); while( dynItr.hasNext() ) { TempDescriptor dynVar = dynItr.next(); + // only stall if the dynamic source is not yourself, denoted by src==NULL + // otherwise the dynamic write nodes will have the local var up-to-date + output.println(" {"); + output.println(" if( "+dynVar+"_srcSESE != NULL ) {"); + output.println(" SESEcommon* common = (SESEcommon*) "+dynVar+"_srcSESE;"); + output.println(" psem_take( &(common->stallSem) );"); + output.println(" "+dynVar+" = *(("+dynVar.getType()+"*) ("+ + dynVar+"_srcSESE + "+dynVar+"_srcOffset));"); + output.println(" }"); + output.println(" }"); + } + + // for each assignment of a variable to rhs that has a dynamic source, + // copy the dynamic sources + Iterator dynAssignItr = cp.getDynAssigns().entrySet().iterator(); + while( dynAssignItr.hasNext() ) { + Map.Entry me = (Map.Entry) dynAssignItr.next(); + TempDescriptor lhs = (TempDescriptor) me.getKey(); + TempDescriptor rhs = (TempDescriptor) me.getValue(); + output.println(" "+lhs+"_srcSESE = "+rhs+"_srcSESE;"); + output.println(" "+lhs+"_srcOffset = "+rhs+"_srcOffset;"); } } } @@ -2908,20 +2919,27 @@ public class BuildCode { Iterator wdItr = writeDynamic.entrySet().iterator(); while( wdItr.hasNext() ) { - Map.Entry me = (Map.Entry) wdItr.next(); - TempDescriptor var = (TempDescriptor) me.getKey(); - VariableSourceToken vst = (VariableSourceToken) me.getValue(); + Map.Entry me = (Map.Entry) wdItr.next(); + TempDescriptor refVar = (TempDescriptor) me.getKey(); + VariableSourceToken vst = (VariableSourceToken) me.getValue(); SESEandAgePair instance = new SESEandAgePair( vst.getSESE(), vst.getAge() ); output.println(" {"); - output.println(" "+var+"_srcSESE = "+instance+";"); - - output.println(" "+vst.getSESE().getSESErecordName()+"* rec = ("+ - vst.getSESE().getSESErecordName()+") "+ - instance+";"); - - output.println(" "+var+"_srcAddr = (INTPTR) &(rec->"+vst.getAddrVar()+");"); + + if( fwdvn.getEnclosingSESE().equals( vst.getSESE() ) ) { + // if the src comes from this SESE, it's a method local variable, + // mark src pointer NULL to signify that the var is up-to-date + output.println(" "+vst.getAddrVar()+"_srcSESE = NULL;"); + output.println(" "+refVar+" = "+vst.getAddrVar()+";"); + + } else { + // otherwise we track where it will come from + output.println(" "+vst.getAddrVar()+"_srcSESE = "+instance+";"); + output.println(" "+vst.getAddrVar()+"_srcOffset = (int) &((("+ + vst.getSESE().getSESErecordName()+"*)0)->"+vst.getAddrVar()+");"); + } + output.println(" }"); } } diff --git a/Robust/src/IR/Flat/FlatSESEEnterNode.java b/Robust/src/IR/Flat/FlatSESEEnterNode.java index 209a5961..b9b00e38 100644 --- a/Robust/src/IR/Flat/FlatSESEEnterNode.java +++ b/Robust/src/IR/Flat/FlatSESEEnterNode.java @@ -33,7 +33,7 @@ public class FlatSESEEnterNode extends FlatNode { protected Set staticInVars; protected Set dynamicInVars; - protected Set dynamicStallVars; + protected Set dynamicVars; protected Hashtable staticInVar2src; @@ -63,7 +63,7 @@ public class FlatSESEEnterNode extends FlatNode { readyInVars = new HashSet(); staticInVars = new HashSet(); dynamicInVars = new HashSet(); - dynamicStallVars = new HashSet(); + dynamicVars = new HashSet(); staticInVar2src = new Hashtable(); } @@ -237,12 +237,12 @@ public class FlatSESEEnterNode extends FlatNode { return dynamicInVars; } - public void addDynamicStallVar( TempDescriptor td ) { - dynamicStallVars.add( td ); + public void addDynamicVar( TempDescriptor td ) { + dynamicVars.add( td ); } - public Set getDynamicStallVarSet() { - return dynamicStallVars; + public Set getDynamicVarSet() { + return dynamicVars; } public void mustTrackAtLeastAge( Integer age ) { diff --git a/Robust/src/IR/Flat/FlatWriteDynamicVarNode.java b/Robust/src/IR/Flat/FlatWriteDynamicVarNode.java index ac9cad81..53b746d3 100644 --- a/Robust/src/IR/Flat/FlatWriteDynamicVarNode.java +++ b/Robust/src/IR/Flat/FlatWriteDynamicVarNode.java @@ -15,14 +15,18 @@ public class FlatWriteDynamicVarNode extends FlatNode { protected Hashtable var2src; + protected FlatSESEEnterNode enclosingSESE; + public FlatWriteDynamicVarNode( FlatNode t, FlatNode h, - Hashtable v2s + Hashtable v2s, + FlatSESEEnterNode c ) { - tailNode = t; - headNode = h; - var2src = v2s; + tailNode = t; + headNode = h; + var2src = v2s; + enclosingSESE = c; } public void spliceIntoIR() { @@ -41,6 +45,10 @@ public class FlatWriteDynamicVarNode extends FlatNode { return var2src; } + public FlatSESEEnterNode getEnclosingSESE() { + return enclosingSESE; + } + public String toString() { return "writeDynVars "+var2src.keySet(); } @@ -50,7 +58,11 @@ public class FlatWriteDynamicVarNode extends FlatNode { } public FlatNode clone(TempMap t) { - return new FlatWriteDynamicVarNode( tailNode, headNode, var2src ); + return new FlatWriteDynamicVarNode( tailNode, + headNode, + var2src, + enclosingSESE + ); } public void rewriteUse(TempMap t) { } diff --git a/Robust/src/Tests/mlp/tinyTest/test.java b/Robust/src/Tests/mlp/tinyTest/test.java index a261f869..4dd35d99 100644 --- a/Robust/src/Tests/mlp/tinyTest/test.java +++ b/Robust/src/Tests/mlp/tinyTest/test.java @@ -12,13 +12,11 @@ public class Test { public static void main( String args[] ) { - //int x = Integer.parseInt( args[0] ); - //int y = Integer.parseInt( args[1] ); - //System.out.println( "root: x="+x+", y="+y ); - int y = 2; + int x = Integer.parseInt( args[0] ); + int y = Integer.parseInt( args[1] ); + System.out.println( "root: x="+x+", y="+y ); - //if( x > 3 ) { - if( true ) { + if( x > 3 ) { sese fi { y = y + 10; } -- 2.34.1