[vm/compiler] Optimize switch statements
Switch statements that either contain only integers or only enum values of the same type can be optimized.
Depending on the number of switch expressions and the number of holes that the range of switch expressions contains, either a binary search or a jump table is used.
TEST=runtime/test/vm/dart{,_2}/optimized_switch
TEST=tests/language{,_2}/switch
Fixes: https://github.com/dart-lang/sdk/issues/49585
Co-authored-by: Gabriel Terwesten gabriel@terwesten.net
Change-Id: I62dcdb7843107f03de7e468c60b4db52ec78f676
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/253787
Reviewed-by: Alexander Markov <alexmarkov@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/tests/vm/dart/optimized_switch_test.dart b/runtime/tests/vm/dart/optimized_switch_test.dart
new file mode 100644
index 0000000..9c80033
--- /dev/null
+++ b/runtime/tests/vm/dart/optimized_switch_test.dart
@@ -0,0 +1,577 @@
+// Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Test switches that use binary search or a jump table to dispatch cases.
+
+import 'package:expect/expect.dart';
+
+void main() {
+ Expect.isTrue(duplicateEnum(L._0) == 0);
+ Expect.isTrue(duplicateEnum(L._1) == 1);
+ Expect.isTrue(duplicateEnum(L._2) == 2);
+ Expect.isTrue(duplicateEnum(L._3) == null);
+
+ Expect.isTrue(duplicateInt(0) == 0);
+ Expect.isTrue(duplicateInt(1) == 1);
+ Expect.isTrue(duplicateInt(2) == 2);
+ Expect.isTrue(duplicateInt(3) == null);
+
+ Expect.isTrue(binarySearchEnumExhaustive(S._0) == 0);
+ Expect.isTrue(binarySearchEnumExhaustive(S._1) == 1);
+ Expect.isTrue(binarySearchEnumExhaustive(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumWithDefault(null) == null);
+ Expect.isTrue(binarySearchEnumWithDefault(S._0) == 0);
+ Expect.isTrue(binarySearchEnumWithDefault(S._1) == null);
+ Expect.isTrue(binarySearchEnumWithDefault(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumHole(S._0) == 0);
+ Expect.isTrue(binarySearchEnumHole(S._1) == null);
+ Expect.isTrue(binarySearchEnumHole(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._0) == null);
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._1) == 1);
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._0) == 0);
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._1) == 1);
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._2) == null);
+
+ Expect.isTrue(binarySearchInt(-2) == null);
+ Expect.isTrue(binarySearchInt(-1) == -1);
+ Expect.isTrue(binarySearchInt(0) == 0);
+ Expect.isTrue(binarySearchInt(1) == 1);
+ Expect.isTrue(binarySearchInt(2) == null);
+
+ Expect.isTrue(binarySearchIntWithDefault(null) == null);
+ Expect.isTrue(binarySearchIntWithDefault(-1) == null);
+ Expect.isTrue(binarySearchIntWithDefault(0) == 0);
+ Expect.isTrue(binarySearchIntWithDefault(1) == null);
+ Expect.isTrue(binarySearchIntWithDefault(2) == 2);
+ Expect.isTrue(binarySearchIntWithDefault(3) == null);
+
+ Expect.isTrue(jumpTableEnumExhaustive(L._0) == 0);
+ Expect.isTrue(jumpTableEnumExhaustive(L._1) == 1);
+ Expect.isTrue(jumpTableEnumExhaustive(L._2) == 2);
+ Expect.isTrue(jumpTableEnumExhaustive(L._3) == 3);
+ Expect.isTrue(jumpTableEnumExhaustive(L._4) == 4);
+ Expect.isTrue(jumpTableEnumExhaustive(L._5) == 5);
+ Expect.isTrue(jumpTableEnumExhaustive(L._6) == 6);
+ Expect.isTrue(jumpTableEnumExhaustive(L._7) == 7);
+ Expect.isTrue(jumpTableEnumExhaustive(L._8) == 8);
+ Expect.isTrue(jumpTableEnumExhaustive(L._9) == 9);
+ Expect.isTrue(jumpTableEnumExhaustive(L._10) == 10);
+ Expect.isTrue(jumpTableEnumExhaustive(L._11) == 11);
+ Expect.isTrue(jumpTableEnumExhaustive(L._12) == 12);
+ Expect.isTrue(jumpTableEnumExhaustive(L._13) == 13);
+ Expect.isTrue(jumpTableEnumExhaustive(L._14) == 14);
+ Expect.isTrue(jumpTableEnumExhaustive(L._15) == 15);
+ Expect.isTrue(jumpTableEnumExhaustive(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumWithDefault(null) == null);
+ Expect.isTrue(jumpTableEnumWithDefault(L._0) == 0);
+ Expect.isTrue(jumpTableEnumWithDefault(L._1) == 1);
+ Expect.isTrue(jumpTableEnumWithDefault(L._2) == 2);
+ Expect.isTrue(jumpTableEnumWithDefault(L._3) == 3);
+ Expect.isTrue(jumpTableEnumWithDefault(L._4) == 4);
+ Expect.isTrue(jumpTableEnumWithDefault(L._5) == 5);
+ Expect.isTrue(jumpTableEnumWithDefault(L._6) == 6);
+ Expect.isTrue(jumpTableEnumWithDefault(L._7) == 7);
+ Expect.isTrue(jumpTableEnumWithDefault(L._8) == null);
+ Expect.isTrue(jumpTableEnumWithDefault(L._9) == 9);
+ Expect.isTrue(jumpTableEnumWithDefault(L._10) == 10);
+ Expect.isTrue(jumpTableEnumWithDefault(L._11) == 11);
+ Expect.isTrue(jumpTableEnumWithDefault(L._12) == 12);
+ Expect.isTrue(jumpTableEnumWithDefault(L._13) == 13);
+ Expect.isTrue(jumpTableEnumWithDefault(L._14) == 14);
+ Expect.isTrue(jumpTableEnumWithDefault(L._15) == 15);
+ Expect.isTrue(jumpTableEnumWithDefault(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumHole(L._0) == 0);
+ Expect.isTrue(jumpTableEnumHole(L._1) == null);
+ Expect.isTrue(jumpTableEnumHole(L._2) == 2);
+ Expect.isTrue(jumpTableEnumHole(L._3) == 3);
+ Expect.isTrue(jumpTableEnumHole(L._4) == 4);
+ Expect.isTrue(jumpTableEnumHole(L._5) == 5);
+ Expect.isTrue(jumpTableEnumHole(L._6) == 6);
+ Expect.isTrue(jumpTableEnumHole(L._7) == 7);
+ Expect.isTrue(jumpTableEnumHole(L._8) == 8);
+ Expect.isTrue(jumpTableEnumHole(L._9) == 9);
+ Expect.isTrue(jumpTableEnumHole(L._10) == 10);
+ Expect.isTrue(jumpTableEnumHole(L._11) == 11);
+ Expect.isTrue(jumpTableEnumHole(L._12) == 12);
+ Expect.isTrue(jumpTableEnumHole(L._13) == 13);
+ Expect.isTrue(jumpTableEnumHole(L._14) == 14);
+ Expect.isTrue(jumpTableEnumHole(L._15) == 15);
+ Expect.isTrue(jumpTableEnumHole(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._0) == null);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._1) == 1);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._2) == 2);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._3) == 3);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._4) == 4);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._5) == 5);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._6) == 6);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._7) == 7);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._8) == 8);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._9) == 9);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._10) == 10);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._11) == 11);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._12) == 12);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._13) == 13);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._14) == 14);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._15) == 15);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._0) == 0);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._1) == 1);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._2) == 2);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._3) == 3);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._4) == 4);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._5) == 5);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._6) == 6);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._7) == 7);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._8) == 8);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._9) == 9);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._10) == 10);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._11) == 11);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._12) == 12);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._13) == 13);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._14) == 14);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._15) == 15);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._16) == null);
+
+ Expect.isTrue(jumpTableInt(-2) == null);
+ Expect.isTrue(jumpTableInt(-1) == -1);
+ Expect.isTrue(jumpTableInt(0) == 0);
+ Expect.isTrue(jumpTableInt(1) == 1);
+ Expect.isTrue(jumpTableInt(2) == 2);
+ Expect.isTrue(jumpTableInt(3) == 3);
+ Expect.isTrue(jumpTableInt(4) == 4);
+ Expect.isTrue(jumpTableInt(5) == 5);
+ Expect.isTrue(jumpTableInt(6) == 6);
+ Expect.isTrue(jumpTableInt(7) == 7);
+ Expect.isTrue(jumpTableInt(8) == 8);
+ Expect.isTrue(jumpTableInt(9) == 9);
+ Expect.isTrue(jumpTableInt(10) == 10);
+ Expect.isTrue(jumpTableInt(11) == 11);
+ Expect.isTrue(jumpTableInt(12) == 12);
+ Expect.isTrue(jumpTableInt(13) == 13);
+ Expect.isTrue(jumpTableInt(14) == 14);
+ Expect.isTrue(jumpTableInt(15) == null);
+
+ Expect.isTrue(jumpTableIntWithDefault(null) == null);
+ Expect.isTrue(jumpTableIntWithDefault(-1) == null);
+ Expect.isTrue(jumpTableIntWithDefault(0) == 0);
+ Expect.isTrue(jumpTableIntWithDefault(1) == 1);
+ Expect.isTrue(jumpTableIntWithDefault(2) == 2);
+ Expect.isTrue(jumpTableIntWithDefault(3) == 3);
+ Expect.isTrue(jumpTableIntWithDefault(4) == 4);
+ Expect.isTrue(jumpTableIntWithDefault(5) == 5);
+ Expect.isTrue(jumpTableIntWithDefault(6) == 6);
+ Expect.isTrue(jumpTableIntWithDefault(7) == 7);
+ Expect.isTrue(jumpTableIntWithDefault(8) == null);
+ Expect.isTrue(jumpTableIntWithDefault(9) == 9);
+ Expect.isTrue(jumpTableIntWithDefault(10) == 10);
+ Expect.isTrue(jumpTableIntWithDefault(11) == 11);
+ Expect.isTrue(jumpTableIntWithDefault(12) == 12);
+ Expect.isTrue(jumpTableIntWithDefault(13) == 13);
+ Expect.isTrue(jumpTableIntWithDefault(14) == 14);
+ Expect.isTrue(jumpTableIntWithDefault(15) == 15);
+ Expect.isTrue(jumpTableIntWithDefault(16) == 16);
+ Expect.isTrue(jumpTableIntWithDefault(17) == null);
+}
+
+/// Small enum that is used to test binary search switches.
+enum S {
+ _0,
+ _1,
+ _2,
+}
+
+/// Large enum that is used to test jump table switches.
+///
+/// Must have enough values to trigger a jump table (currently 16) + 1 so
+/// we can create a jump table switch that is not exhaustive.
+enum L {
+ _0,
+ _1,
+ _2,
+ _3,
+ _4,
+ _5,
+ _6,
+ _7,
+ _8,
+ _9,
+ _10,
+ _11,
+ _12,
+ _13,
+ _14,
+ _15,
+ _16,
+}
+
+int? duplicateEnum(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._1:
+ return 3;
+ }
+}
+
+int? duplicateInt(int v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 1:
+ return 3;
+ }
+}
+
+int binarySearchEnumExhaustive(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._1:
+ return 1;
+ case S._2:
+ return 2;
+ }
+}
+
+int? binarySearchEnumWithDefault(S? v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._2:
+ return 2;
+ default:
+ return null;
+ }
+}
+
+int? binarySearchEnumHole(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._2:
+ return 2;
+ }
+}
+
+int? binarySearchEnumNoLowerBound(S v) {
+ switch (v) {
+ case S._1:
+ return 1;
+ case S._2:
+ return 2;
+ }
+}
+
+int? binarySearchEnumNoUpperBound(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._1:
+ return 1;
+ }
+}
+
+int? binarySearchInt(int v) {
+ switch (v) {
+ case -1:
+ return -1;
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ }
+}
+
+int? binarySearchIntWithDefault(int? v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 2:
+ return 2;
+ default:
+ return null;
+ }
+}
+
+int jumpTableEnumExhaustive(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int? jumpTableEnumWithDefault(L? v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ default:
+ return null;
+ }
+}
+
+int? jumpTableEnumHole(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int? jumpTableEnumNoLowerBound(L v) {
+ switch (v) {
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int? jumpTableEnumNoUpperBound(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ }
+}
+
+int? jumpTableInt(int v) {
+ switch (v) {
+ case -1:
+ return -1;
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 3:
+ return 3;
+ case 4:
+ return 4;
+ case 5:
+ return 5;
+ case 6:
+ return 6;
+ case 7:
+ return 7;
+ case 8:
+ return 8;
+ case 9:
+ return 9;
+ case 10:
+ return 10;
+ case 11:
+ return 11;
+ case 12:
+ return 12;
+ case 13:
+ return 13;
+ case 14:
+ return 14;
+ }
+}
+
+int? jumpTableIntWithDefault(int? v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 3:
+ return 3;
+ case 4:
+ return 4;
+ case 5:
+ return 5;
+ case 6:
+ return 6;
+ case 7:
+ return 7;
+ case 9:
+ return 9;
+ case 10:
+ return 10;
+ case 11:
+ return 11;
+ case 12:
+ return 12;
+ case 13:
+ return 13;
+ case 14:
+ return 14;
+ case 15:
+ return 15;
+ case 16:
+ return 16;
+ default:
+ return null;
+ }
+}
diff --git a/runtime/tests/vm/dart_2/optimized_switch_test.dart b/runtime/tests/vm/dart_2/optimized_switch_test.dart
new file mode 100644
index 0000000..ed63635
--- /dev/null
+++ b/runtime/tests/vm/dart_2/optimized_switch_test.dart
@@ -0,0 +1,579 @@
+// Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// @dart = 2.9
+
+// Test switches that use binary search or a jump table to dispatch cases.
+
+import 'package:expect/expect.dart';
+
+void main() {
+ Expect.isTrue(duplicateEnum(L._0) == 0);
+ Expect.isTrue(duplicateEnum(L._1) == 1);
+ Expect.isTrue(duplicateEnum(L._2) == 2);
+ Expect.isTrue(duplicateEnum(L._3) == null);
+
+ Expect.isTrue(duplicateInt(0) == 0);
+ Expect.isTrue(duplicateInt(1) == 1);
+ Expect.isTrue(duplicateInt(2) == 2);
+ Expect.isTrue(duplicateInt(3) == null);
+
+ Expect.isTrue(binarySearchEnumExhaustive(S._0) == 0);
+ Expect.isTrue(binarySearchEnumExhaustive(S._1) == 1);
+ Expect.isTrue(binarySearchEnumExhaustive(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumWithDefault(null) == null);
+ Expect.isTrue(binarySearchEnumWithDefault(S._0) == 0);
+ Expect.isTrue(binarySearchEnumWithDefault(S._1) == null);
+ Expect.isTrue(binarySearchEnumWithDefault(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumHole(S._0) == 0);
+ Expect.isTrue(binarySearchEnumHole(S._1) == null);
+ Expect.isTrue(binarySearchEnumHole(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._0) == null);
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._1) == 1);
+ Expect.isTrue(binarySearchEnumNoLowerBound(S._2) == 2);
+
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._0) == 0);
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._1) == 1);
+ Expect.isTrue(binarySearchEnumNoUpperBound(S._2) == null);
+
+ Expect.isTrue(binarySearchInt(-2) == null);
+ Expect.isTrue(binarySearchInt(-1) == -1);
+ Expect.isTrue(binarySearchInt(0) == 0);
+ Expect.isTrue(binarySearchInt(1) == 1);
+ Expect.isTrue(binarySearchInt(2) == null);
+
+ Expect.isTrue(binarySearchIntWithDefault(null) == null);
+ Expect.isTrue(binarySearchIntWithDefault(-1) == null);
+ Expect.isTrue(binarySearchIntWithDefault(0) == 0);
+ Expect.isTrue(binarySearchIntWithDefault(1) == null);
+ Expect.isTrue(binarySearchIntWithDefault(2) == 2);
+ Expect.isTrue(binarySearchIntWithDefault(3) == null);
+
+ Expect.isTrue(jumpTableEnumExhaustive(L._0) == 0);
+ Expect.isTrue(jumpTableEnumExhaustive(L._1) == 1);
+ Expect.isTrue(jumpTableEnumExhaustive(L._2) == 2);
+ Expect.isTrue(jumpTableEnumExhaustive(L._3) == 3);
+ Expect.isTrue(jumpTableEnumExhaustive(L._4) == 4);
+ Expect.isTrue(jumpTableEnumExhaustive(L._5) == 5);
+ Expect.isTrue(jumpTableEnumExhaustive(L._6) == 6);
+ Expect.isTrue(jumpTableEnumExhaustive(L._7) == 7);
+ Expect.isTrue(jumpTableEnumExhaustive(L._8) == 8);
+ Expect.isTrue(jumpTableEnumExhaustive(L._9) == 9);
+ Expect.isTrue(jumpTableEnumExhaustive(L._10) == 10);
+ Expect.isTrue(jumpTableEnumExhaustive(L._11) == 11);
+ Expect.isTrue(jumpTableEnumExhaustive(L._12) == 12);
+ Expect.isTrue(jumpTableEnumExhaustive(L._13) == 13);
+ Expect.isTrue(jumpTableEnumExhaustive(L._14) == 14);
+ Expect.isTrue(jumpTableEnumExhaustive(L._15) == 15);
+ Expect.isTrue(jumpTableEnumExhaustive(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumWithDefault(null) == null);
+ Expect.isTrue(jumpTableEnumWithDefault(L._0) == 0);
+ Expect.isTrue(jumpTableEnumWithDefault(L._1) == 1);
+ Expect.isTrue(jumpTableEnumWithDefault(L._2) == 2);
+ Expect.isTrue(jumpTableEnumWithDefault(L._3) == 3);
+ Expect.isTrue(jumpTableEnumWithDefault(L._4) == 4);
+ Expect.isTrue(jumpTableEnumWithDefault(L._5) == 5);
+ Expect.isTrue(jumpTableEnumWithDefault(L._6) == 6);
+ Expect.isTrue(jumpTableEnumWithDefault(L._7) == 7);
+ Expect.isTrue(jumpTableEnumWithDefault(L._8) == null);
+ Expect.isTrue(jumpTableEnumWithDefault(L._9) == 9);
+ Expect.isTrue(jumpTableEnumWithDefault(L._10) == 10);
+ Expect.isTrue(jumpTableEnumWithDefault(L._11) == 11);
+ Expect.isTrue(jumpTableEnumWithDefault(L._12) == 12);
+ Expect.isTrue(jumpTableEnumWithDefault(L._13) == 13);
+ Expect.isTrue(jumpTableEnumWithDefault(L._14) == 14);
+ Expect.isTrue(jumpTableEnumWithDefault(L._15) == 15);
+ Expect.isTrue(jumpTableEnumWithDefault(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumHole(L._0) == 0);
+ Expect.isTrue(jumpTableEnumHole(L._1) == null);
+ Expect.isTrue(jumpTableEnumHole(L._2) == 2);
+ Expect.isTrue(jumpTableEnumHole(L._3) == 3);
+ Expect.isTrue(jumpTableEnumHole(L._4) == 4);
+ Expect.isTrue(jumpTableEnumHole(L._5) == 5);
+ Expect.isTrue(jumpTableEnumHole(L._6) == 6);
+ Expect.isTrue(jumpTableEnumHole(L._7) == 7);
+ Expect.isTrue(jumpTableEnumHole(L._8) == 8);
+ Expect.isTrue(jumpTableEnumHole(L._9) == 9);
+ Expect.isTrue(jumpTableEnumHole(L._10) == 10);
+ Expect.isTrue(jumpTableEnumHole(L._11) == 11);
+ Expect.isTrue(jumpTableEnumHole(L._12) == 12);
+ Expect.isTrue(jumpTableEnumHole(L._13) == 13);
+ Expect.isTrue(jumpTableEnumHole(L._14) == 14);
+ Expect.isTrue(jumpTableEnumHole(L._15) == 15);
+ Expect.isTrue(jumpTableEnumHole(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._0) == null);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._1) == 1);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._2) == 2);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._3) == 3);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._4) == 4);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._5) == 5);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._6) == 6);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._7) == 7);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._8) == 8);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._9) == 9);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._10) == 10);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._11) == 11);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._12) == 12);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._13) == 13);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._14) == 14);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._15) == 15);
+ Expect.isTrue(jumpTableEnumNoLowerBound(L._16) == 16);
+
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._0) == 0);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._1) == 1);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._2) == 2);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._3) == 3);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._4) == 4);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._5) == 5);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._6) == 6);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._7) == 7);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._8) == 8);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._9) == 9);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._10) == 10);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._11) == 11);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._12) == 12);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._13) == 13);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._14) == 14);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._15) == 15);
+ Expect.isTrue(jumpTableEnumNoUpperBound(L._16) == null);
+
+ Expect.isTrue(jumpTableInt(-2) == null);
+ Expect.isTrue(jumpTableInt(-1) == -1);
+ Expect.isTrue(jumpTableInt(0) == 0);
+ Expect.isTrue(jumpTableInt(1) == 1);
+ Expect.isTrue(jumpTableInt(2) == 2);
+ Expect.isTrue(jumpTableInt(3) == 3);
+ Expect.isTrue(jumpTableInt(4) == 4);
+ Expect.isTrue(jumpTableInt(5) == 5);
+ Expect.isTrue(jumpTableInt(6) == 6);
+ Expect.isTrue(jumpTableInt(7) == 7);
+ Expect.isTrue(jumpTableInt(8) == 8);
+ Expect.isTrue(jumpTableInt(9) == 9);
+ Expect.isTrue(jumpTableInt(10) == 10);
+ Expect.isTrue(jumpTableInt(11) == 11);
+ Expect.isTrue(jumpTableInt(12) == 12);
+ Expect.isTrue(jumpTableInt(13) == 13);
+ Expect.isTrue(jumpTableInt(14) == 14);
+ Expect.isTrue(jumpTableInt(15) == null);
+
+ Expect.isTrue(jumpTableIntWithDefault(null) == null);
+ Expect.isTrue(jumpTableIntWithDefault(-1) == null);
+ Expect.isTrue(jumpTableIntWithDefault(0) == 0);
+ Expect.isTrue(jumpTableIntWithDefault(1) == 1);
+ Expect.isTrue(jumpTableIntWithDefault(2) == 2);
+ Expect.isTrue(jumpTableIntWithDefault(3) == 3);
+ Expect.isTrue(jumpTableIntWithDefault(4) == 4);
+ Expect.isTrue(jumpTableIntWithDefault(5) == 5);
+ Expect.isTrue(jumpTableIntWithDefault(6) == 6);
+ Expect.isTrue(jumpTableIntWithDefault(7) == 7);
+ Expect.isTrue(jumpTableIntWithDefault(8) == null);
+ Expect.isTrue(jumpTableIntWithDefault(9) == 9);
+ Expect.isTrue(jumpTableIntWithDefault(10) == 10);
+ Expect.isTrue(jumpTableIntWithDefault(11) == 11);
+ Expect.isTrue(jumpTableIntWithDefault(12) == 12);
+ Expect.isTrue(jumpTableIntWithDefault(13) == 13);
+ Expect.isTrue(jumpTableIntWithDefault(14) == 14);
+ Expect.isTrue(jumpTableIntWithDefault(15) == 15);
+ Expect.isTrue(jumpTableIntWithDefault(16) == 16);
+ Expect.isTrue(jumpTableIntWithDefault(17) == null);
+}
+
+/// Small enum that is used to test binary search switches.
+enum S {
+ _0,
+ _1,
+ _2,
+}
+
+/// Large enum that is used to test jump table switches.
+///
+/// Must have enough values to trigger a jump table (currently 16) + 1 so
+/// we can create a jump table switch that is not exhaustive.
+enum L {
+ _0,
+ _1,
+ _2,
+ _3,
+ _4,
+ _5,
+ _6,
+ _7,
+ _8,
+ _9,
+ _10,
+ _11,
+ _12,
+ _13,
+ _14,
+ _15,
+ _16,
+}
+
+int duplicateEnum(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._1:
+ return 3;
+ }
+}
+
+int duplicateInt(int v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 1:
+ return 3;
+ }
+}
+
+int binarySearchEnumExhaustive(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._1:
+ return 1;
+ case S._2:
+ return 2;
+ }
+}
+
+int binarySearchEnumWithDefault(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._2:
+ return 2;
+ default:
+ return null;
+ }
+}
+
+int binarySearchEnumHole(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._2:
+ return 2;
+ }
+}
+
+int binarySearchEnumNoLowerBound(S v) {
+ switch (v) {
+ case S._1:
+ return 1;
+ case S._2:
+ return 2;
+ }
+}
+
+int binarySearchEnumNoUpperBound(S v) {
+ switch (v) {
+ case S._0:
+ return 0;
+ case S._1:
+ return 1;
+ }
+}
+
+int binarySearchInt(int v) {
+ switch (v) {
+ case -1:
+ return -1;
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ }
+}
+
+int binarySearchIntWithDefault(int v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 2:
+ return 2;
+ default:
+ return null;
+ }
+}
+
+int jumpTableEnumExhaustive(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int jumpTableEnumWithDefault(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ default:
+ return null;
+ }
+}
+
+int jumpTableEnumHole(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int jumpTableEnumNoLowerBound(L v) {
+ switch (v) {
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ case L._16:
+ return 16;
+ }
+}
+
+int jumpTableEnumNoUpperBound(L v) {
+ switch (v) {
+ case L._0:
+ return 0;
+ case L._1:
+ return 1;
+ case L._2:
+ return 2;
+ case L._3:
+ return 3;
+ case L._4:
+ return 4;
+ case L._5:
+ return 5;
+ case L._6:
+ return 6;
+ case L._7:
+ return 7;
+ case L._8:
+ return 8;
+ case L._9:
+ return 9;
+ case L._10:
+ return 10;
+ case L._11:
+ return 11;
+ case L._12:
+ return 12;
+ case L._13:
+ return 13;
+ case L._14:
+ return 14;
+ case L._15:
+ return 15;
+ }
+}
+
+int jumpTableInt(int v) {
+ switch (v) {
+ case -1:
+ return -1;
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 3:
+ return 3;
+ case 4:
+ return 4;
+ case 5:
+ return 5;
+ case 6:
+ return 6;
+ case 7:
+ return 7;
+ case 8:
+ return 8;
+ case 9:
+ return 9;
+ case 10:
+ return 10;
+ case 11:
+ return 11;
+ case 12:
+ return 12;
+ case 13:
+ return 13;
+ case 14:
+ return 14;
+ }
+}
+
+int jumpTableIntWithDefault(int v) {
+ switch (v) {
+ case 0:
+ return 0;
+ case 1:
+ return 1;
+ case 2:
+ return 2;
+ case 3:
+ return 3;
+ case 4:
+ return 4;
+ case 5:
+ return 5;
+ case 6:
+ return 6;
+ case 7:
+ return 7;
+ case 9:
+ return 9;
+ case 10:
+ return 10;
+ case 11:
+ return 11;
+ case 12:
+ return 12;
+ case 13:
+ return 13;
+ case 14:
+ return 14;
+ case 15:
+ return 15;
+ case 16:
+ return 16;
+ default:
+ return null;
+ }
+}
diff --git a/runtime/vm/compiler/backend/branch_optimizer.cc b/runtime/vm/compiler/backend/branch_optimizer.cc
index 3c58635..23511b4 100644
--- a/runtime/vm/compiler/backend/branch_optimizer.cc
+++ b/runtime/vm/compiler/backend/branch_optimizer.cc
@@ -284,8 +284,10 @@
BranchInstr* branch = pred->last_instruction()->AsBranch();
if (branch == nullptr) {
- // There is no "B_pred" block.
- ASSERT(pred->last_instruction()->IsGraphEntry());
+ // There is no "B_pred" block, or the block is the IndirectGoto
+ // of a switch that uses it as a jump table.
+ ASSERT(pred->last_instruction()->IsGraphEntry() ||
+ pred->last_instruction()->IsIndirectGoto());
continue;
}
diff --git a/runtime/vm/compiler/backend/constant_propagator.cc b/runtime/vm/compiler/backend/constant_propagator.cc
index b021b2e..b2c9ad3 100644
--- a/runtime/vm/compiler/backend/constant_propagator.cc
+++ b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -232,8 +232,10 @@
}
void ConstantPropagator::VisitIndirectGoto(IndirectGotoInstr* instr) {
- for (intptr_t i = 0; i < instr->SuccessorCount(); i++) {
- SetReachable(instr->SuccessorAt(i));
+ if (reachable_->Contains(instr->GetBlock()->preorder_number())) {
+ for (intptr_t i = 0; i < instr->SuccessorCount(); i++) {
+ SetReachable(instr->SuccessorAt(i));
+ }
}
}
@@ -1502,7 +1504,11 @@
}
static bool IsEmptyBlock(BlockEntryInstr* block) {
- return block->next()->IsGoto() && !HasPhis(block) &&
+ // A block containing a goto to itself forms an infinite loop.
+ // We don't consider this an empty block to handle the edge-case where code
+ // reduces to an infinite loop.
+ return block->next()->IsGoto() &&
+ block->next()->AsGoto()->successor() != block && !HasPhis(block) &&
!block->IsIndirectEntry();
}
diff --git a/runtime/vm/compiler/frontend/kernel_binary_flowgraph.cc b/runtime/vm/compiler/frontend/kernel_binary_flowgraph.cc
index 921a465..6c5b044 100644
--- a/runtime/vm/compiler/frontend/kernel_binary_flowgraph.cc
+++ b/runtime/vm/compiler/frontend/kernel_binary_flowgraph.cc
@@ -1472,7 +1472,8 @@
return flow_graph_builder_->LoadLocal(variable);
}
-Fragment StreamingFlowGraphBuilder::IndirectGoto(intptr_t target_count) {
+IndirectGotoInstr* StreamingFlowGraphBuilder::IndirectGoto(
+ intptr_t target_count) {
return flow_graph_builder_->IndirectGoto(target_count);
}
@@ -3347,8 +3348,8 @@
instructions += BuildArguments(
&argument_names, &argument_count,
/* positional_argument_count = */ nullptr); // read arguments.
- ++argument_count; // include receiver
- SkipInterfaceMemberNameReference(); // interfaceTargetReference
+ ++argument_count; // include receiver
+ SkipInterfaceMemberNameReference(); // interfaceTargetReference
return instructions +
StaticCall(position, Function::ZoneHandle(Z, function.ptr()),
argument_count, argument_names, ICData::kSuper,
@@ -4276,7 +4277,7 @@
const TokenPosition pos = ReadPosition(); // read file offset.
if (position != nullptr) *position = pos;
- ReadPosition(); // read file end offset.
+ ReadPosition(); // read file end offset.
intptr_t list_length = ReadListLength(); // read number of statements.
for (intptr_t i = 0; i < list_length; ++i) {
@@ -4414,7 +4415,7 @@
const TokenPosition pos = ReadPosition(); // read position.
if (position != nullptr) *position = pos;
- intptr_t target_index = ReadUInt(); // read target index.
+ intptr_t target_index = ReadUInt(); // read target index.
TryFinallyBlock* outer_finally = nullptr;
intptr_t target_context_depth = -1;
@@ -4441,7 +4442,7 @@
const TokenPosition pos = ReadPosition(); // read position.
if (position != nullptr) *position = pos;
- TestFragment condition = TranslateConditionForControl(); // read condition.
+ TestFragment condition = TranslateConditionForControl(); // read condition.
const Fragment body = BuildStatementWithBranchCoverage(); // read body
Fragment body_entry(condition.CreateTrueSuccessor(flow_graph_builder_));
@@ -4582,7 +4583,7 @@
const TokenPosition pos = ReadPosition(); // read position.
if (position != nullptr) *position = pos;
- TokenPosition body_position = ReadPosition(); // read body position.
+ TokenPosition body_position = ReadPosition(); // read body position.
intptr_t variable_kernel_position = ReaderOffset() + data_program_offset_;
SkipVariableDeclaration(); // read variable.
@@ -4640,150 +4641,186 @@
TokenPosition* position) {
const TokenPosition pos = ReadPosition(); // read position.
if (position != nullptr) *position = pos;
- ReadBool(); // read exhaustive flag.
+ const bool is_exhaustive = ReadBool(); // read exhaustive flag.
// We need the number of cases. So start by getting that, then go back.
- intptr_t offset = ReaderOffset();
- SkipExpression(); // temporarily skip condition
- int case_count = ReadListLength(); // read number of cases.
+ const intptr_t offset = ReaderOffset();
+ SkipExpression(); // temporarily skip condition
+ intptr_t case_count = ReadListLength(); // read number of cases.
SetOffset(offset);
SwitchBlock block(flow_graph_builder_, case_count);
- // Instead of using a variable we should reuse the expression on the stack,
- // since it won't be assigned again, we don't need phi nodes.
- Fragment head_instructions = BuildExpression(); // read condition.
- head_instructions +=
+ Fragment instructions = BuildExpression(); // read condition.
+ instructions +=
StoreLocal(TokenPosition::kNoSource, scopes()->switch_variable);
- head_instructions += Drop();
+ instructions += Drop();
case_count = ReadListLength(); // read number of cases.
- // Phase 1: Generate bodies and try to find out whether a body will be target
+ SwitchHelper helper(Z, pos, is_exhaustive, &block, case_count);
+
+ // Build the case bodies and collect the expressions into the helper
+ // for the next step.
+ for (intptr_t i = 0; i < case_count; ++i) {
+ helper.AddCaseBody(BuildSwitchCase(&helper, i));
+ }
+
+ // Build the code to dispatch to the case bodies.
+ switch (helper.SelectDispatchStrategy()) {
+ case kSwitchDispatchAuto:
+ UNREACHABLE();
+ case kSwitchDispatchLinearScan:
+ instructions += BuildLinearScanSwitch(&helper);
+ break;
+ case kSwitchDispatchBinarySearch:
+ instructions += BuildBinarySearchSwitch(&helper);
+ break;
+ case kSwitchDispatchJumpTable:
+ instructions += BuildJumpTableSwitch(&helper);
+ break;
+ }
+
+ return instructions;
+}
+
+Fragment StreamingFlowGraphBuilder::BuildSwitchCase(SwitchHelper* helper,
+ intptr_t case_index) {
+ // Generate case body and try to find out whether the body will be target
// of a jump due to:
// * `continue case_label`
// * `case e1: case e2: body`
- Fragment* body_fragments = Z->Alloc<Fragment>(case_count);
- intptr_t* case_expression_offsets = Z->Alloc<intptr_t>(case_count);
- int default_case = -1;
+ //
+ // Also collect switch expressions into helper.
- for (intptr_t i = 0; i < case_count; ++i) {
- case_expression_offsets[i] = ReaderOffset();
- int expression_count = ReadListLength(); // read number of expressions.
- for (intptr_t j = 0; j < expression_count; ++j) {
- ReadPosition(); // read jth position.
- SkipExpression(); // read jth expression.
- }
- bool is_default = ReadBool(); // read is_default.
- if (is_default) default_case = i;
- Fragment& body_fragment = body_fragments[i] =
- BuildStatementWithBranchCoverage(); // read body.
-
- if (body_fragment.entry == nullptr) {
- // Make a NOP in order to ensure linking works properly.
- body_fragment = NullConstant();
- body_fragment += Drop();
- }
-
- // The Dart language specification mandates fall-throughs in [SwitchCase]es
- // to be runtime errors.
- if (!is_default && body_fragment.is_open() && (i < (case_count - 1))) {
- const Class& klass = Class::ZoneHandle(
- Z, Library::LookupCoreClass(Symbols::FallThroughError()));
- ASSERT(!klass.IsNull());
- const auto& error = klass.EnsureIsFinalized(thread());
- ASSERT(error == Error::null());
-
- GrowableHandlePtrArray<const String> pieces(Z, 3);
- pieces.Add(Symbols::FallThroughError());
- pieces.Add(Symbols::Dot());
- pieces.Add(H.DartSymbolObfuscate("_create"));
-
- const Function& constructor = Function::ZoneHandle(
- Z, klass.LookupConstructorAllowPrivate(String::ZoneHandle(
- Z, Symbols::FromConcatAll(H.thread(), pieces))));
- ASSERT(!constructor.IsNull());
- const String& url = H.DartSymbolPlain(
- parsed_function()->function().ToLibNamePrefixedQualifiedCString());
-
- // Create instance of _FallThroughError
- body_fragment += AllocateObject(TokenPosition::kNoSource, klass, 0);
- LocalVariable* instance = MakeTemporary();
-
- // Call _FallThroughError._create constructor.
- body_fragment += LoadLocal(instance); // this
- body_fragment += Constant(url); // url
- body_fragment += NullConstant(); // line
-
- body_fragment +=
- StaticCall(TokenPosition::kNoSource, constructor, 3, ICData::kStatic);
- body_fragment += Drop();
-
- // Throw the exception
- body_fragment += ThrowException(TokenPosition::kNoSource);
- body_fragment += Drop();
- }
-
- // If there is an implicit fall-through we have one [SwitchCase] and
- // multiple expressions, e.g.
- //
- // switch(expr) {
- // case a:
- // case b:
- // <stmt-body>
- // }
- //
- // This means that the <stmt-body> will have more than 1 incoming edge (one
- // from `a == expr` and one from `a != expr && b == expr`). The
- // `block.Destination()` records the additional jump.
- if (expression_count > 1) {
- block.DestinationDirect(i);
- }
+ const int expression_count = ReadListLength(); // read number of expressions.
+ for (intptr_t j = 0; j < expression_count; ++j) {
+ const TokenPosition pos = ReadPosition(); // read jth position.
+ // read jth expression.
+ const Instance& value =
+ Instance::ZoneHandle(Z, constant_reader_.ReadConstantExpression());
+ helper->AddExpression(case_index, pos, value);
}
- intptr_t end_offset = ReaderOffset();
+ const bool is_default = ReadBool(); // read is_default.
+ if (is_default) helper->set_default_case(case_index);
+ Fragment body_fragment = BuildStatementWithBranchCoverage(); // read body.
- // Phase 2: Generate everything except the real bodies:
- // * jump directly to a body (if there is no jumper)
- // * jump to a wrapper block which jumps to the body (if there is a jumper)
- Fragment current_instructions = head_instructions;
+ if (body_fragment.entry == nullptr) {
+ // Make a NOP in order to ensure linking works properly.
+ body_fragment = NullConstant();
+ body_fragment += Drop();
+ }
+
+ // The Dart language specification mandates fall-throughs in [SwitchCase]es
+ // to be runtime errors.
+ if (!is_default && body_fragment.is_open() &&
+ (case_index < (helper->case_count() - 1))) {
+ const Class& klass = Class::ZoneHandle(
+ Z, Library::LookupCoreClass(Symbols::FallThroughError()));
+ ASSERT(!klass.IsNull());
+ const auto& error = klass.EnsureIsFinalized(thread());
+ ASSERT(error == Error::null());
+
+ GrowableHandlePtrArray<const String> pieces(Z, 3);
+ pieces.Add(Symbols::FallThroughError());
+ pieces.Add(Symbols::Dot());
+ pieces.Add(H.DartSymbolObfuscate("_create"));
+
+ const Function& constructor = Function::ZoneHandle(
+ Z, klass.LookupConstructorAllowPrivate(String::ZoneHandle(
+ Z, Symbols::FromConcatAll(H.thread(), pieces))));
+ ASSERT(!constructor.IsNull());
+ const String& url = H.DartSymbolPlain(
+ parsed_function()->function().ToLibNamePrefixedQualifiedCString());
+
+ // Create instance of _FallThroughError
+ body_fragment += AllocateObject(TokenPosition::kNoSource, klass, 0);
+ LocalVariable* instance = MakeTemporary();
+
+ // Call _FallThroughError._create constructor.
+ body_fragment += LoadLocal(instance); // this
+ body_fragment += Constant(url); // url
+ body_fragment += NullConstant(); // line
+
+ body_fragment +=
+ StaticCall(TokenPosition::kNoSource, constructor, 3, ICData::kStatic);
+ body_fragment += Drop();
+
+ // Throw the exception
+ body_fragment += ThrowException(TokenPosition::kNoSource);
+ body_fragment += Drop();
+ }
+
+ // If there is an implicit fall-through we have one [SwitchCase] and
+ // multiple expressions, e.g.
+ //
+ // switch(expr) {
+ // case a:
+ // case b:
+ // <stmt-body>
+ // }
+ //
+ // This means that the <stmt-body> will have more than 1 incoming edge (one
+ // from `a == expr` and one from `a != expr && b == expr`). The
+ // `block.Destination()` records the additional jump.
+ if (expression_count > 1) {
+ helper->switch_block()->DestinationDirect(case_index);
+ }
+
+ return body_fragment;
+}
+
+Fragment StreamingFlowGraphBuilder::BuildLinearScanSwitch(
+ SwitchHelper* helper) {
+ // Build a switch using a sequence of equality tests.
+ //
+ // From a test:
+ // * jump directly to a body, if there is no jumper.
+ // * jump to a wrapper block which jumps to the body, if there is a jumper.
+
+ SwitchBlock* block = helper->switch_block();
+ const intptr_t case_count = helper->case_count();
+ const intptr_t default_case = helper->default_case();
+ const GrowableArray<Fragment>& case_bodies = helper->case_bodies();
+ Fragment current_instructions;
+ intptr_t expression_index = 0;
+
for (intptr_t i = 0; i < case_count; ++i) {
- SetOffset(case_expression_offsets[i]);
- int expression_count = ReadListLength(); // read length of expressions.
-
if (i == default_case) {
ASSERT(i == (case_count - 1));
- if (block.HadJumper(i)) {
+ if (block->HadJumper(i)) {
// There are several branches to the body, so we will make a goto to
// the join block (and prepend a join instruction to the real body).
- JoinEntryInstr* join = block.DestinationDirect(i);
+ JoinEntryInstr* join = block->DestinationDirect(i);
current_instructions += Goto(join);
current_instructions = Fragment(current_instructions.entry, join);
- current_instructions += body_fragments[i];
+ current_instructions += case_bodies[i];
} else {
- current_instructions += body_fragments[i];
+ current_instructions += case_bodies[i];
}
} else {
JoinEntryInstr* body_join = nullptr;
- if (block.HadJumper(i)) {
- body_join = block.DestinationDirect(i);
- body_fragments[i] = Fragment(body_join) + body_fragments[i];
+ if (block->HadJumper(i)) {
+ body_join = block->DestinationDirect(i);
+ case_bodies[i] = Fragment(body_join) + case_bodies[i];
}
+ const intptr_t expression_count = helper->case_expression_counts().At(i);
for (intptr_t j = 0; j < expression_count; ++j) {
TargetEntryInstr* then;
TargetEntryInstr* otherwise;
- const TokenPosition pos = ReadPosition(); // read jth position.
- current_instructions += Constant(
- Instance::ZoneHandle(Z, constant_reader_.ReadConstantExpression()));
+ const SwitchExpression& expression =
+ helper->expressions().At(expression_index++);
+ current_instructions += Constant(expression.value());
current_instructions += LoadLocal(scopes()->switch_variable);
- current_instructions +=
- InstanceCall(pos, Symbols::EqualOperator(), Token::kEQ,
- /*argument_count=*/2,
- /*checked_argument_count=*/2);
+ current_instructions += InstanceCall(
+ expression.position(), Symbols::EqualOperator(), Token::kEQ,
+ /*argument_count=*/2,
+ /*checked_argument_count=*/2);
current_instructions += BranchIfTrue(&then, &otherwise, false);
Fragment then_fragment(then);
@@ -4794,23 +4831,23 @@
// join instruction).
then_fragment += Goto(body_join);
} else {
- // There is only a signle branch to the body, so we will just append
+ // There is only a single branch to the body, so we will just append
// the body fragment.
- then_fragment += body_fragments[i];
+ then_fragment += case_bodies[i];
}
- current_instructions = Fragment(otherwise);
+ current_instructions = Fragment(current_instructions.entry, otherwise);
}
}
}
- if (case_count > 0 && default_case < 0) {
+ if (case_count > 0 && !helper->has_default()) {
// There is no default, which means we have an open [current_instructions]
// (which is a [TargetEntryInstruction] for the last "otherwise" branch).
//
// Furthermore the last [SwitchCase] can be open as well. If so, we need
// to join these two.
- Fragment& last_body = body_fragments[case_count - 1];
+ Fragment& last_body = case_bodies[case_count - 1];
if (last_body.is_open()) {
ASSERT(current_instructions.is_open());
ASSERT(current_instructions.current->IsTargetEntry());
@@ -4820,7 +4857,7 @@
current_instructions += Goto(join);
last_body += Goto(join);
- current_instructions = Fragment(join);
+ current_instructions = Fragment(current_instructions.entry, join);
}
} else {
// All non-default cases will be closed (i.e. break/continue/throw/return)
@@ -4828,8 +4865,354 @@
// default case.
}
- SetOffset(end_offset);
- return Fragment(head_instructions.entry, current_instructions.current);
+ return current_instructions;
+}
+
+Fragment StreamingFlowGraphBuilder::BuildOptimizedSwitchPrelude(
+ SwitchHelper* helper,
+ JoinEntryInstr* join) {
+ const TokenPosition pos = helper->position();
+
+ // We need to check that the switch variable is of the correct type.
+ // If it is not, we go to [join] which is either the default case or
+ // the exit of the switch statement.
+
+ TargetEntryInstr* then_entry;
+ TargetEntryInstr* otherwise_entry;
+
+ const AbstractType& expression_type =
+ AbstractType::ZoneHandle(Z, helper->expression_class().RareType());
+ ASSERT(dart::SimpleInstanceOfType(expression_type));
+
+ Fragment instructions;
+ instructions += LoadLocal(scopes()->switch_variable);
+ instructions += Constant(expression_type);
+ instructions += InstanceCall(
+ pos, Library::PrivateCoreLibName(Symbols::_simpleInstanceOf()),
+ Token::kIS, /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ instructions += BranchIfTrue(&then_entry, &otherwise_entry, /*negate=*/false);
+
+ Fragment otherwise_instructions(otherwise_entry);
+ otherwise_instructions += Goto(join);
+
+ instructions = Fragment(instructions.entry, then_entry);
+
+ if (helper->is_enum_switch()) {
+ // For an enum switch, we need to load the enum index from the switch
+ // variable.
+
+ instructions += LoadLocal(scopes()->switch_variable);
+ const Field& enum_index_field =
+ Field::ZoneHandle(Z, IG->object_store()->enum_index_field());
+ instructions += B->LoadField(enum_index_field, /*calls_initializer=*/false);
+ instructions += StoreLocal(pos, scopes()->switch_variable);
+ instructions += Drop();
+ }
+
+ return instructions;
+}
+
+Fragment StreamingFlowGraphBuilder::BuildBinarySearchSwitch(
+ SwitchHelper* helper) {
+ // * We build a binary tree of conditional branches where each branch bisects
+ // the remaining cases.
+ // * At holes in the switch expression range we need to add additional
+ // bound checks.
+ // * At each leaf we add the body of the case or a goto, if the case has
+ // jumpers.
+ // * Leafs at the bounds of the switch expression range might need to
+ // do a bound check.
+
+ SwitchBlock* block = helper->switch_block();
+ const intptr_t case_count = helper->case_count();
+ const intptr_t default_case = helper->default_case();
+ const GrowableArray<Fragment>& case_bodies = helper->case_bodies();
+ const intptr_t expression_count = helper->expressions().length();
+ const GrowableArray<SwitchExpression*>& sorted_expressions =
+ helper->sorted_expressions();
+ TargetEntryInstr* then_entry;
+ TargetEntryInstr* otherwise_entry;
+
+ // Entry to the default case or the exit of the switch, if there is no
+ // default case.
+ JoinEntryInstr* join;
+ if (helper->has_default()) {
+ join = block->DestinationDirect(default_case);
+ } else {
+ join = BuildJoinEntry();
+ }
+
+ Fragment join_instructions(join);
+ if (helper->has_default()) {
+ join_instructions += case_bodies.At(default_case);
+ }
+
+ Fragment current_instructions = BuildOptimizedSwitchPrelude(helper, join);
+
+ GrowableArray<SwitchRange> stack;
+ stack.Add(SwitchRange::Branch(0, expression_count - 1, current_instructions));
+
+ while (!stack.is_empty()) {
+ const SwitchRange range = stack.RemoveLast();
+ Fragment branch_instructions = range.branch_instructions();
+
+ if (range.is_leaf()) {
+ const intptr_t expression_index = range.min();
+ const SwitchExpression& expression =
+ *sorted_expressions.At(expression_index);
+
+ if (!range.is_bounds_checked() &&
+ ((helper->RequiresLowerBoundCheck() && expression_index == 0) ||
+ (helper->RequiresUpperBoundCheck() &&
+ expression_index == expression_count - 1))) {
+ // This leaf needs a bound check.
+
+ branch_instructions += LoadLocal(scopes()->switch_variable);
+ branch_instructions += Constant(expression.integer());
+ branch_instructions +=
+ StrictCompare(expression.position(), Token::kEQ_STRICT,
+ /*number_check=*/true);
+ branch_instructions +=
+ BranchIfTrue(&then_entry, &otherwise_entry, /*negate=*/false);
+
+ Fragment otherwise_instructions(otherwise_entry);
+ otherwise_instructions += Goto(join);
+
+ stack.Add(SwitchRange::Leaf(expression_index, Fragment(then_entry),
+ /*is_bounds_checked=*/true));
+ } else {
+ // We are at a leaf where we can add the body of the case or a goto to
+ // [join].
+
+ const intptr_t case_index = expression.case_index();
+
+ if (case_index == default_case) {
+ branch_instructions += Goto(join);
+ } else {
+ if (block->HadJumper(case_index)) {
+ JoinEntryInstr* join = block->DestinationDirect(case_index);
+ branch_instructions += Goto(join);
+
+ if (join->next() == nullptr) {
+ // The first time we reach an expression that jumps to a case
+ // body we emit the body.
+ branch_instructions = Fragment(join);
+ branch_instructions += case_bodies.At(case_index);
+ }
+ } else {
+ branch_instructions += case_bodies.At(case_index);
+ }
+
+ if (!helper->has_default() && case_index == case_count - 1) {
+ if (branch_instructions.is_open()) {
+ branch_instructions += Goto(join);
+ }
+ }
+ }
+
+ ASSERT(branch_instructions.is_closed());
+ }
+ } else {
+ // Add a conditional to bisect the range.
+
+ const intptr_t middle = range.min() + (range.max() - range.min()) / 2;
+ const intptr_t next = middle + 1;
+ const SwitchExpression& middle_expression =
+ *sorted_expressions.At(middle);
+ const SwitchExpression& next_expression = *sorted_expressions.At(next);
+
+ branch_instructions += LoadLocal(scopes()->switch_variable);
+ branch_instructions += Constant(middle_expression.integer());
+ branch_instructions +=
+ InstanceCall(middle_expression.position(),
+ Symbols::LessEqualOperator(), Token::kLTE,
+ /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ branch_instructions +=
+ BranchIfTrue(&then_entry, &otherwise_entry, /*negate=*/false);
+
+ Fragment lower_branch_instructions(then_entry);
+ Fragment upper_branch_instructions(otherwise_entry);
+
+ if (next_expression.integer().AsInt64Value() >
+ middle_expression.integer().AsInt64Value() + 1) {
+ // The upper branch is not contiguous with the lower branch.
+ // Before continuing in the upper branch we add a bound check.
+
+ upper_branch_instructions += LoadLocal(scopes()->switch_variable);
+ upper_branch_instructions += Constant(next_expression.integer());
+ upper_branch_instructions +=
+ InstanceCall(next_expression.position(),
+ Symbols::GreaterEqualOperator(), Token::kGTE,
+ /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ upper_branch_instructions +=
+ BranchIfTrue(&then_entry, &otherwise_entry, /*negate=*/false);
+
+ Fragment otherwise_instructions(otherwise_entry);
+ otherwise_instructions += Goto(join);
+
+ upper_branch_instructions = Fragment(then_entry);
+ }
+
+ stack.Add(
+ SwitchRange::Branch(next, range.max(), upper_branch_instructions));
+ stack.Add(
+ SwitchRange::Branch(range.min(), middle, lower_branch_instructions));
+ }
+ }
+
+ return Fragment(current_instructions.entry, join_instructions.current);
+}
+
+Fragment StreamingFlowGraphBuilder::BuildJumpTableSwitch(SwitchHelper* helper) {
+ // * If input value is not integer or enum value, goto default case or
+ // switch exit.
+ // * If value is enum value, load its index.
+ // * If input integer is outside of jump table range, goto default case
+ // or switch exit.
+ // * Jump to case with jump table.
+ // * For each expression, add entry to jump to case.
+ // * For each hole in the integer range, add entry to jump to default
+ // cause or switch exit.
+
+ SwitchBlock* block = helper->switch_block();
+ const TokenPosition pos = helper->position();
+ const intptr_t case_count = helper->case_count();
+ const intptr_t default_case = helper->default_case();
+ const GrowableArray<Fragment>& case_bodies = helper->case_bodies();
+ const Integer& expression_min = helper->expression_min();
+ const Integer& expression_max = helper->expression_max();
+ TargetEntryInstr* then_entry;
+ TargetEntryInstr* otherwise_entry;
+
+ // Entry to the default case or the exit of the switch, if there is no
+ // default case.
+ JoinEntryInstr* join;
+ if (helper->has_default()) {
+ join = block->DestinationDirect(default_case);
+ } else {
+ join = BuildJoinEntry();
+ }
+
+ Fragment join_instructions(join);
+
+ Fragment current_instructions = BuildOptimizedSwitchPrelude(helper, join);
+
+ if (helper->RequiresLowerBoundCheck()) {
+ current_instructions += LoadLocal(scopes()->switch_variable);
+ current_instructions += Constant(expression_min);
+ current_instructions += InstanceCall(pos, Symbols::GreaterEqualOperator(),
+ Token::kGTE, /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ current_instructions += BranchIfTrue(&then_entry, &otherwise_entry,
+ /*negate=*/false);
+ Fragment otherwise_instructions(otherwise_entry);
+ otherwise_instructions += Goto(join);
+
+ current_instructions = Fragment(current_instructions.entry, then_entry);
+ }
+
+ if (helper->RequiresUpperBoundCheck()) {
+ current_instructions += LoadLocal(scopes()->switch_variable);
+ current_instructions += Constant(expression_max);
+ current_instructions += InstanceCall(pos, Symbols::LessEqualOperator(),
+ Token::kLTE, /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ current_instructions += BranchIfTrue(&then_entry, &otherwise_entry,
+ /*negate=*/false);
+ Fragment otherwise_instructions(otherwise_entry);
+ otherwise_instructions += Goto(join);
+
+ current_instructions = Fragment(current_instructions.entry, then_entry);
+ }
+
+ current_instructions += LoadLocal(scopes()->switch_variable);
+
+ if (!expression_min.IsZero()) {
+ // Adjust for the range of the jump table, which starts at 0.
+ current_instructions += Constant(expression_min);
+ current_instructions +=
+ InstanceCall(pos, Symbols::Minus(), Token::kSUB, /*argument_count=*/2,
+ /*checked_argument_count=*/2);
+ }
+
+ const intptr_t table_size = helper->ExpressionRange();
+ IndirectGotoInstr* indirect_goto = IndirectGoto(table_size);
+ current_instructions <<= indirect_goto;
+ current_instructions = current_instructions.closed();
+
+ GrowableArray<TargetEntryInstr*> table_entries(table_size);
+ table_entries.FillWith(nullptr, 0, table_size);
+
+ // Generate the jump table entries for the switch cases.
+ intptr_t expression_index = 0;
+ for (intptr_t i = 0; i < case_count; ++i) {
+ const int expression_count = helper->case_expression_counts().At(i);
+
+ // Generate jump table entries for each case expression.
+ if (i != default_case) {
+ for (intptr_t j = 0; j < expression_count; ++j) {
+ const SwitchExpression& expression =
+ helper->expressions().At(expression_index++);
+ const intptr_t table_offset =
+ expression.integer().AsInt64Value() - expression_min.AsInt64Value();
+
+ IndirectEntryInstr* indirect_entry =
+ B->BuildIndirectEntry(table_offset, CurrentTryIndex());
+ Fragment indirect_entry_instructions(indirect_entry);
+ indirect_entry_instructions += Goto(block->DestinationDirect(i));
+
+ TargetEntryInstr* entry = B->BuildTargetEntry();
+ Fragment entry_instructions(entry);
+ entry_instructions += Goto(indirect_entry);
+
+ table_entries[table_offset] = entry;
+ }
+ }
+
+ // Connect the case body to its join entry.
+ if (i == default_case) {
+ join_instructions += case_bodies.At(i);
+ } else {
+ Fragment case_instructions(block->DestinationDirect(i));
+ case_instructions += case_bodies.At(i);
+
+ if (i == case_count - 1) {
+ // If the last case is not the default case and it is still open
+ // close it by going to the exit of the switch.
+ if (case_instructions.is_open()) {
+ case_instructions += Goto(join);
+ }
+ }
+
+ ASSERT(case_instructions.is_closed());
+ }
+ }
+
+ // Generate the jump table entries for holes in the integer range.
+ for (intptr_t i = 0; i < table_size; i++) {
+ if (table_entries.At(i) == nullptr) {
+ IndirectEntryInstr* indirect_entry =
+ B->BuildIndirectEntry(i, CurrentTryIndex());
+ Fragment indirect_entry_instructions(indirect_entry);
+ indirect_entry_instructions += Goto(join);
+
+ TargetEntryInstr* entry = flow_graph_builder_->BuildTargetEntry();
+ Fragment entry_instructions(entry);
+ entry_instructions += Goto(indirect_entry);
+
+ table_entries[i] = entry;
+ }
+ }
+
+ // Add the jump table entries to the jump table.
+ for (intptr_t i = 0; i < table_size; i++) {
+ indirect_goto->AddSuccessor(table_entries.At(i));
+ }
+
+ return Fragment(current_instructions.entry, join_instructions.current);
}
Fragment StreamingFlowGraphBuilder::BuildContinueSwitchStatement(
@@ -4837,7 +5220,7 @@
const TokenPosition pos = ReadPosition(); // read position.
if (position != nullptr) *position = pos;
- intptr_t target_index = ReadUInt(); // read target index.
+ intptr_t target_index = ReadUInt(); // read target index.
TryFinallyBlock* outer_finally = nullptr;
intptr_t target_context_depth = -1;
diff --git a/runtime/vm/compiler/frontend/kernel_binary_flowgraph.h b/runtime/vm/compiler/frontend/kernel_binary_flowgraph.h
index 6daf672..22da387 100644
--- a/runtime/vm/compiler/frontend/kernel_binary_flowgraph.h
+++ b/runtime/vm/compiler/frontend/kernel_binary_flowgraph.h
@@ -152,7 +152,7 @@
void InlineBailout(const char* reason);
Fragment DebugStepCheck(TokenPosition position);
Fragment LoadLocal(LocalVariable* variable);
- Fragment IndirectGoto(intptr_t target_count);
+ IndirectGotoInstr* IndirectGoto(intptr_t target_count);
Fragment Return(
TokenPosition position,
intptr_t yield_index = UntaggedPcDescriptors::kInvalidYieldIndex);
@@ -349,6 +349,12 @@
Fragment BuildForStatement(TokenPosition* position);
Fragment BuildForInStatement(bool async, TokenPosition* position);
Fragment BuildSwitchStatement(TokenPosition* position);
+ Fragment BuildSwitchCase(SwitchHelper* helper, intptr_t case_index);
+ Fragment BuildLinearScanSwitch(SwitchHelper* helper);
+ Fragment BuildOptimizedSwitchPrelude(SwitchHelper* helper,
+ JoinEntryInstr* join);
+ Fragment BuildBinarySearchSwitch(SwitchHelper* helper);
+ Fragment BuildJumpTableSwitch(SwitchHelper* helper);
Fragment BuildContinueSwitchStatement(TokenPosition* position);
Fragment BuildIfStatement(TokenPosition* position);
Fragment BuildReturnStatement(TokenPosition* position);
diff --git a/runtime/vm/compiler/frontend/kernel_to_il.cc b/runtime/vm/compiler/frontend/kernel_to_il.cc
index eba8dba..2a553e6 100644
--- a/runtime/vm/compiler/frontend/kernel_to_il.cc
+++ b/runtime/vm/compiler/frontend/kernel_to_il.cc
@@ -45,6 +45,12 @@
false,
"Print huge methods (less optimized)");
+DEFINE_FLAG(int,
+ force_switch_dispatch_type,
+ -1,
+ "Force switch statements to use a particular dispatch type: "
+ "-1=auto, 0=linear scan, 1=binary search, 2=jump table");
+
namespace kernel {
#define Z (zone_)
@@ -476,9 +482,9 @@
}
}
-Fragment FlowGraphBuilder::IndirectGoto(intptr_t target_count) {
+IndirectGotoInstr* FlowGraphBuilder::IndirectGoto(intptr_t target_count) {
Value* index = Pop();
- return Fragment(new (Z) IndirectGotoInstr(target_count, index));
+ return new (Z) IndirectGotoInstr(target_count, index);
}
Fragment FlowGraphBuilder::ThrowLateInitializationError(
@@ -4954,6 +4960,206 @@
return prepend_type_arguments_;
}
+int64_t SwitchHelper::ExpressionRange() const {
+ const int64_t min = expression_min().AsInt64Value();
+ const int64_t max = expression_max().AsInt64Value();
+ ASSERT(min <= max);
+ const uint64_t diff = static_cast<uint64_t>(max) - static_cast<uint64_t>(min);
+ // Saturate to avoid overflow.
+ if (diff > static_cast<uint64_t>(kMaxInt64 - 1)) {
+ return kMaxInt64;
+ }
+ return static_cast<int64_t>(diff + 1);
+}
+
+bool SwitchHelper::RequiresLowerBoundCheck() const {
+ if (is_enum_switch()) {
+ if (expression_min().IsZero()) {
+ // Enum indexes are always positive.
+ return false;
+ }
+ }
+ return true;
+}
+
+bool SwitchHelper::RequiresUpperBoundCheck() const {
+ if (is_enum_switch()) {
+ return has_default() || !is_exhaustive();
+ }
+ return true;
+}
+
+SwitchDispatch SwitchHelper::SelectDispatchStrategy() {
+ // For small to medium-sized switches, binary search is faster than a
+ // jump table.
+ // Please update runtime/tests/vm/dart/optimized_switch_test.dart
+ // when changing this constant.
+ const intptr_t kJumpTableMinExpressions = 16;
+ // This limit comes from IndirectGotoInstr.
+ // Realistically, the current limit should never be hit by any code.
+ const intptr_t kJumpTableMaxSize = kMaxInt32;
+ // Sometimes the switch expressions don't cover a contiguous range.
+ // If the ratio of holes to expressions is too great we fall back to a
+ // binary search to avoid code size explosion.
+ const double kJumpTableMaxHolesRatio = 1.0;
+
+ if (!is_optimizable()) {
+ // The switch is not optimizable, so we can only use linear scan.
+ return kSwitchDispatchLinearScan;
+ }
+
+ if (FLAG_force_switch_dispatch_type == kSwitchDispatchLinearScan) {
+ return kSwitchDispatchLinearScan;
+ }
+
+ PrepareForOptimizedSwitch();
+
+ if (!is_optimizable()) {
+ // While preparing for an optimized switch we might have discovered that
+ // the switch is not optimizable after all.
+ return kSwitchDispatchLinearScan;
+ }
+
+ if (FLAG_force_switch_dispatch_type == kSwitchDispatchBinarySearch) {
+ return kSwitchDispatchBinarySearch;
+ }
+
+ const int64_t range = ExpressionRange();
+ if (range > kJumpTableMaxSize) {
+ return kSwitchDispatchBinarySearch;
+ }
+
+ const intptr_t num_expressions = expressions().length();
+ ASSERT(num_expressions <= range);
+
+ const intptr_t max_holes = num_expressions * kJumpTableMaxHolesRatio;
+ const int64_t holes = range - num_expressions;
+
+ if (FLAG_force_switch_dispatch_type != kSwitchDispatchJumpTable) {
+ if (num_expressions < kJumpTableMinExpressions) {
+ return kSwitchDispatchBinarySearch;
+ }
+
+ if (holes > max_holes) {
+ return kSwitchDispatchBinarySearch;
+ }
+ }
+
+ // After this point we will use a jump table.
+
+ // In the general case, bounds checks are required before a jump table
+ // to handle all possible integer values.
+ // For enums, the set of possible index values is known and much smaller
+ // than the set of all possible integer values. A jump table that covers
+ // either or both bounds of the range of index values requires only one or
+ // no bounds checks.
+ // If the expressions of an enum switch don't cover the full range of
+ // values we can try to extend the jump table to cover the full range, but
+ // not beyond kJumpTableMaxHolesRatio.
+ // The count of enum values is not available when the flow graph is
+ // constructed. The lower bound is always 0 so eliminating the lower
+ // bound check is still possible by extending expression_min to 0.
+ //
+ // In the case of an integer switch we try to extend expression_min to 0
+ // for a different reason.
+ // If the range starts at zero it directly maps to the jump table
+ // and we don't need to adjust the switch variable before the
+ // jump table.
+ if (expression_min().AsInt64Value() > 0) {
+ const intptr_t holes_budget = Utils::Minimum(
+ // Holes still available.
+ max_holes - holes,
+ // Entries left in the jump table.
+ kJumpTableMaxSize - range);
+
+ const int64_t required_holes = expression_min().AsInt64Value();
+ if (required_holes <= holes_budget) {
+ expression_min_ = &Object::smi_zero();
+ }
+ }
+
+ return kSwitchDispatchJumpTable;
+}
+
+void SwitchHelper::PrepareForOptimizedSwitch() {
+ // Find the min and max of integer representations of expressions.
+ // We also populate SwitchExpressions.integer for later use.
+ const Field* enum_index_field = nullptr;
+ for (intptr_t i = 0; i < expressions_.length(); ++i) {
+ SwitchExpression& expression = expressions_[i];
+ sorted_expressions_.Add(&expression);
+
+ const Instance& value = expression.value();
+ const Integer* integer = nullptr;
+ if (is_enum_switch()) {
+ if (enum_index_field == nullptr) {
+ enum_index_field = &Field::Handle(
+ zone_, IsolateGroup::Current()->object_store()->enum_index_field());
+ }
+ integer = &Integer::ZoneHandle(
+ zone_, Integer::RawCast(value.GetField(*enum_index_field)));
+ } else {
+ integer = &Integer::Cast(value);
+ }
+ expression.set_integer(*integer);
+ if (i == 0) {
+ expression_min_ = integer;
+ expression_max_ = integer;
+ } else {
+ if (expression_min_->CompareWith(*integer) > 0) {
+ expression_min_ = integer;
+ }
+ if (expression_max_->CompareWith(*integer) < 0) {
+ expression_max_ = integer;
+ }
+ }
+ }
+
+ // Sort expressions by their integer value.
+ sorted_expressions_.Sort(
+ [](SwitchExpression* const* a, SwitchExpression* const* b) {
+ return (*a)->integer().CompareWith((*b)->integer());
+ });
+
+ // Check that there are no duplicate case expressions.
+ // Duplicate expressions are allowed in switch statements, but
+ // optimized switches don't implemented them.
+ for (intptr_t i = 0; i < sorted_expressions_.length() - 1; ++i) {
+ const SwitchExpression& a = *sorted_expressions_.At(i);
+ const SwitchExpression& b = *sorted_expressions_.At(i + 1);
+ if (a.integer().Equals(b.integer())) {
+ is_optimizable_ = false;
+ break;
+ }
+ }
+}
+
+void SwitchHelper::AddExpression(intptr_t case_index,
+ TokenPosition position,
+ const Instance& value) {
+ case_expression_counts_[case_index]++;
+
+ expressions_.Add(SwitchExpression(case_index, position, value));
+
+ if (is_optimizable_ || expression_class_ == nullptr) {
+ // Check the type of the expression for use in an optimized switch.
+ const Class& value_class = Class::ZoneHandle(zone_, value.clazz());
+ if (expression_class_ == nullptr) {
+ if (value.IsInteger() || value_class.is_enum_class()) {
+ expression_class_ = &value_class;
+ is_optimizable_ = true;
+ } else {
+ // At least one expression (the first) is not suitable for an
+ // optimized switch.
+ is_optimizable_ = false;
+ }
+ } else if (value_class.ptr() != expression_class_->ptr()) {
+ // At least one expression has a different type than the others.
+ is_optimizable_ = false;
+ }
+ }
+}
+
} // namespace kernel
} // namespace dart
diff --git a/runtime/vm/compiler/frontend/kernel_to_il.h b/runtime/vm/compiler/frontend/kernel_to_il.h
index 045750e..69471ce 100644
--- a/runtime/vm/compiler/frontend/kernel_to_il.h
+++ b/runtime/vm/compiler/frontend/kernel_to_il.h
@@ -19,6 +19,7 @@
#include "vm/compiler/frontend/base_flow_graph_builder.h"
#include "vm/compiler/frontend/kernel_translation_helper.h"
#include "vm/compiler/frontend/scope_builder.h"
+#include "vm/object_store.h"
namespace dart {
@@ -193,7 +194,7 @@
Fragment RethrowException(TokenPosition position, int catch_try_index);
Fragment LoadLocal(LocalVariable* variable);
- Fragment IndirectGoto(intptr_t target_count);
+ IndirectGotoInstr* IndirectGoto(intptr_t target_count);
Fragment StoreLateField(const Field& field,
LocalVariable* instance,
LocalVariable* setter_value);
@@ -935,6 +936,190 @@
DISALLOW_COPY_AND_ASSIGN(CatchBlock);
};
+enum SwitchDispatch {
+ kSwitchDispatchAuto = -1,
+ kSwitchDispatchLinearScan,
+ kSwitchDispatchBinarySearch,
+ kSwitchDispatchJumpTable,
+};
+
+// Collected information for a switch expression.
+class SwitchExpression {
+ public:
+ SwitchExpression(intptr_t case_index,
+ TokenPosition position,
+ const Instance& value)
+ : case_index_(case_index), position_(position), value_(&value) {}
+
+ intptr_t case_index() const { return case_index_; }
+ const TokenPosition& position() const { return position_; }
+ // Constant value of the expression.
+ const Instance& value() const { return *value_; }
+
+ // Integer representation of the expression.
+ // For Integers it is the value itself and for Enums it is the index.
+ const Integer& integer() const {
+ ASSERT(integer_ != nullptr);
+ return *integer_;
+ }
+
+ void set_integer(const Integer& integer) {
+ ASSERT(integer_ == nullptr);
+ integer_ = &integer;
+ }
+
+ private:
+ intptr_t case_index_;
+ TokenPosition position_;
+ const Instance* value_;
+ const Integer* integer_ = nullptr;
+};
+
+// A range that is covered by a branch in a binary search switch.
+// Leafs are represented by a range where min == max.
+class SwitchRange {
+ public:
+ static SwitchRange Leaf(intptr_t index,
+ Fragment branch_instructions,
+ bool is_bounds_checked = false) {
+ return SwitchRange(index, index, branch_instructions, is_bounds_checked);
+ }
+
+ static SwitchRange Branch(intptr_t min,
+ intptr_t max,
+ Fragment branch_instructions) {
+ return SwitchRange(min, max, branch_instructions,
+ /*is_bounds_checked=*/false);
+ }
+
+ // min and max are indexes into a sorted array of case expressions.
+ intptr_t min() const { return min_; }
+ intptr_t max() const { return max_; }
+ // The fragment to continue building code for the branch.
+ Fragment branch_instructions() const { return branch_instructions_; }
+ // For leafs, whether the branch is known to be in the bounds of the
+ // overall switch.
+ bool is_bounds_checked() const { return is_bounds_checked_; }
+ bool is_leaf() const { return min_ == max_; }
+
+ private:
+ SwitchRange(intptr_t min,
+ intptr_t max,
+ Fragment branch_instructions,
+ bool is_bounds_checked)
+ : min_(min),
+ max_(max),
+ branch_instructions_(branch_instructions),
+ is_bounds_checked_(is_bounds_checked) {}
+
+ intptr_t min_;
+ intptr_t max_;
+ Fragment branch_instructions_;
+ bool is_bounds_checked_;
+};
+
+// Helper for building flow graph for a switch statement.
+class SwitchHelper {
+ public:
+ SwitchHelper(Zone* zone,
+ TokenPosition position,
+ bool is_exhaustive,
+ SwitchBlock* switch_block,
+ intptr_t case_count)
+ : zone_(zone),
+ position_(position),
+ is_exhaustive_(is_exhaustive),
+ switch_block_(switch_block),
+ case_count_(case_count),
+ case_bodies_(case_count),
+ case_expression_counts_(case_count),
+ expressions_(case_count),
+ sorted_expressions_(case_count) {
+ case_expression_counts_.FillWith(0, 0, case_count);
+ }
+
+ // A switch statement is optimizable if all expression are of the same type
+ // and have integer representations.
+ bool is_optimizable() const { return is_optimizable_; }
+ const TokenPosition& position() const { return position_; }
+ bool is_exhaustive() const { return is_exhaustive_; }
+ SwitchBlock* switch_block() { return switch_block_; }
+ intptr_t case_count() const { return case_count_; }
+
+ // Index of default case.
+ intptr_t default_case() const { return default_case_; }
+ void set_default_case(intptr_t index) {
+ ASSERT(default_case_ == -1);
+ default_case_ = index;
+ }
+
+ const GrowableArray<Fragment>& case_bodies() const { return case_bodies_; }
+
+ // Array of the expression counts for all cases.
+ const GrowableArray<intptr_t>& case_expression_counts() const {
+ return case_expression_counts_;
+ }
+
+ const GrowableArray<SwitchExpression>& expressions() const {
+ return expressions_;
+ }
+
+ const GrowableArray<SwitchExpression*>& sorted_expressions() const {
+ return sorted_expressions_;
+ }
+
+ // The common class of all expressions. The statement must be optimizable.
+ const Class& expression_class() const {
+ ASSERT(expression_class_ != nullptr);
+ return *expression_class_;
+ }
+
+ const Integer& expression_min() const {
+ ASSERT(expression_min_ != nullptr);
+ return *expression_min_;
+ }
+ const Integer& expression_max() const {
+ ASSERT(expression_max_ != nullptr);
+ return *expression_max_;
+ }
+
+ bool has_default() const { return default_case_ >= 0; }
+
+ bool is_enum_switch() const { return expression_class().is_enum_class(); }
+
+ // Returns size of [min..max] range, or kMaxInt64 on overflow.
+ int64_t ExpressionRange() const;
+
+ bool RequiresLowerBoundCheck() const;
+ bool RequiresUpperBoundCheck() const;
+
+ SwitchDispatch SelectDispatchStrategy();
+
+ void AddCaseBody(Fragment body) { case_bodies_.Add(body); }
+
+ void AddExpression(intptr_t case_index,
+ TokenPosition position,
+ const Instance& value);
+
+ private:
+ void PrepareForOptimizedSwitch();
+
+ Zone* zone_;
+ bool is_optimizable_ = false;
+ const TokenPosition position_;
+ const bool is_exhaustive_;
+ SwitchBlock* const switch_block_;
+ const intptr_t case_count_;
+ intptr_t default_case_ = -1;
+ GrowableArray<Fragment> case_bodies_;
+ GrowableArray<intptr_t> case_expression_counts_;
+ GrowableArray<SwitchExpression> expressions_;
+ GrowableArray<SwitchExpression*> sorted_expressions_;
+ const Class* expression_class_ = nullptr;
+ const Integer* expression_min_ = nullptr;
+ const Integer* expression_max_ = nullptr;
+};
+
} // namespace kernel
} // namespace dart
diff --git a/tests/language/switch/backward_jump_test.dart b/tests/language/switch/backward_jump_test.dart
index d4bc491..dbcde00 100644
--- a/tests/language/switch/backward_jump_test.dart
+++ b/tests/language/switch/backward_jump_test.dart
@@ -2,6 +2,11 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import 'package:expect/expect.dart';
main() {
diff --git a/tests/language/switch/empty_block_case_test.dart b/tests/language/switch/empty_block_case_test.dart
index 6edaff4..4fbc593 100644
--- a/tests/language/switch/empty_block_case_test.dart
+++ b/tests/language/switch/empty_block_case_test.dart
@@ -6,6 +6,11 @@
// Test that a case with an empty block does not fall through.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
class EmptyBlockCaseTest {
static testMain() {
var exception = null;
diff --git a/tests/language/switch/fallthru_runtime_test.dart b/tests/language/switch/fallthru_runtime_test.dart
index b1dd57d..373c93f 100644
--- a/tests/language/switch/fallthru_runtime_test.dart
+++ b/tests/language/switch/fallthru_runtime_test.dart
@@ -4,8 +4,14 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Check that FallThroughError is thrown if switch clause does not terminate.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
String test(int n) {
diff --git a/tests/language/switch/infinite_switch_label_test.dart b/tests/language/switch/infinite_switch_label_test.dart
index 7f484cc..816a52c 100644
--- a/tests/language/switch/infinite_switch_label_test.dart
+++ b/tests/language/switch/infinite_switch_label_test.dart
@@ -4,6 +4,11 @@
// Test nested switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
library nested_switch_label;
import "package:expect/expect.dart";
diff --git a/tests/language/switch/label2_test.dart b/tests/language/switch/label2_test.dart
index 612e6a9..e03084d 100644
--- a/tests/language/switch/label2_test.dart
+++ b/tests/language/switch/label2_test.dart
@@ -4,6 +4,11 @@
// Test switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import 'package:expect/expect.dart';
void main() {
diff --git a/tests/language/switch/label_test.dart b/tests/language/switch/label_test.dart
index 290c84f..3a36837 100644
--- a/tests/language/switch/label_test.dart
+++ b/tests/language/switch/label_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class Switcher {
diff --git a/tests/language/switch/nested_switch_label_test.dart b/tests/language/switch/nested_switch_label_test.dart
index 49c2754..efc27a2 100644
--- a/tests/language/switch/nested_switch_label_test.dart
+++ b/tests/language/switch/nested_switch_label_test.dart
@@ -4,6 +4,11 @@
// Test nested switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
library nested_switch_label;
import "package:expect/expect.dart";
diff --git a/tests/language/switch/scope_test.dart b/tests/language/switch/scope_test.dart
index 938a393..4ca4c3b 100644
--- a/tests/language/switch/scope_test.dart
+++ b/tests/language/switch/scope_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test that a new scope is introduced for each switch case.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class SwitchScopeTest {
diff --git a/tests/language/switch/switch6_test.dart b/tests/language/switch/switch6_test.dart
index 43e09dc..32edea5 100644
--- a/tests/language/switch/switch6_test.dart
+++ b/tests/language/switch/switch6_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// The break is in the right scope, http://b/3428700 was agreed upon.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class Switch6Test {
diff --git a/tests/language/switch/switch_test.dart b/tests/language/switch/switch_test.dart
index 032c2b7..3198957 100644
--- a/tests/language/switch/switch_test.dart
+++ b/tests/language/switch/switch_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test switch statement.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class Switcher {
diff --git a/tests/language/switch/try_catch_test.dart b/tests/language/switch/try_catch_test.dart
index beee717..56632e7 100644
--- a/tests/language/switch/try_catch_test.dart
+++ b/tests/language/switch/try_catch_test.dart
@@ -5,6 +5,11 @@
// Regression test for issue 18869: Check that try-catch is working correctly
// inside switch-case clauses.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
test_switch() {
diff --git a/tests/language_2/switch/backward_jump_test.dart b/tests/language_2/switch/backward_jump_test.dart
index d4bc491..dbcde00 100644
--- a/tests/language_2/switch/backward_jump_test.dart
+++ b/tests/language_2/switch/backward_jump_test.dart
@@ -2,6 +2,11 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import 'package:expect/expect.dart';
main() {
diff --git a/tests/language_2/switch/empty_block_case_test.dart b/tests/language_2/switch/empty_block_case_test.dart
index 5e9cfed..9b28adc 100644
--- a/tests/language_2/switch/empty_block_case_test.dart
+++ b/tests/language_2/switch/empty_block_case_test.dart
@@ -8,6 +8,11 @@
// Test that a case with an empty block does not fall through.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
class EmptyBlockCaseTest {
static testMain() {
var exception = null;
diff --git a/tests/language_2/switch/fallthru_runtime_test.dart b/tests/language_2/switch/fallthru_runtime_test.dart
index 3bcdf44c..ca1057f 100644
--- a/tests/language_2/switch/fallthru_runtime_test.dart
+++ b/tests/language_2/switch/fallthru_runtime_test.dart
@@ -8,6 +8,11 @@
// BSD-style license that can be found in the LICENSE file.
// Check that FallThroughError is thrown if switch clause does not terminate.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
String test(int n) {
diff --git a/tests/language_2/switch/infinite_switch_label_test.dart b/tests/language_2/switch/infinite_switch_label_test.dart
index 82de828..2ddfad6 100644
--- a/tests/language_2/switch/infinite_switch_label_test.dart
+++ b/tests/language_2/switch/infinite_switch_label_test.dart
@@ -6,6 +6,11 @@
// Test nested switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
library nested_switch_label;
import "package:expect/expect.dart";
diff --git a/tests/language_2/switch/label2_test.dart b/tests/language_2/switch/label2_test.dart
index d018623..4c2dbb6 100644
--- a/tests/language_2/switch/label2_test.dart
+++ b/tests/language_2/switch/label2_test.dart
@@ -6,6 +6,11 @@
// Test switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import 'package:expect/expect.dart';
void main() {
diff --git a/tests/language_2/switch/label_test.dart b/tests/language_2/switch/label_test.dart
index 601330f..d67bd32 100644
--- a/tests/language_2/switch/label_test.dart
+++ b/tests/language_2/switch/label_test.dart
@@ -1,10 +1,16 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test switch statement using labels.
// @dart = 2.9
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class Switcher {
diff --git a/tests/language_2/switch/nested_switch_label_test.dart b/tests/language_2/switch/nested_switch_label_test.dart
index 55b66b08..1d1b2b5 100644
--- a/tests/language_2/switch/nested_switch_label_test.dart
+++ b/tests/language_2/switch/nested_switch_label_test.dart
@@ -6,6 +6,11 @@
// Test nested switch statement using labels.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
library nested_switch_label;
import "package:expect/expect.dart";
diff --git a/tests/language_2/switch/scope_test.dart b/tests/language_2/switch/scope_test.dart
index c1b6536..c36ec4a 100644
--- a/tests/language_2/switch/scope_test.dart
+++ b/tests/language_2/switch/scope_test.dart
@@ -1,10 +1,16 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test that a new scope is introduced for each switch case.
// @dart = 2.9
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
class SwitchScopeTest {
diff --git a/tests/language_2/switch/switch6_test.dart b/tests/language_2/switch/switch6_test.dart
index 61e9196..9dad116 100644
--- a/tests/language_2/switch/switch6_test.dart
+++ b/tests/language_2/switch/switch6_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// The break is in the right scope, http://b/3428700 was agreed upon.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
// @dart = 2.9
import "package:expect/expect.dart";
diff --git a/tests/language_2/switch/switch_test.dart b/tests/language_2/switch/switch_test.dart
index 52c131c..f190806 100644
--- a/tests/language_2/switch/switch_test.dart
+++ b/tests/language_2/switch/switch_test.dart
@@ -1,8 +1,14 @@
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+
// Test switch statement.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
// @dart = 2.9
import "package:expect/expect.dart";
diff --git a/tests/language_2/switch/try_catch_test.dart b/tests/language_2/switch/try_catch_test.dart
index a37c890..d95e476 100644
--- a/tests/language_2/switch/try_catch_test.dart
+++ b/tests/language_2/switch/try_catch_test.dart
@@ -7,6 +7,11 @@
// Regression test for issue 18869: Check that try-catch is working correctly
// inside switch-case clauses.
+// VMOptions=
+// VMOptions=--force-switch-dispatch-type=0
+// VMOptions=--force-switch-dispatch-type=1
+// VMOptions=--force-switch-dispatch-type=2
+
import "package:expect/expect.dart";
test_switch() {
