# HG changeset patch # User Lukas Stadler # Date 1386868522 -3600 # Node ID 094f4ee9397760590ccf120f3579182a4c81d7e9 # Parent 126ef8e8aa59886ff7d2f8caeb0604c98af2b5b1 some javadoc for switch strategies diff -r 126ef8e8aa59 -r 094f4ee93977 graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java --- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Thu Dec 12 17:09:40 2013 +0100 +++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Thu Dec 12 18:15:22 2013 +0100 @@ -981,6 +981,7 @@ @Override protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { + // a temp is needed for loading object constants boolean needsTemp = key.getKind() == Kind.Object; append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key, needsTemp ? newVariable(key.getKind()) : Value.ILLEGAL)); } diff -r 126ef8e8aa59 -r 094f4ee93977 graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java --- a/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Thu Dec 12 17:09:40 2013 +0100 +++ b/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Thu Dec 12 18:15:22 2013 +0100 @@ -359,6 +359,7 @@ @Override protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { + // a temp is needed for loading long and object constants boolean needsTemp = key.getKind() == Kind.Long || key.getKind() == Kind.Object; append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key, needsTemp ? newVariable(key.getKind()) : Value.ILLEGAL)); } diff -r 126ef8e8aa59 -r 094f4ee93977 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java Thu Dec 12 17:09:40 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java Thu Dec 12 18:15:22 2013 +0100 @@ -29,6 +29,14 @@ import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; +/** + * This class encapsulates different strategies on how to generate code for switch instructions. + * + * The {@link #getBestStrategy(double[], Constant[], LabelRef[])} method can be used to get strategy + * with the smallest average effort (average number of comparisons until a decision is reached). The + * strategy returned by this method will have its averageEffort set, while a strategy constructed + * directly will not. + */ public abstract class SwitchStrategy { private interface SwitchClosure { @@ -75,7 +83,8 @@ } /** - * Backends can subclass this abstract class to generate code for switch strategies. + * Backends can subclass this abstract class and generate code for switch strategies by + * implementing the {@link #conditionalJump(int, Condition, Label)} method. */ public abstract static class BaseSwitchClosure implements SwitchClosure { @@ -133,6 +142,10 @@ } + /** + * This closure is used internally to determine the average effort for a certain strategy on a + * given switch instruction. + */ private class EffortClosure implements SwitchClosure { private int defaultEffort; @@ -189,11 +202,11 @@ } public double getAverageEffort() { - assert averageEffort >= 0; + assert averageEffort >= 0 : "average effort was not calculated yet for this strategy"; return averageEffort; } - /* + /** * Looks for the end of a stretch of key constants that are successive numbers and have the same * target. */ @@ -205,6 +218,10 @@ return slice; } + /** + * Tells the system that the given (inclusive) range of keys is reached after depth number of + * comparisons, which is used to calculate the average effort. + */ protected void registerEffort(int rangeStart, int rangeEnd, int depth) { if (effortClosure != null) { for (int i = rangeStart; i <= rangeEnd; i++) { @@ -214,6 +231,10 @@ } } + /** + * Tells the system that the default successor is reached after depth number of comparisons, + * which is used to calculate average effort. + */ protected void registerDefaultEffort(int depth) { if (effortClosure != null) { effortClosure.defaultEffort += depth; @@ -226,6 +247,10 @@ return getClass().getSimpleName() + "[avgEffort=" + averageEffort + "]"; } + /** + * This strategy orders the keys according to their probability and creates one equality + * comparison per key. + */ public static class SequentialStrategy extends SwitchStrategy { private final Integer[] indexes; @@ -257,6 +282,10 @@ } } + /** + * This strategy divides the keys into ranges of successive keys with the same target and + * creates comparisons for these ranges. + */ public static class RangesStrategy extends SwitchStrategy { private final Integer[] indexes; @@ -314,6 +343,10 @@ } } + /** + * This strategy recursively subdivides the list of keys to create a binary search based on + * probabilities. + */ public static class BinaryStrategy extends SwitchStrategy { private static final double MIN_PROBABILITY = 0.00001; @@ -336,8 +369,10 @@ } /** - * Recursively generate a list of comparisons that always subdivides the key list in the - * middle (in terms of probability, not index). + * Recursively generate a list of comparisons that always subdivides the keys in the given + * (inclusive) range in the middle (in terms of probability, not index). If left is bigger + * than zero, then we always know that the value is equal to or bigger than the left key. + * This does not hold for the right key, as there may be a gap afterwards. */ private void recurseBinarySwitch(SwitchClosure closure, int left, int right, int startDepth) { assert startDepth < keyConstants.length * 3 : "runaway recursion in binary switch"; @@ -354,6 +389,7 @@ registerEffort(right, right, ++depth); registerDefaultEffort(depth); } else { + // here we know that the value can only be one of these two keys in the range closure.conditionalJump(left, Condition.EQ, false); registerEffort(left, left, ++depth); closure.conditionalJump(right, null, false); @@ -433,6 +469,10 @@ return strategies; } + /** + * Creates all switch strategies for the given switch, evaluates them (based on average effort) + * and returns the best one. + */ public static SwitchStrategy getBestStrategy(double[] keyProbabilities, Constant[] keyConstants, LabelRef[] keyTargets) { SwitchStrategy[] strategies = getStrategies(keyProbabilities, keyConstants, keyTargets); double bestEffort = Integer.MAX_VALUE; diff -r 126ef8e8aa59 -r 094f4ee93977 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Thu Dec 12 17:09:40 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Thu Dec 12 18:15:22 2013 +0100 @@ -47,7 +47,7 @@ */ public SwitchNode(ValueNode value, AbstractBeginNode[] successors, int[] keySuccessors, double[] keyProbabilities) { super(StampFactory.forVoid()); - assert value.kind() == Kind.Int || value.kind() == Kind.Long || value.kind() == Kind.Object; + assert value.kind() == Kind.Int || value.kind() == Kind.Long || value.kind() == Kind.Object : value.kind() + " key not supported by SwitchNode"; assert keySuccessors.length == keyProbabilities.length; this.successors = new NodeSuccessorList<>(this, successors); this.value = value;