/*

 * 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 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.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeClass;

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 org.graalvm.util.EconomicMap;

import org.graalvm.util.Equivalence;

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.PrimitiveConstant;

/**

 * 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();

    }

    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);

                    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);

                }

                /*

                 * 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();

                NodeClass<?> nodeClass = trueNext.getNodeClass();

                if (trueNext.getClass() == falseNext.getClass()) {

                    if (trueNext instanceof AbstractBeginNode) {

                        // Cannot do this optimization for begin nodes, because it could

                        // move guards above the if that need to stay below a branch.

                    } else if (nodeClass.equalInputs(trueNext, falseNext) && trueNext.valueEquals(falseNext)) {

                        falseNext.replaceAtUsages(trueNext);

                        graph().removeFixed(falseNext);

                        GraphUtil.unlinkFixedNode(trueNext);

                        graph().addBeforeFixed(this, trueNext);

                        for (Node usage : trueNext.usages().snapshot()) {

                            if (usage.isAlive()) {

                                NodeClass<?> usageNodeClass = usage.getNodeClass();

                                if (usageNodeClass.valueNumberable() && !usageNodeClass.isLeafNode()) {

                                    Node newNode = graph().findDuplicate(usage);

                                    if (newNode != null) {

                                        usage.replaceAtUsagesAndDelete(newNode);

                                    }

                                }

                                if (usage.isAlive()) {

                                    tool.addToWorkList(usage);

                                }

                            }

                        }

                        continue;

                    }

                }

            }

            break;

        } while (true);

    }

    /**

     * Recognize a couple patterns that can be merged into an unsigned compare.

     *

     * @param tool

     * @return true if a replacement was done.

     */

    private boolean checkForUnsignedCompare(SimplifierTool tool) {

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

        if (condition() instanceof IntegerLessThanNode) {

            NodeView view = NodeView.from(tool);

            IntegerLessThanNode lessThan = (IntegerLessThanNode) condition();

            Constant y = lessThan.getY().stamp(view).asConstant();

            if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() == 0 && falseSuccessor().next() instanceof IfNode) {

                IfNode ifNode2 = (IfNode) falseSuccessor().next();

                if (ifNode2.condition() instanceof IntegerLessThanNode) {

                    IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition();

                    AbstractBeginNode falseSucc = ifNode2.falseSuccessor();

                    AbstractBeginNode trueSucc = ifNode2.trueSuccessor();

                    IntegerBelowNode below = null;

                    /*

                     * Convert x >= 0 && x < positive which is represented as !(x < 0) && x <

                     * <positive> into an unsigned compare.

                     */

                    if (lessThan2.getX() == lessThan.getX() && lessThan2.getY().stamp(view) instanceof IntegerStamp &&

                                    ((IntegerStamp) lessThan2.getY().stamp(view)).isPositive() &&

                                    sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) {

                        below = graph().unique(new IntegerBelowNode(lessThan2.getX(), lessThan2.getY()));

                        // swap direction

                        AbstractBeginNode tmp = falseSucc;

                        falseSucc = trueSucc;

                        trueSucc = tmp;

                    } else if (lessThan2.getY() == lessThan.getX() && sameDestination(trueSuccessor(), ifNode2.trueSuccessor)) {

                        /*

                         * Convert x >= 0 && x <= positive which is represented as !(x < 0) &&

                         * !(<positive> > x), into x <| positive + 1. This can only be done for

                         * constants since there isn't a IntegerBelowEqualThanNode but that doesn't

                         * appear to be interesting.

                         */

                        JavaConstant positive = lessThan2.getX().asJavaConstant();

                        if (positive != null && positive.asLong() > 0 && positive.asLong() < positive.getJavaKind().getMaxValue()) {

                            ConstantNode newLimit = ConstantNode.forIntegerStamp(lessThan2.getX().stamp(view), positive.asLong() + 1, graph());