more new mlp stuff
authorjjenista <jjenista>
Thu, 9 Apr 2009 21:20:30 +0000 (21:20 +0000)
committerjjenista <jjenista>
Thu, 9 Apr 2009 21:20:30 +0000 (21:20 +0000)
Robust/src/Analysis/MLP/MLPAnalysis.java
Robust/src/Analysis/MLP/SVKey.java [new file with mode: 0644]
Robust/src/Analysis/MLP/VarSrcTokTable.java [new file with mode: 0644]
Robust/src/Analysis/MLP/VariableSourceToken.java
Robust/src/IR/State.java
Robust/src/Main/Main.java
Robust/src/Makefile
Robust/src/Tests/mlp/tinyTest/makefile
Robust/src/Tests/mlp/tinyTest/test.java
Robust/src/buildscript

index 27c3921e4c5eef20af9a10a2565b43a85aea7c24..1f3611ad1ec857b83a6f4e35dcb362adc5271c91 100644 (file)
@@ -20,6 +20,8 @@ public class MLPAnalysis {
   private Stack<FlatSESEEnterNode> seseStack;
   private Set<FlatSESEEnterNode>   seseRoots;
 
+  private Hashtable< FlatNode, Set<VariableSourceToken> > pointResults;
+
 
   public MLPAnalysis( State state,
                      TypeUtil tu,
@@ -38,6 +40,9 @@ public class MLPAnalysis {
     seseStack = new Stack  <FlatSESEEnterNode>();
     seseRoots = new HashSet<FlatSESEEnterNode>();
 
+    pointResults = new Hashtable< FlatNode, Set<VariableSourceToken> >();
+
+
     // run analysis on each method that is actually called
     // reachability analysis already computed this so reuse
     Iterator<Descriptor> 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<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
     flatNodesToVisit.add( fm );
 
     Set<FlatNode> visited = new HashSet<FlatNode>();
 
     while( !flatNodesToVisit.isEmpty() ) {
-      FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+      Iterator<FlatNode> 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<VariableSourceToken>() );
 
       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<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+    flatNodesToVisit.add( fsen.getFlatExit() );
+
+    while( !flatNodesToVisit.isEmpty() ) {
+      FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+      flatNodesToVisit.remove( fn );      
+
+      Set<VariableSourceToken> prev = pointResults.get( fn );
+
+      // merge sets from control flow joins
+      Set<VariableSourceToken> merge = new HashSet<VariableSourceToken>();
+      for( int i = 0; i < fn.numNext(); i++ ) {
+       FlatNode nn = fn.getNext( i );   
+       merge = mergeVSTsets( merge, pointResults.get( nn ) );
+      }
+
+      Set<VariableSourceToken> 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<VariableSourceToken> 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<VariableSourceToken> analyzeFlatNode( FlatNode fn, 
+                                                   boolean buildForest,
+                                                   Set<VariableSourceToken> 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<VariableSourceToken> vstNew = new HashSet<VariableSourceToken>();
+         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<VariableSourceToken> killTemp( Set<VariableSourceToken> s,
+                                            TempDescriptor t ) {
+    Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
+
+    Iterator<VariableSourceToken> vstitr = s.iterator();
+    while( vstitr.hasNext() ) {
+      VariableSourceToken vst = vstitr.next();    
+
+      if( !vst.getVar().equals( t ) ) {
+       out.add( vst );
+      }
+    }
+
+    return out;
+  }
+
+
+  private Set<VariableSourceToken> mergeVSTsets( Set<VariableSourceToken> s1,
+                                                Set<VariableSourceToken> s2 ) {
+    
+    Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
+
+    Iterator<VariableSourceToken> vst1itr = s1.iterator();
+    while( vst1itr.hasNext() ) {
+      VariableSourceToken vst1 = vst1itr.next();
+
+      int changeAge = -1;
+      
+      Iterator<VariableSourceToken> 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<VariableSourceToken> 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 (file)
index 0000000..afc53d0
--- /dev/null
@@ -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 (file)
index 0000000..145c829
--- /dev/null
@@ -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<VariableSourceToken> > sese2vst;
+  private Hashtable< TempDescriptor,    Set<VariableSourceToken> >  var2vst;
+  private Hashtable< SVKey,             Set<VariableSourceToken> >   sv2vst;
+
+  public VarSrcTokTable() {
+    sese2vst = new Hashtable< FlatSESEEnterNode, Set<VariableSourceToken> >();
+    var2vst  = new Hashtable< TempDescriptor,    Set<VariableSourceToken> >();
+    sv2vst   = new Hashtable< SVKey,             Set<VariableSourceToken> >();
+  }
+
+
+  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+"]";
+  }
+}
index fe43742a2cf740c2bdb5bf04c9bc0a1f4ab11cc8..089ea9144e79ff3929b202a07f7d5614860051dc 100644 (file)
@@ -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+"]";
   }
 }
index e7cc04d541280cc1dd77c7b8658117b294434c5c..48e33c4c5098d7d63eeafbf5e7624dc664bc9725 100644 (file)
@@ -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;
index a6b88127cb8bfc8879ae43586581993a1159f6cd..7445190670ba1a9588f65b7611f2bd4645ad271c 100644 (file)
@@ -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,
index a86f8fe880d604b766c9ce295ed41a7b4bd5b358..51b7b93da2d9cad532b61ac049b8b654d705489f 100644 (file)
@@ -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               \
index a62898aef2670167777f853c133bcf3cba55a041..d23651f8acd46a89654d0c115da0e4778f2ccaae 100644 (file)
@@ -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
 
index ae8d3f13706de628dc52daebd63b9b9b228603e8..c870a9ce5f7267d6fa5bc2df5eb0203ee4a7deb3 100644 (file)
@@ -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;    
   }
 }
index 95682055ffe21cd5820706195be5e743ba2465cf..12279bcb7ba793f1f8065605ffc137123856ee73 100755 (executable)
@@ -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