1 /*
2 * Copyright (c) 2011, 2019, 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
24
25 package org.graalvm.compiler.lir;
26
27 import static jdk.vm.ci.code.ValueUtil.asStackSlot;
28 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
29 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.CONST;
30 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.HINT;
31 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.OUTGOING;
32 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.REG;
33 import static org.graalvm.compiler.lir.LIRInstruction.OperandFlag.STACK;
34
35 import java.util.ArrayList;
36 import java.util.Arrays;
37 import java.util.EnumSet;
38
39 import jdk.internal.vm.compiler.collections.EconomicSet;
40 import jdk.internal.vm.compiler.collections.Equivalence;
41 import org.graalvm.compiler.asm.Label;
42 import org.graalvm.compiler.core.common.GraalOptions;
43 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
44 import org.graalvm.compiler.debug.GraalError;
45 import org.graalvm.compiler.lir.asm.CompilationResultBuilder;
46 import org.graalvm.compiler.lir.framemap.FrameMap;
47
48 import jdk.vm.ci.code.Register;
49 import jdk.vm.ci.code.RegisterSaveLayout;
50 import jdk.vm.ci.code.StackSlot;
51 import jdk.vm.ci.meta.AllocatableValue;
52 import jdk.vm.ci.meta.Constant;
53 import jdk.vm.ci.meta.Value;
54
55 /**
56 * A collection of machine-independent LIR operations, as well as interfaces to be implemented for
57 * specific kinds or LIR operations.
58 */
59 public class StandardOp {
60
61 /**
62 * A block delimiter. Every well formed block must contain exactly one such operation and it
63 * must be the last operation in the block.
64 */
65 public interface BlockEndOp {
66 }
67
68 public interface NullCheck {
69 Value getCheckedValue();
70
71 LIRFrameState getState();
72 }
73
74 public interface ImplicitNullCheck {
75 boolean makeNullCheckFor(Value value, LIRFrameState nullCheckState, int implicitNullCheckLimit);
76 }
77
78 public interface LabelHoldingOp {
79 Label getLabel();
80 }
81
82 /**
83 * LIR operation that defines the position of a label.
84 */
85 public static final class LabelOp extends LIRInstruction implements LabelHoldingOp {
86 public static final LIRInstructionClass<LabelOp> TYPE = LIRInstructionClass.create(LabelOp.class);
87 public static final EnumSet<OperandFlag> incomingFlags = EnumSet.of(REG, STACK);
88
89 /**
90 * In the LIR, every register and variable must be defined before it is used. For method
91 * parameters that are passed in fixed registers, exception objects passed to the exception
92 * handler in a fixed register, or any other use of a fixed register not defined in this
93 * method, an artificial definition is necessary. To avoid spill moves to be inserted
94 * between the label at the beginning of a block an an actual definition in the second
95 * instruction of a block, the registers are defined here in the label.
96 */
97 @Def({REG, STACK}) private Value[] incomingValues;
98 private final Label label;
99 private final boolean align;
100 private int numbPhis;
101
102 public LabelOp(Label label, boolean align) {
103 super(TYPE);
104 this.label = label;
105 this.align = align;
106 this.incomingValues = Value.NO_VALUES;
107 this.numbPhis = 0;
108 }
109
110 public void setPhiValues(Value[] values) {
111 setIncomingValues(values);
112 setNumberOfPhis(values.length);
113 }
114
115 private void setNumberOfPhis(int numPhis) {
116 assert numbPhis == 0;
117 numbPhis = numPhis;
118 }
119
120 public int getPhiSize() {
121 return numbPhis;
122 }
123
124 public void setIncomingValues(Value[] values) {
125 assert this.incomingValues.length == 0;
126 assert values != null;
127 this.incomingValues = values;
128 }
129
130 public int getIncomingSize() {
131 return incomingValues.length;
132 }
133
134 public Value getIncomingValue(int idx) {
135 assert checkRange(idx);
136 return incomingValues[idx];
137 }
138
139 public void clearIncomingValues() {
140 incomingValues = Value.NO_VALUES;
141 }
142
143 public void addIncomingValues(Value[] values) {
144 if (incomingValues.length == 0) {
145 setIncomingValues(values);
146 return;
147 }
148 int t = incomingValues.length + values.length;
149 Value[] newArray = new Value[t];
150 System.arraycopy(incomingValues, 0, newArray, 0, incomingValues.length);
151 System.arraycopy(values, 0, newArray, incomingValues.length, values.length);
152 incomingValues = newArray;
153 }
154
155 private boolean checkRange(int idx) {
156 return idx < incomingValues.length;
157 }
158
159 @Override
160 public void emitCode(CompilationResultBuilder crb) {
161 if (align) {
162 crb.asm.align(GraalOptions.LoopHeaderAlignment.getValue(crb.getOptions()));
163 }
164 crb.asm.bind(label);
165 }
166
167 @Override
168 public Label getLabel() {
169 return label;
170 }
171
172 /**
173 * @return true if this label acts as a PhiIn.
174 */
175 public boolean isPhiIn() {
176 return getPhiSize() > 0;
177 }
178
179 public void forEachIncomingValue(InstructionValueProcedure proc) {
180 for (int i = 0; i < incomingValues.length; i++) {
181 incomingValues[i] = proc.doValue(this, incomingValues[i], OperandMode.DEF, incomingFlags);
182 }
183 }
184 }
185
186 /**
187 * LIR operation that is an unconditional jump to a {@link #destination()}.
188 */
189 public static class JumpOp extends LIRInstruction implements BlockEndOp {
190 public static final LIRInstructionClass<JumpOp> TYPE = LIRInstructionClass.create(JumpOp.class);
191 public static final EnumSet<OperandFlag> outgoingFlags = EnumSet.of(REG, STACK, CONST, OUTGOING);
192
193 @Alive({REG, STACK, CONST, OUTGOING}) private Value[] outgoingValues;
194
195 private final LabelRef destination;
196
197 public JumpOp(LabelRef destination) {
198 this(TYPE, destination);
199 }
200
201 protected JumpOp(LIRInstructionClass<? extends JumpOp> c, LabelRef destination) {
202 super(c);
203 this.destination = destination;
204 this.outgoingValues = Value.NO_VALUES;
205 }
206
207 @Override
208 public void emitCode(CompilationResultBuilder crb) {
209 if (!crb.isSuccessorEdge(destination)) {
210 crb.asm.jmp(destination.label());
211 }
212 }
213
214 public LabelRef destination() {
215 return destination;
216 }
217
218 public void setPhiValues(Value[] values) {
219 assert this.outgoingValues.length == 0;
220 assert values != null;
221 this.outgoingValues = values;
222 }
223
224 public int getPhiSize() {
225 return outgoingValues.length;
226 }
227
228 public Value getOutgoingValue(int idx) {
229 assert checkRange(idx);
230 return outgoingValues[idx];
231 }
232
233 public void clearOutgoingValues() {
234 outgoingValues = Value.NO_VALUES;
235 }
236
237 private boolean checkRange(int idx) {
238 return idx < outgoingValues.length;
239 }
240 }
241
242 /**
243 * Marker interface for a LIR operation that is a conditional jump.
244 */
245 public interface BranchOp extends BlockEndOp {
246 }
247
248 /**
249 * Marker interface for a LIR operation that moves a value to {@link #getResult()}.
250 */
251 public interface MoveOp {
252
253 AllocatableValue getResult();
254
255 // Checkstyle: stop
256 static MoveOp asMoveOp(LIRInstruction op) {
257 return (MoveOp) op;
258 }
259 // Checkstyle: resume
260
261 static boolean isMoveOp(LIRInstruction op) {
262 return op.isMoveOp();
263 }
264 }
265
266 /**
267 * Marker interface for a LIR operation that moves some non-constant value to another location.
268 */
269 public interface ValueMoveOp extends MoveOp {
270
271 AllocatableValue getInput();
272
273 // Checkstyle: stop
274 static ValueMoveOp asValueMoveOp(LIRInstruction op) {
275 return (ValueMoveOp) op;
276 }
277 // Checkstyle: resume
278
279 static boolean isValueMoveOp(LIRInstruction op) {
280 return op.isValueMoveOp();
281 }
282 }
283
284 /**
285 * Marker interface for a LIR operation that loads a {@link #getConstant()}.
286 */
287 public interface LoadConstantOp extends MoveOp {
288
289 Constant getConstant();
290
291 // Checkstyle: stop
292 static LoadConstantOp asLoadConstantOp(LIRInstruction op) {
293 return (LoadConstantOp) op;
294 }
295 // Checkstyle: resume
296
297 static boolean isLoadConstantOp(LIRInstruction op) {
298 return op.isLoadConstantOp();
299 }
300 }
301
302 /**
303 * An operation that saves registers to the stack. The set of saved registers can be
304 * {@linkplain #remove(EconomicSet) pruned} and a mapping from registers to the frame slots in
305 * which they are saved can be {@linkplain #getMap(FrameMap) retrieved}.
306 */
307 public abstract static class SaveRegistersOp extends LIRInstruction {
308 public static final LIRInstructionClass<SaveRegistersOp> TYPE = LIRInstructionClass.create(SaveRegistersOp.class);
309
310 /**
311 * The registers (potentially) saved by this operation.
312 */
313 protected final Register[] savedRegisters;
314
315 /**
316 * The slots to which the registers are saved.
317 */
318 @Def(STACK) protected final AllocatableValue[] slots;
319
320 /**
321 *
322 * @param savedRegisters the registers saved by this operation which may be subject to
323 * {@linkplain #remove(EconomicSet) pruning}
324 * @param savedRegisterLocations the slots to which the registers are saved
325 */
326 protected SaveRegistersOp(LIRInstructionClass<? extends SaveRegistersOp> c, Register[] savedRegisters, AllocatableValue[] savedRegisterLocations) {
327 super(c);
328 assert Arrays.asList(savedRegisterLocations).stream().allMatch(LIRValueUtil::isVirtualStackSlot);
329 this.savedRegisters = savedRegisters;
330 this.slots = savedRegisterLocations;
331 }
332
333 /**
334 * Prunes {@code doNotSave} from the registers saved by this operation.
335 *
336 * @param doNotSave registers that should not be saved by this operation
337 * @return the number of registers pruned
338 */
339 public int remove(EconomicSet<Register> doNotSave) {
340 return prune(doNotSave, savedRegisters);
341 }
342
343 /**
344 * Gets a map from the saved registers saved by this operation to the frame slots in which
345 * they are saved.
346 *
347 * @param frameMap used to {@linkplain FrameMap#offsetForStackSlot(StackSlot) convert} a
348 * virtual slot to a frame slot index
349 */
350
351 public RegisterSaveLayout getMap(FrameMap frameMap) {
352 int total = 0;
353 for (int i = 0; i < savedRegisters.length; i++) {
354 if (savedRegisters[i] != null) {
355 total++;
356 }
357 }
358 Register[] keys = new Register[total];
359 int[] values = new int[total];
360 if (total != 0) {
361 int mapIndex = 0;
362 for (int i = 0; i < savedRegisters.length; i++) {
363 if (savedRegisters[i] != null) {
364 keys[mapIndex] = savedRegisters[i];
365 assert isStackSlot(slots[i]) : "not a StackSlot: " + slots[i];
366 StackSlot slot = asStackSlot(slots[i]);
367 values[mapIndex] = indexForStackSlot(frameMap, slot);
368 mapIndex++;
369 }
370 }
371 assert mapIndex == total;
372 }
373 return new RegisterSaveLayout(keys, values);
374 }
375
376 public Register[] getSavedRegisters() {
377 return savedRegisters;
378 }
379
380 public EconomicSet<Register> getSaveableRegisters() {
381 EconomicSet<Register> registers = EconomicSet.create(Equivalence.IDENTITY);
382 for (Register r : savedRegisters) {
383 registers.add(r);
384 }
385 return registers;
386 }
387
388 public AllocatableValue[] getSlots() {
389 return slots;
390 }
391
392 @Override
393 public abstract void emitCode(CompilationResultBuilder crb);
394
395 static int prune(EconomicSet<Register> toRemove, Register[] registers) {
396 int pruned = 0;
397 for (int i = 0; i < registers.length; i++) {
398 if (registers[i] != null) {
399 if (toRemove.contains(registers[i])) {
400 registers[i] = null;
401 pruned++;
402 }
403 }
404 }
405 return pruned;
406 }
407
408 /**
409 * Computes the index of a stack slot relative to slot 0. This is also the bit index of
410 * stack slots in the reference map.
411 *
412 * @param slot a stack slot
413 * @return the index of the stack slot
414 */
415 private static int indexForStackSlot(FrameMap frameMap, StackSlot slot) {
416 assert frameMap.offsetForStackSlot(slot) % frameMap.getTarget().wordSize == 0;
417 int value = frameMap.offsetForStackSlot(slot) / frameMap.getTarget().wordSize;
418 return value;
419 }
420 }
421
422 /**
423 * Marker interface for an operation that restores the registers saved by
424 * {@link SaveRegistersOp}.
425 */
426 public interface RestoreRegistersOp {
427 }
428
429 /**
430 * Marker interface for an operation that kills some set register and stack locations.
431 */
432 public interface ZapRegistersOp {
433 }
434
435 /**
436 * A LIR operation that does nothing. If the operation records its position, it can be
437 * subsequently {@linkplain #replace(LIR, LIRInstruction) replaced}.
438 */
439 public static final class NoOp extends LIRInstruction {
440 public static final LIRInstructionClass<NoOp> TYPE = LIRInstructionClass.create(NoOp.class);
441
442 /**
443 * The block in which this instruction is located.
444 */
445 final AbstractBlockBase<?> block;
446
447 /**
448 * The block index of this instruction.
449 */
450 final int index;
451
452 public NoOp(AbstractBlockBase<?> block, int index) {
453 super(TYPE);
454 this.block = block;
455 this.index = index;
456 }
457
458 public void replace(LIR lir, LIRInstruction replacement) {
459 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
460 assert instructions.get(index).equals(this) : String.format("Replacing the wrong instruction: %s instead of %s", instructions.get(index), this);
461 instructions.set(index, replacement);
462 }
463
464 public void remove(LIR lir) {
465 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block);
466 assert instructions.get(index).equals(this) : String.format("Removing the wrong instruction: %s instead of %s", instructions.get(index), this);
467 instructions.remove(index);
468 }
469
470 @Override
471 public void emitCode(CompilationResultBuilder crb) {
472 if (block != null) {
473 throw new GraalError(this + " should have been replaced");
474 }
475 }
476 }
477
478 @Opcode("BLACKHOLE")
479 public static final class BlackholeOp extends LIRInstruction {
480 public static final LIRInstructionClass<BlackholeOp> TYPE = LIRInstructionClass.create(BlackholeOp.class);
481
482 @Use({REG, STACK, CONST}) private Value value;
483
484 public BlackholeOp(Value value) {
485 super(TYPE);
486 this.value = value;
487 }
488
489 @Override
490 public void emitCode(CompilationResultBuilder crb) {
491 // do nothing, just keep value alive until at least here
492 }
493 }
494
495 public static final class BindToRegisterOp extends LIRInstruction {
496 public static final LIRInstructionClass<BindToRegisterOp> TYPE = LIRInstructionClass.create(BindToRegisterOp.class);
497
498 @Use({REG}) private Value value;
499
500 public BindToRegisterOp(Value value) {
501 super(TYPE);
502 this.value = value;
503 }
504
505 @Override
506 public void emitCode(CompilationResultBuilder crb) {
507 // do nothing, just keep value alive until at least here
508 }
509 }
510
511 @Opcode("SPILLREGISTERS")
512 public static final class SpillRegistersOp extends LIRInstruction {
513 public static final LIRInstructionClass<SpillRegistersOp> TYPE = LIRInstructionClass.create(SpillRegistersOp.class);
514
515 public SpillRegistersOp() {
516 super(TYPE);
517 }
518
519 @Override
520 public boolean destroysCallerSavedRegisters() {
521 return true;
522 }
523
524 @Override
525 public void emitCode(CompilationResultBuilder crb) {
526 // do nothing, just keep value alive until at least here
527 }
528 }
529
530 public static final class StackMove extends LIRInstruction implements ValueMoveOp {
531 public static final LIRInstructionClass<StackMove> TYPE = LIRInstructionClass.create(StackMove.class);
532
533 @Def({STACK, HINT}) protected AllocatableValue result;
534 @Use({STACK}) protected AllocatableValue input;
535
536 public StackMove(AllocatableValue result, AllocatableValue input) {
537 super(TYPE);
538 this.result = result;
539 this.input = input;
540 }
541
542 @Override
543 public void emitCode(CompilationResultBuilder crb) {
544 throw new GraalError(this + " should have been removed");
545 }
546
547 @Override
548 public AllocatableValue getInput() {
549 return input;
550 }
551
552 @Override
553 public AllocatableValue getResult() {
554 return result;
555 }
556 }
557
558 }