< prev index next >
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/gen/LIRGenerator.java
Print this page
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2019, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
@@ -33,12 +33,12 @@
import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
import java.util.ArrayList;
import java.util.List;
+import java.util.Optional;
-import jdk.vm.ci.code.RegisterConfig;
import org.graalvm.compiler.asm.Label;
import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.core.common.calc.Condition;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.spi.CodeGenProviders;
@@ -57,10 +57,11 @@
import org.graalvm.compiler.lir.LabelRef;
import org.graalvm.compiler.lir.StandardOp;
import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
import org.graalvm.compiler.lir.StandardOp.LabelOp;
import org.graalvm.compiler.lir.StandardOp.SaveRegistersOp;
+import org.graalvm.compiler.lir.hashing.Hasher;
import org.graalvm.compiler.lir.SwitchStrategy;
import org.graalvm.compiler.lir.Variable;
import org.graalvm.compiler.options.Option;
import org.graalvm.compiler.options.OptionKey;
import org.graalvm.compiler.options.OptionType;
@@ -68,10 +69,11 @@
import jdk.vm.ci.code.CallingConvention;
import jdk.vm.ci.code.CodeCacheProvider;
import jdk.vm.ci.code.Register;
import jdk.vm.ci.code.RegisterAttributes;
+import jdk.vm.ci.code.RegisterConfig;
import jdk.vm.ci.code.StackSlot;
import jdk.vm.ci.code.TargetDescription;
import jdk.vm.ci.meta.AllocatableValue;
import jdk.vm.ci.meta.Constant;
import jdk.vm.ci.meta.JavaConstant;
@@ -447,41 +449,73 @@
}
}
@Override
public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
- int keyCount = keyConstants.length;
SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
+
+ int keyCount = keyConstants.length;
+ double minDensity = 1 / Math.sqrt(strategy.getAverageEffort());
+ Optional<Hasher> hasher = hasherFor(keyConstants, minDensity);
+ double hashTableSwitchDensity = hasher.map(h -> keyCount / (double) h.cardinality()).orElse(0d);
long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
double tableSwitchDensity = keyCount / (double) valueRange;
+
/*
* This heuristic tries to find a compromise between the effort for the best switch strategy
* and the density of a tableswitch. If the effort for the strategy is at least 4, then a
* tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
* gradually with additional effort.
*/
- if (strategy.getAverageEffort() < 4 || tableSwitchDensity < (1 / Math.sqrt(strategy.getAverageEffort()))) {
+ if (strategy.getAverageEffort() < 4d || (tableSwitchDensity < minDensity && hashTableSwitchDensity < minDensity)) {
emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
} else {
- int minValue = keyConstants[0].asInt();
- assert valueRange < Integer.MAX_VALUE;
- LabelRef[] targets = new LabelRef[(int) valueRange];
- for (int i = 0; i < valueRange; i++) {
- targets[i] = defaultTarget;
- }
- for (int i = 0; i < keyCount; i++) {
- targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
+ if (hashTableSwitchDensity > tableSwitchDensity) {
+ Hasher h = hasher.get();
+ int cardinality = h.cardinality();
+ LabelRef[] targets = new LabelRef[cardinality];
+ JavaConstant[] keys = new JavaConstant[cardinality];
+ for (int i = 0; i < cardinality; i++) {
+ keys[i] = JavaConstant.INT_0;
+ targets[i] = defaultTarget;
+ }
+ for (int i = 0; i < keyCount; i++) {
+ int idx = h.hash(keyConstants[i].asLong());
+ keys[idx] = keyConstants[i];
+ targets[idx] = keyTargets[i];
+ }
+ emitHashTableSwitch(h, keys, defaultTarget, targets, value);
+ } else {
+ int minValue = keyConstants[0].asInt();
+ assert valueRange < Integer.MAX_VALUE;
+ LabelRef[] targets = new LabelRef[(int) valueRange];
+ for (int i = 0; i < valueRange; i++) {
+ targets[i] = defaultTarget;
+ }
+ for (int i = 0; i < keyCount; i++) {
+ targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
+ }
+ emitTableSwitch(minValue, defaultTarget, targets, value);
}
- emitTableSwitch(minValue, defaultTarget, targets, value);
}
}
@Override
public abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget);
protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key);
+ @SuppressWarnings("unused")
+ protected Optional<Hasher> hasherFor(JavaConstant[] keyConstants, double minDensity) {
+ return Optional.empty();
+ }
+
+ @SuppressWarnings("unused")
+ protected void emitHashTableSwitch(Hasher hasher, JavaConstant[] keys, LabelRef defaultTarget, LabelRef[] targets, Value value) {
+ throw new UnsupportedOperationException(getClass().getSimpleName() + " doesn't support hash table switches");
+ }
+
@Override
public void beforeRegisterAllocation() {
}
/**
< prev index next >