001/*
002 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.replacements;
024
025import static com.oracle.graal.debug.Debug.*;
026import static com.oracle.graal.phases.common.DeadCodeEliminationPhase.Optionality.*;
027import static com.oracle.graal.replacements.SnippetTemplate.AbstractTemplates.*;
028import static java.util.FormattableFlags.*;
029import static jdk.internal.jvmci.meta.LocationIdentity.*;
030
031import java.lang.reflect.*;
032import java.util.*;
033import java.util.concurrent.*;
034import java.util.concurrent.atomic.*;
035import java.util.function.*;
036import java.util.stream.*;
037
038import jdk.internal.jvmci.code.*;
039import jdk.internal.jvmci.common.*;
040import jdk.internal.jvmci.meta.*;
041
042import com.oracle.graal.api.replacements.*;
043import com.oracle.graal.compiler.common.type.*;
044import com.oracle.graal.debug.*;
045import com.oracle.graal.debug.Debug.Scope;
046import com.oracle.graal.graph.Graph.Mark;
047import com.oracle.graal.graph.*;
048import com.oracle.graal.graph.Node;
049import com.oracle.graal.loop.*;
050import com.oracle.graal.nodeinfo.*;
051import com.oracle.graal.nodes.*;
052import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
053import com.oracle.graal.nodes.StructuredGraph.GuardsStage;
054import com.oracle.graal.nodes.calc.*;
055import com.oracle.graal.nodes.java.*;
056import com.oracle.graal.nodes.memory.*;
057import com.oracle.graal.nodes.spi.*;
058import com.oracle.graal.nodes.util.*;
059import com.oracle.graal.phases.common.*;
060import com.oracle.graal.phases.common.FloatingReadPhase.MemoryMapImpl;
061import com.oracle.graal.phases.common.inlining.*;
062import com.oracle.graal.phases.tiers.*;
063import com.oracle.graal.phases.util.*;
064import com.oracle.graal.replacements.Snippet.ConstantParameter;
065import com.oracle.graal.replacements.Snippet.VarargsParameter;
066import com.oracle.graal.replacements.nodes.*;
067import com.oracle.graal.word.*;
068
069/**
070 * A snippet template is a graph created by parsing a snippet method and then specialized by binding
071 * constants to the snippet's {@link ConstantParameter} parameters.
072 *
073 * Snippet templates can be managed in a cache maintained by {@link AbstractTemplates}.
074 */
075public class SnippetTemplate {
076
077    // Checkstyle: stop
078    public static boolean LAZY_SNIPPETS = true;
079
080    // Checkstyle: resume
081
082    /**
083     * Holds the {@link ResolvedJavaMethod} of the snippet, together with some information about the
084     * method that needs to be computed only once. The {@link SnippetInfo} should be created once
085     * per snippet and then cached.
086     */
087    public abstract static class SnippetInfo {
088
089        protected final ResolvedJavaMethod method;
090        protected ResolvedJavaMethod original;
091        protected final LocationIdentity[] privateLocations;
092
093        /**
094         * Lazily constructed parts of {@link SnippetInfo}.
095         */
096        static class Lazy {
097            public Lazy(ResolvedJavaMethod method) {
098                int count = method.getSignature().getParameterCount(false);
099                constantParameters = new boolean[count];
100                varargsParameters = new boolean[count];
101                for (int i = 0; i < count; i++) {
102                    constantParameters[i] = method.getParameterAnnotation(ConstantParameter.class, i) != null;
103                    varargsParameters[i] = method.getParameterAnnotation(VarargsParameter.class, i) != null;
104
105                    assert !constantParameters[i] || !varargsParameters[i] : "Parameter cannot be annotated with both @" + ConstantParameter.class.getSimpleName() + " and @" +
106                                    VarargsParameter.class.getSimpleName();
107                }
108
109                // Retrieve the names only when assertions are turned on.
110                assert initNames(method, count);
111            }
112
113            final boolean[] constantParameters;
114            final boolean[] varargsParameters;
115
116            /**
117             * The parameter names, taken from the local variables table. Only used for assertion
118             * checking, so use only within an assert statement.
119             */
120            String[] names;
121
122            private boolean initNames(ResolvedJavaMethod method, int parameterCount) {
123                names = new String[parameterCount];
124                int slotIdx = 0;
125                for (int i = 0; i < names.length; i++) {
126                    names[i] = method.getLocalVariableTable().getLocal(slotIdx, 0).getName();
127
128                    Kind kind = method.getSignature().getParameterKind(i);
129                    slotIdx += kind.getSlotCount();
130                }
131                return true;
132            }
133
134        }
135
136        /**
137         * Times instantiations of all templates derived form this snippet.
138         *
139         * @see SnippetTemplate#instantiationTimer
140         */
141        private final DebugTimer instantiationTimer;
142
143        /**
144         * Counts instantiations of all templates derived from this snippet.
145         *
146         * @see SnippetTemplate#instantiationCounter
147         */
148        private final DebugMetric instantiationCounter;
149
150        protected abstract Lazy lazy();
151
152        protected SnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
153            this.method = method;
154            this.privateLocations = SnippetCounterNode.addSnippetCounters(privateLocations);
155            instantiationCounter = Debug.metric("SnippetInstantiationCount[%s]", method.getName());
156            instantiationTimer = Debug.timer("SnippetInstantiationTime[%s]", method.getName());
157            assert method.isStatic() : "snippet method must be static: " + method.format("%H.%n");
158        }
159
160        private int templateCount;
161
162        void notifyNewTemplate() {
163            templateCount++;
164            if (templateCount == MaxTemplatesPerSnippet) {
165                TTY.print("WARNING: Exceeded %d templates for snippet %s%n" + "         Adjust maximum with %s system property%n", MaxTemplatesPerSnippet, method.format("%h.%n(%p)"),
166                                MAX_TEMPLATES_PER_SNIPPET_PROPERTY_NAME);
167            }
168        }
169
170        public ResolvedJavaMethod getMethod() {
171            return method;
172        }
173
174        public int getParameterCount() {
175            return lazy().constantParameters.length;
176        }
177
178        public void setOriginalMethod(ResolvedJavaMethod original) {
179            this.original = original;
180        }
181
182        public boolean isConstantParameter(int paramIdx) {
183            return lazy().constantParameters[paramIdx];
184        }
185
186        public boolean isVarargsParameter(int paramIdx) {
187            return lazy().varargsParameters[paramIdx];
188        }
189
190        public String getParameterName(int paramIdx) {
191            String[] names = lazy().names;
192            if (names != null) {
193                return names[paramIdx];
194            }
195            return null;
196        }
197
198        @Override
199        public String toString() {
200            return getClass().getSimpleName() + ":" + method.format("%h.%n");
201        }
202    }
203
204    protected static class LazySnippetInfo extends SnippetInfo {
205        protected final AtomicReference<Lazy> lazy = new AtomicReference<>(null);
206
207        protected LazySnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
208            super(method, privateLocations);
209        }
210
211        @Override
212        protected Lazy lazy() {
213            if (lazy.get() == null) {
214                lazy.compareAndSet(null, new Lazy(method));
215            }
216            return lazy.get();
217        }
218    }
219
220    protected static class EagerSnippetInfo extends SnippetInfo {
221        protected final Lazy lazy;
222
223        protected EagerSnippetInfo(ResolvedJavaMethod method, LocationIdentity[] privateLocations) {
224            super(method, privateLocations);
225            lazy = new Lazy(method);
226        }
227
228        @Override
229        protected Lazy lazy() {
230            return lazy;
231        }
232    }
233
234    /**
235     * Values that are bound to the snippet method parameters. The methods {@link #add},
236     * {@link #addConst}, and {@link #addVarargs} must be called in the same order as in the
237     * signature of the snippet method. The parameter name is passed to the add methods for
238     * assertion checking, i.e., to enforce that the order matches. Which method needs to be called
239     * depends on the annotation of the snippet method parameter:
240     * <ul>
241     * <li>Use {@link #add} for a parameter without an annotation. The value is bound when the
242     * {@link SnippetTemplate} is {@link SnippetTemplate#instantiate instantiated}.
243     * <li>Use {@link #addConst} for a parameter annotated with {@link ConstantParameter}. The value
244     * is bound when the {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created}.
245     * <li>Use {@link #addVarargs} for an array parameter annotated with {@link VarargsParameter}. A
246     * separate {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created} for every
247     * distinct array length. The actual values are bound when the {@link SnippetTemplate} is
248     * {@link SnippetTemplate#instantiate instantiated}
249     * </ul>
250     */
251    public static class Arguments implements Formattable {
252
253        protected final SnippetInfo info;
254        protected final CacheKey cacheKey;
255        protected final Object[] values;
256        protected final Stamp[] constStamps;
257        protected boolean cacheable;
258
259        protected int nextParamIdx;
260
261        public Arguments(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {
262            this.info = info;
263            this.cacheKey = new CacheKey(info, guardsStage, loweringStage);
264            this.values = new Object[info.getParameterCount()];
265            this.constStamps = new Stamp[info.getParameterCount()];
266            this.cacheable = true;
267        }
268
269        public Arguments add(String name, Object value) {
270            assert check(name, false, false);
271            values[nextParamIdx] = value;
272            nextParamIdx++;
273            return this;
274        }
275
276        public Arguments addConst(String name, Object value) {
277            assert value != null;
278            return addConst(name, value, null);
279        }
280
281        public Arguments addConst(String name, Object value, Stamp stamp) {
282            assert check(name, true, false);
283            values[nextParamIdx] = value;
284            constStamps[nextParamIdx] = stamp;
285            cacheKey.setParam(nextParamIdx, value);
286            nextParamIdx++;
287            return this;
288        }
289
290        public Arguments addVarargs(String name, Class<?> componentType, Stamp argStamp, Object value) {
291            assert check(name, false, true);
292            Varargs varargs = new Varargs(componentType, argStamp, value);
293            values[nextParamIdx] = varargs;
294            // A separate template is necessary for every distinct array length
295            cacheKey.setParam(nextParamIdx, varargs.length);
296            nextParamIdx++;
297            return this;
298        }
299
300        public void setCacheable(boolean cacheable) {
301            this.cacheable = cacheable;
302        }
303
304        private boolean check(String name, boolean constParam, boolean varargsParam) {
305            assert nextParamIdx < info.getParameterCount() : "too many parameters: " + name + "  " + this;
306            assert info.getParameterName(nextParamIdx) == null || info.getParameterName(nextParamIdx).equals(name) : "wrong parameter name: " + name + "  " + this;
307            assert constParam == info.isConstantParameter(nextParamIdx) : "Parameter " + (constParam ? "not " : "") + "annotated with @" + ConstantParameter.class.getSimpleName() + ": " + name +
308                            "  " + this;
309            assert varargsParam == info.isVarargsParameter(nextParamIdx) : "Parameter " + (varargsParam ? "not " : "") + "annotated with @" + VarargsParameter.class.getSimpleName() + ": " + name +
310                            "  " + this;
311            return true;
312        }
313
314        @Override
315        public String toString() {
316            StringBuilder result = new StringBuilder();
317            result.append("Parameters<").append(info.method.format("%h.%n")).append(" [");
318            String sep = "";
319            for (int i = 0; i < info.getParameterCount(); i++) {
320                result.append(sep);
321                if (info.isConstantParameter(i)) {
322                    result.append("const ");
323                } else if (info.isVarargsParameter(i)) {
324                    result.append("varargs ");
325                }
326                result.append(info.getParameterName(i)).append(" = ").append(values[i]);
327                sep = ", ";
328            }
329            result.append(">");
330            return result.toString();
331        }
332
333        public void formatTo(Formatter formatter, int flags, int width, int precision) {
334            if ((flags & ALTERNATE) == 0) {
335                formatter.format(applyFormattingFlagsAndWidth(toString(), flags, width));
336            } else {
337                StringBuilder sb = new StringBuilder();
338                sb.append(info.method.getName()).append('(');
339                String sep = "";
340                for (int i = 0; i < info.getParameterCount(); i++) {
341                    if (info.isConstantParameter(i)) {
342                        sb.append(sep);
343                        if (info.getParameterName(i) != null) {
344                            sb.append(info.getParameterName(i));
345                        } else {
346                            sb.append(i);
347                        }
348                        sb.append('=').append(values[i]);
349                        sep = ", ";
350                    }
351                }
352                sb.append(")");
353                String string = sb.toString();
354                if (string.indexOf('%') != -1) {
355                    // Quote any % signs
356                    string = string.replace("%", "%%");
357                }
358                formatter.format(applyFormattingFlagsAndWidth(string, flags & ~ALTERNATE, width));
359            }
360        }
361    }
362
363    /**
364     * Wrapper for the prototype value of a {@linkplain VarargsParameter varargs} parameter.
365     */
366    static class Varargs {
367
368        protected final Class<?> componentType;
369        protected final Stamp stamp;
370        protected final Object value;
371        protected final int length;
372
373        protected Varargs(Class<?> componentType, Stamp stamp, Object value) {
374            this.componentType = componentType;
375            this.stamp = stamp;
376            this.value = value;
377            if (value instanceof List) {
378                this.length = ((List<?>) value).size();
379            } else {
380                this.length = Array.getLength(value);
381            }
382        }
383
384        @Override
385        public String toString() {
386            if (value instanceof boolean[]) {
387                return Arrays.toString((boolean[]) value);
388            }
389            if (value instanceof byte[]) {
390                return Arrays.toString((byte[]) value);
391            }
392            if (value instanceof char[]) {
393                return Arrays.toString((char[]) value);
394            }
395            if (value instanceof short[]) {
396                return Arrays.toString((short[]) value);
397            }
398            if (value instanceof int[]) {
399                return Arrays.toString((int[]) value);
400            }
401            if (value instanceof long[]) {
402                return Arrays.toString((long[]) value);
403            }
404            if (value instanceof float[]) {
405                return Arrays.toString((float[]) value);
406            }
407            if (value instanceof double[]) {
408                return Arrays.toString((double[]) value);
409            }
410            if (value instanceof Object[]) {
411                return Arrays.toString((Object[]) value);
412            }
413            return String.valueOf(value);
414        }
415    }
416
417    @NodeInfo
418    static final class VarargsPlaceholderNode extends FloatingNode implements ArrayLengthProvider {
419
420        public static final NodeClass<VarargsPlaceholderNode> TYPE = NodeClass.create(VarargsPlaceholderNode.class);
421        protected final Varargs varargs;
422
423        public VarargsPlaceholderNode(Varargs varargs, MetaAccessProvider metaAccess) {
424            super(TYPE, StampFactory.exactNonNull(metaAccess.lookupJavaType(varargs.componentType).getArrayClass()));
425            this.varargs = varargs;
426        }
427
428        public ValueNode length() {
429            return ConstantNode.forInt(varargs.length);
430        }
431    }
432
433    static class CacheKey {
434
435        private final ResolvedJavaMethod method;
436        private final Object[] values;
437        private final GuardsStage guardsStage;
438        private final LoweringTool.LoweringStage loweringStage;
439        private int hash;
440
441        protected CacheKey(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {
442            this.method = info.method;
443            this.guardsStage = guardsStage;
444            this.loweringStage = loweringStage;
445            this.values = new Object[info.getParameterCount()];
446            this.hash = info.method.hashCode() + 31 * guardsStage.ordinal();
447        }
448
449        protected void setParam(int paramIdx, Object value) {
450            values[paramIdx] = value;
451            hash = (hash * 31) ^ (value == null ? 0 : value.hashCode());
452        }
453
454        @Override
455        public boolean equals(Object obj) {
456            if (!(obj instanceof CacheKey)) {
457                return false;
458            }
459            CacheKey other = (CacheKey) obj;
460            if (!method.equals(other.method)) {
461                return false;
462            }
463            if (guardsStage != other.guardsStage || loweringStage != other.loweringStage) {
464                return false;
465            }
466            for (int i = 0; i < values.length; i++) {
467                if (values[i] != null && !values[i].equals(other.values[i])) {
468                    return false;
469                }
470            }
471            return true;
472        }
473
474        @Override
475        public int hashCode() {
476            return hash;
477        }
478    }
479
480    private static final DebugTimer SnippetTemplateCreationTime = Debug.timer("SnippetTemplateCreationTime");
481    private static final DebugMetric SnippetTemplates = Debug.metric("SnippetTemplateCount");
482
483    private static final String MAX_TEMPLATES_PER_SNIPPET_PROPERTY_NAME = "graal.maxTemplatesPerSnippet";
484    private static final int MaxTemplatesPerSnippet = Integer.getInteger(MAX_TEMPLATES_PER_SNIPPET_PROPERTY_NAME, 50);
485
486    /**
487     * Base class for snippet classes. It provides a cache for {@link SnippetTemplate}s.
488     */
489    public abstract static class AbstractTemplates implements com.oracle.graal.api.replacements.SnippetTemplateCache {
490
491        static final boolean UseSnippetTemplateCache = Boolean.parseBoolean(System.getProperty("graal.useSnippetTemplateCache", "true"));
492
493        protected final Providers providers;
494        protected final SnippetReflectionProvider snippetReflection;
495        protected final TargetDescription target;
496        private final ConcurrentHashMap<CacheKey, SnippetTemplate> templates;
497
498        protected AbstractTemplates(Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
499            this.providers = providers;
500            this.snippetReflection = snippetReflection;
501            this.target = target;
502            if (UseSnippetTemplateCache) {
503                this.templates = new ConcurrentHashMap<>();
504            } else {
505                this.templates = null;
506            }
507        }
508
509        public static Method findMethod(Class<? extends Snippets> declaringClass, String methodName, Method except) {
510            for (Method m : declaringClass.getDeclaredMethods()) {
511                if (m.getName().equals(methodName) && !m.equals(except)) {
512                    return m;
513                }
514            }
515            return null;
516        }
517
518        /**
519         * Finds the unique method in {@code declaringClass} named {@code methodName} annotated by
520         * {@link Snippet} and returns a {@link SnippetInfo} value describing it. There must be
521         * exactly one snippet method in {@code declaringClass}.
522         */
523        protected SnippetInfo snippet(Class<? extends Snippets> declaringClass, String methodName, LocationIdentity... privateLocations) {
524            assert methodName != null;
525            Method method = findMethod(declaringClass, methodName, null);
526            assert method != null : "did not find @" + Snippet.class.getSimpleName() + " method in " + declaringClass + " named " + methodName;
527            assert method.getAnnotation(Snippet.class) != null : method + " must be annotated with @" + Snippet.class.getSimpleName();
528            assert findMethod(declaringClass, methodName, method) == null : "found more than one method named " + methodName + " in " + declaringClass;
529            ResolvedJavaMethod javaMethod = providers.getMetaAccess().lookupJavaMethod(method);
530            providers.getReplacements().registerSnippet(javaMethod);
531            if (LAZY_SNIPPETS) {
532                return new LazySnippetInfo(javaMethod, privateLocations);
533            } else {
534                return new EagerSnippetInfo(javaMethod, privateLocations);
535            }
536        }
537
538        /**
539         * Gets a template for a given key, creating it first if necessary.
540         */
541        protected SnippetTemplate template(final Arguments args) {
542            SnippetTemplate template = UseSnippetTemplateCache && args.cacheable ? templates.get(args.cacheKey) : null;
543            if (template == null) {
544                SnippetTemplates.increment();
545                try (DebugCloseable a = SnippetTemplateCreationTime.start(); Scope s = Debug.scope("SnippetSpecialization", args.info.method)) {
546                    template = new SnippetTemplate(providers, snippetReflection, args);
547                    if (UseSnippetTemplateCache && args.cacheable) {
548                        templates.put(args.cacheKey, template);
549                    }
550                } catch (Throwable e) {
551                    throw Debug.handle(e);
552                }
553            }
554            return template;
555        }
556    }
557
558    // These values must be compared with equals() not '==' to support replay compilation.
559    private static final Object UNUSED_PARAMETER = "UNUSED_PARAMETER";
560    private static final Object CONSTANT_PARAMETER = "CONSTANT_PARAMETER";
561
562    /**
563     * Determines if any parameter of a given method is annotated with {@link ConstantParameter}.
564     */
565    public static boolean hasConstantParameter(ResolvedJavaMethod method) {
566        for (ConstantParameter p : method.getParameterAnnotations(ConstantParameter.class)) {
567            if (p != null) {
568                return true;
569            }
570        }
571        return false;
572    }
573
574    private final SnippetReflectionProvider snippetReflection;
575
576    /**
577     * Creates a snippet template.
578     */
579    protected SnippetTemplate(final Providers providers, SnippetReflectionProvider snippetReflection, Arguments args) {
580        this.snippetReflection = snippetReflection;
581        this.info = args.info;
582
583        Object[] constantArgs = getConstantArgs(args);
584        StructuredGraph snippetGraph = providers.getReplacements().getSnippet(args.info.method, args.info.original, constantArgs);
585        instantiationTimer = Debug.timer("SnippetTemplateInstantiationTime[%#s]", args);
586        instantiationCounter = Debug.metric("SnippetTemplateInstantiationCount[%#s]", args);
587
588        ResolvedJavaMethod method = snippetGraph.method();
589        Signature signature = method.getSignature();
590
591        PhaseContext phaseContext = new PhaseContext(providers);
592
593        // Copy snippet graph, replacing constant parameters with given arguments
594        final StructuredGraph snippetCopy = new StructuredGraph(snippetGraph.name, snippetGraph.method(), AllowAssumptions.NO);
595        if (!snippetGraph.isInlinedMethodRecordingEnabled()) {
596            snippetCopy.disableInlinedMethodRecording();
597        }
598        if (!snippetGraph.isUnsafeAccessTrackingEnabled()) {
599            snippetCopy.disableUnsafeAccessTracking();
600        }
601
602        Map<Node, Node> nodeReplacements = Node.newIdentityMap();
603        nodeReplacements.put(snippetGraph.start(), snippetCopy.start());
604
605        MetaAccessProvider metaAccess = providers.getMetaAccess();
606        assert checkTemplate(metaAccess, args, method, signature);
607
608        int parameterCount = args.info.getParameterCount();
609        VarargsPlaceholderNode[] placeholders = new VarargsPlaceholderNode[parameterCount];
610
611        for (int i = 0; i < parameterCount; i++) {
612            if (args.info.isConstantParameter(i)) {
613                Object arg = args.values[i];
614                Kind kind = signature.getParameterKind(i);
615                ConstantNode constantNode;
616                if (arg instanceof Constant) {
617                    Stamp stamp = args.constStamps[i];
618                    if (stamp == null) {
619                        assert arg instanceof JavaConstant : "could not determine type of constant " + arg;
620                        constantNode = ConstantNode.forConstant((JavaConstant) arg, metaAccess, snippetCopy);
621                    } else {
622                        constantNode = ConstantNode.forConstant(stamp, (Constant) arg, metaAccess, snippetCopy);
623                    }
624                } else {
625                    constantNode = ConstantNode.forConstant(snippetReflection.forBoxed(kind, arg), metaAccess, snippetCopy);
626                }
627                nodeReplacements.put(snippetGraph.getParameter(i), constantNode);
628            } else if (args.info.isVarargsParameter(i)) {
629                Varargs varargs = (Varargs) args.values[i];
630                VarargsPlaceholderNode placeholder = snippetCopy.unique(new VarargsPlaceholderNode(varargs, providers.getMetaAccess()));
631                nodeReplacements.put(snippetGraph.getParameter(i), placeholder);
632                placeholders[i] = placeholder;
633            }
634        }
635        snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements);
636
637        Debug.dump(snippetCopy, "Before specialization");
638
639        // Gather the template parameters
640        parameters = new Object[parameterCount];
641        for (int i = 0; i < parameterCount; i++) {
642            if (args.info.isConstantParameter(i)) {
643                parameters[i] = CONSTANT_PARAMETER;
644            } else if (args.info.isVarargsParameter(i)) {
645                assert snippetCopy.getParameter(i) == null;
646                Varargs varargs = (Varargs) args.values[i];
647                int length = varargs.length;
648                ParameterNode[] params = new ParameterNode[length];
649                Stamp stamp = varargs.stamp;
650                for (int j = 0; j < length; j++) {
651                    // Use a decimal friendly numbering make it more obvious how values map
652                    assert parameterCount < 10000;
653                    int idx = (i + 1) * 10000 + j;
654                    assert idx >= parameterCount : "collision in parameter numbering";
655                    ParameterNode local = snippetCopy.unique(new ParameterNode(idx, stamp));
656                    params[j] = local;
657                }
658                parameters[i] = params;
659
660                VarargsPlaceholderNode placeholder = placeholders[i];
661                assert placeholder != null;
662                for (Node usage : placeholder.usages().snapshot()) {
663                    if (usage instanceof LoadIndexedNode) {
664                        LoadIndexedNode loadIndexed = (LoadIndexedNode) usage;
665                        Debug.dump(snippetCopy, "Before replacing %s", loadIndexed);
666                        LoadSnippetVarargParameterNode loadSnippetParameter = snippetCopy.add(new LoadSnippetVarargParameterNode(params, loadIndexed.index(), loadIndexed.stamp()));
667                        snippetCopy.replaceFixedWithFixed(loadIndexed, loadSnippetParameter);
668                        Debug.dump(snippetCopy, "After replacing %s", loadIndexed);
669                    } else if (usage instanceof StoreIndexedNode) {
670                        // The template lowering doesn't really treat this as an array so you can't
671                        // store back into the varargs. Allocate your own array if you really need
672                        // this and EA should eliminate it.
673                        throw new JVMCIError("Can't store into VarargsParameter array");
674                    }
675                }
676            } else {
677                ParameterNode local = snippetCopy.getParameter(i);
678                if (local == null) {
679                    // Parameter value was eliminated
680                    parameters[i] = UNUSED_PARAMETER;
681                } else {
682                    parameters[i] = local;
683                }
684            }
685        }
686
687        // Do any required loop explosion
688        boolean exploded = false;
689        do {
690            exploded = false;
691            ExplodeLoopNode explodeLoop = snippetCopy.getNodes().filter(ExplodeLoopNode.class).first();
692            if (explodeLoop != null) { // Earlier canonicalization may have removed the loop
693                // altogether
694                LoopBeginNode loopBegin = explodeLoop.findLoopBegin();
695                if (loopBegin != null) {
696                    LoopEx loop = new LoopsData(snippetCopy).loop(loopBegin);
697                    Mark mark = snippetCopy.getMark();
698                    LoopTransformations.fullUnroll(loop, phaseContext, new CanonicalizerPhase());
699                    new CanonicalizerPhase().applyIncremental(snippetCopy, phaseContext, mark);
700                    loop.deleteUnusedNodes();
701                }
702                GraphUtil.removeFixedWithUnusedInputs(explodeLoop);
703                exploded = true;
704            }
705        } while (exploded);
706
707        GuardsStage guardsStage = args.cacheKey.guardsStage;
708        // Perform lowering on the snippet
709        if (!guardsStage.allowsFloatingGuards()) {
710            new GuardLoweringPhase().apply(snippetCopy, null);
711        }
712        snippetCopy.setGuardsStage(guardsStage);
713        try (Scope s = Debug.scope("LoweringSnippetTemplate", snippetCopy)) {
714            new LoweringPhase(new CanonicalizerPhase(), args.cacheKey.loweringStage).apply(snippetCopy, phaseContext);
715        } catch (Throwable e) {
716            throw Debug.handle(e);
717        }
718
719        ArrayList<StateSplit> curSideEffectNodes = new ArrayList<>();
720        ArrayList<DeoptimizingNode> curDeoptNodes = new ArrayList<>();
721        ArrayList<ValueNode> curStampNodes = new ArrayList<>();
722        for (Node node : snippetCopy.getNodes()) {
723            if (node instanceof ValueNode && ((ValueNode) node).stamp() == StampFactory.forNodeIntrinsic()) {
724                curStampNodes.add((ValueNode) node);
725            }
726            if (node instanceof StateSplit) {
727                StateSplit stateSplit = (StateSplit) node;
728                FrameState frameState = stateSplit.stateAfter();
729                if (stateSplit.hasSideEffect()) {
730                    curSideEffectNodes.add((StateSplit) node);
731                }
732                if (frameState != null) {
733                    stateSplit.setStateAfter(null);
734                }
735            }
736            if (node instanceof DeoptimizingNode) {
737                DeoptimizingNode deoptNode = (DeoptimizingNode) node;
738                if (deoptNode.canDeoptimize()) {
739                    curDeoptNodes.add(deoptNode);
740                }
741            }
742        }
743
744        new DeadCodeEliminationPhase(Required).apply(snippetCopy);
745
746        assert checkAllVarargPlaceholdersAreDeleted(parameterCount, placeholders);
747
748        new FloatingReadPhase(true, true).apply(snippetCopy);
749
750        MemoryAnchorNode anchor = snippetCopy.add(new MemoryAnchorNode());
751        snippetCopy.start().replaceAtUsages(InputType.Memory, anchor);
752
753        this.snippet = snippetCopy;
754
755        Debug.dump(snippet, "SnippetTemplate after fixing memory anchoring");
756
757        StartNode entryPointNode = snippet.start();
758        if (anchor.hasNoUsages()) {
759            anchor.safeDelete();
760            this.memoryAnchor = null;
761        } else {
762            snippetCopy.addAfterFixed(snippetCopy.start(), anchor);
763            this.memoryAnchor = anchor;
764        }
765        List<ReturnNode> returnNodes = snippet.getNodes(ReturnNode.TYPE).snapshot();
766        if (returnNodes.isEmpty()) {
767            this.returnNode = null;
768        } else if (returnNodes.size() == 1) {
769            this.returnNode = returnNodes.get(0);
770        } else {
771            AbstractMergeNode merge = snippet.add(new MergeNode());
772            List<MemoryMapNode> memMaps = returnNodes.stream().map(n -> n.getMemoryMap()).collect(Collectors.toList());
773            ValueNode returnValue = InliningUtil.mergeReturns(merge, returnNodes, null);
774            this.returnNode = snippet.add(new ReturnNode(returnValue));
775            MemoryMapImpl mmap = FloatingReadPhase.mergeMemoryMaps(merge, memMaps);
776            MemoryMapNode memoryMap = snippet.unique(new MemoryMapNode(mmap.getMap()));
777            this.returnNode.setMemoryMap(memoryMap);
778            for (MemoryMapNode mm : memMaps) {
779                if (mm != memoryMap && mm.isAlive()) {
780                    assert mm.hasNoUsages();
781                    GraphUtil.killWithUnusedFloatingInputs(mm);
782                }
783            }
784            merge.setNext(this.returnNode);
785        }
786
787        this.sideEffectNodes = curSideEffectNodes;
788        this.deoptNodes = curDeoptNodes;
789        this.stampNodes = curStampNodes;
790
791        nodes = new ArrayList<>(snippet.getNodeCount());
792        for (Node node : snippet.getNodes()) {
793            if (node != entryPointNode && node != entryPointNode.stateAfter()) {
794                nodes.add(node);
795            }
796        }
797
798        Debug.metric("SnippetTemplateNodeCount[%#s]", args).add(nodes.size());
799        if (UseSnippetTemplateCache && args.cacheable) {
800            args.info.notifyNewTemplate();
801        }
802        Debug.dump(snippet, "SnippetTemplate final state");
803    }
804
805    protected Object[] getConstantArgs(Arguments args) {
806        Object[] constantArgs = args.values.clone();
807        for (int i = 0; i < args.info.getParameterCount(); i++) {
808            if (!args.info.isConstantParameter(i)) {
809                constantArgs[i] = null;
810            } else {
811                assert constantArgs[i] != null : "Can't pass raw null through as argument";
812            }
813        }
814        return constantArgs;
815    }
816
817    private static boolean checkAllVarargPlaceholdersAreDeleted(int parameterCount, VarargsPlaceholderNode[] placeholders) {
818        for (int i = 0; i < parameterCount; i++) {
819            if (placeholders[i] != null) {
820                assert placeholders[i].isDeleted() : placeholders[i];
821            }
822        }
823        return true;
824    }
825
826    private static boolean checkConstantArgument(MetaAccessProvider metaAccess, final ResolvedJavaMethod method, Signature signature, int i, String name, Object arg, Kind kind) {
827        ResolvedJavaType type = signature.getParameterType(i, method.getDeclaringClass()).resolve(method.getDeclaringClass());
828        if (metaAccess.lookupJavaType(WordBase.class).isAssignableFrom(type)) {
829            assert arg instanceof JavaConstant : method + ": word constant parameters must be passed boxed in a Constant value: " + arg;
830            return true;
831        }
832        if (kind != Kind.Object) {
833            assert arg != null && kind.toBoxedJavaClass() == arg.getClass() : method + ": wrong value kind for " + name + ": expected " + kind + ", got " +
834                            (arg == null ? "null" : arg.getClass().getSimpleName());
835        }
836        return true;
837    }
838
839    private static boolean checkVarargs(MetaAccessProvider metaAccess, final ResolvedJavaMethod method, Signature signature, int i, String name, Varargs varargs) {
840        ResolvedJavaType type = (ResolvedJavaType) signature.getParameterType(i, method.getDeclaringClass());
841        assert type.isArray() : "varargs parameter must be an array type";
842        assert type.getComponentType().isAssignableFrom(metaAccess.lookupJavaType(varargs.componentType)) : "componentType for " + name + " not matching " + type.toJavaName() + " instance: " +
843                        varargs.componentType;
844        return true;
845    }
846
847    /**
848     * The graph built from the snippet method.
849     */
850    private final StructuredGraph snippet;
851
852    private final SnippetInfo info;
853
854    /**
855     * The named parameters of this template that must be bound to values during instantiation. For
856     * a parameter that is still live after specialization, the value in this map is either a
857     * {@link ParameterNode} instance or a {@link ParameterNode} array. For an eliminated parameter,
858     * the value is identical to the key.
859     */
860    private final Object[] parameters;
861
862    /**
863     * The return node (if any) of the snippet.
864     */
865    private final ReturnNode returnNode;
866
867    /**
868     * The memory anchor (if any) of the snippet.
869     */
870    private final MemoryAnchorNode memoryAnchor;
871
872    /**
873     * Nodes that inherit the {@link StateSplit#stateAfter()} from the replacee during
874     * instantiation.
875     */
876    private final ArrayList<StateSplit> sideEffectNodes;
877
878    /**
879     * Nodes that inherit a deoptimization {@link FrameState} from the replacee during
880     * instantiation.
881     */
882    private final ArrayList<DeoptimizingNode> deoptNodes;
883
884    /**
885     * The nodes that inherit the {@link ValueNode#stamp()} from the replacee during instantiation.
886     */
887    private final ArrayList<ValueNode> stampNodes;
888
889    /**
890     * The nodes to be inlined when this specialization is instantiated.
891     */
892    private final ArrayList<Node> nodes;
893
894    /**
895     * Times instantiations of this template.
896     *
897     * @see SnippetInfo#instantiationTimer
898     */
899    private final DebugTimer instantiationTimer;
900
901    /**
902     * Counts instantiations of this template.
903     *
904     * @see SnippetInfo#instantiationCounter
905     */
906    private final DebugMetric instantiationCounter;
907
908    /**
909     * Gets the instantiation-time bindings to this template's parameters.
910     *
911     * @return the map that will be used to bind arguments to parameters when inlining this template
912     */
913    private Map<Node, Node> bind(StructuredGraph replaceeGraph, MetaAccessProvider metaAccess, Arguments args) {
914        Map<Node, Node> replacements = Node.newIdentityMap();
915        assert args.info.getParameterCount() == parameters.length : "number of args (" + args.info.getParameterCount() + ") != number of parameters (" + parameters.length + ")";
916        for (int i = 0; i < parameters.length; i++) {
917            Object parameter = parameters[i];
918            assert parameter != null : this + " has no parameter named " + args.info.getParameterName(i);
919            Object argument = args.values[i];
920            if (parameter instanceof ParameterNode) {
921                if (argument instanceof ValueNode) {
922                    replacements.put((ParameterNode) parameter, (ValueNode) argument);
923                } else {
924                    Kind kind = ((ParameterNode) parameter).getKind();
925                    assert argument != null || kind == Kind.Object : this + " cannot accept null for non-object parameter named " + args.info.getParameterName(i);
926                    JavaConstant constant = forBoxed(argument, kind);
927                    replacements.put((ParameterNode) parameter, ConstantNode.forConstant(constant, metaAccess, replaceeGraph));
928                }
929            } else if (parameter instanceof ParameterNode[]) {
930                ParameterNode[] params = (ParameterNode[]) parameter;
931                Varargs varargs = (Varargs) argument;
932                int length = params.length;
933                List<?> list = null;
934                Object array = null;
935                if (varargs.value instanceof List) {
936                    list = (List<?>) varargs.value;
937                    assert list.size() == length : length + " != " + list.size();
938                } else {
939                    array = varargs.value;
940                    assert array != null && array.getClass().isArray();
941                    assert Array.getLength(array) == length : length + " != " + Array.getLength(array);
942                }
943
944                for (int j = 0; j < length; j++) {
945                    ParameterNode param = params[j];
946                    assert param != null;
947                    Object value = list != null ? list.get(j) : Array.get(array, j);
948                    if (value instanceof ValueNode) {
949                        replacements.put(param, (ValueNode) value);
950                    } else {
951                        JavaConstant constant = forBoxed(value, param.getKind());
952                        ConstantNode element = ConstantNode.forConstant(constant, metaAccess, replaceeGraph);
953                        replacements.put(param, element);
954                    }
955                }
956            } else {
957                assert parameter.equals(CONSTANT_PARAMETER) || parameter.equals(UNUSED_PARAMETER) : "unexpected entry for parameter: " + args.info.getParameterName(i) + " -> " + parameter;
958            }
959        }
960        return replacements;
961    }
962
963    /**
964     * Converts a Java boxed value to a {@link JavaConstant} of the right kind. This adjusts for the
965     * limitation that a {@link Local}'s kind is a {@linkplain Kind#getStackKind() stack kind} and
966     * so cannot be used for re-boxing primitives smaller than an int.
967     *
968     * @param argument a Java boxed value
969     * @param localKind the kind of the {@link Local} to which {@code argument} will be bound
970     */
971    protected JavaConstant forBoxed(Object argument, Kind localKind) {
972        assert localKind == localKind.getStackKind();
973        if (localKind == Kind.Int) {
974            return JavaConstant.forBoxedPrimitive(argument);
975        }
976        return snippetReflection.forBoxed(localKind, argument);
977    }
978
979    /**
980     * Logic for replacing a snippet-lowered node at its usages with the return value of the
981     * snippet. An alternative to the {@linkplain SnippetTemplate#DEFAULT_REPLACER default}
982     * replacement logic can be used to handle mismatches between the stamp of the node being
983     * lowered and the stamp of the snippet's return value.
984     */
985    public interface UsageReplacer {
986        /**
987         * Replaces all usages of {@code oldNode} with direct or indirect usages of {@code newNode}.
988         */
989        void replace(ValueNode oldNode, ValueNode newNode);
990    }
991
992    /**
993     * Represents the default {@link UsageReplacer usage replacer} logic which simply delegates to
994     * {@link Node#replaceAtUsages(Node)}.
995     */
996    public static final UsageReplacer DEFAULT_REPLACER = new UsageReplacer() {
997
998        @Override
999        public void replace(ValueNode oldNode, ValueNode newNode) {
1000            if (newNode == null) {
1001                assert oldNode.hasNoUsages();
1002            } else {
1003                oldNode.replaceAtUsages(newNode);
1004            }
1005        }
1006    };
1007
1008    private boolean assertSnippetKills(ValueNode replacee) {
1009        if (!replacee.graph().isAfterFloatingReadPhase()) {
1010            // no floating reads yet, ignore locations created while lowering
1011            return true;
1012        }
1013        if (returnNode == null) {
1014            // The snippet terminates control flow
1015            return true;
1016        }
1017        MemoryMapNode memoryMap = returnNode.getMemoryMap();
1018        if (memoryMap == null || memoryMap.isEmpty()) {
1019            // there are no kills in the snippet graph
1020            return true;
1021        }
1022
1023        Set<LocationIdentity> kills = new HashSet<>(memoryMap.getLocations());
1024
1025        if (replacee instanceof MemoryCheckpoint.Single) {
1026            // check if some node in snippet graph also kills the same location
1027            LocationIdentity locationIdentity = ((MemoryCheckpoint.Single) replacee).getLocationIdentity();
1028            if (locationIdentity.isAny()) {
1029                assert !(memoryMap.getLastLocationAccess(any()) instanceof MemoryAnchorNode) : replacee + " kills ANY_LOCATION, but snippet does not";
1030                // if the replacee kills ANY_LOCATION, the snippet can kill arbitrary locations
1031                return true;
1032            }
1033            assert kills.contains(locationIdentity) : replacee + " kills " + locationIdentity + ", but snippet doesn't contain a kill to this location";
1034            kills.remove(locationIdentity);
1035        }
1036        assert !(replacee instanceof MemoryCheckpoint.Multi) : replacee + " multi not supported (yet)";
1037
1038        // remove ANY_LOCATION if it's just a kill by the start node
1039        if (memoryMap.getLastLocationAccess(any()) instanceof MemoryAnchorNode) {
1040            kills.remove(any());
1041        }
1042
1043        // node can only lower to a ANY_LOCATION kill if the replacee also kills ANY_LOCATION
1044        assert !kills.contains(any()) : "snippet graph contains a kill to ANY_LOCATION, but replacee (" + replacee + ") doesn't kill ANY_LOCATION.  kills: " + kills;
1045
1046        /*
1047         * Kills to private locations are safe, since there can be no floating read to these
1048         * locations except reads that are introduced by the snippet itself or related snippets in
1049         * the same lowering round. These reads are anchored to a MemoryAnchor at the beginning of
1050         * their snippet, so they can not float above a kill in another instance of the same
1051         * snippet.
1052         */
1053        for (LocationIdentity p : this.info.privateLocations) {
1054            kills.remove(p);
1055        }
1056
1057        assert kills.isEmpty() : "snippet graph kills non-private locations " + Arrays.toString(kills.toArray()) + " that replacee (" + replacee + ") doesn't kill";
1058        return true;
1059    }
1060
1061    private static class MemoryInputMap implements MemoryMap {
1062
1063        private final LocationIdentity locationIdentity;
1064        private final MemoryNode lastLocationAccess;
1065
1066        public MemoryInputMap(ValueNode replacee) {
1067            if (replacee instanceof MemoryAccess) {
1068                MemoryAccess access = (MemoryAccess) replacee;
1069                locationIdentity = access.getLocationIdentity();
1070                lastLocationAccess = access.getLastLocationAccess();
1071            } else {
1072                locationIdentity = null;
1073                lastLocationAccess = null;
1074            }
1075        }
1076
1077        @Override
1078        public MemoryNode getLastLocationAccess(LocationIdentity location) {
1079            if (locationIdentity != null && locationIdentity.equals(location)) {
1080                return lastLocationAccess;
1081            } else {
1082                return null;
1083            }
1084        }
1085
1086        @Override
1087        public Collection<LocationIdentity> getLocations() {
1088            if (locationIdentity == null) {
1089                return Collections.emptySet();
1090            } else {
1091                return Collections.singleton(locationIdentity);
1092            }
1093        }
1094    }
1095
1096    private class MemoryOutputMap extends MemoryInputMap {
1097
1098        private final Map<Node, Node> duplicates;
1099
1100        public MemoryOutputMap(ValueNode replacee, Map<Node, Node> duplicates) {
1101            super(replacee);
1102            this.duplicates = duplicates;
1103        }
1104
1105        @Override
1106        public MemoryNode getLastLocationAccess(LocationIdentity locationIdentity) {
1107            MemoryMapNode memoryMap = returnNode.getMemoryMap();
1108            assert memoryMap != null : "no memory map stored for this snippet graph (snippet doesn't have a ReturnNode?)";
1109            MemoryNode lastLocationAccess = memoryMap.getLastLocationAccess(locationIdentity);
1110            assert lastLocationAccess != null : locationIdentity;
1111            if (lastLocationAccess == memoryAnchor) {
1112                return super.getLastLocationAccess(locationIdentity);
1113            } else {
1114                return (MemoryNode) duplicates.get(ValueNodeUtil.asNode(lastLocationAccess));
1115            }
1116        }
1117
1118        @Override
1119        public Collection<LocationIdentity> getLocations() {
1120            return returnNode.getMemoryMap().getLocations();
1121        }
1122    }
1123
1124    private void rewireMemoryGraph(ValueNode replacee, Map<Node, Node> duplicates) {
1125        if (replacee.graph().isAfterFloatingReadPhase()) {
1126            // rewire outgoing memory edges
1127            replaceMemoryUsages(replacee, new MemoryOutputMap(replacee, duplicates));
1128
1129            if (returnNode != null) {
1130                ReturnNode ret = (ReturnNode) duplicates.get(returnNode);
1131                MemoryMapNode memoryMap = ret.getMemoryMap();
1132                ret.setMemoryMap(null);
1133                memoryMap.safeDelete();
1134            }
1135            if (memoryAnchor != null) {
1136                // rewire incoming memory edges
1137                MemoryAnchorNode memoryDuplicate = (MemoryAnchorNode) duplicates.get(memoryAnchor);
1138                replaceMemoryUsages(memoryDuplicate, new MemoryInputMap(replacee));
1139
1140                if (memoryDuplicate.hasNoUsages()) {
1141                    memoryDuplicate.graph().removeFixed(memoryDuplicate);
1142                }
1143            }
1144        }
1145    }
1146
1147    private static LocationIdentity getLocationIdentity(Node node) {
1148        if (node instanceof MemoryAccess) {
1149            return ((MemoryAccess) node).getLocationIdentity();
1150        } else if (node instanceof MemoryProxy) {
1151            return ((MemoryProxy) node).getLocationIdentity();
1152        } else if (node instanceof MemoryPhiNode) {
1153            return ((MemoryPhiNode) node).getLocationIdentity();
1154        } else {
1155            return null;
1156        }
1157    }
1158
1159    private void replaceMemoryUsages(ValueNode node, MemoryMap map) {
1160        for (Node usage : node.usages().snapshot()) {
1161            if (usage instanceof MemoryMapNode) {
1162                continue;
1163            }
1164
1165            LocationIdentity location = getLocationIdentity(usage);
1166            if (location != null) {
1167                NodePosIterator iter = usage.inputs().iterator();
1168                while (iter.hasNext()) {
1169                    Position pos = iter.nextPosition();
1170                    if (pos.getInputType() == InputType.Memory && pos.get(usage) == node) {
1171                        MemoryNode replacement = map.getLastLocationAccess(location);
1172                        if (replacement == null) {
1173                            assert LocationIdentity.any().equals(location) || Arrays.stream(info.privateLocations).anyMatch(Predicate.isEqual(location)) : "Snippet " + info.method.format("%h.%n") +
1174                                            " contains access to the non-private location " + location + ", but replacee doesn't access this location." + map.getLocations();
1175                        } else {
1176                            pos.set(usage, replacement.asNode());
1177                        }
1178                    }
1179                }
1180            }
1181        }
1182    }
1183
1184    /**
1185     * Replaces a given fixed node with this specialized snippet.
1186     *
1187     * @param metaAccess
1188     * @param replacee the node that will be replaced
1189     * @param replacer object that replaces the usages of {@code replacee}
1190     * @param args the arguments to be bound to the flattened positional parameters of the snippet
1191     * @return the map of duplicated nodes (original -&gt; duplicate)
1192     */
1193    public Map<Node, Node> instantiate(MetaAccessProvider metaAccess, FixedNode replacee, UsageReplacer replacer, Arguments args) {
1194        assert assertSnippetKills(replacee);
1195        try (DebugCloseable a = args.info.instantiationTimer.start(); DebugCloseable b = instantiationTimer.start()) {
1196            args.info.instantiationCounter.increment();
1197            instantiationCounter.increment();
1198            // Inline the snippet nodes, replacing parameters with the given args in the process
1199            StartNode entryPointNode = snippet.start();
1200            FixedNode firstCFGNode = entryPointNode.next();
1201            StructuredGraph replaceeGraph = replacee.graph();
1202            Map<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1203            replacements.put(entryPointNode, AbstractBeginNode.prevBegin(replacee));
1204            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1205            Debug.dump(replaceeGraph, "After inlining snippet %s", snippet.method());
1206
1207            // Re-wire the control flow graph around the replacee
1208            FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1209            replacee.replaceAtPredecessor(firstCFGNodeDuplicate);
1210
1211            if (replacee instanceof StateSplit) {
1212                for (StateSplit sideEffectNode : sideEffectNodes) {
1213                    assert ((StateSplit) replacee).hasSideEffect();
1214                    Node sideEffectDup = duplicates.get(sideEffectNode);
1215                    ((StateSplit) sideEffectDup).setStateAfter(((StateSplit) replacee).stateAfter());
1216                }
1217            }
1218
1219            if (replacee instanceof DeoptimizingNode) {
1220                DeoptimizingNode replaceeDeopt = (DeoptimizingNode) replacee;
1221
1222                FrameState stateBefore = null;
1223                FrameState stateDuring = null;
1224                FrameState stateAfter = null;
1225                if (replaceeDeopt.canDeoptimize()) {
1226                    if (replaceeDeopt instanceof DeoptimizingNode.DeoptBefore) {
1227                        stateBefore = ((DeoptimizingNode.DeoptBefore) replaceeDeopt).stateBefore();
1228                    }
1229                    if (replaceeDeopt instanceof DeoptimizingNode.DeoptDuring) {
1230                        stateDuring = ((DeoptimizingNode.DeoptDuring) replaceeDeopt).stateDuring();
1231                    }
1232                    if (replaceeDeopt instanceof DeoptimizingNode.DeoptAfter) {
1233                        stateAfter = ((DeoptimizingNode.DeoptAfter) replaceeDeopt).stateAfter();
1234                    }
1235                }
1236
1237                for (DeoptimizingNode deoptNode : deoptNodes) {
1238                    DeoptimizingNode deoptDup = (DeoptimizingNode) duplicates.get(deoptNode);
1239                    if (deoptDup.canDeoptimize()) {
1240                        if (deoptDup instanceof DeoptimizingNode.DeoptBefore) {
1241                            ((DeoptimizingNode.DeoptBefore) deoptDup).setStateBefore(stateBefore);
1242                        }
1243                        if (deoptDup instanceof DeoptimizingNode.DeoptDuring) {
1244                            DeoptimizingNode.DeoptDuring deoptDupDuring = (DeoptimizingNode.DeoptDuring) deoptDup;
1245                            if (stateDuring != null) {
1246                                deoptDupDuring.setStateDuring(stateDuring);
1247                            } else if (stateAfter != null) {
1248                                deoptDupDuring.computeStateDuring(stateAfter);
1249                            } else if (stateBefore != null) {
1250                                assert !deoptDupDuring.hasSideEffect() : "can't use stateBefore as stateDuring for state split " + deoptDupDuring;
1251                                deoptDupDuring.setStateDuring(stateBefore);
1252                            }
1253                        }
1254                        if (deoptDup instanceof DeoptimizingNode.DeoptAfter) {
1255                            DeoptimizingNode.DeoptAfter deoptDupAfter = (DeoptimizingNode.DeoptAfter) deoptDup;
1256                            if (stateAfter != null) {
1257                                deoptDupAfter.setStateAfter(stateAfter);
1258                            } else {
1259                                assert !deoptDupAfter.hasSideEffect() : "can't use stateBefore as stateAfter for state split " + deoptDupAfter;
1260                                deoptDupAfter.setStateAfter(stateBefore);
1261                            }
1262
1263                        }
1264                    }
1265                }
1266            }
1267
1268            updateStamps(replacee, duplicates);
1269
1270            rewireMemoryGraph(replacee, duplicates);
1271
1272            // Replace all usages of the replacee with the value returned by the snippet
1273            ValueNode returnValue = null;
1274            if (returnNode != null && !(replacee instanceof ControlSinkNode)) {
1275                ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1276                returnValue = returnDuplicate.result();
1277                if (returnValue == null && replacee.usages().isNotEmpty() && replacee instanceof MemoryCheckpoint) {
1278                    replacer.replace(replacee, null);
1279                } else {
1280                    assert returnValue != null || replacee.hasNoUsages();
1281                    replacer.replace(replacee, returnValue);
1282                }
1283                if (returnDuplicate.isAlive()) {
1284                    FixedNode next = null;
1285                    if (replacee instanceof FixedWithNextNode) {
1286                        FixedWithNextNode fwn = (FixedWithNextNode) replacee;
1287                        next = fwn.next();
1288                        fwn.setNext(null);
1289                    }
1290                    returnDuplicate.replaceAndDelete(next);
1291                }
1292            }
1293
1294            // Remove the replacee from its graph
1295            GraphUtil.killCFG(replacee);
1296
1297            Debug.dump(replaceeGraph, "After lowering %s with %s", replacee, this);
1298            return duplicates;
1299        }
1300    }
1301
1302    private void propagateStamp(Node node) {
1303        if (node instanceof PhiNode) {
1304            PhiNode phi = (PhiNode) node;
1305            if (phi.inferStamp()) {
1306                for (Node usage : node.usages()) {
1307                    propagateStamp(usage);
1308                }
1309            }
1310        }
1311    }
1312
1313    private void updateStamps(ValueNode replacee, Map<Node, Node> duplicates) {
1314        for (ValueNode stampNode : stampNodes) {
1315            Node stampDup = duplicates.get(stampNode);
1316            ((ValueNode) stampDup).setStamp(replacee.stamp());
1317        }
1318        for (ParameterNode paramNode : snippet.getNodes(ParameterNode.TYPE)) {
1319            for (Node usage : paramNode.usages()) {
1320                Node usageDup = duplicates.get(usage);
1321                propagateStamp(usageDup);
1322            }
1323        }
1324    }
1325
1326    /**
1327     * Gets a copy of the specialized graph.
1328     */
1329    public StructuredGraph copySpecializedGraph() {
1330        return (StructuredGraph) snippet.copy();
1331    }
1332
1333    /**
1334     * Replaces a given floating node with this specialized snippet.
1335     *
1336     * @param metaAccess
1337     * @param replacee the node that will be replaced
1338     * @param replacer object that replaces the usages of {@code replacee}
1339     * @param args the arguments to be bound to the flattened positional parameters of the snippet
1340     */
1341    public void instantiate(MetaAccessProvider metaAccess, FloatingNode replacee, UsageReplacer replacer, LoweringTool tool, Arguments args) {
1342        assert assertSnippetKills(replacee);
1343        try (DebugCloseable a = args.info.instantiationTimer.start()) {
1344            args.info.instantiationCounter.increment();
1345            instantiationCounter.increment();
1346
1347            // Inline the snippet nodes, replacing parameters with the given args in the process
1348            String name = snippet.name == null ? "{copy}" : snippet.name + "{copy}";
1349            StructuredGraph snippetCopy = new StructuredGraph(name, snippet.method(), AllowAssumptions.NO);
1350            StartNode entryPointNode = snippet.start();
1351            FixedNode firstCFGNode = entryPointNode.next();
1352            StructuredGraph replaceeGraph = replacee.graph();
1353            Map<Node, Node> replacements = bind(replaceeGraph, metaAccess, args);
1354            replacements.put(entryPointNode, tool.getCurrentGuardAnchor().asNode());
1355            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
1356            Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method());
1357
1358            FixedWithNextNode lastFixedNode = tool.lastFixedNode();
1359            assert lastFixedNode != null && lastFixedNode.isAlive() : replaceeGraph + " lastFixed=" + lastFixedNode;
1360            FixedNode next = lastFixedNode.next();
1361            lastFixedNode.setNext(null);
1362            FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1363            replaceeGraph.addAfterFixed(lastFixedNode, firstCFGNodeDuplicate);
1364
1365            if (replacee instanceof StateSplit) {
1366                for (StateSplit sideEffectNode : sideEffectNodes) {
1367                    assert ((StateSplit) replacee).hasSideEffect();
1368                    Node sideEffectDup = duplicates.get(sideEffectNode);
1369                    ((StateSplit) sideEffectDup).setStateAfter(((StateSplit) replacee).stateAfter());
1370                }
1371            }
1372            updateStamps(replacee, duplicates);
1373
1374            rewireMemoryGraph(replacee, duplicates);
1375
1376            // Replace all usages of the replacee with the value returned by the snippet
1377            ReturnNode returnDuplicate = (ReturnNode) duplicates.get(returnNode);
1378            ValueNode returnValue = returnDuplicate.result();
1379            assert returnValue != null || replacee.hasNoUsages();
1380            replacer.replace(replacee, returnValue);
1381
1382            if (returnDuplicate.isAlive()) {
1383                returnDuplicate.replaceAndDelete(next);
1384            }
1385
1386            Debug.dump(replaceeGraph, "After lowering %s with %s", replacee, this);
1387        }
1388    }
1389
1390    @Override
1391    public String toString() {
1392        StringBuilder buf = new StringBuilder(snippet.toString()).append('(');
1393        String sep = "";
1394        for (int i = 0; i < parameters.length; i++) {
1395            String name = "[" + i + "]";
1396            Object value = parameters[i];
1397            buf.append(sep);
1398            sep = ", ";
1399            if (value == null) {
1400                buf.append("<null> ").append(name);
1401            } else if (value.equals(UNUSED_PARAMETER)) {
1402                buf.append("<unused> ").append(name);
1403            } else if (value.equals(CONSTANT_PARAMETER)) {
1404                buf.append("<constant> ").append(name);
1405            } else if (value instanceof ParameterNode) {
1406                ParameterNode param = (ParameterNode) value;
1407                buf.append(param.getKind().getJavaName()).append(' ').append(name);
1408            } else {
1409                ParameterNode[] params = (ParameterNode[]) value;
1410                String kind = params.length == 0 ? "?" : params[0].getKind().getJavaName();
1411                buf.append(kind).append('[').append(params.length).append("] ").append(name);
1412            }
1413        }
1414        return buf.append(')').toString();
1415    }
1416
1417    private static boolean checkTemplate(MetaAccessProvider metaAccess, Arguments args, ResolvedJavaMethod method, Signature signature) {
1418        for (int i = 0; i < args.info.getParameterCount(); i++) {
1419            if (args.info.isConstantParameter(i)) {
1420                Kind kind = signature.getParameterKind(i);
1421                assert checkConstantArgument(metaAccess, method, signature, i, args.info.getParameterName(i), args.values[i], kind);
1422
1423            } else if (args.info.isVarargsParameter(i)) {
1424                assert args.values[i] instanceof Varargs;
1425                Varargs varargs = (Varargs) args.values[i];
1426                assert checkVarargs(metaAccess, method, signature, i, args.info.getParameterName(i), varargs);
1427            }
1428        }
1429        return true;
1430    }
1431}