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 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 org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
29 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
30 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
31 import static jdk.vm.ci.code.ValueUtil.asRegister;
32 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
33 import static jdk.vm.ci.code.ValueUtil.isIllegal;
34 import static jdk.vm.ci.code.ValueUtil.isRegister;
35 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
36
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.HashSet;
40 import java.util.List;
41
42 import org.graalvm.compiler.core.common.LIRKind;
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
56 import jdk.vm.ci.code.Architecture;
57 import jdk.vm.ci.code.RegisterArray;
58 import jdk.vm.ci.code.StackSlot;
59 import jdk.vm.ci.meta.AllocatableValue;
60 import jdk.vm.ci.meta.Value;
61
62 /**
63 */
64 public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver {
65
66 private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(global)]");
67 private static final DebugCounter cycleBreakingSlotsReused = Debug.counter("TraceRA[cycleBreakingSlotsReused(global)]");
68
69 private int insertIdx;
70 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
71
72 private final List<Value> mappingFrom;
73 private final List<Value> mappingFromStack;
74 private final List<AllocatableValue> mappingTo;
75 private final int[] registerBlocked;
76 private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
77 private int[] stackBlocked;
78 private final int firstVirtualStackIndex;
79 private final MoveFactory spillMoveFactory;
80 private final FrameMapBuilder frameMapBuilder;
81
82 private void setValueBlocked(Value location, int direction) {
83 assert direction == 1 || direction == -1 : "out of bounds";
84 if (isStackSlotValue(location)) {
85 int stackIdx = getStackArrayIndex(location);
86 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
87 // incoming stack arguments can be ignored
88 return;
89 }
90 if (stackIdx >= stackBlocked.length) {
91 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
92 }
93 stackBlocked[stackIdx] += direction;
94 } else {
95 assert direction == 1 || direction == -1 : "out of bounds";
96 if (isRegister(location)) {
97 registerBlocked[asRegister(location).number] += direction;
98 } else {
99 throw GraalError.shouldNotReachHere("unhandled value " + location);
100 }
135 return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
136 }
137
138 public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, Architecture arch) {
139
140 this.mappingFrom = new ArrayList<>(8);
141 this.mappingFromStack = new ArrayList<>(8);
142 this.mappingTo = new ArrayList<>(8);
143 this.insertIdx = -1;
144 this.insertionBuffer = new LIRInsertionBuffer();
145
146 this.frameMapBuilder = res.getFrameMapBuilder();
147 this.spillMoveFactory = spillMoveFactory;
148 this.registerBlocked = new int[arch.getRegisters().size()];
149
150 FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
151 this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
152
153 FrameMap frameMap = frameMapBuilderTool.getFrameMap();
154 this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
155 }
156
157 private boolean checkEmpty() {
158 for (int i = 0; i < stackBlocked.length; i++) {
159 assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
160 }
161 assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing";
162 for (int i = 0; i < getRegisters().size(); i++) {
163 assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
164 }
165 return true;
166 }
167
168 private boolean verifyBeforeResolve() {
169 assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.size() : "length must be equal";
170 assert insertIdx != -1 : "insert position not set";
171
172 int i;
173 int j;
174 if (!areMultipleReadsAllowed()) {
279 }
280 return false;
281 }
282
283 private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) {
284 if (to.equals(from)) {
285 return true;
286 }
287 if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
288 // Values differ but Registers are the same
289 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
290 return true;
291 }
292 return false;
293 }
294
295 private static boolean mightBeBlocked(Value location) {
296 return isRegister(location) || isStackSlotValue(location);
297 }
298
299 private void createInsertionBuffer(List<LIRInstruction> list) {
300 assert !insertionBuffer.initialized() : "overwriting existing buffer";
301 insertionBuffer.init(list);
302 }
303
304 private void appendInsertionBuffer() {
305 if (insertionBuffer.initialized()) {
306 insertionBuffer.finish();
307 }
308 assert !insertionBuffer.initialized() : "must be uninitialized now";
309
310 insertIdx = -1;
311 }
312
313 private void insertMove(Value fromOperand, AllocatableValue toOperand) {
314 assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand;
315 assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind()) : "move between different types";
316 assert insertIdx != -1 : "must setup insert position first";
317
318 insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand));
319
387 if (!processedInterval) {
388 breakCycle(spillCandidate);
389 }
390 }
391 }
392
393 // check that all intervals have been processed
394 assert checkEmpty();
395 }
396
397 @SuppressWarnings("try")
398 private void breakCycle(int spillCandidate) {
399 // no move could be processed because there is a cycle in the move list
400 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
401 assert spillCandidate != -1 : "no interval in register for spilling found";
402
403 // create a new spill interval and assign a stack slot to it
404 Value from = mappingFrom.get(spillCandidate);
405 try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) {
406 AllocatableValue spillSlot = null;
407 if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue() && !isStackSlotValue(from)) {
408 // don't use the stack slot if from is already the stack slot
409 Value fromStack = mappingFromStack.get(spillCandidate);
410 if (fromStack != null) {
411 spillSlot = (AllocatableValue) fromStack;
412 cycleBreakingSlotsReused.increment();
413 Debug.log("reuse slot for spilling: %s", spillSlot);
414 }
415 }
416 if (spillSlot == null) {
417 spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind());
418 cycleBreakingSlotsAllocated.increment();
419 Debug.log("created new slot for spilling: %s", spillSlot);
420 // insert a move from register to stack and update the mapping
421 insertMove(from, spillSlot);
422 }
423 block(spillSlot);
424 mappingFrom.set(spillCandidate, spillSlot);
425 unblock(from);
426 }
427 }
428
429 @SuppressWarnings("try")
430 private void printMapping() {
431 try (Indent indent = Debug.logAndIndent("Mapping")) {
432 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
433 Debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i));
434 }
435 }
436 }
437
438 public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) {
439 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
440
441 createInsertionBuffer(insertList);
442 this.insertIdx = insertIdx;
443 }
444
445 @Override
446 public void addMapping(Value from, AllocatableValue to, Value fromStack) {
447 if (Debug.isLogEnabled()) {
448 Debug.log("add move mapping from %s to %s", from, to);
449 }
450
451 assert !from.equals(to) : "from and to interval equal: " + from;
452 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(), to.getValueKind(), from, to);
453 assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind()) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s", fromStack.getValueKind(),
454 to.getValueKind(), fromStack, to);
455 mappingFrom.add(from);
456 mappingFromStack.add(fromStack);
457 mappingTo.add(to);
458 }
|
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.debug.Debug;
43 import org.graalvm.compiler.debug.DebugCounter;
44 import org.graalvm.compiler.debug.GraalError;
45 import org.graalvm.compiler.debug.Indent;
46 import org.graalvm.compiler.lir.LIRInsertionBuffer;
47 import org.graalvm.compiler.lir.LIRInstruction;
48 import org.graalvm.compiler.lir.VirtualStackSlot;
49 import org.graalvm.compiler.lir.framemap.FrameMap;
50 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
51 import org.graalvm.compiler.lir.framemap.FrameMapBuilderTool;
52 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
53 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
54 import org.graalvm.compiler.options.OptionValues;
55
56 import jdk.vm.ci.code.Architecture;
57 import jdk.vm.ci.code.RegisterArray;
58 import jdk.vm.ci.code.StackSlot;
59 import jdk.vm.ci.meta.AllocatableValue;
60 import jdk.vm.ci.meta.Value;
61
62 /**
63 */
64 public final class TraceGlobalMoveResolver extends TraceGlobalMoveResolutionPhase.MoveResolver {
65
66 private static final DebugCounter cycleBreakingSlotsAllocated = Debug.counter("TraceRA[cycleBreakingSlotsAllocated(global)]");
67 private static final DebugCounter cycleBreakingSlotsReused = Debug.counter("TraceRA[cycleBreakingSlotsReused(global)]");
68
69 private int insertIdx;
70 private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
71
72 private final ArrayList<Value> mappingFrom;
73 private final ArrayList<Value> mappingFromStack;
74 private final ArrayList<AllocatableValue> mappingTo;
75 private final int[] registerBlocked;
76 private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
77 private int[] stackBlocked;
78 private final int firstVirtualStackIndex;
79 private final MoveFactory spillMoveFactory;
80 private final FrameMapBuilder frameMapBuilder;
81 private final OptionValues options;
82
83 private void setValueBlocked(Value location, int direction) {
84 assert direction == 1 || direction == -1 : "out of bounds";
85 if (isStackSlotValue(location)) {
86 int stackIdx = getStackArrayIndex(location);
87 if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
88 // incoming stack arguments can be ignored
89 return;
90 }
91 if (stackIdx >= stackBlocked.length) {
92 stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
93 }
94 stackBlocked[stackIdx] += direction;
95 } else {
96 assert direction == 1 || direction == -1 : "out of bounds";
97 if (isRegister(location)) {
98 registerBlocked[asRegister(location).number] += direction;
99 } else {
100 throw GraalError.shouldNotReachHere("unhandled value " + location);
101 }
136 return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
137 }
138
139 public TraceGlobalMoveResolver(LIRGenerationResult res, MoveFactory spillMoveFactory, Architecture arch) {
140
141 this.mappingFrom = new ArrayList<>(8);
142 this.mappingFromStack = new ArrayList<>(8);
143 this.mappingTo = new ArrayList<>(8);
144 this.insertIdx = -1;
145 this.insertionBuffer = new LIRInsertionBuffer();
146
147 this.frameMapBuilder = res.getFrameMapBuilder();
148 this.spillMoveFactory = spillMoveFactory;
149 this.registerBlocked = new int[arch.getRegisters().size()];
150
151 FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
152 this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
153
154 FrameMap frameMap = frameMapBuilderTool.getFrameMap();
155 this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
156 this.options = res.getLIR().getOptions();
157 }
158
159 private boolean checkEmpty() {
160 for (int i = 0; i < stackBlocked.length; i++) {
161 assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
162 }
163 assert mappingFrom.size() == 0 && mappingTo.size() == 0 && mappingFromStack.size() == 0 : "list must be empty before and after processing";
164 for (int i = 0; i < getRegisters().size(); i++) {
165 assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
166 }
167 return true;
168 }
169
170 private boolean verifyBeforeResolve() {
171 assert mappingFrom.size() == mappingTo.size() && mappingFrom.size() == mappingFromStack.size() : "length must be equal";
172 assert insertIdx != -1 : "insert position not set";
173
174 int i;
175 int j;
176 if (!areMultipleReadsAllowed()) {
281 }
282 return false;
283 }
284
285 private static boolean isRegisterToRegisterMoveToSelf(Value from, Value to) {
286 if (to.equals(from)) {
287 return true;
288 }
289 if (isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
290 // Values differ but Registers are the same
291 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
292 return true;
293 }
294 return false;
295 }
296
297 private static boolean mightBeBlocked(Value location) {
298 return isRegister(location) || isStackSlotValue(location);
299 }
300
301 private void createInsertionBuffer(ArrayList<LIRInstruction> list) {
302 assert !insertionBuffer.initialized() : "overwriting existing buffer";
303 insertionBuffer.init(list);
304 }
305
306 private void appendInsertionBuffer() {
307 if (insertionBuffer.initialized()) {
308 insertionBuffer.finish();
309 }
310 assert !insertionBuffer.initialized() : "must be uninitialized now";
311
312 insertIdx = -1;
313 }
314
315 private void insertMove(Value fromOperand, AllocatableValue toOperand) {
316 assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand;
317 assert LIRKind.verifyMoveKinds(fromOperand.getValueKind(), fromOperand.getValueKind()) : "move between different types";
318 assert insertIdx != -1 : "must setup insert position first";
319
320 insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand));
321
389 if (!processedInterval) {
390 breakCycle(spillCandidate);
391 }
392 }
393 }
394
395 // check that all intervals have been processed
396 assert checkEmpty();
397 }
398
399 @SuppressWarnings("try")
400 private void breakCycle(int spillCandidate) {
401 // no move could be processed because there is a cycle in the move list
402 // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
403 assert spillCandidate != -1 : "no interval in register for spilling found";
404
405 // create a new spill interval and assign a stack slot to it
406 Value from = mappingFrom.get(spillCandidate);
407 try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) {
408 AllocatableValue spillSlot = null;
409 if (TraceRegisterAllocationPhase.Options.TraceRAreuseStackSlotsForMoveResolutionCycleBreaking.getValue(options) && !isStackSlotValue(from)) {
410 // don't use the stack slot if from is already the stack slot
411 Value fromStack = mappingFromStack.get(spillCandidate);
412 if (fromStack != null) {
413 spillSlot = (AllocatableValue) fromStack;
414 cycleBreakingSlotsReused.increment();
415 Debug.log("reuse slot for spilling: %s", spillSlot);
416 }
417 }
418 if (spillSlot == null) {
419 spillSlot = frameMapBuilder.allocateSpillSlot(from.getValueKind());
420 cycleBreakingSlotsAllocated.increment();
421 Debug.log("created new slot for spilling: %s", spillSlot);
422 // insert a move from register to stack and update the mapping
423 insertMove(from, spillSlot);
424 }
425 block(spillSlot);
426 mappingFrom.set(spillCandidate, spillSlot);
427 unblock(from);
428 }
429 }
430
431 @SuppressWarnings("try")
432 private void printMapping() {
433 try (Indent indent = Debug.logAndIndent("Mapping")) {
434 for (int i = mappingFrom.size() - 1; i >= 0; i--) {
435 Debug.log("move %s <- %s (%s)", mappingTo.get(i), mappingFrom.get(i), mappingFromStack.get(i));
436 }
437 }
438 }
439
440 public void setInsertPosition(ArrayList<LIRInstruction> insertList, int insertIdx) {
441 assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
442
443 createInsertionBuffer(insertList);
444 this.insertIdx = insertIdx;
445 }
446
447 @Override
448 public void addMapping(Value from, AllocatableValue to, Value fromStack) {
449 if (Debug.isLogEnabled()) {
450 Debug.log("add move mapping from %s to %s", from, to);
451 }
452
453 assert !from.equals(to) : "from and to interval equal: " + from;
454 assert LIRKind.verifyMoveKinds(to.getValueKind(), from.getValueKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getValueKind(), to.getValueKind(), from, to);
455 assert fromStack == null || LIRKind.verifyMoveKinds(to.getValueKind(), fromStack.getValueKind()) : String.format("Kind mismatch: %s vs. %s, fromStack=%s, to=%s", fromStack.getValueKind(),
456 to.getValueKind(), fromStack, to);
457 mappingFrom.add(from);
458 mappingFromStack.add(fromStack);
459 mappingTo.add(to);
460 }
|