Mercurial > hg > truffle
diff graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java @ 5490:82f44f47e1aa
Merge
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Wed, 06 Jun 2012 19:19:10 +0200 |
parents | 5d0d72b37f88 9f4783c0269e |
children | 35f9b57d70cb |
line wrap: on
line diff
--- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 19:09:05 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Wed Jun 06 19:19:10 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,176 +24,252 @@ 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.type.*; 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<Map.Entry<String, Object>> { + public final RiResolvedMethod method; + private final HashMap<String, Object> 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<Entry<String, Object>> 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<SnippetTemplate.Key, SnippetTemplate> 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<SnippetTemplate>() { + @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<SnippetTemplate>() { - @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); + 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(); - final Map<CiConstant, CiConstant> constantArrays = new IdentityHashMap<>(); - IsImmutablePredicate immutabilityPredicate = new IsImmutablePredicate() { - public boolean apply(CiConstant constant) { - return constantArrays.containsKey(constant); - } - }; + // 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<Node, Node> replacements = new IdentityHashMap<>(); + replacements.put(snippetGraph.start(), snippetCopy.start()); - // Copy snippet graph, replacing parameters with given args in the process - StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method()); - IdentityHashMap<Node, Node> 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); - } - } - } - - ConstantNode argNode = ConstantNode.forCiConstant(specializationArg, runtime, snippetCopy); - replacements.put(local, argNode); - } - localCount++; + int parameterCount = signature.argumentCount(false); + Parameter[] parameterAnnotations = new Parameter[parameterCount]; + ConstantNode[] placeholders = new ConstantNode[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; + ConstantNode placeholder = ConstantNode.forObject(array, runtime, snippetCopy); + replacements.put(snippetGraph.getLocal(i), placeholder); + placeholders[i] = placeholder; } - assert localCount == args.length : "snippet argument count mismatch"; - snippetCopy.addDuplicates(snippetGraph.getNodes(), replacements); - - Debug.dump(snippetCopy, "Before specialization"); + parameterAnnotations[i] = p; + } + } + snippetCopy.addDuplicates(snippetGraph.getNodes(), replacements); - if (!replacements.isEmpty()) { - new CanonicalizerPhase(null, runtime, null, 0, immutabilityPredicate).apply(snippetCopy); - } + Debug.dump(snippetCopy, "Before specialization"); + if (!replacements.isEmpty()) { + new CanonicalizerPhase(null, runtime, null, 0, null).apply(snippetCopy); + } - boolean exploded = false; - do { - exploded = false; - ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first(); - if (explodeLoop != null) { - LoopEx loop = new LoopsData(snippetCopy).loop(explodeLoop.findLoopBegin()); - int mark = snippetCopy.getMark(); - LoopTransformations.fullUnroll(loop); - new CanonicalizerPhase(null, runtime, null, mark, immutabilityPredicate).apply(snippetCopy); - FixedNode explodeLoopNext = explodeLoop.next(); - explodeLoop.clearSuccessors(); - explodeLoop.replaceAtPredecessor(explodeLoopNext); - explodeLoop.replaceAtUsages(null); - GraphUtil.killCFG(explodeLoop); - exploded = true; - break; + // Gather the template parameters + parameters = new HashMap<>(); + for (int i = 0; i < parameterCount; i++) { + Parameter p = parameterAnnotations[i]; + if (p != null) { + if (p.multiple()) { + assert snippetCopy.getLocal(i) == null; + Object array = ((Multiple) key.get(p.value())).array; + int length = Array.getLength(array); + LocalNode[] locals = new LocalNode[length]; + Stamp stamp = StampFactory.forKind(runtime.getType(array.getClass().getComponentType()).kind(false)); + for (int j = 0; j < length; j++) { + assert (parameterCount & 0xFFFF) == parameterCount; + int idx = i << 16 | j; + LocalNode local = snippetCopy.unique(new LocalNode(idx, stamp)); + locals[j] = local; } - } while (exploded); + parameters.put(p.value(), locals); - // 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); + ConstantNode placeholder = placeholders[i]; + assert placeholder != null; + for (Node usage : placeholder.usages().snapshot()) { + if (usage instanceof LoadIndexedNode) { + LoadIndexedNode loadIndexed = (LoadIndexedNode) usage; + Debug.dump(snippetCopy, "Before replacing %s", loadIndexed); + LoadSnippetParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetParameterNode(locals, loadIndexed.index(), loadIndexed.stamp())); + snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter); + Debug.dump(snippetCopy, "After replacing %s", loadIndexed); } } - } - - new DeadCodeEliminationPhase().apply(snippetCopy); - return new SnippetTemplate(args, snippetCopy); - } - }); - } - - 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; - } - } + } else { + LocalNode local = snippetCopy.getLocal(i); + assert local != null; + parameters.put(p.value(), local); } } } - // 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; - } + // Do any required loop explosion + boolean exploded = false; + do { + exploded = false; + ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first(); + if (explodeLoop != null) { // Earlier canonicalization may have removed the loop altogether + LoopBeginNode loopBegin = explodeLoop.findLoopBegin(); + if (loopBegin != null) { + LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin); + int mark = snippetCopy.getMark(); + LoopTransformations.fullUnroll(loop); + new CanonicalizerPhase(null, runtime, null, mark, null).apply(snippetCopy); } - localIndex++; - } else { - Object param = parameters[i]; - if (param == null) { - parameters[i] = flattenedArgs[i]; - } else { - assert param instanceof ConstantNode; - assert ((ConstantNode) param).kind().isObject(); + FixedNode explodeLoopNext = explodeLoop.next(); + explodeLoop.clearSuccessors(); + explodeLoop.replaceAtPredecessor(explodeLoopNext); + explodeLoop.replaceAtUsages(null); + GraphUtil.killCFG(explodeLoop); + exploded = true; + } + } 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); } } } + new DeadCodeEliminationPhase().apply(snippetCopy); + + assert checkAllMultipleParameterPlaceholdersAreDeleted(parameterCount, placeholders); + + this.graph = snippetCopy; nodes = new ArrayList<>(graph.getNodeCount()); ReturnNode retNode = null; StartNode entryPointNode = graph.start(); @@ -210,45 +286,93 @@ this.returnNode = retNode; } + private static boolean checkAllMultipleParameterPlaceholdersAreDeleted(int parameterCount, ConstantNode[] placeholders) { + for (int i = 0; i < parameterCount; i++) { + if (placeholders[i] != null) { + assert placeholders[i].isDeleted() : placeholders[i]; + } + } + return true; + } + + 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 value in this map is either a {@link LocalNode} instance or a {@link LocalNode} array. */ - public final Object[] parameters; + private final Map<String, Object> 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<Node> nodes; + private final ArrayList<Node> nodes; - private IdentityHashMap<Node, Node> 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<Node, Node> bind(StructuredGraph replaceeGraph, RiRuntime runtime, Snippet.Arguments args) { IdentityHashMap<Node, Node> 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<String, Object> e : args) { + String name = e.getKey(); + Object 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((LocalNode) parameter, (ValueNode) argument); + } else { + CiKind kind = ((LocalNode) parameter).kind(); + CiConstant constant = CiConstant.forBoxed(kind, argument); + replacements.put((LocalNode) parameter, ConstantNode.forCiConstant(constant, runtime, replaceeGraph)); + } } else { - assert param.equals(arg) : param + " != " + arg; + assert parameter instanceof LocalNode[]; + LocalNode[] locals = (LocalNode[]) parameter; + Object array = argument; + assert array != null && array.getClass().isArray(); + int length = locals.length; + assert Array.getLength(array) == length : length + " != " + Array.getLength(array); + for (int j = 0; j < length; j++) { + LocalNode local = locals[j]; + assert local != null; + CiConstant constant = CiConstant.forBoxed(local.kind(), Array.get(array, j)); + ConstantNode element = ConstantNode.forCiConstant(constant, runtime, replaceeGraph); + replacements.put(local, element); + } } } return replacements; @@ -264,7 +388,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}"; @@ -272,7 +396,7 @@ StartNode entryPointNode = graph.start(); FixedNode firstCFGNode = entryPointNode.next(); StructuredGraph replaceeGraph = (StructuredGraph) replacee.graph(); - IdentityHashMap<Node, Node> replacements = replacements(replaceeGraph, runtime, args); + IdentityHashMap<Node, Node> replacements = bind(replaceeGraph, runtime, args); Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, replacements); Debug.dump(replaceeGraph, "After inlining snippet %s", graphCopy.method()); @@ -310,37 +434,25 @@ 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<Object> list = new ArrayList<>(args.length * 2); - for (Object o : args) { - if (o instanceof Object[]) { - list.addAll(Arrays.asList((Object[]) o)); - } else { - list.add(o); - } - } - return list.toArray(new Object[list.size()]); - } - @Override public String toString() { StringBuilder buf = new StringBuilder(graph.toString()).append('('); - for (int i = 0; i < parameters.length; i++) { - Object param = parameters[i]; - if (param instanceof ConstantNode) { - buf.append(((ConstantNode) param).asConstant().asObject()); - } else if (param instanceof LocalNode) { - buf.append('_'); + String sep = ""; + for (Map.Entry<String, Object> e : parameters.entrySet()) { + String name = e.getKey(); + Object value = e.getValue(); + buf.append(sep); + sep = ", "; + if (value instanceof LocalNode) { + LocalNode local = (LocalNode) value; + buf.append(local.kind().name()).append(' ').append(name); } else { - buf.append(param); - } - if (i != parameters.length - 1) { - buf.append(", "); + LocalNode[] locals = (LocalNode[]) value; + String kind = locals.length == 0 ? "?" : locals[0].kind().name(); + buf.append(kind).append('[').append(locals.length).append("] ").append(name); } } return buf.append(')').toString(); } } +