/*

 * 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_2;

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

import org.graalvm.compiler.debug.DebugCounter;

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

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

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

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

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_2, 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 DebugCounter CORRECTED_PROBABILITIES = Debug.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();

                trueSuccessorProbability = 0;

            }

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

            if (trueSuccessorProbability != 1) {

                CORRECTED_PROBABILITIES.increment();

                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.getConstantReflection(), 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;

                }

            }

        }

    }

    /**

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

            }

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

            ValueNode falseValue = phi.valueAt(falseEnd);

            ValueNode trueValue = phi.valueAt(trueEnd);

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

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

                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 (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) {

            IntegerLessThanNode lessThan = (IntegerLessThanNode) condition();

            Constant y = lessThan.getY().stamp().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() instanceof IntegerStamp && ((IntegerStamp) lessThan2.getY().stamp()).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(), positive.asLong() + 1, graph());

                            below = graph().unique(new IntegerBelowNode(lessThan.getX(), newLimit));

                        }

                    }

                    if (below != null) {

                        ifNode2.setTrueSuccessor(null);

                        ifNode2.setFalseSuccessor(null);

                        IfNode newIfNode = graph().add(new IfNode(below, falseSucc, trueSucc, 1 - trueSuccessorProbability));

                        // Remove the < 0 test.

                        tool.deleteBranch(trueSuccessor);

                        graph().removeSplit(this, falseSuccessor);

                        // Replace the second test with the new one.

                        ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode);

                        ifNode2.safeDelete();

                        return true;

                    }

                }

            }

        }

        return false;

    }

    /**

     * Check it these two blocks end up at the same place. Meeting at the same merge, or

     * deoptimizing in the same way.

     */

    private static boolean sameDestination(AbstractBeginNode succ1, AbstractBeginNode succ2) {

        Node next1 = succ1.next();

        Node next2 = succ2.next();

        if (next1 instanceof EndNode && next2 instanceof EndNode) {

            EndNode end1 = (EndNode) next1;

            EndNode end2 = (EndNode) next2;

            if (end1.merge() == end2.merge()) {

                for (PhiNode phi : end1.merge().phis()) {

                    if (phi.valueAt(end1) != phi.valueAt(end2)) {

                        return false;

                    }

                }

                // They go to the same MergeNode and merge the same values

                return true;

            }

        } else if (next1 instanceof DeoptimizeNode && next2 instanceof DeoptimizeNode) {

            DeoptimizeNode deopt1 = (DeoptimizeNode) next1;

            DeoptimizeNode deopt2 = (DeoptimizeNode) next2;

            if (deopt1.reason() == deopt2.reason() && deopt1.action() == deopt2.action()) {

                // Same deoptimization reason and action.

                return true;

            }

        } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) {

            LoopExitNode exit1 = (LoopExitNode) next1;

            LoopExitNode exit2 = (LoopExitNode) next2;

            if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) {

                // Exit the same loop and end up at the same place.

                return true;

            }

        } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) {

            ReturnNode exit1 = (ReturnNode) next1;

            ReturnNode exit2 = (ReturnNode) next2;

            if (exit1.result() == exit2.result()) {

                // Exit the same loop and end up at the same place.

                return true;

            }

        }

        return false;

    }

    private static boolean prepareForSwap(ConstantReflectionProvider constantReflection, LogicNode a, LogicNode b) {

        if (a instanceof InstanceOfNode) {

            InstanceOfNode instanceOfA = (InstanceOfNode) a;

            if (b instanceof IsNullNode) {

                IsNullNode isNullNode = (IsNullNode) b;

                if (isNullNode.getValue() == instanceOfA.getValue()) {

                    Debug.log("Can swap instanceof and isnull if");

                    return true;

                }

            } else if (b instanceof InstanceOfNode) {

                InstanceOfNode instanceOfB = (InstanceOfNode) b;

                if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&

                                !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {

                    // Two instanceof on the same value with mutually exclusive types.

                    Debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());

                    return true;

                }

            }

        } else if (a instanceof CompareNode) {

            CompareNode compareA = (CompareNode) a;

            Condition conditionA = compareA.condition();

            if (compareA.unorderedIsTrue()) {

                return false;

            }

            if (b instanceof CompareNode) {

                CompareNode compareB = (CompareNode) b;

                if (compareA == compareB) {

                    Debug.log("Same conditions => do not swap and leave the work for global value numbering.");

                    return false;

                }

                if (compareB.unorderedIsTrue()) {

                    return false;

                }

                Condition comparableCondition = null;

                Condition conditionB = compareB.condition();

                if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {

                    comparableCondition = conditionB;

                } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {

                    comparableCondition = conditionB.mirror();

                }

                if (comparableCondition != null) {

                    Condition combined = conditionA.join(comparableCondition);

                    if (combined == null) {

                        // The two conditions are disjoint => can reorder.

                        Debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);

                        return true;

                    }

                } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {

                    boolean canSwap = false;

                    if ((compareA.getX() == compareB.getX() && valuesDistinct(constantReflection, compareA.getY(), compareB.getY()))) {

                        canSwap = true;

                    } else if ((compareA.getX() == compareB.getY() && valuesDistinct(constantReflection, compareA.getY(), compareB.getX()))) {

                        canSwap = true;

                    } else if ((compareA.getY() == compareB.getX() && valuesDistinct(constantReflection, compareA.getX(), compareB.getY()))) {

                        canSwap = true;

                    } else if ((compareA.getY() == compareB.getY() && valuesDistinct(constantReflection, compareA.getX(), compareB.getX()))) {

                        canSwap = true;

                    }

                    if (canSwap) {

                        Debug.log("Can swap equality condition with one shared and one disjoint value.");

                        return true;

                    }

                }

            }

        }

        return false;

    }

    private static boolean valuesDistinct(ConstantReflectionProvider constantReflection, ValueNode a, ValueNode b) {

        if (a.isConstant() && b.isConstant()) {

            Boolean equal = constantReflection.constantEquals(a.asConstant(), b.asConstant());

            if (equal != null) {

                return !equal.booleanValue();