/*

 * Copyright (c) 2009, 2015, 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.nodes;

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

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

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Iterator;

import java.util.List;

import java.util.Objects;

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

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

import org.graalvm.compiler.bytecode.BytecodeDisassembler;

import org.graalvm.compiler.bytecode.Bytecodes;

import org.graalvm.compiler.bytecode.Bytes;

import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;

import org.graalvm.compiler.core.common.calc.Condition;

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

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

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

import org.graalvm.compiler.debug.CounterKey;

import org.graalvm.compiler.debug.DebugCloseable;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeClass;

import org.graalvm.compiler.graph.NodeSourcePosition;

import org.graalvm.compiler.graph.iterators.NodeIterable;

import org.graalvm.compiler.graph.spi.Canonicalizable;

import org.graalvm.compiler.graph.spi.Simplifiable;

import org.graalvm.compiler.graph.spi.SimplifierTool;

import org.graalvm.compiler.nodeinfo.InputType;

import org.graalvm.compiler.nodeinfo.NodeInfo;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.MetaAccessProvider;

import jdk.vm.ci.meta.PrimitiveConstant;

import jdk.vm.ci.meta.ResolvedJavaMethod;

import jdk.vm.ci.meta.ResolvedJavaType;

/**

 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome

 * of a comparison.

 */

@NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")

public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {

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

    private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");

    @Successor AbstractBeginNode trueSuccessor;

    @Successor AbstractBeginNode falseSuccessor;

    @Input(InputType.Condition) LogicNode condition;

    protected double trueSuccessorProbability;

    public LogicNode condition() {

        return condition;

    }

    public void setCondition(LogicNode x) {

        updateUsages(condition, x);

        condition = x;

    }

    public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) {

        this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability);

    }

    public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) {

        super(TYPE, StampFactory.forVoid());

        this.condition = condition;

        this.falseSuccessor = falseSuccessor;

        this.trueSuccessor = trueSuccessor;

        setTrueSuccessorProbability(trueSuccessorProbability);

    }

    /**

     * Gets the true successor.

     *

     * @return the true successor

     */

    public AbstractBeginNode trueSuccessor() {

        return trueSuccessor;

    }

    /**

     * Gets the false successor.

     *

     * @return the false successor

     */

    public AbstractBeginNode falseSuccessor() {

        return falseSuccessor;

    }

    public double getTrueSuccessorProbability() {

        return this.trueSuccessorProbability;

    }

    public void setTrueSuccessor(AbstractBeginNode node) {

        updatePredecessor(trueSuccessor, node);

        trueSuccessor = node;

    }

    public void setFalseSuccessor(AbstractBeginNode node) {

        updatePredecessor(falseSuccessor, node);

        falseSuccessor = node;

    }

    /**

     * Gets the node corresponding to the specified outcome of the branch.

     *

     * @param istrue {@code true} if the true successor is requested, {@code false} otherwise

     * @return the corresponding successor

     */

    public AbstractBeginNode successor(boolean istrue) {

        return istrue ? trueSuccessor : falseSuccessor;

    }

    public void setTrueSuccessorProbability(double prob) {

        assert prob >= -0.000000001 && prob <= 1.000000001 : "Probability out of bounds: " + prob;

        trueSuccessorProbability = Math.min(1.0, Math.max(0.0, prob));

    }

    @Override

    public double probability(AbstractBeginNode successor) {

        return successor == trueSuccessor ? trueSuccessorProbability : 1 - trueSuccessorProbability;

    }

    @Override

    public void generate(NodeLIRBuilderTool gen) {

        gen.emitIf(this);

    }

    @Override

    public boolean verify() {

        assertTrue(condition() != null, "missing condition");

        assertTrue(trueSuccessor() != null, "missing trueSuccessor");

        assertTrue(falseSuccessor() != null, "missing falseSuccessor");

        return super.verify();

    }

    private boolean compareCallContext(NodeSourcePosition successorPosition) {

        NodeSourcePosition position = getNodeSourcePosition();

        NodeSourcePosition successor = successorPosition;

        while (position != null) {

            assertTrue(Objects.equals(position.getMethod(), successor.getMethod()), "method mismatch");

            position = position.getCaller();

            successor = successor.getCaller();

        }

        assertTrue(successor == null, "successor position has more methods");

        return true;

    }

    @Override

    public boolean verifySourcePosition() {

        NodeSourcePosition sourcePosition = getNodeSourcePosition();

        assertTrue(sourcePosition != null, "missing IfNode source position");

        NodeSourcePosition trueSuccessorPosition = trueSuccessor.getNodeSourcePosition();

        assertTrue(trueSuccessorPosition != null, "missing IfNode true successor source position");

        NodeSourcePosition falseSuccessorPosition = falseSuccessor.getNodeSourcePosition();

        assertTrue(falseSuccessorPosition != null, "missing IfNode false successor source position");

        int bci = sourcePosition.getBCI();

        ResolvedJavaMethod method = sourcePosition.getMethod();

        int bytecode = BytecodeDisassembler.getBytecodeAt(method, bci);

        if (!Bytecodes.isIfBytecode(bytecode)) {

            return true;

        }

        byte[] code = (new ResolvedJavaMethodBytecode(method)).getCode();

        int targetBCI = bci + Bytes.beS2(code, bci + 1);

        int nextBCI = bci + Bytecodes.lengthOf(bytecode);

        // At least one successor should have the correct BCI to indicate any possible negation that

        // occurred after bytecode parsing

        boolean matchingSuccessorFound = false;

        if (trueSuccessorPosition.getBCI() == nextBCI || trueSuccessorPosition.getBCI() == targetBCI) {

            assertTrue(compareCallContext(trueSuccessorPosition), "call context different from IfNode in trueSuccessor");

            matchingSuccessorFound = true;

        }

        if (falseSuccessorPosition.getBCI() == nextBCI || falseSuccessorPosition.getBCI() == targetBCI) {

            assertTrue(compareCallContext(falseSuccessorPosition), "call context different from IfNode in falseSuccessor");

            matchingSuccessorFound = true;

        }

        assertTrue(matchingSuccessorFound, "no matching successor position found in IfNode");

        assertTrue(trueSuccessorPosition.getBCI() != falseSuccessorPosition.getBCI(), "successor positions same in IfNode");

        return true;

    }

    public void eliminateNegation() {

        AbstractBeginNode oldTrueSuccessor = trueSuccessor;

        AbstractBeginNode oldFalseSuccessor = falseSuccessor;

        trueSuccessor = oldFalseSuccessor;

        falseSuccessor = oldTrueSuccessor;

        trueSuccessorProbability = 1 - trueSuccessorProbability;

        setCondition(((LogicNegationNode) condition).getValue());

    }

    @Override

    public void simplify(SimplifierTool tool) {

        if (trueSuccessor().next() instanceof DeoptimizeNode) {

            if (trueSuccessorProbability != 0) {

                CORRECTED_PROBABILITIES.increment(getDebug());

                trueSuccessorProbability = 0;

            }

        } else if (falseSuccessor().next() instanceof DeoptimizeNode) {

            if (trueSuccessorProbability != 1) {

                CORRECTED_PROBABILITIES.increment(getDebug());

                trueSuccessorProbability = 1;

            }

        }

        if (condition() instanceof LogicNegationNode) {

            eliminateNegation();

        }

        if (condition() instanceof LogicConstantNode) {

            LogicConstantNode c = (LogicConstantNode) condition();

            if (c.getValue()) {

                tool.deleteBranch(falseSuccessor());

                tool.addToWorkList(trueSuccessor());

                graph().removeSplit(this, trueSuccessor());

            } else {

                tool.deleteBranch(trueSuccessor());

                tool.addToWorkList(falseSuccessor());

                graph().removeSplit(this, falseSuccessor());

            }

            return;

        }

        if (tool.allUsagesAvailable() && trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages()) {

            pushNodesThroughIf(tool);

            if (checkForUnsignedCompare(tool) || removeOrMaterializeIf(tool)) {

                return;

            }

        }

        if (removeIntermediateMaterialization(tool)) {

            return;

        }

        if (splitIfAtPhi(tool)) {

            return;

        }

        if (conditionalNodeOptimization(tool)) {

            return;

        }

        if (falseSuccessor().hasNoUsages() && (!(falseSuccessor() instanceof LoopExitNode)) && falseSuccessor().next() instanceof IfNode) {

            AbstractBeginNode intermediateBegin = falseSuccessor();

            IfNode nextIf = (IfNode) intermediateBegin.next();

            double probabilityB = (1.0 - this.trueSuccessorProbability) * nextIf.trueSuccessorProbability;

            if (this.trueSuccessorProbability < probabilityB) {

                // Reordering of those two if statements is beneficial from the point of view of

                // their probabilities.

                if (prepareForSwap(tool, condition(), nextIf.condition())) {

                    // Reordering is allowed from (if1 => begin => if2) to (if2 => begin => if1).

                    assert intermediateBegin.next() == nextIf;

                    AbstractBeginNode bothFalseBegin = nextIf.falseSuccessor();

                    nextIf.setFalseSuccessor(null);

                    intermediateBegin.setNext(null);

                    this.setFalseSuccessor(null);

                    this.replaceAtPredecessor(nextIf);

                    nextIf.setFalseSuccessor(intermediateBegin);

                    intermediateBegin.setNext(this);

                    this.setFalseSuccessor(bothFalseBegin);

                    NodeSourcePosition intermediateBeginPosition = intermediateBegin.getNodeSourcePosition();

                    intermediateBegin.setNodeSourcePosition(bothFalseBegin.getNodeSourcePosition());

                    bothFalseBegin.setNodeSourcePosition(intermediateBeginPosition);

                    nextIf.setTrueSuccessorProbability(probabilityB);

                    if (probabilityB == 1.0) {

                        this.setTrueSuccessorProbability(0.0);

                    } else {

                        double newProbability = this.trueSuccessorProbability / (1.0 - probabilityB);

                        this.setTrueSuccessorProbability(Math.min(1.0, newProbability));

                    }

                    return;

                }

            }

        }

        if (tryEliminateBoxedReferenceEquals(tool)) {

            return;

        }

    }

    private boolean isUnboxedFrom(MetaAccessProvider meta, NodeView view, ValueNode x, ValueNode src) {

        if (x == src) {

            return true;

        } else if (x instanceof UnboxNode) {

            return isUnboxedFrom(meta, view, ((UnboxNode) x).getValue(), src);

        } else if (x instanceof PiNode) {

            PiNode pi = (PiNode) x;

            return isUnboxedFrom(meta, view, pi.getOriginalNode(), src);

        } else if (x instanceof LoadFieldNode) {

            LoadFieldNode load = (LoadFieldNode) x;

            ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);

            if (load.getValue().stamp(view).javaType(meta).equals(integerType)) {

                return isUnboxedFrom(meta, view, load.getValue(), src);

            } else {

                return false;

            }

        } else {

            return false;

        }

    }

    /**

     * Attempts to replace the following pattern:

     *

     * <pre>

     * Integer x = ...;

     * Integer y = ...;

     * if ((x == y) || x.equals(y)) { ... }

     * </pre>

     *

     * with:

     *

     * <pre>

     * Integer x = ...;

     * Integer y = ...;

     * if (x.equals(y)) { ... }

     * </pre>

     *

     * whenever the probability that the reference check will pass is relatively small.

     *

     * See GR-1315 for more information.

     */

    private boolean tryEliminateBoxedReferenceEquals(SimplifierTool tool) {

        if (!(condition instanceof ObjectEqualsNode)) {

            return false;

        }

        MetaAccessProvider meta = tool.getMetaAccess();

        ObjectEqualsNode equalsCondition = (ObjectEqualsNode) condition;

        ValueNode x = equalsCondition.getX();

        ValueNode y = equalsCondition.getY();

        ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);

        // At least one argument for reference equal must be a boxed primitive.

        NodeView view = NodeView.from(tool);

        if (!x.stamp(view).javaType(meta).equals(integerType) && !y.stamp(view).javaType(meta).equals(integerType)) {

            return false;

        }

        // The reference equality check is usually more efficient compared to a boxing check.

        // The success of the reference equals must therefore be relatively rare, otherwise it makes

        // no sense to eliminate it.

        if (getTrueSuccessorProbability() > 0.4) {

            return false;

        }

        // True branch must be empty.

        if (trueSuccessor instanceof BeginNode || trueSuccessor instanceof LoopExitNode) {

            if (trueSuccessor.next() instanceof EndNode) {

                // Empty true branch.

            } else {

                return false;

            }

        } else {

            return false;

        }

        // False branch must only check the unboxed values.

        UnboxNode unbox = null;

        FixedGuardNode unboxCheck = null;

        for (FixedNode node : falseSuccessor.getBlockNodes()) {

            if (!(node instanceof BeginNode || node instanceof UnboxNode || node instanceof FixedGuardNode || node instanceof EndNode ||

                            node instanceof LoadFieldNode || node instanceof LoopExitNode)) {

                return false;

            }

            if (node instanceof UnboxNode) {

                if (unbox == null) {

                    unbox = (UnboxNode) node;

                } else {

                    return false;

                }

            }

            if (!(node instanceof FixedGuardNode)) {

                continue;

            }

            FixedGuardNode fixed = (FixedGuardNode) node;

            if (!(fixed.condition() instanceof IntegerEqualsNode)) {

                continue;

            }

            IntegerEqualsNode equals = (IntegerEqualsNode) fixed.condition();

            if ((isUnboxedFrom(meta, view, equals.getX(), x) && isUnboxedFrom(meta, view, equals.getY(), y)) ||

                            (isUnboxedFrom(meta, view, equals.getX(), y) && isUnboxedFrom(meta, view, equals.getY(), x))) {

                unboxCheck = fixed;

            }

        }

        if (unbox == null || unboxCheck == null) {

            return false;

        }

        // Falsify the reference check.

        setCondition(graph().addOrUniqueWithInputs(LogicConstantNode.contradiction()));

        return true;

    }

    /**

     * Try to optimize this as if it were a {@link ConditionalNode}.

     */

    private boolean conditionalNodeOptimization(SimplifierTool tool) {

        if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {

            AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();

            AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();

            if (trueEnd.merge() != falseEnd.merge()) {

                return false;

            }

            if (!(trueEnd.merge() instanceof MergeNode)) {

                return false;

            }

            MergeNode merge = (MergeNode) trueEnd.merge();

            if (merge.usages().count() != 1 || merge.phis().count() != 1) {

                return false;

            }

            if (trueSuccessor().anchored().isNotEmpty() || falseSuccessor().anchored().isNotEmpty()) {

                return false;

            }

            PhiNode phi = merge.phis().first();

            ValueNode falseValue = phi.valueAt(falseEnd);

            ValueNode trueValue = phi.valueAt(trueEnd);

            NodeView view = NodeView.from(tool);

            ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view);

            if (result != null) {

                /*

                 * canonicalizeConditional returns possibly new nodes so add them to the graph.

                 */

                if (result.graph() == null) {

                    result = graph().addOrUniqueWithInputs(result);

                }

                result = proxyReplacement(result);

                /*

                 * This optimization can be performed even if multiple values merge at this phi

                 * since the two inputs get simplified into one.

                 */

                phi.setValueAt(trueEnd, result);

                removeThroughFalseBranch(tool, merge);

                return true;

            }

        }

        return false;

    }

    private void pushNodesThroughIf(SimplifierTool tool) {

        assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();

        // push similar nodes upwards through the if, thereby deduplicating them

        do {

            AbstractBeginNode trueSucc = trueSuccessor();

            AbstractBeginNode falseSucc = falseSuccessor();

            if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) {

                FixedWithNextNode trueNext = (FixedWithNextNode) trueSucc.next();

                FixedWithNextNode falseNext = (FixedWithNextNode) falseSucc.next();