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

import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
import static jdk.vm.ci.code.ValueUtil.asRegister;
import static jdk.vm.ci.code.ValueUtil.asStackSlot;
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 java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.debug.DebugCounter;
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.VirtualStackSlot;
import org.graalvm.compiler.lir.framemap.FrameMap;
import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
import org.graalvm.compiler.lir.gen.LIRGenerationResult;
import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;

import jdk.vm.ci.code.Architecture;
import jdk.vm.ci.code.RegisterArray;
import jdk.vm.ci.code.StackSlot;
import jdk.vm.ci.meta.AllocatableValue;
import jdk.vm.ci.meta.Value;

/**
 */
public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver {

    private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(global)]");
    private static final DebugCounter cycleBreakingSlotsReused = Debug.counter("TraceRA[cycleBreakingSlotsReused(global)]");

    private int insertIdx;
    private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted

    private final List<Value> mappingFrom;
    private final List<Value> mappingFromStack;
    private final List<AllocatableValue> mappingTo;
    private final int[] registerBlocked;
    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
    private int[] stackBlocked;
    private final int firstVirtualStackIndex;
    private final MoveFactory spillMoveFactory;
    private final FrameMapBuilder frameMapBuilder;

    private void setValueBlocked(Value location, int direction) {
        assert direction == 1 || direction == -1 : "out of bounds";
        if (isStackSlotValue(location)) {
            int stackIdx = getStackArrayIndex(location);
            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
                // incoming stack arguments can be ignored
                return;
            }
            if (stackIdx >= stackBlocked.length) {
                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
            }
            stackBlocked[stackIdx] += direction;
        } else {
            assert direction == 1 || direction == -1 : "out of bounds";
            if (isRegister(location)) {
                registerBlocked[asRegister(location).number] += direction;
            } else {
                throw GraalError.shouldNotReachHere("unhandled value " + location);
            }
        }
    }

    private int valueBlocked(Value location) {
        if (isStackSlotValue(location)) {
            int stackIdx = getStackArrayIndex(location);
            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
                // incoming stack arguments are always blocked (aka they can not be written)
                return 1;
            }
            if (stackIdx >= stackBlocked.length) {
                return 0;
            }
            return stackBlocked[stackIdx];
        }
        if (isRegister(location)) {
            return registerBlocked[asRegister(location).number];
        }
        throw GraalError.shouldNotReachHere("unhandled value " + location);
    }

    private static boolean areMultipleReadsAllowed() {
        return true;
    }

    private boolean hasMappings() {
        return mappingFrom.size() > 0;
    }

    private MoveFactory getSpillMoveFactory() {
        return spillMoveFactory;
    }

    private RegisterArray getRegisters() {
        return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
    }

    public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, Architecture arch) {

        this.mappingFrom = new ArrayList<>(8);
        this.mappingFromStack = new ArrayList<>(8);
        this.mappingTo = new ArrayList<>(8);
        this.insertIdx = -1;
        this.insertionBuffer = new LIRInsertionBuffer();

        this.frameMapBuilder = res.getFrameMapBuilder();
        this.spillMoveFactory = spillMoveFactory;
        this.registerBlocked = new int[arch.getRegisters().size()];

        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];

        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
    }

    private boolean checkEmpty() {
        for (int i = 0; i < stackBlocked.length; i++) {
            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
        }
        assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing";
        for (int i = 0; i < getRegisters().size(); i++) {
            assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
        }
        return true;
    }

    private boolean verifyBeforeResolve() {
        assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.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";
            }
        }

        for (i = 0; i < mappingTo.size(); i++) {
            Value to = mappingTo.get(i);
            assert !isStackSlotValue(to) || getStackArrayIndex(to) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to;
        }

        HashSet<Value> usedRegs = new HashSet<>();
        if (!areMultipleReadsAllowed()) {
            for (i = 0; i < mappingFrom.size(); i++) {
                Value from = mappingFrom.get(i);
                if (from != null && !isIllegal(from)) {
                    boolean unique = usedRegs.add(from);
                    assert unique : "cannot read from same register twice";
                }
            }
        }

        usedRegs.clear();
        for (i = 0; i < mappingTo.size(); i++) {
            Value to = mappingTo.get(i);
            if (isIllegal(to)) {
                // After insertion the location may become illegal, so don't check it since multiple
                // intervals might be illegal.
                continue;
            }
            boolean unique = usedRegs.add(to);
            assert unique : "cannot write to same register twice";
        }

        return true;
    }

    // mark assignedReg and assignedRegHi of the interval as blocked
    private void block(Value location) {
        if (mightBeBlocked(location)) {
            assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
            setValueBlocked(location, 1);
            Debug.log("block %s", location);
        }
    }

    // mark assignedReg and assignedRegHi of the interval as unblocked
    private void unblock(Value location) {
        if (mightBeBlocked(location)) {
            assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
            setValueBlocked(location, -1);
            Debug.log("unblock %s", location);
        }
    }

    
Checks if to is not blocked or is only blocked by from.
/** * Checks if {@code to} is not blocked or is only blocked by {@code from}. */
private boolean safeToProcessMove(Value fromLocation, Value toLocation) { if (mightBeBlocked(toLocation)) { if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { return false; } } return true; } public static boolean isMoveToSelf(Value from, Value to) { assert to != null; if (to.equals(from)) { return true; } if (from == null) { return false; } if (isShadowedRegisterValue(from)) { /* From is a shadowed register. */ if (isShadowedRegisterValue(to)) { // both shadowed but not equal return false; } ShadowedRegisterValue shadowed = asShadowedRegisterValue(from); if (isRegisterToRegisterMoveToSelf(shadowed.getRegister(), to)) { return true; } if (isStackSlotValue(to)) { return to.equals(shadowed.getStackSlot()); } } else { /* * A shadowed destination value is never a self move it both values are not equal. Fall * through. */ // if (isShadowedRegisterValue(to)) return false; return isRegisterToRegisterMoveToSelf(from, to); } return false; } private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) { if (to.equals(from)) { return true; } if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { // Values differ but Registers are the same assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from); return true; } return false; } private static boolean mightBeBlocked(Value location) { return isRegister(location) || isStackSlotValue(location); } private void createInsertionBuffer(List<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 void insertMove(Value fromOperand, AllocatableValue toOperand) { assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind()) : "move between different types"; assert insertIdx != -1 : "must setup insert position first"; insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand)); if (Debug.isLogEnabled()) { Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); } }
Params:
  • fromOpr – Operand of the from interval
  • toOpr – Operand of the to interval
/** * @param fromOpr Operand of the {@code from} interval * @param toOpr Operand of the {@code to} interval */
private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { return getSpillMoveFactory().createStackMove(toOpr, asAllocatableValue(fromOpr)); } return getSpillMoveFactory().createMove(toOpr, fromOpr); } @SuppressWarnings("try") private void resolveMappings() { 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. for (int i = mappingFrom.size() - 1; i >= 0; i--) { Value from = mappingFrom.get(i); block(from); } ArrayList<AllocatableValue> busySpillSlots = null; while (mappingFrom.size() > 0) { boolean processedInterval = false; int spillCandidate = -1; for (int i = mappingFrom.size() - 1; i >= 0; i--) { Value fromLocation = mappingFrom.get(i); AllocatableValue toLocation = mappingTo.get(i); if (safeToProcessMove(fromLocation, toLocation)) { // this interval can be processed because target is free insertMove(fromLocation, toLocation); unblock(fromLocation); if (isStackSlotValue(toLocation)) { if (busySpillSlots == null) { busySpillSlots = new ArrayList<>(2); } busySpillSlots.add(toLocation); } mappingFrom.remove(i); mappingFromStack.remove(i); mappingTo.remove(i); processedInterval = true; } else if (fromLocation != null) { if (isRegister(fromLocation) && (busySpillSlots == null || !busySpillSlots.contains(mappingFromStack.get(i)))) { // 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; } else if (isStackSlotValue(fromLocation) && spillCandidate == -1) { // fall back to spill a stack slot in case no other candidate is found spillCandidate = i; } } } if (!processedInterval) { breakCycle(spillCandidate); } } } // check that all intervals have been processed assert checkEmpty(); } @SuppressWarnings("try") private 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 Value from = mappingFrom.get(spillCandidate); try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) { AllocatableValue spillSlot = null; if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue() && !isStackSlotValue(from)) { // don't use the stack slot if from is already the stack slot Value fromStack = mappingFromStack.get(spillCandidate); if (fromStack != null) { spillSlot = (AllocatableValue) fromStack; cycleBreakingSlotsReused.increment(); Debug.log("reuse slot for spilling: %s", spillSlot); } } if (spillSlot == null) { spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind()); cycleBreakingSlotsAllocated.increment(); Debug.log("created new slot for spilling: %s", spillSlot); // insert a move from register to stack and update the mapping insertMove(from, spillSlot); } block(spillSlot); mappingFrom.set(spillCandidate, spillSlot); unblock(from); } } @SuppressWarnings("try") private void printMapping() { try (Indent indent = Debug.logAndIndent("Mapping")) { for (int i = mappingFrom.size() - 1; i >= 0; i--) { Debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i)); } } } public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; createInsertionBuffer(insertList); this.insertIdx = insertIdx; } @Override public void addMapping(Value from, AllocatableValue to, Value fromStack) { if (Debug.isLogEnabled()) { Debug.log("add move mapping from %s to %s", from, to); } assert !from.equals(to) : "from and to interval equal: " + from; assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(), to.getValueKind(), from, to); assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind()) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s", fromStack.getValueKind(), to.getValueKind(), fromStack, to); mappingFrom.add(from); mappingFromStack.add(fromStack); mappingTo.add(to); } public void resolveAndAppendMoves() { if (hasMappings()) { resolveMappings(); } appendInsertionBuffer(); } private int getStackArrayIndex(Value stackSlotValue) { if (isStackSlot(stackSlotValue)) { return getStackArrayIndex(asStackSlot(stackSlotValue)); } if (isVirtualStackSlot(stackSlotValue)) { return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); } throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue); } private int getStackArrayIndex(StackSlot stackSlot) { int stackIdx; if (stackSlot.isInCallerFrame()) { // incoming stack arguments can be ignored stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; } else { assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; int offset = -stackSlot.getRawOffset(); assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); stackIdx = offset; } return stackIdx; } private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { return firstVirtualStackIndex + virtualStackSlot.getId(); } }