# HG changeset patch # User Lukas Stadler # Date 1401117129 -7200 # Node ID 4c284376c3743c8be6d792297570ba1278a1e3d3 # Parent 23c4dd4f72a3e119e7a6589f75f10ff54e7aa2df remove dead and redundant phis during LoopBeginNode simplification diff -r 23c4dd4f72a3 -r 4c284376c374 graal/com.oracle.graal.nodes.test/src/com/oracle/graal/nodes/test/LoopPhiCanonicalizerTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes.test/src/com/oracle/graal/nodes/test/LoopPhiCanonicalizerTest.java Mon May 26 17:12:09 2014 +0200 @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2013, 2014, 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.nodes.test; + +import org.junit.*; + +import com.oracle.graal.compiler.test.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.tiers.*; + +public class LoopPhiCanonicalizerTest extends GraalCompilerTest { + + private static int[] array = new int[1000]; + + @BeforeClass + public static void before() { + for (int i = 0; i < array.length; i++) { + array[i] = i; + } + } + + public static long loopSnippet() { + int a = 0; + int b = 0; + int c = 0; + int d = 0; + + long sum = 0; + while (d < 1000) { + sum += array[a++] + array[b++] + array[c++] + array[d++]; + } + return sum; + } + + @Test + public void test() { + StructuredGraph graph = parse("loopSnippet"); + NodePredicate loopPhis = node -> node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode; + + PhaseContext context = new PhaseContext(getProviders(), null); + Assert.assertEquals(5, graph.getNodes().filter(loopPhis).count()); + new CanonicalizerPhase(false).apply(graph, context); + Assert.assertEquals(2, graph.getNodes().filter(loopPhis).count()); + + test("loopSnippet"); + } +} diff -r 23c4dd4f72a3 -r 4c284376c374 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Thu Jun 05 13:19:59 2014 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Mon May 26 17:12:09 2014 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2011, 2014, 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 @@ -29,6 +29,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.graph.spi.*; +import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.util.*; @@ -175,7 +176,8 @@ @Override public void simplify(SimplifierTool tool) { - // nothing yet + removeDeadPhis(); + canonicalizePhis(tool); } public boolean isLoopExit(BeginNode begin) { @@ -209,19 +211,101 @@ * alive. This allows the removal of dead phi loops. */ public void removeDeadPhis() { - Set alive = new HashSet<>(); - for (PhiNode phi : phis()) { - NodePredicate isAlive = u -> !isPhiAtMerge(u) || alive.contains(u); - if (phi.usages().filter(isAlive).isNotEmpty()) { - alive.add(phi); - for (PhiNode keptAlive : phi.values().filter(PhiNode.class).filter(isAlive.negate())) { - alive.add(keptAlive); + if (phis().isNotEmpty()) { + Set alive = new HashSet<>(); + for (PhiNode phi : phis()) { + NodePredicate isAlive = u -> !isPhiAtMerge(u) || alive.contains(u); + if (phi.usages().filter(isAlive).isNotEmpty()) { + alive.add(phi); + for (PhiNode keptAlive : phi.values().filter(PhiNode.class).filter(isAlive.negate())) { + alive.add(keptAlive); + } + } + } + for (PhiNode phi : phis().filter(((NodePredicate) alive::contains).negate()).snapshot()) { + phi.replaceAtUsages(null); + phi.safeDelete(); + } + } + } + + private static final int NO_INCREMENT = Integer.MIN_VALUE; + + /** + * Returns an array with one entry for each input of the phi, which is either + * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in + * the corresponding branch. + */ + private static int[] getSelfIncrements(PhiNode phi) { + int[] selfIncrement = new int[phi.valueCount()]; + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode input = phi.valueAt(i); + long increment = NO_INCREMENT; + if (input != null && input instanceof IntegerAddNode) { + IntegerAddNode add = (IntegerAddNode) input; + if (add.x() == phi && add.y().isConstant()) { + increment = add.y().asConstant().asLong(); + } else if (add.y() == phi && add.x().isConstant()) { + increment = add.x().asConstant().asLong(); + } + } else if (input == phi) { + increment = 0; + } + if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) { + increment = NO_INCREMENT; + } + selfIncrement[i] = (int) increment; + } + return selfIncrement; + } + + /** + * Coalesces loop phis that represent the same value (which is not handled by normal Global + * Value Numbering). + */ + public void canonicalizePhis(SimplifierTool tool) { + int phiCount = phis().count(); + if (phiCount > 1) { + int phiInputCount = phiPredecessorCount(); + int phiIndex = 0; + int[][] selfIncrement = new int[phiCount][]; + PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]); + + for (phiIndex = 0; phiIndex < phiCount; phiIndex++) { + PhiNode phi = phis[phiIndex]; + if (phi != null) { + nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) { + PhiNode otherPhi = phis[otherPhiIndex]; + if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.getNodeClass().valueEqual(phi, otherPhi)) { + continue nextPhi; + } + if (selfIncrement[phiIndex] == null) { + selfIncrement[phiIndex] = getSelfIncrements(phi); + } + if (selfIncrement[otherPhiIndex] == null) { + selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi); + } + int[] phiIncrement = selfIncrement[phiIndex]; + int[] otherPhiIncrement = selfIncrement[otherPhiIndex]; + for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) { + if (phiIncrement[inputIndex] == NO_INCREMENT) { + if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) { + continue nextPhi; + } + } + if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) { + continue nextPhi; + } + } + if (tool != null) { + otherPhi.usages().forEach(tool::addToWorkList); + } + otherPhi.replaceAtUsages(phi); + GraphUtil.killWithUnusedFloatingInputs(otherPhi); + phis[otherPhiIndex] = null; + } } } } - for (PhiNode phi : phis().filter(((NodePredicate) alive::contains).negate()).snapshot()) { - phi.replaceAtUsages(null); - phi.safeDelete(); - } } }