1 /*
2 * Copyright (c) 2009, 2018, 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
39 import jdk.vm.ci.code.RegisterConfig;
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.SwitchStrategy;
63 import org.graalvm.compiler.lir.Variable;
64 import org.graalvm.compiler.options.Option;
65 import org.graalvm.compiler.options.OptionKey;
66 import org.graalvm.compiler.options.OptionType;
67 import org.graalvm.compiler.options.OptionValues;
68
69 import jdk.vm.ci.code.CallingConvention;
70 import jdk.vm.ci.code.CodeCacheProvider;
71 import jdk.vm.ci.code.Register;
72 import jdk.vm.ci.code.RegisterAttributes;
73 import jdk.vm.ci.code.StackSlot;
74 import jdk.vm.ci.code.TargetDescription;
75 import jdk.vm.ci.meta.AllocatableValue;
76 import jdk.vm.ci.meta.Constant;
77 import jdk.vm.ci.meta.JavaConstant;
78 import jdk.vm.ci.meta.JavaKind;
79 import jdk.vm.ci.meta.MetaAccessProvider;
80 import jdk.vm.ci.meta.PlatformKind;
81 import jdk.vm.ci.meta.Value;
82 import jdk.vm.ci.meta.ValueKind;
83
84 /**
85 * This class traverses the HIR instructions and generates LIR instructions from them.
86 */
87 public abstract class LIRGenerator implements LIRGeneratorTool {
88
89 public static class Options {
90 // @formatter:off
91 @Option(help = "Print HIR along side LIR as the latter is generated", type = OptionType.Debug)
92 public static final OptionKey<Boolean> PrintIRWithLIR = new OptionKey<>(false);
432 assert linkageCc.getArgumentCount() == args.length : "argument count mismatch";
433 Value[] argLocations = new Value[args.length];
434 for (int i = 0; i < args.length; i++) {
435 Value arg = args[i];
436 AllocatableValue loc = linkageCc.getArgument(i);
437 emitMove(loc, arg);
438 argLocations[i] = loc;
439 }
440 res.setForeignCall(true);
441 emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
442
443 if (isLegal(linkageCc.getReturn())) {
444 return emitMove(linkageCc.getReturn());
445 } else {
446 return null;
447 }
448 }
449
450 @Override
451 public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
452 int keyCount = keyConstants.length;
453 SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
454 long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
455 double tableSwitchDensity = keyCount / (double) valueRange;
456 /*
457 * This heuristic tries to find a compromise between the effort for the best switch strategy
458 * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
459 * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
460 * gradually with additional effort.
461 */
462 if (strategy.getAverageEffort() < 4 || tableSwitchDensity < (1 / Math.sqrt(strategy.getAverageEffort()))) {
463 emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
464 } else {
465 int minValue = keyConstants[0].asInt();
466 assert valueRange < Integer.MAX_VALUE;
467 LabelRef[] targets = new LabelRef[(int) valueRange];
468 for (int i = 0; i < valueRange; i++) {
469 targets[i] = defaultTarget;
470 }
471 for (int i = 0; i < keyCount; i++) {
472 targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
473 }
474 emitTableSwitch(minValue, defaultTarget, targets, value);
475 }
476 }
477
478 @Override
479 public abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget);
480
481 protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key);
482
483 @Override
484 public void beforeRegisterAllocation() {
485 }
486
487 /**
488 * Gets a garbage value for a given kind.
489 */
490 protected abstract JavaConstant zapValueForKind(PlatformKind kind);
491
492 @Override
493 public LIRKind getLIRKind(Stamp stamp) {
494 return stamp.getLIRKind(lirKindTool);
495 }
496
497 protected LIRKind getAddressKind(Value base, long displacement, Value index) {
498 if (LIRKind.isValue(base) && (index.equals(Value.ILLEGAL) || LIRKind.isValue(index))) {
499 return LIRKind.value(target().arch.getWordKind());
500 } else if (base.getValueKind() instanceof LIRKind && base.getValueKind(LIRKind.class).isReference(0) && displacement == 0L && index.equals(Value.ILLEGAL)) {
501 return LIRKind.reference(target().arch.getWordKind());
|
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);
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());
|