From 43b6b0ce7363eaaeb209dad97f6b1dfcb96f7d0f Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 9 Apr 2009 21:20:30 +0000 Subject: [PATCH] more new mlp stuff --- Robust/src/Analysis/MLP/MLPAnalysis.java | 285 ++++++++++++------ Robust/src/Analysis/MLP/SVKey.java | 50 +++ Robust/src/Analysis/MLP/VarSrcTokTable.java | 52 ++++ .../src/Analysis/MLP/VariableSourceToken.java | 9 +- Robust/src/IR/State.java | 1 + Robust/src/Main/Main.java | 13 +- Robust/src/Makefile | 3 + Robust/src/Tests/mlp/tinyTest/makefile | 4 +- Robust/src/Tests/mlp/tinyTest/test.java | 34 +-- Robust/src/buildscript | 7 + 10 files changed, 335 insertions(+), 123 deletions(-) create mode 100644 Robust/src/Analysis/MLP/SVKey.java create mode 100644 Robust/src/Analysis/MLP/VarSrcTokTable.java diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index 27c3921e..1f3611ad 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -20,6 +20,8 @@ public class MLPAnalysis { private Stack seseStack; private Set seseRoots; + private Hashtable< FlatNode, Set > pointResults; + public MLPAnalysis( State state, TypeUtil tu, @@ -38,6 +40,9 @@ public class MLPAnalysis { seseStack = new Stack (); seseRoots = new HashSet(); + pointResults = new Hashtable< FlatNode, Set >(); + + // run analysis on each method that is actually called // reachability analysis already computed this so reuse Iterator methItr = ownAnalysis.descriptorsToAnalyze.iterator(); @@ -76,20 +81,39 @@ public class MLPAnalysis { private void buildForestForward( FlatMethod fm ) { - + + // start from flat method top, visit every node in + // method exactly once, find SESEs and remember + // roots and child relationships Set flatNodesToVisit = new HashSet(); flatNodesToVisit.add( fm ); Set visited = new HashSet(); while( !flatNodesToVisit.isEmpty() ) { - FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + Iterator fnItr = flatNodesToVisit.iterator(); + FlatNode fn = fnItr.next(); + + System.out.println( " considering "+fn ); + + // only analyze sese exit nodes when all the nodes between + // it and its matching enter have been analyzed + if( !seseStack.empty() && + fn.equals( seseStack.peek().getFlatExit() ) && + flatNodesToVisit.size() != 1 ) { + // not ready for this exit node yet, just grab another + fn = fnItr.next(); + } + flatNodesToVisit.remove( fn ); - visited.add( fn ); + visited.add( fn ); + + System.out.println( " visiting "+fn ); - //System.out.println( " "+fn ); + analyzeFlatNode( fn, true, null, null ); - analyzeFlatNode( fn, true ); + // initialize for backward computation in next step + pointResults.put( fn, new HashSet() ); for( int i = 0; i < fn.numNext(); i++ ) { FlatNode nn = fn.getNext( i ); @@ -103,15 +127,64 @@ public class MLPAnalysis { private void computeReadAndWriteSetBackward( FlatSESEEnterNode fsen ) { - - } + // start from an SESE exit, visit nodes in reverse up to + // SESE enter in a fixed-point scheme, where children SESEs + // should already be analyzed and therefore can be skipped + // because child SESE enter node has all necessary info + Set flatNodesToVisit = new HashSet(); + flatNodesToVisit.add( fsen.getFlatExit() ); + + while( !flatNodesToVisit.isEmpty() ) { + FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); + flatNodesToVisit.remove( fn ); + + Set prev = pointResults.get( fn ); + + // merge sets from control flow joins + Set merge = new HashSet(); + for( int i = 0; i < fn.numNext(); i++ ) { + FlatNode nn = fn.getNext( i ); + merge = mergeVSTsets( merge, pointResults.get( nn ) ); + } + + Set curr = analyzeFlatNode( fn, false, merge, fsen ); + + // if a new result, schedule backward nodes for analysis + if( !prev.equals( curr ) ) { + + System.out.println( " "+fn+":" ); + System.out.println( " prev ="+prev ); + System.out.println( " merge="+merge ); + System.out.println( " curr ="+curr ); + System.out.println( "" ); + + pointResults.put( fn, curr ); + + // don't flow backwards past SESE enter + if( !fn.equals( fsen ) ) { + for( int i = 0; i < fn.numPrev(); i++ ) { + FlatNode nn = fn.getPrev( i ); + flatNodesToVisit.add( nn ); + } + } + } + } + + if( state.MLPDEBUG ) { + System.out.println( "SESE "+fsen.getPrettyIdentifier()+" has in-set:" ); + Iterator tItr = pointResults.get( fsen ).iterator(); + while( tItr.hasNext() ) { + System.out.println( " "+tItr.next() ); + } + } + } - private void analyzeFlatNode( FlatNode fn, boolean buildForest ) { - TempDescriptor lhs; - TempDescriptor rhs; - FieldDescriptor fld; + private Set analyzeFlatNode( FlatNode fn, + boolean buildForest, + Set vstSet, + FlatSESEEnterNode currentSESE ) { // use node type to decide what alterations to make // to the ownership graph @@ -127,15 +200,17 @@ public class MLPAnalysis { seseStack.peek().addChild( fsen ); } seseStack.push( fsen ); + System.out.println( " pushed "+fsen ); } } break; case FKind.FlatSESEExitNode: { - FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; + FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; if( buildForest ) { assert !seseStack.empty(); - seseStack.pop(); + FlatSESEEnterNode fsen = seseStack.pop(); + System.out.println( " popped "+fsen ); } //FlatSESEEnterNode fsen = fsexn.getFlatEnter(); @@ -144,79 +219,37 @@ public class MLPAnalysis { //seseStack.peek().addOutVarSet( fsen.getOutVarSet() ); } break; - /* + /* case FKind.FlatMethod: { FlatMethod fm = (FlatMethod) fn; } break; + */ - case FKind.FlatOpNode: { - FlatOpNode fon = (FlatOpNode) fn; - if( fon.getOp().getOp() == Operation.ASSIGN ) { - lhs = fon.getDest(); - rhs = fon.getLeft(); - - } - } break; - - case FKind.FlatCastNode: { - FlatCastNode fcn = (FlatCastNode) fn; - lhs = fcn.getDst(); - rhs = fcn.getSrc(); - - TypeDescriptor td = fcn.getType(); - assert td != null; - - } break; - - case FKind.FlatFieldNode: { - FlatFieldNode ffn = (FlatFieldNode) fn; - lhs = ffn.getDst(); - rhs = ffn.getSrc(); - fld = ffn.getField(); - if( !fld.getType().isImmutable() || fld.getType().isArray() ) { - - } - } break; - - case FKind.FlatSetFieldNode: { - FlatSetFieldNode fsfn = (FlatSetFieldNode) fn; - lhs = fsfn.getDst(); - fld = fsfn.getField(); - rhs = fsfn.getSrc(); - if( !fld.getType().isImmutable() || fld.getType().isArray() ) { - - } - } break; - - case FKind.FlatElementNode: { - FlatElementNode fen = (FlatElementNode) fn; - lhs = fen.getDst(); - rhs = fen.getSrc(); - if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) { - - assert rhs.getType() != null; - assert rhs.getType().isArray(); - - TypeDescriptor tdElement = rhs.getType().dereference(); - //FieldDescriptor fdElement = getArrayField( tdElement ); - - } - } break; - + case FKind.FlatOpNode: + case FKind.FlatCastNode: + case FKind.FlatFieldNode: + case FKind.FlatSetFieldNode: + case FKind.FlatElementNode: case FKind.FlatSetElementNode: { - FlatSetElementNode fsen = (FlatSetElementNode) fn; - lhs = fsen.getDst(); - rhs = fsen.getSrc(); - if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) { + if( !buildForest ) { + // handle effects of statement in reverse, writes then reads + TempDescriptor [] writeTemps = fn.writesTemps(); + for( int i = 0; i < writeTemps.length; ++i ) { + vstSet = killTemp( vstSet, writeTemps[i] ); + } - assert lhs.getType() != null; - assert lhs.getType().isArray(); - - TypeDescriptor tdElement = lhs.getType().dereference(); - //FieldDescriptor fdElement = getArrayField( tdElement ); + TempDescriptor [] readTemps = fn.readsTemps(); + for( int i = 0; i < readTemps.length; ++i ) { + Set vstNew = new HashSet(); + vstNew.add( new VariableSourceToken( currentSESE, + readTemps[i], + new Integer( 0 ) ) ); + vstSet = mergeVSTsets( vstSet, vstNew ); + } } } break; + /* case FKind.FlatNew: { FlatNew fnn = (FlatNew) fn; lhs = fnn.getDst(); @@ -224,7 +257,9 @@ public class MLPAnalysis { //AllocationSite as = getAllocationSiteFromFlatNewPRIVATE( fnn ); } } break; + */ + /* case FKind.FlatCall: { FlatCall fc = (FlatCall) fn; MethodDescriptor md = fc.getMethod(); @@ -249,18 +284,100 @@ public class MLPAnalysis { } } break; + */ case FKind.FlatReturnNode: { FlatReturnNode frn = (FlatReturnNode) fn; - rhs = frn.getReturnTemp(); - if( rhs != null && !rhs.getType().isImmutable() ) { - - } - if( !seseStack.empty() ) { - throw new Error( "Error: return statement enclosed within SESE "+seseStack.peek() ); + if( buildForest && !seseStack.empty() ) { + throw new Error( "Error: return statement enclosed within "+seseStack.peek() ); } } break; - */ + } // end switch + + + return vstSet; + } + + + private Set killTemp( Set s, + TempDescriptor t ) { + Set out = new HashSet(); + + Iterator vstitr = s.iterator(); + while( vstitr.hasNext() ) { + VariableSourceToken vst = vstitr.next(); + + if( !vst.getVar().equals( t ) ) { + out.add( vst ); + } + } + + return out; + } + + + private Set mergeVSTsets( Set s1, + Set s2 ) { + + Set out = new HashSet(); + + Iterator vst1itr = s1.iterator(); + while( vst1itr.hasNext() ) { + VariableSourceToken vst1 = vst1itr.next(); + + int changeAge = -1; + + Iterator vst2itr = s2.iterator(); + while( vst2itr.hasNext() ) { + VariableSourceToken vst2 = vst2itr.next(); + + if( vst1.getSESE().equals( vst2.getSESE() ) && + vst1.getVar() .equals( vst2.getVar() ) ) { + changeAge = vst1.getAge(); + int a = vst2.getAge(); + if( a < changeAge ) { + changeAge = a; + } + break; + } + } + + if( changeAge < 0 ) { + out.add( vst1 ); + } else { + out.add( new VariableSourceToken( vst1.getSESE(), + vst1.getVar(), + new Integer( changeAge ) ) ); + } + } + + + Iterator vst2itr = s2.iterator(); + while( vst2itr.hasNext() ) { + VariableSourceToken vst2 = vst2itr.next(); + + boolean matchSESEandVar = false; + + vst1itr = s1.iterator(); + while( vst1itr.hasNext() ) { + VariableSourceToken vst1 = vst1itr.next(); + + if( vst1.getSESE().equals( vst2.getSESE() ) && + vst1.getVar() .equals( vst2.getVar() ) ) { + matchSESEandVar = true; + break; + } + } + + if( !matchSESEandVar ) { + out.add( vst2 ); + } + } + + + return out; } } + + diff --git a/Robust/src/Analysis/MLP/SVKey.java b/Robust/src/Analysis/MLP/SVKey.java new file mode 100644 index 00000000..afc53d09 --- /dev/null +++ b/Robust/src/Analysis/MLP/SVKey.java @@ -0,0 +1,50 @@ +package Analysis.MLP; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + +public class SVKey { + + private FlatSESEEnterNode sese; + private TempDescriptor var; + + public SVKey( FlatSESEEnterNode sese, + TempDescriptor var ) { + this.sese = sese; + this.var = var; + } + + public FlatSESEEnterNode getSESE() { + return sese; + } + + public TempDescriptor getVar() { + return var; + } + + public boolean equals( Object o ) { + if( o == null ) { + return false; + } + + if( !(o instanceof SVKey) ) { + return false; + } + + SVKey k = (SVKey) o; + + return var.equals( vst.var ) && + sese.equals( vst.sese ); + } + + public int hashCode() { + return (sese.hashCode() << 2)*(var.hashCode() << 5); + } + + + public String toString() { + return "key["+sese+", "+var+"]"; + } +} diff --git a/Robust/src/Analysis/MLP/VarSrcTokTable.java b/Robust/src/Analysis/MLP/VarSrcTokTable.java new file mode 100644 index 00000000..145c8292 --- /dev/null +++ b/Robust/src/Analysis/MLP/VarSrcTokTable.java @@ -0,0 +1,52 @@ +package Analysis.MLP; + +import IR.*; +import IR.Flat.*; +import java.util.*; +import java.io.*; + +public class VarSrcTokTable { + + // be able to grab the VariableSourceToken triples from the + // table by the sese, by the variable, or by a key that is + // an sese/variable pair + private Hashtable< FlatSESEEnterNode, Set > sese2vst; + private Hashtable< TempDescriptor, Set > var2vst; + private Hashtable< SVKey, Set > sv2vst; + + public VarSrcTokTable() { + sese2vst = new Hashtable< FlatSESEEnterNode, Set >(); + var2vst = new Hashtable< TempDescriptor, Set >(); + sv2vst = new Hashtable< SVKey, Set >(); + } + + + public void add( VariableSourceToken vst ) { + + } + + + public boolean equals( Object o ) { + if( o == null ) { + return false; + } + + if( !(o instanceof VariableSourceToken) ) { + return false; + } + + VariableSourceToken vst = (VariableSourceToken) o; + + return var.equals( vst.var ) && + age.equals( vst.age ); + } + + public int hashCode() { + return (var.hashCode() << 2) ^ age.intValue(); + } + + + public String toString() { + return "["+var+", "+age+"]"; + } +} diff --git a/Robust/src/Analysis/MLP/VariableSourceToken.java b/Robust/src/Analysis/MLP/VariableSourceToken.java index fe43742a..089ea914 100644 --- a/Robust/src/Analysis/MLP/VariableSourceToken.java +++ b/Robust/src/Analysis/MLP/VariableSourceToken.java @@ -43,16 +43,17 @@ public class VariableSourceToken { VariableSourceToken vst = (VariableSourceToken) o; - return var.equals( vst.var ) && - age.equals( vst.age ); + return sese.equals( vst.sese ) && + var.equals( vst.var ) && + age.equals( vst.age ); } public int hashCode() { - return (var.hashCode() << 2) ^ age.intValue(); + return (sese.hashCode() << 3) * (var.hashCode() << 2) ^ age.intValue(); } public String toString() { - return "["+var+", "+age+"]"; + return "["+sese+", "+var+", "+age+"]"; } } diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index e7cc04d5..48e33c4c 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -73,6 +73,7 @@ public class State { public boolean CONSCHECK=false; public boolean INSTRUCTIONFAILURE=false; public boolean MLP=false; + public boolean MLPDEBUG=false; public static double TRUEPROB=0.8; public static boolean PRINTFLAT=false; public static boolean PRINTSCHEDULING=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index a6b88127..74451906 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -153,9 +153,14 @@ public class Main { state.INSTRUCTIONFAILURE=true; else if (option.equals("-abcclose")) state.ARRAYBOUNDARYCHECK=false; - else if (option.equals("-mlp")) + else if (option.equals("-mlp")) { state.MLP=true; - else if (option.equals("-help")) { + state.OWNERSHIP=true; + } else if (option.equals("-mlpdebug")) { + state.MLP=true; + state.MLPDEBUG=true; + state.OWNERSHIP=true; + } else if (option.equals("-help")) { System.out.println("-classlibrary classlibrarydirectory -- directory where classlibrary is located"); System.out.println("-selfloop task -- this task doesn't self loop its parameters forever"); System.out.println("-dir outputdirectory -- output code in outputdirectory"); @@ -186,6 +191,7 @@ public class Main { System.out.println("-abcclose close the array boundary check"); System.out.println("-scheduling do task scheduling"); System.out.println("-mlp build mlp code"); + System.out.println("-mlp build mlp code, report progress and interim results"); System.out.println("-multicore generate multi-core version binary"); System.out.println("-numcore set the number of cores (should be used together with -multicore), defaultly set as 1"); System.out.println("-raw generate raw version binary (should be used together with -multicore)"); @@ -288,9 +294,6 @@ public class Main { } if (state.MLP) { - // gotta run this to have mlp turned on - assert state.OWNERSHIP; - CallGraph callGraph = new CallGraph(state); OwnershipAnalysis oa = new OwnershipAnalysis(state, tu, diff --git a/Robust/src/Makefile b/Robust/src/Makefile index a86f8fe8..51b7b93d 100644 --- a/Robust/src/Makefile +++ b/Robust/src/Makefile @@ -88,6 +88,9 @@ Analysis/OwnershipAnalysis/ChangeTupleSet.class \ Analysis/OwnershipAnalysis/Canonical.class \ Analysis/OwnershipAnalysis/MethodContext.class \ Analysis/MLP/MLPAnalysis.class \ +Analysis/MLP/VariableSourceToken.class \ +Analysis/MLP/SVKey.class \ +Analysis/MLP/VarSrcTokTable.class \ Util/GraphNode.class Util/Namer.class Util/Relation.class \ Interface/HTTPHeader.class Interface/HTTPResponse.class \ Interface/HTTPServices.class Interface/HashStrings.class \ diff --git a/Robust/src/Tests/mlp/tinyTest/makefile b/Robust/src/Tests/mlp/tinyTest/makefile index a62898ae..d23651f8 100644 --- a/Robust/src/Tests/mlp/tinyTest/makefile +++ b/Robust/src/Tests/mlp/tinyTest/makefile @@ -3,8 +3,8 @@ PROGRAM=test SOURCE_FILES=$(PROGRAM).java BUILDSCRIPT=~/research/Robust/src/buildscript -BSFLAGS= -mlp -mainclass Test -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions -flatirusermethods -ownaliasfile aliases.txt #-justanalyze -recover -#BSFLAGS= -mainclass Test -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions -flatirusermethods -ownaliasfile aliases.txt #-justanalyze -recover +#BSFLAGS= -mlpdebug -mainclass Test -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions -flatirusermethods -ownaliasfile aliases.txt #-justanalyze -recover +BSFLAGS= -mainclass Test -ownership -ownallocdepth 1 -ownwritedots final -enable-assertions -flatirusermethods -ownaliasfile aliases.txt #-justanalyze -recover all: $(PROGRAM).bin diff --git a/Robust/src/Tests/mlp/tinyTest/test.java b/Robust/src/Tests/mlp/tinyTest/test.java index ae8d3f13..c870a9ce 100644 --- a/Robust/src/Tests/mlp/tinyTest/test.java +++ b/Robust/src/Tests/mlp/tinyTest/test.java @@ -4,38 +4,16 @@ public class Test { int n = 10; - sese top { - - /* - int[] a = new int[n]; - int[] b = new int[n]; - int[] c = new int[n]; - - for( int i = 0; i < n; ++i ) { - sese { - a[i] = i; - b[i] = n - i; - } - } - - for( int j = 0; j < n; ++j ) { - sese { - c[j] = a[j] + b[j]; - } - } + sese top { + int x = n; - int total = 0; - for( int k = 0; k < n; ++k ) { - sese { - total = total + c[k]; + for( int i = 0; i < 3; ++i ) { + sese loop { + x = x + i; } } - - System.out.println( "total is "+total ); - */ - - int x = n; } + int j = x; } } diff --git a/Robust/src/buildscript b/Robust/src/buildscript index 95682055..12279bcb 100755 --- a/Robust/src/buildscript +++ b/Robust/src/buildscript @@ -64,6 +64,7 @@ NOJAVA=false CHECKFLAG=false RECOVERFLAG=false MLPFLAG=false +MLPDEBUG=false MULTICOREFLAG=false RAWFLAG=false RAWCACHEFLUSHFLAG=false @@ -229,9 +230,15 @@ JAVAOPTS="$JAVAOPTS -instructionfailures" elif [[ $1 = '-joptimize' ]] then JAVAOPTS="$JAVAOPTS -optimize" + elif [[ $1 = '-mlp' ]] then JAVAOPTS="$JAVAOPTS -mlp" + +elif [[ $1 = '-mlpdebug' ]] +then +JAVAOPTS="$JAVAOPTS -mlpdebug" + elif [[ $1 = '-check' ]] then CHECKFLAG=true -- 2.34.1