< 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 ****
/*
! * Copyright (c) 2009, 2018, 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.
--- 1,7 ----
/*
! * 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,44 ****
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 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;
--- 33,44 ----
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 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,66 ****
--- 57,67 ----
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,77 ****
--- 69,79 ----
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,487 ****
}
}
@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);
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()))) {
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];
}
- 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);
@Override
public void beforeRegisterAllocation() {
}
/**
--- 449,521 ----
}
}
@Override
public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
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() < 4d || (tableSwitchDensity < minDensity && hashTableSwitchDensity < minDensity)) {
emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
} else {
! 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);
}
}
}
@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 >