# HG changeset patch # User Thomas Wuerthinger # Date 1339078519 -7200 # Node ID a4dfee0b8fbddbc08f089ddfc52b90441719b4b0 # Parent 80abea6e5e27adcfe39b66e454fdc1d041655859# Parent 35f9b57d70cb6c97d4015ff2843151383f8f88bd Merge. diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,99 @@ +/* + * 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.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; + +public class LoopEx { + private final Loop lirLoop; + private LoopFragmentInside inside; + private LoopFragmentWhole whole; + private boolean isCounted; //TODO (gd) detect + private LoopsData data; + + LoopEx(Loop lirLoop, LoopsData data) { + this.lirLoop = lirLoop; + this.data = data; + } + + public Loop lirLoop() { + return lirLoop; + } + + public LoopFragmentInside inside() { + if (inside == null) { + inside = new LoopFragmentInside(this); + } + return inside; + } + + public LoopFragmentWhole whole() { + if (whole == null) { + whole = new LoopFragmentWhole(this); + } + return whole; + } + + public LoopFragmentInsideFrom insideFrom(FixedNode point) { + // TODO (gd) + return null; + } + + public LoopFragmentInsideBefore insideBefore(FixedNode point) { + // TODO (gd) + return null; + } + + public boolean isInvariant(Node n) { + return !whole().contains(n); + } + + public LoopBeginNode loopBegin() { + return lirLoop().loopBegin(); + } + + public FixedNode predecessor() { + return (FixedNode) loopBegin().forwardEnd().predecessor(); + } + + public FixedNode entryPoint() { + return loopBegin().forwardEnd(); + } + + public boolean isCounted() { + return isCounted; + } + + public LoopEx parent() { + if (lirLoop.parent == null) { + return null; + } + return data.loop(lirLoop.parent); + } + + public int size() { + return whole().nodes().count(); + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,264 @@ +/* + * 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.compiler.loop; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.util.*; + + +public abstract class LoopFragment { + private final LoopEx loop; + private final LoopFragment original; + protected NodeBitMap nodes; + protected boolean nodesReady; + private Map duplicationMap; + + public LoopFragment(LoopEx loop) { + this(loop, null); + this.nodesReady = true; + } + + public LoopFragment(LoopEx loop, LoopFragment original) { + this.loop = loop; + this.original = original; + this.nodesReady = false; + } + + public LoopEx loop() { + return loop; + } + + public abstract LoopFragment duplicate(); + + public abstract void insertBefore(LoopEx l); + + public void disconnect() { + // TODO (gd) possibly abstract + } + + public boolean contains(Node n) { + return nodes().contains(n); + } + + @SuppressWarnings("unchecked") + public New getDuplicatedNode(Old n) { + assert isDuplicate(); + return (New) duplicationMap.get(n); + } + + protected void putDuplicatedNode(Old oldNode, New newNode) { + duplicationMap.put(oldNode, newNode); + } + + public boolean isDuplicate() { + return original != null; + } + + public LoopFragment original() { + return original; + } + + public abstract NodeIterable nodes(); + + public StructuredGraph graph() { + return (StructuredGraph) loop.loopBegin().graph(); + } + + protected abstract DuplicationReplacement getDuplicationReplacement(); + + protected abstract void finishDuplication(); + + protected void patchNodes(final DuplicationReplacement dataFix) { + if (isDuplicate() && !nodesReady) { + assert !original.isDuplicate(); + final DuplicationReplacement cfgFix = getDuplicationReplacement(); + DuplicationReplacement dr; + if (cfgFix == null) { + dr = dataFix; + } else { + dr = new DuplicationReplacement() { + @Override + public Node replacement(Node o) { + Node r1 = dataFix.replacement(o); + if (r1 != o) { + assert cfgFix.replacement(o) == o; + return r1; + } + Node r2 = cfgFix.replacement(o); + if (r2 != o) { + return r2; + } + return o; + } + }; + } + duplicationMap = graph().addDuplicates(nodes(), dr); + finishDuplication(); + nodesReady = true; + } else { + //TODO (gd) apply fix ? + } + } + + public static Collection toHirBlocks(Collection blocks) { + List hir = new ArrayList<>(blocks.size()); + for (Block b : blocks) { + hir.add(b.getBeginNode()); + } + return hir; + } + + protected static NodeBitMap computeNodes(Graph graph, Collection blocks) { + return computeNodes(graph, blocks, Collections.emptyList()); + } + + protected static NodeBitMap computeNodes(Graph graph, Collection blocks, Collection earlyExits) { + NodeBitMap nodes = graph.createNodeBitMap(true); + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + if (n instanceof Invoke) { + nodes.mark(((Invoke) n).callTarget()); + } + if (n instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) n).stateAfter(); + if (stateAfter != null) { + nodes.mark(stateAfter); + } + } + nodes.mark(n); + } + } + for (BeginNode earlyExit : earlyExits) { + FrameState stateAfter = earlyExit.stateAfter(); + assert stateAfter != null; + nodes.mark(stateAfter); + nodes.mark(earlyExit); + for (ValueProxyNode proxy : earlyExit.proxies()) { + nodes.mark(proxy); + } + } + + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + for (Node usage : n.usages()) { + markFloating(usage, nodes); + } + } + } + + return nodes; + } + + private static boolean markFloating(Node n, NodeBitMap loopNodes) { + if (loopNodes.isMarked(n)) { + return true; + } + if (n instanceof FixedNode) { + return false; + } + boolean mark = false; + if (n instanceof PhiNode) { + PhiNode phi = (PhiNode) n; + mark = loopNodes.isMarked(phi.merge()); + if (mark) { + loopNodes.mark(n); + } else { + return false; + } + } + for (Node usage : n.usages()) { + if (markFloating(usage, loopNodes)) { + mark = true; + } + } + if (mark) { + loopNodes.mark(n); + return true; + } + return false; + } + + /** + * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with the original fragment's exits. + */ + protected void mergeEarlyExits() { + assert isDuplicate(); + StructuredGraph graph = graph(); + for (BeginNode earlyExit : toHirBlocks(original().loop().lirLoop().exits)) { + if (!this.contains(earlyExit)) { + continue; + } + BeginNode newEarlyExit = getDuplicatedNode(earlyExit); + assert newEarlyExit != null; + MergeNode merge = graph.add(new MergeNode()); + EndNode originalEnd = graph.add(new EndNode()); + EndNode newEnd = graph.add(new EndNode()); + merge.addForwardEnd(originalEnd); + merge.addForwardEnd(newEnd); + FixedNode next = earlyExit.next(); + earlyExit.setNext(originalEnd); + newEarlyExit.setNext(newEnd); + merge.setNext(next); + FrameState exitState = earlyExit.stateAfter(); + FrameState state = exitState.duplicate(); + merge.setStateAfter(state); + + for (Node anchored : earlyExit.anchored().snapshot()) { + anchored.replaceFirstInput(earlyExit, merge); + } + + for (ValueProxyNode vpn : earlyExit.proxies().snapshot()) { + ValueNode replaceWith; + ValueProxyNode newVpn = getDuplicatedNode(vpn); + if (newVpn != null) { + PhiNode phi = graph.add(vpn.type() == PhiType.Value ? new PhiNode(vpn.kind(), merge) : new PhiNode(vpn.type(), merge)); + phi.addInput(vpn); + phi.addInput(newVpn); + if (vpn.type() == PhiType.Value) { + replaceWith = phi; + } else { + assert vpn.type() == PhiType.Virtual; + ValueNode vof = GraphUtil.unProxify(vpn); + ValueNode newVof = GraphUtil.unProxify(newVpn); + replaceWith = GraphUtil.mergeVirtualChain(graph, vof, newVof, phi, earlyExit, newEarlyExit, merge); + } + } else { + replaceWith = vpn.value(); + } + state.replaceFirstInput(vpn, replaceWith); + for (Node usage : vpn.usages().snapshot()) { + if (usage != exitState && !merge.isPhiAtMerge(usage)) { + usage.replaceFirstInput(vpn, replaceWith); + } + } + } + } + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInside.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInside.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,248 @@ +/* + * 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.compiler.loop; + +import java.util.*; + +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.*; +import com.oracle.graal.nodes.util.*; + + +public class LoopFragmentInside extends LoopFragment { + /** mergedInitializers. + * When an inside fragment's (loop)ends are merged to create a unique exit point, + * some phis must be created : they phis together all the back-values of the loop-phis + * These can then be used to update the loop-phis' forward edge value ('initializer') in the peeling case. + * In the unrolling case they will be used as the value that replace the loop-phis of the duplicated inside fragment + */ + private Map mergedInitializers; + private final DuplicationReplacement dataFix = new DuplicationReplacement() { + @Override + public Node replacement(Node oriInput) { + if (!(oriInput instanceof ValueNode)) { + return oriInput; + } + return prim((ValueNode) oriInput); + } + }; + + public LoopFragmentInside(LoopEx loop) { + super(loop); + } + + public LoopFragmentInside(LoopFragmentInside original) { + super(original.loop(), original); + } + + @Override + public LoopFragmentInside duplicate() { + assert !isDuplicate(); + return new LoopFragmentInside(this); + } + + @Override + public LoopFragmentInside original() { + return (LoopFragmentInside) super.original(); + } + + public void appendInside(LoopEx loop) { + // TODO (gd) + } + + @Override + public void insertBefore(LoopEx loop) { + if (this.loop() != loop) { + throw new UnsupportedOperationException(); + } + patchNodes(dataFix); + + BeginNode end = mergeEnds(); + + original().patchPeeling(this); + + mergeEarlyExits(); + + FixedNode entry = getDuplicatedNode(this.loop().loopBegin()); + loop.entryPoint().replaceAtPredecessor(entry); + end.setNext(loop.entryPoint()); + } + + @Override + public NodeIterable nodes() { + if (nodes == null) { + LoopFragmentWhole whole = loop().whole(); + whole.nodes(); // init nodes bitmap in whole + nodes = whole.nodes.copy(); + // remove the loop begin, its FS and the phis + LoopBeginNode loopBegin = loop().loopBegin(); + //nodes.clear(loopBegin); + nodes.clear(loopBegin.stateAfter()); + for (PhiNode phi : loopBegin.phis()) { + nodes.clear(phi); + } + } + return nodes; + } + + @Override + protected DuplicationReplacement getDuplicationReplacement() { + final LoopBeginNode loopBegin = loop().loopBegin(); + final StructuredGraph graph = graph(); + return new DuplicationReplacement() { + @Override + public Node replacement(Node original) { + if (original == loopBegin) { + return graph.add(new BeginNode()); + } + if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) { + return graph.add(new BeginNode()); + } + if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) { + return graph.add(new EndNode()); + } + return original; + } + }; + } + + @Override + protected void finishDuplication() { + // TODO (gd) ? + + } + + private void patchPeeling(LoopFragmentInside peel) { + LoopBeginNode loopBegin = loop().loopBegin(); + StructuredGraph graph = (StructuredGraph) loopBegin.graph(); + List newPhis = new LinkedList<>(); + for (PhiNode phi : loopBegin.phis().snapshot()) { + ValueNode first; + if (loopBegin.loopEnds().count() == 1) { + ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value + first = peel.prim(b); // corresponding value in the peel + } else { + first = peel.mergedInitializers.get(phi); + } + // create a new phi (we don't patch the old one since some usages of the old one may still be valid) + PhiNode newPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), loopBegin) : new PhiNode(phi.type(), loopBegin)); + newPhi.addInput(first); + for (LoopEndNode end : loopBegin.orderedLoopEnds()) { + newPhi.addInput(phi.valueAt(end)); + } + peel.putDuplicatedNode(phi, newPhi); + newPhis.add(newPhi); + for (Node usage : phi.usages().snapshot()) { + if (peel.getDuplicatedNode(usage) != null) { // patch only usages that should use the new phi ie usages that were peeled + usage.replaceFirstInput(phi, newPhi); + } + } + } + // check new phis to see if they have as input some old phis, replace those inputs with the new corresponding phis + for (PhiNode phi : newPhis) { + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode v = phi.valueAt(i); + if (loopBegin.isPhiAtMerge(v)) { + PhiNode newV = peel.getDuplicatedNode((PhiNode) v); + if (newV != null) { + phi.setValueAt(i, newV); + } + } + } + } + } + + /** + * Gets the corresponding value in this fragment. + * @param peel the peel to look into + * @param b original value + * @return corresponding value in the peel + */ + private ValueNode prim(ValueNode b) { + LoopBeginNode loopBegin = loop().loopBegin(); + if (loopBegin.isPhiAtMerge(b)) { + PhiNode phi = (PhiNode) b; + return phi.valueAt(loopBegin.forwardEnd()); + } else if (nodesReady) { + ValueNode v = getDuplicatedNode(b); + if (v == null) { + return b; + } + return v; + } else { + return b; + } + } + + private BeginNode mergeEnds() { + List endsToMerge = new LinkedList<>(); + Map reverseEnds = new HashMap<>(); // map peel's exit to the corresponding loop exits + LoopBeginNode loopBegin = loop().loopBegin(); + for (LoopEndNode le : loopBegin.loopEnds()) { + EndNode duplicate = getDuplicatedNode(le); + if (duplicate != null) { + endsToMerge.add(duplicate); + reverseEnds.put(duplicate, le); + } + } + mergedInitializers = new IdentityHashMap<>(); + BeginNode newExit; + StructuredGraph graph = graph(); + if (endsToMerge.size() == 1) { + EndNode end = endsToMerge.get(0); + assert end.usages().count() == 0; + newExit = graph.add(new BeginNode()); + end.replaceAtPredecessor(newExit); + end.safeDelete(); + } else { + assert endsToMerge.size() > 1; + MergeNode newExitMerge = graph.add(new MergeNode()); + newExit = newExitMerge; + FrameState duplicateState = loopBegin.stateAfter().duplicate(); + newExitMerge.setStateAfter(duplicateState); + for (EndNode end : endsToMerge) { + newExitMerge.addForwardEnd(end); + } + + for (PhiNode phi : loopBegin.phis().snapshot()) { + PhiNode firstPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), newExitMerge) : new PhiNode(phi.type(), newExitMerge)); + for (EndNode end : newExitMerge.forwardEnds()) { + LoopEndNode loopEnd = reverseEnds.get(end); + ValueNode prim = prim(phi.valueAt(loopEnd)); + assert prim != null; + firstPhi.addInput(prim); + } + ValueNode initializer = firstPhi; + duplicateState.replaceFirstInput(phi, firstPhi); // fix the merge's state after + if (phi.type() == PhiType.Virtual) { + initializer = GraphUtil.mergeVirtualChain(graph, firstPhi, newExitMerge); + } + mergedInitializers.put(phi, initializer); + } + } + return newExit; + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInsideBefore.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInsideBefore.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,58 @@ +/* + * 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.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; + + +public class LoopFragmentInsideBefore extends LoopFragmentInside { + private final FixedNode point; + + public LoopFragmentInsideBefore(LoopEx loop, FixedNode point) { + super(loop); + this.point = point; + } + + // duplicates lazily + public LoopFragmentInsideBefore(LoopFragmentInsideBefore original) { + super(original); + this.point = original.point(); + } + + public FixedNode point() { + return point; + } + + @Override + public LoopFragmentInsideBefore duplicate() { + return new LoopFragmentInsideBefore(this); + } + + @Override + public NodeIterable nodes() { + // TODO Auto-generated method stub + return null; + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInsideFrom.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentInsideFrom.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,58 @@ +/* + * 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.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; + + +public class LoopFragmentInsideFrom extends LoopFragmentInside { + private final FixedNode point; + + public LoopFragmentInsideFrom(LoopEx loop, FixedNode point) { + super(loop); + this.point = point; + } + + // duplicates lazily + public LoopFragmentInsideFrom(LoopFragmentInsideFrom original) { + super(original); + this.point = original.point(); + } + + public FixedNode point() { + return point; + } + + @Override + public LoopFragmentInsideFrom duplicate() { + return new LoopFragmentInsideFrom(this); + } + + @Override + public NodeIterable nodes() { + // TODO Auto-generated method stub + return null; + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,68 @@ +/* + * 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.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.lir.cfg.*; + + +public class LoopFragmentWhole extends LoopFragment { + + public LoopFragmentWhole(LoopEx loop) { + super(loop); + } + + @Override + public LoopFragmentWhole duplicate() { + // TODO (gd) do not forget to make a FULL loop : do not forget the forward end which is not part of the original loop stricto sensus + return null; + } + + @Override + public NodeIterable nodes() { + if (nodes == null) { + Loop lirLoop = loop().lirLoop(); + nodes = LoopFragment.computeNodes(graph(), LoopFragment.toHirBlocks(lirLoop.blocks), LoopFragment.toHirBlocks(lirLoop.exits)); + } + return nodes; + } + + @Override + protected DuplicationReplacement getDuplicationReplacement() { + return null; + } + + @Override + protected void finishDuplication() { + // TODO Auto-generated method stub + + } + + @Override + public void insertBefore(LoopEx loop) { + // TODO Auto-generated method stub + + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformDataResolver.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformDataResolver.java Wed Jun 06 17:20:15 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,201 +0,0 @@ -/* - * 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.compiler.loop; - -import java.util.*; -import java.util.Map.Entry; - -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.NodeClass.NodeClassIterator; -import com.oracle.graal.graph.NodeClass.Position; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; - - - -public class LoopTransformDataResolver { - private List resolvables = new LinkedList<>(); - - private abstract static class ResolvableSuperBlock { - final SuperBlock block; - public ResolvableSuperBlock(SuperBlock block) { - this.block = block; - } - public abstract void resolve(); - } - - private static class PeeledResolvableSuperBlock extends ResolvableSuperBlock{ - final SuperBlock peel; - final boolean nextIteration; - public PeeledResolvableSuperBlock(SuperBlock peeled, SuperBlock peel, boolean nextIteration) { - super(peeled); - this.peel = peel; - this.nextIteration = nextIteration; - } - @Override - public void resolve() { - if (nextIteration) { - SuperBlock peeled = block; - LoopBeginNode loopBegin = (LoopBeginNode) peeled.getEntry(); - Map dup = peel.getDuplicationMapping(); - List newPhis = new LinkedList<>(); - for (PhiNode phi : loopBegin.phis().snapshot()) { - ValueNode first = null; - StructuredGraph graph = (StructuredGraph) loopBegin.graph(); - if (loopBegin.loopEnds().count() == 1) { - ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value - first = prim(b); // corresponding value in the peel - } else { - Map reverseEnds = new HashMap<>(); // map peel's exit to the corresponding loop exits - MergeNode merge = null; // look for the merge if the peel's exits - for (LoopEndNode end : loopBegin.loopEnds()) { - EndNode newEnd = (EndNode) dup.get(end); - if (newEnd != null) { - reverseEnds.put(newEnd, end); - if (prim(phi.valueAt(end)) != null) { - merge = newEnd.merge(); - } - } - } - if (merge != null) { // found values of interest (backedge values that exist in the peel) - PhiNode firstPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), merge) : new PhiNode(phi.type(), merge)); - for (EndNode end : merge.forwardEnds()) { - LoopEndNode loopEnd = reverseEnds.get(end); - ValueNode prim = prim(phi.valueAt(loopEnd)); - assert prim != null; - firstPhi.addInput(prim); - } - first = firstPhi; - merge.stateAfter().replaceFirstInput(phi, firstPhi); // fix the merge's state after (see SuperBlock.mergeExits) - if (phi.type() == PhiType.Virtual) { - first = SuperBlock.mergeVirtualChain(graph, firstPhi, merge); - } - } - } - if (first != null) { // create a new phi (we don't patch the old one since some usages of the old one may still be valid) - PhiNode newPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), loopBegin) : new PhiNode(phi.type(), loopBegin)); - newPhi.addInput(first); - for (LoopEndNode end : loopBegin.orderedLoopEnds()) { - newPhi.addInput(phi.valueAt(end)); - } - dup.put(phi, newPhi); - newPhis.add(newPhi); - for (Node usage : phi.usages().snapshot()) { - if (dup.get(usage) != null) { // patch only usages that should use the new phi ie usages that were peeled - usage.replaceFirstInput(phi, newPhi); - } - } - } - } - // check new phis to see if they have as input some old phis, replace those inputs with the new corresponding phis - for (PhiNode phi : newPhis) { - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode v = phi.valueAt(i); - if (loopBegin.isPhiAtMerge(v)) { - PhiNode newV = (PhiNode) dup.get(v); - if (newV != null) { - phi.setValueAt(i, newV); - } - } - } - } - } - } - - /** - * Gets the corresponding value in the peel. - * @param b original value - * @return corresponding value in the peel - */ - public ValueNode prim(ValueNode b) { - SuperBlock peeled = block; - LoopBeginNode loopBegin = (LoopBeginNode) peeled.getEntry(); - Map dup = peel.getDuplicationMapping(); - if (loopBegin.isPhiAtMerge(b)) { - PhiNode phi = (PhiNode) b; - return phi.valueAt(loopBegin.forwardEnd()); - } else { - ValueNode v = (ValueNode) dup.get(b); - if (v == null && nextIteration) { - // may not be right in inversion case - return b; - } - return v; - } - } - } - - private static class PeelResolvableSuperBlock extends ResolvableSuperBlock{ - final SuperBlock peeled; - public PeelResolvableSuperBlock(SuperBlock peel, SuperBlock peeled) { - super(peel); - this.peeled = peeled; - } - @Override - public void resolve() { - SuperBlock peel = block; - LoopBeginNode loopBegin = (LoopBeginNode) peeled.getEntry(); - for (Entry entry : peel.getDuplicationMapping().entrySet()) { - Node oriNode = entry.getKey(); - Node newNode = entry.getValue(); - for (NodeClassIterator iter = oriNode.inputs().iterator(); iter.hasNext();) { - Position pos = iter.nextPosition(); - if (pos.isValidFor(newNode, oriNode) && pos.get(newNode) == null) { - Node oriInput = pos.get(oriNode); - // oriInput is not checked against null because oriNode.inputs().iterator() only iterates over non-null pos/input - Node v; - if (loopBegin.isPhiAtMerge(oriInput)) { - PhiNode phi = (PhiNode) oriInput; - v = phi.valueAt(loopBegin.forwardEnd()); - } else { - v = oriInput; - } - pos.set(newNode, v); - } - } - } - } - } - - public class WholeLoop { - private final SuperBlock from; - public WholeLoop(SuperBlock from) { - this.from = from; - } - public void peeled(SuperBlock peel) { - resolvables.add(new PeelResolvableSuperBlock(peel, from)); - resolvables.add(new PeeledResolvableSuperBlock(from, peel, true)); - } - - } - - public void resolve() { - for (ResolvableSuperBlock resolvable : this.resolvables) { - resolvable.resolve(); - } - } - - public WholeLoop wholeLoop(SuperBlock block) { - return new WholeLoop(block); - } -} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformUtil.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformUtil.java Wed Jun 06 17:20:15 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,68 +0,0 @@ -/* - * 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.compiler.loop; - -import java.util.*; - -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - - -public class LoopTransformUtil { - - public static void peel(Loop loop) { - peel(loop, wholeLoop(loop)); - } - - public static void peel(Loop loop, SuperBlock wholeLoop) { - SuperBlock peel = wholeLoop.duplicate(true); // duplicates the nodes, merges early exits - - peel.insertBefore(loop.loopBegin().forwardEnd()); // connects peeled part's CFG - - LoopTransformDataResolver resolver = new LoopTransformDataResolver(); - resolver.wholeLoop(wholeLoop).peeled(peel); // block (comming from the loop) was peeled into peel - resolver.resolve(); - - peel.finishDuplication(); - } - - public static SuperBlock wholeLoop(Loop loop) { - List blocks = new LinkedList<>(); - List earlyExits = new LinkedList<>(); - for (Block b : loop.blocks) { - blocks.add(b.getBeginNode()); - } - for (Block b : loop.exits) { - earlyExits.add(b.getBeginNode()); - } - return new SuperBlock(loop.loopBegin(), loop.loopBegin(), blocks, earlyExits); - } - - public static int estimateSize(Loop loop) { - int fixed = 0; - for (Block b : loop.blocks) { - fixed += b.getBeginNode().getBlockNodes().count(); - } - return fixed * 3; - } -} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformations.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformations.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,88 @@ +/* + * 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.compiler.loop; + +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.nodes.*; + + +public abstract class LoopTransformations { + public static void invert(LoopEx loop, FixedNode point) { + LoopFragmentInsideBefore head = loop.insideBefore(point); + LoopFragmentInsideBefore duplicate = head.duplicate(); + head.disconnect(); + head.insertBefore(loop); + duplicate.appendInside(loop); + } + + public static void peel(LoopEx loop) { + loop.inside().duplicate().insertBefore(loop); + } + + public static void fullUnroll(LoopEx loop) { + //assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count + LoopBeginNode loopBegin = loop.loopBegin(); + StructuredGraph graph = (StructuredGraph) loopBegin.graph(); + while (!loopBegin.isDeleted()) { + int mark = graph.getMark(); + peel(loop); + new CanonicalizerPhase(null, null, null, mark, null).apply(graph); + } + } + + public static void unswitch(LoopEx loop, IfNode ifNode) { + // duplicate will be true case, original will be false case + LoopFragmentWhole duplicateLoop = loop.whole().duplicate(); + StructuredGraph graph = (StructuredGraph) ifNode.graph(); + BeginNode tempBegin = graph.add(new BeginNode()); + loop.entryPoint().replaceAtPredecessor(tempBegin); + double takenProbability = ifNode.probability(ifNode.blockSuccessorIndex(ifNode.trueSuccessor())); + IfNode newIf = graph.add(new IfNode(ifNode.compare(), duplicateLoop.loop().entryPoint(), loop.entryPoint(), takenProbability)); + tempBegin.setNext(newIf); + ifNode.setCompare(graph.unique(ConstantNode.forBoolean(false, graph))); + IfNode duplicateIf = duplicateLoop.getDuplicatedNode(ifNode); + duplicateIf.setCompare(graph.unique(ConstantNode.forBoolean(true, graph))); + // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) + } + + public static void unroll(LoopEx loop, int factor) { + assert loop.isCounted(); + if (factor > 0) { + throw new UnsupportedOperationException(); + } + // TODO (gd) implement counted loop + LoopFragmentWhole main = loop.whole(); + LoopFragmentWhole prologue = main.duplicate(); + prologue.insertBefore(loop); + //CountedLoopBeginNode counted = prologue.countedLoop(); + //StructuredGraph graph = (StructuredGraph) counted.graph(); + //ValueNode tripCountPrologue = counted.tripCount(); + //ValueNode tripCountMain = counted.tripCount(); + //graph.replaceFloating(tripCountPrologue, "tripCountPrologue % factor"); + //graph.replaceFloating(tripCountMain, "tripCountMain - (tripCountPrologue % factor)"); + LoopFragmentInside inside = loop.inside(); + for (int i = 0; i < factor; i++) { + inside.duplicate().appendInside(loop); + } + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,75 @@ +/* + * 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.compiler.loop; + +import java.util.*; + +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; + +public class LoopsData { + private Map lirLoopToEx = new IdentityHashMap<>(); + private Map loopBeginToEx = new IdentityHashMap<>(); + + public LoopsData(StructuredGraph graph) { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, false); + for (Loop lirLoop : cfg.getLoops()) { + LoopEx ex = new LoopEx(lirLoop, this); + lirLoopToEx.put(lirLoop, ex); + loopBeginToEx.put(ex.loopBegin(), ex); + } + } + + public LoopEx loop(Loop lirLoop) { + return lirLoopToEx.get(lirLoop); + } + + public LoopEx loop(LoopBeginNode loopBegin) { + return loopBeginToEx.get(loopBegin); + } + + public Collection loops() { + return lirLoopToEx.values(); + } + + public List outterFirst() { + ArrayList loops = new ArrayList<>(loops()); + Collections.sort(loops, new Comparator() { + @Override + public int compare(LoopEx o1, LoopEx o2) { + return o1.lirLoop().depth - o2.lirLoop().depth; + } + }); + return loops; + } + + public Collection countedLoops() { + List counted = new LinkedList<>(); + for (LoopEx loop : loops()) { + if (loop.isCounted()) { + counted.add(loop); + } + } + return counted; + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/SuperBlock.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/SuperBlock.java Wed Jun 06 17:20:15 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,438 +0,0 @@ -/* - * 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.compiler.loop; - -import java.util.*; -import java.util.Map.Entry; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.util.*; -import com.oracle.graal.nodes.virtual.*; - -public class SuperBlock { - protected BeginNode entry; - protected BeginNode exit; - protected List blocks; - protected List earlyExits; - protected Map duplicationMapping; - protected SuperBlock original; - protected NodeBitMap allNodes; - protected NodeBitMap allNodesExcludeLoopPhi; - - public SuperBlock(BeginNode entry, BeginNode exit, List blocks, List earlyExits) { - this.entry = entry; - this.exit = exit; - this.blocks = blocks; - this.earlyExits = earlyExits; - assert blocks.contains(entry); - assert !blocks.contains(exit) || exit == entry; - } - - public Map getDuplicationMapping() { - return duplicationMapping; - } - - public BeginNode getEntry() { - return entry; - } - - public NodeBitMap nodes() { - if (allNodes == null) { - allNodes = computeNodes(); - } - return allNodes; - } - - private NodeBitMap nodesExcludeLoopPhi() { - if (allNodesExcludeLoopPhi == null) { - allNodesExcludeLoopPhi = nodes().copy(); - if (entry instanceof LoopBeginNode) { - for (PhiNode phi : ((LoopBeginNode) entry).phis()) { - allNodesExcludeLoopPhi.clear(phi); - } - } - } - return allNodesExcludeLoopPhi; - } - - public SuperBlock duplicate() { - return duplicate(false); - } - - public SuperBlock duplicate(boolean excludeLoop) { - NodeBitMap nodes = nodes(); - Map replacements = new HashMap<>(); - StructuredGraph graph = (StructuredGraph) entry.graph(); - if (excludeLoop || (entry instanceof MergeNode && !(entry instanceof LoopBeginNode))) { - replacements.put(entry, graph.add(new BeginNode())); // no merge/loop begin - } - List newEarlyExits = new ArrayList<>(earlyExits.size()); - for (BeginNode earlyExit : earlyExits) { - BeginNode newEarlyExit = graph.add(new BeginNode()); - newEarlyExits.add(newEarlyExit); - replacements.put(earlyExit, newEarlyExit); - } - if (exit instanceof LoopBeginNode && excludeLoop) { - assert entry == exit; - nodes = nodesExcludeLoopPhi(); - for (LoopEndNode end : ((LoopBeginNode) exit).loopEnds()) { - if (nodes.isMarked(end)) { - replacements.put(end, graph.add(new EndNode())); - } - } - } - Map duplicates = graph.addDuplicates(nodes, replacements); - BeginNode newExit; - if (excludeLoop || (exit instanceof MergeNode && !(exit instanceof LoopBeginNode))) { - newExit = mergeExits(replacements, duplicates); - } else if (exit != entry) { - newExit = graph.add(new BeginNode()); - replacements.put(exit, newExit); - } else { - newExit = (BeginNode) duplicates.get(exit); - } - - List newBlocks = new ArrayList<>(blocks.size()); - for (BeginNode block : blocks) { - BeginNode newBlock = (BeginNode) duplicates.get(block); - if (newBlock == null) { - newBlock = (BeginNode) replacements.get(block); - } - assert newBlock != null : block; - newBlocks.add(newBlock); - } - for (Entry e : replacements.entrySet()) { - duplicates.put(e.getKey(), e.getValue()); - } - SuperBlock superBlock = new SuperBlock((BeginNode) duplicates.get(entry), newExit, newBlocks, newEarlyExits); - superBlock.duplicationMapping = duplicates; - superBlock.original = this; - return superBlock; - } - - protected StructuredGraph graph() { - return (StructuredGraph) entry.graph(); - } - - private BeginNode mergeExits(Map replacements, Map duplicates) { - List endsToMerge = new LinkedList<>(); - MergeNode mergeExit = (MergeNode) exit; - if (mergeExit instanceof LoopBeginNode) { - LoopBeginNode loopBegin = (LoopBeginNode) mergeExit; - for (LoopEndNode le : loopBegin.loopEnds()) { - Node duplicate = replacements.get(le); - if (duplicate != null) { - endsToMerge.add((EndNode) duplicate); - } - } - } else { - for (EndNode end : mergeExit.forwardEnds()) { - Node duplicate = duplicates.get(end); - if (duplicate != null) { - endsToMerge.add((EndNode) duplicate); - } - } - } - return mergeEnds(mergeExit, endsToMerge); - } - - private BeginNode mergeEnds(MergeNode mergeExit, List endsToMerge) { - BeginNode newExit; - StructuredGraph graph = graph(); - if (endsToMerge.size() == 1) { - EndNode end = endsToMerge.get(0); - assert end.usages().count() == 0; - newExit = graph.add(new BeginNode()); - end.replaceAtPredecessors(newExit); - end.safeDelete(); - } else { - assert endsToMerge.size() > 1; - MergeNode newExitMerge = graph.add(new MergeNode()); - newExit = newExitMerge; - FrameState state = mergeExit.stateAfter(); - if (state != null) { - FrameState duplicateState = state.duplicate(); - // this state is wrong (incudes phis from the loop begin) needs to be fixed while resolving data - newExitMerge.setStateAfter(duplicateState); - } - for (EndNode end : endsToMerge) { - newExitMerge.addForwardEnd(end); - } - } - return newExit; - } - - public void finishDuplication() { - if (original != null) { - mergeEarlyExits((StructuredGraph) entry.graph(), original.earlyExits, duplicationMapping); - } - } - - private static void mergeEarlyExits(StructuredGraph graph, List earlyExits, Map duplicates) { - for (BeginNode earlyExit : earlyExits) { - BeginNode newEarlyExit = (BeginNode) duplicates.get(earlyExit); - assert newEarlyExit != null; - MergeNode merge = graph.add(new MergeNode()); - EndNode originalEnd = graph.add(new EndNode()); - EndNode newEnd = graph.add(new EndNode()); - merge.addForwardEnd(originalEnd); - merge.addForwardEnd(newEnd); - FixedNode next = earlyExit.next(); - earlyExit.setNext(originalEnd); - newEarlyExit.setNext(newEnd); - merge.setNext(next); - FrameState exitState = earlyExit.stateAfter(); - FrameState state = exitState.duplicate(); - merge.setStateAfter(state); - - for (Node anchored : earlyExit.anchored().snapshot()) { - anchored.replaceFirstInput(earlyExit, merge); - } - - for (ValueProxyNode vpn : earlyExit.proxies().snapshot()) { - ValueNode replaceWith; - ValueProxyNode newVpn = (ValueProxyNode) duplicates.get(vpn); - if (newVpn != null) { - PhiNode phi = graph.add(vpn.type() == PhiType.Value ? new PhiNode(vpn.kind(), merge) : new PhiNode(vpn.type(), merge)); - phi.addInput(vpn); - phi.addInput(newVpn); - if (vpn.type() == PhiType.Value) { - replaceWith = phi; - } else { - assert vpn.type() == PhiType.Virtual; - ValueNode vof = GraphUtil.unProxify(vpn); - ValueNode newVof = GraphUtil.unProxify(newVpn); - replaceWith = mergeVirtualChain(graph, vof, newVof, phi, earlyExit, newEarlyExit, merge); - } - } else { - replaceWith = vpn.value(); - } - state.replaceFirstInput(vpn, replaceWith); - for (Node usage : vpn.usages().snapshot()) { - if (usage != exitState && !merge.isPhiAtMerge(usage)) { - usage.replaceFirstInput(vpn, replaceWith); - } - } - } - } - } - - private static ValueProxyNode findProxy(ValueNode value, BeginNode proxyPoint) { - for (ValueProxyNode vpn : proxyPoint.proxies()) { - ValueNode v = vpn; - while (v instanceof ValueProxyNode) { - v = ((ValueProxyNode) v).value(); - if (v == value) { - return vpn; - } - } - } - return null; - } - - private static ValueNode mergeVirtualChain( - StructuredGraph graph, - ValueNode vof, - ValueNode newVof, - PhiNode vPhi, - BeginNode earlyExit, - BeginNode newEarlyExit, - MergeNode merge) { - VirtualObjectNode vObject = virtualObject(vof); - assert virtualObject(newVof) == vObject; - ValueNode[] virtualState = virtualState(vof); - ValueNode[] newVirtualState = virtualState(newVof); - ValueNode chain = vPhi; - for (int i = 0; i < virtualState.length; i++) { - ValueNode value = virtualState[i]; - ValueNode newValue = newVirtualState[i]; - assert value.kind() == newValue.kind(); - if (value != newValue) { - PhiNode valuePhi = graph.add(new PhiNode(value.kind(), merge)); - ValueProxyNode inputProxy = findProxy(value, earlyExit); - if (inputProxy != null) { - ValueProxyNode newInputProxy = findProxy(newValue, newEarlyExit); - assert newInputProxy != null : "no proxy for " + newValue + " at " + newEarlyExit; - valuePhi.addInput(inputProxy); - valuePhi.addInput(newInputProxy); - } else { - valuePhi.addInput(graph.unique(new ValueProxyNode(value, earlyExit, PhiType.Value))); - valuePhi.addInput(newValue); - } - chain = graph.add(new VirtualObjectFieldNode(vObject, chain, valuePhi, i)); - } - } - return chain; - } - - public static ValueNode mergeVirtualChain( - StructuredGraph graph, - PhiNode vPhi, - MergeNode merge) { - NodeInputList virtuals = vPhi.values(); - VirtualObjectNode vObject = virtualObject(GraphUtil.unProxify(virtuals.first())); - List virtualStates = new ArrayList<>(virtuals.size()); - for (ValueNode virtual : virtuals) { - virtualStates.add(virtualState(GraphUtil.unProxify(virtual))); - } - ValueNode chain = vPhi; - int stateLength = virtualStates.get(0).length; - for (int i = 0; i < stateLength; i++) { - ValueNode v = null; - boolean reconcile = false; - for (ValueNode[] state : virtualStates) { - if (v == null) { - v = state[i]; - } else if (v != state[i]) { - reconcile = true; - break; - } - assert v.kind() == state[i].kind(); - } - if (reconcile) { - PhiNode valuePhi = graph.add(new PhiNode(v.kind(), merge)); - for (ValueNode[] state : virtualStates) { - valuePhi.addInput(state[i]); - } - chain = graph.add(new VirtualObjectFieldNode(vObject, chain, valuePhi, i)); - } - } - return chain; - } - - private static VirtualObjectNode virtualObject(ValueNode vof) { - assert vof instanceof VirtualObjectFieldNode || (vof instanceof PhiNode && ((PhiNode) vof).type() == PhiType.Virtual) : vof; - ValueNode currentField = vof; - do { - if (currentField instanceof VirtualObjectFieldNode) { - return ((VirtualObjectFieldNode) currentField).object(); - } else { - assert currentField instanceof PhiNode && ((PhiNode) currentField).type() == PhiType.Virtual : currentField; - currentField = ((PhiNode) currentField).valueAt(0); - } - } while (currentField != null); - throw new GraalInternalError("Invalid virtual chain : cound not find virtual object from %s", vof); - } - - private static ValueNode[] virtualState(ValueNode vof) { - VirtualObjectNode vObj = virtualObject(vof); - int fieldsCount = vObj.fieldsCount(); - int dicovered = 0; - ValueNode[] state = new ValueNode[fieldsCount]; - ValueNode currentField = vof; - do { - if (currentField instanceof VirtualObjectFieldNode) { - int index = ((VirtualObjectFieldNode) currentField).index(); - if (state[index] == null) { - dicovered++; - state[index] = ((VirtualObjectFieldNode) currentField).input(); - if (dicovered >= fieldsCount) { - break; - } - } - currentField = ((VirtualObjectFieldNode) currentField).lastState(); - } else if (currentField instanceof ValueProxyNode) { - currentField = ((ValueProxyNode) currentField).value(); - } else { - assert currentField instanceof PhiNode && ((PhiNode) currentField).type() == PhiType.Virtual : currentField; - currentField = ((PhiNode) currentField).valueAt(0); - } - } while (currentField != null); - return state; - } - - private NodeBitMap computeNodes() { - NodeBitMap nodes = entry.graph().createNodeBitMap(); - for (BeginNode b : blocks) { - for (Node n : b.getBlockNodes()) { - if (n instanceof Invoke) { - nodes.mark(((Invoke) n).callTarget()); - } - if (n instanceof StateSplit) { - FrameState stateAfter = ((StateSplit) n).stateAfter(); - if (stateAfter != null) { - nodes.mark(stateAfter); - } - } - nodes.mark(n); - } - } - for (BeginNode earlyExit : earlyExits) { - FrameState stateAfter = earlyExit.stateAfter(); - assert stateAfter != null; - nodes.mark(stateAfter); - nodes.mark(earlyExit); - for (ValueProxyNode proxy : earlyExit.proxies()) { - nodes.mark(proxy); - } - } - - for (BeginNode b : blocks) { - for (Node n : b.getBlockNodes()) { - for (Node usage : n.usages()) { - markFloating(usage, nodes); - } - } - } - - return nodes; - } - - private static boolean markFloating(Node n, NodeBitMap loopNodes) { - if (loopNodes.isMarked(n)) { - return true; - } - if (n instanceof FixedNode) { - return false; - } - boolean mark = false; - if (n instanceof PhiNode) { - PhiNode phi = (PhiNode) n; - mark = loopNodes.isMarked(phi.merge()); - if (mark) { - loopNodes.mark(n); - } else { - return false; - } - } - for (Node usage : n.usages()) { - if (markFloating(usage, loopNodes)) { - mark = true; - } - } - if (mark) { - loopNodes.mark(n); - return true; - } - return false; - } - - public void insertBefore(FixedNode fixed) { - assert entry.predecessor() == null; - assert exit.next() == null; - fixed.replaceAtPredecessors(entry); - exit.setNext(fixed); - } -} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java Thu Jun 07 16:15:19 2012 +0200 @@ -90,7 +90,7 @@ FixedNode next = otherBegin.next(); otherBegin.setNext(null); guard.setNext(next); - ifNode.replaceAtPredecessors(guard); + ifNode.replaceAtPredecessor(guard); GraphUtil.killCFG(ifNode); } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Thu Jun 07 16:15:19 2012 +0200 @@ -22,12 +22,9 @@ */ package com.oracle.graal.compiler.phases; -import java.util.*; - import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.loop.*; import com.oracle.graal.debug.*; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; public class LoopTransformPhase extends Phase { @@ -35,21 +32,13 @@ @Override protected void run(StructuredGraph graph) { if (graph.hasLoops()) { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - Loop[] loops = cfg.getLoops(); - // outermost first - Arrays.sort(loops, new Comparator() { - @Override - public int compare(Loop o1, Loop o2) { - return o1.depth - o2.depth; - } - }); - for (Loop loop : loops) { + LoopsData data = new LoopsData(graph); + for (LoopEx loop : data.outterFirst()) { double entryProbability = loop.loopBegin().forwardEnd().probability(); if (entryProbability > GraalOptions.MinimumPeelProbability - && LoopTransformUtil.estimateSize(loop) + graph.getNodeCount() < GraalOptions.MaximumDesiredSize) { + && loop.size() + graph.getNodeCount() < GraalOptions.MaximumDesiredSize) { Debug.log("Peeling %s", loop); - LoopTransformUtil.peel(loop); + LoopTransformations.peel(loop); Debug.dump(graph, "After peeling %s", loop); } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Thu Jun 07 16:15:19 2012 +0200 @@ -267,7 +267,7 @@ } FixedNode next = checkCastNode.next(); checkCastNode.setNext(null); - checkCastNode.replaceAtPredecessors(next); + checkCastNode.replaceAtPredecessor(next); GraphUtil.killCFG(checkCastNode); } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Thu Jun 07 16:15:19 2012 +0200 @@ -806,7 +806,7 @@ if (receiverNullCheck) { receiverNullCheck(invoke); } - invoke.node().replaceAtPredecessors(firstCFGNodeDuplicate); + invoke.node().replaceAtPredecessor(firstCFGNodeDuplicate); FrameState stateAtExceptionEdge = null; if (invoke instanceof InvokeWithExceptionNode) { diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Jun 07 16:15:19 2012 +0200 @@ -313,6 +313,15 @@ public Iterator iterator() { return new NodeIterator(); } + + @SuppressWarnings("unchecked") + @Override + public NodeIterable filter(Class clazz) { + if (IterableNodeType.class.isAssignableFrom(clazz)) { + return getNodes((Class) clazz); + } + return super.filter(clazz); + } }; } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Jun 07 16:15:19 2012 +0200 @@ -124,7 +124,7 @@ private NodeUsagesList usages; private Node predecessor; private int modCount; - private NodeClass nodeClass; + private final NodeClass nodeClass; public Node() { this.graph = null; @@ -202,10 +202,10 @@ } /** - * Updates the predecessor sets of the given nodes after a successor slot is changed from oldSuccessor to newSuccessor: + * Updates the predecessor of the given nodes after a successor slot is changed from oldSuccessor to newSuccessor: * removes this node from oldSuccessor's predecessors and adds this node to newSuccessor's predecessors. */ - protected void updatePredecessors(Node oldSuccessor, Node newSuccessor) { + protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) { assert assertTrue(usages != null, "usages == null while adding %s to %s", newSuccessor, this); if (oldSuccessor != newSuccessor) { if (oldSuccessor != null) { @@ -228,7 +228,7 @@ updateUsages(null, input); } for (Node successor : successors()) { - updatePredecessors(null, successor); + updatePredecessor(null, successor); } } @@ -262,12 +262,12 @@ usages.clear(); } - public void replaceAtPredecessors(Node other) { + public void replaceAtPredecessor(Node other) { assert checkReplaceWith(other); if (predecessor != null) { boolean result = predecessor.getNodeClass().replaceFirstSuccessor(predecessor, this, other); assert assertTrue(result, "not found in successors, predecessor: %s", predecessor); - predecessor.updatePredecessors(this, other); + predecessor.updatePredecessor(this, other); } } @@ -276,14 +276,14 @@ if (other != null) { clearSuccessors(); replaceAtUsages(other); - replaceAtPredecessors(other); + replaceAtPredecessor(other); } safeDelete(); } public void replaceFirstSuccessor(Node oldSuccessor, Node newSuccessor) { if (getNodeClass().replaceFirstSuccessor(this, oldSuccessor, newSuccessor)) { - updatePredecessors(oldSuccessor, newSuccessor); + updatePredecessor(oldSuccessor, newSuccessor); } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Jun 07 16:15:19 2012 +0200 @@ -630,6 +630,9 @@ } public boolean isValid(Position pos, NodeClass from) { + if (this == from) { + return true; + } long[] offsets = pos.input ? inputOffsets : successorOffsets; if (pos.index >= offsets.length) { return false; @@ -663,7 +666,7 @@ if (pos.input) { node.updateUsages(old, x); } else { - node.updatePredecessors(old, x); + node.updatePredecessor(old, x); } } else { NodeList list = getNodeList(node, offset); @@ -921,7 +924,7 @@ assert !node.isDeleted() : "trying to duplicate deleted node"; Node replacement = replacements.replacement(node); if (replacement != node) { - replacementsMap.put(node, replacement); + newNodes.put(node, replacement); } else { Node newNode = node.clone(graph); assert newNode.getClass() == node.getClass(); @@ -935,33 +938,27 @@ Node node = entry.getValue(); for (NodeClassIterator iter = oldNode.inputs().iterator(); iter.hasNext();) { Position pos = iter.nextPosition(); + if (!pos.isValidFor(node, oldNode)) { + continue; + } Node input = oldNode.getNodeClass().get(oldNode, pos); - Node target = replacementsMap.get(input); + Node target = newNodes.get(input); if (target == null) { - Node replacement = replacements.replacement(input); - if (replacement != input) { - replacementsMap.put(input, replacement); - target = replacement; - } else { - target = newNodes.get(input); + target = replacementsMap.get(input); + if (target == null) { + Node replacement = replacements.replacement(input); + if (replacement != input) { + replacementsMap.put(input, replacement); + assert replacement == null || node.getNodeClass().inputTypes[pos.index] == null || node.getNodeClass().inputTypes[pos.index].isAssignableFrom(replacement.getClass()); + target = replacement; + } else { // patch to the outer world + target = input; + } } } node.getNodeClass().set(node, pos, target); } } - for (Entry entry : replacementsMap.entrySet()) { - Node oldNode = entry.getKey(); - Node node = entry.getValue(); - for (NodeClassIterator iter = oldNode.inputs().iterator(); iter.hasNext();) { - Position pos = iter.nextPosition(); - if (pos.isValidFor(node, oldNode)) { - Node input = oldNode.getNodeClass().get(oldNode, pos); - if (newNodes.containsKey(input)) { - node.getNodeClass().set(node, pos, newNodes.get(input)); - } - } - } - } // re-wire successors for (Entry entry : newNodes.entrySet()) { @@ -969,31 +966,25 @@ Node node = entry.getValue(); for (NodeClassIterator iter = oldNode.successors().iterator(); iter.hasNext();) { Position pos = iter.nextPosition(); + if (!pos.isValidFor(node, oldNode)) { + continue; + } Node succ = oldNode.getNodeClass().get(oldNode, pos); - Node target = replacementsMap.get(succ); - Node replacement = replacements.replacement(succ); - if (replacement != succ) { - replacementsMap.put(succ, replacement); - target = replacement; - } else { - target = newNodes.get(succ); + Node target = newNodes.get(succ); + if (target == null) { + target = replacementsMap.get(succ); + if (target == null) { + Node replacement = replacements.replacement(succ); + if (replacement != succ) { + replacementsMap.put(succ, replacement); + assert replacement == null || node.getNodeClass().successorTypes[pos.index] == null || node.getNodeClass().successorTypes[pos.index].isAssignableFrom(replacement.getClass()); + target = replacement; + } + } } node.getNodeClass().set(node, pos, target); } } - for (Entry entry : replacementsMap.entrySet()) { - Node oldNode = entry.getKey(); - Node node = entry.getValue(); - for (NodeClassIterator iter = oldNode.successors().iterator(); iter.hasNext();) { - Position pos = iter.nextPosition(); - if (pos.isValidFor(node, oldNode)) { - Node succ = oldNode.getNodeClass().get(oldNode, pos); - if (newNodes.containsKey(succ)) { - node.getNodeClass().set(node, pos, newNodes.get(succ)); - } - } - } - } return newNodes; } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java Thu Jun 07 16:15:19 2012 +0200 @@ -43,7 +43,7 @@ @Override protected void update(T oldNode, T newNode) { - self.updatePredecessors(oldNode, newNode); + self.updatePredecessor(oldNode, newNode); } @Override diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Thu Jun 07 16:15:19 2012 +0200 @@ -34,10 +34,10 @@ return new FilteredNodeIterable<>(this).until(clazz); } @SuppressWarnings("unchecked") - public FilteredNodeIterable filter(Class clazz) { - return (FilteredNodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); + public NodeIterable filter(Class clazz) { + return (NodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); } - public FilteredNodeIterable filterInterface(Class iface) { + public NodeIterable filterInterface(Class iface) { return new FilteredNodeIterable<>(this).and(NodePredicates.isAInterface(iface)); } public FilteredNodeIterable filter(NodePredicate predicate) { diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java Thu Jun 07 16:15:19 2012 +0200 @@ -23,8 +23,8 @@ package com.oracle.graal.hotspot.snippets; import static com.oracle.graal.hotspot.snippets.ArrayCopySnippets.*; import static com.oracle.graal.hotspot.snippets.CheckCastSnippets.Counter.*; -import static com.oracle.graal.snippets.Snippet.Arguments.*; import static com.oracle.graal.snippets.Snippet.Multiple.*; +import static com.oracle.graal.snippets.SnippetTemplate.Arguments.*; import java.io.*; import java.util.*; @@ -43,10 +43,11 @@ import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.snippets.*; -import com.oracle.graal.snippets.Snippet.Arguments; import com.oracle.graal.snippets.Snippet.Constant; import com.oracle.graal.snippets.Snippet.Parameter; +import com.oracle.graal.snippets.SnippetTemplate.Arguments; import com.oracle.graal.snippets.SnippetTemplate.Cache; +import com.oracle.graal.snippets.SnippetTemplate.Key; import com.oracle.graal.snippets.nodes.*; import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; @@ -67,12 +68,15 @@ @Snippet public static Object checkcastExact(@Parameter("object") Object object, @Parameter("exactHub") Object exactHub, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { + isNull.inc(); return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); if (objectHub != exactHub) { + exactMiss.inc(); DeoptimizeNode.deopt(RiDeoptAction.InvalidateReprofile, RiDeoptReason.ClassCastException); } + exactHit.inc(); return object; } @@ -86,12 +90,15 @@ @Snippet public static Object checkcastPrimary(@Parameter("hub") Object hub, @Parameter("object") Object object, @Constant("checkNull") boolean checkNull, @Constant("superCheckOffset") int superCheckOffset) { if (checkNull && object == null) { + isNull.inc(); return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); if (UnsafeLoadNode.loadObject(objectHub, 0, superCheckOffset, true) != hub) { + displayMiss.inc(); DeoptimizeNode.deopt(RiDeoptAction.InvalidateReprofile, RiDeoptReason.ClassCastException); } + displayHit.inc(); return object; } @@ -101,6 +108,7 @@ @Snippet public static Object checkcastSecondary(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { + isNull.inc(); return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); @@ -109,6 +117,7 @@ for (int i = 0; i < hints.length; i++) { Object hintHub = hints[i]; if (hintHub == objectHub) { + hintsHit.inc(); return object; } } @@ -125,6 +134,7 @@ @Snippet public static Object checkcastUnknown(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { + isNull.inc(); return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); @@ -133,6 +143,7 @@ for (int i = 0; i < hints.length; i++) { Object hintHub = hints[i]; if (hintHub == objectHub) { + hintsHit.inc(); return object; } } @@ -150,11 +161,13 @@ static boolean checkSecondarySubType(Object t, Object s) { // if (S.cache == T) return true if (UnsafeLoadNode.loadObject(s, 0, secondarySuperCacheOffset(), true) == t) { + cacheHit.inc(); return true; } // if (T == S) return true if (s == t) { + T_equals_S.inc(); return true; } @@ -164,29 +177,38 @@ for (int i = 0; i < secondarySupers.length; i++) { if (t == loadNonNullObjectElement(secondarySupers, i)) { DirectObjectStoreNode.store(s, secondarySuperCacheOffset(), 0, t); + secondariesHit.inc(); return true; } } - + secondariesMiss.inc(); return false; } static boolean checkUnknownSubType(Object t, Object s) { // int off = T.offset int superCheckOffset = UnsafeLoadNode.load(t, 0, superCheckOffsetOffset(), CiKind.Int); + boolean primary = superCheckOffset != secondarySuperCacheOffset(); // if (T = S[off]) return true if (UnsafeLoadNode.loadObject(s, 0, superCheckOffset, true) == t) { + if (primary) { + cacheHit.inc(); + } else { + displayHit.inc(); + } return true; } // if (off != &cache) return false - if (superCheckOffset != secondarySuperCacheOffset()) { + if (primary) { + displayMiss.inc(); return false; } // if (T == S) return true if (s == t) { + T_equals_S.inc(); return true; } @@ -195,23 +217,29 @@ for (int i = 0; i < secondarySupers.length; i++) { if (t == loadNonNullObjectElement(secondarySupers, i)) { DirectObjectStoreNode.store(s, secondarySuperCacheOffset(), 0, t); + secondariesHit.inc(); return true; } } + secondariesMiss.inc(); return false; } /** - * Counters for the various code paths through a type check. + * Counters for the various code paths through a checkcast. */ public enum Counter { hintsHit("hit a hint type"), - hintsMissed("missed the hint types"), - exactType("tested type is (statically) final"), - noHints("profile information is not used"), - isNull("object tested is null"), - exception("type test failed with a ClassCastException"); + exactHit("exact type test succeeded"), + exactMiss("exact type test failed"), + isNull("object tested was null"), + cacheHit("secondary type cache hit"), + secondariesHit("secondaries scan succeeded"), + secondariesMiss("secondaries scan failed"), + displayHit("primary type test succeeded"), + displayMiss("primary type test failed"), + T_equals_S("object type was equal to secondary type"); final String description; final int index; @@ -246,51 +274,6 @@ static final boolean ENABLED = GraalOptions.CheckcastCounters; } - /** - * Type test used when {@link GraalOptions#CheckcastCounters} is enabled. - */ - @Snippet - public static Object checkcastCounters(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("hintsAreExact") boolean hintsAreExact) { - if (object == null) { - isNull.inc(); - return object; - } - Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); - if (hints.length == 0) { - noHints.inc(); - if (!checkUnknownSubType(hub, objectHub)) { - exception.inc(); - DeoptimizeNode.deopt(RiDeoptAction.InvalidateReprofile, RiDeoptReason.ClassCastException); - } - } else { - // if we get an exact match: succeed immediately - ExplodeLoopNode.explodeLoop(); - for (int i = 0; i < hints.length; i++) { - Object hintHub = hints[i]; - if (hintHub == objectHub) { - if (hintsAreExact) { - exactType.inc(); - } else { - hintsHit.inc(); - } - return object; - } - } - if (!hintsAreExact) { - if (!checkUnknownSubType(hub, objectHub)) { - exception.inc(); - DeoptimizeNode.deopt(RiDeoptAction.InvalidateReprofile, RiDeoptReason.ClassCastException); - } else { - hintsMissed.inc(); - } - } else { - exception.inc(); - DeoptimizeNode.deopt(RiDeoptAction.InvalidateReprofile, RiDeoptReason.ClassCastException); - } - } - return object; - } - @Fold private static int superCheckOffsetOffset() { return CompilerImpl.getInstance().getConfig().superCheckOffsetOffset; @@ -353,7 +336,6 @@ private final RiResolvedMethod primary; private final RiResolvedMethod secondary; private final RiResolvedMethod unknown; - private final RiResolvedMethod counters; private final RiRuntime runtime; public Templates(RiRuntime runtime) { @@ -364,7 +346,6 @@ primary = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastPrimary", Object.class, Object.class, boolean.class, int.class)); secondary = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastSecondary", Object.class, Object.class, Object[].class, boolean.class)); unknown = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastUnknown", Object.class, Object.class, Object[].class, boolean.class)); - counters = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastCounters", Object.class, Object.class, Object[].class, boolean.class)); } catch (NoSuchMethodException e) { throw new GraalInternalError(e); } @@ -381,27 +362,23 @@ final HotSpotTypeResolvedImpl target = (HotSpotTypeResolvedImpl) checkcast.targetClass(); boolean checkNull = !object.stamp().nonNull(); Arguments arguments; - SnippetTemplate.Key key; + Key key; - if (GraalOptions.CheckcastCounters) { + if (target == null) { HotSpotKlassOop[] hints = createHints(hintInfo); - key = new SnippetTemplate.Key(counters).add("hints", multiple(Object.class, hints.length)).add("hintsAreExact", hintInfo.exact); - arguments = arguments("hub", hub).add("object", object).add("hints", hints); - } else if (target == null) { - HotSpotKlassOop[] hints = createHints(hintInfo); - key = new SnippetTemplate.Key(unknown).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); + key = new Key(unknown).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); arguments = arguments("hub", hub).add("object", object).add("hints", hints); } else if (hintInfo.exact) { HotSpotKlassOop[] hints = createHints(hintInfo); assert hints.length == 1; - key = new SnippetTemplate.Key(exact).add("checkNull", checkNull); + key = new Key(exact).add("checkNull", checkNull); arguments = arguments("object", object).add("exactHub", hints[0]); } else if (target.isPrimaryType()) { - key = new SnippetTemplate.Key(primary).add("checkNull", checkNull).add("superCheckOffset", target.superCheckOffset()); + key = new Key(primary).add("checkNull", checkNull).add("superCheckOffset", target.superCheckOffset()); arguments = arguments("hub", hub).add("object", object); } else { HotSpotKlassOop[] hints = createHints(hintInfo); - key = new SnippetTemplate.Key(secondary).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); + key = new Key(secondary).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); arguments = arguments("hub", hub).add("object", object).add("hints", hints); } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Thu Jun 07 16:15:19 2012 +0200 @@ -147,7 +147,7 @@ if (node instanceof FixedWithNextNode) { ((StructuredGraph) graph()).replaceFixedWithFixed(this, (FixedWithNextNode) node); } else if (node instanceof DeoptimizeNode) { - this.replaceAtPredecessors(node); + this.replaceAtPredecessor(node); this.replaceAtUsages(null); GraphUtil.killCFG(this); return; diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Thu Jun 07 16:15:19 2012 +0200 @@ -185,7 +185,7 @@ assert kind() == CiKind.Void && usages().isEmpty(); ((StructuredGraph) graph()).removeSplit(this, NORMAL_EDGE); } else if (node instanceof DeoptimizeNode) { - this.replaceAtPredecessors(node); + this.replaceAtPredecessor(node); this.replaceAtUsages(null); GraphUtil.killCFG(this); return; diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Thu Jun 07 16:15:19 2012 +0200 @@ -177,7 +177,7 @@ phi.addInput(newInput); } this.removeEnd(end); - end.replaceAtPredecessors(newEnd); + end.replaceAtPredecessor(newEnd); end.safeDelete(); tool.addToWorkList(newEnd.predecessor()); // ? } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ScheduledNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ScheduledNode.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ScheduledNode.java Thu Jun 07 16:15:19 2012 +0200 @@ -35,7 +35,7 @@ } public void setScheduledNext(ScheduledNode x) { - updatePredecessors(scheduledNext, x); + updatePredecessor(scheduledNext, x); scheduledNext = x; } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Thu Jun 07 16:15:19 2012 +0200 @@ -201,7 +201,7 @@ assert node.usages().isEmpty() : node + " " + node.usages(); FixedNode next = node.next(); node.setNext(null); - node.replaceAtPredecessors(next); + node.replaceAtPredecessor(next); node.safeDelete(); } @@ -228,7 +228,7 @@ assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement; FixedNode next = node.next(); node.setNext(null); - node.replaceAtPredecessors(next); + node.replaceAtPredecessor(next); node.replaceAtUsages(replacement); node.safeDelete(); } @@ -241,7 +241,7 @@ for (int i = 0; i < node.blockSuccessorCount(); i++) { node.setBlockSuccessor(i, null); } - node.replaceAtPredecessors(begin); + node.replaceAtPredecessor(begin); node.safeDelete(); } @@ -258,7 +258,7 @@ } } if (begin.isAlive()) { - node.replaceAtPredecessors(begin); + node.replaceAtPredecessor(begin); node.safeDelete(); } else { assert node.isDeleted(); @@ -293,7 +293,7 @@ for (int i = 0; i < node.blockSuccessorCount(); i++) { node.setBlockSuccessor(i, null); } - node.replaceAtPredecessors(begin); + node.replaceAtPredecessor(begin); node.replaceAtUsages(replacement); node.safeDelete(); } @@ -353,7 +353,7 @@ stateAfter.safeDelete(); } if (sux == null) { - singleEnd.replaceAtPredecessors(null); + singleEnd.replaceAtPredecessor(null); singleEnd.safeDelete(); } else { singleEnd.replaceAndDelete(sux); diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Thu Jun 07 16:15:19 2012 +0200 @@ -30,6 +30,7 @@ import com.oracle.graal.graph.iterators.*; import com.oracle.graal.graph.iterators.NodePredicates.PositiveTypePredicate; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.virtual.*; @@ -95,7 +96,7 @@ // null out remaining usages node.replaceAtUsages(null); - node.replaceAtPredecessors(null); + node.replaceAtPredecessor(null); killWithUnusedFloatingInputs(node); for (Node usage : usagesSnapshot) { @@ -186,4 +187,144 @@ } return v; } + + private static ValueProxyNode findProxy(ValueNode value, BeginNode proxyPoint) { + for (ValueProxyNode vpn : proxyPoint.proxies()) { + ValueNode v = vpn; + while (v instanceof ValueProxyNode) { + v = ((ValueProxyNode) v).value(); + if (v == value) { + return vpn; + } + } + } + return null; + } + + public static ValueNode mergeVirtualChain( + StructuredGraph graph, + ValueNode vof, + ValueNode newVof, + PhiNode vPhi, + BeginNode earlyExit, + BeginNode newEarlyExit, + MergeNode merge) { + VirtualObjectNode vObject = virtualObject(vof); + assert virtualObject(newVof) == vObject; + ValueNode[] virtualState = virtualState(vof); + ValueNode[] newVirtualState = virtualState(newVof); + ValueNode chain = vPhi; + for (int i = 0; i < virtualState.length; i++) { + ValueNode value = virtualState[i]; + ValueNode newValue = newVirtualState[i]; + assert value.kind() == newValue.kind(); + if (value != newValue) { + PhiNode valuePhi = graph.add(new PhiNode(value.kind(), merge)); + ValueProxyNode inputProxy = findProxy(value, earlyExit); + if (inputProxy != null) { + ValueProxyNode newInputProxy = findProxy(newValue, newEarlyExit); + assert newInputProxy != null : "no proxy for " + newValue + " at " + newEarlyExit; + valuePhi.addInput(inputProxy); + valuePhi.addInput(newInputProxy); + } else { + valuePhi.addInput(graph.unique(new ValueProxyNode(value, earlyExit, PhiType.Value))); + valuePhi.addInput(newValue); + } + chain = graph.add(new VirtualObjectFieldNode(vObject, chain, valuePhi, i)); + } + } + return chain; + } + + public static ValueNode mergeVirtualChain( + StructuredGraph graph, + PhiNode vPhi, + MergeNode merge) { + NodeInputList virtuals = vPhi.values(); + VirtualObjectNode vObject = virtualObject(unProxify(virtuals.first())); + List virtualStates = new ArrayList<>(virtuals.size()); + for (ValueNode virtual : virtuals) { + virtualStates.add(virtualState(unProxify(virtual))); + } + ValueNode chain = vPhi; + int stateLength = virtualStates.get(0).length; + for (int i = 0; i < stateLength; i++) { + ValueNode v = null; + boolean reconcile = false; + for (ValueNode[] state : virtualStates) { + if (v == null) { + v = state[i]; + } else if (v != state[i]) { + reconcile = true; + break; + } + assert v.kind() == state[i].kind(); + } + if (reconcile) { + PhiNode valuePhi = graph.add(new PhiNode(v.kind(), merge)); + for (ValueNode[] state : virtualStates) { + valuePhi.addInput(state[i]); + } + chain = graph.add(new VirtualObjectFieldNode(vObject, chain, valuePhi, i)); + } + } + return chain; + } + + /** + * Returns the VirtualObjectNode associated with the virtual chain of the provided virtual node. + * @param vof a virtual ValueNode (a VirtualObjectFieldNode or a Virtual Phi) + * @return the VirtualObjectNode associated with the virtual chain of the provided virtual node. + */ + public static VirtualObjectNode virtualObject(ValueNode vof) { + assert vof instanceof VirtualObjectFieldNode || (vof instanceof PhiNode && ((PhiNode) vof).type() == PhiType.Virtual) : vof; + ValueNode currentField = vof; + do { + if (currentField instanceof VirtualObjectFieldNode) { + return ((VirtualObjectFieldNode) currentField).object(); + } else { + assert currentField instanceof PhiNode && ((PhiNode) currentField).type() == PhiType.Virtual : currentField; + currentField = ((PhiNode) currentField).valueAt(0); + } + } while (currentField != null); + throw new GraalInternalError("Invalid virtual chain : cound not find virtual object from %s", vof); + } + + /** + * Builds the state of the virtual object at the provided point into a virtual chain. + * @param vof a virtual ValueNode (a VirtualObjectFieldNode or a Virtual Phi) + * @return the state of the virtual object at the provided point into a virtual chain. + */ + public static ValueNode[] virtualState(ValueNode vof) { + return virtualState(vof, virtualObject(vof)); + } + + /** + * Builds the state of the virtual object at the provided point into a virtual chain. + * @param vof a virtual ValueNode (a VirtualObjectFieldNode or a Virtual Phi) + * @param vObj the virtual object + * @return the state of the virtual object at the provided point into a virtual chain. + */ + public static ValueNode[] virtualState(ValueNode vof, VirtualObjectNode vObj) { + int fieldsCount = vObj.fieldsCount(); + int dicovered = 0; + ValueNode[] state = new ValueNode[fieldsCount]; + ValueNode currentField = vof; + do { + if (currentField instanceof VirtualObjectFieldNode) { + int index = ((VirtualObjectFieldNode) currentField).index(); + if (state[index] == null) { + dicovered++; + state[index] = ((VirtualObjectFieldNode) currentField).input(); + } + currentField = ((VirtualObjectFieldNode) currentField).lastState(); + } else if (currentField instanceof ValueProxyNode) { + currentField = ((ValueProxyNode) currentField).value(); + } else { + assert currentField instanceof PhiNode && ((PhiNode) currentField).type() == PhiType.Virtual : currentField; + currentField = ((PhiNode) currentField).valueAt(0); + } + } while (currentField != null && dicovered < fieldsCount); + return state; + } } diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java Thu Jun 07 16:15:19 2012 +0200 @@ -24,8 +24,6 @@ import java.lang.annotation.*; import java.lang.reflect.*; -import java.util.*; -import java.util.Map.Entry; import com.oracle.graal.graph.Node.NodeIntrinsic; import com.oracle.graal.snippets.nodes.*; @@ -80,37 +78,6 @@ } /** - * Arguments used to instantiate a template. - */ - public static class Arguments implements Iterable> { - private final HashMap map = new HashMap<>(); - - public static Arguments arguments(String name, Object value) { - return new Arguments().add(name, value); - } - - public Arguments add(String name, Object value) { - assert !map.containsKey(name); - map.put(name, value); - return this; - } - - public int length() { - return map.size(); - } - - @Override - public Iterator> iterator() { - return map.entrySet().iterator(); - } - - @Override - public String toString() { - return map.toString(); - } - } - - /** * Wrapper for the prototype value of a {@linkplain Parameter#multiple() multiple} parameter. */ public static class Multiple { diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 17:20:15 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Thu Jun 07 16:15:19 2012 +0200 @@ -35,8 +35,8 @@ import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.util.*; -import com.oracle.graal.snippets.Snippet.Arguments; import com.oracle.graal.snippets.Snippet.Constant; import com.oracle.graal.snippets.Snippet.Multiple; import com.oracle.graal.snippets.Snippet.Parameter; @@ -110,6 +110,37 @@ } /** + * Arguments used to instantiate a template. + */ + public static class Arguments implements Iterable> { + private final HashMap map = new HashMap<>(); + + public static Arguments arguments(String name, Object value) { + return new Arguments().add(name, value); + } + + public Arguments add(String name, Object value) { + assert !map.containsKey(name); + map.put(name, value); + return this; + } + + public int length() { + return map.size(); + } + + @Override + public Iterator> iterator() { + return map.entrySet().iterator(); + } + + @Override + public String toString() { + return map.toString(); + } + } + + /** * A collection of snippet templates accessed by a {@link Key} instance. */ public static class Cache { @@ -158,6 +189,7 @@ int parameterCount = signature.argumentCount(false); Parameter[] parameterAnnotations = new Parameter[parameterCount]; + ConstantNode[] placeholders = new ConstantNode[parameterCount]; for (int i = 0; i < parameterCount; i++) { Constant c = CiUtil.getParameterAnnotation(Constant.class, i, method); if (c != null) { @@ -176,7 +208,9 @@ assert multiple != null : method + ": requires a Multiple named " + name; assert checkMultipleArgument(method, signature, i, name, multiple); Object array = ((Multiple) multiple).array; - replacements.put(snippetGraph.getLocal(i), ConstantNode.forObject(array, runtime, snippetCopy)); + ConstantNode placeholder = ConstantNode.forObject(array, runtime, snippetCopy); + replacements.put(snippetGraph.getLocal(i), placeholder); + placeholders[i] = placeholder; } parameterAnnotations[i] = p; } @@ -193,28 +227,36 @@ for (int i = 0; i < parameterCount; i++) { Parameter p = parameterAnnotations[i]; if (p != null) { - ValueNode parameter; if (p.multiple()) { - parameter = null; assert snippetCopy.getLocal(i) == null; - ConstantNode array = (ConstantNode) replacements.get(snippetGraph.getLocal(i)); - for (LoadIndexedNode loadIndexed : snippetCopy.getNodes(LoadIndexedNode.class)) { - if (loadIndexed.array() == array) { + Object array = ((Multiple) key.get(p.value())).array; + int length = Array.getLength(array); + LocalNode[] locals = new LocalNode[length]; + Stamp stamp = StampFactory.forKind(runtime.getType(array.getClass().getComponentType()).kind(false)); + for (int j = 0; j < length; j++) { + assert (parameterCount & 0xFFFF) == parameterCount; + int idx = i << 16 | j; + LocalNode local = snippetCopy.unique(new LocalNode(idx, stamp)); + locals[j] = local; + } + parameters.put(p.value(), locals); + + ConstantNode placeholder = placeholders[i]; + assert placeholder != null; + for (Node usage : placeholder.usages().snapshot()) { + if (usage instanceof LoadIndexedNode) { + LoadIndexedNode loadIndexed = (LoadIndexedNode) usage; Debug.dump(snippetCopy, "Before replacing %s", loadIndexed); - LoadMultipleParameterNode lmp = new LoadMultipleParameterNode(array, i, loadIndexed.index(), loadIndexed.stamp()); - StructuredGraph g = (StructuredGraph) loadIndexed.graph(); - g.add(lmp); - g.replaceFixedWithFixed(loadIndexed, lmp); - parameter = lmp; + LoadSnippetParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetParameterNode(locals, loadIndexed.index(), loadIndexed.stamp())); + snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter); Debug.dump(snippetCopy, "After replacing %s", loadIndexed); - break; } } } else { - parameter = snippetCopy.getLocal(i); + LocalNode local = snippetCopy.getLocal(i); + assert local != null; + parameters.put(p.value(), local); } - assert parameter != null; - parameters.put(p.value(), parameter); } } @@ -222,40 +264,21 @@ boolean exploded = false; do { exploded = false; - for (Node node : snippetCopy.getNodes()) { - if (node instanceof ExplodeLoopNode) { - final ExplodeLoopNode explodeLoop = (ExplodeLoopNode) node; - LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); - if (loopBegin != null) { - ControlFlowGraph cfg = ControlFlowGraph.compute(snippetCopy, true, true, false, false); - for (Loop loop : cfg.getLoops()) { - if (loop.loopBegin() == loopBegin) { - SuperBlock wholeLoop = LoopTransformUtil.wholeLoop(loop); - Debug.dump(snippetCopy, "Before exploding loop %s", loopBegin); - int peel = 0; - while (!loopBegin.isDeleted()) { - int mark = snippetCopy.getMark(); - LoopTransformUtil.peel(loop, wholeLoop); - Debug.dump(snippetCopy, "After peel %d", peel); - new CanonicalizerPhase(null, runtime, null, mark, null).apply(snippetCopy); - peel++; - } - Debug.dump(snippetCopy, "After exploding loop %s", loopBegin); - exploded = true; - break; - } - } - } else { - // Earlier canonicalization removed the loop altogether - } - - FixedNode explodeLoopNext = explodeLoop.next(); - explodeLoop.clearSuccessors(); - explodeLoop.replaceAtPredecessors(explodeLoopNext); - explodeLoop.replaceAtUsages(null); - GraphUtil.killCFG(explodeLoop); - break; + ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first(); + if (explodeLoop != null) { // Earlier canonicalization may have removed the loop altogether + LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); + if (loopBegin != null) { + LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin); + int mark = snippetCopy.getMark(); + LoopTransformations.fullUnroll(loop); + new CanonicalizerPhase(null, runtime, null, mark, null).apply(snippetCopy); } + FixedNode explodeLoopNext = explodeLoop.next(); + explodeLoop.clearSuccessors(); + explodeLoop.replaceAtPredecessor(explodeLoopNext); + explodeLoop.replaceAtUsages(null); + GraphUtil.killCFG(explodeLoop); + exploded = true; } } while (exploded); @@ -274,6 +297,8 @@ new DeadCodeEliminationPhase().apply(snippetCopy); + assert checkAllMultipleParameterPlaceholdersAreDeleted(parameterCount, placeholders); + this.graph = snippetCopy; nodes = new ArrayList<>(graph.getNodeCount()); ReturnNode retNode = null; @@ -291,6 +316,15 @@ this.returnNode = retNode; } + private static boolean checkAllMultipleParameterPlaceholdersAreDeleted(int parameterCount, ConstantNode[] placeholders) { + for (int i = 0; i < parameterCount; i++) { + if (placeholders[i] != null) { + assert placeholders[i].isDeleted() : placeholders[i]; + } + } + return true; + } + private static boolean checkConstantArgument(final RiResolvedMethod method, RiSignature signature, int i, String name, Object arg, CiKind kind) { if (kind.isObject()) { Class type = signature.argumentTypeAt(i, method.holder()).resolve(method.holder()).toJava(); @@ -320,9 +354,9 @@ /** * The named parameters of this template that must be bound to values during instantiation. - * Each parameter is either a {@link LocalNode} or a {@link LoadMultipleParameterNode} instance. + * Each value in this map is either a {@link LocalNode} instance or a {@link LocalNode} array. */ - private final Map parameters; + private final Map parameters; /** * The return node (if any) of the snippet. @@ -339,33 +373,33 @@ * * @return the map that will be used to bind arguments to parameters when inlining this template */ - private IdentityHashMap bind(StructuredGraph replaceeGraph, RiRuntime runtime, Snippet.Arguments args) { + private IdentityHashMap bind(StructuredGraph replaceeGraph, RiRuntime runtime, SnippetTemplate.Arguments args) { IdentityHashMap replacements = new IdentityHashMap<>(); for (Map.Entry e : args) { String name = e.getKey(); - ValueNode parameter = parameters.get(name); + Object parameter = parameters.get(name); assert parameter != null : this + " has no parameter named " + name; Object argument = e.getValue(); if (parameter instanceof LocalNode) { if (argument instanceof ValueNode) { - replacements.put(parameter, (ValueNode) argument); + replacements.put((LocalNode) parameter, (ValueNode) argument); } else { CiKind kind = ((LocalNode) parameter).kind(); CiConstant constant = CiConstant.forBoxed(kind, argument); - replacements.put(parameter, ConstantNode.forCiConstant(constant, runtime, replaceeGraph)); + replacements.put((LocalNode) parameter, ConstantNode.forCiConstant(constant, runtime, replaceeGraph)); } } else { - assert parameter instanceof LoadMultipleParameterNode; + assert parameter instanceof LocalNode[]; + LocalNode[] locals = (LocalNode[]) parameter; Object array = argument; assert array != null && array.getClass().isArray(); - int length = Array.getLength(array); - LoadMultipleParameterNode lmp = (LoadMultipleParameterNode) parameter; - assert length == lmp.getLocalCount() : length + " != " + lmp.getLocalCount(); + int length = locals.length; + assert Array.getLength(array) == length : length + " != " + Array.getLength(array); for (int j = 0; j < length; j++) { - LocalNode local = lmp.getLocal(j); + LocalNode local = locals[j]; assert local != null; - CiConstant constant = CiConstant.forBoxed(lmp.kind(), Array.get(array, j)); + CiConstant constant = CiConstant.forBoxed(local.kind(), Array.get(array, j)); ConstantNode element = ConstantNode.forCiConstant(constant, runtime, replaceeGraph); replacements.put(local, element); } @@ -384,7 +418,7 @@ */ public void instantiate(RiRuntime runtime, Node replacee, - FixedWithNextNode anchor, Arguments args) { + FixedWithNextNode anchor, SnippetTemplate.Arguments args) { // Inline the snippet nodes, replacing parameters with the given args in the process String name = graph.name == null ? "{copy}" : graph.name + "{copy}"; @@ -398,7 +432,7 @@ // Re-wire the control flow graph around the replacee FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode); - anchor.replaceAtPredecessors(firstCFGNodeDuplicate); + anchor.replaceAtPredecessor(firstCFGNodeDuplicate); FixedNode next = anchor.next(); anchor.setNext(null); @@ -434,16 +468,18 @@ public String toString() { StringBuilder buf = new StringBuilder(graph.toString()).append('('); String sep = ""; - for (Map.Entry e : parameters.entrySet()) { + for (Map.Entry e : parameters.entrySet()) { String name = e.getKey(); - ValueNode value = e.getValue(); + Object value = e.getValue(); buf.append(sep); sep = ", "; if (value instanceof LocalNode) { - buf.append(value.kind().name()).append(' ').append(name); + LocalNode local = (LocalNode) value; + buf.append(local.kind().name()).append(' ').append(name); } else { - LoadMultipleParameterNode lmp = (LoadMultipleParameterNode) value; - buf.append(value.kind().name()).append('[').append(lmp.getLocalCount()).append("] ").append(name); + LocalNode[] locals = (LocalNode[]) value; + String kind = locals.length == 0 ? "?" : locals[0].kind().name(); + buf.append(kind).append('[').append(locals.length).append("] ").append(name); } } return buf.append(')').toString(); diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/nodes/LoadMultipleParameterNode.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/nodes/LoadMultipleParameterNode.java Wed Jun 06 17:20:15 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,71 +0,0 @@ -/* - * Copyright (c) 2009, 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.snippets.nodes; - -import java.lang.reflect.*; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.type.*; -import com.oracle.graal.snippets.Snippet.Parameter; - -/** - * Implements the semantics of a snippet {@link Parameter} whose {@link Parameter#multiple()} element is {@code true}. - */ -public final class LoadMultipleParameterNode extends FixedWithNextNode implements Canonicalizable { - - @Input private ValueNode index; - - private final LocalNode[] locals; - - public ValueNode index() { - return index; - } - - public LoadMultipleParameterNode(ConstantNode array, int localIndex, ValueNode index, Stamp stamp) { - super(stamp); - int length = Array.getLength(array.asConstant().asObject()); - this.index = index; - locals = new LocalNode[length]; - for (int i = 0; i < length; i++) { - int idx = localIndex << 16 | i; - LocalNode local = array.graph().unique(new LocalNode(idx, stamp())); - locals[i] = local; - } - } - - public LocalNode getLocal(int idx) { - assert idx < locals.length; - return locals[idx]; - } - - public int getLocalCount() { - return locals.length; - } - - @Override - public ValueNode canonical(CanonicalizerTool tool) { - assert index.isConstant(); - return getLocal(index().asConstant().asInt()); - } -} diff -r 80abea6e5e27 -r a4dfee0b8fbd graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/nodes/LoadSnippetParameterNode.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/nodes/LoadSnippetParameterNode.java Thu Jun 07 16:15:19 2012 +0200 @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2009, 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.snippets.nodes; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; +import com.oracle.graal.snippets.Snippet.Parameter; + +/** + * Implements the semantics of a snippet {@link Parameter} whose {@link Parameter#multiple()} element is {@code true}. + */ +public final class LoadSnippetParameterNode extends FixedWithNextNode implements Canonicalizable { + + @Input private ValueNode index; + + private final LocalNode[] locals; + + public LoadSnippetParameterNode(LocalNode[] locals, ValueNode index, Stamp stamp) { + super(stamp); + this.index = index; + this.locals = locals; + } + + @Override + public ValueNode canonical(CanonicalizerTool tool) { + if (index.isConstant()) { + return locals[index.asConstant().asInt()]; + } + return this; + } +} diff -r 80abea6e5e27 -r a4dfee0b8fbd mx/commands.py --- a/mx/commands.py Wed Jun 06 17:20:15 2012 +0200 +++ b/mx/commands.py Thu Jun 07 16:15:19 2012 +0200 @@ -565,9 +565,7 @@ # Exclude all compiler tests and snippets excludes = ['com.oracle.graal.compiler.tests.*'] for p in mx.projects(): - for s in p.source_dirs(): - _add_classes_with_annotation(excludes, s, None, '@Snippet') - _add_classes_with_annotation(excludes, s, None, '@ClassSubstitution') + _find_classes_with_annotations(excludes, p, None, ['@Snippet', '@ClassSubstitution'], includeInnerClasses=True) agentOptions = { 'append' : 'true' if _jacoco == 'append' else 'false', 'bootclasspath' : 'true', @@ -578,32 +576,47 @@ exe = join(_jdk(build), 'bin', mx.exe_suffix('java')) return mx.run([exe, '-' + vm] + args, nonZeroIsFatal=nonZeroIsFatal, out=out, err=err, cwd=cwd, timeout=timeout) -def _add_classes_with_annotation(classes, srcDir, pkgRoot, annotation): +def _find_classes_with_annotations(classes, p, pkgRoot, annotations, includeInnerClasses=False): """ - Scan 'srcDir' for Java source files containing a line starting with 'annotation' + Scan the sources of project 'p' for Java source files containing a line starting with 'annotation' (ignoring preceding whitespace) and add the fully qualified class name to 'classes' for each Java source file matched. """ + for a in annotations: + assert a.startswith('@') pkgDecl = re.compile(r"^package\s+([a-zA-Z_][\w\.]*)\s*;$") - for root, _, files in os.walk(srcDir): - for name in files: - if name.endswith('.java') and name != 'package-info.java': - hasTest = False - with open(join(root, name)) as f: - pkg = None - for line in f: - if line.startswith("package "): - match = pkgDecl.match(line) - if match: - pkg = match.group(1) - else: - if line.strip().startswith(annotation): - hasTest = True - break - if hasTest: - assert pkg is not None - if pkgRoot is None or pkg.startswith(pkgRoot): - classes.append(pkg + '.' + name[:-len('.java')]) + for srcDir in p.source_dirs(): + outputDir = p.output_dir() + for root, _, files in os.walk(srcDir): + for name in files: + if name.endswith('.java') and name != 'package-info.java': + annotationFound = False + with open(join(root, name)) as f: + pkg = None + for line in f: + if line.startswith("package "): + match = pkgDecl.match(line) + if match: + pkg = match.group(1) + else: + stripped = line.strip() + for a in annotations: + if stripped == a or stripped.startswith(a + '('): + annotationFound = True + break + if annotationFound: + break + if annotationFound: + basename = name[:-len('.java')] + assert pkg is not None + if pkgRoot is None or pkg.startswith(pkgRoot): + pkgOutputDir = join(outputDir, pkg.replace('.', os.path.sep)) + for e in os.listdir(pkgOutputDir): + if includeInnerClasses: + if e.endswith('.class') and (e.startswith(basename) or e.startswith(basename + '$')): + classes.append(pkg + '.' + e[:-len('.class')]) + elif e == basename + '.class': + classes.append(pkg + '.' + basename) # Table of unit tests. @@ -639,7 +652,7 @@ p = mx.project(proj) classes = [] for pkg in _unittests[proj]: - _add_classes_with_annotation(classes, join(p.dir, 'src'), pkg, '@Test') + _find_classes_with_annotations(classes, p, pkg, ['@Test']) if len(pos) != 0: classes = [c for c in classes if containsAny(c, pos)] @@ -669,7 +682,7 @@ p = mx.project(proj) classes = [] for pkg in _jtttests[proj]: - _add_classes_with_annotation(classes, join(p.dir, 'src'), pkg, '@Test') + _find_classes_with_annotations(classes, p, pkg, ['@Test']) if len(pos) != 0: classes = [c for c in classes if containsAny(c, pos)]