truffle: graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java comparison

comparison graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java @ 13302:094f4ee93977

some javadoc for switch strategies

author	Lukas Stadler <lukas.stadler@jku.at>
date	Thu, 12 Dec 2013 18:15:22 +0100
parents	d5e65a244f7d
children	da0851712519

comparison

equal deleted inserted replaced

-:126ef8e8aa59
+:094f4ee93977
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.asm.*;
 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 {
 /**
 * Generates a conditional or unconditional jump. The jump will be unconditional if
 */
 boolean isSameTarget(int index1, int index2);
 }
 /**
-* 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 {
 private final CompilationResultBuilder crb;
 private final AbstractAssembler masm;
 return keyTargets[index1] == keyTargets[index2];
 }
 }
+/**
+* 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;
 private int defaultCount;
 private final int[] keyEfforts = new int[keyConstants.length];
 this.keyProbabilities = keyProbabilities;
 this.keyConstants = keyConstants;
 }
 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.
 */
 protected int getSliceEnd(SwitchClosure closure, int pos) {
 int slice = pos;
 slice++;
 }
 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++) {
 effortClosure.keyEfforts[i] += depth;
 effortClosure.keyCounts[i]++;
 }
 }
 }
+/**
+* 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;
 effortClosure.defaultCount++;
 }
 @Override
 public String toString() {
 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;
 public SequentialStrategy(final double[] keyProbabilities, Constant[] keyConstants) {
 super(keyProbabilities, keyConstants);
 registerEffort(indexes[keyConstants.length - 1], indexes[keyConstants.length - 1], keyConstants.length);
 registerDefaultEffort(keyConstants.length);
 }
 }
+/**
+* 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;
 public RangesStrategy(final double[] keyProbabilities, Constant[] keyConstants) {
 super(keyProbabilities, keyConstants);
 registerDefaultEffort(depth);
 }
 }
 }
+/**
+* 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;
 private final double[] probabilitySums;
 public void run(SwitchClosure closure) {
 recurseBinarySwitch(closure, 0, keyConstants.length - 1, 0);
 }
 /**
-* Recursively generate a list of comparisons that always subdivides the key list in the
+* Recursively generate a list of comparisons that always subdivides the keys in the given
-* middle (in terms of probability, not index).
+* (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";
 int depth = startDepth;
 boolean leftBorder = left == 0;
 registerEffort(left, left, ++depth);
 closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder);
 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);
 registerEffort(right, right, depth);
 }
 strategy.effortClosure = null;
 }
 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;
 SwitchStrategy bestStrategy = null;
 for (SwitchStrategy strategy : strategies) {

Mercurial > hg > truffle

comparison graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java @ 13302:094f4ee93977