# HG changeset patch # User Doug Simon # Date 1339771328 -7200 # Node ID 63bd4fd90c27d0ba130b1d9dee0d360b8062388c # Parent 7d25723b7699da29f6af7229f22006dc8477f1ab# Parent 23a7a21e5f12afb81e5a2e501cd3507068ad334e Merge. diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ReassociateConstants.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ReassociateConstants.java Fri Jun 15 16:42:08 2012 +0200 @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.jtt.optimize; + +import org.junit.*; + + +public class ReassociateConstants { + public static int rnd = (int) (Math.random() * 100); + @Test + public void run0() throws Throwable { + Assert.assertEquals(rnd + 3, 1 + (rnd + 2)); + Assert.assertEquals(rnd + 3, (rnd + 2) + 1); + Assert.assertEquals(rnd + 3, 1 + (2 + rnd)); + Assert.assertEquals(rnd + 3, (2 + rnd) + 1); + + Assert.assertEquals(-1 - rnd, 1 - (rnd + 2)); + Assert.assertEquals(rnd + 1, (rnd + 2) - 1); + Assert.assertEquals(-1 - rnd, 1 - (2 + rnd)); + Assert.assertEquals(rnd + 1, (2 + rnd) - 1); + + Assert.assertEquals(rnd - 1, 1 + (rnd - 2)); + Assert.assertEquals(rnd - 1, (rnd - 2) + 1); + Assert.assertEquals(-rnd + 3, 1 + (2 - rnd)); + Assert.assertEquals(-rnd + 3, (2 - rnd) + 1); + + Assert.assertEquals(-rnd + 3, 1 - (rnd - 2)); + Assert.assertEquals(rnd - 3, (rnd - 2) - 1); + Assert.assertEquals(rnd + -1, 1 - (2 - rnd)); + Assert.assertEquals(-rnd + 1, (2 - rnd) - 1); + } +} diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.type.GenericStamp.*; import com.oracle.graal.nodes.util.*; @@ -89,6 +90,17 @@ return this instanceof ConstantNode; } + private static final NodePredicate IS_CONSTANT = new NodePredicate() { + @Override + public boolean apply(Node n) { + return n instanceof ValueNode && ((ValueNode) n).isConstant(); + } + }; + + public static NodePredicate isConstantPredicate() { + return IS_CONSTANT; + } + /** * Checks whether this value represents the null constant. * @return {@code true} if this value represents the null constant diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -68,6 +68,7 @@ return ConstantNode.forLong(0, graph()); } } + return BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -23,6 +23,8 @@ package com.oracle.graal.nodes.calc; import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.type.*; @@ -53,4 +55,135 @@ this.x = x; this.y = y; } + + public enum ReassociateMatch { + x, + y; + + public ValueNode getValue(BinaryNode binary) { + switch(this) { + case x: + return binary.x(); + case y: + return binary.y(); + default: throw GraalInternalError.shouldNotReachHere(); + } + } + + public ValueNode getOtherValue(BinaryNode binary) { + switch(this) { + case x: + return binary.y(); + case y: + return binary.x(); + default: throw GraalInternalError.shouldNotReachHere(); + } + } + } + + public static boolean canTryReassociate(BinaryNode node) { + return node instanceof IntegerAddNode || node instanceof IntegerSubNode || node instanceof IntegerMulNode + || node instanceof AndNode || node instanceof OrNode || node instanceof XorNode; + } + + public static ReassociateMatch findReassociate(BinaryNode binary, NodePredicate criterion) { + boolean resultX = criterion.apply(binary.x()); + boolean resultY = criterion.apply(binary.y()); + if (resultX && !resultY) { + return ReassociateMatch.x; + } + if (!resultX && resultY) { + return ReassociateMatch.y; + } + return null; + } + + /* In reassociate, complexity comes from the handling of IntegerSub (non commutative) which can be mixed with IntegerAdd. + * if first tries to find m1, m2 which match the criterion : + * (a o m2) o m1 + * (m2 o a) o m1 + * m1 o (a o m2) + * m1 o (m2 o a) + * It then produces 4 boolean for the -/+ case + * invertA : should the final expression be like *-a (rather than a+*) + * aSub : should the final expression be like a-* (rather than a+*) + * invertM1 : should the final expression contain -m1 + * invertM2 : should the final expression contain -m2 + */ + /** + * Tries to re-associate values which satisfy the criterion. + * For example with a constantness criterion : (a + 2) + 1 => a + (1 + 2)
+ * This method accepts only reassociable operations (see {@linkplain #canTryReassociate(BinaryNode)}) such as +, -, *, &, | and ^ + */ + public static BinaryNode reassociate(BinaryNode node, NodePredicate criterion) { + assert canTryReassociate(node); + ReassociateMatch match1 = findReassociate(node, criterion); + if (match1 == null) { + return node; + } + ValueNode otherValue = match1.getOtherValue(node); + boolean addSub = false; + boolean subAdd = false; + if (otherValue.getClass() != node.getClass()) { + if (node instanceof IntegerAddNode && otherValue instanceof IntegerSubNode) { + addSub = true; + } else if (node instanceof IntegerSubNode && otherValue instanceof IntegerAddNode) { + subAdd = true; + } else { + return node; + } + } + BinaryNode other = (BinaryNode) otherValue; + ReassociateMatch match2 = findReassociate(other, criterion); + if (match2 == null) { + return node; + } + boolean invertA = false; + boolean aSub = false; + boolean invertM1 = false; + boolean invertM2 = false; + if (addSub) { + invertM2 = match2 == ReassociateMatch.y; + invertA = !invertM2; + } else if (subAdd) { + invertA = invertM2 = match1 == ReassociateMatch.x; + invertM1 = !invertM2; + } else if (node instanceof IntegerSubNode && other instanceof IntegerSubNode) { + invertA = match1 == ReassociateMatch.x ^ match2 == ReassociateMatch.x; + aSub = match1 == ReassociateMatch.y && match2 == ReassociateMatch.y; + invertM1 = match1 == ReassociateMatch.y && match2 == ReassociateMatch.x; + invertM2 = match1 == ReassociateMatch.x && match2 == ReassociateMatch.x; + } + assert !(invertM1 && invertM2) && !(invertA && aSub); + ValueNode m1 = match1.getValue(node); + ValueNode m2 = match2.getValue(other); + ValueNode a = match2.getOtherValue(other); + if (node instanceof IntegerAddNode || node instanceof IntegerSubNode) { + BinaryNode associated; + if (invertM1) { + associated = IntegerArithmeticNode.sub(m2, m1); + } else if (invertM2) { + associated = IntegerArithmeticNode.sub(m1, m2); + } else { + associated = IntegerArithmeticNode.add(m1, m2); + } + if (invertA) { + return IntegerArithmeticNode.sub(associated, a); + } + if (aSub) { + return IntegerArithmeticNode.sub(a, associated); + } + return IntegerArithmeticNode.add(a, associated); + } else if (node instanceof IntegerMulNode) { + return IntegerArithmeticNode.mul(a, IntegerAddNode.mul(m1, m2)); + } else if (node instanceof AndNode) { + return LogicNode.and(a, LogicNode.and(m1, m2)); + } else if (node instanceof OrNode) { + return LogicNode.or(a, LogicNode.or(m1, m2)); + } else if (node instanceof XorNode) { + return LogicNode.xor(a, LogicNode.xor(m1, m2)); + } else { + throw GraalInternalError.shouldNotReachHere(); + } + } } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -48,33 +48,27 @@ return ConstantNode.forLong(x().asConstant().asLong() + y().asConstant().asLong(), graph()); } } else if (y().isConstant()) { - if (kind() == Kind.Int) { - int c = y().asConstant().asInt(); - if (c == 0) { - return x(); - } - } else { - assert kind() == Kind.Long; - long c = y().asConstant().asLong(); - if (c == 0) { - return x(); - } + long c = y().asConstant().asLong(); + if (c == 0) { + return x(); } // canonicalize expressions like "(a + 1) + 2" - if (x() instanceof IntegerAddNode) { - IntegerAddNode other = (IntegerAddNode) x(); - if (other.y().isConstant()) { - ConstantNode sum; - if (kind() == Kind.Int) { - sum = ConstantNode.forInt(y().asConstant().asInt() + other.y().asConstant().asInt(), graph()); - } else { - assert kind() == Kind.Long; - sum = ConstantNode.forLong(y().asConstant().asLong() + other.y().asConstant().asLong(), graph()); - } - return graph().unique(new IntegerAddNode(kind(), other.x(), sum)); + BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); + if (reassociated != this) { + return reassociated; + } + if (c < 0) { + if (kind() == Kind.Int) { + return IntegerArithmeticNode.sub(x(), ConstantNode.forInt((int) -c, graph())); + } else { + assert kind() == Kind.Long; + return IntegerArithmeticNode.sub(x(), ConstantNode.forLong(-c, graph())); } } } + if (x() instanceof NegateNode) { + return IntegerArithmeticNode.sub(y(), ((NegateNode) x()).x()); + } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -59,19 +59,7 @@ return graph().unique(new LeftShiftNode(kind(), x(), ConstantNode.forInt(CodeUtil.log2(c), graph()))); } // canonicalize expressions like "(a * 1) * 2" - if (x() instanceof IntegerMulNode) { - IntegerMulNode other = (IntegerMulNode) x(); - if (other.y().isConstant()) { - ConstantNode sum; - if (kind() == Kind.Int) { - sum = ConstantNode.forInt(y().asConstant().asInt() * other.y().asConstant().asInt(), graph()); - } else { - assert kind() == Kind.Long; - sum = ConstantNode.forLong(y().asConstant().asLong() * other.y().asConstant().asLong(), graph()); - } - return graph().unique(new IntegerMulNode(kind(), other.x(), sum)); - } - } + return BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -51,17 +51,24 @@ if (c == 0) { return x(); } - if (kind() == Kind.Int) { - return graph().unique(new IntegerAddNode(kind(), x(), ConstantNode.forInt((int) -c, graph()))); - } else { - assert kind() == Kind.Long; - return graph().unique(new IntegerAddNode(kind(), x(), ConstantNode.forLong(-c, graph()))); + BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); + if (reassociated != this) { + return reassociated; + } + if (c < 0) { + if (kind() == Kind.Int) { + return IntegerArithmeticNode.add(x(), ConstantNode.forInt((int) -c, graph())); + } else { + assert kind() == Kind.Long; + return IntegerArithmeticNode.add(x(), ConstantNode.forLong(-c, graph())); + } } } else if (x().isConstant()) { long c = x().asConstant().asLong(); if (c == 0) { return graph().unique(new NegateNode(y())); } + return BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LogicNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LogicNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LogicNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -23,6 +23,7 @@ package com.oracle.graal.nodes.calc; import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; /** @@ -38,4 +39,43 @@ public LogicNode(Kind kind, ValueNode x, ValueNode y) { super(kind, x, y); } + + public static LogicNode and(ValueNode v1, ValueNode v2) { + assert v1.kind() == v2.kind() && v1.graph() == v2.graph(); + Graph graph = v1.graph(); + switch(v1.kind()) { + case Int: + return graph.unique(new AndNode(Kind.Int, v1, v2)); + case Long: + return graph.unique(new AndNode(Kind.Long, v1, v2)); + default: + throw ValueNodeUtil.shouldNotReachHere(); + } + } + + public static LogicNode or(ValueNode v1, ValueNode v2) { + assert v1.kind() == v2.kind() && v1.graph() == v2.graph(); + Graph graph = v1.graph(); + switch(v1.kind()) { + case Int: + return graph.unique(new OrNode(Kind.Int, v1, v2)); + case Long: + return graph.unique(new OrNode(Kind.Long, v1, v2)); + default: + throw ValueNodeUtil.shouldNotReachHere(); + } + } + + public static LogicNode xor(ValueNode v1, ValueNode v2) { + assert v1.kind() == v2.kind() && v1.graph() == v2.graph(); + Graph graph = v1.graph(); + switch(v1.kind()) { + case Int: + return graph.unique(new XorNode(Kind.Int, v1, v2)); + case Long: + return graph.unique(new XorNode(Kind.Long, v1, v2)); + default: + throw ValueNodeUtil.shouldNotReachHere(); + } + } } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -68,6 +68,7 @@ return x(); } } + return BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java Fri Jun 15 16:12:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java Fri Jun 15 16:42:08 2012 +0200 @@ -62,6 +62,7 @@ return x(); } } + return BinaryNode.reassociate(this, ValueNode.isConstantPredicate()); } return this; } diff -r 7d25723b7699 -r 63bd4fd90c27 graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/ReassociateAndCanonicalTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/ReassociateAndCanonicalTest.java Fri Jun 15 16:42:08 2012 +0200 @@ -0,0 +1,249 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.tests; + +import org.junit.*; + +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public class ReassociateAndCanonicalTest extends GraalCompilerTest { + public static int rnd = (int) (Math.random() * 100); + + @Test + public void test1() { + test("test1Snippet", "ref1Snippet"); + } + + public static int test1Snippet() { + return 1 + (rnd + 2); + } + + public static int ref1Snippet() { + return rnd + 3; + } + + @Test + public void test2() { + test("test2Snippet", "ref2Snippet"); + } + + public static int test2Snippet() { + return rnd + 3; + } + + public static int ref2Snippet() { + return (rnd + 2) + 1; + } + + @Test + public void test3() { + test("test3Snippet", "ref3Snippet"); + } + + public static int test3Snippet() { + return rnd + 3; + } + + public static int ref3Snippet() { + return 1 + (2 + rnd); + } + + @Test + public void test4() { + test("test4Snippet", "ref4Snippet"); + } + + public static int test4Snippet() { + return rnd + 3; + } + + public static int ref4Snippet() { + return (2 + rnd) + 1; + } + + @Test + public void test5() { + test("test5Snippet", "ref5Snippet"); + } + + public static int test5Snippet() { + return -1 - rnd; + } + + public static int ref5Snippet() { + return 1 - (rnd + 2); + } + + @Test + public void test6() { + test("test6Snippet", "ref6Snippet"); + } + + public static int test6Snippet() { + return rnd + 1; + } + + public static int ref6Snippet() { + return (rnd + 2) - 1; + } + + @Test + public void test7() { + test("test7Snippet", "ref7Snippet"); + } + + public static int test7Snippet() { + return -1 - rnd; + } + + public static int ref7Snippet() { + return 1 - (2 + rnd); + } + + @Test + public void test8() { + test("test8Snippet", "ref8Snippet"); + } + + public static int test8Snippet() { + return rnd + 1; + } + + public static int ref8Snippet() { + return (2 + rnd) - 1; + } + + @Test + public void test9() { + test("test9Snippet", "ref9Snippet"); + } + + public static int test9Snippet() { + return rnd - 1; + } + + public static int ref9Snippet() { + return 1 + (rnd - 2); + } + + @Test + public void test10() { + test("test10Snippet", "ref10Snippet"); + } + + public static int test10Snippet() { + return rnd - 1; + } + + public static int ref10Snippet() { + return (rnd - 2) + 1; + } + + @Test + public void test11() { + test("test11Snippet", "ref11Snippet"); + } + + public static int test11Snippet() { + return -rnd + 3; + } + + public static int ref11Snippet() { + return 1 + (2 - rnd); + } + + @Test + public void test12() { + test("test12Snippet", "ref12Snippet"); + } + + public static int test12Snippet() { + return -rnd + 3; + } + + public static int ref12Snippet() { + return (2 - rnd) + 1; + } + + @Test + public void test13() { + test("test13Snippet", "ref13Snippet"); + } + + public static int test13Snippet() { + return -rnd + 3; + } + + public static int ref13Snippet() { + return 1 - (rnd - 2); + } + + @Test + public void test14() { + test("test14Snippet", "ref14Snippet"); + } + + public static int test14Snippet() { + return rnd - 3; + } + + public static int ref14Snippet() { + return (rnd - 2) - 1; + } + + @Test + public void test15() { + test("test15Snippet", "ref15Snippet"); + } + + public static int test15Snippet() { + return rnd + -1; + } + + public static int ref15Snippet() { + return 1 - (2 - rnd); + } + + @Test + public void test16() { + test("test16Snippet", "ref16Snippet"); + } + + public static int test16Snippet() { + return -rnd + 1; + } + + public static int ref16Snippet() { + return (2 - rnd) - 1; + } + + private void test(String test, String ref) { + StructuredGraph testGraph = parse(test); + new CanonicalizerPhase(null, runtime(), null).apply(testGraph); + StructuredGraph refGraph = parse(ref); + new CanonicalizerPhase(null, runtime(), null).apply(refGraph); + assertEquals(testGraph, refGraph); + } +}