Mercurial > hg > truffle
changeset 3061:00239c259a42
Compute Loop information, keep Placeholder on loop exits, added some utility functions for data/cfg traversal
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 21 16:58:34 2011 +0200 @@ -28,6 +28,8 @@ import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.compiler.util.LoopUtil.Loop; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; @@ -121,9 +123,10 @@ // nothing to do here... t.printStackTrace(); } + List<Loop> loops = LoopUtil.computeLoops(graph); stream.println(" <nodes>"); - List<Edge> edges = printNodes(graph.getNodes(), shortNames, schedule == null ? null : schedule.getNodeToBlock()); + List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops); stream.println(" </nodes>"); stream.println(" <edges>"); @@ -145,10 +148,14 @@ flush(); } - private List<Edge> printNodes(Collection<Node> nodes, boolean shortNames, NodeMap<Block> nodeToBlock) { + private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops) { ArrayList<Edge> edges = new ArrayList<Edge>(); + NodeBitMap loopExits = graph.createNodeBitMap(); + for (Loop loop : loops) { + loopExits.markAll(loop.exist()); + } - for (Node node : nodes) { + for (Node node : graph.getNodes()) { if (node == Node.Null || omittedClasses.contains(node.getClass())) { continue; } @@ -170,13 +177,28 @@ Block block = nodeToBlock == null ? null : nodeToBlock.get(node); if (block != null) { stream.printf(" <p name='block'>%d</p>%n", block.blockID()); - if (!(node instanceof Phi || node instanceof FrameState || node instanceof Local) && !block.getInstructions().contains(node)) { + if (!(node instanceof Phi || node instanceof FrameState || node instanceof Local || node instanceof LoopCounter) && !block.getInstructions().contains(node)) { stream.printf(" <p name='notInOwnBlock'>true</p>%n"); } } else { stream.printf(" <p name='block'>noBlock</p>%n"); noBlockNodes.add(node); } + if (loopExits.isMarked(node)) { + stream.printf(" <p name='loopExit'>true</p>%n"); + } + StringBuilder sb = new StringBuilder(); + for (Loop loop : loops) { + if (loop.nodes().isMarked(node)) { + if (sb.length() > 0) { + sb.append(", "); + } + sb.append(loop.loopBegin().id()); + } + } + if (sb.length() > 0) { + stream.printf(" <p name='loops'>%s</p>%n", sb); + } for (Entry<Object, Object> entry : props.entrySet()) { String key = entry.getKey().toString(); String value = entry.getValue() == null ? "null" : entry.getValue().toString();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jun 21 16:58:34 2011 +0200 @@ -166,6 +166,7 @@ if (GraalOptions.Time) { GraalTimers.COMPUTE_LINEAR_SCAN_ORDER.stop(); } + } /**
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ControlSplit.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ControlSplit.java Tue Jun 21 16:58:34 2011 +0200 @@ -48,9 +48,6 @@ return super.successorCount() + blockSuccessorCount + SUCCESSOR_COUNT; } - /** - * The list of instructions that produce input for this instruction. - */ public FixedNode blockSuccessor(int index) { assert index >= 0 && index < blockSuccessorCount; return (FixedNode) successors().get(super.successorCount() + SUCCESSOR_COUNT + index); @@ -89,4 +86,28 @@ public FixedNode defaultSuccessor() { return blockSuccessor(blockSuccessorCount - 1); } + + public Iterable<FixedNode> blockSuccessors() { + return new Iterable<FixedNode>() { + @Override + public Iterator<FixedNode> iterator() { + return new Iterator<FixedNode>() { + int i = 0; + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + @Override + public FixedNode next() { + return ControlSplit.this.blockSuccessor(i++); + } + + @Override + public boolean hasNext() { + return i < ControlSplit.this.blockSuccessorCount; + } + }; + } + }; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 21 16:58:34 2011 +0200 @@ -102,4 +102,20 @@ assertTrue(forwardEdge() != null); return true; } + + @Override + public String toString() { + return "LoopBegin: " + super.toString(); + } + + @Override + public Iterable< ? extends Node> dataUsages() { + final Iterator< ? extends Node> dataUsages = super.dataUsages().iterator(); + return new Iterable<Node>() { + @Override + public Iterator<Node> iterator() { + return new StateSplit.FilteringIterator(dataUsages, LoopBegin.class); + } + }; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java Tue Jun 21 16:58:34 2011 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -84,4 +86,9 @@ public String toString() { return "LoopEnd:" + super.toString(); } + + @Override + public Iterable< ? extends Node> dataInputs() { + return Collections.emptyList(); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Tue Jun 21 16:58:34 2011 +0200 @@ -92,18 +92,19 @@ return (EndNode) inputs().variablePart().get(index); } - public Iterable<Node> mergePredecessors() { - return new Iterable<Node>() { + @Override + public Iterable<EndNode> cfgPredecessors() { + return new Iterable<EndNode>() { @Override - public Iterator<Node> iterator() { - return new Iterator<Node>() { + public Iterator<EndNode> iterator() { + return new Iterator<EndNode>() { int i = 0; @Override public void remove() { throw new UnsupportedOperationException(); } @Override - public Node next() { + public EndNode next() { return Merge.this.endAt(i++); } @Override @@ -116,6 +117,11 @@ } @Override + public Iterable< ? extends Node> dataInputs() { + return Collections.emptyList(); + } + + @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("merge #");
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Placeholder.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Placeholder.java Tue Jun 21 16:58:34 2011 +0200 @@ -49,7 +49,7 @@ @Override public void accept(ValueVisitor v) { - assert false; + //assert false; } @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StateSplit.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StateSplit.java Tue Jun 21 16:58:34 2011 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -35,7 +37,7 @@ private static final int INPUT_COUNT = 1; private static final int INPUT_STATE_AFTER = 0; - private static final int SUCCESSOR_COUNT = 1; + private static final int SUCCESSOR_COUNT = 0; @Override protected int inputCount() { @@ -73,4 +75,58 @@ public boolean needsStateAfter() { return true; } + + @Override + public Iterable< ? extends Node> dataInputs() { + final Iterator< ? extends Node> dataInputs = super.dataInputs().iterator(); + return new Iterable<Node>() { + @Override + public Iterator<Node> iterator() { + return new FilteringIterator(dataInputs, FrameState.class); + } + }; + } + + public static final class FilteringIterator implements Iterator<Node> { + + private final Iterator< ? extends Node> input; + private Node next; + private Class< ? > clazz; + + public FilteringIterator(Iterator< ? extends Node> input, Class<?> clazz) { + this.input = input; + this.clazz = clazz; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + + @Override + public Node next() { + forward(); + if (!hasNext()) { + throw new NoSuchElementException(); + } + Node res = next; + next = null; + return res; + } + + @Override + public boolean hasNext() { + forward(); + return next != null; + } + + private void forward() { + while (next == null && input.hasNext()) { + next = input.next(); + if (clazz.isInstance(next)) { + next = null; + } + } + } + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java Tue Jun 21 16:58:34 2011 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -170,4 +171,15 @@ properties.put("operand", operand == null ? "null" : operand.toString()); return properties; } + + @Override + public Iterable<? extends Node> dataUsages() { + final Iterator<? extends Node> dataUsages = super.dataUsages().iterator(); + return new Iterable<Node>() { + @Override + public Iterator<Node> iterator() { + return new StateSplit.FilteringIterator(dataUsages, FrameState.class); + } + }; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 21 16:58:34 2011 +0200 @@ -39,6 +39,7 @@ import com.oracle.max.graal.compiler.ir.Deoptimize.DeoptAction; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.compiler.util.LoopUtil.Loop; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.bytecode.*; @@ -197,9 +198,15 @@ addToWorkList(blockFromBci[0]); iterateAllBlocks(); + List<Loop> loops = LoopUtil.computeLoops(graph); + NodeBitMap loopExits = graph.createNodeBitMap(); + for (Loop loop : loops) { + loopExits.markAll(loop.exist()); + } + // remove Placeholders for (Node n : graph.getNodes()) { - if (n instanceof Placeholder) { + if (n instanceof Placeholder && !loopExits.isMarked(n)) { Placeholder p = (Placeholder) n; p.replace(p.next()); } @@ -419,6 +426,8 @@ dispatchBlock = blockFromBci[handlerBCI]; } } + Placeholder p = new Placeholder(graph); + p.setStateAfter(frameState.duplicateWithoutStack(bci)); Value currentExceptionObject; if (exceptionObject == null) { @@ -431,10 +440,11 @@ if (exceptionObject == null) { ExceptionObject eObj = (ExceptionObject) currentExceptionObject; eObj.setNext(target); - return eObj; + p.setNext(eObj); } else { - return target; + p.setNext(target); } + return p; } return null; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jun 21 16:58:34 2011 +0200 @@ -279,6 +279,9 @@ private void inlineMethod(Invoke invoke, RiMethod method) { FrameState stateAfter = invoke.stateAfter(); FixedNode exceptionEdge = invoke.exceptionEdge(); + if (exceptionEdge instanceof Placeholder) { + exceptionEdge = ((Placeholder) exceptionEdge).next(); + } CompilerGraph graph; Object stored = GraphBuilderPhase.cachedGraphs.get(method);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Jun 21 16:58:34 2011 +0200 @@ -44,7 +44,7 @@ } private void doLoop(LoopBegin loopBegin) { - NodeBitMap loopNodes = computeLoopNodes(loopBegin); + NodeBitMap loopNodes = LoopUtil.computeLoopNodes(loopBegin); List<LoopCounter> counters = findLoopCounters(loopBegin, loopNodes); mergeLoopCounters(counters, loopBegin); } @@ -151,38 +151,4 @@ } return counters; } - - private NodeBitMap computeLoopNodes(LoopBegin loopBegin) { - LoopEnd loopEnd = loopBegin.loopEnd(); - NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap(); - NodeFlood workCFG = loopBegin.graph().createNodeFlood(); - NodeFlood workData = loopBegin.graph().createNodeFlood(); - workCFG.add(loopEnd); - for (Node n : workCFG) { - workData.add(n); - loopNodes.mark(n); - if (n == loopBegin) { - continue; - } - for (Node pred : n.predecessors()) { - workCFG.add(pred); - } - if (n instanceof Merge) { - Merge merge = (Merge) n; - for (int i = 0; i < merge.endCount(); i++) { - workCFG.add(merge.endAt(i)); - } - } - } - for (Node n : workData) { - loopNodes.mark(n); - for (Node usage : n.usages()) { - if (usage instanceof FrameState) { - continue; - } - workData.add(usage); - } - } - return loopNodes; - } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Jun 21 16:58:34 2011 +0200 @@ -137,7 +137,7 @@ Node n = block.firstNode(); if (n instanceof Merge) { Merge m = (Merge) n; - for (Node pred : m.mergePredecessors()) { + for (Node pred : m.cfgPredecessors()) { Block predBlock = nodeToBlock.get(pred); predBlock.addSuccessor(block); } @@ -241,11 +241,6 @@ assert !n.isDeleted(); - Block prevBlock = nodeToBlock.get(n); - if (prevBlock != null) { - return prevBlock; - } - if (n instanceof Phi) { Block block = nodeToBlock.get(((Phi) n).merge()); nodeToBlock.set(n, block); @@ -256,6 +251,11 @@ nodeToBlock.set(n, block); } + Block prevBlock = nodeToBlock.get(n); + if (prevBlock != null) { + return prevBlock; + } + Block block = null; for (Node succ : n.successors()) { block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); @@ -279,7 +279,7 @@ } } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { Merge merge = ((FrameState) usage).block(); - for (Node pred : merge.mergePredecessors()) { + for (Node pred : merge.cfgPredecessors()) { block = getCommonDominator(block, nodeToBlock.get(pred)); } } else if (usage instanceof LoopCounter) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Jun 21 16:58:34 2011 +0200 @@ -0,0 +1,145 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.util; + +import java.util.*; + +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.graph.*; + +public class LoopUtil { + + public static class Loop { + private final LoopBegin loopBegin; + private final NodeBitMap nodes; + private Loop parent; + private final List<FixedNode> exits; + public Loop(LoopBegin loopBegin, NodeBitMap nodes) { + this.loopBegin = loopBegin; + this.nodes = nodes; + this.exits = new LinkedList<FixedNode>(); + } + + public LoopBegin loopBegin() { + return loopBegin; + } + + public NodeBitMap nodes() { + return nodes; + } + + public Loop parent() { + return parent; + } + + public List<FixedNode> exist() { + return exits; + } + + public void setParent(Loop parent) { + this.parent = parent; + } + } + + public static List<Loop> computeLoops(Graph graph) { + List<Loop> loops = new LinkedList<LoopUtil.Loop>(); + for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) { + NodeBitMap nodes = computeLoopNodes(loopBegin); + Loop loop = new Loop(loopBegin, nodes); + NodeFlood workCFG = graph.createNodeFlood(); + workCFG.add(loopBegin.loopEnd()); + for (Node n : workCFG) { + if (n == loopBegin) { + continue; + } + if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { + for (Node sux : n.cfgSuccessors()) { + if (!nodes.isMarked(sux) && sux instanceof FixedNode) { + loop.exits.add((FixedNode) sux); + } + } + } + for (Node pred : n.cfgPredecessors()) { + workCFG.add(pred); + } + } + loops.add(loop); + } + for (Loop loop : loops) { + for (Loop other : loops) { + if (other != loop && other.nodes().isMarked(loop.loopBegin())) { + if (loop.parent() == null || loop.parent().nodes().isMarked(other.loopBegin())) { + loop.setParent(other); + } + } + } + } + return loops; + } + + public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) { + LoopEnd loopEnd = loopBegin.loopEnd(); + NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap(); + NodeFlood workCFG = loopBegin.graph().createNodeFlood(); + NodeFlood workData1 = loopBegin.graph().createNodeFlood(); + NodeFlood workData2 = loopBegin.graph().createNodeFlood(); + workCFG.add(loopEnd); + for (Node n : workCFG) { + workData1.add(n); + workData2.add(n); + loopNodes.mark(n); + if (n == loopBegin) { + continue; + } + if (n instanceof LoopBegin) { + workCFG.add(((LoopBegin) n).loopEnd()); + } + for (Node pred : n.cfgPredecessors()) { + workCFG.add(pred); + } + } + NodeBitMap inOrAfter = loopBegin.graph().createNodeBitMap(); + for (Node n : workData1) { + inOrAfter.mark(n); + for (Node usage : n.dataUsages()) { + workData1.add(usage); + } + } + NodeBitMap inOrBefore = loopBegin.graph().createNodeBitMap(); + for (Node n : workData2) { + inOrBefore.mark(n); + for (Node input : n.dataInputs()) { + workData2.add(input); + } + if (n instanceof Merge) { //add phis & counters + for (Node usage : n.dataUsages()) { + workData2.add(usage); + } + } + } + inOrBefore.setIntersect(inOrAfter); + loopNodes.setUnion(inOrBefore); + return loopNodes; + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameStateBuilder.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameStateBuilder.java Tue Jun 21 16:58:34 2011 +0200 @@ -507,4 +507,10 @@ public FrameState outerFrameState() { return null; } + + public FrameState duplicateWithoutStack(int bci) { + FrameState frameState = new FrameState(method, bci, locals, new Value[0], 0, locks, true, graph); + frameState.setOuterFrameState(outerFrameState()); + return frameState; + } }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolvedImpl.java Tue Jun 21 11:44:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolvedImpl.java Tue Jun 21 16:58:34 2011 +0200 @@ -34,7 +34,7 @@ */ public final class HotSpotMethodResolvedImpl extends HotSpotMethod implements HotSpotMethodResolved { - // Do not use as a Java object! + /** DO NOT USE IN JAVA CODE! */ @Deprecated private Object javaMirror;