Mercurial > hg > truffle
changeset 4649:5195b780d253
Merge
| author | Lukas Stadler <lukas.stadler@jku.at> |
|---|---|
| date | Mon, 20 Feb 2012 14:34:51 +0100 |
| parents | 83b4cc4df77a (diff) 8aa283b5e173 (current diff) |
| children | 8e39bd349bbb |
| files | |
| diffstat | 20 files changed, 966 insertions(+), 88 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompiler.java Mon Feb 20 14:34: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) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Feb 20 14:34: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;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java Mon Feb 20 14:34:51 2012 +0100 @@ -48,7 +48,7 @@ FixedNode current = start; do { - if (current instanceof Invoke) { + if (current instanceof InvokeWithExceptionNode) { invoke((Invoke) current); queueSuccessors(current, null); current = nextQueuedNode();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Mon Feb 20 14:34:51 2012 +0100 @@ -24,6 +24,7 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.debug.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.nodes.*; @@ -52,9 +53,11 @@ @Override protected void run(StructuredGraph graph) { - NodeWorkList nodeWorkList = graph.createNodeWorkList(!newNodes, MAX_ITERATION_PER_NODE); + NodeWorkList nodeWorkList = graph.createNodeWorkList(false, MAX_ITERATION_PER_NODE); if (newNodes) { nodeWorkList.addAll(graph.getNewNodes()); + } else { + nodeWorkList.addAll(new GraphOrder(graph)); } canonicalize(graph, nodeWorkList, runtime, target, assumptions);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Mon Feb 20 14:34:51 2012 +0100 @@ -28,6 +28,7 @@ import com.oracle.max.criutils.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.graph.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.cri.*; import com.oracle.max.graal.debug.*; import com.oracle.max.graal.graph.*; @@ -40,67 +41,6 @@ public class EscapeAnalysisPhase extends Phase { - public static class GraphOrder implements Iterable<Node> { - - private final ArrayList<Node> nodes = new ArrayList<>(); - - public GraphOrder(Graph graph) { - NodeBitMap visited = graph.createNodeBitMap(); - - for (ReturnNode node : graph.getNodes(ReturnNode.class)) { - visit(visited, node); - } - for (UnwindNode node : graph.getNodes(UnwindNode.class)) { - visit(visited, node); - } - for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) { - visit(visited, node); - } - } - - private void visit(NodeBitMap visited, Node node) { - if (node != null && !visited.isMarked(node)) { - visited.mark(node); - for (Node input : node.inputs()) { - visit(visited, input); - } - if (node.predecessor() != null) { - visit(visited, node.predecessor()); - } - nodes.add(node); - } - } - - @Override - public Iterator<Node> iterator() { - return new Iterator<Node>() { - - private int pos = 0; - - private void removeDeleted() { - while (pos < nodes.size() && nodes.get(pos).isDeleted()) { - pos++; - } - } - - @Override - public boolean hasNext() { - removeDeleted(); - return pos < nodes.size(); - } - - @Override - public Node next() { - return nodes.get(pos++); - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - }; - } - } public static class BlockExitState implements MergeableState<BlockExitState> { public final ValueNode[] fieldState;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java Mon Feb 20 14:34:51 2012 +0100 @@ -54,6 +54,21 @@ sortNodesWithinBlocks(graph); } + public void scheduleGraph() { + for (Block block : cfg.getBlocks()) { + List<Node> nodeList = nodesFor.get(block); + ScheduledNode last = null; + for (Node node : nodeList) { + if (!(node instanceof FrameState)) { + if (last != null) { + last.setScheduledNext((ScheduledNode) node); + } + last = (ScheduledNode) node; + } + } + } + } + public ControlFlowGraph getCFG() { return cfg; } @@ -273,9 +288,9 @@ if (canNotMove) { // (cwi) this was the assertion commented out below. However, it is failing frequently when the // scheduler is used for debug printing in early compiler phases. This was annoying during debugging - // when an excpetion breakpoint is set for assertion errors, so I changed it to a bailout. + // when an exception breakpoint is set for assertion errors, so I changed it to a bailout. if (b.getEndNode() instanceof ControlSplitNode) { - throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block whcih can not be move"). + throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move"). addContext(lastSorted). addContext(b.getEndNode()); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/UnscheduleNodes.java Mon Feb 20 14:34:51 2012 +0100 @@ -0,0 +1,81 @@ +/* + * 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.compiler.schedule; + +import java.util.*; + +import com.oracle.max.graal.compiler.graph.*; +import com.oracle.max.graal.compiler.types.*; +import com.oracle.max.graal.nodes.*; + +class UnscheduleState implements MergeableState<UnscheduleState> { + + public FixedWithNextNode last; + + @Override + public boolean merge(MergeNode merge, Collection<UnscheduleState> withStates) { + last = null; + return true; + } + + @Override + public void loopBegin(LoopBeginNode loop) { + last = null; + } + + @Override + public void loopEnds(LoopBeginNode loop, Collection<UnscheduleState> loopEndStates) { + last = null; + } + + @Override + public void afterSplit(FixedNode node) { + last = null; + } + + @Override + public UnscheduleState clone() { + return new UnscheduleState(); + } +} + +public class UnscheduleNodes extends ScheduledNodeIterator<UnscheduleState> { + + public UnscheduleNodes(FixedNode start) { + super(start, new UnscheduleState()); + } + + @Override + protected void node(ScheduledNode node) { + if (node instanceof FixedNode) { + if (state.last != null) { + state.last.setNext((FixedNode) node); + } + if (node instanceof FixedWithNextNode) { + state.last = (FixedWithNextNode) node; + } + } else { + node.setScheduledNext(null); + } + } +}
--- /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:34: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<Block> 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); + } +}
--- /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:34: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<TypeInfo> { + + private HashMap<ValueNode, PiNodeList> piNodes = new HashMap<>(); + + public TypeInfo(HashMap<ValueNode, PiNodeList> piNodes) { + this.piNodes.putAll(piNodes); + } + + @Override + public TypeInfo clone() { + return new TypeInfo(piNodes); + } + + @Override + public boolean merge(MergeNode merge, Collection<TypeInfo> withStates) { + if (merge.forwardEndCount() > 1) { + HashMap<ValueNode, PiNodeList> newPiNodes = new HashMap<>(); + for (Entry<ValueNode, PiNodeList> 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<TypeInfo> 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<TypeInfo> { + + public PropagateTypes(FixedNode start) { + super(start, new TypeInfo(new HashMap<ValueNode, PiNodeList>())); + } + + @Override + protected void node(ScheduledNode node) { + if (node instanceof Canonicalizable || node instanceof Invoke) { + NodeClassIterator iter = node.inputs().iterator(); + ArrayList<Node> 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); + } + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/types/ScheduledNodeIterator.java Mon Feb 20 14:34:51 2012 +0100 @@ -0,0 +1,189 @@ +/* + * Copyright (c) 2011, 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 com.oracle.max.graal.compiler.graph.*; +import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.nodes.*; + +public abstract class ScheduledNodeIterator<T extends MergeableState<T>> { + + private final NodeBitMap visitedEnds; + private final Deque<ScheduledNode> nodeQueue; + private final IdentityHashMap<ScheduledNode, T> nodeStates; + private final FixedNode start; + + protected T state; + + public ScheduledNodeIterator(FixedNode start, T initialState) { + visitedEnds = start.graph().createNodeBitMap(); + nodeQueue = new ArrayDeque<>(); + nodeStates = new IdentityHashMap<>(); + this.start = start; + this.state = initialState; + } + + public void apply() { + ScheduledNode current = start; + + do { + if (current instanceof LoopBeginNode) { + state.loopBegin((LoopBeginNode) current); + nodeStates.put(current, state); + state = state.clone(); + loopBegin((LoopBeginNode) current); + current = current.scheduledNext(); + assert current != null; + } else if (current instanceof LoopEndNode) { + loopEnd((LoopEndNode) current); + finishLoopEnds((LoopEndNode) current); + current = nextQueuedNode(); + } else if (current instanceof MergeNode) { + merge((MergeNode) current); + current = current.scheduledNext(); + assert current != null; + } else if (current instanceof EndNode) { + end((EndNode) current); + queueMerge((EndNode) current); + current = nextQueuedNode(); + } else if (current instanceof ControlSplitNode) { + controlSplit((ControlSplitNode) current); + queueSuccessors(current); + current = nextQueuedNode(); + } else { + ScheduledNode next = current.scheduledNext(); + node(current); + if (next == null) { + current = nextQueuedNode(); + } else { + current = next; + } + } + } while(current != null); + } + + private void queueSuccessors(ScheduledNode x) { + nodeStates.put(x, state); + for (Node node : x.successors()) { + if (node != null) { + nodeQueue.addFirst((FixedNode) node); + } + } + } + + private ScheduledNode nextQueuedNode() { + int maxIterations = nodeQueue.size(); + while (maxIterations-- > 0) { + ScheduledNode node = nodeQueue.removeFirst(); + if (node instanceof MergeNode) { + MergeNode merge = (MergeNode) node; + state = nodeStates.get(merge.forwardEndAt(0)).clone(); + ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1); + for (int i = 1; i < merge.forwardEndCount(); i++) { + T other = nodeStates.get(merge.forwardEndAt(i)); + assert other != null; + states.add(other); + } + boolean ready = state.merge(merge, states); + if (ready) { + return merge; + } else { + nodeQueue.addLast(merge); + } + } else { + assert node.predecessor() != null; + state = nodeStates.get(node.predecessor()).clone(); + state.afterSplit((FixedNode) node); + return node; + } + } + return null; + } + + private void queueMerge(EndNode end) { + assert !visitedEnds.isMarked(end); + assert !nodeStates.containsKey(end); + nodeStates.put(end, state); + visitedEnds.mark(end); + MergeNode merge = end.merge(); + boolean endsVisited = true; + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { + endsVisited = false; + break; + } + } + if (endsVisited) { + nodeQueue.add(merge); + } + } + + private void finishLoopEnds(LoopEndNode end) { + assert !visitedEnds.isMarked(end); + assert !nodeStates.containsKey(end); + nodeStates.put(end, state); + visitedEnds.mark(end); + LoopBeginNode begin = end.loopBegin(); + boolean endsVisited = true; + for (LoopEndNode le : begin.loopEnds()) { + if (!visitedEnds.isMarked(le)) { + endsVisited = false; + break; + } + } + if (endsVisited) { + ArrayList<T> states = new ArrayList<>(begin.loopEnds().count()); + for (LoopEndNode le : begin.orderedLoopEnds()) { + states.add(nodeStates.get(le)); + } + T loopBeginState = nodeStates.get(begin); + if (loopBeginState != null) { + loopBeginState.loopEnds(begin, states); + } + } + } + + protected abstract void node(ScheduledNode node); + + protected void end(EndNode endNode) { + node(endNode); + } + + protected void merge(MergeNode merge) { + node(merge); + } + + protected void loopBegin(LoopBeginNode loopBegin) { + node(loopBegin); + } + + protected void loopEnd(LoopEndNode loopEnd) { + node(loopEnd); + } + + protected void controlSplit(ControlSplitNode controlSplit) { + node(controlSplit); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphOrder.java Mon Feb 20 14:34:51 2012 +0100 @@ -0,0 +1,141 @@ +/* + * 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.util; + +import java.util.*; + +import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.nodes.*; + +public class GraphOrder implements Iterable<Node> { + + private final ArrayList<Node> nodes = new ArrayList<>(); + + private GraphOrder() { + } + + public GraphOrder(Graph graph) { + NodeBitMap visited = graph.createNodeBitMap(); + + for (ReturnNode node : graph.getNodes(ReturnNode.class)) { + visitForward(visited, node); + } + for (UnwindNode node : graph.getNodes(UnwindNode.class)) { + visitForward(visited, node); + } + for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) { + visitForward(visited, node); + } + } + + public static GraphOrder forwardGraph(Graph graph) { + GraphOrder result = new GraphOrder(); + + NodeBitMap visited = graph.createNodeBitMap(); + + for (ReturnNode node : graph.getNodes(ReturnNode.class)) { + result.visitForward(visited, node); + } + for (UnwindNode node : graph.getNodes(UnwindNode.class)) { + result.visitForward(visited, node); + } + for (DeoptimizeNode node : graph.getNodes(DeoptimizeNode.class)) { + result.visitForward(visited, node); + } + return result; + } + + public static GraphOrder backwardGraph(Graph graph) { + GraphOrder result = new GraphOrder(); + + NodeBitMap visited = graph.createNodeBitMap(); + + for (Node node : forwardGraph(graph)) { + result.visitBackward(visited, node); + } + return result; + } + + private void visitForward(NodeBitMap visited, Node node) { + if (node != null && !visited.isMarked(node)) { + visited.mark(node); + if (node.predecessor() != null) { + visitForward(visited, node.predecessor()); + } + if (node instanceof MergeNode) { + // make sure that the cfg predecessors of a MergeNode are processed first + MergeNode merge = (MergeNode) node; + for (int i = 0; i < merge.forwardEndCount(); i++) { + visitForward(visited, merge.forwardEndAt(i)); + } + } + for (Node input : node.inputs()) { + visitForward(visited, input); + } + nodes.add(node); + } + } + + private void visitBackward(NodeBitMap visited, Node node) { + if (node != null && !visited.isMarked(node)) { + visited.mark(node); + for (Node successor : node.successors()) { + visitBackward(visited, successor); + } + for (Node usage : node.usages()) { + visitBackward(visited, usage); + } + nodes.add(node); + } + } + + @Override + public Iterator<Node> iterator() { + return new Iterator<Node>() { + + private int pos = 0; + + private void removeDeleted() { + while (pos < nodes.size() && nodes.get(pos).isDeleted()) { + pos++; + } + } + + @Override + public boolean hasNext() { + removeDeleted(); + return pos < nodes.size(); + } + + @Override + public Node next() { + return nodes.get(pos++); + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } +}
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Mon Feb 20 14:34:51 2012 +0100 @@ -176,21 +176,24 @@ @SuppressWarnings("unchecked") public <T extends Node & ValueNumberable> T unique(T node) { assert checkValueNumberable(node); - if (!node.getNodeClass().hasOutgoingEdges()) { - Node cachedNode = cachedNodes.get(new CacheEntry(node)); - if (cachedNode != null && cachedNode.isAlive()) { - return (T) cachedNode; - } else { - Node result = add(node); - cachedNodes.put(new CacheEntry(node), result); - return (T) result; + + for (Node input : node.inputs()) { + if (input != null) { + for (Node usage : input.usages()) { + if (usage != node && node.getNodeClass().valueEqual(node, usage) && node.getNodeClass().edgesEqual(node, usage)) { + return (T) usage; + } + } + return add(node); } + } + Node cachedNode = cachedNodes.get(new CacheEntry(node)); + if (cachedNode != null && cachedNode.isAlive()) { + return (T) cachedNode; } else { - Node duplicate = findDuplicate(node); - if (duplicate != null) { - return (T) duplicate; - } - return add(node); + Node result = add(node); + cachedNodes.put(new CacheEntry(node), result); + return (T) result; } }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Mon Feb 20 14:34:51 2012 +0100 @@ -86,7 +86,7 @@ @Target(ElementType.METHOD) public static @interface NodeIntrinsic { /** - * Gets the {@link Node} subclass instantiated when intrinsifyng a call to the annotated method. + * Gets the {@link Node} subclass instantiated when intrinsifying a call to the annotated method. * If not specified, then the class in which the annotated method is declared is used * (and is assumed to be a {@link Node} subclass). */
--- a/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/ri/HotSpotRuntime.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/ri/HotSpotRuntime.java Mon Feb 20 14:34:51 2012 +0100 @@ -269,7 +269,7 @@ if (elementType.superType() != null) { AnchorNode anchor = graph.add(new AnchorNode()); graph.addBeforeFixed(storeIndexed, anchor); - ConstantNode type = graph.unique(ConstantNode.forCiConstant(elementType.getEncoding(Representation.ObjectHub), this, graph)); + ConstantNode type = ConstantNode.forCiConstant(elementType.getEncoding(Representation.ObjectHub), this, graph); value = graph.unique(new CheckCastNode(anchor, type, elementType, value)); } else { assert elementType.name().equals("Ljava/lang/Object;") : elementType.name();
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FixedWithNextNode.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FixedWithNextNode.java Mon Feb 20 14:34:51 2012 +0100 @@ -29,15 +29,13 @@ */ public abstract class FixedWithNextNode extends FixedNode { - @Successor private FixedNode next; // the immediate successor of the current node - public FixedNode next() { - return next; + assert scheduledNext() == null || scheduledNext() instanceof FixedNode : "next() cannot be used while the graph is scheduled"; + return (FixedNode) scheduledNext(); } public void setNext(FixedNode x) { - updatePredecessors(next, x); - next = x; + setScheduledNext(x); } public FixedWithNextNode(Stamp stamp) {
--- /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:34: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)); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/ScheduledNode.java Mon Feb 20 14:34:51 2012 +0100 @@ -0,0 +1,39 @@ +/* + * 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.graph.*; + +public class ScheduledNode extends Node { + + @Successor private ScheduledNode scheduledNext; // the immediate successor of the current node + + public ScheduledNode scheduledNext() { + return scheduledNext; + } + + public void setScheduledNext(ScheduledNode x) { + updatePredecessors(scheduledNext, x); + scheduledNext = x; + } +}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/ValueNode.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/ValueNode.java Mon Feb 20 14:34:51 2012 +0100 @@ -24,14 +24,13 @@ import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; -import com.oracle.max.graal.graph.*; import com.oracle.max.graal.nodes.type.*; /** * This class represents a value within the graph, including local variables, phis, and * all other instructions. */ -public abstract class ValueNode extends Node implements StampProvider { +public abstract class ValueNode extends ScheduledNode implements StampProvider { /** * The kind of this value. This is {@link CiKind#Void} for instructions that produce no value.
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/type/StampFactory.java Mon Feb 20 12:30:58 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/type/StampFactory.java Mon Feb 20 14:34:51 2012 +0100 @@ -101,7 +101,7 @@ return false; } else if (other.nonNull() || nonNull()) { // One of the two values cannot be null. - return !other.declaredType().isSubtypeOf(declaredType()) && !declaredType().isSubtypeOf(other.declaredType()); + return !other.declaredType().isInterface() && !declaredType().isInterface() && !other.declaredType().isSubtypeOf(declaredType()) && !declaredType().isSubtypeOf(other.declaredType()); } else { // Both values may be null. return false;
--- /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:34: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 <T extends Node & Node.IterableNodeType> void test(String snippet, Class<T> 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()); + } +}