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 2017/04/04 19:04:52 UTC

[3/3] incubator-systemml git commit: [SYSTEMML-1459] Fix dangling parent hop refs via new cleanup rewrite

[SYSTEMML-1459] Fix dangling parent hop refs via new cleanup rewrite

The cost-based codegen plan selector uses hops with multiple consumers
as candidates for decisions on materalization points. On end-to-end
algorithm scenarios, we encountered side effects from specific dynamic
simplification rewrites which did not properly cleanup parent-child
pointers of removed hops.

This patch fixes the problematic rewrites and adds a general-purpose
cleanup rewrite, which removes all dangling parent hop references in one
pass through the hop DAG. Additionally, this patch also hardens special
cases of the rewrite 'fuse binary DAG to unary' to ensure only one
rewrite is applied at a time.


Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/f12759d7
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/f12759d7
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/f12759d7

Branch: refs/heads/master
Commit: f12759d754de5ba802d6a8765e9f4a51f8324054
Parents: 69d8b7c
Author: Matthias Boehm <mb...@gmail.com>
Authored: Mon Apr 3 22:00:11 2017 -0700
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Mon Apr 3 23:32:03 2017 -0700

----------------------------------------------------------------------
 src/main/java/org/apache/sysml/hops/Hop.java    |   8 +-
 .../java/org/apache/sysml/hops/MultipleOp.java  |   8 +-
 .../sysml/hops/codegen/cplan/CNodeUnary.java    |   1 +
 .../RewriteAlgebraicSimplificationDynamic.java  |   4 +
 .../RewriteAlgebraicSimplificationStatic.java   |  26 ++---
 .../RewriteRemoveDanglingParentReferences.java  | 115 +++++++++++++++++++
 .../org/apache/sysml/parser/DMLTranslator.java  |   4 +-
 7 files changed, 141 insertions(+), 25 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/Hop.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/Hop.java b/src/main/java/org/apache/sysml/hops/Hop.java
index cdee2c7..15a0cc3 100644
--- a/src/main/java/org/apache/sysml/hops/Hop.java
+++ b/src/main/java/org/apache/sysml/hops/Hop.java
@@ -1005,7 +1005,7 @@ public abstract class Hop
 	};
 	
 	// Operations that require a variable number of operands
-	public enum MultipleOperandOperation {
+	public enum MultiInputOp {
 		PRINTF
 	}
 	
@@ -1250,10 +1250,10 @@ public abstract class Hop
 	 * constructLops() method that is used to construct the Lops that correspond
 	 * to a Hop.
 	 */
-	protected static final HashMap<MultipleOperandOperation, MultipleCP.OperationType> MultipleOperandOperationHopTypeToLopType;
+	protected static final HashMap<MultiInputOp, MultipleCP.OperationType> MultipleOperandOperationHopTypeToLopType;
 	static {
-		MultipleOperandOperationHopTypeToLopType = new HashMap<MultipleOperandOperation, MultipleCP.OperationType>();
-		MultipleOperandOperationHopTypeToLopType.put(MultipleOperandOperation.PRINTF, MultipleCP.OperationType.PRINTF);
+		MultipleOperandOperationHopTypeToLopType = new HashMap<MultiInputOp, MultipleCP.OperationType>();
+		MultipleOperandOperationHopTypeToLopType.put(MultiInputOp.PRINTF, MultipleCP.OperationType.PRINTF);
 	}
 
 	protected static final HashMap<Hop.OpOp1, String> HopsOpOp12String;

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/MultipleOp.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/MultipleOp.java b/src/main/java/org/apache/sysml/hops/MultipleOp.java
index 07e1bd1..419bca2 100644
--- a/src/main/java/org/apache/sysml/hops/MultipleOp.java
+++ b/src/main/java/org/apache/sysml/hops/MultipleOp.java
@@ -35,7 +35,7 @@ import org.apache.sysml.parser.Expression.ValueType;
  *
  */
 public class MultipleOp extends Hop {
-	protected MultipleOperandOperation multipleOperandOperation = null;
+	protected MultiInputOp multipleOperandOperation = null;
 
 	protected MultipleOp() {
 	}
@@ -58,7 +58,7 @@ public class MultipleOp extends Hop {
 	 *             thrown if a HopsException occurs
 	 */
 	public MultipleOp(String name, DataType dataType, ValueType valueType,
-			MultipleOperandOperation multipleOperandOperation, Hop... inputs) throws HopsException {
+			MultiInputOp multipleOperandOperation, Hop... inputs) throws HopsException {
 		super(name, dataType, valueType);
 		this.multipleOperandOperation = multipleOperandOperation;
 
@@ -71,7 +71,7 @@ public class MultipleOp extends Hop {
 		refreshSizeInformation();
 	}
 
-	public MultipleOperandOperation getOp() {
+	public MultiInputOp getOp() {
 		return multipleOperandOperation;
 	}
 
@@ -158,7 +158,7 @@ public class MultipleOp extends Hop {
 		if (!(that instanceof MultipleOp))
 			return false;
 
-		if (multipleOperandOperation == MultipleOperandOperation.PRINTF) {
+		if (multipleOperandOperation == MultiInputOp.PRINTF) {
 			return false;
 		}
 

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java b/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
index 119dc8c..e28a989 100644
--- a/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
+++ b/src/main/java/org/apache/sysml/hops/codegen/cplan/CNodeUnary.java
@@ -156,6 +156,7 @@ public class CNodeUnary extends CNode
 			case LOOKUP_R:	return "u(ixr)";
 			case LOOKUP_RC:	return "u(ixrc)";
 			case LOOKUP0:	return "u(ix0)";
+			case POW2:      return "^2";
 			default:		return "u("+_type.name().toLowerCase()+")";
 		}
 	}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
index 66f6879..d2e5831 100644
--- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
+++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationDynamic.java
@@ -212,6 +212,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
 				Hop hnew = HopRewriteUtils.createDataGenOpByVal( new LiteralOp(hi.getDim1()), 
 						                                         new LiteralOp(hi.getDim2()), 0);
 				HopRewriteUtils.replaceChildReference(parent, hi, hnew, pos);
+				HopRewriteUtils.cleanupUnreferenced(hi, input);
 				hi = hnew;
 				
 				LOG.debug("Applied removeEmptyRightIndexing");
@@ -235,6 +236,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
 				
 				//remove unnecessary right indexing
 				HopRewriteUtils.replaceChildReference(parent, hi, input, pos);
+				HopRewriteUtils.cleanupUnreferenced(hi);
 				hi = input;
 				
 				LOG.debug("Applied removeUnnecessaryRightIndexing");
@@ -258,6 +260,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
 				//remove unnecessary right indexing		
 				Hop hnew = HopRewriteUtils.createDataGenOp( input1, 0);
 				HopRewriteUtils.replaceChildReference(parent, hi, hnew, pos);
+				HopRewriteUtils.cleanupUnreferenced(hi, input2);
 				hi = hnew;
 				
 				LOG.debug("Applied removeEmptyLeftIndexing");
@@ -279,6 +282,7 @@ public class RewriteAlgebraicSimplificationDynamic extends HopRewriteRule
 				
 				//remove unnecessary right indexing				
 				HopRewriteUtils.replaceChildReference(parent, hi, input, pos);
+				HopRewriteUtils.cleanupUnreferenced(hi);
 				hi = input;
 				
 				LOG.debug("Applied removeUnnecessaryLeftIndexing");

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationStatic.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationStatic.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationStatic.java
index 3345ee1..a0ccb0f 100644
--- a/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationStatic.java
+++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteAlgebraicSimplificationStatic.java
@@ -672,20 +672,18 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 				{
 					Hop leftC1 = left.getInput().get(0);
 					Hop leftC2 = left.getInput().get(1);
-					//System.out.println("aOp2:"+((BinaryOp)left).getOp()+": "+leftC1.getName()+" "+leftC2.getName());
-						
+					
 					if( leftC1.getDataType()==DataType.MATRIX && leftC2.getDataType()==DataType.MATRIX &&
 						(right == leftC1 || right == leftC2) && leftC1 !=leftC2 ){ //any mult order
 						X = right;
 						Y = ( right == leftC1 ) ? leftC2 : leftC1;
 					}
 					if( X != null ){ //rewrite 'binary +/-' 
-						HopRewriteUtils.removeChildReference(parent, hi);
 						LiteralOp literal = new LiteralOp(1);
 						BinaryOp plus = HopRewriteUtils.createBinary(Y, literal, bop.getOp());
 						BinaryOp mult = HopRewriteUtils.createBinary(plus, X, OpOp2.MULT);
-						
-						HopRewriteUtils.addChildReference(parent, mult, pos);							
+						HopRewriteUtils.replaceChildReference(parent, hi, mult, pos);
+						HopRewriteUtils.cleanupUnreferenced(hi, left);
 						hi = mult;
 						applied = true;
 						
@@ -706,7 +704,8 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 						LiteralOp literal = new LiteralOp(1);
 						BinaryOp plus = HopRewriteUtils.createBinary(literal, Y, bop.getOp());
 						BinaryOp mult = HopRewriteUtils.createBinary(plus, X, OpOp2.MULT);
-						HopRewriteUtils.replaceChildReference(parent, hi, mult, pos);	
+						HopRewriteUtils.replaceChildReference(parent, hi, mult, pos);
+						HopRewriteUtils.cleanupUnreferenced(hi, right);
 						hi = mult;
 
 						LOG.debug("Applied simplifyDistributiveBinaryOperation2");
@@ -759,6 +758,7 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 						BinaryOp bop3 = HopRewriteUtils.createBinary(left, left2, op);
 						BinaryOp bop4 = HopRewriteUtils.createBinary(bop3, right2, op);
 						HopRewriteUtils.replaceChildReference(parent, bop, bop4, pos);	
+						HopRewriteUtils.cleanupUnreferenced(bop, bop2);
 						hi = bop4;
 						
 						applied = true;
@@ -780,12 +780,10 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 						&& (right2.getDim1() > 1 || right.getDim1() == 1) ) //X not vector, or Y vector
 					{
 						//((op()*X)*Y) -> op()*(X*Y)
-						HopRewriteUtils.removeChildReference(parent, bop);
-						
 						BinaryOp bop3 = HopRewriteUtils.createBinary(right2, right, op);
 						BinaryOp bop4 = HopRewriteUtils.createBinary(left2, bop3, op);
-						
-						HopRewriteUtils.addChildReference(parent, bop4, pos);	
+						HopRewriteUtils.replaceChildReference(parent, bop, bop4, pos);
+						HopRewriteUtils.cleanupUnreferenced(bop, bop2);
 						hi = bop4;
 						
 						LOG.debug("Applied simplifyBushyBinaryOperation2");
@@ -1125,7 +1123,7 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 				}		
 			}
 			//select positive (selp) operator
-			if( bop.getOp() == OpOp2.MULT && left.getDataType()==DataType.MATRIX && right.getDataType()==DataType.MATRIX )
+			else if( bop.getOp() == OpOp2.MULT && left.getDataType()==DataType.MATRIX && right.getDataType()==DataType.MATRIX )
 			{
 				//by definition, either left or right or none applies. 
 				//note: if there are multiple consumers on the intermediate tmp=(X>0), it's still beneficial
@@ -1173,9 +1171,8 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 					}
 				}
 			}
-			
 			//select positive (selp) operator; pattern: max(X,0) -> selp+
-			if( bop.getOp() == OpOp2.MAX && left.getDataType()==DataType.MATRIX 
+			else if( bop.getOp() == OpOp2.MAX && left.getDataType()==DataType.MATRIX 
 					&& right instanceof LiteralOp && HopRewriteUtils.getDoubleValue((LiteralOp)right)==0 )
 			{
 				UnaryOp unary = HopRewriteUtils.createUnary(left, OpOp1.SELP);
@@ -1185,9 +1182,8 @@ public class RewriteAlgebraicSimplificationStatic extends HopRewriteRule
 				
 				LOG.debug("Applied fuseBinarySubDAGToUnaryOperation-selp3");
 			}
-			
 			//select positive (selp) operator; pattern: max(0,X) -> selp+
-			if( bop.getOp() == OpOp2.MAX && right.getDataType()==DataType.MATRIX 
+			else if( bop.getOp() == OpOp2.MAX && right.getDataType()==DataType.MATRIX 
 					&& left instanceof LiteralOp && HopRewriteUtils.getDoubleValue((LiteralOp)left)==0 )
 			{
 				UnaryOp unary = HopRewriteUtils.createUnary(right, OpOp1.SELP);

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/hops/rewrite/RewriteRemoveDanglingParentReferences.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/hops/rewrite/RewriteRemoveDanglingParentReferences.java b/src/main/java/org/apache/sysml/hops/rewrite/RewriteRemoveDanglingParentReferences.java
new file mode 100644
index 0000000..ac8fb68
--- /dev/null
+++ b/src/main/java/org/apache/sysml/hops/rewrite/RewriteRemoveDanglingParentReferences.java
@@ -0,0 +1,115 @@
+/*
+ * 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.rewrite;
+
+import java.util.ArrayList;
+
+import org.apache.sysml.hops.DataOp;
+import org.apache.sysml.hops.FunctionOp;
+import org.apache.sysml.hops.Hop;
+import org.apache.sysml.hops.Hop.DataOpTypes;
+import org.apache.sysml.hops.Hop.MultiInputOp;
+import org.apache.sysml.hops.Hop.OpOp1;
+import org.apache.sysml.hops.HopsException;
+import org.apache.sysml.hops.MultipleOp;
+import org.apache.sysml.hops.UnaryOp;
+
+/**
+ * This rewrite is a general-purpose cleanup pass that removes any
+ * dangling parent references in one pass through the hop DAG. These
+ * dangling references could have been introduced by rewrites that 
+ * remove operators but miss a proper cleanup. 
+ * 
+ */
+public class RewriteRemoveDanglingParentReferences extends HopRewriteRule
+{
+	@Override
+	public ArrayList<Hop> rewriteHopDAGs(ArrayList<Hop> roots, ProgramRewriteStatus state)
+		throws HopsException
+	{
+		if( roots == null )
+			return null;
+		
+		int numRm = 0;
+		for( Hop h : roots ) 
+			numRm += removeDanglingParentReferences( h, false );
+		
+		if( LOG.isDebugEnabled() && numRm > 0 )
+			LOG.debug("Remove Dangling Parents - removed "+numRm+" operators.");
+		
+		return roots;
+	}
+
+	@Override
+	public Hop rewriteHopDAG(Hop root, ProgramRewriteStatus state) 
+		throws HopsException
+	{
+		if( root == null )
+			return root;
+		
+		//note: the predicate can have an arbitrary root node
+		//and hence, we pin this node to prevent its removal
+		int numRm = removeDanglingParentReferences( root, true );
+		
+		if( LOG.isDebugEnabled() && numRm > 0 )
+			LOG.debug("Remove Dangling Parents - removed "+numRm+" operators.");
+		
+		return root;
+	}
+	
+	private int removeDanglingParentReferences( Hop hop, boolean pin ) 
+		throws HopsException
+	{
+		//check mark processed
+		if( hop.isVisited() )
+			return 0;
+		
+		//mark node itself as processed (because it's reachable over parents)
+		hop.setVisited();
+		
+		//process parents recursively (w/ potential modification)
+		int count = 0;
+		for( int i=0; i<hop.getParent().size(); i++ ) {
+			Hop p = hop.getParent().get(i);
+			count += removeDanglingParentReferences(p, false);
+			i -= hop.getParent().contains(p) ? 0 : 1; //skip back
+		}
+		
+		//process node itself and children recursively
+		ArrayList<Hop> inputs = hop.getInput();
+		if( !pin && hop.getParent().isEmpty() && !isValidRootNode(hop) ) {
+			HopRewriteUtils.cleanupUnreferenced(hop);
+			count++;
+		}
+		for( int i=0; i<inputs.size(); i++ )
+			count += removeDanglingParentReferences(inputs.get(i), false);
+		
+		return count;
+	}
+	
+	private static boolean isValidRootNode(Hop hop) {
+		return (hop instanceof DataOp && ((DataOp)hop).isWrite())
+			|| (hop instanceof UnaryOp && ((UnaryOp)hop).getOp()==OpOp1.STOP)
+			|| (hop instanceof UnaryOp && ((UnaryOp)hop).getOp()==OpOp1.PRINT)
+			|| (hop instanceof MultipleOp && ((MultipleOp)hop).getOp()==MultiInputOp.PRINTF)
+			|| (hop instanceof FunctionOp)
+			|| (hop instanceof DataOp && ((DataOp)hop).getDataOpType()==DataOpTypes.FUNCTIONOUTPUT);
+	}
+}

http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/f12759d7/src/main/java/org/apache/sysml/parser/DMLTranslator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/parser/DMLTranslator.java b/src/main/java/org/apache/sysml/parser/DMLTranslator.java
index aa09fe5..2b8128b 100644
--- a/src/main/java/org/apache/sysml/parser/DMLTranslator.java
+++ b/src/main/java/org/apache/sysml/parser/DMLTranslator.java
@@ -41,6 +41,7 @@ import org.apache.sysml.hops.Hop.AggOp;
 import org.apache.sysml.hops.Hop.DataGenMethod;
 import org.apache.sysml.hops.Hop.DataOpTypes;
 import org.apache.sysml.hops.Hop.Direction;
+import org.apache.sysml.hops.Hop.MultiInputOp;
 import org.apache.sysml.hops.Hop.OpOp2;
 import org.apache.sysml.hops.Hop.OpOp3;
 import org.apache.sysml.hops.Hop.ParamBuiltinOp;
@@ -949,7 +950,6 @@ public class DMLTranslator
 								current.getEndColumn());
 						output.add(stopHop);
 					} else if (ptype == PRINTTYPE.PRINTF) {
-						Hop.MultipleOperandOperation printfOperation = Hop.MultipleOperandOperation.PRINTF;
 						List<Expression> expressions = ps.getExpressions();
 						Hop[] inHops = new Hop[expressions.size()];
 						// process the expressions (function parameters) that
@@ -962,7 +962,7 @@ public class DMLTranslator
 						}
 						target.setValueType(ValueType.STRING);
 						Hop printfHop = new MultipleOp(target.getName(), target.getDataType(), target.getValueType(),
-								printfOperation, inHops);
+								MultiInputOp.PRINTF, inHops);
 						output.add(printfHop);
 					}