Mercurial > hg > truffle
changeset 4614:a3882fd1ae61
Make it possible to have multiple LoopEnds per LoopBegin
Factor out the 2 versions of KillCFG (GraphUitl/Canonicalizer)
Remove unused loop detection code from FloatingReadPhase
Made InvokeNode's toString/getDebugProperties more robust
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ComputeLinearScanOrder.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/ComputeLinearScanOrder.java Thu Feb 16 11:57:38 2012 +0100 @@ -29,6 +29,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.lir.cfg.*; +import com.oracle.max.graal.nodes.*; public final class ComputeLinearScanOrder { @@ -261,18 +262,19 @@ if (cur.isLoopEnd() && cur.isLoopHeader()) { codeEmittingOrder.add(cur); } else { - if (!cur.isLoopHeader() || !GraalOptions.OptReorderLoops) { + if (!cur.isLoopHeader() || ((LoopBeginNode) cur.getBeginNode()).loopEnds().count() > 1 || !GraalOptions.OptReorderLoops) { codeEmittingOrder.add(cur); if (cur.isLoopEnd() && GraalOptions.OptReorderLoops) { Block loopHeader = loopHeaders[cur.getLoop().index]; - assert loopHeader != null; - codeEmittingOrder.add(loopHeader); + if (loopHeader != null) { + codeEmittingOrder.add(loopHeader); - for (int i = 0; i < loopHeader.numberOfSux(); i++) { - Block succ = loopHeader.suxAt(i); - if (succ.getLoopDepth() == loopHeader.getLoopDepth()) { - succ.align = true; + for (int i = 0; i < loopHeader.numberOfSux(); i++) { + Block succ = loopHeader.suxAt(i); + if (succ.getLoopDepth() == loopHeader.getLoopDepth()) { + succ.align = true; + } } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Thu Feb 16 11:57:38 2012 +0100 @@ -682,12 +682,11 @@ if (GraalOptions.GenLoopSafepoints && x.hasSafepointPolling()) { emitSafepointPoll(x); } - moveToPhi(x.loopBegin(), x); } private ArrayList<CiValue> phiValues = new ArrayList<>(); - private void moveToPhi(MergeNode merge, FixedNode pred) { + private void moveToPhi(MergeNode merge, EndNode pred) { if (GraalOptions.AllocSSA) { assert phiValues.isEmpty(); for (PhiNode phi : merge.phis()) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/MergeableState.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/MergeableState.java Thu Feb 16 11:57:38 2012 +0100 @@ -30,6 +30,6 @@ T clone(); boolean merge(MergeNode merge, Collection<T> withStates); void loopBegin(LoopBeginNode loopBegin); - void loopEnd(LoopEndNode loopEnd, T loopEndState); + void loopEnds(LoopBeginNode loopBegin, Collection<T> loopEndStates); void afterSplit(FixedNode node); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/PostOrderNodeIterator.java Thu Feb 16 11:57:38 2012 +0100 @@ -60,11 +60,8 @@ current = ((LoopBeginNode) current).next(); assert current != null; } else if (current instanceof LoopEndNode) { - T loopBeginState = nodeStates.get(((LoopEndNode) current).loopBegin()); - if (loopBeginState != null) { - loopBeginState.loopEnd((LoopEndNode) current, state); - } loopEnd((LoopEndNode) current); + finishLoopEnds((LoopEndNode) current); current = nextQueuedNode(); } else if (current instanceof MergeNode) { merge((MergeNode) current); @@ -122,10 +119,10 @@ FixedNode node = nodeQueue.removeFirst(); if (node instanceof MergeNode) { MergeNode merge = (MergeNode) node; - state = nodeStates.get(merge.endAt(0)).clone(); - ArrayList<T> states = new ArrayList<>(merge.endCount() - 1); - for (int i = 1; i < merge.endCount(); i++) { - T other = nodeStates.get(merge.endAt(i)); + state = nodeStates.get(merge.forwardEndAt(0)).clone(); + ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1); + for (int i = 1; i < merge.forwardEndCount(); i++) { + T other = nodeStates.get(merge.forwardEndAt(i)); assert other != null; states.add(other); } @@ -145,6 +142,31 @@ return null; } + private void finishLoopEnds(LoopEndNode end) { + assert !visitedEnds.isMarked(end); + assert !nodeStates.containsKey(end); + nodeStates.put(end, state); + visitedEnds.mark(end); + LoopBeginNode begin = end.loopBegin(); + boolean endsVisited = true; + for (LoopEndNode le : begin.loopEnds()) { + if (!visitedEnds.isMarked(le)) { + endsVisited = false; + break; + } + } + if (endsVisited) { + ArrayList<T> states = new ArrayList<>(begin.loopEnds().count()); + for (LoopEndNode le : begin.orderedLoopEnds()) { + states.add(nodeStates.get(le)); + } + T loopBeginState = nodeStates.get(begin); + if (loopBeginState != null) { + loopBeginState.loopEnds(begin, states); + } + } + } + private void queueMerge(EndNode end) { assert !visitedEnds.isMarked(end); assert !nodeStates.containsKey(end); @@ -152,8 +174,8 @@ visitedEnds.mark(end); MergeNode merge = end.merge(); boolean endsVisited = true; - for (int i = 0; i < merge.endCount(); i++) { - if (!visitedEnds.isMarked(merge.endAt(i))) { + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { endsVisited = false; break; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -22,8 +22,6 @@ */ package com.oracle.max.graal.compiler.phases; -import static com.oracle.max.graal.graph.iterators.NodePredicates.*; - import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; import com.oracle.max.graal.debug.*; @@ -31,6 +29,7 @@ import com.oracle.max.graal.nodes.*; import com.oracle.max.graal.nodes.calc.*; import com.oracle.max.graal.nodes.spi.*; +import com.oracle.max.graal.nodes.util.*; public class CanonicalizerPhase extends Phase { private static final int MAX_ITERATION_PER_NODE = 10; @@ -62,6 +61,7 @@ } public static void canonicalize(StructuredGraph graph, NodeWorkList nodeWorkList, RiRuntime runtime, CiTarget target, CiAssumptions assumptions) { + graph.trackInputChange(nodeWorkList); Tool tool = new Tool(nodeWorkList, runtime, target, assumptions); for (Node node : nodeWorkList) { if (node instanceof Canonicalizable) { @@ -113,36 +113,23 @@ } } } - - for (Node newNode : graph.getNewNodes()) { - nodeWorkList.add(newNode); - } - if (canonical != null) { - nodeWorkList.replaced(canonical, node, false); - } + nodeWorkList.addAll(graph.getNewNodes()); } } else if (node instanceof Simplifiable) { ((Simplifiable) node).simplify(tool); } } - + graph.stopTrackingInputChange(); while (graph.getUsagesDroppedNodesCount() > 0) { for (Node n : graph.getAndCleanUsagesDroppedNodes()) { if (!n.isDeleted() && n.usages().size() == 0 && n instanceof FloatingNode) { - killFloating((FloatingNode) n); + n.clearInputs(); + n.safeDelete(); } } } } - - private static void killFloating(FloatingNode node) { - if (node.usages().size() == 0) { - node.clearInputs(); - node.safeDelete(); - } - } - private static final class Tool implements SimplifierTool { private final NodeWorkList nodeWorkList; @@ -160,89 +147,7 @@ @Override public void deleteBranch(FixedNode branch) { branch.predecessor().replaceFirstSuccessor(branch, null); - killCFG(branch); - } - - public void killCFG(FixedNode node) { - for (Node successor : node.successors()) { - if (successor != null) { - node.replaceFirstSuccessor(successor, null); - assert !node.isDeleted(); - killCFG((FixedNode) successor); - } - } - if (node instanceof LoopEndNode) { - LoopEndNode loopEnd = (LoopEndNode) node; - LoopBeginNode loopBegin = loopEnd.loopBegin(); - if (loopBegin != null) { - assert loopBegin.isAlive(); - assert loopBegin.endCount() == 1; - EndNode predEnd = loopBegin.endAt(0); - - for (PhiNode phi : loopBegin.phis().snapshot()) { - ValueNode value = phi.valueAt(0); - phi.replaceAndDelete(value); - nodeWorkList.replaced(value, phi, false); - } - FixedNode next = loopBegin.next(); - loopEnd.setLoopBegin(null); - loopBegin.safeDelete(); - - predEnd.replaceAndDelete(next); - } - } else if (node instanceof EndNode) { - EndNode end = (EndNode) node; - MergeNode merge = end.merge(); - if (merge instanceof LoopBeginNode) { - for (PhiNode phi : merge.phis().snapshot()) { - ValueNode value = phi.valueAt(0); - phi.replaceAndDelete(value); - nodeWorkList.replaced(value, phi, false); - } - if (((LoopBeginNode) merge).loopEnd() != null) { - ((LoopBeginNode) merge).loopEnd().setLoopBegin(null); - } - killCFG(merge); - } else { - merge.removeEnd(end); - if (merge.phiPredecessorCount() == 1) { - for (PhiNode phi : merge.phis().snapshot()) { - ValueNode value = phi.valueAt(0); - phi.replaceAndDelete(value); - nodeWorkList.replaced(value, phi, false); - } - Node replacedSux = merge.phiPredecessorAt(0); - Node pred = replacedSux.predecessor(); - assert replacedSux instanceof EndNode; - FixedNode next = merge.next(); - merge.setNext(null); - pred.replaceFirstSuccessor(replacedSux, next); - FrameState stateAfter = merge.stateAfter(); - merge.setStateAfter(null); - if (stateAfter != null && stateAfter.usages().isEmpty()) { - stateAfter.safeDelete(); - } - merge.safeDelete(); - replacedSux.safeDelete(); - } - } - } - killNonCFG(node, null); - } - - public void killNonCFG(Node node, Node input) { - if (node instanceof PhiNode) { - node.replaceFirstInput(input, null); - } else { - for (Node usage : node.usages().filter(isA(FloatingNode.class).or(CallTargetNode.class)).snapshot()) { - if (!usage.isDeleted()) { - killNonCFG(usage, node); - } - } - // null out remaining usages - node.replaceAtUsages(null); - node.safeDelete(); - } + GraphUtil.killCFG(branch); } /**
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -73,26 +73,32 @@ public static class LoopInfo { public final LoopBeginNode loopBegin; - public final Set<LoopInfo> requires = new HashSet<>(4); + public final NodeMap<Set<LoopInfo>> requires; private double loopFrequency = -1; public boolean ended = false; public LoopInfo(LoopBeginNode loopBegin) { this.loopBegin = loopBegin; + this.requires = loopBegin.graph().createNodeMap(); } public double loopFrequency() { if (loopFrequency == -1 && ended) { - double factor = 1; - for (LoopInfo required : requires) { - double t = required.loopFrequency(); - if (t == -1) { - return -1; + double backEdgeProb = 0.0; + for (LoopEndNode le : loopBegin.loopEnds()) { + double factor = 1; + Set<LoopInfo> requireds = requires.get(le); + for (LoopInfo required : requireds) { + double t = required.loopFrequency(); + if (t == -1) { + return -1; + } + factor *= t; } - factor *= t; + backEdgeProb += le.probability() * factor; } - double d = loopBegin.loopEnd().probability() * factor; + double d = backEdgeProb; if (d < EPSILON) { d = EPSILON; } else if (d > loopBegin.probability() - EPSILON) { @@ -128,7 +134,7 @@ @Override public boolean merge(MergeNode merge, Collection<Probability> withStates) { - if (merge.endCount() > 1) { + if (merge.forwardEndCount() > 1) { HashSet<LoopInfo> intersection = new HashSet<>(loops); for (Probability other : withStates) { intersection.retainAll(other.loops); @@ -170,11 +176,21 @@ } @Override - public void loopEnd(LoopEndNode loopEnd, Probability loopEndState) { + public void loopEnds(LoopBeginNode loopBegin, Collection<Probability> loopEndStates) { assert loopInfo != null; - for (LoopInfo innerLoop : loopEndState.loops) { - if (innerLoop != loopInfo && !loops.contains(innerLoop)) { - loopInfo.requires.add(innerLoop); + List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); + int i = 0; + for (Probability proba : loopEndStates) { + LoopEndNode loopEnd = loopEnds.get(i++); + Set<LoopInfo> requires = loopInfo.requires.get(loopEnd); + if (requires == null) { + requires = new HashSet<>(); + loopInfo.requires.set(loopEnd, requires); + } + for (LoopInfo innerLoop : proba.loops) { + if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) { + requires.add(innerLoop); + } } } loopInfo.ended = true; @@ -229,8 +245,8 @@ @Override public boolean merge(MergeNode merge, Collection<LoopCount> withStates) { - assert merge.endCount() == withStates.size() + 1; - if (merge.endCount() > 1) { + assert merge.forwardEndCount() == withStates.size() + 1; + if (merge.forwardEndCount() > 1) { Set<LoopInfo> loops = mergeLoops.get(merge); assert loops != null; double countProd = 1; @@ -248,7 +264,7 @@ } @Override - public void loopEnd(LoopEndNode loopEnd, LoopCount loopEndState) { + public void loopEnds(LoopBeginNode loopBegin, Collection<LoopCount> loopEndStates) { // nothing to do... }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -43,9 +43,9 @@ // remove chained Merges for (MergeNode merge : graph.getNodes(MergeNode.class)) { - if (merge.endCount() == 1 && !(merge instanceof LoopBeginNode)) { + if (merge.forwardEndCount() == 1 && !(merge instanceof LoopBeginNode)) { replacePhis(merge); - EndNode endNode = merge.endAt(0); + EndNode endNode = merge.forwardEndAt(0); FixedNode next = merge.next(); merge.safeDelete(); endNode.replaceAndDelete(next); @@ -76,21 +76,21 @@ } } } - for (LoopEndNode node : graph.getNodes(LoopEndNode.class)) { - if (!flood.isMarked(node)) { - LoopBeginNode loop = node.loopBegin(); - if (flood.isMarked(loop)) { + for (LoopBeginNode loop : graph.getNodes(LoopBeginNode.class)) { + if (flood.isMarked(loop)) { + boolean reachable = false; + for (LoopEndNode end : loop.loopEnds()) { + if (flood.isMarked(end)) { + reachable = true; + break; + } + } + if (!reachable) { Debug.log("Removing loop with unreachable end: %s", loop); - node.setLoopBegin(null); - EndNode endNode = loop.endAt(0); - assert endNode.predecessor() != null; - replacePhis(loop); - loop.removeEnd(endNode); - - FixedNode next = loop.next(); - loop.setNext(null); - endNode.replaceAndDelete(next); - loop.safeDelete(); + for (LoopEndNode end : loop.loopEnds().snapshot()) { + loop.removeEnd(end); + } + graph.reduceDegenerateLoopBegin(loop); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -189,15 +189,15 @@ } @Override - public void loopEnd(LoopEndNode x, BlockExitState loopEndState) { + public void loopEnds(LoopBeginNode loopBegin, Collection<BlockExitState> loopEndStates) { while (!(virtualObjectField instanceof PhiNode)) { virtualObjectField = ((VirtualObjectFieldNode) virtualObjectField).lastState(); } - ((PhiNode) virtualObjectField).addInput(loopEndState.virtualObjectField); - assert ((PhiNode) virtualObjectField).valueCount() == 2; - for (int i2 = 0; i2 < fieldState.length; i2++) { - ((PhiNode) fieldState[i2]).addInput(loopEndState.fieldState[i2]); - assert ((PhiNode) fieldState[i2]).valueCount() == 2; + for (BlockExitState loopEndState : loopEndStates) { + ((PhiNode) virtualObjectField).addInput(loopEndState.virtualObjectField); + for (int i2 = 0; i2 < fieldState.length; i2++) { + ((PhiNode) fieldState[i2]).addInput(loopEndState.fieldState[i2]); + } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/FloatingReadPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -57,10 +57,8 @@ for (Map.Entry<Object, Node> entry : loopEntryMap.entrySet()) { PhiNode phiNode = (PhiNode) entry.getValue(); - assert phiNode.valueCount() == 1; - + Object key = entry.getKey(); Node other; - Object key = entry.getKey(); if (otherMemoryMap.map.containsKey(key)) { other = otherMemoryMap.map.get(key); } else { @@ -113,7 +111,7 @@ PhiNode phi = (PhiNode) original; phi.addInput((ValueNode) newValue); Debug.log("Add new input to %s: %s.", original, newValue); - assert phi.valueCount() <= phi.merge().endCount() : phi.merge(); + assert phi.valueCount() <= phi.merge().forwardEndCount() : phi.merge(); } else { PhiNode phi = m.graph().unique(new PhiNode(CiKind.Illegal, m, PhiType.Memory)); for (int i = 0; i < mergeOperationCount + 1; ++i) { @@ -121,7 +119,7 @@ } phi.addInput((ValueNode) newValue); Debug.log("Creating new %s merge=%s newValue=%s location=%s.", phi, phi.merge(), newValue, location); - assert phi.valueCount() <= phi.merge().endCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().endCount() + "/" + mergeOperationCount; + assert phi.valueCount() <= phi.merge().forwardEndCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().forwardEndCount() + "/" + mergeOperationCount; assert m.usages().contains(phi); assert phi.merge().usages().contains(phi); for (Node input : phi.inputs()) { @@ -263,10 +261,10 @@ if (b.isLoopHeader()) { Loop loop = b.getLoop(); map.createLoopEntryMemoryMap(modifiedValues.get(loop), loop); - } else { - for (int i = 1; i < b.getPredecessors().size(); ++i) { - assert b.getBeginNode() instanceof MergeNode : b.getBeginNode(); - Block block = b.getPredecessors().get(i); + } + for (int i = 1; i < b.getPredecessors().size(); ++i) { + Block block = b.getPredecessors().get(i); + if (!block.isLoopEnd()) { map.mergeWith(memoryMaps[block.getId()], b); } } @@ -313,40 +311,4 @@ private static void traceWrite(Loop loop, Object locationIdentity, HashMap<Loop, Set<Object>> modifiedValues) { modifiedValues.get(loop).add(locationIdentity); } - - private void mark(LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) { - - if (nodeToLoop.get(begin) != null) { - // Loop already processed. - return; - } - nodeToLoop.set(begin, begin); - - NodeFlood workCFG = begin.graph().createNodeFlood(); - workCFG.add(begin.loopEnd()); - for (Node n : workCFG) { - if (n == begin) { - // Stop at loop begin. - continue; - } - markNode(n, begin, outer, nodeToLoop); - - for (Node pred : n.cfgPredecessors()) { - workCFG.add(pred); - } - } - } - - private void markNode(Node n, LoopBeginNode begin, LoopBeginNode outer, NodeMap<LoopBeginNode> nodeToLoop) { - LoopBeginNode oldMark = nodeToLoop.get(n); - if (oldMark == null || oldMark == outer) { - - // We have an inner loop, start marking it. - if (n instanceof LoopBeginNode) { - mark((LoopBeginNode) n, begin, nodeToLoop); - } - - nodeToLoop.set(n, begin); - } - } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/SchedulePhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -204,10 +204,11 @@ TTY.println(merge.toString()); TTY.println(phi.toString()); TTY.println(merge.cfgPredecessors().toString()); + TTY.println(mergeBlock.getPredecessors().toString()); TTY.println(phi.inputs().toString()); TTY.println("value count: " + phi.valueCount()); } - closure.apply(mergeBlock.getPredecessors().get(i)); + closure.apply(mergeBlock.getPredecessors().get(i)); } } } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java Thu Feb 16 11:57:38 2012 +0100 @@ -358,7 +358,7 @@ if (tsux instanceof MergeNode) { EndNode endNode = graph.add(new EndNode()); result = graph.add(new IfNode(isTypeNode, endNode, nextNode, tsuxProbability)); - ((MergeNode) tsux).addEnd(endNode); + ((MergeNode) tsux).addForwardEnd(endNode); } else { result = graph.add(new IfNode(isTypeNode, tsux, nextNode, tsuxProbability)); } @@ -389,7 +389,7 @@ EndNode endNode = graph.add(new EndNode()); // TODO (ch) set probability duplicatedInvoke.setNext(endNode); - returnMerge.addEnd(endNode); + returnMerge.addForwardEnd(endNode); if (returnValuePhi != null) { returnValuePhi.addInput(duplicatedInvoke.node()); } @@ -424,7 +424,7 @@ EndNode endNode = graph.add(new EndNode()); newExceptionObject.setNext(endNode); - exceptionMerge.addEnd(endNode); + exceptionMerge.addForwardEnd(endNode); exceptionObjectPhi.addInput(newExceptionObject); ((InvokeWithExceptionNode) result).setExceptionEdge(newExceptionEdge);
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Thu Feb 16 11:57:38 2012 +0100 @@ -49,6 +49,7 @@ private GraphEventLog eventLog; ArrayList<Node> usagesDropped = new ArrayList<>(); + NodeWorkList inputChanged; private final HashMap<CacheEntry, Node> cachedNodes = new HashMap<>(); private static final class CacheEntry { @@ -159,6 +160,14 @@ return result; } + public void trackInputChange(NodeWorkList worklist) { + this.inputChanged = worklist; + } + + public void stopTrackingInputChange() { + inputChanged = null; + } + /** * Adds a new node to the graph, if a <i>similar</i> node already exists in the graph, the provided node will not be added to the graph but the <i>similar</i> node will be returned instead. * @param node
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Thu Feb 16 11:57:38 2012 +0100 @@ -180,6 +180,10 @@ assert assertTrue(result, "not found in usages, old input: %s", oldInput); } if (newInput != null) { + NodeWorkList inputChanged = graph.inputChanged; + if (inputChanged != null) { + inputChanged.addAgain(this); + } newInput.usages.add(this); } }
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java Thu Feb 16 11:57:38 2012 +0100 @@ -145,6 +145,23 @@ throw new RuntimeException(e); } } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder("B").append(blockID); + sb.append('[').append(startBci).append("->").append(endBci); + if (isLoopHeader || isExceptionEntry) { + sb.append(' '); + if (isLoopHeader) { + sb.append('L'); + } + if (isExceptionEntry) { + sb.append('!'); + } + } + sb.append(']'); + return sb.toString(); + } } public static class ExceptionBlock extends Block {
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java Thu Feb 16 11:57:38 2012 +0100 @@ -243,12 +243,7 @@ return blocksVisited.contains(block); } - public void mergeOrClone(Block target, FrameStateAccess newState) { - AbstractStateSplit first = (AbstractStateSplit) target.firstInstruction; - - if (target.isLoopHeader && isVisited(target)) { - first = (AbstractStateSplit) loopBegin(target).loopEnd().predecessor(); - } + public void mergeOrClone(Block target, FrameStateAccess newState, StateSplit first) { int bci = target.startBci; if (target instanceof ExceptionBlock) { @@ -256,10 +251,11 @@ } FrameState existingState = first.stateAfter(); - if (existingState == null) { + // There was no state : new target // copy state because it is modified first.setStateAfter(newState.duplicate(bci)); + return; } else { if (!GraalOptions.AssumeVerifiedBytecode && !existingState.isCompatibleWith(newState)) { // stacks or locks do not match--bytecodes would not verify @@ -271,27 +267,31 @@ assert existingState.stackSize() == newState.stackSize(); if (first instanceof PlaceholderNode) { + // there is no merge yet here PlaceholderNode p = (PlaceholderNode) first; if (p.predecessor() == null) { + //nothing seems to come here, yet there's a state? + Debug.log("Funky control flow going to @bci %d : we already have a state but no predecessor", bci); p.setStateAfter(newState.duplicate(bci)); return; } else { + //create a merge MergeNode merge = currentGraph.add(new MergeNode()); FixedNode next = p.next(); - EndNode end = currentGraph.add(new EndNode()); - p.setNext(end); + if (p.predecessor() != null) { + EndNode end = currentGraph.add(new EndNode()); + p.setNext(end); + merge.addForwardEnd(end); + } merge.setNext(next); - merge.addEnd(end); - merge.setStateAfter(existingState); - p.setStateAfter(existingState.duplicate(bci)); - if (!(next instanceof LoopEndNode)) { - target.firstInstruction = merge; - } - first = merge; + FrameState mergeState = existingState.duplicate(bci); + merge.setStateAfter(mergeState); + mergeState.merge(merge, newState); + target.firstInstruction = merge; } + } else { + existingState.merge((MergeNode) first, newState); } - - existingState.merge((MergeNode) first, newState); } } @@ -921,7 +921,7 @@ for (ExceptionInfo info : exceptions) { EndNode end = currentGraph.add(new EndNode()); info.exceptionEdge.setNext(end); - merge.addEnd(end); + merge.addForwardEnd(end); phi.addInput(info.exception); } merge.setStateAfter(frameState.duplicate(bci())); @@ -1264,48 +1264,42 @@ if (block.firstInstruction == null) { if (block.isLoopHeader) { - LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode()); - loopBegin.addEnd(currentGraph.add(new EndNode())); - LoopEndNode loopEnd = currentGraph.add(new LoopEndNode()); - loopEnd.setLoopBegin(loopBegin); - PlaceholderNode pBegin = currentGraph.add(new PlaceholderNode()); - pBegin.setNext(loopBegin.forwardEdge()); - PlaceholderNode pEnd = currentGraph.add(new PlaceholderNode()); - pEnd.setNext(loopEnd); - loopBegin.setStateAfter(stateAfter.duplicate(block.startBci)); - block.firstInstruction = pBegin; + LoopBeginNode loop = currentGraph.add(new LoopBeginNode()); + EndNode end = currentGraph.add(new EndNode()); + loop.addForwardEnd(end); + PlaceholderNode p = currentGraph.add(new PlaceholderNode()); + p.setNext(end); + block.firstInstruction = p; } else { block.firstInstruction = currentGraph.add(new PlaceholderNode()); } } - mergeOrClone(block, stateAfter); + LoopEndNode loopend = null; + StateSplit mergeAt = null; + if (block.isLoopHeader && isVisited(block)) { // backedge + loopend = currentGraph.add(new LoopEndNode(loopBegin(block))); + mergeAt = loopBegin(block); + } else { + mergeAt = (StateSplit) block.firstInstruction; + } + + mergeOrClone(block, stateAfter, mergeAt); addToWorkList(block); FixedNode result = null; - if (block.isLoopHeader && isVisited(block)) { - result = (FixedNode) loopBegin(block).loopEnd().predecessor(); + if (loopend != null) { + result = loopend; } else { result = block.firstInstruction; } - assert result instanceof MergeNode || result instanceof PlaceholderNode : result; if (result instanceof MergeNode) { - if (result instanceof LoopBeginNode) { - result = ((LoopBeginNode) result).forwardEdge(); - } else { - EndNode end = currentGraph.add(new EndNode()); - ((MergeNode) result).addEnd(end); - PlaceholderNode p = currentGraph.add(new PlaceholderNode()); - int bci = block.startBci; - if (block instanceof ExceptionBlock) { - bci = ((ExceptionBlock) block).deoptBci; - } - p.setStateAfter(stateAfter.duplicate(bci)); - p.setNext(end); - result = p; - } + EndNode end = currentGraph.add(new EndNode()); + ((MergeNode) result).addForwardEnd(end); + result = end; } - assert !(result instanceof LoopBeginNode || result instanceof MergeNode); + assert !(result instanceof MergeNode); + Debug.log("createTarget(%s, state) = %s", block, result); return result; } @@ -1332,10 +1326,9 @@ if (block.isLoopHeader) { LoopBeginNode begin = loopBegin(block); FrameState preLoopState = ((StateSplit) block.firstInstruction).stateAfter(); - assert preLoopState != null; - FrameState duplicate = preLoopState.duplicate(preLoopState.bci); - begin.setStateAfter(duplicate); - duplicate.insertLoopPhis(begin); + FrameState loopState = preLoopState.duplicate(preLoopState.bci); + begin.setStateAfter(loopState); + loopState.insertLoopPhis(begin); lastInstr = begin; } else { lastInstr = block.firstInstruction; @@ -1361,11 +1354,7 @@ private void connectLoopEndToBegin() { for (LoopBeginNode begin : currentGraph.getNodes(LoopBeginNode.class)) { - LoopEndNode loopEnd = begin.loopEnd(); - AbstractStateSplit loopEndStateSplit = (AbstractStateSplit) loopEnd.predecessor(); - if (loopEndStateSplit.stateAfter() != null) { - begin.stateAfter().mergeLoop(begin, loopEndStateSplit.stateAfter()); - } else { + if (begin.loopEnds().isEmpty()) { // This can happen with degenerated loops like this one: // for (;;) { // try { @@ -1373,30 +1362,18 @@ // } catch (UnresolvedException iioe) { // } // } - // Delete the phis (all of them must have exactly one input). - for (PhiNode phi : begin.phis().snapshot()) { - assert phi.valueCount() == 1; - begin.stateAfter().deleteRedundantPhi(phi, phi.firstValue()); - } - // Delete the loop end. - loopEndStateSplit.safeDelete(); - loopEnd.safeDelete(); - - // Remove the loop begin. - EndNode loopEntryEnd = begin.forwardEdge(); - FixedNode beginSucc = begin.next(); - FrameState stateAfter = begin.stateAfter(); - begin.safeDelete(); - stateAfter.safeDelete(); - loopEntryEnd.replaceAndDelete(beginSucc); + // Remove the loop begin or transform it into a merge. + assert begin.forwardEndCount() > 0; + currentGraph.reduceDegenerateLoopBegin(begin); + } else { + begin.stateAfter().simplifyLoopState(); } } } private static LoopBeginNode loopBegin(Block block) { - EndNode endNode = (EndNode) block.firstInstruction.next(); - LoopBeginNode loopBegin = (LoopBeginNode) endNode.merge(); + LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) block.firstInstruction.next()).merge(); return loopBegin; }
--- a/graal/com.oracle.max.graal.lir/src/com/oracle/max/graal/lir/cfg/ControlFlowGraph.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.lir/src/com/oracle/max/graal/lir/cfg/ControlFlowGraph.java Thu Feb 16 11:57:38 2012 +0100 @@ -136,7 +136,7 @@ // First time we see this block: push all successors. for (Node suxNode : block.getEndNode().cfgSuccessors()) { Block suxBlock = blockFor(suxNode); - assert suxBlock.id != BLOCK_ID_VISITED; + assert suxBlock.id != BLOCK_ID_VISITED : "Sux already visited?? from " + block.getEndNode() + " to " + suxNode; if (suxBlock.id == BLOCK_ID_INITIAL) { stack.add(suxBlock); } @@ -163,7 +163,9 @@ predecessors.add(nodeToBlock.get(predNode)); } if (block.getBeginNode() instanceof LoopBeginNode) { - predecessors.add(nodeToBlock.get(((LoopBeginNode) block.getBeginNode()).loopEnd())); + for (LoopEndNode predNode : ((LoopBeginNode) block.getBeginNode()).orderedLoopEnds()) { + predecessors.add(nodeToBlock.get(predNode)); + } } block.predecessors = predecessors; @@ -186,9 +188,10 @@ Loop loop = new Loop(block.getLoop(), loopsList.size(), block); loopsList.add(loop); - LoopEndNode end = ((LoopBeginNode) beginNode).loopEnd(); - Block endBlock = nodeToBlock.get(end); - computeLoopBlocks(endBlock, loop); + for (LoopEndNode end : ((LoopBeginNode) beginNode).loopEnds()) { + Block endBlock = nodeToBlock.get(end); + computeLoopBlocks(endBlock, loop); + } } } loops = loopsList.toArray(new Loop[loopsList.size()]); @@ -228,16 +231,12 @@ List<Block> predecessors = block.getPredecessors(); assert predecessors.size() > 0; - if (block.isLoopHeader()) { - // Loop headers have exactly one non-loop predecessor, and that is the dominator. - setDominator(block, predecessors.get(0)); - continue; - } - Block dominator = predecessors.get(0); for (int j = 1; j < predecessors.size(); j++) { Block pred = predecessors.get(j); - dominator = commonDominator(dominator, pred); + if (!pred.isLoopEnd()) { + dominator = commonDominator(dominator, pred); + } } setDominator(block, dominator); }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/EndNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/EndNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -28,7 +28,7 @@ import com.oracle.max.graal.nodes.spi.*; import com.oracle.max.graal.nodes.type.*; -public final class EndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable { +public class EndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable { public EndNode() { super(StampFactory.illegal());
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java Thu Feb 16 11:57:38 2012 +0100 @@ -329,7 +329,7 @@ * @param block the block begin for which we are creating the phi * @param i the index into the stack for which to create a phi */ - public PhiNode setupPhiForStack(MergeNode block, int i) { + public PhiNode setupLoopPhiForStack(MergeNode block, int i) { ValueNode p = stackAt(i); if (p != null) { if (p instanceof PhiNode) { @@ -339,6 +339,7 @@ } } PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value)); + phi.addInput(p); setValueAt(localsSize + i, phi); return phi; } @@ -350,7 +351,7 @@ * @param block the block begin for which we are creating the phi * @param i the index of the local variable for which to create the phi */ - public PhiNode setupPhiForLocal(MergeNode block, int i) { + public PhiNode setupLoopPhiForLocal(MergeNode block, int i) { ValueNode p = localAt(i); if (p instanceof PhiNode) { PhiNode phi = (PhiNode) p; @@ -359,6 +360,7 @@ } } PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value)); + phi.addInput(p); storeLocal(i, phi); return phi; } @@ -401,9 +403,9 @@ for (int i = 0; i < valuesSize(); i++) { ValueNode currentValue = valueAt(i); ValueNode otherValue = other.valueAt(i); - if (currentValue != otherValue) { + if (currentValue != otherValue || block instanceof LoopBeginNode) { if (block.isPhiAtMerge(currentValue)) { - addToPhi((PhiNode) currentValue, otherValue); + addToPhi((PhiNode) currentValue, otherValue, block instanceof LoopBeginNode); } else { setValueAt(i, combineValues(currentValue, otherValue, block)); } @@ -411,12 +413,18 @@ } } - private ValueNode combineValues(ValueNode currentValue, ValueNode otherValue, MergeNode block) { + public void simplifyLoopState() { + for (PhiNode phi : values.filter(PhiNode.class).snapshot()) { + checkRedundantPhi(phi); + } + } + + private static ValueNode combineValues(ValueNode currentValue, ValueNode otherValue, MergeNode block) { if (currentValue == null || otherValue == null || currentValue.kind() != otherValue.kind()) { return null; } - PhiNode phi = graph().unique(new PhiNode(currentValue.kind(), block, PhiType.Value)); + PhiNode phi = currentValue.graph().add(new PhiNode(currentValue.kind(), block, PhiType.Value)); for (int j = 0; j < block.phiPredecessorCount(); ++j) { phi.addInput(currentValue); } @@ -425,43 +433,28 @@ return phi; } - private static void addToPhi(PhiNode phiNode, ValueNode otherValue) { + private static void addToPhi(PhiNode phiNode, ValueNode otherValue, boolean recursiveInvalidCheck) { if (otherValue == null || otherValue.kind() != phiNode.kind()) { - phiNode.replaceAtUsages(null); - phiNode.safeDelete(); + if (recursiveInvalidCheck) { + deleteInvalidPhi(phiNode); + } else { + phiNode.replaceAtUsages(null); + phiNode.safeDelete(); + } } else { phiNode.addInput(otherValue); } } - public void mergeLoop(LoopBeginNode block, FrameStateAccess other) { - assert checkSize(other); - for (int i = 0; i < valuesSize(); i++) { - PhiNode currentValue = (PhiNode) valueAt(i); - if (currentValue != null) { - assert currentValue.merge() == block; - assert currentValue.valueCount() == 1; - ValueNode otherValue = other.valueAt(i); - if (otherValue == currentValue) { - deleteRedundantPhi(currentValue, currentValue.firstValue()); - } else if (otherValue == null || otherValue.kind() != currentValue.kind()) { - deleteInvalidPhi(currentValue); - } else { - currentValue.addInput(otherValue); - } - } - } - } - - public void deleteRedundantPhi(PhiNode redundantPhi, ValueNode phiValue) { + public static void deleteRedundantPhi(PhiNode redundantPhi, ValueNode phiValue) { Collection<PhiNode> phiUsages = redundantPhi.usages().filter(PhiNode.class).snapshot(); - ((StructuredGraph) graph()).replaceFloating(redundantPhi, phiValue); + ((StructuredGraph) redundantPhi.graph()).replaceFloating(redundantPhi, phiValue); for (PhiNode phi : phiUsages) { checkRedundantPhi(phi); } } - private void checkRedundantPhi(PhiNode phiNode) { + private static void checkRedundantPhi(PhiNode phiNode) { if (phiNode.isDeleted() || phiNode.valueCount() == 1) { return; } @@ -472,7 +465,7 @@ } } - private void deleteInvalidPhi(PhiNode phiNode) { + private static void deleteInvalidPhi(PhiNode phiNode) { if (!phiNode.isDeleted()) { Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot(); phiNode.replaceAtUsages(null); @@ -575,13 +568,13 @@ // always insert phis for the stack ValueNode x = stackAt(i); if (x != null) { - setupPhiForStack(loopBegin, i).addInput(x); + setupLoopPhiForStack(loopBegin, i); } } for (int i = 0; i < localsSize(); i++) { ValueNode x = localAt(i); if (x != null) { - setupPhiForLocal(loopBegin, i).addInput(x); + setupLoopPhiForLocal(loopBegin, i); } } }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/IfNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/IfNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -121,7 +121,7 @@ EndNode trueEnd = (EndNode) trueSuccessor().next(); EndNode falseEnd = (EndNode) falseSuccessor().next(); MergeNode merge = trueEnd.merge(); - if (merge == falseEnd.merge() && merge.endCount() == 2) { + if (merge == falseEnd.merge() && merge.forwardEndCount() == 2) { Iterator<PhiNode> phis = merge.phis().iterator(); if (!phis.hasNext()) { // empty if construct with no phis: remove it @@ -130,7 +130,7 @@ PhiNode singlePhi = phis.next(); if (!phis.hasNext()) { // one phi at the merge of an otherwise empty if construct: try to convert into a MaterializeNode - boolean inverted = trueEnd == merge.endAt(FALSE_EDGE); + boolean inverted = trueEnd == merge.forwardEndAt(FALSE_EDGE); ValueNode trueValue = singlePhi.valueAt(inverted ? 1 : 0); ValueNode falseValue = singlePhi.valueAt(inverted ? 0 : 1); if (trueValue.kind() != falseValue.kind()) {
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/InvokeNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/InvokeNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -71,7 +71,9 @@ @Override public Map<Object, Object> getDebugProperties() { Map<Object, Object> debugProperties = super.getDebugProperties(); - debugProperties.put("targetMethod", CiUtil.format("%h.%n(%p)", callTarget.targetMethod())); + if (callTarget != null && callTarget.targetMethod() != null) { + debugProperties.put("targetMethod", CiUtil.format("%h.%n(%p)", callTarget.targetMethod())); + } return debugProperties; } @@ -85,6 +87,9 @@ if (verbosity == Verbosity.Long) { return super.toString(Verbosity.Short) + "(bci=" + bci() + ")"; } else if (verbosity == Verbosity.Name) { + if (callTarget == null || callTarget.targetMethod() == null) { + return "Invoke#??Invalid!"; + } return "Invoke#" + callTarget.targetMethod().name(); } else { return super.toString(verbosity);
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopBeginNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -25,12 +25,13 @@ import java.util.*; import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.graph.iterators.*; import com.oracle.max.graal.nodes.spi.*; public class LoopBeginNode extends MergeNode implements Node.IterableNodeType, LIRLowerable { - private double loopFrequency; + private int nextEndIndex; public LoopBeginNode() { loopFrequency = 1; @@ -44,8 +45,24 @@ this.loopFrequency = loopFrequency; } - public LoopEndNode loopEnd() { - return usages().filter(LoopEndNode.class).first(); + public NodeIterable<LoopEndNode> loopEnds() { + return usages().filter(LoopEndNode.class); + } + + public List<LoopEndNode> orderedLoopEnds() { + List<LoopEndNode> snapshot = usages().filter(LoopEndNode.class).snapshot(); + Collections.sort(snapshot, new Comparator<LoopEndNode>() { + @Override + public int compare(LoopEndNode o1, LoopEndNode o2) { + return o1.endIndex() - o2.endIndex(); + } + }); + return snapshot; + } + + public EndNode forwardEnd() { + assert forwardEndCount() == 1; + return forwardEndAt(0); } @Override @@ -54,39 +71,61 @@ } @Override + protected void deleteEnd(EndNode end) { + if (end instanceof LoopEndNode) { + LoopEndNode loopEnd = (LoopEndNode) end; + loopEnd.setLoopBegin(null); + int idx = loopEnd.endIndex(); + for (LoopEndNode le : loopEnds()) { + int leIdx = le.endIndex(); + assert leIdx != idx; + if (leIdx > idx) { + le.setEndIndex(leIdx - 1); + } + } + } else { + super.deleteEnd(end); + } + } + + @Override public int phiPredecessorCount() { - return endCount() + 1; + return forwardEndCount() + loopEnds().count(); } @Override - public int phiPredecessorIndex(FixedNode pred) { - if (pred == forwardEdge()) { - return 0; - } else if (pred == this.loopEnd()) { - return 1; + public int phiPredecessorIndex(EndNode pred) { + if (pred instanceof LoopEndNode) { + LoopEndNode loopEnd = (LoopEndNode) pred; + if (loopEnd.loopBegin() == this) { + assert loopEnd.endIndex() < loopEnds().count(); + return loopEnd.endIndex() + forwardEndCount(); + } + } else { + return super.forwardEndIndex(pred); } - throw ValueUtil.shouldNotReachHere("unknown pred : " + pred + "(sp=" + forwardEdge() + ", le=" + this.loopEnd() + ")"); + throw ValueUtil.shouldNotReachHere("unknown pred : " + pred); } @Override - public FixedNode phiPredecessorAt(int index) { - if (index == 0) { - return forwardEdge(); - } else if (index == 1) { - return loopEnd(); + public EndNode phiPredecessorAt(int index) { + if (index < forwardEndCount()) { + return forwardEndAt(index); + } + for (LoopEndNode end : loopEnds()) { + int idx = index - forwardEndCount(); + assert idx >= 0; + if (end.endIndex() == idx) { + return end; + } } throw ValueUtil.shouldNotReachHere(); } - public EndNode forwardEdge() { - return this.endAt(0); - } - @Override public boolean verify() { - assertTrue(loopEnd() != null, "missing loopEnd"); - assertTrue(forwardEdge() != null, "missing forwardEdge"); - assertTrue(usages().filter(LoopEndNode.class).count() == 1, "multiple loop ends"); + assertTrue(loopEnds().count() > 0, "missing loopEnd"); + assertTrue(forwardEndCount() == 1, "LoopBegin should only have one forward edge"); return super.verify(); } @@ -96,4 +135,8 @@ properties.put("loopFrequency", String.format("%7.1f", loopFrequency)); return properties; } + + public int nextEndIndex() { + return nextEndIndex++; + } }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopEndNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/LoopEndNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -22,19 +22,29 @@ */ package com.oracle.max.graal.nodes; +import java.util.*; + import com.oracle.max.graal.graph.*; import com.oracle.max.graal.nodes.spi.*; -import com.oracle.max.graal.nodes.type.*; -public class LoopEndNode extends FixedNode implements Node.IterableNodeType, LIRLowerable { +public final class LoopEndNode extends EndNode { @Input(notDataflow = true) private LoopBeginNode loopBegin; @Data private boolean safepointPolling; + @Data private int endIndex; - public LoopEndNode() { - super(StampFactory.illegal()); + public LoopEndNode(LoopBeginNode begin) { + int idx = begin.nextEndIndex(); + assert idx >= 0; this.safepointPolling = true; + this.endIndex = idx; + this.loopBegin = begin; + } + + @Override + public MergeNode merge() { + return loopBegin(); } public LoopBeginNode loopBegin() { @@ -58,11 +68,26 @@ @Override public void generate(LIRGeneratorTool gen) { gen.visitLoopEnd(this); + super.generate(gen); } @Override public boolean verify() { assertTrue(loopBegin != null, "must have a loop begin"); + assertTrue(usages().count() == 0, "LoopEnds can not be used"); return super.verify(); } + + public int endIndex() { + return endIndex; + } + + public void setEndIndex(int idx) { + this.endIndex = idx; + } + + @Override + public Iterable< ? extends Node> cfgSuccessors() { + return Collections.emptyList(); + } }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/MergeNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/MergeNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -43,19 +43,19 @@ gen.visitMerge(this); } - public int endIndex(EndNode end) { + public int forwardEndIndex(EndNode end) { return ends.indexOf(end); } - public void addEnd(EndNode end) { + public void addForwardEnd(EndNode end) { ends.add(end); } - public int endCount() { + public int forwardEndCount() { return ends.size(); } - public EndNode endAt(int index) { + public EndNode forwardEndAt(int index) { return ends.get(index); } @@ -74,67 +74,41 @@ return value instanceof PhiNode && ((PhiNode) value).merge() == this; } - - /** - * Formats a given instruction as a value in a {@linkplain FrameState frame state}. If the instruction is a phi defined at a given - * block, its {@linkplain PhiNode#valueCount() inputs} are appended to the returned string. - * - * @param index the index of the value in the frame state - * @param value the frame state value - * @return the instruction representation as a string - */ - public String stateString(int index, ValueNode value) { - StringBuilder sb = new StringBuilder(30); - sb.append(String.format("%2d %s", index, ValueUtil.valueString(value))); - if (value instanceof PhiNode) { - PhiNode phi = (PhiNode) value; - // print phi operands - if (phi.merge() == this) { - sb.append(" ["); - for (int j = 0; j < phi.valueCount(); j++) { - sb.append(' '); - ValueNode operand = phi.valueAt(j); - if (operand != null) { - sb.append(ValueUtil.valueString(operand)); - } else { - sb.append("NULL"); - } - } - sb.append("] "); - } - } - return sb.toString(); - } - /** * Removes the given end from the merge, along with the entries corresponding to this end in the phis connected to the merge. * @param pred the end to remove */ public void removeEnd(EndNode pred) { - int predIndex = ends.indexOf(pred); + int predIndex = phiPredecessorIndex(pred); assert predIndex != -1; - ends.remove(predIndex); - + deleteEnd(pred); for (PhiNode phi : phis()) { phi.removeInput(predIndex); } } + protected void deleteEnd(EndNode end) { + ends.remove(end); + } + public void clearEnds() { ends.clear(); } - public int phiPredecessorCount() { - return endCount(); + public NodeIterable<EndNode> forwardEnds() { + return ends; } - public int phiPredecessorIndex(FixedNode pred) { - EndNode end = (EndNode) pred; - return endIndex(end); + public int phiPredecessorCount() { + return forwardEndCount(); } - public FixedNode phiPredecessorAt(int index) { - return endAt(index); + public int phiPredecessorIndex(EndNode pred) { + return forwardEndIndex(pred); + } + + public EndNode phiPredecessorAt(int index) { + return forwardEndAt(index); } public NodeIterable<PhiNode> phis() {
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PhiNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PhiNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -100,7 +100,7 @@ values.set(i, x); } - public ValueNode valueAt(FixedNode pred) { + public ValueNode valueAt(EndNode pred) { return valueAt(merge().phiPredecessorIndex(pred)); }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/StructuredGraph.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/StructuredGraph.java Thu Feb 16 11:57:38 2012 +0100 @@ -285,4 +285,37 @@ newNode.setNext(node); } + public void reduceDegenerateLoopBegin(LoopBeginNode begin) { + assert begin.loopEnds().count() == 0 : "Loop begin still has backedges"; + if (begin.forwardEndCount() == 1) { // bypass merge and remove + reduceTrivialMerge(begin); + } else { // convert to merge + MergeNode merge = this.add(new MergeNode()); + this.replaceFixedWithFixed(begin, merge); + } + } + + public void reduceTrivialMerge(MergeNode merge) { + assert merge.forwardEndCount() == 1; + assert !(merge instanceof LoopBeginNode) || ((LoopBeginNode) merge).loopEnds().count() == 0; + for (PhiNode phi : merge.phis().snapshot()) { + assert phi.valueCount() == 1; + ValueNode singleValue = phi.valueAt(0); + phi.replaceAtUsages(singleValue); + phi.safeDelete(); + } + EndNode singleEnd = merge.forwardEndAt(0); + FixedNode sux = merge.next(); + FrameState stateAfter = merge.stateAfter(); + merge.safeDelete(); + if (stateAfter != null && stateAfter.usages().count() == 0) { + stateAfter.safeDelete(); + } + if (sux == null) { + singleEnd.replaceAtPredecessors(null); + singleEnd.safeDelete(); + } else { + singleEnd.replaceAndDelete(sux); + } + } }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/calc/ConditionalNode.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/calc/ConditionalNode.java Thu Feb 16 11:57:38 2012 +0100 @@ -81,8 +81,8 @@ ifNode.setTrueSuccessor(BeginNode.begin(trueEnd)); ifNode.setFalseSuccessor(BeginNode.begin(falseEnd)); MergeNode merge = graph.add(new MergeNode()); - merge.addEnd(trueEnd); - merge.addEnd(falseEnd); + merge.addForwardEnd(trueEnd); + merge.addForwardEnd(falseEnd); PhiNode phi = graph.unique(new PhiNode(kind, merge, PhiType.Value)); phi.addInput(trueValue); phi.addInput(falseValue);
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/util/GraphUtil.java Wed Feb 15 20:09:25 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/util/GraphUtil.java Thu Feb 16 11:57:38 2012 +0100 @@ -22,10 +22,13 @@ */ package com.oracle.max.graal.nodes.util; +import static com.oracle.max.graal.graph.iterators.NodePredicates.*; + import java.util.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.nodes.*; +import com.oracle.max.graal.nodes.calc.*; public class GraphUtil { @@ -35,9 +38,6 @@ // We reached a control flow end. EndNode end = (EndNode) node; killEnd(end); - } else if (node instanceof LoopEndNode) { - // We reached a loop end. - killLoopEnd(node); } else { // Normal control flow node. for (Node successor : node.successors().snapshot()) { @@ -47,59 +47,33 @@ propagateKill(node); } - private static void killLoopEnd(FixedNode node) { - LoopEndNode loopEndNode = (LoopEndNode) node; - LoopBeginNode loop = loopEndNode.loopBegin(); - loopEndNode.setLoopBegin(null); - EndNode endNode = loop.endAt(0); - assert endNode.predecessor() != null; - replaceLoopPhis(loop); - loop.removeEnd(endNode); - - FixedNode next = loop.next(); - loop.setNext(null); - endNode.replaceAndDelete(next); - loop.safeDelete(); - } - - private static void replaceLoopPhis(MergeNode merge) { - for (Node usage : merge.usages().snapshot()) { - assert usage instanceof PhiNode; - ((StructuredGraph) merge.graph()).replaceFloating((PhiNode) usage, ((PhiNode) usage).valueAt(0)); - } - } - private static void killEnd(EndNode end) { MergeNode merge = end.merge(); - if (merge instanceof LoopBeginNode) { + merge.removeEnd(end); + if (merge instanceof LoopBeginNode && merge.forwardEndCount() == 0) { //dead loop for (PhiNode phi : merge.phis().snapshot()) { - ValueNode value = phi.valueAt(0); - phi.replaceAndDelete(value); + propagateKill(phi); } - killCFG(merge); - } else { - merge.removeEnd(end); - if (merge.phiPredecessorCount() == 1) { - for (PhiNode phi : merge.phis().snapshot()) { - ValueNode value = phi.valueAt(0); - phi.replaceAndDelete(value); - } - Node replacedSux = merge.phiPredecessorAt(0); - Node pred = replacedSux.predecessor(); - assert replacedSux instanceof EndNode; - FixedNode next = merge.next(); - merge.setNext(null); - pred.replaceFirstSuccessor(replacedSux, next); - merge.safeDelete(); - replacedSux.safeDelete(); + LoopBeginNode begin = (LoopBeginNode) merge; + // disconnect and delete loop ends + for (LoopEndNode loopend : begin.loopEnds().snapshot()) { + loopend.predecessor().replaceFirstSuccessor(loopend, null); + loopend.safeDelete(); } + FixedNode next = begin.next(); + begin.safeDelete(); + killCFG(next); + } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().count() == 0) { // not a loop anymore + ((StructuredGraph) end.graph()).reduceDegenerateLoopBegin((LoopBeginNode) merge); + } else if (merge.phiPredecessorCount() == 1) { // not a merge anymore + ((StructuredGraph) end.graph()).reduceTrivialMerge(merge); } } // TODO(tw): Factor this code with other branch deletion code. public static void propagateKill(Node node) { if (node != null && node.isAlive()) { - List<Node> usagesSnapshot = node.usages().snapshot(); + List<Node> usagesSnapshot = node.usages().filter(isA(FloatingNode.class).or(CallTargetNode.class)).snapshot(); // null out remaining usages node.replaceAtUsages(null); @@ -108,7 +82,11 @@ for (Node usage : usagesSnapshot) { if (!usage.isDeleted()) { - propagateKill(usage); + if (usage instanceof PhiNode) { + usage.replaceFirstInput(node, null); + } else { + propagateKill(usage); + } } } }