You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2018/06/14 03:12:21 UTC
[2/2] systemml git commit: [SYSTEMML-2393/4] Eliminate
side-effect-free functions w/ unused outputs
[SYSTEMML-2393/4] Eliminate side-effect-free functions w/ unused outputs
This patch extends the new IPA pass for dead code elimination by the
removal of side-effect-free function calls with unused outputs. As a
necessary precondition, we now track (in a best effort manner)
side-effect-free functions (explicitly annotated UDFs or DML-bodied
functions w/o prints/persistent writes or functions w/ side effects).
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/ea6dc8c5
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/ea6dc8c5
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/ea6dc8c5
Branch: refs/heads/master
Commit: ea6dc8c58e7f6d9cbe0b3e2c6cd638a6afad99d9
Parents: 2a1e857
Author: Matthias Boehm <mb...@gmail.com>
Authored: Wed Jun 13 20:12:00 2018 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Wed Jun 13 20:12:32 2018 -0700
----------------------------------------------------------------------
.../sysml/hops/ipa/FunctionCallGraph.java | 89 ++++++++++++++++++++
.../hops/ipa/IPAPassEliminateDeadCode.java | 27 ++++--
.../misc/IPADeadCodeEliminationTest.java | 32 ++++++-
.../functions/misc/IPADeadCodeRemoval_Fun2.dml | 31 +++++++
.../functions/misc/IPADeadCodeRemoval_Fun3.dml | 32 +++++++
5 files changed, 199 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/ea6dc8c5/src/main/java/org/apache/sysml/hops/ipa/FunctionCallGraph.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/ipa/FunctionCallGraph.java b/src/main/java/org/apache/sysml/hops/ipa/FunctionCallGraph.java
index b1bf301..e889703 100644
--- a/src/main/java/org/apache/sysml/hops/ipa/FunctionCallGraph.java
+++ b/src/main/java/org/apache/sysml/hops/ipa/FunctionCallGraph.java
@@ -32,6 +32,9 @@ import java.util.stream.Collectors;
import org.apache.sysml.hops.FunctionOp;
import org.apache.sysml.hops.Hop;
import org.apache.sysml.hops.HopsException;
+import org.apache.sysml.hops.Hop.DataOpTypes;
+import org.apache.sysml.hops.Hop.OpOp1;
+import org.apache.sysml.hops.Hop.OpOpN;
import org.apache.sysml.hops.rewrite.HopRewriteUtils;
import org.apache.sysml.parser.DMLProgram;
import org.apache.sysml.parser.ExternalFunctionStatement;
@@ -63,6 +66,9 @@ public class FunctionCallGraph
//subset of direct or indirect recursive functions
private final HashSet<String> _fRecursive;
+ //subset of side-effect-free functions
+ private final HashSet<String> _fSideEffectFree;
+
// a boolean value to indicate if exists the second order function (e.g. eval, paramserv)
// and the UDFs that are marked secondorder="true"
private final boolean _containsSecondOrder;
@@ -78,6 +84,7 @@ public class FunctionCallGraph
_fCalls = new HashMap<>();
_fCallsSB = new HashMap<>();
_fRecursive = new HashSet<>();
+ _fSideEffectFree = new HashSet<>();
_containsSecondOrder = constructFunctionCallGraph(prog);
}
@@ -92,6 +99,7 @@ public class FunctionCallGraph
_fCalls = new HashMap<>();
_fCallsSB = new HashMap<>();
_fRecursive = new HashSet<>();
+ _fSideEffectFree = new HashSet<>();
_containsSecondOrder = constructFunctionCallGraph(sb);
}
@@ -190,6 +198,33 @@ public class FunctionCallGraph
}
/**
+ * Indicates if the given function is side effect free, i.e., has no
+ * prints, no persistent write, and includes no or only calls to
+ * side-effect-free functions.
+ *
+ * @param fnamespace function namespace
+ * @param fname function name
+ * @return true if the given function is side-effect-free, false otherwise
+ */
+ public boolean isSideEffectFreeFunction(String fnamespace, String fname) {
+ return isSideEffectFreeFunction(
+ DMLProgram.constructFunctionKey(fnamespace, fname));
+ }
+
+ /**
+ * Indicates if the given function is side effect free, i.e., has no
+ * prints, no persistent write, and includes no or only calls to
+ * side-effect-free functions.
+ *
+ * @param fkey function key of calling function, null indicates the main program
+ * @return true if the given function is side-effect-free, false otherwise
+ */
+ public boolean isSideEffectFreeFunction(String fkey) {
+ String lfkey = (fkey == null) ? MAIN_FUNCTION_KEY : fkey;
+ return _fSideEffectFree.contains(lfkey);
+ }
+
+ /**
* Returns all functions that are reachable either directly or indirectly
* form the main program, except the main program itself.
*
@@ -255,11 +290,18 @@ public class FunctionCallGraph
boolean ret = false;
try {
+ //construct the main function call graph
Stack<String> fstack = new Stack<>();
HashSet<String> lfset = new HashSet<>();
_fGraph.put(MAIN_FUNCTION_KEY, new HashSet<String>());
for( StatementBlock sblk : prog.getStatementBlocks() )
ret |= rConstructFunctionCallGraph(MAIN_FUNCTION_KEY, sblk, fstack, lfset);
+
+ //analyze all non-recursive functions if free of side effects
+ _fSideEffectFree.addAll(_fCalls.keySet().stream()
+ .filter(s -> !s.startsWith(DMLProgram.INTERNAL_NAMESPACE))
+ .filter(s -> isSideEffectFree(prog.getFunctionStatementBlock(s)))
+ .collect(Collectors.toList()));
}
catch(HopsException ex) {
throw new RuntimeException(ex);
@@ -371,4 +413,51 @@ public class FunctionCallGraph
return ret;
}
+
+ private static boolean isSideEffectFree(FunctionStatementBlock fsb) {
+ //check for side-effect-free external functions (explicit annotation)
+ if( fsb.getStatement(0) instanceof ExternalFunctionStatement
+ && !((ExternalFunctionStatement)fsb.getStatement(0)).hasSideEffects() ) {
+ return true;
+ }
+ //check regular dml-bodied function for prints, pwrite, and other functions
+ FunctionStatement fstmt = (FunctionStatement) fsb.getStatement(0);
+ for( StatementBlock csb : fstmt.getBody() )
+ if( rHasSideEffects(csb) )
+ return false;
+ return true;
+ }
+
+ private static boolean rHasSideEffects(StatementBlock sb) {
+ boolean ret = false;
+ if( sb instanceof ForStatementBlock ) {
+ ForStatement fstmt = (ForStatement) sb.getStatement(0);
+ for( StatementBlock csb : fstmt.getBody() )
+ ret |= rHasSideEffects(csb);
+ }
+ else if( sb instanceof WhileStatementBlock ) {
+ WhileStatement wstmt = (WhileStatement) sb.getStatement(0);
+ for( StatementBlock csb : wstmt.getBody() )
+ ret |= rHasSideEffects(csb);
+ }
+ else if( sb instanceof IfStatementBlock ) {
+ IfStatement istmt = (IfStatement) sb.getStatement(0);
+ for( StatementBlock csb : istmt.getIfBody() )
+ ret |= rHasSideEffects(csb);
+ if( istmt.getElseBody() != null )
+ for( StatementBlock csb : istmt.getElseBody() )
+ ret |= rHasSideEffects(csb);
+ }
+ else if( sb.getHops() != null ) {
+ //check for print, printf, pwrite, function calls, all of
+ //which can only appear as root nodes in the DAG
+ for( Hop root : sb.getHops() ) {
+ ret |= HopRewriteUtils.isUnary(root, OpOp1.PRINT)
+ || HopRewriteUtils.isNary(root, OpOpN.PRINTF)
+ || HopRewriteUtils.isData(root, DataOpTypes.PERSISTENTWRITE)
+ || root instanceof FunctionOp;
+ }
+ }
+ return ret;
+ }
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/ea6dc8c5/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java b/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java
index 2fb4338..9ce79b0 100644
--- a/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java
+++ b/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java
@@ -19,10 +19,12 @@
package org.apache.sysml.hops.ipa;
+import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
+import org.apache.sysml.hops.FunctionOp;
import org.apache.sysml.hops.Hop;
import org.apache.sysml.hops.Hop.DataOpTypes;
import org.apache.sysml.hops.rewrite.HopRewriteUtils;
@@ -52,7 +54,7 @@ public class IPAPassEliminateDeadCode extends IPAPass
@Override
public void rewriteProgram( DMLProgram prog, FunctionCallGraph fgraph, FunctionCallSizeInfo fcallSizes ) {
// step 1: backwards pass over main program to track used and remove unused vars
- findAndRemoveDeadCode(prog.getStatementBlocks(), new HashSet<>());
+ findAndRemoveDeadCode(prog.getStatementBlocks(), new HashSet<>(), fgraph);
// step 2: backwards pass over functions to track used and remove unused vars
for( FunctionStatementBlock fsb : prog.getFunctionStatementBlocks() ) {
@@ -62,19 +64,19 @@ public class IPAPassEliminateDeadCode extends IPAPass
fstmt.getOutputParams().stream().forEach(d -> usedVars.add(d.getName()));
// backward pass over function to track used and remove unused vars
- findAndRemoveDeadCode(fstmt.getBody(), usedVars);
+ findAndRemoveDeadCode(fstmt.getBody(), usedVars, fgraph);
}
}
- private void findAndRemoveDeadCode(List<StatementBlock> sbs, Set<String> usedVars) {
+ private static void findAndRemoveDeadCode(List<StatementBlock> sbs, Set<String> usedVars, FunctionCallGraph fgraph) {
for( int i=sbs.size()-1; i >= 0; i-- ) {
// remove unused assignments
if( HopRewriteUtils.isLastLevelStatementBlock(sbs.get(i)) ) {
List<Hop> roots = sbs.get(i).getHops();
for( int j=0; j<roots.size(); j++ ) {
Hop root = roots.get(j);
- if( HopRewriteUtils.isData(root, DataOpTypes.TRANSIENTWRITE)
- && !usedVars.contains(root.getName()) ) {
+ if( (HopRewriteUtils.isData(root, DataOpTypes.TRANSIENTWRITE) && !usedVars.contains(root.getName()))
+ || isFunctionCallWithUnusedOutputs(root, usedVars, fgraph) ) {
roots.remove(j); j--;
rRemoveOpFromDAG(root);
}
@@ -88,7 +90,14 @@ public class IPAPassEliminateDeadCode extends IPAPass
}
}
- private void rRemoveOpFromDAG(Hop current) {
+ private static boolean isFunctionCallWithUnusedOutputs(Hop hop, Set<String> varNames, FunctionCallGraph fgraph) {
+ return hop instanceof FunctionOp
+ && fgraph.isSideEffectFreeFunction(((FunctionOp)hop).getFunctionKey())
+ && Arrays.stream(((FunctionOp) hop).getOutputVariableNames())
+ .allMatch(var -> !varNames.contains(var));
+ }
+
+ private static void rRemoveOpFromDAG(Hop current) {
for( int i=0; i<current.getInput().size(); i++ ) {
Hop c = current.getInput().get(i);
HopRewriteUtils.removeChildReference(current, c);
@@ -97,7 +106,7 @@ public class IPAPassEliminateDeadCode extends IPAPass
}
}
- private Set<String> rCollectReadVariableNames(StatementBlock sb, Set<String> varNames) {
+ private static Set<String> rCollectReadVariableNames(StatementBlock sb, Set<String> varNames) {
if( sb instanceof WhileStatementBlock ) {
WhileStatementBlock wsb = (WhileStatementBlock) sb;
WhileStatement wstmt = (WhileStatement) sb.getStatement(0);
@@ -132,14 +141,14 @@ public class IPAPassEliminateDeadCode extends IPAPass
return varNames;
}
- private Set<String> collectReadVariableNames(Hop hop, Set<String> varNames) {
+ private static Set<String> collectReadVariableNames(Hop hop, Set<String> varNames) {
if( hop == null )
return varNames;
hop.resetVisitStatus();
return rCollectReadVariableNames(hop, varNames);
}
- private Set<String> rCollectReadVariableNames(Hop hop, Set<String> varNames) {
+ private static Set<String> rCollectReadVariableNames(Hop hop, Set<String> varNames) {
if( hop.isVisited() )
return varNames;
for( Hop c : hop.getInput() )
http://git-wip-us.apache.org/repos/asf/systemml/blob/ea6dc8c5/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java b/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java
index 1516969..3afe992 100644
--- a/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java
+++ b/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java
@@ -31,6 +31,8 @@ public class IPADeadCodeEliminationTest extends AutomatedTestBase
{
private final static String TEST_NAME1 = "IPADeadCodeRemoval_Main";
private final static String TEST_NAME2 = "IPADeadCodeRemoval_Fun";
+ private final static String TEST_NAME3 = "IPADeadCodeRemoval_Fun2";
+ private final static String TEST_NAME4 = "IPADeadCodeRemoval_Fun3"; //w/ print
private final static String TEST_DIR = "functions/misc/";
private final static String TEST_CLASS_DIR = TEST_DIR + IPADeadCodeEliminationTest.class.getSimpleName() + "/";
@@ -38,8 +40,10 @@ public class IPADeadCodeEliminationTest extends AutomatedTestBase
@Override
public void setUp() {
TestUtils.clearAssertionInformation();
- addTestConfiguration( TEST_NAME1, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME1, new String[] { "R" }) );
- addTestConfiguration( TEST_NAME2, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME2, new String[] { "R" }) );
+ addTestConfiguration( TEST_NAME1, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME1, new String[] { "R" }) );
+ addTestConfiguration( TEST_NAME2, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME2, new String[] { "R" }) );
+ addTestConfiguration( TEST_NAME3, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME3, new String[] { "R" }) );
+ addTestConfiguration( TEST_NAME4, new TestConfiguration(TEST_CLASS_DIR, TEST_NAME4, new String[] { "R" }) );
}
@Test
@@ -61,6 +65,26 @@ public class IPADeadCodeEliminationTest extends AutomatedTestBase
public void testDeadCodeRemovalFunIPA() {
runIPALiteralReplacementTest( TEST_NAME2, true );
}
+
+ @Test
+ public void testDeadCodeRemovalFun2NoIPA() {
+ runIPALiteralReplacementTest( TEST_NAME3, false );
+ }
+
+ @Test
+ public void testDeadCodeRemovalFun2IPA() {
+ runIPALiteralReplacementTest( TEST_NAME3, true );
+ }
+
+ @Test
+ public void testDeadCodeRemovalFun3NoIPA() {
+ runIPALiteralReplacementTest( TEST_NAME4, false );
+ }
+
+ @Test
+ public void testDeadCodeRemovalFun3IPA() {
+ runIPALiteralReplacementTest( TEST_NAME4, true );
+ }
private void runIPALiteralReplacementTest( String testname, boolean IPA )
{
@@ -75,8 +99,10 @@ public class IPADeadCodeEliminationTest extends AutomatedTestBase
OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = IPA;
runTest(true, false, null, -1);
- if( IPA ) //check for applied dead code removal
+ if( IPA && !testname.equals(TEST_NAME4) ) //check for applied dead code removal
Assert.assertTrue(!heavyHittersContainsString("uak+"));
+ if( testname.equals(TEST_NAME4) )
+ Assert.assertTrue(heavyHittersContainsString("uak+"));
}
finally {
OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = oldFlagIPA;
http://git-wip-us.apache.org/repos/asf/systemml/blob/ea6dc8c5/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun2.dml
----------------------------------------------------------------------
diff --git a/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun2.dml b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun2.dml
new file mode 100644
index 0000000..e243ed3
--- /dev/null
+++ b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun2.dml
@@ -0,0 +1,31 @@
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+
+foo = function(matrix[double] A) return (matrix[double] B) {
+ C = A + 7;
+ while(FALSE){}
+ B = C + sum(A + C);
+}
+
+A = matrix(7, 10, 10);
+B = foo(A);
+if( 1 == 0 )
+ print("sum = "+sum(B));
http://git-wip-us.apache.org/repos/asf/systemml/blob/ea6dc8c5/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun3.dml
----------------------------------------------------------------------
diff --git a/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun3.dml b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun3.dml
new file mode 100644
index 0000000..9fa20db
--- /dev/null
+++ b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun3.dml
@@ -0,0 +1,32 @@
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+
+foo = function(matrix[double] A) return (matrix[double] B) {
+ C = A + 7;
+ while(FALSE){}
+ B = C + sum(A + C);
+ print(sum(B));
+}
+
+A = matrix(7, 10, 10);
+B = foo(A);
+if( 1 == 0 )
+ print("sum = "+sum(B));