001/*
002 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.lir.alloc.lsra.ssa;
024
025import static jdk.internal.jvmci.code.ValueUtil.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import jdk.internal.jvmci.common.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.lir.*;
034import com.oracle.graal.lir.alloc.lsra.*;
035import com.oracle.graal.lir.framemap.*;
036
037public final class SSAMoveResolver extends MoveResolver {
038
039    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
040    private int[] stackBlocked;
041    private final int firstVirtualStackIndex;
042
043    public SSAMoveResolver(LinearScan allocator) {
044        super(allocator);
045        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder();
046        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
047        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
048        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
049    }
050
051    @Override
052    public boolean checkEmpty() {
053        for (int i = 0; i < stackBlocked.length; i++) {
054            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
055        }
056        return super.checkEmpty();
057    }
058
059    @Override
060    protected void checkMultipleReads() {
061        // multiple reads are allowed in SSA LSRA
062    }
063
064    @Override
065    protected void verifyStackSlotMapping() {
066        // relax disjoint stack maps invariant
067    }
068
069    @Override
070    protected boolean areMultipleReadsAllowed() {
071        return true;
072    }
073
074    @Override
075    protected boolean mightBeBlocked(Value location) {
076        if (super.mightBeBlocked(location)) {
077            return true;
078        }
079        if (isStackSlotValue(location)) {
080            return true;
081        }
082        return false;
083    }
084
085    private int getStackArrayIndex(StackSlotValue stackSlotValue) {
086        if (isStackSlot(stackSlotValue)) {
087            return getStackArrayIndex(asStackSlot(stackSlotValue));
088        }
089        if (isVirtualStackSlot(stackSlotValue)) {
090            return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
091        }
092        throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue);
093    }
094
095    private int getStackArrayIndex(StackSlot stackSlot) {
096        int stackIdx;
097        if (stackSlot.isInCallerFrame()) {
098            // incoming stack arguments can be ignored
099            stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
100        } else {
101            assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
102            int offset = -stackSlot.getRawOffset();
103            assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
104            stackIdx = offset;
105        }
106        return stackIdx;
107    }
108
109    private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
110        return firstVirtualStackIndex + virtualStackSlot.getId();
111    }
112
113    @Override
114    protected void setValueBlocked(Value location, int direction) {
115        assert direction == 1 || direction == -1 : "out of bounds";
116        if (isStackSlotValue(location)) {
117            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
118            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
119                // incoming stack arguments can be ignored
120                return;
121            }
122            if (stackIdx >= stackBlocked.length) {
123                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
124            }
125            stackBlocked[stackIdx] += direction;
126        } else {
127            super.setValueBlocked(location, direction);
128        }
129    }
130
131    @Override
132    protected int valueBlocked(Value location) {
133        if (isStackSlotValue(location)) {
134            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
135            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
136                // incoming stack arguments are always blocked (aka they can not be written)
137                return 1;
138            }
139            if (stackIdx >= stackBlocked.length) {
140                return 0;
141            }
142            return stackBlocked[stackIdx];
143        }
144        return super.valueBlocked(location);
145    }
146
147    @Override
148    protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
149        if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
150            return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
151        }
152        return super.createMove(fromOpr, toOpr, fromLocation, toLocation);
153    }
154
155    @Override
156    protected void breakCycle(int spillCandidate) {
157        if (spillCandidate != -1) {
158            super.breakCycle(spillCandidate);
159            return;
160        }
161        assert mappingFromSize() > 1;
162        // Arbitrarily select the first entry for spilling.
163        int stackSpillCandidate = 0;
164        Interval fromInterval = getMappingFrom(stackSpillCandidate);
165        assert isStackSlotValue(fromInterval.location());
166        // allocate new stack slot
167        StackSlotValue spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
168        spillInterval(stackSpillCandidate, fromInterval, spillSlot);
169    }
170}