Mercurial > hg > truffle
changeset 5218:c4696edb6e95
Merge.
| author | Doug Simon <doug.simon@oracle.com> |
|---|---|
| date | Tue, 10 Apr 2012 12:22:46 +0200 |
| parents | b64933dc4830 (diff) 70777e50f1e6 (current diff) |
| children | ddccd4abdb09 |
| files | |
| diffstat | 46 files changed, 1889 insertions(+), 171 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Apr 10 12:22:46 2012 +0200 @@ -128,46 +128,38 @@ new PhiStampPhase().apply(graph); + if (GraalOptions.ProbabilityAnalysis && graph.start().probability() == 0) { + new ComputeProbabilityPhase().apply(graph); + } + + if (GraalOptions.PropagateTypes) { + new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); + } + if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } - if (GraalOptions.ProbabilityAnalysis && graph.start().probability() == 0) { - new ComputeProbabilityPhase().apply(graph); - } - if (GraalOptions.Intrinsify) { new IntrinsificationPhase(runtime).apply(graph); } - if (GraalOptions.PropagateTypes) { - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, assumptions).apply(graph); - } - - new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); - } - if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) { new InliningPhase(target, runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); new DeadCodeEliminationPhase().apply(graph); new PhiStampPhase().apply(graph); - } + if (GraalOptions.PropagateTypes) { + new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); + } - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } } - if (GraalOptions.PropagateTypes) { - new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); - } plan.runPhases(PhasePosition.HIGH_LEVEL, graph); - if (GraalOptions.OptLoops) { - new SafepointPollingEliminationPhase().apply(graph); - } - if (GraalOptions.EscapeAnalysis && !plan.isPhaseDisabled(EscapeAnalysisPhase.class)) { new EscapeAnalysisPhase(target, runtime, assumptions, cache, plan, optimisticOpts).apply(graph); new PhiStampPhase().apply(graph); @@ -175,7 +167,18 @@ new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } } - + if (GraalOptions.OptLoops) { + if (GraalOptions.OptLoopTransform) { + new LoopTransformPhase().apply(graph); + } + if (GraalOptions.OptSafepointElimination) { + new SafepointPollingEliminationPhase().apply(graph); + } + } + new RemoveValueProxyPhase().apply(graph); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } if (GraalOptions.OptGVN) { new GlobalValueNumberingPhase().apply(graph); } @@ -197,6 +200,9 @@ if (GraalOptions.PropagateTypes) { new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); } + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } if (GraalOptions.OptGVN) { new GlobalValueNumberingPhase().apply(graph); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Tue Apr 10 12:22:46 2012 +0200 @@ -98,6 +98,9 @@ //rematerialize settings public static float MinimumUsageProbability = 0.95f; + //loop transform settings + public static float MinimumPeelProbability = 0.25f; + // debugging settings public static int MethodEndBreakpointGuards = 0; public static boolean ZapStackOnMethodEntry = ____; @@ -143,6 +146,7 @@ public static boolean PrintAssembly = ____; public static boolean PrintCodeBytes = ____; public static int PrintAssemblyBytesPerLine = 16; + public static boolean PrintBailout = ____; public static int TraceLinearScanLevel = 0; public static boolean TraceRegisterAllocation = false; public static int TraceLIRGeneratorLevel = 0; @@ -192,12 +196,14 @@ public static boolean OptReadElimination = true; public static boolean OptGVN = true; public static boolean OptCanonicalizer = true; - public static boolean OptLoops = ____; + public static boolean OptLoops = true; public static boolean ScheduleOutOfLoops = true; public static boolean OptReorderLoops = true; public static boolean OptEliminateGuards = true; public static boolean OptImplicitNullChecks = true; public static boolean OptLivenessAnalysis = true; + public static boolean OptLoopTransform = true; + public static boolean OptSafepointElimination = true; /** * Flag to turn on SSA-based register allocation, which is currently under development.
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Tue Apr 10 12:22:46 2012 +0200 @@ -860,7 +860,7 @@ for (int operandNum = 0; operandNum < blockData.get(ir.cfg.getStartBlock()).liveIn.size(); operandNum++) { if (blockData.get(ir.cfg.getStartBlock()).liveIn.get(operandNum)) { CiValue operand = operandFor(operandNum); - TTY.println(" var %d; operand=%s", operandNum, operand.toString()); + TTY.println(" var %d; operand=%s; node=%s", operandNum, operand.toString(), gen.valueForOperand(operand)); for (int j = 0; j < numBlocks; j++) { Block block = blockAt(j);
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Tue Apr 10 12:22:46 2012 +0200 @@ -31,6 +31,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.virtual.*; public class DebugInfoBuilder { @@ -54,7 +55,13 @@ FrameState current = topState; do { for (Node n : current.virtualObjectMappings()) { - VirtualObjectFieldNode field = (VirtualObjectFieldNode) n; + Node p = n; + while (p instanceof PhiNode) { + PhiNode phi = (PhiNode) p; + assert phi.type() == PhiType.Virtual; + p = phi.valueAt(0); + } + VirtualObjectFieldNode field = (VirtualObjectFieldNode) p; // null states occur for objects with 0 fields if (field != null && !objectStates.containsKey(field.object())) { objectStates.put(field.object(), field);
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Tue Apr 10 12:22:46 2012 +0200 @@ -27,6 +27,7 @@ import static com.oracle.max.cri.ci.CiValue.*; import java.util.*; +import java.util.Map.Entry; import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.util.*; @@ -173,6 +174,15 @@ return nodeOperands.get(node); } + public ValueNode valueForOperand(CiValue value) { + for (Entry<Node, CiValue> entry : nodeOperands.entries()) { + if (entry.getValue() == value) { + return (ValueNode) entry.getKey(); + } + } + return null; + } + /** * Creates a new {@linkplain Variable variable}. * @param kind The kind of the new variable.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopTransformDataResolver.java Tue Apr 10 12:22:46 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 Tue Apr 10 12:22:46 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 Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,352 @@ +/* + * 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; + protected NodeBitMap loopNodes; + + 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 NodeBitMap loopNodes() { + if (loopNodes == null) { + loopNodes = computeNodes(); + } + return loopNodes; + } + + public SuperBlock duplicate() { + NodeBitMap nodes = loopNodes(); + 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 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, ""); + } + } + } + + if (entry instanceof LoopBeginNode) { + for (PhiNode phi : ((LoopBeginNode) entry).phis()) { + nodes.clear(phi); + } + } + + return nodes; + } + + 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); + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java Tue Apr 10 12:22:46 2012 +0200 @@ -130,8 +130,12 @@ @Override public void loopEnds(LoopBeginNode loopBegin, List<BlockExitState> loopEndStates) { - while (!(virtualObjectField instanceof PhiNode)) { - virtualObjectField = ((VirtualObjectFieldNode) virtualObjectField).lastState(); + while (!loopBegin.isPhiAtMerge(virtualObjectField)) { + if (virtualObjectField instanceof PhiNode) { + virtualObjectField = ((PhiNode) virtualObjectField).valueAt(0); + } else { + virtualObjectField = ((VirtualObjectFieldNode) virtualObjectField).lastState(); + } } for (BlockExitState loopEndState : loopEndStates) { ((PhiNode) virtualObjectField).addInput(loopEndState.virtualObjectField); @@ -184,6 +188,11 @@ FixedNode next = node.next(); graph.removeFixed(node); + for (ValueProxyNode vpn : virtual.usages().filter(ValueProxyNode.class).snapshot()) { + assert vpn.value() == virtual; + graph.replaceFloating(vpn, virtual); + } + if (virtual.fieldsCount() > 0) { final BlockExitState startState = new BlockExitState(escapeFields, virtual); final PostOrderNodeIterator<?> iterator = new PostOrderNodeIterator<BlockExitState>(next, startState) { @@ -193,9 +202,25 @@ if (changedField != -1) { state.updateField(changedField); } + if (curNode instanceof LoopExitNode) { + state.virtualObjectField = graph.unique(new ValueProxyNode(state.virtualObjectField, (LoopExitNode) curNode, PhiType.Virtual)); + for (int i = 0; i < state.fieldState.length; i++) { + state.fieldState[i] = graph.unique(new ValueProxyNode(state.fieldState[i], (LoopExitNode) curNode, PhiType.Value)); + } + } if (!curNode.isDeleted() && curNode instanceof StateSplit && ((StateSplit) curNode).stateAfter() != null) { if (state.virtualObjectField != null) { - ((StateSplit) curNode).stateAfter().addVirtualObjectMapping(state.virtualObjectField); + ValueNode v = state.virtualObjectField; + if (curNode instanceof LoopBeginNode) { + while (!((LoopBeginNode) curNode).isPhiAtMerge(v)) { + if (v instanceof PhiNode) { + v = ((PhiNode) v).valueAt(0); + } else { + v = ((VirtualObjectFieldNode) v).lastState(); + } + } + } + ((StateSplit) curNode).stateAfter().addVirtualObjectMapping(v); } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformPhase.java Tue Apr 10 12:22:46 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.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 { + + @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) { + double entryProbability = loop.loopBegin().forwardEnd().probability(); + if (entryProbability > GraalOptions.MinimumPeelProbability) { + Debug.log("Peeling %s", loop); + LoopTransformUtil.peel(loop); + Debug.dump(graph, "After peeling %s", loop); + } + } + } + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/RemoveValueProxyPhase.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,44 @@ +/* + * Copyright (c) 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 com.oracle.graal.nodes.*; + +public class RemoveValueProxyPhase extends Phase { + + @Override + protected void run(StructuredGraph graph) { + for (ValueProxyNode vpn : graph.getNodes(ValueProxyNode.class)) { + graph.replaceFloating(vpn, vpn.value()); + } + for (LoopExitNode exit : graph.getNodes(LoopExitNode.class)) { + FrameState stateAfter = exit.stateAfter(); + if (stateAfter != null) { + exit.setStateAfter(null); + if (stateAfter.usages().count() == 0) { + stateAfter.safeDelete(); + } + } + } + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Tue Apr 10 12:22:46 2012 +0200 @@ -227,6 +227,9 @@ if (newInstance instanceof ValueNode && ((ValueNode) newInstance).kind() != CiKind.Object) { StructuredGraph graph = (StructuredGraph) newInstance.graph(); for (CheckCastNode checkCastNode : newInstance.usages().filter(CheckCastNode.class).snapshot()) { + for (ValueProxyNode vpn : checkCastNode.usages().filter(ValueProxyNode.class).snapshot()) { + graph.replaceFloating(vpn, checkCastNode); + } for (Node checkCastUsage : checkCastNode.usages().snapshot()) { if (checkCastUsage instanceof ValueAnchorNode) { ValueAnchorNode valueAnchorNode = (ValueAnchorNode) checkCastUsage;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java Tue Apr 10 12:22:46 2012 +0200 @@ -108,6 +108,7 @@ return; } assert !(n instanceof PhiNode) : n; + assert !(n instanceof MergeNode); // if in CFG, schedule at the latest position possible in the outermost loop possible Block latestBlock = latestBlock(n); Block block; @@ -120,7 +121,6 @@ } else { block = latestBlock; } - assert !(n instanceof MergeNode); cfg.getNodeToBlock().set(n, block); nodesFor.get(block).add(n); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Tue Apr 10 12:22:46 2012 +0200 @@ -882,15 +882,7 @@ returnDuplicate.clearInputs(); Node n = invoke.next(); invoke.setNext(null); - if (n instanceof BeginNode) { - BeginNode begin = (BeginNode) n; - FixedNode next = begin.next(); - begin.setNext(null); - returnDuplicate.replaceAndDelete(next); - begin.safeDelete(); - } else { - returnDuplicate.replaceAndDelete(n); - } + returnDuplicate.replaceAndDelete(n); } invoke.node().clearInputs();
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Tue Apr 10 12:22:46 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.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/CompilationTask.java Tue Apr 10 12:22:46 2012 +0200 @@ -132,8 +132,12 @@ } catch (CiBailout bailout) { Debug.metric("Bailouts").increment(); if (GraalOptions.ExitVMOnBailout) { + TTY.cachedOut.println(CiUtil.format("%H.%n(%p)", method)); bailout.printStackTrace(TTY.cachedOut); System.exit(-1); + } else if (GraalOptions.PrintBailout) { + TTY.cachedOut.println(CiUtil.format("%H.%n(%p)", method)); + bailout.printStackTrace(TTY.cachedOut); } } catch (Throwable t) { if (GraalOptions.ExitVMOnException) {
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotRuntime.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/ri/HotSpotRuntime.java Tue Apr 10 12:22:46 2012 +0200 @@ -304,10 +304,9 @@ AnchorNode anchor = graph.add(new AnchorNode()); graph.addBeforeFixed(storeIndexed, anchor); GuardNode guard = (GuardNode) tool.createGuard(graph.unique(new NullCheckNode(array, false)), RiDeoptReason.NullCheckException, RiDeoptAction.InvalidateReprofile, StructuredGraph.INVALID_GRAPH_ID); - ReadNode arrayClass = graph.add(new ReadNode(array, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.hubOffset, graph), StampFactory.objectNonNull())); + FloatingReadNode arrayClass = graph.unique(new FloatingReadNode(array, null, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.hubOffset, graph), StampFactory.objectNonNull())); arrayClass.setGuard(guard); - graph.addBeforeFixed(storeIndexed, arrayClass); - ReadNode arrayElementKlass = graph.add(new ReadNode(arrayClass, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.arrayClassElementOffset, graph), StampFactory.objectNonNull())); + FloatingReadNode arrayElementKlass = graph.unique(new FloatingReadNode(arrayClass, null, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Object, config.arrayClassElementOffset, graph), StampFactory.objectNonNull())); value = graph.unique(new CheckCastNode(anchor, arrayElementKlass, null, value)); } } @@ -387,7 +386,7 @@ SafeReadNode klassOop = safeRead(graph, CiKind.Object, receiver, config.klassOopOffset, StampFactory.objectNonNull(), StructuredGraph.INVALID_GRAPH_ID); graph.start().setNext(klassOop); // TODO(thomaswue): Care about primitive classes! Crashes for primitive classes at the moment (klassOop == null) - ReadNode result = graph.add(new ReadNode(klassOop, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Int, config.klassModifierFlagsOffset, graph), StampFactory.forKind(CiKind.Int))); + FloatingReadNode result = graph.unique(new FloatingReadNode(klassOop, null, LocationNode.create(LocationNode.FINAL_LOCATION, CiKind.Int, config.klassModifierFlagsOffset, graph), StampFactory.forKind(CiKind.Int))); ReturnNode ret = graph.add(new ReturnNode(result)); klassOop.setNext(ret); return graph;
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Tue Apr 10 12:22:46 2012 +0200 @@ -121,12 +121,14 @@ public int endBci; public boolean isExceptionEntry; public boolean isLoopHeader; + public int loopId; public int blockID; public FixedWithNextNode firstInstruction; public FrameStateBuilder entryState; public ArrayList<Block> successors = new ArrayList<>(2); + public long exits; public int normalSuccessors; private boolean visited; @@ -191,6 +193,7 @@ private final BytecodeStream stream; private final RiExceptionHandler[] exceptionHandlers; private Block[] blockMap; + public Block[] loopHeaders; /** * Creates a new BlockMap instance from bytecode of the given method . @@ -204,6 +207,7 @@ this.blockMap = new Block[method.codeSize()]; this.canTrap = new BitSet(blockMap.length); this.blocks = new ArrayList<>(); + this.loopHeaders = new Block[64]; } public RiExceptionHandler[] exceptionHandlers() { @@ -223,7 +227,11 @@ } createJsrAlternatives(blockMap[0]); } + if (Debug.isLogEnabled()) { + this.log("Before BlockOrder"); + } computeBlockOrder(); + fixLoopBits(); initializeBlockIds(); @@ -231,7 +239,9 @@ // Discard big arrays so that they can be GCed blockMap = null; - + if (Debug.isLogEnabled()) { + this.log("Before LivenessAnalysis"); + } if (GraalOptions.OptLivenessAnalysis) { Debug.scope("LivenessAnalysis", new Runnable() { @Override @@ -541,6 +551,26 @@ } } + private boolean loopChanges; + + private void fixLoopBits() { + do { + loopChanges = false; + for (Block b : blocks) { + b.visited = false; + } + + long loop = fixLoopBits(blockMap[0]); + + if (loop != 0) { + // There is a path from a loop end to the method entry that does not pass the loop header. + // Therefore, the loop is non reducible (has more than one entry). + // We don't want to compile such methods because the IR only supports structured loops. + throw new CiBailout("Non-reducible loop"); + } + } while (loopChanges); + } + private void computeBlockOrder() { long loop = computeBlockOrder(blockMap[0]); @@ -555,6 +585,64 @@ Collections.reverse(blocks); } + public void log(String name) { + if (Debug.isLogEnabled()) { + String n = System.lineSeparator(); + StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :"); + sb.append(n); + Iterable<Block> it; + if (blocks.isEmpty()) { + it = new HashSet<>(Arrays.asList(blockMap)); + } else { + it = blocks; + } + for (Block b : it) { + if (b == null) { + continue; + } + sb.append("B").append(b.blockID).append(" (").append(b.startBci).append(" -> ").append(b.endBci).append(")"); + if (b.isLoopHeader) { + sb.append(" LoopHeader"); + } + if (b.isExceptionEntry) { + sb.append(" ExceptionEntry"); + } + sb.append(n).append(" Sux : "); + for (Block s : b.successors) { + sb.append("B").append(s.blockID).append(" (").append(s.startBci).append(" -> ").append(s.endBci).append(")"); + if (s.isExceptionEntry) { + sb.append("!"); + } + sb.append(" "); + } + sb.append(n).append(" Loop : "); + long l = b.loops; + int pos = 0; + while (l != 0) { + int lMask = 1 << pos; + if ((l & lMask) != 0) { + sb.append("B").append(loopHeaders[pos].blockID).append(" "); + l &= ~lMask; + } + pos++; + } + sb.append(n).append(" Exits : "); + l = b.exits; + pos = 0; + while (l != 0) { + int lMask = 1 << pos; + if ((l & lMask) != 0) { + sb.append("B").append(loopHeaders[pos].blockID).append(" "); + l &= ~lMask; + } + pos++; + } + sb.append(n); + } + Debug.log(sb.toString()); + } + } + /** * The next available loop number. */ @@ -581,6 +669,9 @@ assert block.loops == 0; block.loops = (long) 1 << (long) nextLoop; + Debug.log("makeLoopHeader(%s) -> %x", block, block.loops); + loopHeaders[nextLoop] = block; + block.loopId = nextLoop; nextLoop++; } assert Long.bitCount(block.loops) == 1; @@ -596,9 +687,13 @@ if (block.active) { // Reached block via backward branch. makeLoopHeader(block); + // Return cached loop information for this block. + return block.loops; + } else if (block.isLoopHeader) { + return block.loops & ~(1L << block.loopId); + } else { + return block.loops; } - // Return cached loop information for this block. - return block.loops; } block.visited = true; @@ -610,18 +705,50 @@ loops |= computeBlockOrder(successor); } + block.loops = loops; + Debug.log("computeBlockOrder(%s) -> %x", block, block.loops); + if (block.isLoopHeader) { - assert Long.bitCount(block.loops) == 1; - loops &= ~block.loops; + loops &= ~(1L << block.loopId); } - block.loops = loops; block.active = false; blocks.add(block); return loops; } + private long fixLoopBits(Block block) { + if (block.visited) { + // Return cached loop information for this block. + if (block.isLoopHeader) { + return block.loops & ~(1L << block.loopId); + } else { + return block.loops; + } + } + + block.visited = true; + long loops = block.loops; + for (Block successor : block.successors) { + // Recursively process successors. + loops |= fixLoopBits(successor); + } + for (Block successor : block.successors) { + successor.exits = loops & ~successor.loops; + } + if (block.loops != loops) { + loopChanges = true; + block.loops = loops; + Debug.log("fixLoopBits0(%s) -> %x", block, block.loops); + } + + if (block.isLoopHeader) { + loops &= ~(1L << block.loopId); + } + + return loops; + } private void computeLiveness() { for (Block block : blocks) {
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Tue Apr 10 12:22:46 2012 +0200 @@ -28,6 +28,7 @@ import java.util.*; +import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; import com.oracle.graal.nodes.*; @@ -200,15 +201,40 @@ } // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles). List<PhiNode> phiUsages = phi.usages().filter(PhiNode.class).snapshot(); + List<ValueProxyNode> vpnUsages = phi.usages().filter(ValueProxyNode.class).snapshot(); // Remove the phi function from all FrameStates where it is used and then delete it. - assert phi.usages().filter(isNotA(FrameState.class).nor(PhiNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states"; + assert phi.usages().filter(isNotA(FrameState.class).nor(PhiNode.class).nor(ValueProxyNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states"; phi.replaceAtUsages(null); phi.safeDelete(); for (PhiNode phiUsage : phiUsages) { deletePhi(phiUsage); } + for (ValueProxyNode proxyUsage : vpnUsages) { + deleteProxy(proxyUsage); + } + } + + private void deleteProxy(ValueProxyNode proxy) { + if (proxy.isDeleted()) { + return; + } + // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles). + List<PhiNode> phiUsages = proxy.usages().filter(PhiNode.class).snapshot(); + List<ValueProxyNode> vpnUsages = proxy.usages().filter(ValueProxyNode.class).snapshot(); + + // Remove the proxy function from all FrameStates where it is used and then delete it. + assert proxy.usages().filter(isNotA(FrameState.class).nor(PhiNode.class).nor(ValueProxyNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states"; + proxy.replaceAtUsages(null); + proxy.safeDelete(); + + for (PhiNode phiUsage : phiUsages) { + deletePhi(phiUsage); + } + for (ValueProxyNode proxyUsage : vpnUsages) { + deleteProxy(proxyUsage); + } } public void insertLoopPhis(LoopBeginNode loopBegin) { @@ -220,6 +246,23 @@ } } + public void insertProxies(LoopExitNode loopExit, FrameStateBuilder loopEntryState) { + for (int i = 0; i < localsSize(); i++) { + ValueNode value = localAt(i); + if (value != null && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) { + Debug.log(" inserting proxy for %s", value); + storeLocal(i, graph.unique(new ValueProxyNode(value, loopExit, PhiType.Value))); + } + } + for (int i = 0; i < stackSize(); i++) { + ValueNode value = stackAt(i); + if (value != null && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) { + Debug.log(" inserting proxy for %s", value); + storeStack(i, graph.unique(new ValueProxyNode(value, loopExit, PhiType.Value))); + } + } + } + private PhiNode createLoopPhi(MergeNode block, ValueNode value) { if (value == null) { return null; @@ -545,4 +588,18 @@ assert kind != CiKind.Void && kind != CiKind.Illegal; return kind == CiKind.Long || kind == CiKind.Double; } + + public boolean contains(ValueNode value) { + for (int i = 0; i < localsSize(); i++) { + if (localAt(i) == value) { + return true; + } + } + for (int i = 0; i < stackSize(); i++) { + if (stackAt(i) == value) { + return true; + } + } + return false; + } }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Tue Apr 10 12:22:46 2012 +0200 @@ -43,6 +43,7 @@ import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind; import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.util.*; import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; import com.oracle.max.cri.ri.RiType.Representation; @@ -104,6 +105,8 @@ } } + private Block[] loopHeaders; + public GraphBuilderPhase(RiRuntime runtime, GraphBuilderConfiguration graphBuilderConfig, OptimisticOptimizations optimisticOpts) { this.graphBuilderConfig = graphBuilderConfig; this.optimisticOpts = optimisticOpts; @@ -156,6 +159,7 @@ this.canTrapBitSet = blockMap.canTrap; exceptionHandlers = blockMap.exceptionHandlers(); + loopHeaders = blockMap.loopHeaders; lastInstr = currentGraph.start(); if (isSynchronized(method.accessFlags())) { @@ -1197,6 +1201,67 @@ return x; } + private static class Target { + FixedNode fixed; + FrameStateBuilder state; + public Target(FixedNode fixed, FrameStateBuilder state) { + this.fixed = fixed; + this.state = state; + } + } + + private Target checkLoopExit(FixedNode traget, Block targetBlock, FrameStateBuilder state) { + if (currentBlock != null) { + long exits = currentBlock.loops & ~targetBlock.loops; + if (exits != 0) { + LoopExitNode firstLoopExit = null; + LoopExitNode lastLoopExit = null; + + int pos = 0; + ArrayList<Block> exitLoops = new ArrayList<>(Long.bitCount(exits)); + do { + int lMask = 1 << pos; + if ((exits & lMask) != 0) { + exitLoops.add(loopHeaders[pos]); + exits &= ~lMask; + } + pos++; + } while (exits != 0); + + Collections.sort(exitLoops, new Comparator<Block>() { + @Override + public int compare(Block o1, Block o2) { + return Long.bitCount(o2.loops) - Long.bitCount(o1.loops); + } + }); + + int bci = targetBlock.startBci; + if (targetBlock instanceof ExceptionBlock) { + bci = ((ExceptionBlock) targetBlock).deoptBci; + } + FrameStateBuilder newState = state.copy(); + for (Block loop : exitLoops) { + LoopBeginNode loopBegin = (LoopBeginNode) loop.firstInstruction; + LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); + if (lastLoopExit != null) { + lastLoopExit.setNext(loopExit); + } + if (firstLoopExit == null) { + firstLoopExit = loopExit; + } + lastLoopExit = loopExit; + Debug.log("Traget %s (%s) Exits %s, scanning framestates...", targetBlock, traget, loop); + newState.insertProxies(loopExit, loop.entryState); + loopExit.setStateAfter(newState.create(bci)); + } + + lastLoopExit.setNext(traget); + return new Target(firstLoopExit, newState); + } + } + return new Target(traget, state); + } + private FixedNode createTarget(double probability, Block block, FrameStateBuilder stateAfter) { assert probability >= 0 && probability <= 1; if (probability == 0 && optimisticOpts.removeNeverExecutedCode()) { @@ -1206,23 +1271,25 @@ } } - private FixedNode createTarget(Block block, FrameStateBuilder stateAfter) { - assert block != null && stateAfter != null; - assert !block.isExceptionEntry || stateAfter.stackSize() == 1; + private FixedNode createTarget(Block block, FrameStateBuilder state) { + assert block != null && state != null; + assert !block.isExceptionEntry || state.stackSize() == 1; if (block.firstInstruction == null) { // This is the first time we see this block as a branch target. // Create and return a placeholder that later can be replaced with a MergeNode when we see this block again. block.firstInstruction = currentGraph.add(new BlockPlaceholderNode()); - block.entryState = stateAfter.copy(); + Target target = checkLoopExit(block.firstInstruction, block, state); + FixedNode result = target.fixed; + block.entryState = target.state == state ? state.copy() : target.state; block.entryState.clearNonLiveLocals(block.localsLiveIn); Debug.log("createTarget %s: first visit, result: %s", block, block.firstInstruction); - return block.firstInstruction; + return result; } // We already saw this block before, so we have to merge states. - if (!block.entryState.isCompatibleWith(stateAfter)) { + if (!block.entryState.isCompatibleWith(state)) { throw new CiBailout("stacks do not match; bytecodes would not verify"); } @@ -1230,8 +1297,9 @@ assert block.isLoopHeader && currentBlock.blockID >= block.blockID : "must be backward branch"; // Backward loop edge. We need to create a special LoopEndNode and merge with the loop begin node created before. LoopBeginNode loopBegin = (LoopBeginNode) block.firstInstruction; - LoopEndNode result = currentGraph.add(new LoopEndNode(loopBegin)); - block.entryState.merge(loopBegin, stateAfter); + Target target = checkLoopExit(currentGraph.add(new LoopEndNode(loopBegin)), block, state); + FixedNode result = target.fixed; + block.entryState.merge(loopBegin, target.state); Debug.log("createTarget %s: merging backward branch to loop header %s, result: %s", block, loopBegin, result); return result; @@ -1260,9 +1328,11 @@ MergeNode mergeNode = (MergeNode) block.firstInstruction; // The EndNode for the newly merged edge. - EndNode result = currentGraph.add(new EndNode()); - block.entryState.merge(mergeNode, stateAfter); - mergeNode.addForwardEnd(result); + EndNode newEnd = currentGraph.add(new EndNode()); + Target target = checkLoopExit(newEnd, block, state); + FixedNode result = target.fixed; + block.entryState.merge(mergeNode, target.state); + mergeNode.addForwardEnd(newEnd); Debug.log("createTarget %s: merging state, result: %s", block, result); return result; @@ -1274,9 +1344,7 @@ */ private BeginNode createBlockTarget(double probability, Block block, FrameStateBuilder stateAfter) { FixedNode target = createTarget(probability, block, stateAfter); - assert !(target instanceof BeginNode); - BeginNode begin = currentGraph.add(new BeginNode()); - begin.setNext(target); + BeginNode begin = BeginNode.begin(target); assert !(target instanceof DeoptimizeNode && begin.stateAfter() != null) : "We are not allowed to set the stateAfter of the begin node, because we have to deoptimize to a bci _before_ the actual if, so that the interpreter can update the profiling information."; @@ -1340,25 +1408,7 @@ assert begin.forwardEndCount() == 1; currentGraph.reduceDegenerateLoopBegin(begin); } else { - // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either the same or the phi itself. - for (PhiNode phi : begin.phis().snapshot()) { - checkRedundantPhi(phi); - } - } - } - } - - private static void checkRedundantPhi(PhiNode phiNode) { - if (phiNode.isDeleted() || phiNode.valueCount() == 1) { - return; - } - - ValueNode singleValue = phiNode.singleValue(); - if (singleValue != null) { - Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot(); - ((StructuredGraph) phiNode.graph()).replaceFloating(phiNode, singleValue); - for (PhiNode phi : phiUsages) { - checkRedundantPhi(phi); + GraphUtil.normalizeLoopBegin(begin); } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/Loop15.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,64 @@ +/* + * 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.jtt.loop; + +import org.junit.*; + +public class Loop15 { + + public static int test(int arg) { + Object o = null; + int result = 10; + for (int k = 0; k < arg; ++k) { + if (o == null) { + o = new Object(); + } + if (k >= 5) { + break; + } + result++; + } + return result + (o == null ? 0 : 1); + } + + @Test + public void run0() throws Throwable { + Assert.assertEquals(16, test(5)); + } + + @Test + public void run1() throws Throwable { + Assert.assertEquals(10, test(0)); + } + + @Test + public void run2() throws Throwable { + Assert.assertEquals(12, test(1)); + } + + @Test + public void run3() throws Throwable { + Assert.assertEquals(16, test(10)); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/Loop16.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,63 @@ +/* + * Copyright (c) 2007, 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. + */ +// Checkstyle: stop +package com.oracle.graal.jtt.loop; + +import org.junit.*; + +/* + * Tests exiting 2 loops at the same time with escape-analysed values flowing out of loops + */ +public class Loop16 { + + public int a; + public int b; + public int c; + + public static int test(int count) { + return new Loop16().run(count); + } + + public int run(int count) { + l1: for (int i = 0; i <= count; i++) { + if (i > 5) { + for (int j = 0; j < i; j++) { + a += i; + if (a > 500) { + break l1; + } + } + } else if (i > 7) { + b += i; + } else { + c += i; + } + } + return a + b + c; + } + + @Test + public void run0() throws Throwable { + Assert.assertEquals(526, test(40)); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/Loop17.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2007, 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. + */ +// Checkstyle: stop +package com.oracle.graal.jtt.loop; + +import org.junit.*; + +/* + * Test around an object that escapes directly from inside a loop (no virtual phi on the loop) + */ +public class Loop17 { + + private static class L { + public int a; + public int b; + public int c; + public L(int a, int b, int c) { + this.a = a; + this.b = b; + this.c = c; + } + } + + + public static int test(int count) { + int i = 0; + L l; + do { + l = new L(i, i+1, i+2); + } while (++i < count); + + return l.a + l.b * 10 + l.c * 100; + } + + @Test + public void run0() throws Throwable { + Assert.assertEquals(543, test(new L(4,4,4).a)); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/LoopLastIndexOf.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,100 @@ +/* + * Copyright (c) 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.jtt.loop; + +import org.junit.*; + +/* + * see java.lang.String.lastIndexOf(char[], int, int, char[], int ,int, int) + */ +public class LoopLastIndexOf { + + private final char[] v1 = new char[]{'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'}; + private final char[] v2 = new char[]{'d', 'a'}; + private final char[] v3 = new char[]{'d', 'b', 'c'}; + private final char[] v4 = new char[]{'z', 'a', 'b', 'c'}; + + public static int test(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) { + int rightIndex = sourceCount - targetCount; + if (fromIndex < 0) { + return -1; + } + if (fromIndex > rightIndex) { + fromIndex = rightIndex; + } + /* Empty string always matches. */ + if (targetCount == 0) { + return fromIndex; + } + + int strLastIndex = targetOffset + targetCount - 1; + char strLastChar = target[strLastIndex]; + int min = sourceOffset + targetCount - 1; + int i = min + fromIndex; + + startSearchForLastChar: while (true) { + while (i >= min && source[i] != strLastChar) { + i--; + } + if (i < min) { + return -1; + } + int j = i - 1; + int start = j - (targetCount - 1); + int k = strLastIndex - 1; + + while (j > start) { + if (source[j--] != target[k--]) { + i--; + continue startSearchForLastChar; + } + } + return start - sourceOffset + 1; + } + } + + @Test + public void run0() throws Throwable { + Assert.assertEquals(7, test(v1, 0, v1.length, v2, 0, v2.length, 10)); + } + + @Test + public void run1() throws Throwable { + Assert.assertEquals(-1, test(v1, 0, v1.length, v3, 0, v3.length, 10)); + } + + @Test + public void run2() throws Throwable { + Assert.assertEquals(-1, test(v1, 0, v1.length, v4, 0, v4.length, 10)); + } + + @Test + public void run3() throws Throwable { + Assert.assertEquals(-1, test(v1, 1, v1.length - 1, v3, 0, v3.length, 10)); + } + + @Test(expected = ArrayIndexOutOfBoundsException.class) + public void run4() throws Throwable { + Assert.assertEquals(-1, test(v1, 1, v1.length, v3, 0, v3.length, 10)); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/loop/LoopParseLong.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,86 @@ +/* + * Copyright (c) 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.jtt.loop; + +import org.junit.*; + +public class LoopParseLong { + + public static long test(String s, int radix) throws NumberFormatException { + if (s == null) { + throw new NumberFormatException("null"); + } + if (radix < Character.MIN_RADIX) { + throw new NumberFormatException("radix " + radix + " less than Character.MIN_RADIX"); + } + if (radix > Character.MAX_RADIX) { + throw new NumberFormatException("radix " + radix + " greater than Character.MAX_RADIX"); + } + long result = 0; + boolean negative = false; + int i = 0; + int len = s.length(); + long limit = -Long.MAX_VALUE; + long multmin; + int digit; + if (len > 0) { + char firstChar = s.charAt(0); + if (firstChar < '0') { + if (firstChar == '-') { + negative = true; + limit = Long.MIN_VALUE; + } else if (firstChar != '+') { + throw new NumberFormatException(); + } + if (len == 1) { + throw new NumberFormatException(); + } + i++; + } + multmin = limit / radix; + while (i < len) { + digit = Character.digit(s.charAt(i++), radix); + if (digit < 0) { + throw new NumberFormatException(); + } + if (result < multmin) { + throw new NumberFormatException(); + } + result *= radix; + if (result < limit + digit) { + throw new NumberFormatException(); + } + result -= digit; + } + } else { + throw new NumberFormatException(); + } + return negative ? result : -result; + } + + @Test + public void run0() throws Throwable { + Assert.assertEquals(Character.digit('7', 10), test("7", 10)); + Assert.assertEquals(-100, test("-100", 10)); + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/CFGVerifier.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/CFGVerifier.java Tue Apr 10 12:22:46 2012 +0200 @@ -46,7 +46,7 @@ assert dominated.getDominator() == block; } - assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().header == block; + assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().header == block : block.beginNode; } if (cfg.getLoops() != null) { @@ -58,8 +58,16 @@ Loop blockLoop = block.getLoop(); while (blockLoop != loop) { + assert blockLoop != null; blockLoop = blockLoop.parent; - assert blockLoop != null; + } + + if (!(block.isLoopHeader() && block.getLoop() == loop)) { + for (Block pred : block.getPredecessors()) { + if (!loop.blocks.contains(pred)) { + return false; + } + } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Tue Apr 10 12:22:46 2012 +0200 @@ -24,6 +24,7 @@ import java.util.*; +import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; @@ -201,26 +202,51 @@ Loop loop = new Loop(block.getLoop(), loopsList.size(), block); loopsList.add(loop); - for (LoopEndNode end : ((LoopBeginNode) beginNode).loopEnds()) { + LoopBeginNode loopBegin = (LoopBeginNode) beginNode; + for (LoopEndNode end : loopBegin.loopEnds()) { Block endBlock = nodeToBlock.get(end); computeLoopBlocks(endBlock, loop); } + + for (LoopExitNode exit : loopBegin.loopExits()) { + Block exitBlock = nodeToBlock.get(exit); + List<Block> predecessors = exitBlock.getPredecessors(); + assert predecessors.size() == 1; + computeLoopBlocks(predecessors.get(0), loop); + loop.exits.add(exitBlock); + } + List<Block> unexpected = new LinkedList<>(); + for (Block b : loop.blocks) { + for (Block sux : b.getSuccessors()) { + if (sux.loop != loop) { + BeginNode begin = sux.getBeginNode(); + if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) { + Debug.log("Unexpected loop exit with %s, including whole branch in the loop", sux); + unexpected.add(sux); + } + } + } + } + for (Block b : unexpected) { + addBranchToLoop(loop, b); + } } } loops = loopsList.toArray(new Loop[loopsList.size()]); + } - for (Loop loop : loops) { - for (Block block : loop.blocks) { - for (Block sux : block.getSuccessors()) { - if (sux.getLoopDepth() < loop.depth) { - loop.exits.add(sux); - } - } - } + private static void addBranchToLoop(Loop l, Block b) { + if (l.blocks.contains(b)) { + return; + } + l.blocks.add(b); + b.loop = l; + for (Block sux : b.getSuccessors()) { + addBranchToLoop(l, sux); } } - private void computeLoopBlocks(Block block, Loop loop) { + private static void computeLoopBlocks(Block block, Loop loop) { if (block.getLoop() == loop) { return; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Loop.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Loop.java Tue Apr 10 12:22:46 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 Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.graal.nodes; +import static com.oracle.graal.graph.iterators.NodePredicates.*; + import java.util.*; import com.oracle.graal.graph.*; @@ -59,28 +61,45 @@ // This begin node is necessary. } else { // This begin node can be removed and all guards moved up to the preceding begin node. - if (!usages().isEmpty()) { - Node prevBegin = prev; - while (!(prevBegin instanceof BeginNode)) { - prevBegin = prevBegin.predecessor(); - } - for (Node usage : usages()) { - tool.addToWorkList(usage); - } - replaceAtUsages(prevBegin); - } + prepareDelete(); ((StructuredGraph) graph()).removeFixed(this); } } - public void evacuateGuards() { + public static BeginNode prevBegin(FixedNode from) { + Node prevBegin = from; + while (prevBegin != null) { + if (prevBegin instanceof BeginNode) { + return (BeginNode) prevBegin; + } + prevBegin = prevBegin.predecessor(); + } + return null; + } + + public void evacuateGuards(FixedNode evacuateFrom) { if (!usages().isEmpty()) { - Node prevBegin = predecessor(); + BeginNode prevBegin = prevBegin(evacuateFrom); assert prevBegin != null; - while (!(prevBegin instanceof BeginNode)) { - prevBegin = prevBegin.predecessor(); + for (Node anchored : anchored().snapshot()) { + anchored.replaceFirstInput(this, prevBegin); } - replaceAtUsages(prevBegin); + } + } + + public void prepareDelete() { + prepareDelete((FixedNode) predecessor()); + } + + public void prepareDelete(FixedNode evacuateFrom) { + removeProxies(); + evacuateGuards(evacuateFrom); + } + + public void removeProxies() { + StructuredGraph graph = (StructuredGraph) graph(); + for (ValueProxyNode vpn : proxies().snapshot()) { + graph.replaceFloating(vpn, vpn.value()); } } @@ -98,4 +117,53 @@ public NodeIterable<GuardNode> guards() { return usages().filter(GuardNode.class); } + + public NodeIterable<Node> anchored() { + return usages().filter(isNotA(ValueProxyNode.class)); + } + + 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/FixedNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -53,4 +53,9 @@ return properties; } + @Override + public boolean verify() { + assertTrue(this.successors().isNotEmpty() || this.predecessor() != null, "FixedNode should not float"); + return super.verify(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Tue Apr 10 12:22:46 2012 +0200 @@ -161,7 +161,7 @@ } public void addVirtualObjectMapping(Node virtualObject) { - assert virtualObject instanceof VirtualObjectFieldNode || virtualObject instanceof PhiNode : virtualObject; + assert virtualObject instanceof VirtualObjectFieldNode || virtualObject instanceof PhiNode || virtualObject instanceof ValueProxyNode : virtualObject; virtualObjectMappings.add(virtualObject); } @@ -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);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -161,14 +161,16 @@ EndNode falseEnd = (EndNode) falseSuccessor.next(); assert trueEnd.merge() == falseEnd.merge(); + FixedWithNextNode pred = (FixedWithNextNode) predecessor(); MergeNode merge = trueEnd.merge(); + merge.prepareDelete(pred); assert merge.usages().isEmpty(); FixedNode next = merge.next(); merge.setNext(null); setTrueSuccessor(null); setFalseSuccessor(null); - ((FixedWithNextNode) predecessor()).setNext(next); + pred.setNext(next); safeDelete(); trueSuccessor.safeDelete(); falseSuccessor.safeDelete();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.graal.nodes; +import static com.oracle.graal.graph.iterators.NodePredicates.*; + import java.util.*; import com.oracle.graal.graph.*; @@ -49,8 +51,17 @@ return usages().filter(LoopEndNode.class); } + public NodeIterable<LoopExitNode> loopExits() { + return usages().filter(LoopExitNode.class); + } + + @Override + public NodeIterable<Node> anchored() { + return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class)); + } + public List<LoopEndNode> orderedLoopEnds() { - List<LoopEndNode> snapshot = usages().filter(LoopEndNode.class).snapshot(); + List<LoopEndNode> snapshot = loopEnds().snapshot(); Collections.sort(snapshot, new Comparator<LoopEndNode>() { @Override public int compare(LoopEndNode o1, LoopEndNode o2) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopExitNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,42 @@ +/* + * Copyright (c) 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.nodes; + +import com.oracle.graal.nodes.spi.*; + +public class LoopExitNode extends BeginNode { + @Input(notDataflow = true) private LoopBeginNode loopBegin; + public LoopExitNode(LoopBeginNode loop) { + assert loop != null; + loopBegin = loop; + } + + public LoopBeginNode loopBegin() { + return loopBegin; + } + + @Override + public void simplify(SimplifierTool tool) { + // + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -28,6 +28,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.util.*; /** * Denotes the merging of multiple control-flow paths. @@ -115,12 +116,22 @@ } public NodeIterable<PhiNode> phis() { - return this.usages().filter(new NodePredicate() { + return this.usages().filter(PhiNode.class).filter(new NodePredicate() { @Override public boolean apply(Node n) { - return n instanceof PhiNode && ((PhiNode) n).merge() == MergeNode.this; + return ((PhiNode) n).merge() == MergeNode.this; } - }).filter(PhiNode.class); + }); + } + + @Override + public NodeIterable<Node> anchored() { + return super.anchored().filter(isNotA(PhiNode.class).or(new NodePredicate() { + @Override + public boolean apply(Node n) { + return ((PhiNode) n).merge() != MergeNode.this; + } + })); } @Override @@ -136,7 +147,9 @@ } } } - Debug.log("Split %s into loop ends for %s", this, begin); + FixedNode evacuateAnchoredTo = new ComputeImmediateDominator(this).compute(); + Debug.log("Split %s into loop ends for %s. Evacuate to %s", this, begin, evacuateAnchoredTo); + this.prepareDelete(evacuateAnchoredTo); int numEnds = this.forwardEndCount(); StructuredGraph graph = (StructuredGraph) graph(); for (int i = 0; i < numEnds - 1; i++) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -33,22 +33,15 @@ * and a variable. */ public final class PhiNode extends FloatingNode implements Canonicalizable, Node.IterableNodeType { - - @Input(notDataflow = true) private MergeNode merge; - - @Input private final NodeInputList<ValueNode> values = new NodeInputList<>(this); - - public MergeNode merge() { - return merge; - } - public static enum PhiType { Value, // normal value phis Memory, // memory phis Virtual // phis used for VirtualObjectField merges } - private final PhiType type; + @Input(notDataflow = true) private MergeNode merge; + @Input private final NodeInputList<ValueNode> values = new NodeInputList<>(this); + @Data private final PhiType type; public PhiNode(CiKind kind, MergeNode merge, PhiType type) { super(StampFactory.forKind(kind)); @@ -60,6 +53,10 @@ return type; } + public MergeNode merge() { + return merge; + } + public NodeInputList<ValueNode> values() { return values; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Tue Apr 10 12:22:46 2012 +0200 @@ -168,6 +168,9 @@ public void removeFixed(FixedWithNextNode node) { assert node != null; + if (node instanceof BeginNode) { + ((BeginNode) node).prepareDelete(); + } assert node.usages().isEmpty() : node + " " + node.usages(); FixedNode next = node.next(); node.setNext(null); @@ -208,15 +211,11 @@ assert node.usages().isEmpty(); assert survivingSuccessor >= 0 && survivingSuccessor < node.blockSuccessorCount() : "invalid surviving successor " + survivingSuccessor + " for " + node; BeginNode begin = node.blockSuccessor(survivingSuccessor); - begin.evacuateGuards(); - FixedNode next = begin.next(); - begin.setNext(null); for (int i = 0; i < node.blockSuccessorCount(); i++) { node.setBlockSuccessor(i, null); } - node.replaceAtPredecessors(next); + node.replaceAtPredecessors(begin); node.safeDelete(); - begin.safeDelete(); } public void removeSplitPropagate(ControlSplitNode node, int survivingSuccessor) { @@ -224,9 +223,6 @@ assert node.usages().isEmpty(); assert survivingSuccessor >= 0 && survivingSuccessor < node.blockSuccessorCount() : "invalid surviving successor " + survivingSuccessor + " for " + node; BeginNode begin = node.blockSuccessor(survivingSuccessor); - begin.evacuateGuards(); - FixedNode next = begin.next(); - begin.setNext(null); for (int i = 0; i < node.blockSuccessorCount(); i++) { BeginNode successor = node.blockSuccessor(i); node.setBlockSuccessor(i, null); @@ -234,10 +230,9 @@ GraphUtil.killCFG(successor); } } - if (next.isAlive()) { - node.replaceAtPredecessors(next); + if (begin.isAlive()) { + node.replaceAtPredecessors(begin); node.safeDelete(); - begin.safeDelete(); } else { assert node.isDeleted(); } @@ -257,31 +252,23 @@ assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement; assert survivingSuccessor >= 0 && survivingSuccessor < node.blockSuccessorCount() : "invalid surviving successor " + survivingSuccessor + " for " + node; BeginNode begin = node.blockSuccessor(survivingSuccessor); - begin.evacuateGuards(); - FixedNode next = begin.next(); - begin.setNext(null); for (int i = 0; i < node.blockSuccessorCount(); i++) { node.setBlockSuccessor(i, null); } - replacement.setNext(next); + replacement.setNext(begin); node.replaceAndDelete(replacement); - begin.safeDelete(); } public void replaceSplitWithFloating(ControlSplitNode node, FloatingNode replacement, int survivingSuccessor) { assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement; assert survivingSuccessor >= 0 && survivingSuccessor < node.blockSuccessorCount() : "invalid surviving successor " + survivingSuccessor + " for " + node; BeginNode begin = node.blockSuccessor(survivingSuccessor); - begin.evacuateGuards(); - FixedNode next = begin.next(); - begin.setNext(null); for (int i = 0; i < node.blockSuccessorCount(); i++) { node.setBlockSuccessor(i, null); } - node.replaceAtPredecessors(next); + node.replaceAtPredecessors(begin); node.replaceAtUsages(replacement); node.safeDelete(); - begin.safeDelete(); } public void addAfterFixed(FixedWithNextNode node, FixedWithNextNode newNode) { @@ -325,14 +312,15 @@ EndNode singleEnd = merge.forwardEndAt(0); FixedNode sux = merge.next(); FrameState stateAfter = merge.stateAfter(); + // remove loop exits + if (merge instanceof LoopBeginNode) { + for (LoopExitNode exit : ((LoopBeginNode) merge).loopExits().snapshot()) { + exit.removeProxies(); + replaceFixedWithFixed(exit, this.add(new BeginNode())); + } + } // evacuateGuards - Node prevBegin = singleEnd.predecessor(); - assert prevBegin != null; - while (!(prevBegin instanceof BeginNode)) { - prevBegin = prevBegin.predecessor(); - } - merge.replaceAtUsages(prevBegin); - + merge.prepareDelete((FixedNode) singleEnd.predecessor()); merge.safeDelete(); if (stateAfter != null && stateAfter.usages().isEmpty()) { stateAfter.safeDelete();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -0,0 +1,63 @@ +/* + * Copyright (c) 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.nodes; + +import com.oracle.graal.graph.Node; +import com.oracle.graal.graph.Node.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.calc.*; + + + +public class ValueProxyNode extends FloatingNode implements Node.IterableNodeType, ValueNumberable { + @Input(notDataflow = true) private BeginNode proxyPoint; + @Input private ValueNode value; + @Data private final PhiType type; + + public ValueProxyNode(ValueNode value, BeginNode exit, PhiType type) { + super(value.stamp()); + this.type = type; + assert exit != null; + this.proxyPoint = exit; + this.value = value; + } + + public ValueNode value() { + return value; + } + + public BeginNode proxyPoint() { + return proxyPoint; + } + + public PhiType type() { + return type; + } + + @Override + public boolean verify() { + assert value != null; + assert proxyPoint != null; + return super.verify(); + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -52,7 +52,7 @@ return x(); } if (c == 0) { - return ConstantNode.forInt(0, graph()); + return ConstantNode.defaultForKind(kind(), graph()); } if (c > 0 && CiUtil.isPowerOf2(c)) { return graph().unique(new LeftShiftNode(kind(), x(), ConstantNode.forInt(CiUtil.log2(c), graph())));
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessIndexedNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/AccessIndexedNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -36,6 +36,8 @@ @Input private ValueNode index; @Input private ValueNode length; + @Data private final CiKind elementType; + private final long leafGraphId; public ValueNode index() { return index; @@ -45,9 +47,6 @@ return length; } - private final CiKind elementType; - private final long leafGraphId; - /** * Create an new AccessIndexedNode. * @param kind the result kind of the access
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -39,7 +39,7 @@ */ public final class CheckCastNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType, TypeFeedbackProvider, TypeCanonicalizable { - @Input protected final FixedNode anchor; + @Input(notDataflow = true) protected final FixedNode anchor; @Data protected final boolean emitCode; public FixedNode anchor() {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewArrayNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewArrayNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -32,6 +32,7 @@ import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.util.*; /** * The {@code NewArrayNode} class is the base of all instructions that allocate arrays. @@ -130,7 +131,7 @@ public int updateState(Node node, Node current, Map<Object, Integer> fieldIndex, ValueNode[] fieldState) { if (current instanceof AccessIndexedNode) { AccessIndexedNode x = (AccessIndexedNode) current; - if (x.array() == node) { + if (GraphUtil.unProxify(x.array()) == node) { int index = ((AccessIndexedNode) current).index().asConstant().asInt(); if (current instanceof LoadIndexedNode) { x.replaceAtUsages(fieldState[index]);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewInstanceNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewInstanceNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -29,6 +29,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.util.*; /** * The {@code NewInstanceNode} represents the allocation of an instance class object. @@ -110,7 +111,7 @@ public int updateState(Node node, Node current, Map<Object, Integer> fieldIndex, ValueNode[] fieldState) { if (current instanceof AccessFieldNode) { AccessFieldNode x = (AccessFieldNode) current; - if (x.object() == node) { + if (GraphUtil.unProxify(x.object()) == node) { int field = fieldIndex.get(x.field()); StructuredGraph graph = (StructuredGraph) x.graph(); if (current instanceof LoadFieldNode) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/EscapeOp.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/EscapeOp.java Tue Apr 10 12:22:46 2012 +0200 @@ -81,6 +81,13 @@ } else if (usage instanceof ArrayLengthNode) { assert ((ArrayLengthNode) usage).array() == node; return false; + } else if (usage instanceof ValueProxyNode) { + for (Node vpnUsage : usage.usages().snapshot()) { + if (escape(usage, vpnUsage)) { + return true; + } + } + return false; } else { return true; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Tue Apr 10 12:22:46 2012 +0200 @@ -27,8 +27,10 @@ import java.util.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.virtual.*; public class GraphUtil { @@ -40,7 +42,11 @@ killEnd(end); } else { // Normal control flow node. - for (Node successor : node.successors().snapshot()) { + /* We do not take a successor snapshot because this iterator supports concurrent modifications + * as long as they do not change the size of the successor list. Not tasking a snapshot allows + * us to see modifications to other branches that may happen while processing one branch. + */ + for (Node successor : node.successors()) { killCFG((FixedNode) successor); } } @@ -50,28 +56,39 @@ private static void killEnd(EndNode end) { MergeNode merge = end.merge(); merge.removeEnd(end); + StructuredGraph graph = (StructuredGraph) end.graph(); if (merge instanceof LoopBeginNode && merge.forwardEndCount() == 0) { //dead loop for (PhiNode phi : merge.phis().snapshot()) { propagateKill(phi); } LoopBeginNode begin = (LoopBeginNode) merge; - // disconnect and delete loop ends + // disconnect and delete loop ends & loop exits for (LoopEndNode loopend : begin.loopEnds().snapshot()) { loopend.predecessor().replaceFirstSuccessor(loopend, null); loopend.safeDelete(); } + for (LoopExitNode loopexit : begin.loopExits().snapshot()) { + for (ValueProxyNode vpn : loopexit.proxies().snapshot()) { + graph.replaceFloating(vpn, vpn.value()); + } + graph.replaceFixedWithFixed(loopexit, graph.add(new BeginNode())); + } killCFG(begin.next()); begin.safeDelete(); } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().isEmpty()) { // not a loop anymore - ((StructuredGraph) end.graph()).reduceDegenerateLoopBegin((LoopBeginNode) merge); + graph.reduceDegenerateLoopBegin((LoopBeginNode) merge); } else if (merge.phiPredecessorCount() == 1) { // not a merge anymore - ((StructuredGraph) end.graph()).reduceTrivialMerge(merge); + graph.reduceTrivialMerge(merge); } } + public static NodePredicate isFloatingNode() { + return isA(FloatingNode.class).or(CallTargetNode.class).or(FrameState.class).or(VirtualObjectFieldNode.class).or(VirtualObjectNode.class); + } + public static void propagateKill(Node node) { if (node != null && node.isAlive()) { - List<Node> usagesSnapshot = node.usages().filter(isA(FloatingNode.class).or(CallTargetNode.class).or(FrameState.class)).snapshot(); + List<Node> usagesSnapshot = node.usages().filter(isFloatingNode()).snapshot(); // null out remaining usages node.replaceAtUsages(null); @@ -91,7 +108,7 @@ } public static void killUnusedFloatingInputs(Node node) { - List<Node> floatingInputs = node.inputs().filter(isA(FloatingNode.class).or(CallTargetNode.class).or(FrameState.class)).snapshot(); + List<Node> floatingInputs = node.inputs().filter(isFloatingNode()).snapshot(); node.safeDelete(); for (Node in : floatingInputs) { @@ -100,4 +117,70 @@ } } } + + public static void checkRedundantPhi(PhiNode phiNode) { + if (phiNode.isDeleted() || phiNode.valueCount() == 1) { + return; + } + + ValueNode singleValue = phiNode.singleValue(); + if (singleValue != null) { + Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot(); + Collection<ValueProxyNode> proxyUsages = phiNode.usages().filter(ValueProxyNode.class).snapshot(); + ((StructuredGraph) phiNode.graph()).replaceFloating(phiNode, singleValue); + for (PhiNode phi : phiUsages) { + checkRedundantPhi(phi); + } + for (ValueProxyNode proxy : proxyUsages) { + checkRedundantProxy(proxy); + } + } + } + + public static void checkRedundantProxy(ValueProxyNode vpn) { + BeginNode proxyPoint = vpn.proxyPoint(); + if (proxyPoint instanceof LoopExitNode) { + LoopExitNode exit = (LoopExitNode) proxyPoint; + LoopBeginNode loopBegin = exit.loopBegin(); + ValueNode vpnValue = vpn.value(); + for (ValueNode v : loopBegin.stateAfter().values()) { + ValueNode v2 = v; + if (loopBegin.isPhiAtMerge(v2)) { + v2 = ((PhiNode) v2).valueAt(loopBegin.forwardEnd()); + } + if (vpnValue == v2) { + Collection<PhiNode> phiUsages = vpn.usages().filter(PhiNode.class).snapshot(); + Collection<ValueProxyNode> proxyUsages = vpn.usages().filter(ValueProxyNode.class).snapshot(); + ((StructuredGraph) vpn.graph()).replaceFloating(vpn, vpnValue); + for (PhiNode phi : phiUsages) { + checkRedundantPhi(phi); + } + for (ValueProxyNode proxy : proxyUsages) { + checkRedundantProxy(proxy); + } + return; + } + } + } + } + + public static void normalizeLoopBegin(LoopBeginNode begin) { + // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either the same or the phi itself. + for (PhiNode phi : begin.phis().snapshot()) { + GraphUtil.checkRedundantPhi(phi); + } + for (LoopExitNode exit : begin.loopExits()) { + for (ValueProxyNode vpn : exit.proxies().snapshot()) { + GraphUtil.checkRedundantProxy(vpn); + } + } + } + + public static ValueNode unProxify(ValueNode proxy) { + ValueNode v = proxy; + while (v instanceof ValueProxyNode) { + v = ((ValueProxyNode) v).value(); + } + return v; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectFieldNode.java Sun Apr 08 00:09:10 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectFieldNode.java Tue Apr 10 12:22:46 2012 +0200 @@ -66,6 +66,13 @@ } @Override + public boolean verify() { + assertTrue(object != null, "No object"); + assertTrue(input != null, "No input"); + return super.verify(); + } + + @Override public Map<Object, Object> getDebugProperties() { Map<Object, Object> properties = super.getDebugProperties(); properties.put("index", index); @@ -74,7 +81,7 @@ @Override public String toString(Verbosity verbosity) { - if (verbosity == Verbosity.Name && object().fields() != null) { + if (verbosity == Verbosity.Name && object() != null && object().fields() != null) { return super.toString(Verbosity.Name) + " " + object().fields()[index].name(); } else { return super.toString(verbosity);