Mercurial > hg > graal-compiler
changeset 5214:1020e363a05d
Loop peeling
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 09 19:56:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 09 19:59:01 2012 +0200 @@ -168,6 +168,7 @@ } } if (GraalOptions.OptLoops) { + new LoopTransformPhase().apply(graph); new SafepointPollingEliminationPhase().apply(graph); } new RemoveValueProxyPhase().apply(graph);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformDataResolver.java Mon Apr 09 19:59:01 2012 +0200 @@ -0,0 +1,196 @@ +/* + * 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.*; + + + +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; + 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 = loopBegin.graph().add(new PhiNode(phi.kind(), merge, phi.type())); + 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 (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 = loopBegin.graph().add(new PhiNode(phi.kind(), loopBegin, phi.type())); + 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); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformUtil.java Mon Apr 09 19:59:01 2012 +0200 @@ -0,0 +1,59 @@ +/* + * 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.*; +import com.oracle.graal.nodes.util.*; + + +public class LoopTransformUtil { + + public static void peel(Loop loop) { + GraphUtil.normalizeLoopBegin(loop.loopBegin()); + SuperBlock block = wholeLoop(loop); + SuperBlock peel = block.duplicate(); // duplicates the nodes, merges early exits + + peel.insertBefore(loop.loopBegin().forwardEnd()); // connects peeled part's CFG + + LoopTransformDataResolver resolver = new LoopTransformDataResolver(); + resolver.wholeLoop(block).peeled(peel); // block (comming from the loop) was peeled into peel + resolver.resolve(); + + peel.finish(); + } + + 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, loop.loopBegin()); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/SuperBlock.java Mon Apr 09 19:59:01 2012 +0200 @@ -0,0 +1,344 @@ +/* + * 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 LoopBeginNode loop; + protected Map<Node, Node> duplicationMapping; + protected SuperBlock original; + + public SuperBlock(BeginNode entry, BeginNode exit, List<BeginNode> blocks, List<BeginNode> earlyExits, LoopBeginNode loop) { + this.entry = entry; + this.exit = exit; + this.blocks = blocks; + this.earlyExits = earlyExits; + this.loop = loop; + assert blocks.contains(entry); + assert !blocks.contains(exit) || exit == entry; + } + + public Map<Node, Node> getDuplicationMapping() { + return duplicationMapping; + } + + public BeginNode getEntry() { + return entry; + } + + public SuperBlock duplicate() { + NodeBitMap nodes = computeNodes(); + Map<Node, Node> replacements = new HashMap<>(); + StructuredGraph graph = (StructuredGraph) entry.graph(); + BeginNode newEntry = graph.add(new BeginNode()); + BeginNode newExit = null; + List<BeginNode> newEarlyExits = new ArrayList<>(earlyExits.size()); + if (!(exit instanceof MergeNode)) { + newExit = graph.add(new BeginNode()); + replacements.put(exit, newExit); + } + replacements.put(entry, newEntry); // no merge/loop begin + for (BeginNode earlyExit : earlyExits) { + BeginNode newEarlyExit = graph.add(new BeginNode()); + newEarlyExits.add(newEarlyExit); + replacements.put(earlyExit, newEarlyExit); + } + if (loop != null) { + for (LoopEndNode end : loop.loopEnds()) { + if (nodes.isMarked(end)) { + replacements.put(end, graph.add(new EndNode())); + } + } + } + Map<Node, Node> duplicates = graph.addDuplicates(nodes, replacements); + if (exit instanceof MergeNode) { + newExit = mergeExits(replacements, graph, duplicates, (MergeNode) 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(newEntry, newExit, newBlocks, newEarlyExits, loop); + superBlock.duplicationMapping = duplicates; + superBlock.original = this; + return superBlock; + } + + private BeginNode mergeExits(Map<Node, Node> replacements, StructuredGraph graph, Map<Node, Node> duplicates, MergeNode mergeExit) { + BeginNode newExit; + List<EndNode> endsToMerge = new LinkedList<>(); + if (mergeExit == loop) { + 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); + } + } + } + + 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().duplicate(); + newExitMerge.setStateAfter(state); // this state is wrong (incudes phis from the loop begin) needs to be fixed while resolving data + for (EndNode end : endsToMerge) { + newExitMerge.addForwardEnd(end); + } + } + return newExit; + } + + public void finish() { + 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 (ValueProxyNode vpn : earlyExit.proxies().snapshot()) { + ValueNode replaceWith; + ValueProxyNode newVpn = (ValueProxyNode) duplicates.get(vpn); + if (newVpn != null) { + PhiNode phi = graph.add(new PhiNode(vpn.kind(), merge, vpn.type())); + phi.addInput(vpn); + phi.addInput(newVpn); + if (vpn.type() == PhiType.Value) { + replaceWith = phi; + } else { + assert vpn.type() == PhiType.Virtual; + VirtualObjectFieldNode vof = (VirtualObjectFieldNode) GraphUtil.unProxify(vpn); + VirtualObjectFieldNode newVof = (VirtualObjectFieldNode) 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()) { + if (GraphUtil.unProxify(vpn) == value) { + return vpn; + } + } + return null; + } + + private static ValueNode mergeVirtualChain( + StructuredGraph graph, + VirtualObjectFieldNode vof, + VirtualObjectFieldNode newVof, + PhiNode vPhi, + BeginNode earlyExit, + BeginNode newEarlyExit, + MergeNode merge) { + VirtualObjectNode vObject = vof.object(); + assert newVof.object() == 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, PhiType.Value)); + ValueProxyNode inputProxy = findProxy(value, earlyExit); + if (inputProxy != null) { + ValueProxyNode newInputProxy = findProxy(newValue, newEarlyExit); + assert newInputProxy != null; + 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; + } + + private static ValueNode[] virtualState(VirtualObjectFieldNode vof) { + VirtualObjectNode vObj = vof.object(); + 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 { + assert currentField instanceof PhiNode && ((PhiNode) currentField).type() == PhiType.Virtual : currentField; + currentField = ((PhiNode) currentField).valueAt(0); + } + } while (currentField != null); + return state; + } + + private NodeBitMap computeNodes() { + NodeBitMap loopNodes = entry.graph().createNodeBitMap(); + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + if (n instanceof Invoke) { + loopNodes.mark(((Invoke) n).callTarget()); + } + if (n instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) n).stateAfter(); + if (stateAfter != null) { + loopNodes.mark(stateAfter); + } + } + loopNodes.mark(n); + } + } + for (BeginNode earlyExit : earlyExits) { + FrameState stateAfter = earlyExit.stateAfter(); + assert stateAfter != null; + loopNodes.mark(stateAfter); + loopNodes.mark(earlyExit); + for (ValueProxyNode proxy : earlyExit.proxies()) { + loopNodes.mark(proxy); + } + } + + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + for (Node usage : n.usages()) { + markFloating(usage, loopNodes, ""); + } + } + } + + if (entry instanceof LoopBeginNode) { + for (PhiNode phi : ((LoopBeginNode) entry).phis()) { + loopNodes.clear(phi); + } + } + + return loopNodes; + } + + private static boolean markFloating(Node n, NodeBitMap loopNodes, String ind) { + //System.out.println(ind + "markFloating(" + n + ")"); + if (loopNodes.isMarked(n)) { + return true; + } + if (n instanceof FixedNode) { + return false; + } + boolean mark = false; + if (n instanceof PhiNode) { + mark = loopNodes.isMarked(((PhiNode) n).merge()); + if (mark) { + loopNodes.mark(n); + } else { + return false; + } + } + for (Node usage : n.usages()) { + if (markFloating(usage, loopNodes, " " + ind)) { + 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); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Mon Apr 09 19:59:01 2012 +0200 @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.phases; + +import java.util.*; + +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 { + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); + Loop[] loops = cfg.getLoops(); + Arrays.sort(loops, new Comparator<Loop>() { + @Override + public int compare(Loop o1, Loop o2) { + return o1.depth - o2.depth; + } + }); + for (Loop loop : loops) { + LoopTransformUtil.peel(loop); + Debug.dump(graph, "After peeling %s", loop); + } + } + } + + +}
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Mon Apr 09 19:56:10 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Mon Apr 09 19:59:01 2012 +0200 @@ -352,6 +352,10 @@ node.getNodeClass().set(node, this, value); } + public boolean isValidFor(Node node, Node from) { + return node.getNodeClass().isValid(this, from.getNodeClass()); + } + @Override public int hashCode() { final int prime = 31; @@ -605,6 +609,18 @@ return true; } + public boolean isValid(Position pos, NodeClass from) { + long[] offsets = pos.input ? inputOffsets : successorOffsets; + if (pos.index >= offsets.length) { + return false; + } + long[] fromOffsets = pos.input ? from.inputOffsets : from.successorOffsets; + if (pos.index >= fromOffsets.length) { + return false; + } + return offsets[pos.index] == fromOffsets[pos.index]; + } + public Node get(Node node, Position pos) { long offset = pos.input ? inputOffsets[pos.index] : successorOffsets[pos.index]; if (pos.subIndex == NOT_ITERABLE) { @@ -678,7 +694,7 @@ while (index < directInputCount) { Node input = getNode(node, inputOffsets[index]); if (input == old) { - assert other == null || inputTypes[index].isAssignableFrom(other.getClass()); + assert other == null || inputTypes[index].isAssignableFrom(other.getClass()); // : "Can not assign " + other.getClass() + " to " + inputTypes[index] + " in " + node; putNode(node, inputOffsets[index], other); return true; } @@ -700,7 +716,7 @@ while (index < directSuccessorCount) { Node successor = getNode(node, successorOffsets[index]); if (successor == old) { - assert other == null || successorTypes[index].isAssignableFrom(other.getClass()) : successorTypes[index] + " is not compatible with " + other.getClass(); + assert other == null || successorTypes[index].isAssignableFrom(other.getClass()); // : successorTypes[index] + " is not compatible with " + other.getClass(); putNode(node, successorOffsets[index], other); return true; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Loop.java Mon Apr 09 19:56:10 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Loop.java Mon Apr 09 19:59:01 2012 +0200 @@ -24,6 +24,8 @@ import java.util.*; +import com.oracle.graal.nodes.*; + public class Loop { public final Loop parent; public final List<Loop> children; @@ -53,4 +55,8 @@ public String toString() { return "loop " + index + " depth " + depth + (parent != null ? " outer " + parent.index : ""); } + + public LoopBeginNode loopBegin() { + return (LoopBeginNode) header.getBeginNode(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Mon Apr 09 19:56:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Mon Apr 09 19:59:01 2012 +0200 @@ -126,4 +126,45 @@ public NodeIterable<ValueProxyNode> proxies() { return usages().filter(ValueProxyNode.class); } + + public NodeIterable<FixedNode> getBlockNodes() { + return new NodeIterable<FixedNode>() { + @Override + public Iterator<FixedNode> iterator() { + return new BlockNodeIterator(BeginNode.this); + } + }; + } + + private class BlockNodeIterator implements Iterator<FixedNode> { + private FixedNode current; + + public BlockNodeIterator(FixedNode next) { + this.current = next; + } + + @Override + public boolean hasNext() { + return current != null; + } + + @Override + public FixedNode next() { + FixedNode ret = current; + if (ret == null) { + throw new NoSuchElementException(); + } + if (!(current instanceof FixedWithNextNode) || (current instanceof BeginNode && current != BeginNode.this)) { + current = null; + } else { + current = ((FixedWithNextNode) current).next(); + } + return ret; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Mon Apr 09 19:56:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Mon Apr 09 19:59:01 2012 +0200 @@ -184,6 +184,13 @@ return duplicate(newBci, false); } + /** + * Gets a copy of this frame state. + */ + public FrameState duplicate() { + return duplicate(bci); + } + public FrameState duplicate(int newBci, boolean duplicateOuter) { FrameState other = graph().add(new FrameState(method, newBci, localsSize, stackSize, rethrowException, duringCall)); other.values.setAll(values);