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 */
23 package org.graalvm.compiler.lir.alloc.lsra.ssa;
24
25 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
27 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
28 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
29 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
30
31 import java.util.Arrays;
32
33 import org.graalvm.compiler.debug.GraalError;
34 import org.graalvm.compiler.lir.LIRInstruction;
35 import org.graalvm.compiler.lir.VirtualStackSlot;
36 import org.graalvm.compiler.lir.alloc.lsra.Interval;
37 import org.graalvm.compiler.lir.alloc.lsra.LinearScan;
38 import org.graalvm.compiler.lir.alloc.lsra.MoveResolver;
39 import org.graalvm.compiler.lir.framemap.FrameMap;
40 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
41
42 import jdk.vm.ci.code.StackSlot;
43 import jdk.vm.ci.meta.AllocatableValue;
44 import jdk.vm.ci.meta.Value;
45
46 public 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 }