/*

 * Copyright (c) 2011, 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 jdk.vm.ci.code.MemoryBarriers.JMM_POST_VOLATILE_READ;

import static jdk.vm.ci.code.MemoryBarriers.JMM_POST_VOLATILE_WRITE;

import static jdk.vm.ci.code.MemoryBarriers.JMM_PRE_VOLATILE_READ;

import static jdk.vm.ci.code.MemoryBarriers.JMM_PRE_VOLATILE_WRITE;

import static jdk.vm.ci.meta.DeoptimizationAction.InvalidateReprofile;

import static jdk.vm.ci.meta.DeoptimizationReason.BoundsCheckException;

import static jdk.vm.ci.meta.DeoptimizationReason.NullCheckException;

import static org.graalvm.compiler.nodes.NamedLocationIdentity.ARRAY_LENGTH_LOCATION;

import static org.graalvm.compiler.nodes.java.ArrayLengthNode.readArrayLength;

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

import java.nio.ByteOrder;

import java.util.ArrayList;

import java.util.BitSet;

import java.util.List;

import org.graalvm.compiler.api.directives.GraalDirectives;

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

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

import org.graalvm.compiler.core.common.spi.ForeignCallDescriptor;

import org.graalvm.compiler.core.common.spi.ForeignCallsProvider;

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

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

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

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

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

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugHandlersFactory;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.nodeinfo.InputType;

import org.graalvm.compiler.nodes.CompressionNode.CompressionOp;

import org.graalvm.compiler.nodes.ConstantNode;

import org.graalvm.compiler.nodes.FieldLocationIdentity;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.LogicNode;

import org.graalvm.compiler.nodes.NamedLocationIdentity;

import org.graalvm.compiler.nodes.NodeView;

import org.graalvm.compiler.nodes.PiNode;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.ValueNode;

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

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

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

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

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

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

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

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

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

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

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

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

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

import org.graalvm.compiler.nodes.debug.VerifyHeapNode;

import org.graalvm.compiler.nodes.extended.BoxNode;

import org.graalvm.compiler.nodes.extended.FixedValueAnchorNode;

import org.graalvm.compiler.nodes.extended.ForeignCallNode;

import org.graalvm.compiler.nodes.extended.GuardedUnsafeLoadNode;

import org.graalvm.compiler.nodes.extended.GuardingNode;

import org.graalvm.compiler.nodes.extended.JavaReadNode;

import org.graalvm.compiler.nodes.extended.JavaWriteNode;

import org.graalvm.compiler.nodes.extended.LoadHubNode;

import org.graalvm.compiler.nodes.extended.MembarNode;

import org.graalvm.compiler.nodes.extended.RawLoadNode;

import org.graalvm.compiler.nodes.extended.RawStoreNode;

import org.graalvm.compiler.nodes.extended.UnboxNode;

import org.graalvm.compiler.nodes.extended.UnsafeMemoryLoadNode;

import org.graalvm.compiler.nodes.extended.UnsafeMemoryStoreNode;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

import org.graalvm.compiler.nodes.memory.HeapAccess.BarrierType;

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

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

import org.graalvm.compiler.nodes.memory.address.AddressNode;

import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;

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

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

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

import org.graalvm.compiler.nodes.type.StampTool;

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

import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;

import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;

import org.graalvm.compiler.nodes.virtual.VirtualArrayNode;

import org.graalvm.compiler.nodes.virtual.VirtualInstanceNode;

import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;

import org.graalvm.compiler.options.OptionValues;

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

import org.graalvm.compiler.replacements.SnippetLowerableMemoryNode.SnippetLowering;

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

import org.graalvm.compiler.replacements.nodes.BinaryMathIntrinsicNode.BinaryOperation;

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

import org.graalvm.compiler.replacements.nodes.UnaryMathIntrinsicNode.UnaryOperation;

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

import jdk.vm.ci.code.CodeUtil;

import jdk.vm.ci.code.MemoryBarriers;

import jdk.vm.ci.code.TargetDescription;

import jdk.vm.ci.meta.DeoptimizationAction;

import jdk.vm.ci.meta.DeoptimizationReason;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.ResolvedJavaField;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaType;

/**

 * VM-independent lowerings for standard Java nodes. VM-specific methods are abstract and must be

 * implemented by VM-specific subclasses.

 */

public abstract class DefaultJavaLoweringProvider implements LoweringProvider {

    protected final MetaAccessProvider metaAccess;

    protected final ForeignCallsProvider foreignCalls;

    protected final TargetDescription target;

    private final boolean useCompressedOops;

    private BoxingSnippets.Templates boxingSnippets;

    private ConstantStringIndexOfSnippets.Templates indexOfSnippets;

    public DefaultJavaLoweringProvider(MetaAccessProvider metaAccess, ForeignCallsProvider foreignCalls, TargetDescription target, boolean useCompressedOops) {

        this.metaAccess = metaAccess;

        this.foreignCalls = foreignCalls;

        this.target = target;

        this.useCompressedOops = useCompressedOops;

    }

    public void initialize(OptionValues options, Iterable<DebugHandlersFactory> factories, SnippetCounter.Group.Factory factory, Providers providers, SnippetReflectionProvider snippetReflection) {

        boxingSnippets = new BoxingSnippets.Templates(options, factories, factory, providers, snippetReflection, target);

        indexOfSnippets = new ConstantStringIndexOfSnippets.Templates(options, factories, providers, snippetReflection, target);

        providers.getReplacements().registerSnippetTemplateCache(new SnippetCounterNode.SnippetCounterSnippets.Templates(options, factories, providers, snippetReflection, target));

    }

    public final TargetDescription getTarget() {

        return target;

    }

    @Override

    public void lower(Node n, LoweringTool tool) {

        assert n instanceof Lowerable;

        StructuredGraph graph = (StructuredGraph) n.graph();

        }

    }

    private void lowerSecondHalf(UnpackEndianHalfNode n) {

        ByteOrder byteOrder = target.arch.getByteOrder();

        n.lower(byteOrder);

    }

    private void lowerIndexOf(StringIndexOfNode n) {

        if (n.getArgument(3).isConstant()) {

            SnippetLowering lowering = new SnippetLowering() {

                @Override

                public void lower(SnippetLowerableMemoryNode node, LoweringTool tool) {

                    if (tool.getLoweringStage() != LoweringTool.StandardLoweringStage.LOW_TIER) {

                        return;

                    }

                    indexOfSnippets.lower(node, tool);

                }

            };

            SnippetLowerableMemoryNode snippetLower = new SnippetLowerableMemoryNode(lowering, NamedLocationIdentity.getArrayLocation(JavaKind.Char), n.stamp(NodeView.DEFAULT), n.toArgumentArray());

            n.graph().add(snippetLower);

            n.graph().replaceFixedWithFixed(n, snippetLower);

        }

    }

    private void lowerBinaryMath(BinaryMathIntrinsicNode math, LoweringTool tool) {

        if (tool.getLoweringStage() == LoweringTool.StandardLoweringStage.HIGH_TIER) {

            return;

        }

        ResolvedJavaMethod method = math.graph().method();

        if (method != null) {

            if (method.getAnnotation(Snippet.class) != null) {

                /*

                 * In the context of the snippet use the LIR lowering instead of the Node lowering.

                 */

                return;

            }

            if (method.getName().equalsIgnoreCase(math.getOperation().name()) && tool.getMetaAccess().lookupJavaType(Math.class).equals(method.getDeclaringClass())) {

                /*

                 * A root compilation of the intrinsic method should emit the full assembly

                 * implementation.

                 */

                return;

            }

        }

        ForeignCallDescriptor foreignCall = toForeignCall(math.getOperation());

        if (foreignCall != null) {

            StructuredGraph graph = math.graph();

            ForeignCallNode call = graph.add(new ForeignCallNode(foreignCalls, toForeignCall(math.getOperation()), math.getX(), math.getY()));

            graph.addAfterFixed(tool.lastFixedNode(), call);

            math.replaceAtUsages(call);

        }

    }

    private void lowerUnaryMath(UnaryMathIntrinsicNode math, LoweringTool tool) {

        if (tool.getLoweringStage() == LoweringTool.StandardLoweringStage.HIGH_TIER) {

            return;

        }

        ResolvedJavaMethod method = math.graph().method();

        if (method != null) {

            if (method.getAnnotation(Snippet.class) != null) {

                /*

                 * In the context of the snippet use the LIR lowering instead of the Node lowering.

                 */

                return;

            }

            if (method.getName().equalsIgnoreCase(math.getOperation().name()) && tool.getMetaAccess().lookupJavaType(Math.class).equals(method.getDeclaringClass())) {

                /*

                 * A root compilation of the intrinsic method should emit the full assembly

                 * implementation.

                 */

                return;

            }

        }

        ForeignCallDescriptor foreignCall = toForeignCall(math.getOperation());

        if (foreignCall != null) {

            StructuredGraph graph = math.graph();

            ForeignCallNode call = math.graph().add(new ForeignCallNode(foreignCalls, foreignCall, math.getValue()));

            graph.addAfterFixed(tool.lastFixedNode(), call);

            math.replaceAtUsages(call);

        }

    }

    protected ForeignCallDescriptor toForeignCall(UnaryOperation operation) {

        return operation.foreignCallDescriptor;

    }

    protected ForeignCallDescriptor toForeignCall(BinaryOperation operation) {

        return operation.foreignCallDescriptor;

    }

    protected void lowerVerifyHeap(VerifyHeapNode n) {

        GraphUtil.removeFixedWithUnusedInputs(n);

    }

    protected AddressNode createOffsetAddress(StructuredGraph graph, ValueNode object, long offset) {

        ValueNode o = ConstantNode.forIntegerKind(target.wordJavaKind, offset, graph);

        return graph.unique(new OffsetAddressNode(object, o));

    }

    protected AddressNode createFieldAddress(StructuredGraph graph, ValueNode object, ResolvedJavaField field) {

        int offset = fieldOffset(field);

        if (offset >= 0) {

            return createOffsetAddress(graph, object, offset);

        } else {

            return null;

        }

    }

    protected abstract JavaKind getStorageKind(ResolvedJavaField field);

    protected void lowerLoadFieldNode(LoadFieldNode loadField, LoweringTool tool) {

        assert loadField.getStackKind() != JavaKind.Illegal;

        StructuredGraph graph = loadField.graph();

        ResolvedJavaField field = loadField.field();

        ValueNode object = loadField.isStatic() ? staticFieldBase(graph, field) : loadField.object();

        object = createNullCheckedValue(object, loadField, tool);

        Stamp loadStamp = loadStamp(loadField.stamp(NodeView.DEFAULT), getStorageKind(field));

        AddressNode address = createFieldAddress(graph, object, field);

        assert address != null : "Field that is loaded must not be eliminated: " + field.getDeclaringClass().toJavaName(true) + "." + field.getName();

        ReadNode memoryRead = graph.add(new ReadNode(address, fieldLocationIdentity(field), loadStamp, fieldLoadBarrierType(field)));

        ValueNode readValue = implicitLoadConvert(graph, getStorageKind(field), memoryRead);

        loadField.replaceAtUsages(readValue);

        graph.replaceFixed(loadField, memoryRead);

        if (loadField.isVolatile()) {

            MembarNode preMembar = graph.add(new MembarNode(JMM_PRE_VOLATILE_READ));

            graph.addBeforeFixed(memoryRead, preMembar);

            MembarNode postMembar = graph.add(new MembarNode(JMM_POST_VOLATILE_READ));

            graph.addAfterFixed(memoryRead, postMembar);

        }

    }

    protected void lowerStoreFieldNode(StoreFieldNode storeField, LoweringTool tool) {

        StructuredGraph graph = storeField.graph();

        ResolvedJavaField field = storeField.field();

        ValueNode object = storeField.isStatic() ? staticFieldBase(graph, field) : storeField.object();

        object = createNullCheckedValue(object, storeField, tool);

        ValueNode value = implicitStoreConvert(graph, getStorageKind(storeField.field()), storeField.value());

        AddressNode address = createFieldAddress(graph, object, field);

        assert address != null;

        WriteNode memoryWrite = graph.add(new WriteNode(address, fieldLocationIdentity(field), value, fieldStoreBarrierType(storeField.field())));

        memoryWrite.setStateAfter(storeField.stateAfter());

        graph.replaceFixedWithFixed(storeField, memoryWrite);

        if (storeField.isVolatile()) {

            MembarNode preMembar = graph.add(new MembarNode(JMM_PRE_VOLATILE_WRITE));

            graph.addBeforeFixed(memoryWrite, preMembar);

            MembarNode postMembar = graph.add(new MembarNode(JMM_POST_VOLATILE_WRITE));

            graph.addAfterFixed(memoryWrite, postMembar);

        }

    }

    /**

     * Create a PiNode on the index proving that the index is positive. On some platforms this is

     * important to allow the index to be used as an int in the address mode.

     */

    public AddressNode createArrayIndexAddress(StructuredGraph graph, ValueNode array, JavaKind elementKind, ValueNode index, GuardingNode boundsCheck) {

        IntegerStamp indexStamp = StampFactory.forInteger(32, 0, Integer.MAX_VALUE - 1);

        ValueNode positiveIndex = graph.maybeAddOrUnique(PiNode.create(index, indexStamp, boundsCheck != null ? boundsCheck.asNode() : null));

        return createArrayAddress(graph, array, elementKind, positiveIndex);

    }

    public AddressNode createArrayAddress(StructuredGraph graph, ValueNode array, JavaKind elementKind, ValueNode index) {

        ValueNode wordIndex;

        if (target.wordSize > 4) {

            wordIndex = graph.unique(new SignExtendNode(index, target.wordSize * 8));

        } else {

            assert target.wordSize == 4 : "unsupported word size";

            wordIndex = index;

        }

        int shift = CodeUtil.log2(arrayScalingFactor(elementKind));

        ValueNode scaledIndex = graph.unique(new LeftShiftNode(wordIndex, ConstantNode.forInt(shift, graph)));

        int base = arrayBaseOffset(elementKind);

        ValueNode offset = graph.unique(new AddNode(scaledIndex, ConstantNode.forIntegerKind(target.wordJavaKind, base, graph)));

        return graph.unique(new OffsetAddressNode(array, offset));

    }

    protected void lowerLoadIndexedNode(LoadIndexedNode loadIndexed, LoweringTool tool) {

        StructuredGraph graph = loadIndexed.graph();

        ValueNode array = loadIndexed.array();

        array = createNullCheckedValue(array, loadIndexed, tool);

        JavaKind elementKind = loadIndexed.elementKind();

        Stamp loadStamp = loadStamp(loadIndexed.stamp(NodeView.DEFAULT), elementKind);

        GuardingNode boundsCheck = getBoundsCheck(loadIndexed, array, tool);

        AddressNode address = createArrayIndexAddress(graph, array, elementKind, loadIndexed.index(), boundsCheck);

        ReadNode memoryRead = graph.add(new ReadNode(address, NamedLocationIdentity.getArrayLocation(elementKind), loadStamp, BarrierType.NONE));

        memoryRead.setGuard(boundsCheck);

        ValueNode readValue = implicitLoadConvert(graph, elementKind, memoryRead);

        loadIndexed.replaceAtUsages(readValue);

        graph.replaceFixed(loadIndexed, memoryRead);

    }

    protected void lowerStoreIndexedNode(StoreIndexedNode storeIndexed, LoweringTool tool) {

        StructuredGraph graph = storeIndexed.graph();

        ValueNode value = storeIndexed.value();

        ValueNode array = storeIndexed.array();

        array = this.createNullCheckedValue(array, storeIndexed, tool);

        GuardingNode boundsCheck = getBoundsCheck(storeIndexed, array, tool);

        JavaKind elementKind = storeIndexed.elementKind();

        LogicNode condition = null;

            /* Array store check. */

            TypeReference arrayType = StampTool.typeReferenceOrNull(array);

            if (arrayType != null && arrayType.isExact()) {

                ResolvedJavaType elementType = arrayType.getType().getComponentType();

                if (!elementType.isJavaLangObject()) {

                    TypeReference typeReference = TypeReference.createTrusted(storeIndexed.graph().getAssumptions(), elementType);

                    LogicNode typeTest = graph.addOrUniqueWithInputs(InstanceOfNode.create(typeReference, value));

                    condition = LogicNode.or(graph.unique(IsNullNode.create(value)), typeTest, GraalDirectives.UNLIKELY_PROBABILITY);

                }

            } else {

                /*

                 * The guard on the read hub should be the null check of the array that was

                 * introduced earlier.

                 */

                ValueNode arrayClass = createReadHub(graph, array, tool);

                ValueNode componentHub = createReadArrayComponentHub(graph, arrayClass, storeIndexed);

                LogicNode typeTest = graph.unique(InstanceOfDynamicNode.create(graph.getAssumptions(), tool.getConstantReflection(), componentHub, value, false));

                condition = LogicNode.or(graph.unique(IsNullNode.create(value)), typeTest, GraalDirectives.UNLIKELY_PROBABILITY);

            }

        }

        AddressNode address = createArrayIndexAddress(graph, array, elementKind, storeIndexed.index(), boundsCheck);

        WriteNode memoryWrite = graph.add(new WriteNode(address, NamedLocationIdentity.getArrayLocation(elementKind), implicitStoreConvert(graph, elementKind, value),

                        arrayStoreBarrierType(storeIndexed.elementKind())));

        memoryWrite.setGuard(boundsCheck);

        if (condition != null) {

            tool.createGuard(storeIndexed, condition, DeoptimizationReason.ArrayStoreException, DeoptimizationAction.InvalidateReprofile);

        }

        memoryWrite.setStateAfter(storeIndexed.stateAfter());

        graph.replaceFixedWithFixed(storeIndexed, memoryWrite);

    }

    protected void lowerArrayLengthNode(ArrayLengthNode arrayLengthNode, LoweringTool tool) {

        arrayLengthNode.replaceAtUsages(createReadArrayLength(arrayLengthNode.array(), arrayLengthNode, tool));

        StructuredGraph graph = arrayLengthNode.graph();

        graph.removeFixed(arrayLengthNode);

    }

    /**

     * Creates a read node that read the array length and is guarded by a null-check.

     *

     * The created node is placed before {@code before} in the CFG.

     */

    protected ReadNode createReadArrayLength(ValueNode array, FixedNode before, LoweringTool tool) {

        StructuredGraph graph = array.graph();

        ValueNode canonicalArray = this.createNullCheckedValue(skipPiWhileNonNull(array), before, tool);

        AddressNode address = createOffsetAddress(graph, canonicalArray, arrayLengthOffset());

        ReadNode readArrayLength = graph.add(new ReadNode(address, ARRAY_LENGTH_LOCATION, StampFactory.positiveInt(), BarrierType.NONE));

        graph.addBeforeFixed(before, readArrayLength);

        return readArrayLength;