29 import static jdk.vm.ci.code.ValueUtil.isLegal;
30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
31 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
33 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
34 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
35
36 import java.util.ArrayList;
37 import java.util.List;
38 import java.util.Optional;
39
40 import org.graalvm.compiler.asm.Label;
41 import org.graalvm.compiler.core.common.LIRKind;
42 import org.graalvm.compiler.core.common.calc.Condition;
43 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
44 import org.graalvm.compiler.core.common.spi.CodeGenProviders;
45 import org.graalvm.compiler.core.common.spi.ForeignCallLinkage;
46 import org.graalvm.compiler.core.common.spi.ForeignCallsProvider;
47 import org.graalvm.compiler.core.common.spi.LIRKindTool;
48 import org.graalvm.compiler.core.common.type.Stamp;
49 import org.graalvm.compiler.debug.GraalError;
50 import org.graalvm.compiler.debug.TTY;
51 import org.graalvm.compiler.graph.NodeSourcePosition;
52 import org.graalvm.compiler.lir.ConstantValue;
53 import org.graalvm.compiler.lir.LIR;
54 import org.graalvm.compiler.lir.LIRFrameState;
55 import org.graalvm.compiler.lir.LIRInstruction;
56 import org.graalvm.compiler.lir.LIRVerifier;
57 import org.graalvm.compiler.lir.LabelRef;
58 import org.graalvm.compiler.lir.StandardOp;
59 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
60 import org.graalvm.compiler.lir.StandardOp.LabelOp;
61 import org.graalvm.compiler.lir.StandardOp.SaveRegistersOp;
62 import org.graalvm.compiler.lir.hashing.Hasher;
63 import org.graalvm.compiler.lir.SwitchStrategy;
64 import org.graalvm.compiler.lir.Variable;
65 import org.graalvm.compiler.options.Option;
66 import org.graalvm.compiler.options.OptionKey;
67 import org.graalvm.compiler.options.OptionType;
68 import org.graalvm.compiler.options.OptionValues;
369
370 @Override
371 public AbstractBlockBase<?> getCurrentBlock() {
372 return currentBlock;
373 }
374
375 @Override
376 public void close() {
377 doBlockEnd();
378 }
379
380 }
381
382 @Override
383 public final BlockScope getBlockScope(AbstractBlockBase<?> block) {
384 BlockScopeImpl blockScope = new BlockScopeImpl(block);
385 blockScope.doBlockStart();
386 return blockScope;
387 }
388
389 @Override
390 public void emitIncomingValues(Value[] params) {
391 ((LabelOp) res.getLIR().getLIRforBlock(getCurrentBlock()).get(0)).setIncomingValues(params);
392 }
393
394 @Override
395 public abstract void emitJump(LabelRef label);
396
397 @Override
398 public abstract void emitCompareBranch(PlatformKind cmpKind, Value left, Value right, Condition cond, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination,
399 double trueDestinationProbability);
400
401 @Override
402 public abstract void emitOverflowCheckBranch(LabelRef overflow, LabelRef noOverflow, LIRKind cmpKind, double overflowProbability);
403
404 @Override
405 public abstract void emitIntegerTestBranch(Value left, Value right, LabelRef trueDestination, LabelRef falseDestination, double trueSuccessorProbability);
406
407 @Override
408 public abstract Variable emitConditionalMove(PlatformKind cmpKind, Value leftVal, Value right, Condition cond, boolean unorderedIsTrue, Value trueValue, Value falseValue);
440 argLocations[i] = loc;
441 }
442 res.setForeignCall(true);
443 emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
444
445 if (isLegal(linkageCc.getReturn())) {
446 return emitMove(linkageCc.getReturn());
447 } else {
448 return null;
449 }
450 }
451
452 @Override
453 public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
454 SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
455
456 int keyCount = keyConstants.length;
457 double minDensity = 1 / Math.sqrt(strategy.getAverageEffort());
458 Optional<Hasher> hasher = hasherFor(keyConstants, minDensity);
459 double hashTableSwitchDensity = hasher.map(h -> keyCount / (double) h.cardinality()).orElse(0d);
460 long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1;
461 double tableSwitchDensity = keyCount / (double) valueRange;
462
463 /*
464 * This heuristic tries to find a compromise between the effort for the best switch strategy
465 * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
466 * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
467 * gradually with additional effort.
468 */
469 if (strategy.getAverageEffort() < 4d || (tableSwitchDensity < minDensity && hashTableSwitchDensity < minDensity)) {
470 emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
471 } else {
472 if (hashTableSwitchDensity > tableSwitchDensity) {
473 Hasher h = hasher.get();
474 int cardinality = h.cardinality();
475 LabelRef[] targets = new LabelRef[cardinality];
476 JavaConstant[] keys = new JavaConstant[cardinality];
477 for (int i = 0; i < cardinality; i++) {
478 keys[i] = JavaConstant.INT_0;
479 targets[i] = defaultTarget;
480 }
481 for (int i = 0; i < keyCount; i++) {
482 int idx = h.hash(keyConstants[i].asLong());
483 keys[idx] = keyConstants[i];
484 targets[idx] = keyTargets[i];
485 }
486 emitHashTableSwitch(h, keys, defaultTarget, targets, value);
487 } else {
488 int minValue = keyConstants[0].asInt();
489 assert valueRange < Integer.MAX_VALUE;
490 LabelRef[] targets = new LabelRef[(int) valueRange];
491 for (int i = 0; i < valueRange; i++) {
492 targets[i] = defaultTarget;
493 }
494 for (int i = 0; i < keyCount; i++) {
495 targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
496 }
497 emitTableSwitch(minValue, defaultTarget, targets, value);
498 }
499 }
500 }
501
502 @Override
|
29 import static jdk.vm.ci.code.ValueUtil.isLegal;
30 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
31 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant;
32 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
33 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
34 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
35
36 import java.util.ArrayList;
37 import java.util.List;
38 import java.util.Optional;
39
40 import org.graalvm.compiler.asm.Label;
41 import org.graalvm.compiler.core.common.LIRKind;
42 import org.graalvm.compiler.core.common.calc.Condition;
43 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
44 import org.graalvm.compiler.core.common.spi.CodeGenProviders;
45 import org.graalvm.compiler.core.common.spi.ForeignCallLinkage;
46 import org.graalvm.compiler.core.common.spi.ForeignCallsProvider;
47 import org.graalvm.compiler.core.common.spi.LIRKindTool;
48 import org.graalvm.compiler.core.common.type.Stamp;
49 import org.graalvm.compiler.debug.DebugCloseable;
50 import org.graalvm.compiler.debug.GraalError;
51 import org.graalvm.compiler.debug.TTY;
52 import org.graalvm.compiler.graph.NodeSourcePosition;
53 import org.graalvm.compiler.lir.ConstantValue;
54 import org.graalvm.compiler.lir.LIR;
55 import org.graalvm.compiler.lir.LIRFrameState;
56 import org.graalvm.compiler.lir.LIRInstruction;
57 import org.graalvm.compiler.lir.LIRVerifier;
58 import org.graalvm.compiler.lir.LabelRef;
59 import org.graalvm.compiler.lir.StandardOp;
60 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
61 import org.graalvm.compiler.lir.StandardOp.LabelOp;
62 import org.graalvm.compiler.lir.StandardOp.SaveRegistersOp;
63 import org.graalvm.compiler.lir.hashing.Hasher;
64 import org.graalvm.compiler.lir.SwitchStrategy;
65 import org.graalvm.compiler.lir.Variable;
66 import org.graalvm.compiler.options.Option;
67 import org.graalvm.compiler.options.OptionKey;
68 import org.graalvm.compiler.options.OptionType;
69 import org.graalvm.compiler.options.OptionValues;
370
371 @Override
372 public AbstractBlockBase<?> getCurrentBlock() {
373 return currentBlock;
374 }
375
376 @Override
377 public void close() {
378 doBlockEnd();
379 }
380
381 }
382
383 @Override
384 public final BlockScope getBlockScope(AbstractBlockBase<?> block) {
385 BlockScopeImpl blockScope = new BlockScopeImpl(block);
386 blockScope.doBlockStart();
387 return blockScope;
388 }
389
390 private final class MatchScope implements DebugCloseable {
391
392 private MatchScope(AbstractBlockBase<?> block) {
393 currentBlock = block;
394 }
395
396 @Override
397 public void close() {
398 currentBlock = null;
399 }
400
401 }
402
403 public final DebugCloseable getMatchScope(AbstractBlockBase<?> block) {
404 MatchScope matchScope = new MatchScope(block);
405 return matchScope;
406 }
407
408 @Override
409 public void emitIncomingValues(Value[] params) {
410 ((LabelOp) res.getLIR().getLIRforBlock(getCurrentBlock()).get(0)).setIncomingValues(params);
411 }
412
413 @Override
414 public abstract void emitJump(LabelRef label);
415
416 @Override
417 public abstract void emitCompareBranch(PlatformKind cmpKind, Value left, Value right, Condition cond, boolean unorderedIsTrue, LabelRef trueDestination, LabelRef falseDestination,
418 double trueDestinationProbability);
419
420 @Override
421 public abstract void emitOverflowCheckBranch(LabelRef overflow, LabelRef noOverflow, LIRKind cmpKind, double overflowProbability);
422
423 @Override
424 public abstract void emitIntegerTestBranch(Value left, Value right, LabelRef trueDestination, LabelRef falseDestination, double trueSuccessorProbability);
425
426 @Override
427 public abstract Variable emitConditionalMove(PlatformKind cmpKind, Value leftVal, Value right, Condition cond, boolean unorderedIsTrue, Value trueValue, Value falseValue);
459 argLocations[i] = loc;
460 }
461 res.setForeignCall(true);
462 emitForeignCallOp(linkage, linkageCc.getReturn(), argLocations, linkage.getTemporaries(), state);
463
464 if (isLegal(linkageCc.getReturn())) {
465 return emitMove(linkageCc.getReturn());
466 } else {
467 return null;
468 }
469 }
470
471 @Override
472 public void emitStrategySwitch(JavaConstant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) {
473 SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets);
474
475 int keyCount = keyConstants.length;
476 double minDensity = 1 / Math.sqrt(strategy.getAverageEffort());
477 Optional<Hasher> hasher = hasherFor(keyConstants, minDensity);
478 double hashTableSwitchDensity = hasher.map(h -> keyCount / (double) h.cardinality()).orElse(0d);
479 // The value range computation below may overflow, so compute it as a long.
480 long valueRange = (long) keyConstants[keyCount - 1].asInt() - (long) keyConstants[0].asInt() + 1;
481 double tableSwitchDensity = keyCount / (double) valueRange;
482
483 /*
484 * This heuristic tries to find a compromise between the effort for the best switch strategy
485 * and the density of a tableswitch. If the effort for the strategy is at least 4, then a
486 * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers
487 * gradually with additional effort.
488 */
489 if (strategy.getAverageEffort() < 4d || (tableSwitchDensity < minDensity && hashTableSwitchDensity < minDensity)) {
490 emitStrategySwitch(strategy, value, keyTargets, defaultTarget);
491 } else {
492 if (hashTableSwitchDensity > tableSwitchDensity) {
493 Hasher h = hasher.get();
494 int cardinality = h.cardinality();
495 LabelRef[] targets = new LabelRef[cardinality];
496 JavaConstant[] keys = new JavaConstant[cardinality];
497 for (int i = 0; i < cardinality; i++) {
498 keys[i] = JavaConstant.INT_0;
499 targets[i] = defaultTarget;
500 }
501 for (int i = 0; i < keyCount; i++) {
502 int idx = h.hash(keyConstants[i].asInt());
503 keys[idx] = keyConstants[i];
504 targets[idx] = keyTargets[i];
505 }
506 emitHashTableSwitch(h, keys, defaultTarget, targets, value);
507 } else {
508 int minValue = keyConstants[0].asInt();
509 assert valueRange < Integer.MAX_VALUE;
510 LabelRef[] targets = new LabelRef[(int) valueRange];
511 for (int i = 0; i < valueRange; i++) {
512 targets[i] = defaultTarget;
513 }
514 for (int i = 0; i < keyCount; i++) {
515 targets[keyConstants[i].asInt() - minValue] = keyTargets[i];
516 }
517 emitTableSwitch(minValue, defaultTarget, targets, value);
518 }
519 }
520 }
521
522 @Override
|