1/*
2 * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package org.graalvm.compiler.lir.alloc.lsra.ssa;
24
25import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
26import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
27import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
28import static jdk.vm.ci.code.ValueUtil.asStackSlot;
29import static jdk.vm.ci.code.ValueUtil.isStackSlot;
30
31import java.util.Arrays;
32
33import org.graalvm.compiler.debug.GraalError;
34import org.graalvm.compiler.lir.LIRInstruction;
35import org.graalvm.compiler.lir.VirtualStackSlot;
36import org.graalvm.compiler.lir.alloc.lsra.Interval;
37import org.graalvm.compiler.lir.alloc.lsra.LinearScan;
38import org.graalvm.compiler.lir.alloc.lsra.MoveResolver;
39import org.graalvm.compiler.lir.framemap.FrameMap;
40import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
41
42import jdk.vm.ci.code.StackSlot;
43import jdk.vm.ci.meta.AllocatableValue;
44import jdk.vm.ci.meta.Value;
45
46public final class SSAMoveResolver extends MoveResolver {
47
48    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
49    private int[] stackBlocked;
50    private final int firstVirtualStackIndex;
51
52    public SSAMoveResolver(LinearScan allocator) {
53        super(allocator);
54        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder();
55        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
56        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
57        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
58    }
59
60    @Override
61    public boolean checkEmpty() {
62        for (int i = 0; i < stackBlocked.length; i++) {
63            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
64        }
65        return super.checkEmpty();
66    }
67
68    @Override
69    protected void checkMultipleReads() {
70        // multiple reads are allowed in SSA LSRA
71    }
72
73    @Override
74    protected void verifyStackSlotMapping() {
75        // relax disjoint stack maps invariant
76    }
77
78    @Override
79    protected boolean areMultipleReadsAllowed() {
80        return true;
81    }
82
83    @Override
84    protected boolean mightBeBlocked(Value location) {
85        if (super.mightBeBlocked(location)) {
86            return true;
87        }
88        if (isStackSlotValue(location)) {
89            return true;
90        }
91        return false;
92    }
93
94    private int getStackArrayIndex(Value stackSlotValue) {
95        if (isStackSlot(stackSlotValue)) {
96            return getStackArrayIndex(asStackSlot(stackSlotValue));
97        }
98        if (isVirtualStackSlot(stackSlotValue)) {
99            return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
100        }
101        throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue);
102    }
103
104    private int getStackArrayIndex(StackSlot stackSlot) {
105        int stackIdx;
106        if (stackSlot.isInCallerFrame()) {
107            // incoming stack arguments can be ignored
108            stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
109        } else {
110            assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
111            int offset = -stackSlot.getRawOffset();
112            assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
113            stackIdx = offset;
114        }
115        return stackIdx;
116    }
117
118    private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
119        return firstVirtualStackIndex + virtualStackSlot.getId();
120    }
121
122    @Override
123    protected void setValueBlocked(Value location, int direction) {
124        assert direction == 1 || direction == -1 : "out of bounds";
125        if (isStackSlotValue(location)) {
126            int stackIdx = getStackArrayIndex(location);
127            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
128                // incoming stack arguments can be ignored
129                return;
130            }
131            if (stackIdx >= stackBlocked.length) {
132                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
133            }
134            stackBlocked[stackIdx] += direction;
135        } else {
136            super.setValueBlocked(location, direction);
137        }
138    }
139
140    @Override
141    protected int valueBlocked(Value location) {
142        if (isStackSlotValue(location)) {
143            int stackIdx = getStackArrayIndex(location);
144            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
145                // incoming stack arguments are always blocked (aka they can not be written)
146                return 1;
147            }
148            if (stackIdx >= stackBlocked.length) {
149                return 0;
150            }
151            return stackBlocked[stackIdx];
152        }
153        return super.valueBlocked(location);
154    }
155
156    @Override
157    protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
158        if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
159            return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
160        }
161        return super.createMove(fromOpr, toOpr, fromLocation, toLocation);
162    }
163
164    @Override
165    protected void breakCycle(int spillCandidate) {
166        if (spillCandidate != -1) {
167            super.breakCycle(spillCandidate);
168            return;
169        }
170        assert mappingFromSize() > 1;
171        // Arbitrarily select the first entry for spilling.
172        int stackSpillCandidate = 0;
173        Interval fromInterval = getMappingFrom(stackSpillCandidate);
174        // allocate new stack slot
175        VirtualStackSlot spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
176        spillInterval(stackSpillCandidate, fromInterval, spillSlot);
177    }
178}
179