/*

 * 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.lir.alloc.trace.lsra;

import static jdk.vm.ci.code.ValueUtil.asRegister;

import static jdk.vm.ci.code.ValueUtil.isIllegal;

import static jdk.vm.ci.code.ValueUtil.isRegister;

import static jdk.vm.ci.code.ValueUtil.isStackSlot;

import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;

import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;

import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.EnumSet;

import java.util.List;

import org.graalvm.compiler.core.common.LIRKind;

import org.graalvm.compiler.core.common.util.Util;

import org.graalvm.compiler.debug.Assertions;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.lir.LIRInstruction;

import org.graalvm.compiler.lir.Variable;

import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;

import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.code.RegisterValue;

import jdk.vm.ci.code.StackSlot;

import jdk.vm.ci.meta.AllocatableValue;

import jdk.vm.ci.meta.JavaConstant;

import jdk.vm.ci.meta.Value;

import jdk.vm.ci.meta.ValueKind;

/**

 * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.

 */

final class TraceInterval extends IntervalHint {

    /**

     * Constants denoting the register usage priority for an interval. The constants are declared in

     * increasing order of priority are are used to optimize spilling when multiple overlapping

     * intervals compete for limited registers.

     */

    public enum RegisterPriority {

        /**

         * No special reason for an interval to be allocated a register.

         */

        None,

        /**

         * Priority level for intervals live at the end of a loop.

         */

        LiveAtLoopEnd,

        /**

         * Priority level for intervals that should be allocated to a register.

         */

        ShouldHaveRegister,

        /**

         * Priority level for intervals that must be allocated to a register.

         */

        MustHaveRegister;

        public static final RegisterPriority[] VALUES = values();

        /**

         * Determines if this priority is higher than or equal to a given priority.

         */

        public boolean greaterEqual(RegisterPriority other) {

            return ordinal() >= other.ordinal();

        }

        /**

         * Determines if this priority is lower than a given priority.

         */

        public boolean lessThan(RegisterPriority other) {

            return ordinal() < other.ordinal();

        }

        public CharSequence shortName() {

            return name().subSequence(0, 1);

        }

    }

    /**

     * Constants denoting whether an interval is bound to a specific register. This models platform

     * dependencies on register usage for certain instructions.

     */

    enum RegisterBinding {

        /**

         * Interval is bound to a specific register as required by the platform.

         */

        Fixed,

        /**

         * Interval has no specific register requirements.

         */

        Any,

        /**

         * Interval is bound to a stack slot.

         */

        Stack;

        public static final RegisterBinding[] VALUES = values();

    }

    /**

     * Constants denoting the linear-scan states an interval may be in with respect to the

     * {@linkplain TraceInterval#from() start} {@code position} of the interval being processed.

     */

    enum State {

        /**

         * An interval that starts after {@code position}.

         */

        Unhandled,

        /**

         * An interval that {@linkplain TraceInterval#covers covers} {@code position} and has an

         * assigned register.

         */

        Active,

        /**

         * An interval that starts before and ends after {@code position} but does not

         * {@linkplain TraceInterval#covers cover} it due to a lifetime hole.

         */

        Inactive,

        /**

         * An interval that ends before {@code position} or is spilled to memory.

         */

        Handled;

    }

    /**

     * Constants used in optimization of spilling of an interval.

     */

    public enum SpillState {

        /**

         * Starting state of calculation: no definition found yet.

         */

        NoDefinitionFound,

        /**

         * One definition has already been found. Two consecutive definitions are treated as one

         * (e.g. a consecutive move and add because of two-operand LIR form). The position of this

         * definition is given by {@link TraceInterval#spillDefinitionPos()}.

         */

        NoSpillStore,

        /**

         * A spill move has already been inserted.

         */

        SpillStore,

        /**

         * The interval starts in memory (e.g. method parameter), so a store is never necessary.

         */

        StartInMemory,

        /**

         * The interval has more than one definition (e.g. resulting from phi moves), so stores to

         * memory are not optimized.

         */

        NoOptimization;

        public static final EnumSet<SpillState> IN_MEMORY = EnumSet.of(SpillStore, StartInMemory);

    }

    /**

     * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval

     * prior to register allocation.

     */

    public final Variable operand;

    /**

     * The operand number for this interval's {@linkplain #operand operand}.

     */

    public final int operandNumber;

    /**

     * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this

     * interval. In case of a spilled interval which is re-materialized this is

     * {@link Value#ILLEGAL}.

     */

    private AllocatableValue location;

    /**

     * The stack slot to which all splits of this interval are spilled if necessary.

     */

    private AllocatableValue spillSlot;

    /**

     * The start of the range, inclusive.

     */

    private int intFrom;

    /**

     * The end of the range, exclusive.

     */

    private int intTo;

    /**

     * List of (use-positions, register-priorities) pairs, sorted by use-positions.

     */

    private int[] usePosListArray;

    private int usePosListSize;

    /**

     * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.

     */

    TraceInterval next;

    /**

     * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split

     * parent}, it points to itself.

     */

    private TraceInterval splitParent;

    /**

     * List of all intervals that are split off from this interval. This is only used if this is a

     * {@linkplain #isSplitParent() split parent}.

     */

    private ArrayList<TraceInterval> splitChildren = null;

    /**

     * Current split child that has been active or inactive last (always stored in split parents).

     */

    private TraceInterval currentSplitChild;

    /**

     * Specifies if move is inserted between currentSplitChild and this interval when interval gets

     * active the first time.

     */

    private boolean insertMoveWhenActivated;

    /**

     * For spill move optimization.

     */

    private SpillState spillState;

    /**

     * Position where this interval is defined (if defined only once).

     */

    private int spillDefinitionPos;

    /**

     * This interval should be assigned the same location as the hint interval.

     */

    private IntervalHint locationHint;

    /**

     * The value with which a spilled child interval can be re-materialized. Currently this must be

     * a Constant.

     */

    private JavaConstant materializedValue;

    /**

     * Sentinel interval to denote the end of an interval list.

     */

    static final TraceInterval EndMarker = new TraceInterval(new Variable(ValueKind.Illegal, Integer.MAX_VALUE), -1);

    TraceInterval(Variable operand) {

        this(operand, operand.index);

    }

    private TraceInterval(Variable operand, int operandNumber) {

        assert operand != null;

        this.operand = operand;

        this.operandNumber = operandNumber;

        if (isRegister(operand)) {

            location = operand;

        } else {

            assert isIllegal(operand) || isVariable(operand);

        }

        this.intFrom = Integer.MAX_VALUE;

        this.intTo = Integer.MAX_VALUE;

        this.usePosListArray = new int[4 * 2];

        this.next = EndMarker;

        this.spillState = SpillState.NoDefinitionFound;

        this.spillDefinitionPos = -1;

        splitParent = this;

        currentSplitChild = this;

    }

    private boolean splitChildrenEmpty() {

        assert splitChildren == null || !splitChildren.isEmpty();

        return splitChildren == null;

    }

    void assignLocation(AllocatableValue newLocation) {

        if (isRegister(newLocation)) {

            assert this.location == null : "cannot re-assign location for " + this;

            if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind().equals(LIRKind.Illegal)) {

                this.location = asRegister(newLocation).asValue(kind());

                return;

            }

        } else if (isIllegal(newLocation)) {

            assert canMaterialize();

        } else {

            assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this;

            assert isStackSlotValue(newLocation);

            assert !newLocation.getValueKind().equals(LIRKind.Illegal);

            assert newLocation.getValueKind().equals(this.kind());

        }

        this.location = newLocation;

    }

    /**

     * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to

     * this interval.

     */

    @Override

    public AllocatableValue location() {

        return location;

    }

    private ValueKind<?> kind() {

        return operand.getValueKind();

    }

    public boolean isEmpty() {

        return intFrom == Integer.MAX_VALUE && intTo == Integer.MAX_VALUE;

    }

    public void setTo(int pos) {

        assert intFrom == Integer.MAX_VALUE || intFrom < pos;

        intTo = pos;

    }

    public void setFrom(int pos) {

        assert intTo == Integer.MAX_VALUE || pos < intTo;

        intFrom = pos;

    }

    @Override

    public int from() {

        return intFrom;

    }

    int to() {

        return intTo;

    }

    public void setLocationHint(IntervalHint interval) {

        locationHint = interval;

    }

    public boolean hasHint() {

        return locationHint != null;

    }

    public boolean isSplitParent() {

        return splitParent == this;

    }

    boolean isSplitChild() {

        return splitParent != this;

    }

    /**

     * Gets the split parent for this interval.

     */

    public TraceInterval splitParent() {

        assert splitParent.isSplitParent() : "not a split parent: " + this;

        return splitParent;

    }

    /**

     * Gets the canonical spill slot for this interval.

     */

    public AllocatableValue spillSlot() {

        return splitParent().spillSlot;

    }

    public void setSpillSlot(AllocatableValue slot) {

        assert isStackSlotValue(slot);

        assert spillSlot() == null || (isVirtualStackSlot(spillSlot()) && isStackSlot(slot)) : String.format("cannot overwrite existing spill slot %s of interval %s with %s", spillSlot(), this, slot);

        splitParent().spillSlot = slot;

    }

    TraceInterval currentSplitChild() {

        return splitParent().currentSplitChild;

    }

    void makeCurrentSplitChild() {

        splitParent().currentSplitChild = this;

    }

    boolean insertMoveWhenActivated() {

        return insertMoveWhenActivated;

    }

    void setInsertMoveWhenActivated(boolean b) {

        insertMoveWhenActivated = b;

    }

    // for spill optimization

    public SpillState spillState() {

        return splitParent().spillState;

    }

    public int spillDefinitionPos() {

        return splitParent().spillDefinitionPos;

    }

    public void setSpillState(SpillState state) {

        assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";

        splitParent().spillState = state;

    }

    public void setSpillDefinitionPos(int pos) {

        assert spillState() == SpillState.NoDefinitionFound || spillState() == SpillState.NoSpillStore || spillDefinitionPos() == -1 : "cannot set the position twice";

        int to = to();

        assert pos < to : String.format("Cannot spill %s at %d", this, pos);

        splitParent().spillDefinitionPos = pos;

    }

    /**

     * Returns true if this interval has a shadow copy on the stack that is correct after

     * {@code opId}.

     */

    public boolean inMemoryAt(int opId) {

        SpillState spillSt = spillState();

        return spillSt == SpillState.StartInMemory || (spillSt == SpillState.SpillStore && opId > spillDefinitionPos() && !canMaterialize());

    }

    // test intersection

    boolean intersects(TraceInterval i) {

        return intersectsAt(i) != -1;

    }

    int intersectsAt(TraceInterval i) {

        TraceInterval i1;

        TraceInterval i2;

        if (i.from() < this.from()) {

            i1 = i;

            i2 = this;

        } else {

            i1 = this;

            i2 = i;

        }

        assert i1.from() <= i2.from();

        if (i1.to() <= i2.from()) {

            return -1;

        }

        return i2.from();

    }

    /**

     * Sets the value which is used for re-materialization.

     */

    public void addMaterializationValue(JavaConstant value) {

        if (materializedValue != null) {

            throw GraalError.shouldNotReachHere(String.format("Multiple materialization values for %s?", this));

        }

        materializedValue = value;

    }

    /**

     * Returns true if this interval can be re-materialized when spilled. This means that no

     * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored.

     */

    public boolean canMaterialize() {

        return getMaterializedValue() != null;

    }

    /**

     * Returns a value which can be moved to a register instead of a restore-move from stack.

     */

    public JavaConstant getMaterializedValue() {

        return splitParent().materializedValue;

    }

    // consistency check of split-children

    boolean checkSplitChildren() {

        if (!splitChildrenEmpty()) {

            assert isSplitParent() : "only split parents can have children";

            for (int i = 0; i < splitChildren.size(); i++) {

                TraceInterval i1 = splitChildren.get(i);

                assert i1.splitParent() == this : "not a split child of this interval";

                assert i1.kind().equals(kind()) : "must be equal for all split children";

                assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children";

                for (int j = i + 1; j < splitChildren.size(); j++) {

                    TraceInterval i2 = splitChildren.get(j);

                    assert i1.operandNumber != i2.operandNumber : "same register number";

                    if (i1.from() < i2.from()) {

                        assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping";

                    } else {

                        assert i2.from() < i1.from() : "intervals start at same opId";