1 /*
2 * Copyright (c) 2009, 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.gen;
26
27 import static jdk.vm.ci.code.ValueUtil.asAllocatableValue;
28 import static jdk.vm.ci.code.ValueUtil.isAllocatableValue;
29 import static jdk.vm.ci.code.ValueUtil.isLegal;
30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
31 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
33 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
34 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
35
36 import java.util.ArrayList;
37 import java.util.List;
38 import java.util.Optional;
39
40 import org.graalvm.compiler.asm.Label;
41 import org.graalvm.compiler.core.common.LIRKind;
42 import org.graalvm.compiler.core.common.calc.Condition;
43 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
44 import org.graalvm.compiler.core.common.spi.CodeGenProviders;
45 import org.graalvm.compiler.core.common.spi.ForeignCallLinkage;
46 import org.graalvm.compiler.core.common.spi.ForeignCallsProvider;
47 import org.graalvm.compiler.core.common.spi.LIRKindTool;
48 import org.graalvm.compiler.core.common.type.Stamp;
49 import org.graalvm.compiler.debug.GraalError;
50 import org.graalvm.compiler.debug.TTY;
51 import org.graalvm.compiler.graph.NodeSourcePosition;
52 import org.graalvm.compiler.lir.ConstantValue;
53 import org.graalvm.compiler.lir.LIR;
54 import org.graalvm.compiler.lir.LIRFrameState;
55 import org.graalvm.compiler.lir.LIRInstruction;
56 import org.graalvm.compiler.lir.LIRVerifier;
57 import org.graalvm.compiler.lir.LabelRef;
58 import org.graalvm.compiler.lir.StandardOp;
59 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
60 import org.graalvm.compiler.lir.StandardOp.LabelOp;
61 import org.graalvm.compiler.lir.StandardOp.SaveRegistersOp;
62 import org.graalvm.compiler.lir.hashing.Hasher;
63 import org.graalvm.compiler.lir.SwitchStrategy;
64 import org.graalvm.compiler.lir.Variable;
65 import org.graalvm.compiler.options.Option;
66 import org.graalvm.compiler.options.OptionKey;
67 import org.graalvm.compiler.options.OptionType;
68 import org.graalvm.compiler.options.OptionValues;
69
70 import jdk.vm.ci.code.CallingConvention;
71 import jdk.vm.ci.code.CodeCacheProvider;
72 import jdk.vm.ci.code.Register;
73 import jdk.vm.ci.code.RegisterAttributes;
74 import jdk.vm.ci.code.RegisterConfig;
75 import jdk.vm.ci.code.StackSlot;
76 import jdk.vm.ci.code.TargetDescription;
77 import jdk.vm.ci.meta.AllocatableValue;
78 import jdk.vm.ci.meta.Constant;
79 import jdk.vm.ci.meta.JavaConstant;
80 import jdk.vm.ci.meta.JavaKind;
81 import jdk.vm.ci.meta.MetaAccessProvider;
82 import jdk.vm.ci.meta.PlatformKind;
83 import jdk.vm.ci.meta.Value;
84 import jdk.vm.ci.meta.ValueKind;
85
86 /**
87 * This class traverses the HIR instructions and generates LIR instructions from them.
88 */
89 public abstract class LIRGenerator implements LIRGeneratorTool {
90
91 public static class Options {
92 // @formatter:off
93 @Option(help = "Print HIR along side LIR as the latter is generated", type = OptionType.Debug)
94 public static final OptionKey<Boolean> PrintIRWithLIR = new OptionKey<>(false);
95 @Option(help = "The trace level for the LIR generator", type = OptionType.Debug)
96 public static final OptionKey<Integer> TraceLIRGeneratorLevel = new OptionKey<>(0);
97 // @formatter:on
98 }
99
100 private final LIRKindTool lirKindTool;
101
102 private final CodeGenProviders providers;
103
104 private AbstractBlockBase<?> currentBlock;
105
106 private LIRGenerationResult res;
107
108 protected final ArithmeticLIRGenerator arithmeticLIRGen;
109 private final MoveFactory moveFactory;
110
111 private final boolean printIrWithLir;
112 private final int traceLIRGeneratorLevel;
113
114 public LIRGenerator(LIRKindTool lirKindTool, ArithmeticLIRGenerator arithmeticLIRGen, MoveFactory moveFactory, CodeGenProviders providers, LIRGenerationResult res) {
115 this.lirKindTool = lirKindTool;
116 this.arithmeticLIRGen = arithmeticLIRGen;
117 this.res = res;
118 this.providers = providers;
119 OptionValues options = res.getLIR().getOptions();
120 this.printIrWithLir = !TTY.isSuppressed() && Options.PrintIRWithLIR.getValue(options);
121 this.traceLIRGeneratorLevel = TTY.isSuppressed() ? 0 : Options.TraceLIRGeneratorLevel.getValue(options);
122
123 assert arithmeticLIRGen.lirGen == null;
124 arithmeticLIRGen.lirGen = this;
125 this.moveFactory = moveFactory;
126 }
127
128 @Override
129 public ArithmeticLIRGeneratorTool getArithmetic() {
130 return arithmeticLIRGen;
131 }
132
133 @Override
134 public MoveFactory getMoveFactory() {
135 return moveFactory;
136 }
137
138 private MoveFactory spillMoveFactory;
139
140 @Override
141 public MoveFactory getSpillMoveFactory() {
142 if (spillMoveFactory == null) {
143 boolean verify = false;
144 assert (verify = true) == true;
145 if (verify) {
146 spillMoveFactory = new VerifyingMoveFactory(moveFactory);
147 } else {
148 spillMoveFactory = moveFactory;
149 }
150 }
151 return spillMoveFactory;
152 }
153
154 @Override
155 public LIRKind getValueKind(JavaKind javaKind) {
156 return LIRKind.fromJavaKind(target().arch, javaKind);
157 }
158
159 @Override
160 public TargetDescription target() {
161 return getCodeCache().getTarget();
162 }
163
164 @Override
165 public CodeGenProviders getProviders() {
166 return providers;
167 }
168
169 @Override
170 public MetaAccessProvider getMetaAccess() {
171 return providers.getMetaAccess();
172 }
173
174 @Override
175 public CodeCacheProvider getCodeCache() {
176 return providers.getCodeCache();
177 }
178
179 @Override
180 public ForeignCallsProvider getForeignCalls() {
181 return providers.getForeignCalls();
182 }
183
184 public LIRKindTool getLIRKindTool() {
185 return lirKindTool;
186 }
187
188 /**
189 * Hide {@link #nextVariable()} from other users.
190 */
191 public abstract static class VariableProvider {
192 private int numVariables;
193
194 public int numVariables() {
195 return numVariables;
196 }
197
198 private int nextVariable() {
199 return numVariables++;
200 }
201 }
202
203 @Override
204 public Variable newVariable(ValueKind<?> valueKind) {
205 return new Variable(valueKind, ((VariableProvider) res.getLIR()).nextVariable());
206 }
207
208 @Override
209 public RegisterConfig getRegisterConfig() {
210 return res.getRegisterConfig();
211 }
212
213 @Override
214 public RegisterAttributes attributes(Register register) {
215 return getRegisterConfig().getAttributesMap()[register.number];
216 }
217
218 @Override
219 public Variable emitMove(Value input) {
220 assert !(input instanceof Variable) : "Creating a copy of a variable via this method is not supported (and potentially a bug): " + input;
221 Variable result = newVariable(input.getValueKind());
222 emitMove(result, input);
223 return result;
224 }
225
226 @Override
227 public void emitMove(AllocatableValue dst, Value src) {
228 append(moveFactory.createMove(dst, src));
229 }
230
231 @Override
232 public void emitMoveConstant(AllocatableValue dst, Constant src) {
233 append(moveFactory.createLoad(dst, src));
234 }
235
236 @Override
237 public Value emitConstant(LIRKind kind, Constant constant) {
238 if (moveFactory.canInlineConstant(constant)) {
239 return new ConstantValue(toRegisterKind(kind), constant);
240 } else {
241 return emitLoadConstant(toRegisterKind(kind), constant);
242 }
243 }
244
245 @Override
246 public Value emitJavaConstant(JavaConstant constant) {
247 return emitConstant(getValueKind(constant.getJavaKind()), constant);
248 }
249
250 @Override
251 public AllocatableValue emitLoadConstant(ValueKind<?> kind, Constant constant) {
252 Variable result = newVariable(kind);
253 emitMoveConstant(result, constant);
254 return result;
255 }
256
257 @Override
258 public AllocatableValue asAllocatable(Value value) {
259 if (isAllocatableValue(value)) {
260 return asAllocatableValue(value);
261 } else if (isConstantValue(value)) {
262 return emitLoadConstant(value.getValueKind(), asConstant(value));
263 } else {
264 return emitMove(value);
265 }
266 }
267
268 @Override
269 public Variable load(Value value) {
270 if (!isVariable(value)) {
271 return emitMove(value);
272 }
273 return (Variable) value;
274 }
275
276 @Override
277 public Value loadNonConst(Value value) {
278 if (isConstantValue(value) && !moveFactory.canInlineConstant(asConstant(value))) {
279 return emitMove(value);
280 }
281 return value;
282 }
283
284 /**
285 * Determines if only oop maps are required for the code generated from the LIR.
286 */
287 @Override
288 public boolean needOnlyOopMaps() {
289 return false;
290 }
291
292 /**
293 * Gets the ABI specific operand used to return a value of a given kind from a method.
294 *
295 * @param javaKind the kind of value being returned
296 * @param valueKind the backend type of the value being returned
297 * @return the operand representing the ABI defined location used return a value of kind
298 * {@code kind}
299 */
300 @Override
301 public AllocatableValue resultOperandFor(JavaKind javaKind, ValueKind<?> valueKind) {
302 Register reg = getRegisterConfig().getReturnRegister(javaKind);
303 assert target().arch.canStoreValue(reg.getRegisterCategory(), valueKind.getPlatformKind()) : reg.getRegisterCategory() + " " + valueKind.getPlatformKind();
304 return reg.asValue(valueKind);
305 }
306
307 NodeSourcePosition currentPosition;
308
309 @Override
310 public void setSourcePosition(NodeSourcePosition position) {
311 currentPosition = position;
312 }
313
314 @Override
315 public <I extends LIRInstruction> I append(I op) {
316 LIR lir = res.getLIR();
317 if (printIrWithLir) {
318 TTY.println(op.toStringWithIdPrefix());
319 TTY.println();
320 }
321 assert LIRVerifier.verify(op);
322 ArrayList<LIRInstruction> lirForBlock = lir.getLIRforBlock(getCurrentBlock());
323 op.setPosition(currentPosition);
324 lirForBlock.add(op);
325 return op;
326 }
327
328 @Override
329 public boolean hasBlockEnd(AbstractBlockBase<?> block) {
330 ArrayList<LIRInstruction> ops = getResult().getLIR().getLIRforBlock(block);
331 if (ops.size() == 0) {
332 return false;
333 }
334 return ops.get(ops.size() - 1) instanceof BlockEndOp;
335 }
336
337 private final class BlockScopeImpl extends BlockScope {
338
339 private BlockScopeImpl(AbstractBlockBase<?> block) {
340 currentBlock = block;
341 }
342
343 private void doBlockStart() {
344 if (printIrWithLir) {
345 TTY.print(currentBlock.toString());
346 }
347
348 // set up the list of LIR instructions
349 assert res.getLIR().getLIRforBlock(currentBlock) == null : "LIR list already computed for this block";
350 res.getLIR().setLIRforBlock(currentBlock, new ArrayList<LIRInstruction>());
351
352 append(new LabelOp(new Label(currentBlock.getId()), currentBlock.isAligned()));
353
354 if (traceLIRGeneratorLevel >= 1) {
355 TTY.println("BEGIN Generating LIR for block B" + currentBlock.getId());
356 }
357 }
358
359 private void doBlockEnd() {
360 if (traceLIRGeneratorLevel >= 1) {
361 TTY.println("END Generating LIR for block B" + currentBlock.getId());
362 }
363
364 if (printIrWithLir) {
365 TTY.println();
366 }
367 currentBlock = null;
368 }
369
370 @Override
371 public AbstractBlockBase<?> getCurrentBlock() {
372 return currentBlock;
373 }
374
375 @Override
376 public void close() {
377 doBlockEnd();
378 }
379
380 }
381
382 @Override
383 public final BlockScope getBlockScope(AbstractBlockBase<?> block) {
384 BlockScopeImpl blockScope = new BlockScopeImpl(block);
385 blockScope.doBlockStart();
386 return blockScope;
387 }
388
389 @Override
390 public void emitIncomingValues(Value[] params) {
391 ((LabelOp) res.getLIR().getLIRforBlock(getCurrentBlock()).get(0)).setIncomingValues(params);
392 }
393
394 @Override
395 public abstract void emitJump(LabelRef label);
396
397 @Override
398 public abstract void emitCompareBranch(PlatformKind cmpKind, Value left, Value right, Condition cond, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination,
399 double trueDestinationProbability);
400
401 @Override
402 public abstract void emitOverflowCheckBranch(LabelRef overflow, LabelRef noOverflow, LIRKind cmpKind, double overflowProbability);
403
404 @Override
405 public abstract void emitIntegerTestBranch(Value left, Value right, LabelRef trueDestination, LabelRef falseDestination, double trueSuccessorProbability);
406
407 @Override
408 public abstract Variable emitConditionalMove(PlatformKind cmpKind, Value leftVal, Value right, Condition cond, boolean unorderedIsTrue, Value trueValue, Value falseValue);
409
410 @Override
411 public abstract Variable emitIntegerTestMove(Value leftVal, Value right, Value trueValue, Value falseValue);
412
413 /**
414 * Emits the single call operation at the heart of generating LIR for a
415 * {@linkplain #emitForeignCall(ForeignCallLinkage, LIRFrameState, Value...) foreign call}.
416 */
417 protected abstract void emitForeignCallOp(ForeignCallLinkage linkage, Value result, Value[] arguments, Value[] temps, LIRFrameState info);
418
419 @Override
420 public Variable emitForeignCall(ForeignCallLinkage linkage, LIRFrameState frameState, Value... args) {
421 LIRFrameState state = null;
422 if (linkage.needsDebugInfo()) {
423 if (frameState != null) {
424 state = frameState;
425 } else {
426 assert needOnlyOopMaps();
427 state = new LIRFrameState(null, null, null);
428 }
429 }
430
431 // move the arguments into the correct location
432 CallingConvention linkageCc = linkage.getOutgoingCallingConvention();
433 res.getFrameMapBuilder().callsMethod(linkageCc);
434 assert linkageCc.getArgumentCount() == args.length : "argument count mismatch";
435 Value[] argLocations = new Value[args.length];
436 for (int i = 0; i < args.length; i++) {
437 Value arg = args[i];
438 AllocatableValue loc = linkageCc.getArgument(i);
439 emitMove(loc, arg);
440 argLocations[i] = loc;
441 }
442 res.setForeignCall(true);
443 emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
444
445 if (isLegal(linkageCc.getReturn())) {
446 return emitMove(linkageCc.getReturn());
447 } else {
448 return null;
449 }
450 }
451
452 @Override
453 public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
454 SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
455
456 int keyCount = keyConstants.length;
457 double minDensity = 1 / Math.sqrt(strategy.getAverageEffort());
458 Optional<Hasher> hasher = hasherFor(keyConstants, minDensity);
459 double hashTableSwitchDensity = hasher.map(h -> keyCount / (double) h.cardinality()).orElse(0d);
460 long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
461 double tableSwitchDensity = keyCount / (double) valueRange;
462
463 /*
464 * This heuristic tries to find a compromise between the effort for the best switch strategy
465 * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
466 * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
467 * gradually with additional effort.
468 */
469 if (strategy.getAverageEffort() < 4d || (tableSwitchDensity < minDensity && hashTableSwitchDensity < minDensity)) {
470 emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
471 } else {
472 if (hashTableSwitchDensity > tableSwitchDensity) {
473 Hasher h = hasher.get();
474 int cardinality = h.cardinality();
475 LabelRef[] targets = new LabelRef[cardinality];
476 JavaConstant[] keys = new JavaConstant[cardinality];
477 for (int i = 0; i < cardinality; i++) {
478 keys[i] = JavaConstant.INT_0;
479 targets[i] = defaultTarget;
480 }
481 for (int i = 0; i < keyCount; i++) {
482 int idx = h.hash(keyConstants[i].asLong());
483 keys[idx] = keyConstants[i];
484 targets[idx] = keyTargets[i];
485 }
486 emitHashTableSwitch(h, keys, defaultTarget, targets, value);
487 } else {
488 int minValue = keyConstants[0].asInt();
489 assert valueRange < Integer.MAX_VALUE;
490 LabelRef[] targets = new LabelRef[(int) valueRange];
491 for (int i = 0; i < valueRange; i++) {
492 targets[i] = defaultTarget;
493 }
494 for (int i = 0; i < keyCount; i++) {
495 targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
496 }
497 emitTableSwitch(minValue, defaultTarget, targets, value);
498 }
499 }
500 }
501
502 @Override
503 public abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget);
504
505 protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key);
506
507 @SuppressWarnings("unused")
508 protected Optional<Hasher> hasherFor(JavaConstant[] keyConstants, double minDensity) {
509 return Optional.empty();
510 }
511
512 @SuppressWarnings("unused")
513 protected void emitHashTableSwitch(Hasher hasher, JavaConstant[] keys, LabelRef defaultTarget, LabelRef[] targets, Value value) {
514 throw new UnsupportedOperationException(getClass().getSimpleName() + " doesn't support hash table switches");
515 }
516
517 @Override
518 public void beforeRegisterAllocation() {
519 }
520
521 /**
522 * Gets a garbage value for a given kind.
523 */
524 protected abstract JavaConstant zapValueForKind(PlatformKind kind);
525
526 @Override
527 public LIRKind getLIRKind(Stamp stamp) {
528 return stamp.getLIRKind(lirKindTool);
529 }
530
531 protected LIRKind getAddressKind(Value base, long displacement, Value index) {
532 if (LIRKind.isValue(base) && (index.equals(Value.ILLEGAL) || LIRKind.isValue(index))) {
533 return LIRKind.value(target().arch.getWordKind());
534 } else if (base.getValueKind() instanceof LIRKind && base.getValueKind(LIRKind.class).isReference(0) && displacement == 0L && index.equals(Value.ILLEGAL)) {
535 return LIRKind.reference(target().arch.getWordKind());
536 } else {
537 return LIRKind.unknownReference(target().arch.getWordKind());
538 }
539 }
540
541 @Override
542 public AbstractBlockBase<?> getCurrentBlock() {
543 return currentBlock;
544 }
545
546 @Override
547 public LIRGenerationResult getResult() {
548 return res;
549 }
550
551 @Override
552 public void emitBlackhole(Value operand) {
553 append(new StandardOp.BlackholeOp(operand));
554 }
555
556 @Override
557 public LIRInstruction createBenchmarkCounter(String name, String group, Value increment) {
558 throw GraalError.unimplemented();
559 }
560
561 @Override
562 public LIRInstruction createMultiBenchmarkCounter(String[] names, String[] groups, Value[] increments) {
563 throw GraalError.unimplemented();
564 }
565
566 @Override
567 public abstract SaveRegistersOp createZapRegisters(Register[] zappedRegisters, JavaConstant[] zapValues);
568
569 @Override
570 public SaveRegistersOp createZapRegisters() {
571 Register[] zappedRegisters = getResult().getFrameMap().getRegisterConfig().getAllocatableRegisters().toArray();
572 JavaConstant[] zapValues = new JavaConstant[zappedRegisters.length];
573 for (int i = 0; i < zappedRegisters.length; i++) {
574 PlatformKind kind = target().arch.getLargestStorableKind(zappedRegisters[i].getRegisterCategory());
575 zapValues[i] = zapValueForKind(kind);
576 }
577 return createZapRegisters(zappedRegisters, zapValues);
578 }
579
580 @Override
581 public abstract LIRInstruction createZapArgumentSpace(StackSlot[] zappedStack, JavaConstant[] zapValues);
582
583 @Override
584 public LIRInstruction zapArgumentSpace() {
585 List<StackSlot> slots = null;
586 for (AllocatableValue arg : res.getCallingConvention().getArguments()) {
587 if (isStackSlot(arg)) {
588 if (slots == null) {
589 slots = new ArrayList<>();
590 }
591 slots.add((StackSlot) arg);
592 } else {
593 assert !isVirtualStackSlot(arg);
594 }
595 }
596 if (slots == null) {
597 return null;
598 }
599 StackSlot[] zappedStack = slots.toArray(new StackSlot[slots.size()]);
600 JavaConstant[] zapValues = new JavaConstant[zappedStack.length];
601 for (int i = 0; i < zappedStack.length; i++) {
602 PlatformKind kind = zappedStack[i].getPlatformKind();
603 zapValues[i] = zapValueForKind(kind);
604 }
605 return createZapArgumentSpace(zappedStack, zapValues);
606 }
607 }