/*

 * Copyright (c) 2012, 2016, 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 org.graalvm.compiler.core.common.CompilationIdentifier.INVALID_COMPILATION_ID;

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

import static org.graalvm.compiler.core.common.LocationIdentity.ANY_LOCATION;

import static org.graalvm.compiler.core.common.LocationIdentity.any;

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

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 java.util.FormattableFlags.ALTERNATE;

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.HashSet;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Map;

import java.util.Objects;

import java.util.Set;

import java.util.concurrent.atomic.AtomicReference;

import java.util.function.Predicate;

import java.util.stream.Collectors;

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

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

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.LocationIdentity;

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.Debug;

import org.graalvm.compiler.debug.Debug.Scope;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugCounter;

import org.graalvm.compiler.debug.DebugTimer;

import org.graalvm.compiler.debug.GraalError;

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

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeClass;

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.LoopBeginNode;

import org.graalvm.compiler.nodes.MergeNode;

import org.graalvm.compiler.nodes.ParameterNode;

import org.graalvm.compiler.nodes.PhiNode;

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.AllowAssumptions;

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.debug.instrumentation.InstrumentationNode;

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

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.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.OptionValue;

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.inlining.InliningUtil;

import org.graalvm.compiler.phases.tiers.PhaseContext;

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

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

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

import org.graalvm.compiler.word.WordBase;

import jdk.vm.ci.code.TargetDescription;

import jdk.vm.ci.meta.Constant;

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.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 ResolvedJavaMethod original;

        protected final LocationIdentity[] privateLocations;

        /**

         * Lazily constructed parts of {@link SnippetInfo}.

         */

        static class Lazy {

            Lazy(ResolvedJavaMethod method) {

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

                constantParameters = new boolean[count];

                varargsParameters = new boolean[count];

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

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

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

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

                                    VarargsParameter.class.getSimpleName();

                }

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

                assert initNames(method, count);

            }

            final boolean[] constantParameters;

            final boolean[] varargsParameters;

            /**

             * 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 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 form this snippet.

         *

         * @see SnippetTemplate#instantiationTimer

         */

        private final DebugTimer instantiationTimer;

        /**

         * Counts instantiations of all templates derived from this snippet.

         *

         * @see SnippetTemplate#instantiationCounter

         */

        private final DebugCounter instantiationCounter;

        protected abstract Lazy lazy();

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

            this.method = method;

            this.privateLocations = SnippetCounterNode.addSnippetCounters(privateLocations);

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

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

            assert method.isStatic() : "snippet method must be static: " + method.format("%H.%n");

        }

        public ResolvedJavaMethod getMethod() {

            return method;

        }

        public int getParameterCount() {

            return lazy().constantParameters.length;

        }

        public void setOriginalMethod(ResolvedJavaMethod original) {

            this.original = original;

        }

        public boolean isConstantParameter(int paramIdx) {

            return lazy().constantParameters[paramIdx];

        }

        public boolean isVarargsParameter(int paramIdx) {

            return lazy().varargsParameters[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, LocationIdentity[] privateLocations) {

            super(method, privateLocations);

        }

        @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, LocationIdentity[] privateLocations) {

            super(method, privateLocations);

            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;

        }

        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: " + 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[]) {

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

            }

            if (value instanceof int[]) {

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

            }

            if (value instanceof long[]) {

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

            }

            if (value instanceof float[]) {

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

            }

            if (value instanceof double[]) {

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

            }

            if (value instanceof Object[]) {

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

            }

            return String.valueOf(value);

        }

    }

    @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)

    static final class VarargsPlaceholderNode extends FloatingNode implements ArrayLengthProvider {

        public static final NodeClass<VarargsPlaceholderNode> TYPE = NodeClass.create(VarargsPlaceholderNode.class);

        protected final Varargs varargs;

        protected VarargsPlaceholderNode(Varargs varargs, MetaAccessProvider metaAccess) {

            super(TYPE, StampFactory.objectNonNull(TypeReference.createExactTrusted(metaAccess.lookupJavaType(varargs.componentType).getArrayClass())));

            this.varargs = varargs;

        }

        @Override

        public ValueNode length() {

            return ConstantNode.forInt(varargs.length);

        }

    }

    static class CacheKey {

        private final ResolvedJavaMethod method;

        private final Object[] values;

        private final GuardsStage guardsStage;

        private final LoweringTool.LoweringStage loweringStage;

        private int hash;

        protected CacheKey(SnippetInfo info, GuardsStage guardsStage, LoweringTool.LoweringStage loweringStage) {

            this.method = info.method;

            this.guardsStage = guardsStage;

            this.loweringStage = loweringStage;

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

            this.hash = info.method.hashCode() + 31 * guardsStage.ordinal();

        }

        protected void setParam(int paramIdx, Object value) {

            values[paramIdx] = value;

            hash = (hash * 31) ^ (value == null ? 0 : value.hashCode());

        }

        @Override

        public boolean equals(Object obj) {

            if (!(obj instanceof CacheKey)) {

                return false;

            }

            CacheKey other = (CacheKey) obj;

            if (!method.equals(other.method)) {

                return false;

            }

            if (guardsStage != other.guardsStage || loweringStage != other.loweringStage) {

                return false;