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