/*

 * Copyright (c) 2016, 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.hotspot.phases.aot;

import static org.graalvm.util.CollectionsUtil.anyMatch;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

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

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.hotspot.nodes.aot.InitializeKlassNode;

import org.graalvm.compiler.hotspot.nodes.aot.ResolveConstantNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.FixedWithNextNode;

import org.graalvm.compiler.nodes.Invoke;

import org.graalvm.compiler.nodes.StructuredGraph;

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

import org.graalvm.compiler.phases.BasePhase;

import org.graalvm.compiler.phases.graph.MergeableState;

import org.graalvm.compiler.phases.graph.PostOrderNodeIterator;

import jdk.vm.ci.hotspot.HotSpotMetaspaceConstant;

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.ResolvedJavaType;

public class EliminateRedundantInitializationPhase extends BasePhase<CoreProviders> {

    /**

     * Find each {@link Invoke} that has a corresponding {@link InitializeKlassNode}. These

     * {@link InitializeKlassNode} are redundant and are removed.

     */

    private static void removeInitsAtStaticCalls(StructuredGraph graph) {

        for (Invoke invoke : graph.getInvokes()) {

            Node classInit = invoke.classInit();

            if (classInit != null) {

                classInit.replaceAtUsages(null);

                graph.removeFixed((FixedWithNextNode) classInit);

            }

        }

    }

    /**

     * Remove redundant {@link InitializeKlassNode} or {@link ResolveConstantNode} instances from

     * the graph.

     *

     * @param graph the program graph

     */

    private static void removeRedundantInits(StructuredGraph graph) {

        // Find and remove redundant nodes from the graph.

        List<FixedWithNextNode> redundantNodes = findRedundantInits(graph);

        for (FixedWithNextNode n : redundantNodes) {

            graph.removeFixed(n);

        }

    }

    /**

     * Find {@link InitializeKlassNode} and {@link ResolveConstantNode} instances that can be

     * removed because there is an existing dominating node.

     *

     * @param graph the program graph

     */

    private static List<FixedWithNextNode> findRedundantInits(StructuredGraph graph) {

        EliminateRedundantInitializationIterator i = new EliminateRedundantInitializationIterator(graph.start(), new InitializedTypes());

        i.apply();

        return i.getRedundantNodes();

    }

    /**

     * State for {@link EliminateRedundantInitializationIterator}.

     */

    private static class InitializedTypes extends MergeableState<InitializedTypes> implements Cloneable {

        private EconomicSet<ResolvedJavaType> types;

        InitializedTypes() {

            types = EconomicSet.create();

        }

        private InitializedTypes(EconomicSet<ResolvedJavaType> types) {

            this.types = types;

        }

        @Override

        public InitializedTypes clone() {

            return new InitializedTypes(EconomicSet.create(types));

        }

        public boolean contains(ResolvedJavaType type) {

            if (type.isInterface() || type.isArray()) {

                // Check for exact match for interfaces

                return types.contains(type);

            }

            // For other types see if there is the same type or a subtype

            return anyMatch(types, t -> type.isAssignableFrom(t));

        }

        public void add(ResolvedJavaType type) {

            types.add(type);

        }

        /**

         * Merge two given types. Interfaces and arrays have to be the same to merge successfully.

         * For other types the answer is the LCA.

         *

         * @param a initialized type

         * @param b initialized type

         * @return lowest common type that is initialized if either a or b are initialized, null if

         *         no such type exists.

         */

        private static ResolvedJavaType merge(ResolvedJavaType a, ResolvedJavaType b) {

            // We want exact match for interfaces or arrays

            if (a.isInterface() || b.isInterface() || a.isArray() || b.isArray()) {

                if (a.equals(b)) {

                    return a;

                } else {

                    return null;

                }

            } else {

                // And LCA for other types

                ResolvedJavaType c = a.findLeastCommonAncestor(b);

                if (c.isJavaLangObject()) {

                    // Not a very useful type, always initialized, don't pollute the sets.

                    return null;

                }

                return c;

            }

        }

        /**

         * Merge two sets of types. Essentially a computation of the LCA for each element of the

         * cartesian product of the input sets. Interfaces have to match exactly.

         *

         * @param a set of initialized types

         * @param b set of initialized types

         * @return set of common types that would be initialized if types in either a or b are

         *         initialized

         */

        private static EconomicSet<ResolvedJavaType> merge(EconomicSet<ResolvedJavaType> a, EconomicSet<ResolvedJavaType> b) {

            EconomicSet<ResolvedJavaType> c = EconomicSet.create();

            for (ResolvedJavaType ta : a) {

                for (ResolvedJavaType tb : b) {

                    ResolvedJavaType tc = merge(ta, tb);

                    if (tc != null) {

                        c.add(tc);

                        if (tc.isInterface() || tc.isArray()) {

                            // Interfaces and arrays are not going merge with anything else, so bail

                            // out early.

                            break;

                        }

                    }

                }

            }

            return c;

        }

        @Override

        public boolean merge(AbstractMergeNode merge, List<InitializedTypes> withStates) {

            for (InitializedTypes ts : withStates) {

                types = merge(types, ts.types);

            }

            return true;

        }

        protected static String toString(EconomicSet<ResolvedJavaType> types) {

            StringBuilder b = new StringBuilder();

            b.append("[");

            Iterator<ResolvedJavaType> i = types.iterator();

            while (i.hasNext()) {

                ResolvedJavaType t = i.next();

                b.append(t.toString());

                if (i.hasNext()) {

                    b.append(",");

                }

            }

            b.append("]");

            return b.toString();

        }

        @Override

        public String toString() {

            return toString(types);

        }

    }

    /**

     * Do data flow analysis of class initializations and array resolutions. Collect redundant

     * nodes.

     */

    private static class EliminateRedundantInitializationIterator extends PostOrderNodeIterator<InitializedTypes> {

        private List<FixedWithNextNode> redundantNodes = new ArrayList<>();

        public List<FixedWithNextNode> getRedundantNodes() {

            return redundantNodes;

        }

        EliminateRedundantInitializationIterator(FixedNode start, InitializedTypes initialState) {

            super(start, initialState);

        }

        private void processType(FixedWithNextNode node, Constant c) {

            HotSpotMetaspaceConstant klass = (HotSpotMetaspaceConstant) c;

            ResolvedJavaType t = klass.asResolvedJavaType();

            if (t != null) {

                if (state.contains(t)) {

                    redundantNodes.add(node);

                } else {

                    state.add(t);

                }

            }

        }

        @Override

        protected void node(FixedNode node) {

            if (node instanceof InitializeKlassNode) {

                InitializeKlassNode i = (InitializeKlassNode) node;

                if (i.value().isConstant()) {

                    processType(i, i.value().asConstant());

                }

            } else if (node instanceof ResolveConstantNode) {

                ResolveConstantNode r = (ResolveConstantNode) node;

                if (r.hasNoUsages()) {

                    if (r.value().isConstant()) {

                        processType(r, r.value().asConstant());

                    }

                }

            }

        }

    }

    @Override

    protected void run(StructuredGraph graph, CoreProviders context) {

        removeInitsAtStaticCalls(graph);

        removeRedundantInits(graph);

    }

}