From 8348531b6d79c4af6112182748496de616933326 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 5 Apr 2010 20:44:09 +0000 Subject: [PATCH] implemented stack method visit but with callees on top, something crazy is happening to sharing for ALL visit methods... --- .../Analysis/Disjoint/DisjointAnalysis.java | 76 ++++++++-- .../Benchmarks/disjoint/expectedSharing.tex | 76 ++++++++++ .../disjoint/genTable-all-benchmarks.sh | 141 ++++++++++++++++++ ...eTable.sh => genTable-paper-benchmarks.sh} | 18 +-- Robust/src/Benchmarks/disjoint/makefile | 4 + Robust/src/IR/State.java | 1 + Robust/src/Main/Main.java | 15 +- 7 files changed, 308 insertions(+), 23 deletions(-) create mode 100644 Robust/src/Benchmarks/disjoint/expectedSharing.tex create mode 100755 Robust/src/Benchmarks/disjoint/genTable-all-benchmarks.sh rename Robust/src/Benchmarks/disjoint/{makeTable.sh => genTable-paper-benchmarks.sh} (93%) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index b073e3ab..e8e6b296 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -380,6 +380,13 @@ public class DisjointAnalysis { protected Hashtable mapDescriptorToPriority; + // when analyzing a method and scheduling more: + // remember set of callee's enqueued for analysis + // so they can be put on top of the callers in + // the stack-visit mode + protected Set + calleesToEnqueue; + // maps a descriptor to its current partial result // from the intraprocedural fixed-point analysis-- @@ -484,7 +491,9 @@ public class DisjointAnalysis { mapTypeToArrayField = new Hashtable (); - if( state.DISJOINTDVISITSTACK ) { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { descriptorsToVisitStack = new Stack(); } @@ -500,6 +509,9 @@ public class DisjointAnalysis { mapDescriptorToPriority = new Hashtable(); + calleesToEnqueue = + new HashSet(); + mapDescriptorToAllocSiteSet = new Hashtable >(); @@ -549,8 +561,13 @@ public class DisjointAnalysis { this.snapNodeCounter = 0; // count nodes from 0 this.pm=new PointerMethod(); - assert state.DISJOINTDVISITSTACK || state.DISJOINTDVISITPQUE; + assert + state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITPQUE || + state.DISJOINTDVISITSTACKEESONTOP; assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITPQUE); + assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITSTACKEESONTOP); + assert !(state.DISJOINTDVISITPQUE && state.DISJOINTDVISITSTACKEESONTOP); // set some static configuration for ReachGraphs ReachGraph.allocationDepth = allocationDepth; @@ -596,7 +613,9 @@ public class DisjointAnalysis { protected boolean moreDescriptorsToVisit() { - if( state.DISJOINTDVISITSTACK ) { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { return !descriptorsToVisitStack.isEmpty(); } else if( state.DISJOINTDVISITPQUE ) { @@ -660,7 +679,9 @@ public class DisjointAnalysis { mapDescriptorToPriority.put( d, new Integer( p ) ); - if( state.DISJOINTDVISITSTACK ) { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { descriptorsToVisitStack.add( new DescriptorQWrapper( p, d ) ); } else if( state.DISJOINTDVISITPQUE ) { @@ -675,7 +696,9 @@ public class DisjointAnalysis { while( moreDescriptorsToVisit() ) { Descriptor d = null; - if( state.DISJOINTDVISITSTACK ) { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { d = descriptorsToVisitStack.pop().getDescriptor(); } else if( state.DISJOINTDVISITPQUE ) { @@ -695,6 +718,10 @@ public class DisjointAnalysis { System.out.println( "Analyzing " + d ); + if( state.DISJOINTDVISITSTACKEESONTOP ) { + assert calleesToEnqueue.isEmpty(); + } + ReachGraph rg = analyzeMethod( d ); ReachGraph rgPrev = getPartial( d ); @@ -708,7 +735,25 @@ public class DisjointAnalysis { Descriptor dNext = depsItr.next(); enqueue( dNext ); } - } + + if( state.DISJOINTDVISITSTACKEESONTOP ) { + depsItr = calleesToEnqueue.iterator(); + while( depsItr.hasNext() ) { + Descriptor dNext = depsItr.next(); + enqueue( dNext ); + } + calleesToEnqueue.clear(); + } + + } else { + // we got the result result as the last visit + // to this method, but we might need to clean + // something up + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.clear(); + } + } + } } @@ -1054,10 +1099,14 @@ public class DisjointAnalysis { // if heap at call site changed, update the contribution, // and reschedule the callee for analysis addIHMcontribution( mdCallee, fc, heapForThisCall_cur ); - enqueue( mdCallee ); - } + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdCallee ); + } else { + enqueue( mdCallee ); + } + } // the transformation for a call site should update the @@ -1097,7 +1146,12 @@ public class DisjointAnalysis { if( rgEffect == null ) { // if this method has never been analyzed just schedule it // for analysis and skip over this call site for now - enqueue( mdPossible ); + if( state.DISJOINTDVISITSTACKEESONTOP ) { + calleesToEnqueue.add( mdPossible ); + } else { + enqueue( mdPossible ); + } + } else { rgCopy.resolveMethodCall( fc, fmPossible, @@ -1426,7 +1480,9 @@ public class DisjointAnalysis { if( !descriptorsToVisitSet.contains( d ) ) { Integer priority = mapDescriptorToPriority.get( d ); - if( state.DISJOINTDVISITSTACK ) { + if( state.DISJOINTDVISITSTACK || + state.DISJOINTDVISITSTACKEESONTOP + ) { descriptorsToVisitStack.add( new DescriptorQWrapper( priority, d ) ); diff --git a/Robust/src/Benchmarks/disjoint/expectedSharing.tex b/Robust/src/Benchmarks/disjoint/expectedSharing.tex new file mode 100644 index 00000000..532271b2 --- /dev/null +++ b/Robust/src/Benchmarks/disjoint/expectedSharing.tex @@ -0,0 +1,76 @@ +\documentclass{amsart}[9pt] +\usepackage{color} +\begin{document} + + +\section{Current Sharing} + +\begin{tabular}{|l|c|c|c|c|} +\hline +Benchmark & Ownership & Disjoint & Disjoint & Disjoint Stack \\ + & Sharing & Stack & Queue & Callees on top \\ +\hline +Bank & 0 & 0 & 0 & \\ +Chat & 3 & 0 & 3 & \\ +WebPortal & 0 & 0 & 0 & \\ +jHTTPp2 & 0 & 0 & 0 & \\ +MapReduce1 & 2 & \color{red}{1} & \color{red}{1}& \\ +MultiGame & 10 & 10 & 10 & \\ +PERT & 0 & 0 & 0 & \\ +FilterBank & 0 & 0 & 0 & \\ +Fractal & 1 & 1 & 1 & \\ +MolDyn & 2 & 2 & 2 & \\ +MonteCarlo & 0 & 0 & 0 & \\ +Series & 0 & 0 & 0 & \\ +KMeans-Bamboo & 2 & 2 & 2 & \\ +MapReduce2 & 3 & \color{red}{0} & \color{red}{0}& \\ +FluidAnimate & 2 & \color{red}{error}& 2 & \\ +Spider1 & 0 & 0 & 0 & \\ +Spider2 & 0 & \color{red}{error}& 0 & \\ +TileSearch & 0 & 0 & 0 & \\ +TicTacToe & 0 & \color{red}{error}& 0 & \\ +WebServer1 & 0 & 0 & 0 & \\ +WebServer2 & 0 & \color{red}{error}& 0 & \\ +Tracking & 0 & 0 & 0 & \\ +\hline +\end{tabular} + + + +\section{Current Analysis Runtimes} +These times were measured on DC-11. + +\begin{tabular}{|l|c|c|c|c|} +\hline +Benchmark & Ownership & Disjoint & Disjoint & Disjoint Stack \\ + & Sharing & Stack & Queue & Callees on top \\ +\hline +Bank & & & & \\ +Chat & & & & \\ +WebPortal & & & & \\ +jHTTPp2 & & & & \\ +MapReduce1 & & & & \\ +MultiGame & & & & \\ +PERT & & & & \\ +FilterBank & & & & \\ +Fractal & & & & \\ +MolDyn & & & & \\ +MonteCarlo & & & & \\ +Series & & & & \\ +KMeans-Bamboo & & & & \\ +MapReduce2 & & & & \\ +FluidAnimate & & & & \\ +Spider1 & & & & \\ +Spider2 & & & & \\ +TileSearch & & & & \\ +TicTacToe & & & & \\ +WebServer1 & & & & \\ +WebServer2 & & & & \\ +Tracking & & & & \\ +\hline +\end{tabular} + + + + +\end{document} diff --git a/Robust/src/Benchmarks/disjoint/genTable-all-benchmarks.sh b/Robust/src/Benchmarks/disjoint/genTable-all-benchmarks.sh new file mode 100755 index 00000000..925f5dde --- /dev/null +++ b/Robust/src/Benchmarks/disjoint/genTable-all-benchmarks.sh @@ -0,0 +1,141 @@ +#!/bin/bash + +num="0" + +NAME[$num]=Bank +BDIR[$num]=BankApp +num=$[$num+1] + +NAME[$num]=Chat +BDIR[$num]=ChatTag +num=$[$num+1] + +NAME[$num]=WebPortal +BDIR[$num]=Conglomerator/Tag +num=$[$num+1] + +NAME[$num]=jHTTPp2 +BDIR[$num]=Jhttpp2/BR +num=$[$num+1] + +NAME[$num]=MapReduce1 +BDIR[$num]=MapReduce/Tag +num=$[$num+1] + +NAME[$num]=MultiGame +BDIR[$num]=MMG/Tag +num=$[$num+1] + +NAME[$num]=PERT +BDIR[$num]=PERT/Tag +num=$[$num+1] + +NAME[$num]=FilterBank +BDIR[$num]=Scheduling/FilterBank +num=$[$num+1] + +NAME[$num]=Fractal +BDIR[$num]=Scheduling/Fractal +num=$[$num+1] + +NAME[$num]=MolDyn +BDIR[$num]=Scheduling/JGFMolDyn +num=$[$num+1] + +NAME[$num]=MonteCarlo +BDIR[$num]=Scheduling/JGFMonteCarlo +num=$[$num+1] + +NAME[$num]=Series +BDIR[$num]=Scheduling/JGFSeries +num=$[$num+1] + +NAME[$num]=KMeans-Bamboo +BDIR[$num]=Scheduling/KMeans +num=$[$num+1] + +NAME[$num]=MapReduce2 +BDIR[$num]=Scheduling/MapReduce +num=$[$num+1] + +NAME[$num]=FluidAnimate +BDIR[$num]=Scheduling/PSFluidAnimate +num=$[$num+1] + +NAME[$num]=Spider1 +BDIR[$num]=Spider/BR +num=$[$num+1] + +NAME[$num]=Spider2 +BDIR[$num]=Spider/BRTag +num=$[$num+1] + +NAME[$num]=TileSearch +BDIR[$num]=TileSearch/Tag +num=$[$num+1] + +NAME[$num]=TicTacToe +BDIR[$num]=TTTTag +num=$[$num+1] + +NAME[$num]=WebServer1 +BDIR[$num]=WebServer +num=$[$num+1] + +NAME[$num]=WebServer2 +BDIR[$num]=WebServerTag +num=$[$num+1] + +NAME[$num]=Tracking +BDIR[$num]=Scheduling/Tracking +num=$[$num+1] + + + +########################### +# No need to modify below! +########################### + +BENCHTOP=~/research/Robust/src/Benchmarks +BENCHSUM=$BENCHTOP/disjoint + +TABFILE=tabResults.tex +rm -f $TABFILE +touch $TABFILE +echo '\begin{tabular}{|l|l|r|r|r|}' >> $TABFILE +echo '\hline' >> $TABFILE +echo 'Benchmark & Sharing & Time (s) & Lines & Methods \\' >> $TABFILE +echo '\hline' >> $TABFILE + +i="0" +while [ $i -lt $num ]; do + cd $BENCHTOP/${BDIR[$i]} + # unfortunately this echo adds an unwanted newline + echo ${NAME[$i]} >> $BENCHSUM/$TABFILE + make -f $BENCHSUM/makefile bamboo-release + cat aliases.txt >> $BENCHSUM/$TABFILE + make -f $BENCHSUM/makefile clean + i=$[$i+1] +done + +cd $BENCHSUM + +echo '\hline' >> $TABFILE +echo '\end{tabular}' >> $TABFILE + +# remove unwanted newlines from file so latex doesn't barf +sed ' +/$/ { +# append the next line + N +# look for multi-line pattern + /\n \&/ { +# delete everything between + s/\n \&/ \&/ +# print + P +# then delete the first line + D + } +}' <$TABFILE >$TABFILE.temp +mv $TABFILE.temp $TABFILE diff --git a/Robust/src/Benchmarks/disjoint/makeTable.sh b/Robust/src/Benchmarks/disjoint/genTable-paper-benchmarks.sh similarity index 93% rename from Robust/src/Benchmarks/disjoint/makeTable.sh rename to Robust/src/Benchmarks/disjoint/genTable-paper-benchmarks.sh index 4fed125e..c9a5eca0 100755 --- a/Robust/src/Benchmarks/disjoint/makeTable.sh +++ b/Robust/src/Benchmarks/disjoint/genTable-paper-benchmarks.sh @@ -22,9 +22,9 @@ num=$[$num+1] #BDIR[$num]=MapReduce/Tag #num=$[$num+1] -#NAME[$num]=MultiGame -#BDIR[$num]=MMG/Tag -#num=$[$num+1] +NAME[$num]=MultiGame +BDIR[$num]=MMG/Tag +num=$[$num+1] #NAME[$num]=PERT #BDIR[$num]=PERT/Tag @@ -54,9 +54,9 @@ NAME[$num]=KMeans-Bamboo BDIR[$num]=Scheduling/KMeans num=$[$num+1] -#NAME[$num]=FluidAnimate -#BDIR[$num]=Scheduling/PSFluidAnimate -#num=$[$num+1] +NAME[$num]=FluidAnimate +BDIR[$num]=Scheduling/PSFluidAnimate +num=$[$num+1] NAME[$num]=Spider BDIR[$num]=Spider/BR @@ -66,9 +66,9 @@ num=$[$num+1] #BDIR[$num]=TileSearch/Tag #num=$[$num+1] -NAME[$num]=TicTacToe -BDIR[$num]=TTTTag -num=$[$num+1] +#NAME[$num]=TicTacToe +#BDIR[$num]=TTTTag +#num=$[$num+1] NAME[$num]=WebServer BDIR[$num]=WebServer diff --git a/Robust/src/Benchmarks/disjoint/makefile b/Robust/src/Benchmarks/disjoint/makefile index 9265730d..0f3f9544 100644 --- a/Robust/src/Benchmarks/disjoint/makefile +++ b/Robust/src/Benchmarks/disjoint/makefile @@ -34,6 +34,7 @@ JAVAFLAGS= -mainclass test VISITMODE= -disjoint-dvisit-stack #VISITMODE= -disjoint-dvisit-pqueue +#VISITMODE= -disjoint-dvisit-stack-callees-on-top DEBUGMODE= -enable-assertions -disjoint-write-dots final -disjoint-alias-file aliases.txt normal RELEASEMODE= -disjoint-release-mode -disjoint-alias-file aliases.txt tabbed @@ -52,6 +53,9 @@ bamboo-s: bamboo-q: $(BUILDSCRIPT) $(BAMBOOFLAGS) $(DEBUGMODE) -disjoint-dvisit-pqueue $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java +bamboo-sees: + $(BUILDSCRIPT) $(BAMBOOFLAGS) $(DEBUGMODE) -disjoint-dvisit-stack-callees-on-top $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java + bamboo-release: $(BUILDSCRIPT) $(BAMBOOFLAGS) $(RELEASEMODE) $(VISITMODE) $(BSFLAGS) $(DEBUGFLAGS) $(SNAPFLAGS) *.java diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index 065c72c7..3248253f 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -85,6 +85,7 @@ public class State { public boolean DISJOINTSNAPSTOPAFTER=false; public boolean DISJOINTDVISITSTACK=true; public boolean DISJOINTDVISITPQUE=false; + public boolean DISJOINTDVISITSTACKEESONTOP=false; public boolean OPTIONAL=false; public boolean ARRAYPAD=false; diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 7dee49c0..5d63f7b1 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -221,12 +221,19 @@ public class Main { state.DISJOINTRELEASEMODE = true; } else if( option.equals( "-disjoint-dvisit-stack" ) ) { - state.DISJOINTDVISITSTACK = true; - state.DISJOINTDVISITPQUE = false; + state.DISJOINTDVISITSTACK = true; + state.DISJOINTDVISITPQUE = false; + state.DISJOINTDVISITSTACKEESONTOP = false; } else if( option.equals( "-disjoint-dvisit-pqueue" ) ) { - state.DISJOINTDVISITPQUE = true; - state.DISJOINTDVISITSTACK = false; + state.DISJOINTDVISITPQUE = true; + state.DISJOINTDVISITSTACK = false; + state.DISJOINTDVISITSTACKEESONTOP = false; + + } else if( option.equals( "-disjoint-dvisit-stack-callees-on-top" ) ) { + state.DISJOINTDVISITSTACKEESONTOP = true; + state.DISJOINTDVISITPQUE = false; + state.DISJOINTDVISITSTACK = false; } -- 2.34.1