# HG changeset patch # User Lukas Stadler # Date 1329744591 -3600 # Node ID 83b4cc4df77ac8b15efde28194b73a8edc04621d # Parent b32ccf2376d2b91c3a67957ae4013a94820f075e experimental: added PiNode and PropagateTypesPhase diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Mon Feb 20 14:28:39 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Mon Feb 20 14:29:51 2012 +0100 @@ -36,6 +36,7 @@ import com.oracle.max.graal.compiler.phases.PhasePlan.PhasePosition; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.compiler.target.*; +import com.oracle.max.graal.compiler.types.*; import com.oracle.max.graal.cri.*; import com.oracle.max.graal.debug.*; import com.oracle.max.graal.lir.*; @@ -144,6 +145,14 @@ new IntrinsificationPhase(runtime).apply(graph); } + if (GraalOptions.PropagateTypes) { + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } + + new PropagateTypesPhase(target, runtime, assumptions).apply(graph); + } + if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) { new InliningPhase(target, runtime, null, assumptions, plan).apply(graph); new DeadCodeEliminationPhase().apply(graph); @@ -154,6 +163,10 @@ new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } + if (GraalOptions.PropagateTypes) { + new PropagateTypesPhase(target, runtime, assumptions).apply(graph); + } + plan.runPhases(PhasePosition.HIGH_LEVEL, graph); if (GraalOptions.OptLoops) { diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Feb 20 14:28:39 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Feb 20 14:29:51 2012 +0100 @@ -141,6 +141,7 @@ public static boolean AssumeVerifiedBytecode = true; // Code generator settings + public static boolean PropagateTypes = true; public static boolean UseBranchPrediction = true; public static boolean UseExceptionProbability = true; public static boolean AllowExplicitExceptionChecks = true; diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PostOrderBlockIterator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PostOrderBlockIterator.java Mon Feb 20 14:29:51 2012 +0100 @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.types; + +import java.util.*; + +import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.lir.cfg.*; + +public abstract class PostOrderBlockIterator { + + private final BitMap visitedEndBlocks; + private final Deque blockQueue; + + public PostOrderBlockIterator(Block start, int blockCount) { + visitedEndBlocks = new BitMap(blockCount); + blockQueue = new ArrayDeque<>(); + blockQueue.add(start); + } + + public void apply() { + while (!blockQueue.isEmpty()) { + Block current = blockQueue.removeLast(); + block(current); + + for (int i = 0; i < current.getSuccessors().size(); i++) { + Block successor = current.getSuccessors().get(i); + if (successor.getPredecessors().size() > 1) { + queueMerge(current, successor); + } else { + blockQueue.addLast(successor); + } + } + } + } + + protected abstract void block(Block block); + + private void queueMerge(Block end, Block merge) { + visitedEndBlocks.set(end.getId()); + for (Block pred : merge.getPredecessors()) { + if (!visitedEndBlocks.get(pred.getId())) { + return; + } + } + blockQueue.addFirst(merge); + } +} diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PropagateTypesPhase.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/PropagateTypesPhase.java Mon Feb 20 14:29:51 2012 +0100 @@ -0,0 +1,264 @@ +/* + * 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.max.graal.compiler.types; + +import java.util.*; +import java.util.Map.Entry; + +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; +import com.oracle.max.graal.compiler.graph.*; +import com.oracle.max.graal.compiler.phases.*; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.debug.*; +import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.graph.NodeClass.NodeClassIterator; +import com.oracle.max.graal.graph.NodeClass.Position; +import com.oracle.max.graal.nodes.*; +import com.oracle.max.graal.nodes.calc.*; +import com.oracle.max.graal.nodes.java.*; +import com.oracle.max.graal.nodes.spi.*; +import com.oracle.max.graal.nodes.type.*; + +public class PropagateTypesPhase extends Phase { + + private final CiTarget target; + private final RiRuntime runtime; + private final CiAssumptions assumptions; + + private NodeWorkList changedNodes; + + public PropagateTypesPhase(CiTarget target, RiRuntime runtime, CiAssumptions assumptions) { + this.target = target; + this.runtime = runtime; + this.assumptions = assumptions; + } + + @Override + protected void run(StructuredGraph graph) { + + new DeadCodeEliminationPhase().apply(graph); + + changedNodes = graph.createNodeWorkList(false, 10); + + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph); + + schedule.scheduleGraph(); + Debug.dump(graph, "scheduled"); + + new PropagateTypes(graph.start()).apply(); + Debug.dump(graph, "after propagation"); + + new UnscheduleNodes(graph.start()).apply(); + + CanonicalizerPhase.canonicalize(graph, changedNodes, runtime, target, assumptions); + } + + private class PiNodeList { + + public final PiNodeList last; + public final ValueNode replacement; + public final int depth; + + public PiNodeList(ValueNode replacement, PiNodeList last) { + this.last = last; + this.replacement = replacement; + this.depth = last != null ? last.depth + 1 : 1; + } + + public PiNodeList merge(PiNodeList other) { + PiNodeList thisList = this; + PiNodeList otherList = other; + while (thisList.depth > otherList.depth) { + thisList = thisList.last; + } + while (otherList.depth > thisList.depth) { + otherList = otherList.last; + } + while (thisList != otherList) { + thisList = thisList.last; + otherList = otherList.last; + } + return thisList; + } + } + + private class TypeInfo implements MergeableState { + + private HashMap piNodes = new HashMap<>(); + + public TypeInfo(HashMap piNodes) { + this.piNodes.putAll(piNodes); + } + + @Override + public TypeInfo clone() { + return new TypeInfo(piNodes); + } + + @Override + public boolean merge(MergeNode merge, Collection withStates) { + if (merge.forwardEndCount() > 1) { + HashMap newPiNodes = new HashMap<>(); + for (Entry entry : piNodes.entrySet()) { + PiNodeList list = entry.getValue(); + for (TypeInfo info : withStates) { + PiNodeList other = info.piNodes.get(entry.getKey()); + if (other == null) { + list = null; + } else { + list = list.merge(other); + } + if (list == null) { + break; + } + } + if (list != null) { + newPiNodes.put(entry.getKey(), list); + } + } + piNodes = newPiNodes; + } + return true; + } + + @Override + public void loopBegin(LoopBeginNode loop) { + } + + @Override + public void loopEnds(LoopBeginNode loop, Collection loopEndStates) { + } + + @Override + public void afterSplit(FixedNode node) { + assert node.predecessor() != null; + assert node.predecessor() instanceof ControlSplitNode; +// TTY.println("after split: %s", node); + if (node.predecessor() instanceof IfNode) { + IfNode ifNode = (IfNode) node.predecessor(); + if (ifNode.compare() instanceof InstanceOfNode) { + InstanceOfNode instanceOf = (InstanceOfNode) ifNode.compare(); + assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor(); + if ((node == ifNode.trueSuccessor() && !instanceOf.negated()) || (node == ifNode.falseSuccessor() && instanceOf.negated())) { + ValueNode value = instanceOf.object(); + if (value.declaredType() != instanceOf.targetClass() || !value.stamp().nonNull()) { + PiNode piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(instanceOf.targetClass()))); + PiNodeList list = piNodes.get(value); + piNodes.put(value, new PiNodeList(piNode, list)); + } + } + } else if (ifNode.compare() instanceof CompareNode) { + CompareNode compare = (CompareNode) ifNode.compare(); + assert node == ifNode.trueSuccessor() || node == ifNode.falseSuccessor(); + if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.EQ) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.NE)) { + if (compare.y().isConstant()) { + ValueNode value = compare.x(); + PiNodeList list = piNodes.get(value); + piNodes.put(value, new PiNodeList(compare.y(), list)); + } + } else if ((node == ifNode.trueSuccessor() && compare.condition() == Condition.NE) || (node == ifNode.falseSuccessor() && compare.condition() == Condition.EQ)) { + if (!compare.x().isConstant() && compare.y().isNullConstant() && !compare.x().stamp().nonNull()) { + ValueNode value = compare.x(); + PiNode piNode; + if (value.exactType() != null) { + piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.exactType()))); + } else if (value.declaredType() != null) { + piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.declaredNonNull(value.declaredType()))); + } else { + piNode = node.graph().unique(new PiNode(value, (BeginNode) node, StampFactory.objectNonNull())); + } + PiNodeList list = piNodes.get(value); + piNodes.put(value, new PiNodeList(piNode, list)); + } + } + } + } + } + } + + private class Tool implements CanonicalizerTool { + @Override + public CiTarget target() { + return target; + } + + @Override + public CiAssumptions assumptions() { + return assumptions; + } + + @Override + public RiRuntime runtime() { + return runtime; + } + } + + private final Tool tool = new Tool(); + + private class PropagateTypes extends ScheduledNodeIterator { + + public PropagateTypes(FixedNode start) { + super(start, new TypeInfo(new HashMap())); + } + + @Override + protected void node(ScheduledNode node) { + if (node instanceof Canonicalizable || node instanceof Invoke) { + NodeClassIterator iter = node.inputs().iterator(); + ArrayList changedInputs = new ArrayList<>(); + while (iter.hasNext()) { + Position pos = iter.nextPosition(); + Node value = pos.get(node); + PiNodeList list = state.piNodes.get(value); + if (list != null) { + changedInputs.add(list.replacement instanceof PiNode ? value : null); + pos.set(node, list.replacement); + } else { + changedInputs.add(null); + } + } + + ValueNode canonical = null; + if (node instanceof Canonicalizable) { + canonical = ((Canonicalizable) node).canonical(tool); + } + + if (canonical == node) { + iter = node.inputs().iterator(); + int i = 0; + while (iter.hasNext()) { + Position pos = iter.nextPosition(); + if (changedInputs.get(i) != null) { + pos.set(node, changedInputs.get(i)); + } + i++; + } + } else { + changedNodes.add(node); + } + } + } + } +} diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PiNode.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PiNode.java Mon Feb 20 14:29:51 2012 +0100 @@ -0,0 +1,53 @@ +/* + * 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.max.graal.nodes; + +import com.oracle.max.graal.nodes.calc.*; +import com.oracle.max.graal.nodes.spi.*; +import com.oracle.max.graal.nodes.type.*; + + +public class PiNode extends FloatingNode implements LIRLowerable { + + @Input private ValueNode value; + @Input private BeginNode anchor; + + public ValueNode value() { + return value; + } + + public BeginNode anchor() { + return anchor; + } + + public PiNode(ValueNode value, BeginNode anchor, Stamp stamp) { + super(stamp); + this.value = value; + this.anchor = anchor; + } + + @Override + public void generate(LIRGeneratorTool generator) { + generator.setResult(this, generator.operand(value)); + } +} diff -r b32ccf2376d2 -r 83b4cc4df77a graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/TypeSystemTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/TypeSystemTest.java Mon Feb 20 14:29:51 2012 +0100 @@ -0,0 +1,71 @@ +/* + * 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.max.graal.compiler.tests; + +import org.junit.*; + +import com.oracle.max.graal.compiler.phases.*; +import com.oracle.max.graal.compiler.types.*; +import com.oracle.max.graal.debug.*; +import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.nodes.*; +import com.oracle.max.graal.nodes.java.*; + +/** + * In the following tests, the scalar type system of the compiler should be complete enough to see the relation between the different conditions. + */ +public class TypeSystemTest extends GraphTest { + + @Test + public void test1() { + test("test1Snippet", CheckCastNode.class); + } + + public static int test1Snippet(Object a) { + if (a instanceof Boolean) { + return ((Boolean) a).booleanValue() ? 0 : 1; + } + return 1; + } + + @Test + public void test2() { + test("test2Snippet", CheckCastNode.class); + } + + public static int test2Snippet(Object a) { + if (a instanceof Integer) { + return ((Number) a).intValue(); + } + return 1; + } + + private void test(String snippet, Class clazz) { + StructuredGraph graph = parse(snippet); + Debug.dump(graph, "Graph"); + new CanonicalizerPhase(null, runtime(), null).apply(graph); + new PropagateTypesPhase(null, null, null).apply(graph); + Debug.dump(graph, "Graph"); + Assert.assertFalse("shouldn't have nodes of type " + clazz, graph.getNodes(clazz).iterator().hasNext()); + } +}