Mercurial > hg > truffle
changeset 5820:547587296886
Make ReadEliminationPhase support phis (eliminates read when the last access is a memeory phi of writes, recursively)
Add a TopStamp (identity element for meet) and use it to create kind-less phis that later get a non-top phi by infering thir stamp thanks to inputs
ignore binary graph files
line wrap: on
line diff
--- a/.hgignore Thu Jul 12 16:59:09 2012 +0200 +++ b/.hgignore Thu Jul 12 18:58:36 2012 +0200 @@ -55,3 +55,5 @@ ^.hgtip .DS_Store javadoc/ +syntax: glob +*.bgv
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ReadEliminationPhase.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ReadEliminationPhase.java Thu Jul 12 18:58:36 2012 +0200 @@ -22,26 +22,84 @@ */ package com.oracle.graal.compiler.phases; +import java.util.*; + import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.extended.*; public class ReadEliminationPhase extends Phase { + private Queue<PhiNode> newPhis; @Override protected void run(StructuredGraph graph) { + newPhis = new LinkedList<>(); for (FloatingReadNode n : graph.getNodes(FloatingReadNode.class)) { - if (n.lastLocationAccess() != null) { - Node memoryInput = n.lastLocationAccess(); - if (memoryInput instanceof WriteNode) { - WriteNode other = (WriteNode) memoryInput; - if (other.object() == n.object() && other.location() == n.location()) { - Debug.log("Eliminated memory read %1.1s and replaced with node %s", n, other.value()); - graph.replaceFloating(n, other.value()); - } + if (isReadEliminable(n)) { + NodeMap<ValueNode> nodeMap = n.graph().createNodeMap(); + ValueNode value = getValue(n.lastLocationAccess(), nodeMap); + Debug.log("Eliminated memory read %1.1s and replaced with node %s", n, value); + graph.replaceFloating(n, value); + } + } + // get a proper stamp for the new phis + while (!newPhis.isEmpty()) { + PhiNode phi = newPhis.poll(); + if (phi.inferStamp()) { + for (PhiNode usagePhi : phi.usages().filter(PhiNode.class)) { + newPhis.add(usagePhi); } } } } + + private boolean isReadEliminable(FloatingReadNode n) { + return isWrites(n, n.lastLocationAccess(), n.graph().createNodeBitMap()); + } + + private boolean isWrites(FloatingReadNode n, Node lastLocationAccess, NodeBitMap visited) { + if (lastLocationAccess == null) { + return false; + } + if (visited.isMarked(lastLocationAccess)) { + return true; // dataflow loops must come from Phis assume them ok until proven wrong + } + if (lastLocationAccess instanceof WriteNode) { + WriteNode other = (WriteNode) lastLocationAccess; + return other.object() == n.object() && other.location() == n.location(); + } + if (lastLocationAccess instanceof PhiNode) { + visited.mark(lastLocationAccess); + for (ValueNode value : ((PhiNode) lastLocationAccess).values()) { + if (!isWrites(n, value, visited)) { + return false; + } + } + return true; + } + return false; + } + + private ValueNode getValue(Node lastLocationAccess, NodeMap<ValueNode> nodeMap) { + ValueNode exisiting = nodeMap.get(lastLocationAccess); + if (exisiting != null) { + return exisiting; + } + if (lastLocationAccess instanceof WriteNode) { + return ((WriteNode) lastLocationAccess).value(); + } + if (lastLocationAccess instanceof PhiNode) { + PhiNode phi = (PhiNode) lastLocationAccess; + PhiNode newPhi = phi.graph().add(new PhiNode(PhiType.Value, phi.merge())); + nodeMap.set(lastLocationAccess, newPhi); + for (ValueNode value : phi.values()) { + newPhi.addInput(getValue(value, nodeMap)); + } + newPhis.add(newPhi); + return newPhi; + } + throw GraalInternalError.shouldNotReachHere(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Thu Jul 12 18:58:36 2012 +0200 @@ -36,7 +36,7 @@ public final class PhiNode extends FloatingNode implements Canonicalizable, Node.IterableNodeType { public static enum PhiType { - Value(null), // normal value phis + Value(StampFactory.top()), // normal value phis Memory(StampFactory.dependency()); public final Stamp stamp; @@ -62,7 +62,9 @@ } /** - * Create a non-value phi ({@link PhiType#Memory} with the specified kind. + * Create a phi with the specified {@link PhiType}. + * If you use this to create a {@link PhiType#Value value} phi, its {@link Kind kind} will originally be {@link Kind#Void void} ; + * use {@link PhiNode#inferStamp()} to update it when it has valid inputs. * @param type the type of the new phi * @param merge the merge that the new phi belongs to */
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Thu Jul 12 18:58:36 2012 +0200 @@ -55,19 +55,16 @@ public ValueNode(Stamp stamp) { this.stamp = stamp; this.dependencies = new NodeInputList<>(this); - assert kind() != null && kind() == kind().stackKind() : kind() + " != " + kind().stackKind(); } public ValueNode(Stamp stamp, ValueNode... dependencies) { this.stamp = stamp; this.dependencies = new NodeInputList<>(this, dependencies); - assert kind() != null && kind() == kind().stackKind() : kind() + " != " + kind().stackKind(); } public ValueNode(Stamp stamp, List<ValueNode> dependencies) { this.stamp = stamp; this.dependencies = new NodeInputList<>(this, dependencies); - assert kind() != null && kind() == kind().stackKind() : kind() + " != " + kind().stackKind(); } public Stamp stamp() { @@ -176,6 +173,8 @@ for (ValueNode v : dependencies().nonNull()) { assertTrue(!(v.stamp() instanceof GenericStamp) || ((GenericStamp) v.stamp()).type() == GenericStampType.Dependency, "cannot depend on node with stamp %s", v.stamp()); } + assertTrue(kind() != null, "Should have a valid kind"); + assertTrue(kind() == kind().stackKind(), "Should have a stack kind : %s", kind()); return super.verify(); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/FloatStamp.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/FloatStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -91,6 +91,9 @@ @Override public Stamp meet(Stamp otherStamp) { + if (otherStamp == StampFactory.top()) { + return this; + } FloatStamp other = (FloatStamp) otherStamp; assert kind() == other.kind(); double meetUpperBound = Math.max(upperBound, other.upperBound);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/GenericStamp.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/GenericStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -53,6 +53,9 @@ @Override public Stamp meet(Stamp other) { + if (other == StampFactory.top()) { + return this; + } assert ((GenericStamp) other).type == type; return this; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -104,6 +104,9 @@ @Override public Stamp meet(Stamp otherStamp) { + if (otherStamp == StampFactory.top()) { + return this; + } IntegerStamp other = (IntegerStamp) otherStamp; assert kind() == other.kind(); long meetUpperBound = Math.max(upperBound, other.upperBound);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/ObjectStamp.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/ObjectStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -75,6 +75,9 @@ @Override public Stamp meet(Stamp otherStamp) { + if (otherStamp == StampFactory.top()) { + return this; + } ObjectStamp other = (ObjectStamp) otherStamp; ResolvedJavaType orType = meetTypes(type(), other.type()); boolean meetExactType = orType == type && orType == other.type && exactType && other.exactType;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Thu Jul 12 18:58:36 2012 +0200 @@ -28,7 +28,7 @@ public class StampFactory { - + private static final TopStamp top = new TopStamp(); private static final Stamp[] stampCache = new Stamp[Kind.values().length]; private static final Stamp objectStamp = new ObjectStamp(null, false, false); private static final Stamp objectNonNullStamp = new ObjectStamp(null, false, true); @@ -98,6 +98,10 @@ return positiveInt; } + public static Stamp top() { + return top; + } + public static Stamp forInteger(Kind kind, long lowerBound, long upperBound, long mask) { return new IntegerStamp(kind, lowerBound, upperBound, mask); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/TopStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -0,0 +1,42 @@ +/* + * Copyright (c) 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.nodes.type; + + +public final class TopStamp extends Stamp { + + TopStamp() { + super(null); + } + + @Override + public boolean alwaysDistinct(Stamp other) { + return false; + } + + @Override + public Stamp meet(Stamp other) { + return other; + } + +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/WordStamp.java Thu Jul 12 16:59:09 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/WordStamp.java Thu Jul 12 18:58:36 2012 +0200 @@ -56,6 +56,9 @@ @Override public Stamp meet(Stamp otherStamp) { + if (otherStamp == StampFactory.top()) { + return this; + } WordStamp other = (WordStamp) otherStamp; if (other.nonNull == nonNull) { return this;