# HG changeset patch # User Thomas Wuerthinger # Date 1338996015 -7200 # Node ID 80abea6e5e27adcfe39b66e454fdc1d041655859 # Parent c78cf0abfdff5dee007e8d3780cecfef938ef321# Parent e26e6dca0bcfa02d5e5210dae916767d221c1ee7 Merge. diff -r c78cf0abfdff -r 80abea6e5e27 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Wed Jun 06 17:20:07 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Wed Jun 06 17:20:15 2012 +0200 @@ -24,9 +24,11 @@ import java.util.*; +import com.oracle.graal.graph.iterators.*; -public final class NodeBitMap implements Iterable{ + +public final class NodeBitMap extends NodeIterable{ private final boolean autoGrow; private final BitMap bitMap; private final Graph graph; @@ -186,4 +188,19 @@ public NodeBitMap copy() { return new NodeBitMap(graph, autoGrow, bitMap.copy()); } + + @Override + public NodeIterable distinct() { + return this; + } + + @Override + public int count() { + return bitMap.cardinality(); + } + + @Override + public boolean contains(Node node) { + return isMarked(node); + } } diff -r c78cf0abfdff -r 80abea6e5e27 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Wed Jun 06 17:20:07 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Wed Jun 06 17:20:15 2012 +0200 @@ -46,7 +46,7 @@ public FilteredNodeIterable nonNull() { return new FilteredNodeIterable<>(this).and(NodePredicates.isNotNull()); } - public FilteredNodeIterable distinct() { + public NodeIterable distinct() { return new FilteredNodeIterable<>(this).distinct(); } public List snapshot() { diff -r c78cf0abfdff -r 80abea6e5e27 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java Wed Jun 06 17:20:07 2012 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/CheckCastSnippets.java Wed Jun 06 17:20:15 2012 +0200 @@ -23,12 +23,11 @@ package com.oracle.graal.hotspot.snippets; import static com.oracle.graal.hotspot.snippets.ArrayCopySnippets.*; import static com.oracle.graal.hotspot.snippets.CheckCastSnippets.Counter.*; -import static com.oracle.graal.hotspot.snippets.CheckCastSnippets.TemplateFlag.*; -import static com.oracle.graal.snippets.SnippetTemplate.*; +import static com.oracle.graal.snippets.Snippet.Arguments.*; +import static com.oracle.graal.snippets.Snippet.Multiple.*; import java.io.*; import java.util.*; -import java.util.concurrent.*; import sun.misc.*; @@ -44,6 +43,10 @@ import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.snippets.*; +import com.oracle.graal.snippets.Snippet.Arguments; +import com.oracle.graal.snippets.Snippet.Constant; +import com.oracle.graal.snippets.Snippet.Parameter; +import com.oracle.graal.snippets.SnippetTemplate.Cache; import com.oracle.graal.snippets.nodes.*; import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; @@ -53,7 +56,7 @@ * Snippets used for implementing the type test of a checkcast instruction. * * The test first checks against the profiled types (if any) and then implements the - * checks described in paper + * checks described in the paper * Fast subtype checking in the HotSpot JVM by Cliff Click and John Rose. */ public class CheckCastSnippets implements SnippetsInterface { @@ -62,7 +65,7 @@ * Type test used when the type being tested against is a final type. */ @Snippet - public static Object checkcastExact(Object object, Object exactHub, boolean checkNull) { + public static Object checkcastExact(@Parameter("object") Object object, @Parameter("exactHub") Object exactHub, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { return object; } @@ -81,7 +84,7 @@ * first. */ @Snippet - public static Object checkcastPrimary(Object hub, Object object, boolean checkNull, int superCheckOffset) { + public static Object checkcastPrimary(@Parameter("hub") Object hub, @Parameter("object") Object object, @Constant("checkNull") boolean checkNull, @Constant("superCheckOffset") int superCheckOffset) { if (checkNull && object == null) { return object; } @@ -96,15 +99,15 @@ * Type test used when the type being tested against is a restricted secondary type. */ @Snippet - public static Object checkcastSecondary(Object hub, Object object, Object[] hintHubs, boolean checkNull) { + public static Object checkcastSecondary(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); // if we get an exact match: succeed immediately ExplodeLoopNode.explodeLoop(); - for (int i = 0; i < hintHubs.length; i++) { - Object hintHub = hintHubs[i]; + for (int i = 0; i < hints.length; i++) { + Object hintHub = hints[i]; if (hintHub == objectHub) { return object; } @@ -120,15 +123,15 @@ * in an object array store check). */ @Snippet - public static Object checkcastUnknown(Object hub, Object object, Object[] hintHubs, boolean checkNull) { + public static Object checkcastUnknown(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("checkNull") boolean checkNull) { if (checkNull && object == null) { return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); // if we get an exact match: succeed immediately ExplodeLoopNode.explodeLoop(); - for (int i = 0; i < hintHubs.length; i++) { - Object hintHub = hintHubs[i]; + for (int i = 0; i < hints.length; i++) { + Object hintHub = hints[i]; if (hintHub == objectHub) { return object; } @@ -247,13 +250,13 @@ * Type test used when {@link GraalOptions#CheckcastCounters} is enabled. */ @Snippet - public static Object checkcastCounters(Object hub, Object object, Object[] hintHubs, boolean hintsAreExact) { + public static Object checkcastCounters(@Parameter("hub") Object hub, @Parameter("object") Object object, @Parameter(value = "hints", multiple = true) Object[] hints, @Constant("hintsAreExact") boolean hintsAreExact) { if (object == null) { isNull.inc(); return object; } Object objectHub = UnsafeLoadNode.loadObject(object, 0, hubOffset(), true); - if (hintHubs.length == 0) { + if (hints.length == 0) { noHints.inc(); if (!checkUnknownSubType(hub, objectHub)) { exception.inc(); @@ -262,8 +265,8 @@ } else { // if we get an exact match: succeed immediately ExplodeLoopNode.explodeLoop(); - for (int i = 0; i < hintHubs.length; i++) { - Object hintHub = hintHubs[i]; + for (int i = 0; i < hints.length; i++) { + Object hintHub = hints[i]; if (hintHub == objectHub) { if (hintsAreExact) { exactType.inc(); @@ -343,43 +346,9 @@ } } - public enum TemplateFlag { - CHECK_NULL, - EXACT_HINTS, - COUNTERS, - PRIMARY_SUPER, - SECONDARY_SUPER, - UNKNOWN_SUPER; - - public int bit(boolean value) { - if (value) { - return bit(); - } - return 0; - } - - public boolean bool(int flags) { - return (flags & bit()) != 0; - } - - static final int FLAGS_BITS = values().length; - static final int FLAGS_MASK = (1 << FLAGS_BITS) - 1; - - static final int NHINTS_SHIFT = FLAGS_BITS; - static final int NHINTS_BITS = 3; - static final int SUPER_CHECK_OFFSET_SHIFT = NHINTS_SHIFT + NHINTS_BITS; - - public int bit() { - return 1 << ordinal(); - } - } - - /** - * Templates for partially specialized checkcast snippet graphs. - */ public static class Templates { - private final ConcurrentHashMap templates; + private final Cache cache; private final RiResolvedMethod exact; private final RiResolvedMethod primary; private final RiResolvedMethod secondary; @@ -389,7 +358,7 @@ public Templates(RiRuntime runtime) { this.runtime = runtime; - this.templates = new ConcurrentHashMap<>(); + this.cache = new Cache(runtime); try { exact = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastExact", Object.class, Object.class, boolean.class)); primary = runtime.getRiMethod(CheckCastSnippets.class.getDeclaredMethod("checkcastPrimary", Object.class, Object.class, boolean.class, int.class)); @@ -402,110 +371,52 @@ } /** - * Interface for lazily creating a snippet template. - */ - abstract static class Factory { - abstract SnippetTemplate create(HotSpotKlassOop[] hints, int flags); - } - - /** - * Gets a template from the template cache, creating and installing it first if necessary. - */ - private SnippetTemplate getTemplate(int nHints, int flags, int superCheckOffset, Factory factory) { - assert (flags & ~FLAGS_MASK) == 0; - assert nHints >= 0 && nHints < (1 << NHINTS_BITS) - 1 : "nHints out of range"; - assert superCheckOffset >= 0 && superCheckOffset == ((superCheckOffset << SUPER_CHECK_OFFSET_SHIFT) >>> SUPER_CHECK_OFFSET_SHIFT) : "superCheckOffset out of range"; - Integer key = superCheckOffset << SUPER_CHECK_OFFSET_SHIFT | nHints << NHINTS_SHIFT | flags; - SnippetTemplate result = templates.get(key); - if (result == null) { - HotSpotKlassOop[] hints = new HotSpotKlassOop[nHints]; - for (int i = 0; i < hints.length; i++) { - hints[i] = new HotSpotKlassOop(null, Templates.class); - } - result = factory.create(hints, flags); - //System.err.println(result); - templates.put(key, result); - } - return result; - } - - private static HotSpotKlassOop[] createHintHubs(TypeCheckHints hints) { - HotSpotKlassOop[] hintHubs = new HotSpotKlassOop[hints.types.length]; - for (int i = 0; i < hintHubs.length; i++) { - hintHubs[i] = ((HotSpotType) hints.types[i]).klassOop(); - } - return hintHubs; - } - - /** * Lowers a checkcast node. */ public void lower(CheckCastNode checkcast, CiLoweringTool tool) { StructuredGraph graph = (StructuredGraph) checkcast.graph(); ValueNode hub = checkcast.targetClassInstruction(); ValueNode object = checkcast.object(); - TypeCheckHints hints = new TypeCheckHints(checkcast.targetClass(), checkcast.profile(), tool.assumptions(), GraalOptions.CheckcastMinHintHitProbability, GraalOptions.CheckcastMaxHints); - Debug.log("Lowering checkcast in %s: node=%s, hintsHubs=%s, exact=%b", graph, checkcast, Arrays.toString(hints.types), hints.exact); + TypeCheckHints hintInfo = new TypeCheckHints(checkcast.targetClass(), checkcast.profile(), tool.assumptions(), GraalOptions.CheckcastMinHintHitProbability, GraalOptions.CheckcastMaxHints); + final HotSpotTypeResolvedImpl target = (HotSpotTypeResolvedImpl) checkcast.targetClass(); + boolean checkNull = !object.stamp().nonNull(); + Arguments arguments; + SnippetTemplate.Key key; - final HotSpotTypeResolvedImpl target = (HotSpotTypeResolvedImpl) checkcast.targetClass(); - int flags = CHECK_NULL.bit(!object.stamp().nonNull()); if (GraalOptions.CheckcastCounters) { - HotSpotKlassOop[] hintHubs = createHintHubs(hints); - SnippetTemplate template = getTemplate(hintHubs.length, flags | EXACT_HINTS.bit(hints.exact) | COUNTERS.bit(), 0, new Factory() { - @SuppressWarnings("hiding") - @Override - SnippetTemplate create(HotSpotKlassOop[] hints, int flags) { - // checkcastCounters(Object hub, Object object, Object[] hintHubs, boolean hintsAreExact) - return SnippetTemplate.create(runtime, counters, _, _, hints, EXACT_HINTS.bool(flags)); - } - }); - template.instantiate(runtime, checkcast, checkcast, hub, object, hintHubs, hints.exact); + HotSpotKlassOop[] hints = createHints(hintInfo); + key = new SnippetTemplate.Key(counters).add("hints", multiple(Object.class, hints.length)).add("hintsAreExact", hintInfo.exact); + arguments = arguments("hub", hub).add("object", object).add("hints", hints); } else if (target == null) { - HotSpotKlassOop[] hintHubs = createHintHubs(hints); - SnippetTemplate template = getTemplate(hintHubs.length, flags | UNKNOWN_SUPER.bit(), 0, new Factory() { - @SuppressWarnings("hiding") - @Override - SnippetTemplate create(HotSpotKlassOop[] hints, int flags) { - // checkcastUnknown(Object hub, Object object, Object[] hintHubs, boolean checkNull) - return SnippetTemplate.create(runtime, unknown, _, _, hints, CHECK_NULL.bool(flags)); - } - }); - template.instantiate(runtime, checkcast, checkcast, hub, object, hintHubs); - } else if (hints.exact) { - HotSpotKlassOop[] hintHubs = createHintHubs(hints); - assert hintHubs.length == 1; - SnippetTemplate template = getTemplate(hintHubs.length, flags | EXACT_HINTS.bit(), 0, new Factory() { - @SuppressWarnings("hiding") - @Override - SnippetTemplate create(HotSpotKlassOop[] hints, int flags) { - // checkcastExact(Object object, Object exactHub, boolean checkNull) - return SnippetTemplate.create(runtime, exact, _, hints[0], CHECK_NULL.bool(flags)); - } - }); - template.instantiate(runtime, checkcast, checkcast, object, hintHubs[0]); + HotSpotKlassOop[] hints = createHints(hintInfo); + key = new SnippetTemplate.Key(unknown).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); + arguments = arguments("hub", hub).add("object", object).add("hints", hints); + } else if (hintInfo.exact) { + HotSpotKlassOop[] hints = createHints(hintInfo); + assert hints.length == 1; + key = new SnippetTemplate.Key(exact).add("checkNull", checkNull); + arguments = arguments("object", object).add("exactHub", hints[0]); } else if (target.isPrimaryType()) { - SnippetTemplate template = getTemplate(0, flags | PRIMARY_SUPER.bit(), target.superCheckOffset(), new Factory() { - @SuppressWarnings("hiding") - @Override - SnippetTemplate create(HotSpotKlassOop[] hints, int flags) { - // checkcastPrimary(Object hub, Object object, boolean checkNull, int superCheckOffset) - return SnippetTemplate.create(runtime, primary, _, _, CHECK_NULL.bool(flags), target.superCheckOffset()); - } - }); - template.instantiate(runtime, checkcast, checkcast, hub, object); + key = new SnippetTemplate.Key(primary).add("checkNull", checkNull).add("superCheckOffset", target.superCheckOffset()); + arguments = arguments("hub", hub).add("object", object); } else { - HotSpotKlassOop[] hintHubs = createHintHubs(hints); - SnippetTemplate template = getTemplate(hintHubs.length, flags | SECONDARY_SUPER.bit(), 0, new Factory() { - @SuppressWarnings("hiding") - @Override - SnippetTemplate create(HotSpotKlassOop[] hints, int flags) { - // checkcastSecondary(Object hub, Object object, Object[] hintHubs, boolean checkNull) - return SnippetTemplate.create(runtime, secondary, _, _, hints, CHECK_NULL.bool(flags)); - } - }); - template.instantiate(runtime, checkcast, checkcast, hub, object, hintHubs); + HotSpotKlassOop[] hints = createHints(hintInfo); + key = new SnippetTemplate.Key(secondary).add("hints", multiple(Object.class, hints.length)).add("checkNull", checkNull); + arguments = arguments("hub", hub).add("object", object).add("hints", hints); } + + SnippetTemplate template = cache.get(key); + Debug.log("Lowering checkcast in %s: node=%s, template=%s, arguments=%s", graph, checkcast, template, arguments); + template.instantiate(runtime, checkcast, checkcast, arguments); new DeadCodeEliminationPhase().apply(graph); } + + private static HotSpotKlassOop[] createHints(TypeCheckHints hints) { + HotSpotKlassOop[] hintHubs = new HotSpotKlassOop[hints.types.length]; + for (int i = 0; i < hintHubs.length; i++) { + hintHubs[i] = ((HotSpotType) hints.types[i]).klassOop(); + } + return hintHubs; + } } } diff -r c78cf0abfdff -r 80abea6e5e27 graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java Wed Jun 06 17:20:07 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/Snippet.java Wed Jun 06 17:20:15 2012 +0200 @@ -23,8 +23,12 @@ package com.oracle.graal.snippets; import java.lang.annotation.*; +import java.lang.reflect.*; +import java.util.*; +import java.util.Map.Entry; import com.oracle.graal.graph.Node.NodeIntrinsic; +import com.oracle.graal.snippets.nodes.*; /** * A snippet is a Graal graph expressed as a Java source method. Graal snippets can be used for: @@ -37,4 +41,113 @@ @Retention(RetentionPolicy.RUNTIME) @Target(ElementType.METHOD) public @interface Snippet { + + /** + * Denotes a snippet parameter that will be bound during snippet + * template {@linkplain SnippetTemplate#instantiate instantiation}. + */ + @Retention(RetentionPolicy.RUNTIME) + @Target(ElementType.PARAMETER) + public @interface Parameter { + /** + * The name of this parameter. + */ + String value(); + + /** + * Determines if this parameter represents 0 or more arguments. During snippet template creation, + * its value must be an array whose length specifies the number of arguments (the contents + * of the array are ignored) bound to the parameter during {@linkplain SnippetTemplate#instantiate instantiation}. + * + * Such a parameter must be used in a counted loop in the snippet preceded by a call + * to {@link ExplodeLoopNode#explodeLoop()}. The counted looped must be a + * standard iteration over all the loop's elements (i.e. {@code for (T e : arr) ... }). + */ + boolean multiple() default false; + } + + /** + * Denotes a snippet parameter that will bound to a constant value during + * snippet template {@linkplain SnippetTemplate#instantiate instantiation}. + */ + @Retention(RetentionPolicy.RUNTIME) + @Target(ElementType.PARAMETER) + public @interface Constant { + /** + * The name of this constant. + */ + String value(); + } + + /** + * Arguments used to instantiate a template. + */ + public static class Arguments implements Iterable> { + private final HashMap map = new HashMap<>(); + + public static Arguments arguments(String name, Object value) { + return new Arguments().add(name, value); + } + + public Arguments add(String name, Object value) { + assert !map.containsKey(name); + map.put(name, value); + return this; + } + + public int length() { + return map.size(); + } + + @Override + public Iterator> iterator() { + return map.entrySet().iterator(); + } + + @Override + public String toString() { + return map.toString(); + } + } + + /** + * Wrapper for the prototype value of a {@linkplain Parameter#multiple() multiple} parameter. + */ + public static class Multiple { + public final Object array; + private final Class componentType; + private final int length; + + public static Multiple multiple(Class componentType, int length) { + return new Multiple(Array.newInstance(componentType, length)); + } + + public Multiple(Object array) { + assert array != null; + this.componentType = array.getClass().getComponentType(); + assert this.componentType != null; + this.length = java.lang.reflect.Array.getLength(array); + this.array = array; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof Multiple) { + Multiple other = (Multiple) obj; + return other.componentType == componentType && + other.length == length; + } + return false; + } + + @Override + public int hashCode() { + return componentType.hashCode() ^ length; + } + + @Override + public String toString() { + return componentType.getName() + "[" + length + "]"; + } + } } diff -r c78cf0abfdff -r 80abea6e5e27 graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 17:20:07 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 17:20:15 2012 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -24,194 +24,257 @@ import java.lang.reflect.*; import java.util.*; +import java.util.Map.Entry; import java.util.concurrent.*; import com.oracle.graal.compiler.loop.*; import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.phases.CanonicalizerPhase.IsImmutablePredicate; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.Verbosity; import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.util.*; +import com.oracle.graal.snippets.Snippet.Arguments; +import com.oracle.graal.snippets.Snippet.Constant; +import com.oracle.graal.snippets.Snippet.Multiple; +import com.oracle.graal.snippets.Snippet.Parameter; import com.oracle.graal.snippets.nodes.*; import com.oracle.max.cri.ci.*; import com.oracle.max.cri.ri.*; /** * A snippet template is a graph created by parsing a snippet method and then - * specialized by binding constants to some of the snippet arguments and applying - * transformations such as canonicalization and loop peeling. + * specialized by binding constants to the snippet's {@link Constant} parameters. + * + * Snippet templates can be managed in a {@link Cache}. */ public class SnippetTemplate { /** - * Special value denoting a non-specialized argument. + * A snippet template key encapsulates the method from which a snippet was built + * and the arguments used to specialized the snippet. + * + * @see Cache */ - public static final Object _ = new Object() { + public static class Key implements Iterable> { + public final RiResolvedMethod method; + private final HashMap map = new HashMap<>(); + private int hash; + + public Key(RiResolvedMethod method) { + this.method = method; + this.hash = method.hashCode(); + } + + public Key add(String name, Object value) { + assert value != null; + assert !map.containsKey(name); + map.put(name, value); + hash = hash ^ name.hashCode() * (value.hashCode() + 1); + return this; + } + + public int length() { + return map.size(); + } + + public Object get(String name) { + return map.get(name); + } + + @Override + public Iterator> iterator() { + return map.entrySet().iterator(); + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof Key) { + Key other = (Key) obj; + return other.method == method && other.map.equals(map); + } + return false; + } + + @Override + public int hashCode() { + return hash; + } + @Override public String toString() { - return "_"; + return CiUtil.format("%h.%n", method) + map.toString(); + } + } + + /** + * A collection of snippet templates accessed by a {@link Key} instance. + */ + public static class Cache { + + private final ConcurrentHashMap templates = new ConcurrentHashMap<>(); + private final RiRuntime runtime; + + + public Cache(RiRuntime runtime) { + this.runtime = runtime; } - }; + + /** + * Gets a template for a given key, creating it first if necessary. + */ + public SnippetTemplate get(final SnippetTemplate.Key key) { + SnippetTemplate template = templates.get(key); + if (template == null) { + template = Debug.scope("SnippetSpecialization", key.method, new Callable() { + @Override + public SnippetTemplate call() throws Exception { + return new SnippetTemplate(runtime, key); + } + }); + //System.out.println(key + " -> " + template); + templates.put(key, template); + } + return template; + } + + } /** * Creates a snippet template. - * - * @param runtime - * @param method the snippet method to create the initial graph from - * @param args the arguments used to specialize the graph */ - public static SnippetTemplate create(final RiRuntime runtime, final RiResolvedMethod method, final Object... args) { - return Debug.scope("SnippetSpecialization", method, new Callable() { - @Override - public SnippetTemplate call() throws Exception { - assert Modifier.isStatic(method.accessFlags()) : "snippet method must be static: " + method; - RiSignature signature = method.signature(); - assert signature.argumentCount(false) == args.length : "snippet method expects " + signature.argumentCount(false) + " arguments, " + args.length + " given"; - StructuredGraph snippetGraph = (StructuredGraph) method.compilerStorage().get(Graph.class); - - final Map constantArrays = new IdentityHashMap<>(); - IsImmutablePredicate immutabilityPredicate = new IsImmutablePredicate() { - public boolean apply(CiConstant constant) { - return constantArrays.containsKey(constant); - } - }; + public SnippetTemplate(RiRuntime runtime, SnippetTemplate.Key key) { + RiResolvedMethod method = key.method; + assert Modifier.isStatic(method.accessFlags()) : "snippet method must be static: " + method; + RiSignature signature = method.signature(); - // Copy snippet graph, replacing parameters with given args in the process - StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method()); - IdentityHashMap replacements = new IdentityHashMap<>(); - replacements.put(snippetGraph.start(), snippetCopy.start()); - int localCount = 0; - for (LocalNode local : snippetGraph.getNodes(LocalNode.class)) { - int index = local.index(); - Object arg = args[index]; - if (arg != _) { - CiKind kind = signature.argumentKindAt(index, false); - assert kind.isObject() || (arg != null && kind.toBoxedJavaClass() == arg.getClass()) : - "arg " + index + " for " + method + " has wrong kind: expected " + kind + ", got " + (arg == null ? "null" : arg.getClass().getSimpleName()); - CiConstant specializationArg = CiConstant.forBoxed(kind, arg); - if (kind.isObject()) { - assert arg == null || signature.argumentTypeAt(index, method.holder()).resolve(method.holder()).toJava().isInstance(arg) : - String.format("argument %d is of wrong type: expected %s, got %s", index, signature.argumentTypeAt(index, method.holder()).resolve(method.holder()).toJava().getName(), arg.getClass().getName()); - if (arg != null) { - if (arg.getClass().isArray()) { - constantArrays.put(specializationArg, specializationArg); - } - } - } + // Copy snippet graph, replacing @Constant parameters with given arguments + StructuredGraph snippetGraph = (StructuredGraph) method.compilerStorage().get(Graph.class); + StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method()); + IdentityHashMap replacements = new IdentityHashMap<>(); + replacements.put(snippetGraph.start(), snippetCopy.start()); - ConstantNode argNode = ConstantNode.forCiConstant(specializationArg, runtime, snippetCopy); - replacements.put(local, argNode); - } - localCount++; + int parameterCount = signature.argumentCount(false); + Parameter[] parameterAnnotations = new Parameter[parameterCount]; + for (int i = 0; i < parameterCount; i++) { + Constant c = CiUtil.getParameterAnnotation(Constant.class, i, method); + if (c != null) { + String name = c.value(); + Object arg = key.get(name); + assert arg != null : method + ": requires a constant named " + name; + CiKind kind = signature.argumentKindAt(i, false); + assert checkConstantArgument(method, signature, i, name, arg, kind); + replacements.put(snippetGraph.getLocal(i), ConstantNode.forCiConstant(CiConstant.forBoxed(kind, arg), runtime, snippetCopy)); + } else { + Parameter p = CiUtil.getParameterAnnotation(Parameter.class, i, method); + assert p != null : method + ": parameter " + i + " must be annotated with either @Constant or @Parameter"; + String name = p.value(); + if (p.multiple()) { + Object multiple = key.get(name); + assert multiple != null : method + ": requires a Multiple named " + name; + assert checkMultipleArgument(method, signature, i, name, multiple); + Object array = ((Multiple) multiple).array; + replacements.put(snippetGraph.getLocal(i), ConstantNode.forObject(array, runtime, snippetCopy)); } - assert localCount == args.length : "snippet argument count mismatch"; - snippetCopy.addDuplicates(snippetGraph.getNodes(), replacements); - - Debug.dump(snippetCopy, "Before specialization"); - - if (!replacements.isEmpty()) { - new CanonicalizerPhase(null, runtime, null, 0, immutabilityPredicate).apply(snippetCopy); - } + parameterAnnotations[i] = p; + } + } + snippetCopy.addDuplicates(snippetGraph.getNodes(), replacements); - boolean exploded = false; - do { - exploded = false; - for (Node node : snippetCopy.getNodes()) { - if (node instanceof ExplodeLoopNode) { - final ExplodeLoopNode explodeLoop = (ExplodeLoopNode) node; - LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); - ControlFlowGraph cfg = ControlFlowGraph.compute(snippetCopy, true, true, false, false); - for (Loop loop : cfg.getLoops()) { - if (loop.loopBegin() == loopBegin) { - SuperBlock wholeLoop = LoopTransformUtil.wholeLoop(loop); - Debug.dump(snippetCopy, "Before exploding loop %s", loopBegin); - int peel = 0; - while (!loopBegin.isDeleted()) { - int mark = snippetCopy.getMark(); - LoopTransformUtil.peel(loop, wholeLoop); - Debug.dump(snippetCopy, "After peel %d", peel); - new CanonicalizerPhase(null, runtime, null, mark, immutabilityPredicate).apply(snippetCopy); - peel++; - } - Debug.dump(snippetCopy, "After exploding loop %s", loopBegin); - exploded = true; - break; - } - } + Debug.dump(snippetCopy, "Before specialization"); + if (!replacements.isEmpty()) { + new CanonicalizerPhase(null, runtime, null, 0, null).apply(snippetCopy); + } - FixedNode explodeLoopNext = explodeLoop.next(); - explodeLoop.clearSuccessors(); - explodeLoop.replaceAtPredecessors(explodeLoopNext); - explodeLoop.replaceAtUsages(null); - GraphUtil.killCFG(explodeLoop); + // Gather the template parameters + parameters = new HashMap<>(); + for (int i = 0; i < parameterCount; i++) { + Parameter p = parameterAnnotations[i]; + if (p != null) { + ValueNode parameter; + if (p.multiple()) { + parameter = null; + assert snippetCopy.getLocal(i) == null; + ConstantNode array = (ConstantNode) replacements.get(snippetGraph.getLocal(i)); + for (LoadIndexedNode loadIndexed : snippetCopy.getNodes(LoadIndexedNode.class)) { + if (loadIndexed.array() == array) { + Debug.dump(snippetCopy, "Before replacing %s", loadIndexed); + LoadMultipleParameterNode lmp = new LoadMultipleParameterNode(array, i, loadIndexed.index(), loadIndexed.stamp()); + StructuredGraph g = (StructuredGraph) loadIndexed.graph(); + g.add(lmp); + g.replaceFixedWithFixed(loadIndexed, lmp); + parameter = lmp; + Debug.dump(snippetCopy, "After replacing %s", loadIndexed); break; } } - } while (exploded); - - // Remove all frame states from inlined snippet graph. Snippets must be atomic (i.e. free - // of side-effects that prevent deoptimizing to a point before the snippet). - for (Node node : snippetCopy.getNodes()) { - if (node instanceof StateSplit) { - StateSplit stateSplit = (StateSplit) node; - FrameState frameState = stateSplit.stateAfter(); - assert !stateSplit.hasSideEffect() : "snippets cannot contain side-effecting node " + node + "\n " + frameState.toString(Verbosity.Debugger); - if (frameState != null) { - stateSplit.setStateAfter(null); - } - } + } else { + parameter = snippetCopy.getLocal(i); } - - new DeadCodeEliminationPhase().apply(snippetCopy); - return new SnippetTemplate(args, snippetCopy); + assert parameter != null; + parameters.put(p.value(), parameter); } - }); - } - - SnippetTemplate(Object[] args, StructuredGraph graph) { - Object[] flattenedArgs = flatten(args); - this.graph = graph; - this.parameters = new Object[flattenedArgs.length]; + } - // Find the constant nodes corresponding to the flattened positional parameters - for (ConstantNode node : graph.getNodes().filter(ConstantNode.class)) { - if (node.kind().isObject()) { - CiConstant constant = node.asConstant(); - if (constant.kind.isObject() && !constant.isNull()) { - for (int i = 0; i < flattenedArgs.length; i++) { - if (flattenedArgs[i] == constant.asObject()) { - parameters[i] = node; + // Do any required loop explosion + boolean exploded = false; + do { + exploded = false; + for (Node node : snippetCopy.getNodes()) { + if (node instanceof ExplodeLoopNode) { + final ExplodeLoopNode explodeLoop = (ExplodeLoopNode) node; + LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); + if (loopBegin != null) { + ControlFlowGraph cfg = ControlFlowGraph.compute(snippetCopy, true, true, false, false); + for (Loop loop : cfg.getLoops()) { + if (loop.loopBegin() == loopBegin) { + SuperBlock wholeLoop = LoopTransformUtil.wholeLoop(loop); + Debug.dump(snippetCopy, "Before exploding loop %s", loopBegin); + int peel = 0; + while (!loopBegin.isDeleted()) { + int mark = snippetCopy.getMark(); + LoopTransformUtil.peel(loop, wholeLoop); + Debug.dump(snippetCopy, "After peel %d", peel); + new CanonicalizerPhase(null, runtime, null, mark, null).apply(snippetCopy); + peel++; + } + Debug.dump(snippetCopy, "After exploding loop %s", loopBegin); + exploded = true; + break; + } } + } else { + // Earlier canonicalization removed the loop altogether } + + FixedNode explodeLoopNext = explodeLoop.next(); + explodeLoop.clearSuccessors(); + explodeLoop.replaceAtPredecessors(explodeLoopNext); + explodeLoop.replaceAtUsages(null); + GraphUtil.killCFG(explodeLoop); + break; + } + } + } while (exploded); + + // Remove all frame states from inlined snippet graph. Snippets must be atomic (i.e. free + // of side-effects that prevent deoptimizing to a point before the snippet). + for (Node node : snippetCopy.getNodes()) { + if (node instanceof StateSplit) { + StateSplit stateSplit = (StateSplit) node; + FrameState frameState = stateSplit.stateAfter(); + assert !stateSplit.hasSideEffect() : "snippets cannot contain side-effecting node " + node + "\n " + frameState.toString(Verbosity.Debugger); + if (frameState != null) { + stateSplit.setStateAfter(null); } } } - // Find the local nodes corresponding to the flattened positional parameters - int localIndex = 0; - for (int i = 0; i < flattenedArgs.length; i++) { - if (flattenedArgs[i] == _) { - for (LocalNode local : graph.getNodes(LocalNode.class)) { - if (local.index() == localIndex) { - assert parameters[i] == null; - parameters[i] = local; - } - } - localIndex++; - } else { - Object param = parameters[i]; - if (param == null) { - parameters[i] = flattenedArgs[i]; - } else { - assert param instanceof ConstantNode; - assert ((ConstantNode) param).kind().isObject(); - } - } - } + new DeadCodeEliminationPhase().apply(snippetCopy); + this.graph = snippetCopy; nodes = new ArrayList<>(graph.getNodeCount()); ReturnNode retNode = null; StartNode entryPointNode = graph.start(); @@ -228,45 +291,84 @@ this.returnNode = retNode; } + private static boolean checkConstantArgument(final RiResolvedMethod method, RiSignature signature, int i, String name, Object arg, CiKind kind) { + if (kind.isObject()) { + Class type = signature.argumentTypeAt(i, method.holder()).resolve(method.holder()).toJava(); + assert type.isInstance(arg) : + method + ": wrong value type for " + name + ": expected " + type.getName() + ", got " + arg.getClass().getName(); + } else { + assert kind.toBoxedJavaClass() == arg.getClass() : + method + ": wrong value kind for " + name + ": expected " + kind + ", got " + arg.getClass().getSimpleName(); + } + return true; + } + + private static boolean checkMultipleArgument(final RiResolvedMethod method, RiSignature signature, int i, String name, Object multiple) { + assert multiple instanceof Multiple; + Object arg = ((Multiple) multiple).array; + RiResolvedType type = (RiResolvedType) signature.argumentTypeAt(i, method.holder()); + Class< ? > javaType = type.toJava(); + assert javaType.isArray() : "multiple parameter must be an array type"; + assert javaType.isInstance(arg) : "value for " + name + " is not a " + javaType.getName() + " instance: " + arg; + return true; + } + /** * The graph built from the snippet method. */ - public final StructuredGraph graph; + private final StructuredGraph graph; /** - * The flattened positional parameters of this snippet. - * A {@link LocalNode} element is bound to a {@link ValueNode} to be supplied during - * instantiation, a {@link ConstantNode} is replaced by an object constant and any - * other element denotes an input fixed during specialization. + * The named parameters of this template that must be bound to values during instantiation. + * Each parameter is either a {@link LocalNode} or a {@link LoadMultipleParameterNode} instance. */ - public final Object[] parameters; + private final Map parameters; /** * The return node (if any) of the snippet. */ - public final ReturnNode returnNode; + private final ReturnNode returnNode; /** * The nodes to be inlined when this specialization is instantiated. */ - public final ArrayList nodes; + private final ArrayList nodes; - private IdentityHashMap replacements(StructuredGraph replaceeGraph, RiRuntime runtime, Object... args) { - Object[] flattenedArgs = flatten(args); + /** + * Gets the instantiation-time bindings to this template's parameters. + * + * @return the map that will be used to bind arguments to parameters when inlining this template + */ + private IdentityHashMap bind(StructuredGraph replaceeGraph, RiRuntime runtime, Snippet.Arguments args) { IdentityHashMap replacements = new IdentityHashMap<>(); - assert parameters.length >= flattenedArgs.length; - for (int i = 0; i < flattenedArgs.length; i++) { - Object param = parameters[i]; - Object arg = flattenedArgs[i]; - if (arg == null) { - assert !(param instanceof ValueNode) : param; - } else if (arg instanceof ValueNode) { - assert param instanceof LocalNode; - replacements.put((LocalNode) param, (ValueNode) arg); - } else if (param instanceof ConstantNode) { - replacements.put((ConstantNode) param, ConstantNode.forObject(arg, runtime, replaceeGraph)); + + for (Map.Entry e : args) { + String name = e.getKey(); + ValueNode parameter = parameters.get(name); + assert parameter != null : this + " has no parameter named " + name; + Object argument = e.getValue(); + if (parameter instanceof LocalNode) { + if (argument instanceof ValueNode) { + replacements.put(parameter, (ValueNode) argument); + } else { + CiKind kind = ((LocalNode) parameter).kind(); + CiConstant constant = CiConstant.forBoxed(kind, argument); + replacements.put(parameter, ConstantNode.forCiConstant(constant, runtime, replaceeGraph)); + } } else { - assert param.equals(arg) : param + " != " + arg; + assert parameter instanceof LoadMultipleParameterNode; + Object array = argument; + assert array != null && array.getClass().isArray(); + int length = Array.getLength(array); + LoadMultipleParameterNode lmp = (LoadMultipleParameterNode) parameter; + assert length == lmp.getLocalCount() : length + " != " + lmp.getLocalCount(); + for (int j = 0; j < length; j++) { + LocalNode local = lmp.getLocal(j); + assert local != null; + CiConstant constant = CiConstant.forBoxed(lmp.kind(), Array.get(array, j)); + ConstantNode element = ConstantNode.forCiConstant(constant, runtime, replaceeGraph); + replacements.put(local, element); + } } } return replacements; @@ -282,7 +384,7 @@ */ public void instantiate(RiRuntime runtime, Node replacee, - FixedWithNextNode anchor, Object... args) { + FixedWithNextNode anchor, Arguments args) { // Inline the snippet nodes, replacing parameters with the given args in the process String name = graph.name == null ? "{copy}" : graph.name + "{copy}"; @@ -290,7 +392,7 @@ StartNode entryPointNode = graph.start(); FixedNode firstCFGNode = entryPointNode.next(); StructuredGraph replaceeGraph = (StructuredGraph) replacee.graph(); - IdentityHashMap replacements = replacements(replaceeGraph, runtime, args); + IdentityHashMap replacements = bind(replaceeGraph, runtime, args); Map duplicates = replaceeGraph.addDuplicates(nodes, replacements); Debug.dump(replaceeGraph, "After inlining snippet %s", graphCopy.method()); @@ -328,37 +430,23 @@ Debug.dump(replaceeGraph, "After lowering %s with %s", replacee, this); } - /** - * Flattens a list of objects by replacing any array in {@code args} with its elements. - */ - private static Object[] flatten(Object... args) { - List