Repository: systemml Updated Branches: refs/heads/master ebfe327e4 -> ea6dc8c58
[SYSTEMML-2391] New IPA pass for additional dead code elimination Dead code elimination implicitly happens on HOP DAG construction and according to the data flow analysis of used variables. However, with IPA and rewrites additional branches and function calls might get removed which sometimes creates additional opportunities for dead code elimination. Therefore, this patch adds an additional IPA pass for explicit dead code elimination across statement blocks in the main program and individual functions. Furthermore, this also includes improved rewrites for DAG splits to properly maintain the read variables of artificial block-crossing variables. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/2a1e8570 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/2a1e8570 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/2a1e8570 Branch: refs/heads/master Commit: 2a1e85707690b8ee96053c479b1a005e9bd95434 Parents: ebfe327 Author: Matthias Boehm <[email protected]> Authored: Wed Jun 13 16:35:37 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Wed Jun 13 20:12:28 2018 -0700 ---------------------------------------------------------------------- .../hops/ipa/IPAPassEliminateDeadCode.java | 152 +++++++++++++++++++ .../sysml/hops/ipa/InterProceduralAnalysis.java | 2 + .../RewriteSplitDagDataDependentOperators.java | 11 +- .../misc/IPADeadCodeEliminationTest.java | 85 +++++++++++ .../functions/misc/IPADeadCodeRemoval_Fun.dml | 32 ++++ .../functions/misc/IPADeadCodeRemoval_Main.dml | 27 ++++ .../functions/misc/ZPackageSuite.java | 1 + 7 files changed, 303 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/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 new file mode 100644 index 0000000..2fb4338 --- /dev/null +++ b/src/main/java/org/apache/sysml/hops/ipa/IPAPassEliminateDeadCode.java @@ -0,0 +1,152 @@ +/* + * 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. + */ + +package org.apache.sysml.hops.ipa; + +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.apache.sysml.hops.Hop; +import org.apache.sysml.hops.Hop.DataOpTypes; +import org.apache.sysml.hops.rewrite.HopRewriteUtils; +import org.apache.sysml.parser.DMLProgram; +import org.apache.sysml.parser.ForStatement; +import org.apache.sysml.parser.ForStatementBlock; +import org.apache.sysml.parser.FunctionStatement; +import org.apache.sysml.parser.FunctionStatementBlock; +import org.apache.sysml.parser.IfStatement; +import org.apache.sysml.parser.IfStatementBlock; +import org.apache.sysml.parser.StatementBlock; +import org.apache.sysml.parser.WhileStatement; +import org.apache.sysml.parser.WhileStatementBlock; + +/** + * This rewrite eliminates unnecessary sub-DAGs that produce + * transient write outputs which are never consumed subsequently. + * + */ +public class IPAPassEliminateDeadCode extends IPAPass +{ + @Override + public boolean isApplicable(FunctionCallGraph fgraph) { + return InterProceduralAnalysis.ELIMINATE_DEAD_CODE; + } + + @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<>()); + + // step 2: backwards pass over functions to track used and remove unused vars + for( FunctionStatementBlock fsb : prog.getFunctionStatementBlocks() ) { + // mark function outputs as used variables + Set<String> usedVars = new HashSet<>(); + FunctionStatement fstmt = (FunctionStatement) fsb.getStatement(0); + fstmt.getOutputParams().stream().forEach(d -> usedVars.add(d.getName())); + + // backward pass over function to track used and remove unused vars + findAndRemoveDeadCode(fstmt.getBody(), usedVars); + } + } + + private void findAndRemoveDeadCode(List<StatementBlock> sbs, Set<String> usedVars) { + 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()) ) { + roots.remove(j); j--; + rRemoveOpFromDAG(root); + } + } + } + + // maintain used variables (in terms of existing transient reads because + // other rewrites such as simplification, DAG splits, and code motion might + // have removed/added reads and not consistently updated variablesRead() + usedVars.addAll(rCollectReadVariableNames(sbs.get(i), new HashSet<>())); + } + } + + private void rRemoveOpFromDAG(Hop current) { + for( int i=0; i<current.getInput().size(); i++ ) { + Hop c = current.getInput().get(i); + HopRewriteUtils.removeChildReference(current, c); + if( c.getParent().isEmpty() ) + rRemoveOpFromDAG(c); + } + } + + private Set<String> rCollectReadVariableNames(StatementBlock sb, Set<String> varNames) { + if( sb instanceof WhileStatementBlock ) { + WhileStatementBlock wsb = (WhileStatementBlock) sb; + WhileStatement wstmt = (WhileStatement) sb.getStatement(0); + collectReadVariableNames(wsb.getPredicateHops(), varNames); + for( StatementBlock csb : wstmt.getBody() ) + rCollectReadVariableNames(csb, varNames); + } + else if( sb instanceof ForStatementBlock ) { + ForStatementBlock fsb = (ForStatementBlock) sb; + ForStatement fstmt = (ForStatement) sb.getStatement(0); + collectReadVariableNames(fsb.getFromHops(), varNames); + collectReadVariableNames(fsb.getToHops(), varNames); + collectReadVariableNames(fsb.getIncrementHops(), varNames); + for( StatementBlock csb : fstmt.getBody() ) + rCollectReadVariableNames(csb, varNames); + } + else if( sb instanceof IfStatementBlock ) { + IfStatementBlock isb = (IfStatementBlock) sb; + IfStatement istmt = (IfStatement) sb.getStatement(0); + collectReadVariableNames(isb.getPredicateHops(), varNames); + for( StatementBlock csb : istmt.getIfBody() ) + rCollectReadVariableNames(csb, varNames); + if( istmt.getElseBody() != null ) + for( StatementBlock csb : istmt.getElseBody() ) + rCollectReadVariableNames(csb, varNames); + } + else if( sb.getHops() != null ) { + Hop.resetVisitStatus(sb.getHops()); + for( Hop hop : sb.getHops() ) + rCollectReadVariableNames(hop, varNames); + } + return varNames; + } + + private 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) { + if( hop.isVisited() ) + return varNames; + for( Hop c : hop.getInput() ) + rCollectReadVariableNames(c, varNames); + if( HopRewriteUtils.isData(hop, DataOpTypes.TRANSIENTREAD) ) + varNames.add(hop.getName()); + hop.isVisited(); + return varNames; + } +} http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java index 463a531..a46e841 100644 --- a/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java +++ b/src/main/java/org/apache/sysml/hops/ipa/InterProceduralAnalysis.java @@ -96,6 +96,7 @@ public class InterProceduralAnalysis protected static final boolean PROPAGATE_SCALAR_LITERALS = true; //propagate and replace scalar literals into functions protected static final boolean APPLY_STATIC_REWRITES = true; //apply static hop dag and statement block rewrites protected static final int INLINING_MAX_NUM_OPS = 10; //inline single-statement functions w/ #ops <= threshold, other than dataops and literals + protected static final boolean ELIMINATE_DEAD_CODE = true; //remove dead code (e.g., assigments) not used later on static { // for internal debugging only @@ -137,6 +138,7 @@ public class InterProceduralAnalysis _passes.add(new IPAPassPropagateReplaceLiterals()); _passes.add(new IPAPassApplyStaticHopRewrites()); _passes.add(new IPAPassInlineFunctions()); + _passes.add(new IPAPassEliminateDeadCode()); } public InterProceduralAnalysis(StatementBlock sb) { http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/src/main/java/org/apache/sysml/hops/rewrite/RewriteSplitDagDataDependentOperators.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteSplitDagDataDependentOperators.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteSplitDagDataDependentOperators.java index afbf483..a254a1f 100644 --- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteSplitDagDataDependentOperators.java +++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteSplitDagDataDependentOperators.java @@ -173,6 +173,7 @@ public class RewriteSplitDagDataDependentOperators extends StatementBlockRewrite diVar.setValueType(c.getValueType()); sb1.liveOut().addVariable(varname, new DataIdentifier(diVar)); sb.liveIn().addVariable(varname, new DataIdentifier(diVar)); + sb.variablesRead().addVariable(varname, new DataIdentifier(diVar)); } //ensure disjoint operators across DAGs (prevent replicated operations) @@ -192,27 +193,23 @@ public class RewriteSplitDagDataDependentOperators extends StatementBlockRewrite ret.add(sb); //statement block with remaining hops sb.setSplitDag(true); //avoid later merge by other rewrites } - catch(Exception ex) - { + catch(Exception ex) { throw new HopsException("Failed to split hops dag for data dependent operators with unknown size.", ex); } LOG.debug("Applied splitDagDataDependentOperators (lines "+sb.getBeginLine()+"-"+sb.getEndLine()+")."); } //keep original hop dag - else - { + else { ret.add(sb); } return ret; } - private void collectDataDependentOperators( ArrayList<Hop> roots, ArrayList<Hop> cand ) - { + private void collectDataDependentOperators( ArrayList<Hop> roots, ArrayList<Hop> cand ) { if( roots == null ) return; - Hop.resetVisitStatus(roots); for( Hop root : roots ) rCollectDataDependentOperators(root, cand); http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/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 new file mode 100644 index 0000000..1516969 --- /dev/null +++ b/src/test/java/org/apache/sysml/test/integration/functions/misc/IPADeadCodeEliminationTest.java @@ -0,0 +1,85 @@ +/* + * 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. + */ + +package org.apache.sysml.test.integration.functions.misc; + +import org.junit.Assert; +import org.junit.Test; + +import org.apache.sysml.hops.OptimizerUtils; +import org.apache.sysml.test.integration.AutomatedTestBase; +import org.apache.sysml.test.integration.TestConfiguration; +import org.apache.sysml.test.utils.TestUtils; + +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_DIR = "functions/misc/"; + private final static String TEST_CLASS_DIR = TEST_DIR + IPADeadCodeEliminationTest.class.getSimpleName() + "/"; + + @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" }) ); + } + + @Test + public void testDeadCodeRemovalMainNoIPA() { + runIPALiteralReplacementTest( TEST_NAME1, false ); + } + + @Test + public void testDeadCodeRemovalMainIPA() { + runIPALiteralReplacementTest( TEST_NAME1, true ); + } + + @Test + public void testDeadCodeRemovalFunNoIPA() { + runIPALiteralReplacementTest( TEST_NAME2, false ); + } + + @Test + public void testDeadCodeRemovalFunIPA() { + runIPALiteralReplacementTest( TEST_NAME2, true ); + } + + private void runIPALiteralReplacementTest( String testname, boolean IPA ) + { + boolean oldFlagIPA = OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS; + + try { + TestConfiguration config = getTestConfiguration(testname); + loadTestConfiguration(config); + String HOME = SCRIPT_DIR + TEST_DIR; + fullDMLScriptName = HOME + testname + ".dml"; + programArgs = new String[]{"-stats"}; + OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = IPA; + runTest(true, false, null, -1); + + if( IPA ) //check for applied dead code removal + Assert.assertTrue(!heavyHittersContainsString("uak+")); + } + finally { + OptimizerUtils.ALLOW_INTER_PROCEDURAL_ANALYSIS = oldFlagIPA; + } + } +} http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun.dml b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun.dml new file mode 100644 index 0000000..33816c9 --- /dev/null +++ b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Fun.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) { + s = sum(A); + B = A + 7; + while(FALSE){} + if( 1 == 0 ) + print("sum = " + s); +} + +A = matrix(7, 10, 10); +B = foo(A); +print("max = " + max(B)); http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/src/test/scripts/functions/misc/IPADeadCodeRemoval_Main.dml ---------------------------------------------------------------------- diff --git a/src/test/scripts/functions/misc/IPADeadCodeRemoval_Main.dml b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Main.dml new file mode 100644 index 0000000..71547f8 --- /dev/null +++ b/src/test/scripts/functions/misc/IPADeadCodeRemoval_Main.dml @@ -0,0 +1,27 @@ +#------------------------------------------------------------- +# +# 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. +# +#------------------------------------------------------------- + +A = matrix(7, 10, 10); +s = sum(A); +while(FALSE){} +if( 1 == 0 ) + print("sum = " + s); +print("max = "+ max(A)); http://git-wip-us.apache.org/repos/asf/systemml/blob/2a1e8570/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java ---------------------------------------------------------------------- diff --git a/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java b/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java index 75e9970..8b08155 100644 --- a/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java +++ b/src/test_suites/java/org/apache/sysml/test/integration/functions/misc/ZPackageSuite.java @@ -41,6 +41,7 @@ import org.junit.runners.Suite; InvalidFunctionAssignmentTest.class, InvalidFunctionSignatureTest.class, IPAConstantFoldingScalarVariablePropagationTest.class, + IPADeadCodeEliminationTest.class, IPAFunctionInliningTest.class, IPALiteralReplacementTest.class, IPANnzPropagationTest.class,
