Mercurial > hg > truffle
changeset 5489:5d0d72b37f88
Switch to new loop transformation framework, use it for peeling and full unrolling for snippets
Change behaviour or addDuplicates : it now connects things to the 'outer world' for inputs. Only replacement of nodes which are in the set of duplicated nodes get their edges updates
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 Wed Jun 06 19:09:05 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 Wed Jun 06 19:09:05 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 Wed Jun 06 19:09:05 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 Wed Jun 06 19:09:05 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 Wed Jun 06 19:09:05 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 Wed Jun 06 19:09:05 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 Wed Jun 06 18:55:39 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,202 +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; -import com.oracle.graal.nodes.util.*; - - - -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 = GraphUtil.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 Wed Jun 06 18:55:39 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 Wed Jun 06 19:09:05 2012 +0200 @@ -0,0 +1,87 @@ +/* + * 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))); + duplicateLoop.getDuplicatedNode(ifNode).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 Wed Jun 06 19:09:05 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 Wed Jun 06 18:55:39 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,313 +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.*; - -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.replaceAtPredecessor(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 = 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); - } - } - } - } - } - - 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.replaceAtPredecessor(entry); - exit.setNext(fixed); - } -}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Wed Jun 06 18:55:39 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Wed Jun 06 19:09:05 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.graph/src/com/oracle/graal/graph/NodeClass.java Wed Jun 06 18:55:39 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Wed Jun 06 19:09:05 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; @@ -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,38 +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); - Class< ? > edgeType = node.getNodeClass().inputTypes[pos.index]; - if (edgeType != null && !edgeType.isAssignableFrom(replacement.getClass())) { - target = null; - } else { + 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; } - } else { - target = newNodes.get(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()) { @@ -974,36 +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); - Class< ? > edgeType = node.getNodeClass().successorTypes[pos.index]; - if (edgeType != null && !edgeType.isAssignableFrom(replacement.getClass())) { - target = null; - } else { - target = replacement; + 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; + } } - } else { - target = newNodes.get(succ); } 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.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 18:55:39 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 19:09:05 2012 +0200 @@ -32,7 +32,6 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; -import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.snippets.nodes.*; @@ -119,36 +118,19 @@ boolean exploded = false; do { exploded = false; - for (Node node : snippetCopy.getNodes()) { - if (node instanceof ExplodeLoopNode) { - final ExplodeLoopNode explodeLoop = (ExplodeLoopNode) node; - LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); - 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, immutabilityPredicate).apply(snippetCopy); - peel++; - } - Debug.dump(snippetCopy, "After exploding loop %s", loopBegin); - exploded = true; - break; - } - } - - FixedNode explodeLoopNext = explodeLoop.next(); - explodeLoop.clearSuccessors(); - explodeLoop.replaceAtPredecessor(explodeLoopNext); - explodeLoop.replaceAtUsages(null); - GraphUtil.killCFG(explodeLoop); - break; - } + ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first(); + if (explodeLoop != null) { + LoopEx loop = new LoopsData(snippetCopy).loop(explodeLoop.findLoopBegin()); + int mark = snippetCopy.getMark(); + LoopTransformations.fullUnroll(loop); + new CanonicalizerPhase(null, runtime, null, mark, immutabilityPredicate).apply(snippetCopy); + FixedNode explodeLoopNext = explodeLoop.next(); + explodeLoop.clearSuccessors(); + explodeLoop.replaceAtPredecessor(explodeLoopNext); + explodeLoop.replaceAtUsages(null); + GraphUtil.killCFG(explodeLoop); + exploded = true; + break; } } while (exploded);