Mercurial > hg > truffle
changeset 5210:e3e7542d78b7
Loop-closed form GraphBuidling
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Apr 09 19:15:41 2012 +0200 @@ -170,6 +170,10 @@ if (GraalOptions.OptLoops) { 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); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/EscapeAnalysisPhase.java Mon Apr 09 19:15:41 2012 +0200 @@ -188,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) { @@ -197,6 +202,12 @@ 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) { ValueNode v = state.virtualObjectField;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/RemoveValueProxyPhase.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/SnippetIntrinsificationPhase.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Mon Apr 09 19:15:41 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.java/src/com/oracle/graal/java/BciBlockMapping.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Mon Apr 09 19:15:41 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); } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java Mon Apr 09 19:15:41 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.nodes/src/com/oracle/graal/nodes/BeginNode.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Mon Apr 09 19:15:41 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.*; @@ -91,9 +93,17 @@ } 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()); + } + } + @Override public boolean verify() { assertTrue(predecessor() != null || this == ((StructuredGraph) graph()).start() || this instanceof MergeNode, "begin nodes must be connected"); @@ -110,6 +120,10 @@ } public NodeIterable<Node> anchored() { - return usages(); + return usages().filter(isNotA(ValueProxyNode.class)); + } + + public NodeIterable<ValueProxyNode> proxies() { + return usages().filter(ValueProxyNode.class); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java Mon Apr 09 19:15:41 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); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Mon Apr 09 19:15:41 2012 +0200 @@ -51,9 +51,13 @@ 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)); + return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class)); } public List<LoopEndNode> orderedLoopEnds() {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopExitNode.java Mon Apr 09 19:15:41 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/StructuredGraph.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Mon Apr 09 19:15:41 2012 +0200 @@ -312,6 +312,13 @@ 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 merge.prepareDelete((FixedNode) singleEnd.predecessor()); merge.safeDelete();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java Mon Apr 09 19:15:41 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/java/NewArrayNode.java Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewArrayNode.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/NewInstanceNode.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/EscapeOp.java Mon Apr 09 19:15:41 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 Fri Apr 06 17:58:00 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java Mon Apr 09 19:15:41 2012 +0200 @@ -62,11 +62,17 @@ 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 @@ -111,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; + } }