hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/SwitchStrategy.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2013, 2015, 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.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package org.graalvm.compiler.lir;

 import java.util.Arrays;
 import java.util.Comparator;

 import org.graalvm.compiler.asm.Assembler;
 import org.graalvm.compiler.asm.Label;
 import org.graalvm.compiler.core.common.calc.Condition;
 import org.graalvm.compiler.lir.asm.CompilationResultBuilder;

 import jdk.vm.ci.meta.Constant;
 import jdk.vm.ci.meta.JavaConstant;

 /**
  * This class encapsulates different strategies on how to generate code for switch instructions.
  *
  * The {@link #getBestStrategy(double[], JavaConstant[], 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
          * condition is null. If defaultTarget is true, then the jump will go the the default.
          *
          * @param index Index of the value and the jump target (only used if defaultTarget == false)
          * @param condition The condition on which to jump (can be null)
          * @param defaultTarget true if the jump should go to the default target, false if index
          *            should be used.
          */
         void conditionalJump(int index, Condition condition, boolean defaultTarget);

         /**
          * Generates a conditional jump to the target with the specified index. The fall through
          * should go to the default target.
          *
          * @param index Index of the value and the jump target
          * @param condition The condition on which to jump
          * @param canFallThrough true if this is the last instruction in the switch statement, to
          *            allow for fall-through optimizations.
          */
         void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough);

         /**
          * Create a new label and generate a conditional jump to it.
          *
          * @param index Index of the value and the jump target
          * @param condition The condition on which to jump
          * @return a new Label
          */
         Label conditionalJump(int index, Condition condition);

         /**
          * Binds a label returned by {@link #conditionalJump(int, Condition)}.
          */
         void bind(Label label);

         /**
          * Return true iff the target of both indexes is the same.
          */
         boolean isSameTarget(int index1, int index2);
     }

     /**
      * 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 Assembler masm;
         private final LabelRef[] keyTargets;
         private final LabelRef defaultTarget;

         public BaseSwitchClosure(CompilationResultBuilder crb, Assembler masm, LabelRef[] keyTargets, LabelRef defaultTarget) {
             this.crb = crb;
             this.masm = masm;
             this.keyTargets = keyTargets;
             this.defaultTarget = defaultTarget;
         }

         /**
          * This method generates code for a comparison between the actual value and the constant at
          * the given index and a condition jump to target.
          */
         protected abstract void conditionalJump(int index, Condition condition, Label target);

         @Override
         public void conditionalJump(int index, Condition condition, boolean targetDefault) {
             Label target = targetDefault ? defaultTarget.label() : keyTargets[index].label();
             if (condition == null) {
                 masm.jmp(target);
             } else {
                 conditionalJump(index, condition, target);
             }
         }

         @Override
         public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
             if (canFallThrough && crb.isSuccessorEdge(defaultTarget)) {
                 conditionalJump(index, condition, keyTargets[index].label());
             } else if (canFallThrough && crb.isSuccessorEdge(keyTargets[index])) {
                 conditionalJump(index, condition.negate(), defaultTarget.label());
             } else {
                 conditionalJump(index, condition, keyTargets[index].label());
                 masm.jmp(defaultTarget.label());
             }
         }

         @Override
         public Label conditionalJump(int index, Condition condition) {
             Label label = new Label();
             conditionalJump(index, condition, label);
             return label;
         }

         @Override
         public void bind(Label label) {
             masm.bind(label);
         }

         @Override
         public boolean isSameTarget(int index1, int index2) {
             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[keyProbabilities.length];
         private final int[] keyCounts = new int[keyProbabilities.length];
         private final LabelRef[] keyTargets;

         EffortClosure(LabelRef[] keyTargets) {
             this.keyTargets = keyTargets;
         }

         @Override
         public void conditionalJump(int index, Condition condition, boolean defaultTarget) {
             // nothing to do
         }

         @Override
         public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
             // nothing to do
         }

         @Override
         public Label conditionalJump(int index, Condition condition) {
             // nothing to do
             return null;
         }

         @Override
         public void bind(Label label) {
             // nothing to do
         }

         @Override
         public boolean isSameTarget(int index1, int index2) {
             return keyTargets[index1] == keyTargets[index2];
         }

         public double getAverageEffort() {
             double defaultProbability = 1;
             double effort = 0;
             for (int i = 0; i < keyProbabilities.length; i++) {
                 effort += keyEfforts[i] * keyProbabilities[i] / keyCounts[i];
                 defaultProbability -= keyProbabilities[i];
             }
             return effort + defaultEffort * defaultProbability / defaultCount;
         }
     }

     public final double[] keyProbabilities;
     private double averageEffort = -1;
     private EffortClosure effortClosure;

     public SwitchStrategy(double[] keyProbabilities) {
         assert keyProbabilities.length >= 2;
         this.keyProbabilities = keyProbabilities;
     }

     public abstract Constant[] getKeyConstants();

     public double getAverageEffort() {
         assert averageEffort >= 0 : "average effort was not calculated yet for this strategy";
         return averageEffort;
     }

     /**
      * 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;
         private final Constant[] keyConstants;

         public SequentialStrategy(final double[] keyProbabilities, Constant[] keyConstants) {
             super(keyProbabilities);
             assert keyProbabilities.length == keyConstants.length;

             this.keyConstants = keyConstants;
             int keyCount = keyConstants.length;
             indexes = new Integer[keyCount];
             for (int i = 0; i < keyCount; i++) {
                 indexes[i] = i;
             }
             Arrays.sort(indexes, new Comparator<Integer>() {
                 @Override
                 public int compare(Integer o1, Integer o2) {
                     return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
                 }
             });
         }

         @Override
         public Constant[] getKeyConstants() {
             return keyConstants;
         }

         @Override
         public void run(SwitchClosure closure) {
             for (int i = 0; i < keyConstants.length - 1; i++) {
                 closure.conditionalJump(indexes[i], Condition.EQ, false);
                 registerEffort(indexes[i], indexes[i], i + 1);
             }
             closure.conditionalJumpOrDefault(indexes[keyConstants.length - 1], Condition.EQ, true);
             registerEffort(indexes[keyConstants.length - 1], indexes[keyConstants.length - 1], keyConstants.length);
             registerDefaultEffort(keyConstants.length);
         }
     }

     /**
      * Base class for strategies that rely on primitive integer keys.
      */
     private abstract static class PrimitiveStrategy extends SwitchStrategy {
         protected final JavaConstant[] keyConstants;

         protected PrimitiveStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
             super(keyProbabilities);
             assert keyProbabilities.length == keyConstants.length;
             this.keyConstants = keyConstants;
         }

         @Override
         public JavaConstant[] getKeyConstants() {
             return keyConstants;
         }

         /**
          * 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;
             while (slice < (keyConstants.length - 1) && keyConstants[slice + 1].asLong() == keyConstants[slice].asLong() + 1 && closure.isSameTarget(slice, slice + 1)) {
                 slice++;
             }
             return slice;
         }
     }

     /**
      * 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 PrimitiveStrategy {
         private final Integer[] indexes;

         public RangesStrategy(final double[] keyProbabilities, JavaConstant[] keyConstants) {
             super(keyProbabilities, keyConstants);

             int keyCount = keyConstants.length;
             indexes = new Integer[keyCount];
             for (int i = 0; i < keyCount; i++) {
                 indexes[i] = i;
             }
             Arrays.sort(indexes, new Comparator<Integer>() {
                 @Override
                 public int compare(Integer o1, Integer o2) {
                     return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
                 }
             });
         }

         @Override
         public void run(SwitchClosure closure) {
             int depth = 0;
             closure.conditionalJump(0, Condition.LT, true);
             registerDefaultEffort(++depth);
             int rangeStart = 0;
             int rangeEnd = getSliceEnd(closure, rangeStart);
             while (rangeEnd != keyConstants.length - 1) {
                 if (rangeStart == rangeEnd) {
                     closure.conditionalJump(rangeStart, Condition.EQ, false);
                     registerEffort(rangeStart, rangeEnd, ++depth);
                 } else {
                     if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
                         closure.conditionalJump(rangeStart, Condition.LT, true);
                         registerDefaultEffort(++depth);
                     }
                     closure.conditionalJump(rangeEnd, Condition.LE, false);
                     registerEffort(rangeStart, rangeEnd, ++depth);
                 }
                 rangeStart = rangeEnd + 1;
                 rangeEnd = getSliceEnd(closure, rangeStart);
             }
             if (rangeStart == rangeEnd) {
                 closure.conditionalJumpOrDefault(rangeStart, Condition.EQ, true);
                 registerEffort(rangeStart, rangeEnd, ++depth);
                 registerDefaultEffort(depth);
             } else {
                 if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
                     closure.conditionalJump(rangeStart, Condition.LT, true);
                     registerDefaultEffort(++depth);
                 }
                 closure.conditionalJumpOrDefault(rangeEnd, Condition.LE, true);
                 registerEffort(rangeStart, rangeEnd, ++depth);
                 registerDefaultEffort(depth);
             }
         }
     }

     /**
      * This strategy recursively subdivides the list of keys to create a binary search based on
      * probabilities.
      */
     public static class BinaryStrategy extends PrimitiveStrategy {

         private static final double MIN_PROBABILITY = 0.00001;

         private final double[] probabilitySums;

         public BinaryStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
             super(keyProbabilities, keyConstants);
             probabilitySums = new double[keyProbabilities.length + 1];
             double sum = 0;
             for (int i = 0; i < keyConstants.length; i++) {
                 sum += Math.max(keyProbabilities[i], MIN_PROBABILITY);
                 probabilitySums[i + 1] = sum;
             }
         }

         @Override
         public void run(SwitchClosure closure) {
             recurseBinarySwitch(closure, 0, keyConstants.length - 1, 0);
         }

         /**
          * 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";
             int depth = startDepth;
             boolean leftBorder = left == 0;
             boolean rightBorder = right == keyConstants.length - 1;

             if (left + 1 == right) {
                 // only two possible values
                 if (leftBorder || rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong() || keyConstants[left].asLong() + 1 != keyConstants[right].asLong()) {
                     closure.conditionalJump(left, Condition.EQ, false);
                     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);
                 }
                 return;
             }
             double probabilityStart = probabilitySums[left];
             double probabilityMiddle = (probabilityStart + probabilitySums[right + 1]) / 2;
             assert probabilityStart >= probabilityStart;
             int middle = left;
             while (getSliceEnd(closure, middle + 1) < right && probabilitySums[getSliceEnd(closure, middle + 1)] < probabilityMiddle) {
                 middle = getSliceEnd(closure, middle + 1);
             }
             middle = getSliceEnd(closure, middle);
             assert middle < keyConstants.length - 1;

             if (getSliceEnd(closure, left) == middle) {
                 if (left == 0) {
                     closure.conditionalJump(0, Condition.LT, true);
                     registerDefaultEffort(++depth);
                 }
                 closure.conditionalJump(middle, Condition.LE, false);
                 registerEffort(left, middle, ++depth);

                 if (middle + 1 == right) {
                     closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder);
                     registerEffort(right, right, ++depth);
                     registerDefaultEffort(depth);
                 } else {
                     if (keyConstants[middle].asLong() + 1 != keyConstants[middle + 1].asLong()) {
                         closure.conditionalJump(middle + 1, Condition.LT, true);
                         registerDefaultEffort(++depth);
                     }
                     if (getSliceEnd(closure, middle + 1) == right) {
                         if (right == keyConstants.length - 1 || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
                             closure.conditionalJumpOrDefault(right, Condition.LE, rightBorder);
                             registerEffort(middle + 1, right, ++depth);
                             registerDefaultEffort(depth);
                         } else {
                             closure.conditionalJump(middle + 1, null, false);
                             registerEffort(middle + 1, right, depth);
                         }
                     } else {
                         recurseBinarySwitch(closure, middle + 1, right, depth);
                     }
                 }
             } else if (getSliceEnd(closure, middle + 1) == right) {
                 if (rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
                     closure.conditionalJump(right, Condition.GT, true);
                     registerDefaultEffort(++depth);
                 }
                 closure.conditionalJump(middle + 1, Condition.GE, false);
                 registerEffort(middle + 1, right, ++depth);
                 recurseBinarySwitch(closure, left, middle, depth);
             } else {
                 Label label = closure.conditionalJump(middle + 1, Condition.GE);
                 depth++;
                 recurseBinarySwitch(closure, left, middle, depth);
                 closure.bind(label);
                 recurseBinarySwitch(closure, middle + 1, right, depth);
             }
         }
     }

     public abstract void run(SwitchClosure closure);

     private static SwitchStrategy[] getStrategies(double[] keyProbabilities, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
         SwitchStrategy[] strategies = new SwitchStrategy[]{new SequentialStrategy(keyProbabilities, keyConstants), new RangesStrategy(keyProbabilities, keyConstants),
                         new BinaryStrategy(keyProbabilities, keyConstants)};
         for (SwitchStrategy strategy : strategies) {
             strategy.effortClosure = strategy.new EffortClosure(keyTargets);
             strategy.run(strategy.effortClosure);
             strategy.averageEffort = strategy.effortClosure.getAverageEffort();
             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, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
         SwitchStrategy[] strategies = getStrategies(keyProbabilities, keyConstants, keyTargets);
         double bestEffort = Integer.MAX_VALUE;
         SwitchStrategy bestStrategy = null;
         for (SwitchStrategy strategy : strategies) {
             if (strategy.getAverageEffort() < bestEffort) {
                 bestEffort = strategy.getAverageEffort();
                 bestStrategy = strategy;
             }
         }
         return bestStrategy;
     }
 }
	/*
	* Copyright (c) 2013, 2015, 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.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package org.graalvm.compiler.lir;

	import java.util.Arrays;
	import java.util.Comparator;

	import org.graalvm.compiler.asm.Assembler;
	import org.graalvm.compiler.asm.Label;
	import org.graalvm.compiler.core.common.calc.Condition;
	import org.graalvm.compiler.lir.asm.CompilationResultBuilder;

	import jdk.vm.ci.meta.Constant;
	import jdk.vm.ci.meta.JavaConstant;

	/**
	* This class encapsulates different strategies on how to generate code for switch instructions.
	*
	* The {@link #getBestStrategy(double[], JavaConstant[], 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
	* condition is null. If defaultTarget is true, then the jump will go the the default.
	*
	* @param index Index of the value and the jump target (only used if defaultTarget == false)
	* @param condition The condition on which to jump (can be null)
	* @param defaultTarget true if the jump should go to the default target, false if index
	* should be used.
	*/
	void conditionalJump(int index, Condition condition, boolean defaultTarget);

	/**
	* Generates a conditional jump to the target with the specified index. The fall through
	* should go to the default target.
	*
	* @param index Index of the value and the jump target
	* @param condition The condition on which to jump
	* @param canFallThrough true if this is the last instruction in the switch statement, to
	* allow for fall-through optimizations.
	*/
	void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough);

	/**
	* Create a new label and generate a conditional jump to it.
	*
	* @param index Index of the value and the jump target
	* @param condition The condition on which to jump
	* @return a new Label
	*/
	Label conditionalJump(int index, Condition condition);

	/**
	* Binds a label returned by {@link #conditionalJump(int, Condition)}.
	*/
	void bind(Label label);

	/**
	* Return true iff the target of both indexes is the same.
	*/
	boolean isSameTarget(int index1, int index2);
	}

	/**
	* 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 Assembler masm;
	private final LabelRef[] keyTargets;
	private final LabelRef defaultTarget;

	public BaseSwitchClosure(CompilationResultBuilder crb, Assembler masm, LabelRef[] keyTargets, LabelRef defaultTarget) {
	this.crb = crb;
	this.masm = masm;
	this.keyTargets = keyTargets;
	this.defaultTarget = defaultTarget;
	}

	/**
	* This method generates code for a comparison between the actual value and the constant at
	* the given index and a condition jump to target.
	*/
	protected abstract void conditionalJump(int index, Condition condition, Label target);

	@Override
	public void conditionalJump(int index, Condition condition, boolean targetDefault) {
	Label target = targetDefault ? defaultTarget.label() : keyTargets[index].label();
	if (condition == null) {
	masm.jmp(target);
	} else {
	conditionalJump(index, condition, target);
	}
	}

	@Override
	public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
	if (canFallThrough && crb.isSuccessorEdge(defaultTarget)) {
	conditionalJump(index, condition, keyTargets[index].label());
	} else if (canFallThrough && crb.isSuccessorEdge(keyTargets[index])) {
	conditionalJump(index, condition.negate(), defaultTarget.label());
	} else {
	conditionalJump(index, condition, keyTargets[index].label());
	masm.jmp(defaultTarget.label());
	}
	}

	@Override
	public Label conditionalJump(int index, Condition condition) {
	Label label = new Label();
	conditionalJump(index, condition, label);
	return label;
	}

	@Override
	public void bind(Label label) {
	masm.bind(label);
	}

	@Override
	public boolean isSameTarget(int index1, int index2) {
	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[keyProbabilities.length];
	private final int[] keyCounts = new int[keyProbabilities.length];
	private final LabelRef[] keyTargets;

	EffortClosure(LabelRef[] keyTargets) {
	this.keyTargets = keyTargets;
	}

	@Override
	public void conditionalJump(int index, Condition condition, boolean defaultTarget) {
	// nothing to do
	}

	@Override
	public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
	// nothing to do
	}

	@Override
	public Label conditionalJump(int index, Condition condition) {
	// nothing to do
	return null;
	}

	@Override
	public void bind(Label label) {
	// nothing to do
	}

	@Override
	public boolean isSameTarget(int index1, int index2) {
	return keyTargets[index1] == keyTargets[index2];
	}

	public double getAverageEffort() {
	double defaultProbability = 1;
	double effort = 0;
	for (int i = 0; i < keyProbabilities.length; i++) {
	effort += keyEfforts[i] * keyProbabilities[i] / keyCounts[i];
	defaultProbability -= keyProbabilities[i];
	}
	return effort + defaultEffort * defaultProbability / defaultCount;
	}
	}

	public final double[] keyProbabilities;
	private double averageEffort = -1;
	private EffortClosure effortClosure;

	public SwitchStrategy(double[] keyProbabilities) {
	assert keyProbabilities.length >= 2;
	this.keyProbabilities = keyProbabilities;
	}

	public abstract Constant[] getKeyConstants();

	public double getAverageEffort() {
	assert averageEffort >= 0 : "average effort was not calculated yet for this strategy";
	return averageEffort;
	}

	/**
	* 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;
	private final Constant[] keyConstants;

	public SequentialStrategy(final double[] keyProbabilities, Constant[] keyConstants) {
	super(keyProbabilities);
	assert keyProbabilities.length == keyConstants.length;

	this.keyConstants = keyConstants;
	int keyCount = keyConstants.length;
	indexes = new Integer[keyCount];
	for (int i = 0; i < keyCount; i++) {
	indexes[i] = i;
	}
	Arrays.sort(indexes, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
	return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
	}
	});
	}

	@Override
	public Constant[] getKeyConstants() {
	return keyConstants;
	}

	@Override
	public void run(SwitchClosure closure) {
	for (int i = 0; i < keyConstants.length - 1; i++) {
	closure.conditionalJump(indexes[i], Condition.EQ, false);
	registerEffort(indexes[i], indexes[i], i + 1);
	}
	closure.conditionalJumpOrDefault(indexes[keyConstants.length - 1], Condition.EQ, true);
	registerEffort(indexes[keyConstants.length - 1], indexes[keyConstants.length - 1], keyConstants.length);
	registerDefaultEffort(keyConstants.length);
	}
	}

	/**
	* Base class for strategies that rely on primitive integer keys.
	*/
	private abstract static class PrimitiveStrategy extends SwitchStrategy {
	protected final JavaConstant[] keyConstants;

	protected PrimitiveStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
	super(keyProbabilities);
	assert keyProbabilities.length == keyConstants.length;
	this.keyConstants = keyConstants;
	}

	@Override
	public JavaConstant[] getKeyConstants() {
	return keyConstants;
	}

	/**
	* 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;
	while (slice < (keyConstants.length - 1) && keyConstants[slice + 1].asLong() == keyConstants[slice].asLong() + 1 && closure.isSameTarget(slice, slice + 1)) {
	slice++;
	}
	return slice;
	}
	}

	/**
	* 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 PrimitiveStrategy {
	private final Integer[] indexes;

	public RangesStrategy(final double[] keyProbabilities, JavaConstant[] keyConstants) {
	super(keyProbabilities, keyConstants);

	int keyCount = keyConstants.length;
	indexes = new Integer[keyCount];
	for (int i = 0; i < keyCount; i++) {
	indexes[i] = i;
	}
	Arrays.sort(indexes, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
	return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
	}
	});
	}

	@Override
	public void run(SwitchClosure closure) {
	int depth = 0;
	closure.conditionalJump(0, Condition.LT, true);
	registerDefaultEffort(++depth);
	int rangeStart = 0;
	int rangeEnd = getSliceEnd(closure, rangeStart);
	while (rangeEnd != keyConstants.length - 1) {
	if (rangeStart == rangeEnd) {
	closure.conditionalJump(rangeStart, Condition.EQ, false);
	registerEffort(rangeStart, rangeEnd, ++depth);
	} else {
	if (rangeStart == 0 \|\| keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
	closure.conditionalJump(rangeStart, Condition.LT, true);
	registerDefaultEffort(++depth);
	}
	closure.conditionalJump(rangeEnd, Condition.LE, false);
	registerEffort(rangeStart, rangeEnd, ++depth);
	}
	rangeStart = rangeEnd + 1;
	rangeEnd = getSliceEnd(closure, rangeStart);
	}
	if (rangeStart == rangeEnd) {
	closure.conditionalJumpOrDefault(rangeStart, Condition.EQ, true);
	registerEffort(rangeStart, rangeEnd, ++depth);
	registerDefaultEffort(depth);
	} else {
	if (rangeStart == 0 \|\| keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
	closure.conditionalJump(rangeStart, Condition.LT, true);
	registerDefaultEffort(++depth);
	}
	closure.conditionalJumpOrDefault(rangeEnd, Condition.LE, true);
	registerEffort(rangeStart, rangeEnd, ++depth);
	registerDefaultEffort(depth);
	}
	}
	}

	/**
	* This strategy recursively subdivides the list of keys to create a binary search based on
	* probabilities.
	*/
	public static class BinaryStrategy extends PrimitiveStrategy {

	private static final double MIN_PROBABILITY = 0.00001;

	private final double[] probabilitySums;

	public BinaryStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
	super(keyProbabilities, keyConstants);
	probabilitySums = new double[keyProbabilities.length + 1];
	double sum = 0;
	for (int i = 0; i < keyConstants.length; i++) {
	sum += Math.max(keyProbabilities[i], MIN_PROBABILITY);
	probabilitySums[i + 1] = sum;
	}
	}

	@Override
	public void run(SwitchClosure closure) {
	recurseBinarySwitch(closure, 0, keyConstants.length - 1, 0);
	}

	/**
	* 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";
	int depth = startDepth;
	boolean leftBorder = left == 0;
	boolean rightBorder = right == keyConstants.length - 1;

	if (left + 1 == right) {
	// only two possible values
	if (leftBorder \|\| rightBorder \|\| keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong() \|\| keyConstants[left].asLong() + 1 != keyConstants[right].asLong()) {
	closure.conditionalJump(left, Condition.EQ, false);
	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);
	}
	return;
	}
	double probabilityStart = probabilitySums[left];
	double probabilityMiddle = (probabilityStart + probabilitySums[right + 1]) / 2;
	assert probabilityStart >= probabilityStart;
	int middle = left;
	while (getSliceEnd(closure, middle + 1) < right && probabilitySums[getSliceEnd(closure, middle + 1)] < probabilityMiddle) {
	middle = getSliceEnd(closure, middle + 1);
	}
	middle = getSliceEnd(closure, middle);
	assert middle < keyConstants.length - 1;

	if (getSliceEnd(closure, left) == middle) {
	if (left == 0) {
	closure.conditionalJump(0, Condition.LT, true);
	registerDefaultEffort(++depth);
	}
	closure.conditionalJump(middle, Condition.LE, false);
	registerEffort(left, middle, ++depth);

	if (middle + 1 == right) {
	closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder);
	registerEffort(right, right, ++depth);
	registerDefaultEffort(depth);
	} else {
	if (keyConstants[middle].asLong() + 1 != keyConstants[middle + 1].asLong()) {
	closure.conditionalJump(middle + 1, Condition.LT, true);
	registerDefaultEffort(++depth);
	}
	if (getSliceEnd(closure, middle + 1) == right) {
	if (right == keyConstants.length - 1 \|\| keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
	closure.conditionalJumpOrDefault(right, Condition.LE, rightBorder);
	registerEffort(middle + 1, right, ++depth);
	registerDefaultEffort(depth);
	} else {
	closure.conditionalJump(middle + 1, null, false);
	registerEffort(middle + 1, right, depth);
	}
	} else {
	recurseBinarySwitch(closure, middle + 1, right, depth);
	}
	}
	} else if (getSliceEnd(closure, middle + 1) == right) {
	if (rightBorder \|\| keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
	closure.conditionalJump(right, Condition.GT, true);
	registerDefaultEffort(++depth);
	}
	closure.conditionalJump(middle + 1, Condition.GE, false);
	registerEffort(middle + 1, right, ++depth);
	recurseBinarySwitch(closure, left, middle, depth);
	} else {
	Label label = closure.conditionalJump(middle + 1, Condition.GE);
	depth++;
	recurseBinarySwitch(closure, left, middle, depth);
	closure.bind(label);
	recurseBinarySwitch(closure, middle + 1, right, depth);
	}
	}
	}

	public abstract void run(SwitchClosure closure);

	private static SwitchStrategy[] getStrategies(double[] keyProbabilities, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
	SwitchStrategy[] strategies = new SwitchStrategy[]{new SequentialStrategy(keyProbabilities, keyConstants), new RangesStrategy(keyProbabilities, keyConstants),
	new BinaryStrategy(keyProbabilities, keyConstants)};
	for (SwitchStrategy strategy : strategies) {
	strategy.effortClosure = strategy.new EffortClosure(keyTargets);
	strategy.run(strategy.effortClosure);
	strategy.averageEffort = strategy.effortClosure.getAverageEffort();
	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, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
	SwitchStrategy[] strategies = getStrategies(keyProbabilities, keyConstants, keyTargets);
	double bestEffort = Integer.MAX_VALUE;
	SwitchStrategy bestStrategy = null;
	for (SwitchStrategy strategy : strategies) {
	if (strategy.getAverageEffort() < bestEffort) {
	bestEffort = strategy.getAverageEffort();
	bestStrategy = strategy;
	}
	}
	return bestStrategy;
	}
	}