1 /*
2 * Copyright (c) 2009, 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.trace;
24
25 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
28 import static jdk.vm.ci.code.ValueUtil.isIllegal;
29 import static jdk.vm.ci.code.ValueUtil.isRegister;
30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
31 import static org.graalvm.compiler.lir.LIRValueUtil.asVirtualStackSlot;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
33 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
34 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
35 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
36
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.HashSet;
40
41 import org.graalvm.compiler.core.common.LIRKind;
42 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
43 import org.graalvm.compiler.debug.Debug;
44 import org.graalvm.compiler.debug.DebugCounter;
45 import org.graalvm.compiler.debug.GraalError;
46 import org.graalvm.compiler.debug.Indent;
47 import org.graalvm.compiler.lir.LIRInsertionBuffer;
48 import org.graalvm.compiler.lir.LIRInstruction;
49 import org.graalvm.compiler.lir.VirtualStackSlot;
50 import org.graalvm.compiler.lir.framemap.FrameMap;
51 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
52 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
53 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
54 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
55 import org.graalvm.compiler.options.OptionValues;
56
57 import jdk.vm.ci.code.Architecture;
58 import jdk.vm.ci.code.RegisterArray;
59 import jdk.vm.ci.code.StackSlot;
60 import jdk.vm.ci.meta.AllocatableValue;
61 import jdk.vm.ci.meta.Value;
62
63 /**
64 */
65 public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver {
66
67 private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(global)]");
68 private static final DebugCounter cycleBreakingSlotsReused = Debug.counter("TraceRA[cycleBreakingSlotsReused(global)]");
69
70 private int insertIdx;
71 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
72
73 private final ArrayList<Value> mappingFrom;
74 private final ArrayList<Value> mappingFromStack;
75 private final ArrayList<AllocatableValue> mappingTo;
76 private final int[] registerBlocked;
77 private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
78 private int[] stackBlocked;
79 private final int firstVirtualStackIndex;
80 private final MoveFactory spillMoveFactory;
81 private final FrameMapBuilder frameMapBuilder;
82 private final OptionValues options;
83 private final RegisterAllocationConfig registerAllocationConfig;
84 private final LIRGenerationResult res;
85
86 private void setValueBlocked(Value location, int direction) {
87 assert direction == 1 || direction == -1 : "out of bounds";
88 if (isStackSlotValue(location)) {
89 int stackIdx = getStackArrayIndex(location);
90 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
91 // incoming stack arguments can be ignored
92 return;
93 }
94 if (stackIdx >= stackBlocked.length) {
95 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
96 }
97 stackBlocked[stackIdx] += direction;
98 } else {
99 assert direction == 1 || direction == -1 : "out of bounds";
100 if (isRegister(location)) {
101 registerBlocked[asRegister(location).number] += direction;
102 } else {
103 throw GraalError.shouldNotReachHere("unhandled value " + location);
104 }
105 }
106 }
107
108 private int valueBlocked(Value location) {
109 if (isStackSlotValue(location)) {
110 int stackIdx = getStackArrayIndex(location);
111 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
112 // incoming stack arguments are always blocked (aka they can not be written)
113 return 1;
114 }
115 if (stackIdx >= stackBlocked.length) {
116 return 0;
117 }
118 return stackBlocked[stackIdx];
119 }
120 if (isRegister(location)) {
121 return registerBlocked[asRegister(location).number];
122 }
123 throw GraalError.shouldNotReachHere("unhandled value " + location);
124 }
125
126 private static boolean areMultipleReadsAllowed() {
127 return true;
128 }
129
130 private boolean hasMappings() {
131 return mappingFrom.size() > 0;
132 }
133
134 private MoveFactory getSpillMoveFactory() {
135 return spillMoveFactory;
136 }
137
138 private RegisterArray getRegisters() {
139 return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
140 }
141
142 public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig, Architecture arch) {
143
144 this.mappingFrom = new ArrayList<>(8);
145 this.mappingFromStack = new ArrayList<>(8);
146 this.mappingTo = new ArrayList<>(8);
147 this.insertIdx = -1;
148 this.insertionBuffer = new LIRInsertionBuffer();
149
150 this.frameMapBuilder = res.getFrameMapBuilder();
151 this.spillMoveFactory = spillMoveFactory;
152 this.registerBlocked = new int[arch.getRegisters().size()];
153 this.registerAllocationConfig = registerAllocationConfig;
154
155 FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
156 this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
157
158 FrameMap frameMap = frameMapBuilderTool.getFrameMap();
159 this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
160 this.options = res.getLIR().getOptions();
161 this.res = res;
162 }
163
164 private boolean checkEmpty() {
165 for (int i = 0; i < stackBlocked.length; i++) {
166 assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
167 }
168 assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing";
169 for (int i = 0; i < getRegisters().size(); i++) {
170 assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
171 }
172 return true;
173 }
174
175 private boolean verifyBeforeResolve() {
176 assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.size() : "length must be equal";
177 assert insertIdx != -1 : "insert position not set";
178
179 int i;
180 int j;
181 if (!areMultipleReadsAllowed()) {
182 for (i = 0; i < mappingFrom.size(); i++) {
183 for (j = i + 1; j < mappingFrom.size(); j++) {
184 assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
185 }
186 }
187 }
188
189 for (i = 0; i < mappingTo.size(); i++) {
190 for (j = i + 1; j < mappingTo.size(); j++) {
191 assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
192 }
193 }
194
195 for (i = 0; i < mappingTo.size(); i++) {
196 Value to = mappingTo.get(i);
197 assert !isStackSlotValue(to) || getStackArrayIndex(to) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to;
198 }
199
200 HashSet<Value> usedRegs = new HashSet<>();
201 if (!areMultipleReadsAllowed()) {
202 for (i = 0; i < mappingFrom.size(); i++) {
203 Value from = mappingFrom.get(i);
204 if (from != null && !isIllegal(from)) {
205 boolean unique = usedRegs.add(from);
206 assert unique : "cannot read from same register twice";
207 }
208 }
209 }
210
211 usedRegs.clear();
212 for (i = 0; i < mappingTo.size(); i++) {
213 Value to = mappingTo.get(i);
214 if (isIllegal(to)) {
215 // After insertion the location may become illegal, so don't check it since multiple
216 // intervals might be illegal.
217 continue;
218 }
219 boolean unique = usedRegs.add(to);
220 assert unique : "cannot write to same register twice";
221 }
222
223 return true;
224 }
225
226 // mark assignedReg and assignedRegHi of the interval as blocked
227 private void block(Value location) {
228 if (mightBeBlocked(location)) {
229 assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
230 setValueBlocked(location, 1);
231 Debug.log("block %s", location);
232 }
233 }
234
235 // mark assignedReg and assignedRegHi of the interval as unblocked
236 private void unblock(Value location) {
237 if (mightBeBlocked(location)) {
238 assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
239 setValueBlocked(location, -1);
240 Debug.log("unblock %s", location);
241 }
242 }
243
244 /**
245 * Checks if {@code to} is not blocked or is only blocked by {@code from}.
246 */
247 private boolean safeToProcessMove(Value fromLocation, Value toLocation) {
248 if (mightBeBlocked(toLocation)) {
249 if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) {
250 return false;
251 }
252 }
253
254 return true;
255 }
256
257 public static boolean isMoveToSelf(Value from, Value to) {
258 assert to != null;
259 if (to.equals(from)) {
260 return true;
261 }
262 if (from == null) {
263 return false;
264 }
265 if (isShadowedRegisterValue(from)) {
266 /* From is a shadowed register. */
267 if (isShadowedRegisterValue(to)) {
268 // both shadowed but not equal
269 return false;
270 }
271 ShadowedRegisterValue shadowed = asShadowedRegisterValue(from);
272 if (isRegisterToRegisterMoveToSelf(shadowed.getRegister(), to)) {
273 return true;
274 }
275 if (isStackSlotValue(to)) {
276 return to.equals(shadowed.getStackSlot());
277 }
278 } else {
279 /*
280 * A shadowed destination value is never a self move it both values are not equal. Fall
281 * through.
282 */
283 // if (isShadowedRegisterValue(to)) return false;
284
285 return isRegisterToRegisterMoveToSelf(from, to);
286 }
287 return false;
288 }
289
290 private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) {
291 if (to.equals(from)) {
292 return true;
293 }
294 if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
295 // Values differ but Registers are the same
296 return true;
297 }
298 return false;
299 }
300
301 private static boolean mightBeBlocked(Value location) {
302 return isRegister(location) || isStackSlotValue(location);
303 }
304
305 private void createInsertionBuffer(ArrayList<LIRInstruction> list) {
306 assert !insertionBuffer.initialized() : "overwriting existing buffer";
307 insertionBuffer.init(list);
308 }
309
310 private void appendInsertionBuffer() {
311 if (insertionBuffer.initialized()) {
312 insertionBuffer.finish();
313 }
314 assert !insertionBuffer.initialized() : "must be uninitialized now";
315
316 insertIdx = -1;
317 }
318
319 private LIRInstruction insertMove(Value fromOperand, AllocatableValue toOperand) {
320 assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand;
321 assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind(), registerAllocationConfig) : "move between different types";
322 assert insertIdx != -1 : "must setup insert position first";
323
324 LIRInstruction move = createMove(fromOperand, toOperand);
325 insertionBuffer.append(insertIdx, move);
326
327 if (Debug.isLogEnabled()) {
328 Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx);
329 }
330 return move;
331 }
332
333 /**
334 * @param fromOpr Operand of the {@code from} interval
335 * @param toOpr Operand of the {@code to} interval
336 */
337 private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) {
338 if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) {
339 return getSpillMoveFactory().createStackMove(toOpr, asAllocatableValue(fromOpr));
340 }
341 return getSpillMoveFactory().createMove(toOpr, fromOpr);
342 }
343
344 @SuppressWarnings("try")
345 private void resolveMappings() {
346 try (Indent indent = Debug.logAndIndent("resolveMapping")) {
347 assert verifyBeforeResolve();
348 if (Debug.isLogEnabled()) {
349 printMapping();
350 }
351
352 // Block all registers that are used as input operands of a move.
353 // When a register is blocked, no move to this register is emitted.
354 // This is necessary for detecting cycles in moves.
355 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
356 Value from = mappingFrom.get(i);
357 block(from);
358 }
359
360 ArrayList<AllocatableValue> busySpillSlots = null;
361 while (mappingFrom.size() > 0) {
362 boolean processedInterval = false;
363
364 int spillCandidate = -1;
365 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
366 Value fromLocation = mappingFrom.get(i);
367 AllocatableValue toLocation = mappingTo.get(i);
368 if (safeToProcessMove(fromLocation, toLocation)) {
369 // this interval can be processed because target is free
370 LIRInstruction move = insertMove(fromLocation, toLocation);
371 move.setComment(res, "TraceGlobalMoveResolver: resolveMapping");
372 unblock(fromLocation);
373 if (isStackSlotValue(toLocation)) {
374 if (busySpillSlots == null) {
375 busySpillSlots = new ArrayList<>(2);
376 }
377 busySpillSlots.add(toLocation);
378 }
379 mappingFrom.remove(i);
380 mappingFromStack.remove(i);
381 mappingTo.remove(i);
382
383 processedInterval = true;
384 } else if (fromLocation != null) {
385 if (isRegister(fromLocation) && (busySpillSlots == null || !busySpillSlots.contains(mappingFromStack.get(i)))) {
386 // this interval cannot be processed now because target is not free
387 // it starts in a register, so it is a possible candidate for spilling
388 spillCandidate = i;
389 } else if (isStackSlotValue(fromLocation) && spillCandidate == -1) {
390 // fall back to spill a stack slot in case no other candidate is found
391 spillCandidate = i;
392 }
393 }
394 }
395
396 if (!processedInterval) {
397 breakCycle(spillCandidate);
398 }
399 }
400 }
401
402 // check that all intervals have been processed
403 assert checkEmpty();
404 }
405
406 @SuppressWarnings("try")
407 private void breakCycle(int spillCandidate) {
408 // no move could be processed because there is a cycle in the move list
409 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
410 assert spillCandidate != -1 : "no interval in register for spilling found";
411
412 // create a new spill interval and assign a stack slot to it
413 Value from = mappingFrom.get(spillCandidate);
414 try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) {
415 AllocatableValue spillSlot = null;
416 if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue(options) && !isStackSlotValue(from)) {
417 // don't use the stack slot if from is already the stack slot
418 Value fromStack = mappingFromStack.get(spillCandidate);
419 if (fromStack != null) {
420 spillSlot = (AllocatableValue) fromStack;
421 cycleBreakingSlotsReused.increment();
422 Debug.log("reuse slot for spilling: %s", spillSlot);
423 }
424 }
425 if (spillSlot == null) {
426 spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind());
427 cycleBreakingSlotsAllocated.increment();
428 Debug.log("created new slot for spilling: %s", spillSlot);
429 // insert a move from register to stack and update the mapping
430 LIRInstruction move = insertMove(from, spillSlot);
431 move.setComment(res, "TraceGlobalMoveResolver: breakCycle");
432 }
433 block(spillSlot);
434 mappingFrom.set(spillCandidate, spillSlot);
435 unblock(from);
436 }
437 }
438
439 @SuppressWarnings("try")
440 private void printMapping() {
441 try (Indent indent = Debug.logAndIndent("Mapping")) {
442 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
443 Debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i));
444 }
445 }
446 }
447
448 public void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) {
449 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
450
451 createInsertionBuffer(insertList);
452 this.insertIdx = insertIdx;
453 }
454
455 @Override
456 public void addMapping(Value from, AllocatableValue to, Value fromStack) {
457 if (Debug.isLogEnabled()) {
458 Debug.log("add move mapping from %s to %s", from, to);
459 }
460
461 assert !from.equals(to) : "from and to interval equal: " + from;
462 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind(), registerAllocationConfig) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(),
463 to.getValueKind(), from, to);
464 assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind(), registerAllocationConfig) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s",
465 fromStack.getValueKind(),
466 to.getValueKind(), fromStack, to);
467 mappingFrom.add(from);
468 mappingFromStack.add(fromStack);
469 mappingTo.add(to);
470 }
471
472 public void resolveAndAppendMoves() {
473 if (hasMappings()) {
474 resolveMappings();
475 }
476 appendInsertionBuffer();
477 }
478
479 private int getStackArrayIndex(Value stackSlotValue) {
480 if (isStackSlot(stackSlotValue)) {
481 return getStackArrayIndex(asStackSlot(stackSlotValue));
482 }
483 if (isVirtualStackSlot(stackSlotValue)) {
484 return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
485 }
486 throw GraalError.shouldNotReachHere("value is not a stack slot: " + stackSlotValue);
487 }
488
489 private int getStackArrayIndex(StackSlot stackSlot) {
490 int stackIdx;
491 if (stackSlot.isInCallerFrame()) {
492 // incoming stack arguments can be ignored
493 stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
494 } else {
495 assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
496 int offset = -stackSlot.getRawOffset();
497 assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
498 stackIdx = offset;
499 }
500 return stackIdx;
501 }
502
503 private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
504 return firstVirtualStackIndex + virtualStackSlot.getId();
505 }
506
507 }