/*

 * Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.compiler.replacements;

import static java.util.FormattableFlags.ALTERNATE;

import static jdk.vm.ci.services.Services.IS_IN_NATIVE_IMAGE;

import static org.graalvm.compiler.debug.DebugContext.DEFAULT_LOG_STREAM;

import static org.graalvm.compiler.debug.DebugContext.applyFormattingFlagsAndWidth;

import static org.graalvm.compiler.debug.DebugOptions.DebugStubsAndSnippets;

import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;

import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;

import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;

import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;

import static jdk.internal.vm.compiler.word.LocationIdentity.any;

import java.lang.reflect.Array;

import java.lang.reflect.Method;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.Formattable;

import java.util.Formatter;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Map;

import java.util.concurrent.atomic.AtomicInteger;

import java.util.concurrent.atomic.AtomicReference;

import java.util.function.Predicate;

import jdk.internal.vm.compiler.collections.EconomicMap;

import jdk.internal.vm.compiler.collections.EconomicSet;

import jdk.internal.vm.compiler.collections.Equivalence;

import jdk.internal.vm.compiler.collections.UnmodifiableEconomicMap;

import org.graalvm.compiler.api.replacements.Fold;

import org.graalvm.compiler.api.replacements.Snippet;

import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;

import org.graalvm.compiler.api.replacements.Snippet.NonNullParameter;

import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter;

import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;

import org.graalvm.compiler.core.common.GraalOptions;

import org.graalvm.compiler.core.common.type.Stamp;

import org.graalvm.compiler.core.common.type.StampFactory;

import org.graalvm.compiler.core.common.type.StampPair;

import org.graalvm.compiler.core.common.type.TypeReference;

import org.graalvm.compiler.debug.Assertions;

import org.graalvm.compiler.debug.CounterKey;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.DebugContext.Description;

import org.graalvm.compiler.debug.DebugHandlersFactory;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.debug.TimerKey;

import org.graalvm.compiler.graph.Graph.Mark;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.Node.NodeIntrinsic;

import org.graalvm.compiler.graph.NodeClass;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.graph.Position;

import org.graalvm.compiler.loop.LoopEx;

import org.graalvm.compiler.loop.LoopsData;

import org.graalvm.compiler.loop.phases.LoopTransformations;

import org.graalvm.compiler.nodeinfo.InputType;

import org.graalvm.compiler.nodeinfo.NodeInfo;

import org.graalvm.compiler.nodes.AbstractBeginNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.ConstantNode;

import org.graalvm.compiler.nodes.ControlSinkNode;

import org.graalvm.compiler.nodes.DeoptimizingNode;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.FrameState;

import org.graalvm.compiler.nodes.InliningLog;

import org.graalvm.compiler.nodes.LoopBeginNode;

import org.graalvm.compiler.nodes.MergeNode;

import org.graalvm.compiler.nodes.NodeView;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.PhiNode;

import org.graalvm.compiler.nodes.PiNode.Placeholder;

import org.graalvm.compiler.nodes.PiNode.PlaceholderStamp;

import org.graalvm.compiler.nodes.ReturnNode;

import org.graalvm.compiler.nodes.StartNode;

import org.graalvm.compiler.nodes.StateSplit;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.ValueNodeUtil;

import org.graalvm.compiler.nodes.calc.FloatingNode;

import org.graalvm.compiler.nodes.java.LoadIndexedNode;

import org.graalvm.compiler.nodes.java.MethodCallTargetNode;

import org.graalvm.compiler.nodes.java.StoreIndexedNode;

import org.graalvm.compiler.nodes.memory.MemoryAccess;

import org.graalvm.compiler.nodes.memory.MemoryAnchorNode;

import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;

import org.graalvm.compiler.nodes.memory.MemoryMap;

import org.graalvm.compiler.nodes.memory.MemoryMapNode;

import org.graalvm.compiler.nodes.memory.MemoryNode;

import org.graalvm.compiler.nodes.memory.MemoryPhiNode;

import org.graalvm.compiler.nodes.spi.ArrayLengthProvider;

import org.graalvm.compiler.nodes.spi.CoreProviders;

import org.graalvm.compiler.nodes.spi.LoweringTool;

import org.graalvm.compiler.nodes.spi.MemoryProxy;

import org.graalvm.compiler.nodes.util.GraphUtil;

import org.graalvm.compiler.options.Option;

import org.graalvm.compiler.options.OptionKey;

import org.graalvm.compiler.options.OptionValues;

import org.graalvm.compiler.phases.common.CanonicalizerPhase;

import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;

import org.graalvm.compiler.phases.common.FloatingReadPhase;

import org.graalvm.compiler.phases.common.FloatingReadPhase.MemoryMapImpl;

import org.graalvm.compiler.phases.common.GuardLoweringPhase;

import org.graalvm.compiler.phases.common.LoweringPhase;

import org.graalvm.compiler.phases.common.RemoveValueProxyPhase;

import org.graalvm.compiler.phases.common.inlining.InliningUtil;

import org.graalvm.compiler.phases.util.Providers;

import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;

import org.graalvm.compiler.replacements.nodes.LoadSnippetVarargParameterNode;

import org.graalvm.util.CollectionsUtil;

import jdk.internal.vm.compiler.word.LocationIdentity;

import jdk.internal.vm.compiler.word.WordBase;

import jdk.vm.ci.code.TargetDescription;

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.ConstantReflectionProvider;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.Local;

import jdk.vm.ci.meta.LocalVariableTable;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaMethod.Parameter;

import jdk.vm.ci.meta.ResolvedJavaType;

import jdk.vm.ci.meta.Signature;

/**

 * A snippet template is a graph created by parsing a snippet method and then specialized by binding

 * constants to the snippet's {@link ConstantParameter} parameters.

 *

 * Snippet templates can be managed in a cache maintained by {@link AbstractTemplates}.

 */

public class SnippetTemplate {

    private boolean mayRemoveLocation = false;

    /**

     * Holds the {@link ResolvedJavaMethod} of the snippet, together with some information about the

     * method that needs to be computed only once. The {@link SnippetInfo} should be created once

     * per snippet and then cached.

     */

    public abstract static class SnippetInfo {

        protected final ResolvedJavaMethod method;

        protected final ResolvedJavaMethod original;

        protected final LocationIdentity[] privateLocations;

        protected final Object receiver;

        public Object getReceiver() {

            return receiver;

        }

        boolean hasReceiver() {

            assert hasReceiver(method) == (receiver != null) : "Snippet with the receiver must have it set as constant. Snippet: " + this;

            return hasReceiver(method);

        }

        static boolean hasReceiver(ResolvedJavaMethod method) {

            return method.hasReceiver();

        }

        /**

         * Lazily constructed parts of {@link SnippetInfo}.

         */

        static class Lazy {

            Lazy(ResolvedJavaMethod method) {

                int count = method.getSignature().getParameterCount(hasReceiver(method));

                constantParameters = new boolean[count];

                varargsParameters = new boolean[count];

                nonNullParameters = new boolean[count];

                int offset = hasReceiver(method) ? 1 : 0;

                for (int i = offset; i < count; i++) {

                    constantParameters[i] = method.getParameterAnnotation(ConstantParameter.class, i - offset) != null;

                    varargsParameters[i] = method.getParameterAnnotation(VarargsParameter.class, i - offset) != null;

                    nonNullParameters[i] = method.getParameterAnnotation(NonNullParameter.class, i - offset) != null;

                    assert !constantParameters[i - offset] || !varargsParameters[i - offset] : "Parameter cannot be annotated with both @" + ConstantParameter.class.getSimpleName() + " and @" +

                                    VarargsParameter.class.getSimpleName();

                }

                if (method.hasReceiver()) {

                    // Receiver must be constant.

                    assert !constantParameters[0];

                    constantParameters[0] = true;

                }

                // Retrieve the names only when assertions are turned on. Parameter annotations are

                // unsupported in the native image.

                assert IS_IN_NATIVE_IMAGE || initNames(method, count);

            }

            final boolean[] constantParameters;

            final boolean[] varargsParameters;

            final boolean[] nonNullParameters;

            /**

             * The parameter names, taken from the local variables table. Only used for assertion

             * checking, so use only within an assert statement.

             */

            String[] names;

            private boolean initNames(ResolvedJavaMethod method, int parameterCount) {

                names = new String[parameterCount];

                int offset = 0;

                if (method.hasReceiver()) {

                    names[0] = "this";

                    offset = 1;

                }

                Parameter[] params = method.getParameters();

                if (params != null) {

                    for (int i = offset; i < names.length; i++) {

                        if (params[i - offset].isNamePresent()) {

                            names[i] = params[i - offset].getName();

                        }

                    }

                } else {

                    int slotIdx = 0;

                    LocalVariableTable localVariableTable = method.getLocalVariableTable();

                    if (localVariableTable != null) {

                        for (int i = 0; i < names.length; i++) {

                            Local local = localVariableTable.getLocal(slotIdx, 0);

                            if (local != null) {

                                names[i] = local.getName();

                            }

                            JavaKind kind = method.getSignature().getParameterKind(i);

                            slotIdx += kind.getSlotCount();

                        }

                    }

                }

                return true;

            }

        }

        /**

         * Times instantiations of all templates derived from this snippet.

         */

        private final TimerKey instantiationTimer;

        /**

         * Counts instantiations of all templates derived from this snippet.

         */

        private final CounterKey instantiationCounter;

        protected abstract Lazy lazy();

        protected SnippetInfo(ResolvedJavaMethod method, ResolvedJavaMethod original, LocationIdentity[] privateLocations, Object receiver) {

            this.method = method;

            this.original = original;

            this.privateLocations = privateLocations;

            instantiationCounter = DebugContext.counter("SnippetInstantiationCount[%s]", method.getName());

            instantiationTimer = DebugContext.timer("SnippetInstantiationTime[%s]", method.getName());

            this.receiver = receiver;

        }

        public ResolvedJavaMethod getMethod() {

            return method;

        }

        public int getParameterCount() {

            return lazy().constantParameters.length;

        }

        public boolean isConstantParameter(int paramIdx) {

            return lazy().constantParameters[paramIdx];

        }

        public boolean isVarargsParameter(int paramIdx) {

            return lazy().varargsParameters[paramIdx];

        }

        public boolean isNonNullParameter(int paramIdx) {

            return lazy().nonNullParameters[paramIdx];

        }

        public String getParameterName(int paramIdx) {

            String[] names = lazy().names;

            if (names != null) {

                return names[paramIdx];

            }

            return null;

        }

        @Override

        public String toString() {

            return getClass().getSimpleName() + ":" + method.format("%h.%n");

        }

    }

    protected static class LazySnippetInfo extends SnippetInfo {

        protected final AtomicReference<Lazy> lazy = new AtomicReference<>(null);

        protected LazySnippetInfo(ResolvedJavaMethod method, ResolvedJavaMethod original, LocationIdentity[] privateLocations, Object receiver) {

            super(method, original, privateLocations, receiver);

        }

        @Override

        protected Lazy lazy() {

            if (lazy.get() == null) {

                lazy.compareAndSet(null, new Lazy(method));

            }

            return lazy.get();

        }

    }

    protected static class EagerSnippetInfo extends SnippetInfo {

        protected final Lazy lazy;

        protected EagerSnippetInfo(ResolvedJavaMethod method, ResolvedJavaMethod original, LocationIdentity[] privateLocations, Object receiver) {

            super(method, original, privateLocations, receiver);

            lazy = new Lazy(method);

        }

        @Override

        protected Lazy lazy() {

            return lazy;

        }

    }

    /**

     * Values that are bound to the snippet method parameters. The methods {@link #add},

     * {@link #addConst}, and {@link #addVarargs} must be called in the same order as in the

     * signature of the snippet method. The parameter name is passed to the add methods for

     * assertion checking, i.e., to enforce that the order matches. Which method needs to be called

     * depends on the annotation of the snippet method parameter:

     * <ul>

     * <li>Use {@link #add} for a parameter without an annotation. The value is bound when the

     * {@link SnippetTemplate} is {@link SnippetTemplate#instantiate instantiated}.

     * <li>Use {@link #addConst} for a parameter annotated with {@link ConstantParameter}. The value

     * is bound when the {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created}.

     * <li>Use {@link #addVarargs} for an array parameter annotated with {@link VarargsParameter}. A

     * separate {@link SnippetTemplate} is {@link SnippetTemplate#SnippetTemplate created} for every

     * distinct array length. The actual values are bound when the {@link SnippetTemplate} is

     * {@link SnippetTemplate#instantiate instantiated}

     * </ul>

     */

    public static class Arguments implements Formattable {

        protected final SnippetInfo info;

        protected final CacheKey cacheKey;

        protected final Object[] values;

        protected final Stamp[] constStamps;

        protected boolean cacheable;

        protected int nextParamIdx;

        public Arguments(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {

            this.info = info;

            this.cacheKey = new CacheKey(info, guardsStage, loweringStage);

            this.values = new Object[info.getParameterCount()];

            this.constStamps = new Stamp[info.getParameterCount()];

            this.cacheable = true;

            if (info.hasReceiver()) {

                addConst("this", info.getReceiver());

            }

        }

        public Arguments add(String name, Object value) {

            assert check(name, false, false);

            values[nextParamIdx] = value;

            nextParamIdx++;

            return this;

        }

        public Arguments addConst(String name, Object value) {

            assert value != null;

            return addConst(name, value, null);

        }

        public Arguments addConst(String name, Object value, Stamp stamp) {

            assert check(name, true, false);

            values[nextParamIdx] = value;

            constStamps[nextParamIdx] = stamp;

            cacheKey.setParam(nextParamIdx, value);

            nextParamIdx++;

            return this;

        }

        public Arguments addVarargs(String name, Class<?> componentType, Stamp argStamp, Object value) {

            assert check(name, false, true);

            Varargs varargs = new Varargs(componentType, argStamp, value);

            values[nextParamIdx] = varargs;

            // A separate template is necessary for every distinct array length

            cacheKey.setParam(nextParamIdx, varargs.length);

            nextParamIdx++;

            return this;

        }

        public void setCacheable(boolean cacheable) {

            this.cacheable = cacheable;

        }

        private boolean check(String name, boolean constParam, boolean varargsParam) {

            assert nextParamIdx < info.getParameterCount() : "too many parameters: " + name + "  " + this;

            assert info.getParameterName(nextParamIdx) == null || info.getParameterName(nextParamIdx).equals(name) : "wrong parameter name at " + nextParamIdx + " : " + name + "  " + this;

            assert constParam == info.isConstantParameter(nextParamIdx) : "Parameter " + (constParam ? "not " : "") + "annotated with @" + ConstantParameter.class.getSimpleName() + ": " + name +

                            "  " + this;

            assert varargsParam == info.isVarargsParameter(nextParamIdx) : "Parameter " + (varargsParam ? "not " : "") + "annotated with @" + VarargsParameter.class.getSimpleName() + ": " + name +

                            "  " + this;

            return true;

        }

        @Override

        public String toString() {

            StringBuilder result = new StringBuilder();

            result.append("Parameters<").append(info.method.format("%h.%n")).append(" [");

            String sep = "";

            for (int i = 0; i < info.getParameterCount(); i++) {

                result.append(sep);

                if (info.isConstantParameter(i)) {

                    result.append("const ");

                } else if (info.isVarargsParameter(i)) {

                    result.append("varargs ");

                }

                result.append(info.getParameterName(i)).append(" = ").append(values[i]);

                sep = ", ";

            }

            result.append(">");

            return result.toString();

        }

        @Override

        public void formatTo(Formatter formatter, int flags, int width, int precision) {

            if ((flags & ALTERNATE) == 0) {

                formatter.format(applyFormattingFlagsAndWidth(toString(), flags, width));

            } else {

                StringBuilder sb = new StringBuilder();

                sb.append(info.method.getName()).append('(');

                String sep = "";

                for (int i = 0; i < info.getParameterCount(); i++) {

                    if (info.isConstantParameter(i)) {

                        sb.append(sep);

                        if (info.getParameterName(i) != null) {

                            sb.append(info.getParameterName(i));

                        } else {

                            sb.append(i);

                        }

                        sb.append('=').append(values[i]);

                        sep = ", ";

                    }

                }

                sb.append(")");

                String string = sb.toString();

                if (string.indexOf('%') != -1) {

                    // Quote any % signs

                    string = string.replace("%", "%%");

                }

                formatter.format(applyFormattingFlagsAndWidth(string, flags & ~ALTERNATE, width));

            }

        }

    }

    /**

     * Wrapper for the prototype value of a {@linkplain VarargsParameter varargs} parameter.

     */

    static class Varargs {

        protected final Class<?> componentType;

        protected final Stamp stamp;

        protected final Object value;

        protected final int length;

        protected Varargs(Class<?> componentType, Stamp stamp, Object value) {

            this.componentType = componentType;

            this.stamp = stamp;

            this.value = value;

            if (value instanceof List) {

                this.length = ((List<?>) value).size();

            } else {

                this.length = Array.getLength(value);

            }

        }

        @Override

        public String toString() {

            if (value instanceof boolean[]) {

                return Arrays.toString((boolean[]) value);

            }

            if (value instanceof byte[]) {

                return Arrays.toString((byte[]) value);

            }

            if (value instanceof char[]) {

                return Arrays.toString((char[]) value);

            }

            if (value instanceof short[]) {