1 /*
2 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir;
24
25 import java.util.Arrays;
26 import java.util.Comparator;
27
28 import org.graalvm.compiler.asm.Assembler;
29 import org.graalvm.compiler.asm.Label;
30 import org.graalvm.compiler.core.common.calc.Condition;
31 import org.graalvm.compiler.lir.asm.CompilationResultBuilder;
32
33 import jdk.vm.ci.meta.Constant;
34 import jdk.vm.ci.meta.JavaConstant;
35
36 /**
37 * This class encapsulates different strategies on how to generate code for switch instructions.
38 *
39 * The {@link #getBestStrategy(double[], JavaConstant[], LabelRef[])} method can be used to get
40 * strategy with the smallest average effort (average number of comparisons until a decision is
41 * reached). The strategy returned by this method will have its averageEffort set, while a strategy
42 * constructed directly will not.
43 */
44 public abstract class SwitchStrategy {
45
46 private interface SwitchClosure {
47 /**
48 * Generates a conditional or unconditional jump. The jump will be unconditional if
49 * condition is null. If defaultTarget is true, then the jump will go the the default.
50 *
51 * @param index Index of the value and the jump target (only used if defaultTarget == false)
52 * @param condition The condition on which to jump (can be null)
53 * @param defaultTarget true if the jump should go to the default target, false if index
54 * should be used.
55 */
56 void conditionalJump(int index, Condition condition, boolean defaultTarget);
57
58 /**
59 * Generates a conditional jump to the target with the specified index. The fall through
60 * should go to the default target.
61 *
62 * @param index Index of the value and the jump target
63 * @param condition The condition on which to jump
64 * @param canFallThrough true if this is the last instruction in the switch statement, to
65 * allow for fall-through optimizations.
66 */
67 void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough);
68
69 /**
70 * Create a new label and generate a conditional jump to it.
71 *
72 * @param index Index of the value and the jump target
73 * @param condition The condition on which to jump
74 * @return a new Label
75 */
76 Label conditionalJump(int index, Condition condition);
77
78 /**
79 * Binds a label returned by {@link #conditionalJump(int, Condition)}.
80 */
81 void bind(Label label);
82
83 /**
84 * Return true iff the target of both indexes is the same.
85 */
86 boolean isSameTarget(int index1, int index2);
87 }
88
89 /**
90 * Backends can subclass this abstract class and generate code for switch strategies by
91 * implementing the {@link #conditionalJump(int, Condition, Label)} method.
92 */
93 public abstract static class BaseSwitchClosure implements SwitchClosure {
94
95 private final CompilationResultBuilder crb;
96 private final Assembler masm;
97 private final LabelRef[] keyTargets;
98 private final LabelRef defaultTarget;
99
100 public BaseSwitchClosure(CompilationResultBuilder crb, Assembler masm, LabelRef[] keyTargets, LabelRef defaultTarget) {
101 this.crb = crb;
102 this.masm = masm;
103 this.keyTargets = keyTargets;
104 this.defaultTarget = defaultTarget;
105 }
106
107 /**
108 * This method generates code for a comparison between the actual value and the constant at
109 * the given index and a condition jump to target.
110 */
111 protected abstract void conditionalJump(int index, Condition condition, Label target);
112
113 @Override
114 public void conditionalJump(int index, Condition condition, boolean targetDefault) {
115 Label target = targetDefault ? defaultTarget.label() : keyTargets[index].label();
116 if (condition == null) {
117 masm.jmp(target);
118 } else {
119 conditionalJump(index, condition, target);
120 }
121 }
122
123 @Override
124 public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
125 if (canFallThrough && crb.isSuccessorEdge(defaultTarget)) {
126 conditionalJump(index, condition, keyTargets[index].label());
127 } else if (canFallThrough && crb.isSuccessorEdge(keyTargets[index])) {
128 conditionalJump(index, condition.negate(), defaultTarget.label());
129 } else {
130 conditionalJump(index, condition, keyTargets[index].label());
131 masm.jmp(defaultTarget.label());
132 }
133 }
134
135 @Override
136 public Label conditionalJump(int index, Condition condition) {
137 Label label = new Label();
138 conditionalJump(index, condition, label);
139 return label;
140 }
141
142 @Override
143 public void bind(Label label) {
144 masm.bind(label);
145 }
146
147 @Override
148 public boolean isSameTarget(int index1, int index2) {
149 return keyTargets[index1] == keyTargets[index2];
150 }
151
152 }
153
154 /**
155 * This closure is used internally to determine the average effort for a certain strategy on a
156 * given switch instruction.
157 */
158 private class EffortClosure implements SwitchClosure {
159
160 private int defaultEffort;
161 private int defaultCount;
162 private final int[] keyEfforts = new int[keyProbabilities.length];
163 private final int[] keyCounts = new int[keyProbabilities.length];
164 private final LabelRef[] keyTargets;
165
166 EffortClosure(LabelRef[] keyTargets) {
167 this.keyTargets = keyTargets;
168 }
169
170 @Override
171 public void conditionalJump(int index, Condition condition, boolean defaultTarget) {
172 // nothing to do
173 }
174
175 @Override
176 public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) {
177 // nothing to do
178 }
179
180 @Override
181 public Label conditionalJump(int index, Condition condition) {
182 // nothing to do
183 return null;
184 }
185
186 @Override
187 public void bind(Label label) {
188 // nothing to do
189 }
190
191 @Override
192 public boolean isSameTarget(int index1, int index2) {
193 return keyTargets[index1] == keyTargets[index2];
194 }
195
196 public double getAverageEffort() {
197 double defaultProbability = 1;
198 double effort = 0;
199 for (int i = 0; i < keyProbabilities.length; i++) {
200 effort += keyEfforts[i] * keyProbabilities[i] / keyCounts[i];
201 defaultProbability -= keyProbabilities[i];
202 }
203 return effort + defaultEffort * defaultProbability / defaultCount;
204 }
205 }
206
207 public final double[] keyProbabilities;
208 private double averageEffort = -1;
209 private EffortClosure effortClosure;
210
211 public SwitchStrategy(double[] keyProbabilities) {
212 assert keyProbabilities.length >= 2;
213 this.keyProbabilities = keyProbabilities;
214 }
215
216 public abstract Constant[] getKeyConstants();
217
218 public double getAverageEffort() {
219 assert averageEffort >= 0 : "average effort was not calculated yet for this strategy";
220 return averageEffort;
221 }
222
223 /**
224 * Tells the system that the given (inclusive) range of keys is reached after depth number of
225 * comparisons, which is used to calculate the average effort.
226 */
227 protected void registerEffort(int rangeStart, int rangeEnd, int depth) {
228 if (effortClosure != null) {
229 for (int i = rangeStart; i <= rangeEnd; i++) {
230 effortClosure.keyEfforts[i] += depth;
231 effortClosure.keyCounts[i]++;
232 }
233 }
234 }
235
236 /**
237 * Tells the system that the default successor is reached after depth number of comparisons,
238 * which is used to calculate average effort.
239 */
240 protected void registerDefaultEffort(int depth) {
241 if (effortClosure != null) {
242 effortClosure.defaultEffort += depth;
243 effortClosure.defaultCount++;
244 }
245 }
246
247 @Override
248 public String toString() {
249 return getClass().getSimpleName() + "[avgEffort=" + averageEffort + "]";
250 }
251
252 /**
253 * This strategy orders the keys according to their probability and creates one equality
254 * comparison per key.
255 */
256 public static class SequentialStrategy extends SwitchStrategy {
257 private final Integer[] indexes;
258 private final Constant[] keyConstants;
259
260 public SequentialStrategy(final double[] keyProbabilities, Constant[] keyConstants) {
261 super(keyProbabilities);
262 assert keyProbabilities.length == keyConstants.length;
263
264 this.keyConstants = keyConstants;
265 int keyCount = keyConstants.length;
266 indexes = new Integer[keyCount];
267 for (int i = 0; i < keyCount; i++) {
268 indexes[i] = i;
269 }
270 Arrays.sort(indexes, new Comparator<Integer>() {
271 @Override
272 public int compare(Integer o1, Integer o2) {
273 return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
274 }
275 });
276 }
277
278 @Override
279 public Constant[] getKeyConstants() {
280 return keyConstants;
281 }
282
283 @Override
284 public void run(SwitchClosure closure) {
285 for (int i = 0; i < keyConstants.length - 1; i++) {
286 closure.conditionalJump(indexes[i], Condition.EQ, false);
287 registerEffort(indexes[i], indexes[i], i + 1);
288 }
289 closure.conditionalJumpOrDefault(indexes[keyConstants.length - 1], Condition.EQ, true);
290 registerEffort(indexes[keyConstants.length - 1], indexes[keyConstants.length - 1], keyConstants.length);
291 registerDefaultEffort(keyConstants.length);
292 }
293 }
294
295 /**
296 * Base class for strategies that rely on primitive integer keys.
297 */
298 private abstract static class PrimitiveStrategy extends SwitchStrategy {
299 protected final JavaConstant[] keyConstants;
300
301 protected PrimitiveStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
302 super(keyProbabilities);
303 assert keyProbabilities.length == keyConstants.length;
304 this.keyConstants = keyConstants;
305 }
306
307 @Override
308 public JavaConstant[] getKeyConstants() {
309 return keyConstants;
310 }
311
312 /**
313 * Looks for the end of a stretch of key constants that are successive numbers and have the
314 * same target.
315 */
316 protected int getSliceEnd(SwitchClosure closure, int pos) {
317 int slice = pos;
318 while (slice < (keyConstants.length - 1) && keyConstants[slice + 1].asLong() == keyConstants[slice].asLong() + 1 && closure.isSameTarget(slice, slice + 1)) {
319 slice++;
320 }
321 return slice;
322 }
323 }
324
325 /**
326 * This strategy divides the keys into ranges of successive keys with the same target and
327 * creates comparisons for these ranges.
328 */
329 public static class RangesStrategy extends PrimitiveStrategy {
330 private final Integer[] indexes;
331
332 public RangesStrategy(final double[] keyProbabilities, JavaConstant[] keyConstants) {
333 super(keyProbabilities, keyConstants);
334
335 int keyCount = keyConstants.length;
336 indexes = new Integer[keyCount];
337 for (int i = 0; i < keyCount; i++) {
338 indexes[i] = i;
339 }
340 Arrays.sort(indexes, new Comparator<Integer>() {
341 @Override
342 public int compare(Integer o1, Integer o2) {
343 return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0;
344 }
345 });
346 }
347
348 @Override
349 public void run(SwitchClosure closure) {
350 int depth = 0;
351 closure.conditionalJump(0, Condition.LT, true);
352 registerDefaultEffort(++depth);
353 int rangeStart = 0;
354 int rangeEnd = getSliceEnd(closure, rangeStart);
355 while (rangeEnd != keyConstants.length - 1) {
356 if (rangeStart == rangeEnd) {
357 closure.conditionalJump(rangeStart, Condition.EQ, false);
358 registerEffort(rangeStart, rangeEnd, ++depth);
359 } else {
360 if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
361 closure.conditionalJump(rangeStart, Condition.LT, true);
362 registerDefaultEffort(++depth);
363 }
364 closure.conditionalJump(rangeEnd, Condition.LE, false);
365 registerEffort(rangeStart, rangeEnd, ++depth);
366 }
367 rangeStart = rangeEnd + 1;
368 rangeEnd = getSliceEnd(closure, rangeStart);
369 }
370 if (rangeStart == rangeEnd) {
371 closure.conditionalJumpOrDefault(rangeStart, Condition.EQ, true);
372 registerEffort(rangeStart, rangeEnd, ++depth);
373 registerDefaultEffort(depth);
374 } else {
375 if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) {
376 closure.conditionalJump(rangeStart, Condition.LT, true);
377 registerDefaultEffort(++depth);
378 }
379 closure.conditionalJumpOrDefault(rangeEnd, Condition.LE, true);
380 registerEffort(rangeStart, rangeEnd, ++depth);
381 registerDefaultEffort(depth);
382 }
383 }
384 }
385
386 /**
387 * This strategy recursively subdivides the list of keys to create a binary search based on
388 * probabilities.
389 */
390 public static class BinaryStrategy extends PrimitiveStrategy {
391
392 private static final double MIN_PROBABILITY = 0.00001;
393
394 private final double[] probabilitySums;
395
396 public BinaryStrategy(double[] keyProbabilities, JavaConstant[] keyConstants) {
397 super(keyProbabilities, keyConstants);
398 probabilitySums = new double[keyProbabilities.length + 1];
399 double sum = 0;
400 for (int i = 0; i < keyConstants.length; i++) {
401 sum += Math.max(keyProbabilities[i], MIN_PROBABILITY);
402 probabilitySums[i + 1] = sum;
403 }
404 }
405
406 @Override
407 public void run(SwitchClosure closure) {
408 recurseBinarySwitch(closure, 0, keyConstants.length - 1, 0);
409 }
410
411 /**
412 * Recursively generate a list of comparisons that always subdivides the keys in the given
413 * (inclusive) range in the middle (in terms of probability, not index). If left is bigger
414 * than zero, then we always know that the value is equal to or bigger than the left key.
415 * This does not hold for the right key, as there may be a gap afterwards.
416 */
417 private void recurseBinarySwitch(SwitchClosure closure, int left, int right, int startDepth) {
418 assert startDepth < keyConstants.length * 3 : "runaway recursion in binary switch";
419 int depth = startDepth;
420 boolean leftBorder = left == 0;
421 boolean rightBorder = right == keyConstants.length - 1;
422
423 if (left + 1 == right) {
424 // only two possible values
425 if (leftBorder || rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong() || keyConstants[left].asLong() + 1 != keyConstants[right].asLong()) {
426 closure.conditionalJump(left, Condition.EQ, false);
427 registerEffort(left, left, ++depth);
428 closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder);
429 registerEffort(right, right, ++depth);
430 registerDefaultEffort(depth);
431 } else {
432 // here we know that the value can only be one of these two keys in the range
433 closure.conditionalJump(left, Condition.EQ, false);
434 registerEffort(left, left, ++depth);
435 closure.conditionalJump(right, null, false);
436 registerEffort(right, right, depth);
437 }
438 return;
439 }
440 double probabilityStart = probabilitySums[left];
441 double probabilityMiddle = (probabilityStart + probabilitySums[right + 1]) / 2;
442 assert probabilityStart >= probabilityStart;
443 int middle = left;
444 while (getSliceEnd(closure, middle + 1) < right && probabilitySums[getSliceEnd(closure, middle + 1)] < probabilityMiddle) {
445 middle = getSliceEnd(closure, middle + 1);
446 }
447 middle = getSliceEnd(closure, middle);
448 assert middle < keyConstants.length - 1;
449
450 if (getSliceEnd(closure, left) == middle) {
451 if (left == 0) {
452 closure.conditionalJump(0, Condition.LT, true);
453 registerDefaultEffort(++depth);
454 }
455 closure.conditionalJump(middle, Condition.LE, false);
456 registerEffort(left, middle, ++depth);
457
458 if (middle + 1 == right) {
459 closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder);
460 registerEffort(right, right, ++depth);
461 registerDefaultEffort(depth);
462 } else {
463 if (keyConstants[middle].asLong() + 1 != keyConstants[middle + 1].asLong()) {
464 closure.conditionalJump(middle + 1, Condition.LT, true);
465 registerDefaultEffort(++depth);
466 }
467 if (getSliceEnd(closure, middle + 1) == right) {
468 if (right == keyConstants.length - 1 || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
469 closure.conditionalJumpOrDefault(right, Condition.LE, rightBorder);
470 registerEffort(middle + 1, right, ++depth);
471 registerDefaultEffort(depth);
472 } else {
473 closure.conditionalJump(middle + 1, null, false);
474 registerEffort(middle + 1, right, depth);
475 }
476 } else {
477 recurseBinarySwitch(closure, middle + 1, right, depth);
478 }
479 }
480 } else if (getSliceEnd(closure, middle + 1) == right) {
481 if (rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) {
482 closure.conditionalJump(right, Condition.GT, true);
483 registerDefaultEffort(++depth);
484 }
485 closure.conditionalJump(middle + 1, Condition.GE, false);
486 registerEffort(middle + 1, right, ++depth);
487 recurseBinarySwitch(closure, left, middle, depth);
488 } else {
489 Label label = closure.conditionalJump(middle + 1, Condition.GE);
490 depth++;
491 recurseBinarySwitch(closure, left, middle, depth);
492 closure.bind(label);
493 recurseBinarySwitch(closure, middle + 1, right, depth);
494 }
495 }
496 }
497
498 public abstract void run(SwitchClosure closure);
499
500 private static SwitchStrategy[] getStrategies(double[] keyProbabilities, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
501 SwitchStrategy[] strategies = new SwitchStrategy[]{new SequentialStrategy(keyProbabilities, keyConstants), new RangesStrategy(keyProbabilities, keyConstants),
502 new BinaryStrategy(keyProbabilities, keyConstants)};
503 for (SwitchStrategy strategy : strategies) {
504 strategy.effortClosure = strategy.new EffortClosure(keyTargets);
505 strategy.run(strategy.effortClosure);
506 strategy.averageEffort = strategy.effortClosure.getAverageEffort();
507 strategy.effortClosure = null;
508 }
509 return strategies;
510 }
511
512 /**
513 * Creates all switch strategies for the given switch, evaluates them (based on average effort)
514 * and returns the best one.
515 */
516 public static SwitchStrategy getBestStrategy(double[] keyProbabilities, JavaConstant[] keyConstants, LabelRef[] keyTargets) {
517 SwitchStrategy[] strategies = getStrategies(keyProbabilities, keyConstants, keyTargets);
518 double bestEffort = Integer.MAX_VALUE;
519 SwitchStrategy bestStrategy = null;
520 for (SwitchStrategy strategy : strategies) {
521 if (strategy.getAverageEffort() < bestEffort) {
522 bestEffort = strategy.getAverageEffort();
523 bestStrategy = strategy;
524 }
525 }
526 return bestStrategy;
527 }
528 }