# HG changeset patch # User Lukas Stadler # Date 1307536227 -7200 # Node ID 7eec76f3e39e6015bba56caa49674e4fff8fb585 # Parent 693e4e92346b912db24d9ebe4f5ba5eb6fbda75f adjust monitor index while inlining, renamed NodeWorklist to NodeFlood diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jun 08 14:30:27 2011 +0200 @@ -532,7 +532,7 @@ @Override public void visitMonitorAddress(MonitorAddress x) { CiValue result = createResultVariable(x); - lir.monitorAddress(x.monitor(), result); + lir.monitorAddress(x.monitorIndex(), result); } /** diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Wed Jun 08 14:30:27 2011 +0200 @@ -202,7 +202,12 @@ int maxLocks = 0; for (Node node : compilation.graph.getNodes()) { if (node instanceof FrameState) { - int lockCount = ((FrameState) node).locksSize(); + FrameState current = (FrameState) node; + int lockCount = 0; + while (current != null) { + lockCount += current.locksSize(); + current = current.outerFrameState(); + } if (lockCount > maxLocks) { maxLocks = lockCount; } diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorAddress.java Wed Jun 08 14:30:27 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.*; @@ -34,11 +36,11 @@ private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; - private int monitor; + private int monitorIndex; - public MonitorAddress(int monitor, Graph graph) { + public MonitorAddress(int monitorIndex, Graph graph) { super(CiKind.Word, INPUT_COUNT, SUCCESSOR_COUNT, graph); - this.monitor = monitor; + this.monitorIndex = monitorIndex; } @Override @@ -46,18 +48,31 @@ v.visitMonitorAddress(this); } - public int monitor() { - return monitor; + public int monitorIndex() { + return monitorIndex; + } + + public void setMonitorIndex(int monitorIndex) { + this.monitorIndex = monitorIndex; } @Override public void print(LogStream out) { - out.print("monitor_address (").print(monitor()).print(")"); + out.print("monitor_address (").print(monitorIndex()).print(")"); + } + + + + @Override + public Map getDebugProperties() { + Map properties = super.getDebugProperties(); + properties.put("monitorIndex", monitorIndex); + return properties; } @Override public Node copy(Graph into) { - MonitorAddress x = new MonitorAddress(monitor, into); + MonitorAddress x = new MonitorAddress(monitorIndex, into); return x; } } diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Wed Jun 08 14:30:27 2011 +0200 @@ -31,7 +31,7 @@ public class DeadCodeEliminationPhase extends Phase { private NodeBitMap alive; - private NodeWorklist worklist; + private NodeFlood flood; private Graph graph; public int deletedNodeCount; @@ -40,9 +40,9 @@ protected void run(Graph graph) { this.graph = graph; this.alive = graph.createNodeBitMap(); - this.worklist = graph.createNodeWorklist(); + this.flood = graph.createNodeFlood(); - worklist.add(graph.start()); + flood.add(graph.start()); iterateSuccessors(); disconnectCFGNodes(); @@ -65,20 +65,20 @@ } private void iterateSuccessors() { - for (Node current : worklist) { + for (Node current : flood) { for (Node successor : current.successors()) { - worklist.add(successor); + flood.add(successor); } } } private void disconnectCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) { + if (node != Node.Null && !flood.isMarked(node) && isCFG(node)) { // iterate backwards so that the predecessor indexes in removePhiPredecessor are correct for (int i = node.successors().size() - 1; i >= 0; i--) { Node successor = node.successors().get(i); - if (successor != Node.Null && worklist.isMarked(successor)) { + if (successor != Node.Null && flood.isMarked(successor)) { if (successor instanceof Merge) { ((Merge) successor).removePhiPredecessor(node); } @@ -92,7 +92,7 @@ private void deleteCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) { + if (node != Node.Null && !flood.isMarked(node) && isCFG(node)) { node.delete(); deletedNodeCount++; } @@ -101,22 +101,22 @@ private void iterateInputs() { for (Node node : graph.getNodes()) { - if (node != Node.Null && worklist.isMarked(node)) { + if (node != Node.Null && flood.isMarked(node)) { for (Node input : node.inputs()) { - worklist.add(input); + flood.add(input); } } } - for (Node current : worklist) { + for (Node current : flood) { for (Node input : current.inputs()) { - worklist.add(input); + flood.add(input); } } } private void disconnectNonCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) { + if (node != Node.Null && !flood.isMarked(node) && !isCFG(node)) { node.inputs().clearAll(); } } @@ -124,7 +124,7 @@ private void deleteNonCFGNodes() { for (Node node : graph.getNodes()) { - if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) { + if (node != Node.Null && !flood.isMarked(node) && !isCFG(node)) { node.delete(); deletedNodeCount++; } diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Wed Jun 08 14:30:27 2011 +0200 @@ -54,37 +54,37 @@ inliningSize += method.code().length; } + static HashMap methodCount = new HashMap(); @Override protected void run(Graph graph) { inliningSize = compilation.method.code().length; int iterations = C1XOptions.MaximumRecursiveInlineLevel; + + do { - for (Node node : graph.getNodes()) { - if (node instanceof Invoke) { - Invoke invoke = (Invoke) node; - RiMethod target = invoke.target; - if (!checkInliningConditions(invoke) || !target.isResolved() || Modifier.isNative(target.accessFlags())) { - continue; + for (Invoke invoke : graph.getNodes(Invoke.class)) { + RiMethod target = invoke.target; + if (!checkInliningConditions(invoke) || !target.isResolved() || Modifier.isNative(target.accessFlags())) { + continue; + } + if (target.canBeStaticallyBound()) { + if (checkInliningConditions(invoke.target)) { + addToQueue(invoke, invoke.target); } - if (target.canBeStaticallyBound()) { - if (checkInliningConditions(invoke.target)) { - addToQueue(invoke, invoke.target); - } - } else { - RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); - if (concrete != null && concrete.isResolved() && !Modifier.isNative(concrete.accessFlags())) { - if (checkInliningConditions(concrete)) { - if (C1XOptions.TraceInlining) { - System.out.println("registering concrete method assumption..."); - } - compilation.assumptions.recordConcreteMethod(invoke.target, concrete); - addToQueue(invoke, concrete); + } else { + RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target); + if (concrete != null && concrete.isResolved() && !Modifier.isNative(concrete.accessFlags())) { + if (checkInliningConditions(concrete)) { + if (C1XOptions.TraceInlining) { + System.out.println("registering concrete method assumption..."); } + compilation.assumptions.recordConcreteMethod(invoke.target, concrete); + addToQueue(invoke, concrete); } } - if (inliningSize > C1XOptions.MaximumInstructionCount) { - break; - } + } + if (inliningSize > C1XOptions.MaximumInstructionCount) { + break; } } @@ -97,6 +97,12 @@ while ((invoke = invokes.poll()) != null) { RiMethod method = methods.remove(); inlineMethod(invoke, method); + + if (methodCount.get(method) == null) { + methodCount.put(method, 1); + } else { + methodCount.put(method, methodCount.get(method) + 1); + } } DeadCodeEliminationPhase dce = new DeadCodeEliminationPhase(); dce.apply(graph); @@ -112,6 +118,16 @@ break; } } while(--iterations > 0); + + int inlined = 0; + int duplicate = 0; + for (Map.Entry entry : methodCount.entrySet()) { + inlined += entry.getValue(); + duplicate += entry.getValue() - 1; + } + if (inlined > 0) { + System.out.printf("overhead_: %d (%5.3f %%)\n", duplicate, duplicate * 100.0 / inlined); + } } private boolean checkInliningConditions(Invoke invoke) { @@ -213,6 +229,17 @@ Map duplicates = compilation.graph.addDuplicate(nodes, replacements); + int monitorIndexDelta = stateAfter.locksSize(); + if (monitorIndexDelta > 0) { + System.out.println("Adjusting locks"); + for (Map.Entry entry : duplicates.entrySet()) { + if (entry.getValue() instanceof MonitorAddress) { + MonitorAddress address = (MonitorAddress) entry.getValue(); + address.setMonitorIndex(address.monitorIndex() + monitorIndexDelta); + } + } + } + if (returnNode != null) { List usages = new ArrayList(invoke.usages()); for (Node usage : usages) { diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java --- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Wed Jun 08 13:06:45 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java Wed Jun 08 14:30:27 2011 +0200 @@ -26,6 +26,7 @@ import java.util.Collection; import java.util.Collections; import java.util.HashMap; +import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Map.Entry; @@ -53,6 +54,53 @@ return Collections.unmodifiableList(nodes); } + public static class TypedNodeIterator implements Iterator { + private final Class type; + private final Iterator iter; + private Node nextNode; + + public TypedNodeIterator(Class type, Iterator iter) { + this.type = type; + this.iter = iter; + forward(); + } + + private void forward() { + do { + if (!iter.hasNext()) { + nextNode = null; + return; + } + nextNode = iter.next(); + } while (nextNode == null || !type.isInstance(nextNode)); + } + + public boolean hasNext() { + return nextNode != null; + } + + @SuppressWarnings("unchecked") + public T next() { + try { + return (T) nextNode; + } finally { + forward(); + } + } + + public void remove() { + throw new UnsupportedOperationException(); + } + } + + public Iterable getNodes(final Class type) { + return new Iterable() { + public Iterator iterator() { + return new TypedNodeIterator(type, nodes.iterator()); + } + }; + } + int register(Node node) { int id = nextId++; nodes.add(id, node); @@ -75,8 +123,8 @@ return new NodeMap(this); } - public NodeWorklist createNodeWorklist() { - return new NodeWorklist(this); + public NodeFlood createNodeFlood() { + return new NodeFlood(this); } public Map addDuplicate(Collection nodes, Map replacements) { diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeFlood.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeFlood.java Wed Jun 08 14:30:27 2011 +0200 @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2011, 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.graph; + +import java.util.ArrayDeque; +import java.util.Iterator; +import java.util.Queue; + + +public class NodeFlood implements Iterable { + private final NodeBitMap visited; + private final Queue worklist; + + NodeFlood(Graph graph) { + visited = graph.createNodeBitMap(); + worklist = new ArrayDeque(); + } + + public void add(Node node) { + if (node != null && !visited.isMarked(node)) { + visited.mark(node); + worklist.add(node); + } + } + + public boolean isMarked(Node node) { + return visited.isMarked(node); + } + + private static class QueueConsumingIterator implements Iterator { + private final Queue queue; + + public QueueConsumingIterator(Queue queue) { + this.queue = queue; + } + + @Override + public boolean hasNext() { + return !queue.isEmpty(); + } + + @Override + public Node next() { + return queue.remove(); + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + } + + @Override + public Iterator iterator() { + return new QueueConsumingIterator(worklist); + } + + private static class UnmarkedNodeIterator implements Iterator { + private final NodeBitMap visited; + private Iterator nodes; + private Node nextNode; + + public UnmarkedNodeIterator(NodeBitMap visited, Iterator nodes) { + this.visited = visited; + this.nodes = nodes; + forward(); + } + + private void forward() { + do { + if (!nodes.hasNext()) { + nextNode = null; + return; + } + nextNode = nodes.next(); + } while (visited.isMarked(nextNode)); + } + + @Override + public boolean hasNext() { + return nextNode != null; + } + + @Override + public Node next() { + try { + return nextNode; + } finally { + forward(); + } + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + + } + + public Iterable unmarkedNodes() { + return new Iterable() { + @Override + public Iterator iterator() { + return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator()); + } + }; + } +} diff -r 693e4e92346b -r 7eec76f3e39e graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorklist.java --- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeWorklist.java Wed Jun 08 13:06:45 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,128 +0,0 @@ -/* - * Copyright (c) 2011, 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.graph; - -import java.util.ArrayDeque; -import java.util.Iterator; -import java.util.Queue; - - -public class NodeWorklist implements Iterable { - private final NodeBitMap visited; - private final Queue worklist; - - NodeWorklist(Graph graph) { - visited = graph.createNodeBitMap(); - worklist = new ArrayDeque(); - } - - public void add(Node node) { - if (node != null && !visited.isMarked(node)) { - visited.mark(node); - worklist.add(node); - } - } - - public boolean isMarked(Node node) { - return visited.isMarked(node); - } - - private static class QueueConsumingIterator implements Iterator { - private final Queue queue; - - public QueueConsumingIterator(Queue queue) { - this.queue = queue; - } - - @Override - public boolean hasNext() { - return !queue.isEmpty(); - } - - @Override - public Node next() { - return queue.remove(); - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - } - - @Override - public Iterator iterator() { - return new QueueConsumingIterator(worklist); - } - - private static class UnmarkedNodeIterator implements Iterator { - private final NodeBitMap visited; - private Iterator nodes; - private Node nextNode; - - public UnmarkedNodeIterator(NodeBitMap visited, Iterator nodes) { - this.visited = visited; - this.nodes = nodes; - forward(); - } - - private void forward() { - do { - if (!nodes.hasNext()) { - nextNode = null; - return; - } - nextNode = nodes.next(); - } while (visited.isMarked(nextNode)); - } - - @Override - public boolean hasNext() { - return nextNode != null; - } - - @Override - public Node next() { - try { - return nextNode; - } finally { - forward(); - } - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - - } - - public Iterable unmarkedNodes() { - return new Iterable() { - @Override - public Iterator iterator() { - return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator()); - } - }; - } -}