Mercurial > hg > truffle
diff graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java @ 5481:e26e6dca0bcf
added @Parameter and @Constant annotations which simplify creation and instantiation of snippets
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Tue, 05 Jun 2012 21:43:42 +0200 |
parents | 174eb2b7f6ba |
children | 9f4783c0269e |
line wrap: on
line diff
--- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Mon Jun 04 16:00:25 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Tue Jun 05 21:43:42 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<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); - - final Map<CiConstant, CiConstant> 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<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); - } - } - } + // 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()); - 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<String, ValueNode> 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(); + 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<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()); @@ -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<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, ValueNode> e : parameters.entrySet()) { + String name = e.getKey(); + ValueNode value = e.getValue(); + buf.append(sep); + sep = ", "; + if (value instanceof LocalNode) { + buf.append(value.kind().name()).append(' ').append(name); } else { - buf.append(param); - } - if (i != parameters.length - 1) { - buf.append(", "); + LoadMultipleParameterNode lmp = (LoadMultipleParameterNode) value; + buf.append(value.kind().name()).append('[').append(lmp.getLocalCount()).append("] ").append(name); } } return buf.append(')').toString(); } } +