/*

 * 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.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 java.util.ArrayList;

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

import org.graalvm.compiler.debug.CounterKey;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.debug.Indent;

import org.graalvm.compiler.lir.LIRInsertionBuffer;

import org.graalvm.compiler.lir.LIRInstruction;

import org.graalvm.compiler.lir.LIRValueUtil;

import org.graalvm.compiler.lir.gen.LIRGenerationResult;

import jdk.vm.ci.meta.AllocatableValue;

import jdk.vm.ci.meta.Constant;

import jdk.vm.ci.meta.Value;

/**

 */

public class MoveResolver {

    private static final CounterKey cycleBreakingSlotsAllocated = DebugContext.counter("LSRA[cycleBreakingSlotsAllocated]");

    private final LinearScan allocator;

    private int insertIdx;

    private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted

    private final ArrayList<Interval> mappingFrom;

    private final ArrayList<Constant> mappingFromOpr;

    private final ArrayList<Interval> mappingTo;

    private boolean multipleReadsAllowed;

    private final int[] registerBlocked;

    private final LIRGenerationResult res;

    protected void setValueBlocked(Value location, int direction) {

        assert direction == 1 || direction == -1 : "out of bounds";

        if (isRegister(location)) {

            registerBlocked[asRegister(location).number] += direction;

        } else {

            throw GraalError.shouldNotReachHere("unhandled value " + location);

        }

    }

    protected Interval getMappingFrom(int i) {

        return mappingFrom.get(i);

    }

    protected int mappingFromSize() {

        return mappingFrom.size();

    }

    protected int valueBlocked(Value location) {

        if (isRegister(location)) {

            return registerBlocked[asRegister(location).number];

        }

        throw GraalError.shouldNotReachHere("unhandled value " + location);

    }

    void setMultipleReadsAllowed() {

        multipleReadsAllowed = true;

    }

    protected boolean areMultipleReadsAllowed() {

        return multipleReadsAllowed;

    }

    boolean hasMappings() {

        return mappingFrom.size() > 0;

    }

    protected LinearScan getAllocator() {

        return allocator;

    }

    protected MoveResolver(LinearScan allocator) {

        this.allocator = allocator;

        this.multipleReadsAllowed = false;

        this.mappingFrom = new ArrayList<>(8);

        this.mappingFromOpr = new ArrayList<>(8);

        this.mappingTo = new ArrayList<>(8);

        this.insertIdx = -1;

        this.insertionBuffer = new LIRInsertionBuffer();

        this.registerBlocked = new int[allocator.getRegisters().size()];

        this.res = allocator.getLIRGenerationResult();

    }

    protected boolean checkEmpty() {

        assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";

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

            assert registerBlocked[i] == 0 : "register map must be empty before and after processing";

        }

        checkMultipleReads();

        return true;

    }

    protected void checkMultipleReads() {

        assert !areMultipleReadsAllowed() : "must have default value";

    }

    private boolean verifyBeforeResolve() {

        assert mappingFrom.size() == mappingFromOpr.size() : "length must be equal";

        assert mappingFrom.size() == mappingTo.size() : "length must be equal";

        assert insertIdx != -1 : "insert position not set";

        int i;

        int j;

        if (!areMultipleReadsAllowed()) {

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

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

                    assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";

                }

            }

        }

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

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

                assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";

            }

        }

        EconomicSet<Value> usedRegs = EconomicSet.create(Equivalence.DEFAULT);

        if (!areMultipleReadsAllowed()) {

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

                Interval interval = mappingFrom.get(i);

                if (interval != null && !isIllegal(interval.location())) {

                    boolean unique = usedRegs.add(interval.location());

                    assert unique : "cannot read from same register twice";

                }

            }

        }

        usedRegs.clear();

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

            Interval interval = mappingTo.get(i);

            if (isIllegal(interval.location())) {

                // After insertion the location may become illegal, so don't check it since multiple

                // intervals might be illegal.

                continue;

            }

            boolean unique = usedRegs.add(interval.location());

            assert unique : "cannot write to same register twice";

        }

        verifyStackSlotMapping();

        return true;

    }

    protected void verifyStackSlotMapping() {

        EconomicSet<Value> usedRegs = EconomicSet.create(Equivalence.DEFAULT);

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

            Interval interval = mappingFrom.get(i);

            if (interval != null && !isRegister(interval.location())) {

                usedRegs.add(interval.location());

            }

        }

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

            Interval interval = mappingTo.get(i);

            assert !usedRegs.contains(interval.location()) ||

                            checkIntervalLocation(mappingFrom.get(i), interval, mappingFromOpr.get(i)) : "stack slots used in mappingFrom must be disjoint to mappingTo";

        }

    }

    private static boolean checkIntervalLocation(Interval from, Interval to, Constant fromOpr) {

        if (from == null) {

            return fromOpr != null;

        } else {

            return to.location().equals(from.location());

        }

    }

    // mark assignedReg and assignedRegHi of the interval as blocked

    private void blockRegisters(Interval interval) {

        Value location = interval.location();

        if (mightBeBlocked(location)) {

            assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;

            int direction = 1;

            setValueBlocked(location, direction);

            allocator.getDebug().log("block %s", location);

        }

    }

    // mark assignedReg and assignedRegHi of the interval as unblocked

    private void unblockRegisters(Interval interval) {

        Value location = interval.location();

        if (mightBeBlocked(location)) {

            assert valueBlocked(location) > 0 : "location already marked as unused: " + location;

            setValueBlocked(location, -1);

            allocator.getDebug().log("unblock %s", location);

        }

    }

    /**

     * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is

     * only blocked by {@code from}.

     */

    private boolean safeToProcessMove(Interval from, Interval to) {

        Value fromReg = from != null ? from.location() : null;

        Value location = to.location();

        if (mightBeBlocked(location)) {

            if ((valueBlocked(location) > 1 || (valueBlocked(location) == 1 && !isMoveToSelf(fromReg, location)))) {

                return false;

            }

        }

        return true;

    }

    protected boolean isMoveToSelf(Value from, Value to) {

        assert to != null;

        if (to.equals(from)) {

            return true;

        }

        if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {

            assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind(), allocator.getRegisterAllocationConfig()) : String.format("Same register but Kind mismatch %s <- %s", to, from);

            return true;

        }

        return false;

    }

    protected boolean mightBeBlocked(Value location) {

        return isRegister(location);

    }

    private void createInsertionBuffer(ArrayList<LIRInstruction> list) {

        assert !insertionBuffer.initialized() : "overwriting existing buffer";

        insertionBuffer.init(list);

    }

    private void appendInsertionBuffer() {

        if (insertionBuffer.initialized()) {

            insertionBuffer.finish();

        }

        assert !insertionBuffer.initialized() : "must be uninitialized now";

        insertIdx = -1;

    }

    private LIRInstruction insertMove(Interval fromInterval, Interval toInterval) {

        assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;

        assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind(), allocator.getRegisterAllocationConfig()) : "move between different types";

        assert insertIdx != -1 : "must setup insert position first";

        LIRInstruction move = createMove(fromInterval.operand, toInterval.operand, fromInterval.location(), toInterval.location());

        insertionBuffer.append(insertIdx, move);

        DebugContext debug = allocator.getDebug();

        if (debug.isLogEnabled()) {

            debug.log("insert move from %s to %s at %d", fromInterval, toInterval, insertIdx);

        }

        return move;

    }

    /**

     * @param fromOpr {@link Interval#operand operand} of the {@code from} interval

     * @param toOpr {@link Interval#operand operand} of the {@code to} interval

     * @param fromLocation {@link Interval#location() location} of the {@code to} interval

     * @param toLocation {@link Interval#location() location} of the {@code to} interval

     */

    protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {

        return getAllocator().getSpillMoveFactory().createMove(toOpr, fromOpr);

    }

    private LIRInstruction insertMove(Constant fromOpr, Interval toInterval) {

        assert insertIdx != -1 : "must setup insert position first";

        AllocatableValue toOpr = toInterval.operand;

        LIRInstruction move;

        if (LIRValueUtil.isStackSlotValue(toInterval.location())) {

            move = getAllocator().getSpillMoveFactory().createStackLoad(toOpr, fromOpr);

        } else {

            move = getAllocator().getSpillMoveFactory().createLoad(toOpr, fromOpr);

        }

        insertionBuffer.append(insertIdx, move);

        DebugContext debug = allocator.getDebug();

        if (debug.isLogEnabled()) {

            debug.log("insert move from value %s to %s at %d", fromOpr, toInterval, insertIdx);

        }

        return move;

    }

    @SuppressWarnings("try")

    private void resolveMappings() {

        DebugContext debug = allocator.getDebug();

        try (Indent indent = debug.logAndIndent("resolveMapping")) {

            assert verifyBeforeResolve();

            if (debug.isLogEnabled()) {

                printMapping();

            }

            // Block all registers that are used as input operands of a move.

            // When a register is blocked, no move to this register is emitted.

            // This is necessary for detecting cycles in moves.

            int i;

            for (i = mappingFrom.size() - 1; i >= 0; i--) {

                Interval fromInterval = mappingFrom.get(i);

                if (fromInterval != null) {

                    blockRegisters(fromInterval);

                }

            }

            ArrayList<AllocatableValue> busySpillSlots = null;

            while (mappingFrom.size() > 0) {

                boolean processedInterval = false;

                int spillCandidate = -1;

                for (i = mappingFrom.size() - 1; i >= 0; i--) {

                    Interval fromInterval = mappingFrom.get(i);

                    Interval toInterval = mappingTo.get(i);

                    if (safeToProcessMove(fromInterval, toInterval)) {

                        // this interval can be processed because target is free

                        final LIRInstruction move;

                        if (fromInterval != null) {

                            move = insertMove(fromInterval, toInterval);

                            unblockRegisters(fromInterval);

                        } else {

                            move = insertMove(mappingFromOpr.get(i), toInterval);

                        }

                        move.setComment(res, "MoveResolver resolve mapping");

                        if (LIRValueUtil.isStackSlotValue(toInterval.location())) {

                            if (busySpillSlots == null) {

                                busySpillSlots = new ArrayList<>(2);

                            }

                            busySpillSlots.add(toInterval.location());

                        }

                        mappingFrom.remove(i);

                        mappingFromOpr.remove(i);

                        mappingTo.remove(i);

                        processedInterval = true;

                    } else if (fromInterval != null && isRegister(fromInterval.location()) &&

                                    (busySpillSlots == null || !busySpillSlots.contains(fromInterval.spillSlot()))) {

                        // this interval cannot be processed now because target is not free

                        // it starts in a register, so it is a possible candidate for spilling

                        spillCandidate = i;

                    }

                }

                if (!processedInterval) {

                    breakCycle(spillCandidate);

                }

            }

        }

        // reset to default value

        multipleReadsAllowed = false;

        // check that all intervals have been processed

        assert checkEmpty();

    }

    protected void breakCycle(int spillCandidate) {

        // no move could be processed because there is a cycle in the move list

        // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory

        assert spillCandidate != -1 : "no interval in register for spilling found";

        // create a new spill interval and assign a stack slot to it

        Interval fromInterval = mappingFrom.get(spillCandidate);

        // do not allocate a new spill slot for temporary interval, but

        // use spill slot assigned to fromInterval. Otherwise moves from

        // one stack slot to another can happen (not allowed by LIRAssembler

        AllocatableValue spillSlot = fromInterval.spillSlot();

        if (spillSlot == null) {

            spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());

            fromInterval.setSpillSlot(spillSlot);

            cycleBreakingSlotsAllocated.increment(allocator.getDebug());

        }

        spillInterval(spillCandidate, fromInterval, spillSlot);

    }

    protected void spillInterval(int spillCandidate, Interval fromInterval, AllocatableValue spillSlot) {

        assert mappingFrom.get(spillCandidate).equals(fromInterval);

        Interval spillInterval = getAllocator().createDerivedInterval(fromInterval);

        spillInterval.setKind(fromInterval.kind());

        // add a dummy range because real position is difficult to calculate

        // Note: this range is a special case when the integrity of the allocation is

        // checked

        spillInterval.addRange(1, 2);

        spillInterval.assignLocation(spillSlot);

        DebugContext debug = allocator.getDebug();

        if (debug.isLogEnabled()) {

            debug.log("created new Interval for spilling: %s", spillInterval);

        }

        blockRegisters(spillInterval);

        // insert a move from register to stack and update the mapping

        LIRInstruction move = insertMove(fromInterval, spillInterval);

        mappingFrom.set(spillCandidate, spillInterval);

        unblockRegisters(fromInterval);

        move.setComment(res, "MoveResolver break cycle");

    }

    @SuppressWarnings("try")

    private void printMapping() {

        DebugContext debug = allocator.getDebug();

        try (Indent indent = debug.logAndIndent("Mapping")) {

            for (int i = mappingFrom.size() - 1; i >= 0; i--) {

                Interval fromInterval = mappingFrom.get(i);

                Interval toInterval = mappingTo.get(i);

                String from;

                Value to = toInterval.location();

                if (fromInterval == null) {

                    from = mappingFromOpr.get(i).toString();

                } else {

                    from = fromInterval.location().toString();

                }

                debug.log("move %s <- %s", from, to);

            }

        }

    }

    void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) {

        assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";

        createInsertionBuffer(insertList);

        this.insertIdx = insertIdx;

    }

    void moveInsertPosition(ArrayList<LIRInstruction> newInsertList, int newInsertIdx) {

        if (insertionBuffer.lirList() != null && (insertionBuffer.lirList() != newInsertList || this.insertIdx != newInsertIdx)) {

            // insert position changed . resolve current mappings

            resolveMappings();

        }

        if (insertionBuffer.lirList() != newInsertList) {

            // block changed . append insertionBuffer because it is

            // bound to a specific block and create a new insertionBuffer

            appendInsertionBuffer();

            createInsertionBuffer(newInsertList);

        }

        this.insertIdx = newInsertIdx;

    }

    public void addMapping(Interval fromInterval, Interval toInterval) {

        DebugContext debug = allocator.getDebug();

        if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) {

            if (debug.isLogEnabled()) {

                debug.log("no store to rematerializable interval %s needed", toInterval);

            }

            return;

        }

        if (isIllegal(fromInterval.location()) && fromInterval.canMaterialize()) {

            // Instead of a reload, re-materialize the value

            Constant rematValue = fromInterval.getMaterializedValue();

            addMapping(rematValue, toInterval);

            return;

        }

        if (debug.isLogEnabled()) {

            debug.log("add move mapping from %s to %s", fromInterval, toInterval);

        }

        assert !fromInterval.operand.equals(toInterval.operand) : "from and to interval equal: " + fromInterval;

        assert LIRKind.verifyMoveKinds(toInterval.kind(), fromInterval.kind(), allocator.getRegisterAllocationConfig()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s",

                        fromInterval.kind(),

                        toInterval.kind(), fromInterval, toInterval);

        mappingFrom.add(fromInterval);

        mappingFromOpr.add(null);

        mappingTo.add(toInterval);

    }

    public void addMapping(Constant fromOpr, Interval toInterval) {

        DebugContext debug = allocator.getDebug();

        if (debug.isLogEnabled()) {

            debug.log("add move mapping from %s to %s", fromOpr, toInterval);

        }

        mappingFrom.add(null);

        mappingFromOpr.add(fromOpr);

        mappingTo.add(toInterval);

    }

    void resolveAndAppendMoves() {

        if (hasMappings()) {

            resolveMappings();

        }

        appendInsertionBuffer();

    }

}