Mercurial > hg > graal-compiler
changeset 5492:35f9b57d70cb
Merge
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Thu, 07 Jun 2012 13:01:45 +0200 |
parents | f0130457c50c (diff) f70b1547c7bf (current diff) |
children | a4dfee0b8fbd e09a1efdeafd |
files | graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java |
diffstat | 27 files changed, 1186 insertions(+), 824 deletions(-) [+] |
line wrap: on
line diff
--- /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 13:01:45 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(); + } +}
--- /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 13:01:45 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<Node, Node> 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 extends Node, Old extends New> New getDuplicatedNode(Old n) { + assert isDuplicate(); + return (New) duplicationMap.get(n); + } + + protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) { + duplicationMap.put(oldNode, newNode); + } + + public boolean isDuplicate() { + return original != null; + } + + public LoopFragment original() { + return original; + } + + public abstract NodeIterable<Node> 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<BeginNode> toHirBlocks(Collection<Block> blocks) { + List<BeginNode> hir = new ArrayList<>(blocks.size()); + for (Block b : blocks) { + hir.add(b.getBeginNode()); + } + return hir; + } + + protected static NodeBitMap computeNodes(Graph graph, Collection<BeginNode> blocks) { + return computeNodes(graph, blocks, Collections.<BeginNode>emptyList()); + } + + protected static NodeBitMap computeNodes(Graph graph, Collection<BeginNode> blocks, Collection<BeginNode> 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); + } + } + } + } + } +}
--- /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 13:01:45 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<PhiNode, ValueNode> 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<Node> 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<PhiNode> 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<EndNode> endsToMerge = new LinkedList<>(); + Map<EndNode, LoopEndNode> 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; + } +}
--- /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 13:01:45 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<Node> nodes() { + // TODO Auto-generated method stub + return null; + } +}
--- /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 13:01:45 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<Node> nodes() { + // TODO Auto-generated method stub + return null; + } +}
--- /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 13:01:45 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<Node> 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 + + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformDataResolver.java Thu Jun 07 12:15:41 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<ResolvableSuperBlock> 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<Node, Node> dup = peel.getDuplicationMapping(); - List<PhiNode> 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<EndNode, LoopEndNode> 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<Node, Node> 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<Node, Node> 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); - } -}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformUtil.java Thu Jun 07 12:15:41 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<BeginNode> blocks = new LinkedList<>(); - List<BeginNode> 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; - } -}
--- /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 13:01:45 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); + } + } +}
--- /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 13:01:45 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<Loop, LoopEx> lirLoopToEx = new IdentityHashMap<>(); + private Map<LoopBeginNode, LoopEx> 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<LoopEx> loops() { + return lirLoopToEx.values(); + } + + public List<LoopEx> outterFirst() { + ArrayList<LoopEx> loops = new ArrayList<>(loops()); + Collections.sort(loops, new Comparator<LoopEx>() { + @Override + public int compare(LoopEx o1, LoopEx o2) { + return o1.lirLoop().depth - o2.lirLoop().depth; + } + }); + return loops; + } + + public Collection<LoopEx> countedLoops() { + List<LoopEx> counted = new LinkedList<>(); + for (LoopEx loop : loops()) { + if (loop.isCounted()) { + counted.add(loop); + } + } + return counted; + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/SuperBlock.java Thu Jun 07 12:15:41 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<BeginNode> blocks; - protected List<BeginNode> earlyExits; - protected Map<Node, Node> duplicationMapping; - protected SuperBlock original; - protected NodeBitMap allNodes; - protected NodeBitMap allNodesExcludeLoopPhi; - - public SuperBlock(BeginNode entry, BeginNode exit, List<BeginNode> blocks, List<BeginNode> 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<Node, Node> 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<Node, Node> 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<BeginNode> 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<Node, Node> 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<BeginNode> 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<Node, Node> 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<Node, Node> replacements, Map<Node, Node> duplicates) { - List<EndNode> 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<EndNode> 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<BeginNode> earlyExits, Map<Node, Node> 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<ValueNode> virtuals = vPhi.values(); - VirtualObjectNode vObject = virtualObject(GraphUtil.unProxify(virtuals.first())); - List<ValueNode[]> 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); - } -}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/ConvertDeoptimizeToGuardPhase.java Thu Jun 07 13:01:45 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); } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Thu Jun 07 13:01:45 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<Loop>() { - @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); } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Thu Jun 07 13:01:45 2012 +0200 @@ -267,7 +267,7 @@ } FixedNode next = checkCastNode.next(); checkCastNode.setNext(null); - checkCastNode.replaceAtPredecessors(next); + checkCastNode.replaceAtPredecessor(next); GraphUtil.killCFG(checkCastNode); } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Thu Jun 07 13:01:45 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) {
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Jun 07 13:01:45 2012 +0200 @@ -313,6 +313,15 @@ public Iterator<Node> iterator() { return new NodeIterator(); } + + @SuppressWarnings("unchecked") + @Override + public <F extends Node> NodeIterable<F> filter(Class<F> clazz) { + if (IterableNodeType.class.isAssignableFrom(clazz)) { + return getNodes((Class) clazz); + } + return super.filter(clazz); + } }; }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java Thu Jun 07 13:01:45 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); } }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Jun 07 13:01:45 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<Node> 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<Node, Node> 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<Node, Node> 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<Node, Node> 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; } }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java Thu Jun 07 13:01:45 2012 +0200 @@ -43,7 +43,7 @@ @Override protected void update(T oldNode, T newNode) { - self.updatePredecessors(oldNode, newNode); + self.updatePredecessor(oldNode, newNode); } @Override
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Thu Jun 07 13:01:45 2012 +0200 @@ -34,10 +34,10 @@ return new FilteredNodeIterable<>(this).until(clazz); } @SuppressWarnings("unchecked") - public <F extends T> FilteredNodeIterable<F> filter(Class<F> clazz) { - return (FilteredNodeIterable<F>) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); + public <F extends T> NodeIterable<F> filter(Class<F> clazz) { + return (NodeIterable<F>) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); } - public FilteredNodeIterable<T> filterInterface(Class<?> iface) { + public NodeIterable<T> filterInterface(Class<?> iface) { return new FilteredNodeIterable<>(this).and(NodePredicates.isAInterface(iface)); } public FilteredNodeIterable<T> filter(NodePredicate predicate) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Thu Jun 07 13:01:45 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;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Thu Jun 07 13:01:45 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;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Thu Jun 07 13:01:45 2012 +0200 @@ -177,7 +177,7 @@ phi.addInput(newInput); } this.removeEnd(end); - end.replaceAtPredecessors(newEnd); + end.replaceAtPredecessor(newEnd); end.safeDelete(); tool.addToWorkList(newEnd.predecessor()); // ? }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ScheduledNode.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ScheduledNode.java Thu Jun 07 13:01:45 2012 +0200 @@ -35,7 +35,7 @@ } public void setScheduledNext(ScheduledNode x) { - updatePredecessors(scheduledNext, x); + updatePredecessor(scheduledNext, x); scheduledNext = x; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Thu Jun 07 13:01:45 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);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Thu Jun 07 13:01:45 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<ValueNode> virtuals = vPhi.values(); + VirtualObjectNode vObject = virtualObject(unProxify(virtuals.first())); + List<ValueNode[]> 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; + } }
--- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Thu Jun 07 12:15:41 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Thu Jun 07 13:01:45 2012 +0200 @@ -264,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); @@ -451,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);