From 0204ba8d05f0727780915c0923b9ce4e4e35cdda Mon Sep 17 00:00:00 2001 From: jjenista Date: Wed, 21 Oct 2009 21:36:59 +0000 Subject: [PATCH] Added feature for nullfying dead variables, which didn't change sharing for benchmarks. It is left in, but commented out, until we decide we need it. --- Robust/src/Analysis/Liveness.java | 15 ++++ Robust/src/Analysis/MLP/MLPAnalysis.java | 3 +- .../OwnershipAnalysis/OwnershipAnalysis.java | 53 +++++++++----- .../OwnershipAnalysis/OwnershipGraph.java | 31 +++++++++ .../Benchmarks/Ownership/evalNullifyDead.tex | 69 +++++++++++++++++++ Robust/src/Main/Main.java | 7 ++ 6 files changed, 160 insertions(+), 18 deletions(-) create mode 100644 Robust/src/Benchmarks/Ownership/evalNullifyDead.tex diff --git a/Robust/src/Analysis/Liveness.java b/Robust/src/Analysis/Liveness.java index 0c62d0b5..9f93732d 100644 --- a/Robust/src/Analysis/Liveness.java +++ b/Robust/src/Analysis/Liveness.java @@ -67,4 +67,19 @@ public class Liveness { } return liveoutmap; } + + + // Also allow an instantiation of this object that memoizes results + protected Hashtable< FlatMethod, Hashtable< FlatNode, Set > > fm2liveMap; + + public Liveness() { + fm2liveMap = new Hashtable< FlatMethod, Hashtable< FlatNode, Set > >(); + } + + public Set getLiveInTemps( FlatMethod fm, FlatNode fn ) { + if( !fm2liveMap.containsKey( fm ) ) { + fm2liveMap.put( fm, Liveness.computeLiveTemps( fm ) ); + } + return fm2liveMap.get( fm ).get( fn ); + } } \ No newline at end of file diff --git a/Robust/src/Analysis/MLP/MLPAnalysis.java b/Robust/src/Analysis/MLP/MLPAnalysis.java index db941a42..a26e2c6a 100644 --- a/Robust/src/Analysis/MLP/MLPAnalysis.java +++ b/Robust/src/Analysis/MLP/MLPAnalysis.java @@ -1,6 +1,7 @@ package Analysis.MLP; import Analysis.CallGraph.*; +import Analysis.Liveness; import Analysis.OwnershipAnalysis.*; import IR.*; import IR.Flat.*; @@ -199,7 +200,7 @@ public class MLPAnalysis { // disjoint analysis with a set of flagged allocation sites of live-in variable try { - OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph, + OwnershipAnalysis oa2 = new OwnershipAnalysis(state, tu, callGraph, new Liveness(), state.OWNERSHIPALLOCDEPTH, false, false, state.OWNERSHIPALIASFILE, state.METHODEFFECTS, diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index f7ff02f6..19862e12 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -1,6 +1,7 @@ package Analysis.OwnershipAnalysis; import Analysis.CallGraph.*; +import Analysis.Liveness; import IR.*; import IR.Flat.*; import IR.Tree.Modifiers; @@ -315,6 +316,7 @@ public class OwnershipAnalysis { // data from the compiler public State state; public CallGraph callGraph; + public Liveness liveness; public TypeUtil typeUtil; public int allocationDepth; @@ -393,27 +395,29 @@ public class OwnershipAnalysis { public OwnershipAnalysis(State state, TypeUtil tu, CallGraph callGraph, + Liveness liveness, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, String aliasFile) throws java.io.IOException { this.methodEffects = false; - init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); + init(state,tu,callGraph,liveness,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); } public OwnershipAnalysis(State state, - TypeUtil tu, - CallGraph callGraph, - int allocationDepth, - boolean writeDOTs, - boolean writeAllDOTs, - String aliasFile, - boolean methodEffects) throws java.io.IOException { + TypeUtil tu, + CallGraph callGraph, + Liveness liveness, + int allocationDepth, + boolean writeDOTs, + boolean writeAllDOTs, + String aliasFile, + boolean methodEffects) throws java.io.IOException { this.methodEffects = methodEffects; - init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); + init(state,tu,callGraph,liveness,allocationDepth,writeDOTs,writeAllDOTs,aliasFile); } @@ -422,6 +426,7 @@ public class OwnershipAnalysis { State state, TypeUtil tu, CallGraph callGraph, + Liveness liveness, int allocationDepth, boolean writeDOTs, boolean writeAllDOTs, @@ -432,24 +437,26 @@ public class OwnershipAnalysis { this.methodEffects = methodEffects; this.mapMethodContextToLiveInAllocationSiteSet=mapMethodContextToLiveInAllocationSiteSet; - init(state, tu, callGraph, allocationDepth, writeDOTs, writeAllDOTs, + init(state, tu, callGraph, liveness, allocationDepth, writeDOTs, writeAllDOTs, aliasFile); } private void init(State state, - TypeUtil tu, - CallGraph callGraph, - int allocationDepth, - boolean writeDOTs, - boolean writeAllDOTs, - String aliasFile) throws java.io.IOException { + TypeUtil tu, + CallGraph callGraph, + Liveness liveness, + int allocationDepth, + boolean writeDOTs, + boolean writeAllDOTs, + String aliasFile) throws java.io.IOException { analysisComplete = false; this.state = state; this.typeUtil = tu; this.callGraph = callGraph; + this.liveness = liveness; this.allocationDepth = allocationDepth; this.writeDOTs = writeDOTs; this.writeAllDOTs = writeAllDOTs; @@ -548,7 +555,7 @@ public class OwnershipAnalysis { meAnalysis.createNewMapping(mc); - og = analyzeFlatNode(mc, fm, null, og); + og = analyzeFlatNode(mc, fm, fm, null, og); setGraphForMethodContext(mc, og); } @@ -735,6 +742,7 @@ public class OwnershipAnalysis { // ownership graph made from the merge of the // parent graphs og = analyzeFlatNode(mc, + flatm, fn, returnNodesToCombineForCompleteOwnershipGraph, og); @@ -781,9 +789,19 @@ public class OwnershipAnalysis { private OwnershipGraph analyzeFlatNode(MethodContext mc, + FlatMethod fmContaining, FlatNode fn, HashSet setRetNodes, OwnershipGraph og) throws java.io.IOException { + + + // any variables that are no longer live should be + // nullified in the graph to reduce edges + // NOTE: it is not clear we need this. It costs a + // liveness calculation for every method, so only + // turn it on if we find we actually need it. + //og.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) ); + TempDescriptor lhs; TempDescriptor rhs; @@ -1070,6 +1088,7 @@ public class OwnershipAnalysis { setRetNodes.add(frn); break; } + Hashtable table=mapMethodContextToFlatNodeOwnershipGraph.get(mc); if(table==null){ diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index f2d1263e..6df454bc 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -75,6 +75,9 @@ public class OwnershipGraph { public Hashtable paramIndex2paramTokenSecondaryStar; + + + public OwnershipGraph() { id2hrn = new Hashtable(); @@ -299,6 +302,34 @@ public class OwnershipGraph { // of the nodes and edges involved. // //////////////////////////////////////////////////// + + public void nullifyDeadVars( Set liveIn ) { + + // make a set of the temps that are out of scope, don't + // consider them when nullifying dead in-scope variables + Set outOfScope = new HashSet(); + outOfScope.add( tdReturn ); + outOfScope.add( tdAliasBlob ); + outOfScope.addAll( paramIndex2tdQ.values() ); + outOfScope.addAll( paramIndex2tdR.values() ); + + Iterator varItr = td2ln.entrySet().iterator(); + while( varItr.hasNext() ) { + Map.Entry me = (Map.Entry) varItr.next(); + TempDescriptor td = (TempDescriptor) me.getKey(); + LabelNode ln = (LabelNode) me.getValue(); + + // if this variable is not out-of-scope or live + // in graph, nullify its references to anything + if( !outOfScope.contains( td ) && + !liveIn.contains( td ) + ) { + clearReferenceEdgesFrom( ln, null, null, true ); + } + } + } + + public void assignTempXEqualToTempY(TempDescriptor x, TempDescriptor y) { diff --git a/Robust/src/Benchmarks/Ownership/evalNullifyDead.tex b/Robust/src/Benchmarks/Ownership/evalNullifyDead.tex new file mode 100644 index 00000000..f6903fed --- /dev/null +++ b/Robust/src/Benchmarks/Ownership/evalNullifyDead.tex @@ -0,0 +1,69 @@ +\documentclass{article} +\begin{document} + +Nullfy dead means to remove references from variables when they are no +longer live. + +\section{Analysis without Nullify Dead} +\begin{tabular}{|l|l|r|r|r|} +\hline +Benchmark & Sharing & Time (s) & Lines & Methods \\ +\hline +Bank & 0 & 6.20 & 1827 & 67 \\ +Chat & 3 & 5.84 & 1512 & 71 \\ +Conglomerator & 0 & 3.84 & 1981 & 93 \\ +jHTTPp2 & 0 & 5.65 & 2585 & 122 \\ +MapReduce1 & 2 & 11.96 & 2276 & 114 \\ +MultiGame & 10 & 30.89 & 3005 & 46 \\ +Performance & 0 & 2.65 & 1762 & 30 \\ +PERT & 0 & 3.20 & 1952 & 61 \\ +FilterBank & 0 & 1.23 & 1323 & 9 \\ +Fractal & 1 & 1.43 & 1336 & 8 \\ +MolDynamics & 2 & 7.96 & 1904 & 31 \\ +MonteCarlo & 0 & 4.10 & 3544 & 49 \\ +Series & 0 & 1.24 & 1407 & 10 \\ +KMeans & 2 & 5.24 & 2661 & 45 \\ +MapReduce2 & 3 & 20.39 & 2220 & 95 \\ +FluidAnimate & 2 & 1045.30 & 3589 & 82 \\ +Spider1 & 0 & 7.01 & 1595 & 80 \\ +Spider2 & 0 & 7.62 & 1599 & 83 \\ +TileSearch & 0 & 8.24 & 2052 & 34 \\ +TicTacToe & 0 & 4.15 & 1534 & 68 \\ +WebServer1 & 0 & 7.81 & 1858 & 97 \\ +WebServer2 & 0 & 8.03 & 1857 & 100 \\ +\hline +\end{tabular} + + +\section{Using Nullify Dead} +\begin{tabular}{|l|l|r|r|r|} +\hline +Benchmark & Sharing & Time (s) & Lines & Methods \\ +\hline +Bank & 0 & 5.70 & 1827 & 67 \\ +Chat & 3 & 5.60 & 1512 & 71 \\ +Conglomerator & 0 & 5.42 & 1981 & 93 \\ +jHTTPp2 & 0 & 6.45 & 2585 & 122 \\ +MapReduce1 & 2 & 11.68 & 2276 & 114 \\ +MultiGame & 10 & 22.27 & 3005 & 46 \\ +Performance & 0 & 2.74 & 1762 & 30 \\ +PERT & 0 & 4.24 & 1952 & 61 \\ +FilterBank & 0 & 1.56 & 1323 & 9 \\ +Fractal & 1 & 1.26 & 1336 & 8 \\ +MolDynamics & 2 & 6.58 & 1904 & 31 \\ +MonteCarlo & 0 & 4.24 & 3544 & 49 \\ +Series & 0 & 1.70 & 1407 & 10 \\ +KMeans & 2 & 5.51 & 2661 & 45 \\ +MapReduce2 & 3 & 17.76 & 2220 & 95 \\ +FluidAnimate & 2 & 164.37 & 3589 & 82 \\ +Spider1 & 0 & 6.58 & 1595 & 80 \\ +Spider2 & 0 & 6.24 & 1599 & 83 \\ +TileSearch & 0 & 8.18 & 2052 & 34 \\ +TicTacToe & 0 & 5.16 & 1534 & 68 \\ +WebServer1 & 0 & 6.79 & 1858 & 97 \\ +WebServer2 & 0 & 6.45 & 1857 & 100 \\ +\hline +\end{tabular} + + +\end{document} diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 4ee1bcd2..a4e54b0d 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -43,6 +43,7 @@ import Analysis.FlatIRGraph.FlatIRGraph; import Analysis.OwnershipAnalysis.OwnershipAnalysis; import Analysis.MLP.MLPAnalysis; import Analysis.Loops.*; +import Analysis.Liveness; import IR.MethodDescriptor; import IR.Flat.FlatMethod; import Interface.*; @@ -347,9 +348,11 @@ public class Main { if (state.OWNERSHIP && !state.MLP) { CallGraph callGraph = new CallGraph(state); + Liveness liveness = new Liveness(); OwnershipAnalysis oa = new OwnershipAnalysis(state, tu, callGraph, + liveness, state.OWNERSHIPALLOCDEPTH, state.OWNERSHIPWRITEDOTS, state.OWNERSHIPWRITEALL, @@ -359,9 +362,11 @@ public class Main { if (state.MLP) { CallGraph callGraph = new CallGraph(state); + Liveness liveness = new Liveness(); OwnershipAnalysis oa = new OwnershipAnalysis(state, tu, callGraph, + liveness, state.OWNERSHIPALLOCDEPTH, state.OWNERSHIPWRITEDOTS, state.OWNERSHIPWRITEALL, @@ -406,9 +411,11 @@ public class Main { if (state.SCHEDULING) { // Use ownership analysis to get alias information CallGraph callGraph = new CallGraph(state); + Liveness liveness = new Liveness(); OwnershipAnalysis oa = new OwnershipAnalysis(state, tu, callGraph, + liveness, state.OWNERSHIPALLOCDEPTH, state.OWNERSHIPWRITEDOTS, state.OWNERSHIPWRITEALL, -- 2.34.1