# HG changeset patch # User Thomas Wuerthinger # Date 1379370601 -7200 # Node ID 77d9f12797c5bbade2bea3a9796fe8eca5b9a8aa # Parent 8505bcff4bdc9f314a0da4b188cfd22ea3d20d73 Use NodeMap in inlining utility when number of nodes is high. diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Tue Sep 17 00:30:01 2013 +0200 @@ -188,7 +188,7 @@ */ public Graph copy(String newName) { Graph copy = new Graph(newName); - copy.addDuplicates(getNodes(), (Map) null); + copy.addDuplicates(getNodes(), this, this.getNodeCount(), (Map) null); return copy; } @@ -712,14 +712,14 @@ * @param replacementsMap the replacement map (can be null if no replacement is to be performed) * @return a map which associates the original nodes from {@code nodes} to their duplicates */ - public Map addDuplicates(Iterable newNodes, Map replacementsMap) { + public Map addDuplicates(Iterable newNodes, final Graph oldGraph, int estimatedNodeCount, Map replacementsMap) { DuplicationReplacement replacements; if (replacementsMap == null) { replacements = null; } else { replacements = new MapReplacement(replacementsMap); } - return addDuplicates(newNodes, replacements); + return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements); } public interface DuplicationReplacement { @@ -744,7 +744,7 @@ } @SuppressWarnings("all") - public Map addDuplicates(Iterable newNodes, DuplicationReplacement replacements) { - return NodeClass.addGraphDuplicate(this, newNodes, replacements); + public Map addDuplicates(Iterable newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) { + return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements); } } diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Tue Sep 17 00:30:01 2013 +0200 @@ -26,7 +26,6 @@ import java.lang.reflect.*; import java.util.*; -import java.util.Map.Entry; import java.util.concurrent.*; import com.oracle.graal.debug.*; @@ -1048,8 +1047,8 @@ return nameTemplate; } - static Map addGraphDuplicate(final Graph graph, Iterable nodes, final DuplicationReplacement replacements) { - final IdentityHashMap newNodes = new IdentityHashMap<>(); + static Map addGraphDuplicate(final Graph graph, final Graph oldGraph, int estimatedNodeCount, Iterable nodes, final DuplicationReplacement replacements) { + final Map newNodes = (estimatedNodeCount > (oldGraph.getNodeCount() + oldGraph.getDeletedNodeCount() >> 4)) ? new NodeNodeMap(oldGraph) : new IdentityHashMap(); createNodeDuplicates(graph, nodes, replacements, newNodes); DuplicationReplacement replacementClosure = new DuplicationReplacement() { @@ -1074,9 +1073,8 @@ }; // re-wire inputs - for (Entry entry : newNodes.entrySet()) { - Node oldNode = entry.getKey(); - Node node = entry.getValue(); + for (Node oldNode : nodes) { + Node node = newNodes.get(oldNode); NodeClass oldNodeClass = oldNode.getNodeClass(); NodeClass nodeClass = node.getNodeClass(); if (oldNodeClass == nodeClass && (replacements == null || replacements.replacement(oldNode) == oldNode)) { @@ -1089,7 +1087,7 @@ return newNodes; } - private static void createNodeDuplicates(final Graph graph, Iterable nodes, final DuplicationReplacement replacements, final IdentityHashMap newNodes) { + private static void createNodeDuplicates(final Graph graph, Iterable nodes, final DuplicationReplacement replacements, final Map newNodes) { for (Node node : nodes) { if (node != null) { assert !node.isDeleted() : "trying to duplicate deleted node: " + node; @@ -1110,8 +1108,8 @@ } } - private static void transferValuesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final IdentityHashMap newNodes, Node oldNode, Node node, - NodeClass oldNodeClass, NodeClass nodeClass) { + private static void transferValuesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final Map newNodes, Node oldNode, Node node, NodeClass oldNodeClass, + NodeClass nodeClass) { for (NodeClassIterator iter = oldNode.inputs().iterator(); iter.hasNext();) { Position pos = iter.nextPosition(); if (!nodeClass.isValid(pos, oldNodeClass)) { diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java Tue Sep 17 00:30:01 2013 +0200 @@ -26,11 +26,11 @@ import java.util.*; import java.util.Map.Entry; -public final class NodeMap { +public class NodeMap { private final Graph graph; private final boolean autogrow; - private Object[] values; + protected Object[] values; public NodeMap(Graph graph) { this(graph, false); @@ -54,6 +54,29 @@ return (T) values[node.id()]; } + public boolean isEmpty() { + return !entries().iterator().hasNext(); + } + + public boolean containsKey(Object key) { + if (key instanceof Node) { + Node node = (Node) key; + if (node.graph() == graph()) { + return get(node) != null; + } + } + return false; + } + + public boolean containsValue(Object value) { + for (Object o : values) { + if (o == value) { + return true; + } + } + return false; + } + public Graph graph() { return graph; } diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeNodeMap.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeNodeMap.java Tue Sep 17 00:30:01 2013 +0200 @@ -0,0 +1,75 @@ +/* + * 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.graal.graph; + +import java.util.*; + +public final class NodeNodeMap extends NodeMap implements Map { + + public NodeNodeMap(Graph graph) { + super(graph, true); + } + + public NodeNodeMap(NodeNodeMap copyFrom) { + super(copyFrom); + } + + public Node get(Object key) { + return super.get((Node) key); + } + + public Node put(Node key, Node value) { + Node oldValue = super.get(key); + super.set(key, value); + return oldValue; + } + + public Node remove(Object key) { + throw new UnsupportedOperationException("Cannot remove keys from this map"); + } + + public void putAll(Map m) { + for (Entry entry : m.entrySet()) { + put(entry.getKey(), entry.getValue()); + } + } + + public Set keySet() { + throw new UnsupportedOperationException("Cannot get key set from this map"); + } + + public Collection values() { + ArrayList result = new ArrayList<>(this.size()); + for (int i = 0; i < values.length; ++i) { + Object v = values[i]; + if (v != null) { + result.add((Node) v); + } + } + return result; + } + + public Set> entrySet() { + throw new UnsupportedOperationException("Cannot get entry set for this map"); + } +} diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Tue Sep 17 00:30:01 2013 +0200 @@ -131,7 +131,8 @@ } else { dr = null; } - duplicationMap = graph().addDuplicates(original().nodes(), dr); + NodeIterable nodesIterable = original().nodes(); + duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr); finishDuplication(); nodesReady = true; } else { diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Tue Sep 17 00:30:01 2013 +0200 @@ -178,7 +178,7 @@ StructuredGraph copy = new StructuredGraph(newName, newMethod, graphId, entryBCI); HashMap replacements = new HashMap<>(); replacements.put(start, copy.start); - copy.addDuplicates(getNodes(), replacements); + copy.addDuplicates(getNodes(), this, this.getNodeCount(), replacements); return copy; } diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Tue Sep 17 00:30:01 2013 +0200 @@ -1334,7 +1334,7 @@ assert invoke.asNode().successors().first() != null : invoke; assert invoke.asNode().predecessor() != null; - Map duplicates = graph.addDuplicates(nodes, localReplacement); + Map duplicates = graph.addDuplicates(nodes, inlineGraph, inlineGraph.getNodeCount(), localReplacement); FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode); invoke.asNode().replaceAtPredecessor(firstCFGNodeDuplicate); @@ -1377,7 +1377,8 @@ if (stateAfter != null) { FrameState outerFrameState = null; int callerLockDepth = stateAfter.nestedLockDepth(); - for (Node node : duplicates.values()) { + for (Node inlinedNode : inlineGraph.getNodes()) { + Node node = duplicates.get(inlinedNode); if (node instanceof FrameState) { FrameState frameState = (FrameState) node; assert frameState.bci != FrameState.BEFORE_BCI : frameState; @@ -1420,7 +1421,7 @@ if (returnNode != null) { if (returnNode.result() instanceof LocalNode) { returnValue = localReplacement.replacement(returnNode.result()); - } else { + } else if (returnNode.result() != null) { returnValue = duplicates.get(returnNode.result()); } invoke.asNode().replaceAtUsages(returnValue); diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Tue Sep 17 00:30:01 2013 +0200 @@ -260,11 +260,11 @@ for (final AbstractEndNode forwardEnd : merge.forwardEnds()) { Map duplicates; if (replacements == null || replacements.get(endIndex) == null) { - duplicates = graph.addDuplicates(duplicatedNodes, (DuplicationReplacement) null); + duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), (DuplicationReplacement) null); } else { HashMap replace = new HashMap<>(); replace.put(replacements.get(endIndex).object(), replacements.get(endIndex)); - duplicates = graph.addDuplicates(duplicatedNodes, replace); + duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), replace); } for (Map.Entry phi : bottomPhis.entrySet()) { phi.getValue().initializeValueAt(merge.forwardEndIndex(forwardEnd), (ValueNode) duplicates.get(phi.getKey())); diff -r 8505bcff4bdc -r 77d9f12797c5 graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java --- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Mon Sep 16 23:17:56 2013 +0200 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Tue Sep 17 00:30:01 2013 +0200 @@ -420,7 +420,7 @@ placeholders[i] = placeholder; } } - snippetCopy.addDuplicates(snippetGraph.getNodes(), nodeReplacements); + snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements); Debug.dump(snippetCopy, "Before specialization"); if (!nodeReplacements.isEmpty()) { @@ -750,7 +750,7 @@ FixedNode firstCFGNode = entryPointNode.next(); StructuredGraph replaceeGraph = replacee.graph(); IdentityHashMap replacements = bind(replaceeGraph, runtime, args); - Map duplicates = replaceeGraph.addDuplicates(nodes, replacements); + Map duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements); Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method()); // Re-wire the control flow graph around the replacee @@ -791,7 +791,7 @@ if (returnNode != null) { if (returnNode.result() instanceof LocalNode) { returnValue = (ValueNode) replacements.get(returnNode.result()); - } else { + } else if (returnNode.result() != null) { returnValue = (ValueNode) duplicates.get(returnNode.result()); } Node returnDuplicate = duplicates.get(returnNode); @@ -844,7 +844,7 @@ FixedNode firstCFGNode = entryPointNode.next(); StructuredGraph replaceeGraph = replacee.graph(); IdentityHashMap replacements = bind(replaceeGraph, runtime, args); - Map duplicates = replaceeGraph.addDuplicates(nodes, replacements); + Map duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements); Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method()); FixedWithNextNode lastFixedNode = tool.lastFixedNode();