| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 import 'sexpr_unstringifier.dart'; | 5 import 'sexpr_unstringifier.dart'; |
| 6 import "package:expect/expect.dart"; | 6 import "package:expect/expect.dart"; |
| 7 import 'package:compiler/src/cps_ir/cps_ir_nodes.dart'; | 7 import 'package:compiler/src/cps_ir/cps_ir_nodes.dart'; |
| 8 import 'package:compiler/src/cps_ir/cps_ir_nodes_sexpr.dart'; | 8 import 'package:compiler/src/cps_ir/cps_ir_nodes_sexpr.dart'; |
| 9 import 'package:compiler/src/cps_ir/optimizers.dart'; | 9 import 'package:compiler/src/cps_ir/optimizers.dart'; |
| 10 | 10 |
| 11 // The 'read in loop' IR tests the most basic case of redundant phi removal | 11 // The 'read in loop' IR tests the most basic case of redundant phi removal |
| 12 // and represents the following source code: | 12 // and represents the following source code: |
| 13 // | 13 // |
| 14 // void main() { | 14 // void main() { |
| 15 // int j = 42; | 15 // int j = 42; |
| 16 // for (int i = 0; i < 2; i++) { | 16 // for (int i = 0; i < 2; i++) { |
| 17 // print(j.toString()); | 17 // print(j.toString()); |
| 18 // } | 18 // } |
| 19 // } | 19 // } |
| 20 | 20 |
| 21 String READ_IN_LOOP_IN = """ | 21 String READ_IN_LOOP_IN = """ |
| 22 (FunctionDefinition main () return () | 22 (FunctionDefinition main () return () |
| 23 (LetPrim v0 (Constant IntConstant(42))) | 23 (LetPrim v0 (Constant (Int 42))) |
| 24 (LetPrim v1 (Constant IntConstant(0))) | 24 (LetPrim v1 (Constant (Int 0))) |
| 25 (LetCont* (k0 v2 v3) | 25 (LetCont* (k0 v2 v3) |
| 26 (LetCont (k1) (LetPrim v4 (Constant NullConstant)) | 26 (LetCont (k1) (LetPrim v4 (Constant (Null))) |
| 27 (InvokeContinuation return v4)) | 27 (InvokeContinuation return v4)) |
| 28 (LetCont (k2) | 28 (LetCont (k2) |
| 29 (LetCont (k3 v5) | 29 (LetCont (k3 v5) |
| 30 (LetCont (k4 v6) (LetPrim v7 (Constant IntConstant(1))) | 30 (LetCont (k4 v6) (LetPrim v7 (Constant (Int 1))) |
| 31 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) | 31 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) |
| 32 (InvokeMethod v3 + v7 k5)) | 32 (InvokeMethod v3 + v7 k5)) |
| 33 (InvokeStatic print v5 k4)) | 33 (InvokeStatic print v5 k4)) |
| 34 (InvokeMethod v2 toString k3)) | 34 (InvokeMethod v2 toString k3)) |
| 35 (LetPrim v9 (Constant IntConstant(2))) | 35 (LetPrim v9 (Constant (Int 2))) |
| 36 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) | 36 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) |
| 37 (InvokeMethod v3 < v9 k6)) | 37 (InvokeMethod v3 < v9 k6)) |
| 38 (InvokeContinuation k0 v0 v1)) | 38 (InvokeContinuation k0 v0 v1)) |
| 39 """; | 39 """; |
| 40 | 40 |
| 41 String READ_IN_LOOP_OUT = """ | 41 String READ_IN_LOOP_OUT = """ |
| 42 (FunctionDefinition main () return () | 42 (FunctionDefinition main () return () |
| 43 (LetPrim v0 (Constant IntConstant(42))) | 43 (LetPrim v0 (Constant (Int 42))) |
| 44 (LetPrim v1 (Constant IntConstant(0))) | 44 (LetPrim v1 (Constant (Int 0))) |
| 45 (LetCont* (k0 v2) | 45 (LetCont* (k0 v2) |
| 46 (LetCont (k1) (LetPrim v3 (Constant NullConstant)) | 46 (LetCont (k1) (LetPrim v3 (Constant (Null))) |
| 47 (InvokeContinuation return v3)) | 47 (InvokeContinuation return v3)) |
| 48 (LetCont (k2) | 48 (LetCont (k2) |
| 49 (LetCont (k3 v4) | 49 (LetCont (k3 v4) |
| 50 (LetCont (k4 v5) (LetPrim v6 (Constant IntConstant(1))) | 50 (LetCont (k4 v5) (LetPrim v6 (Constant (Int 1))) |
| 51 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) | 51 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) |
| 52 (InvokeMethod v2 + v6 k5)) | 52 (InvokeMethod v2 + v6 k5)) |
| 53 (InvokeStatic print v4 k4)) | 53 (InvokeStatic print v4 k4)) |
| 54 (InvokeMethod v0 toString k3)) | 54 (InvokeMethod v0 toString k3)) |
| 55 (LetPrim v8 (Constant IntConstant(2))) | 55 (LetPrim v8 (Constant (Int 2))) |
| 56 (LetCont (k6 v9) (Branch (IsTrue v9) k2 k1)) | 56 (LetCont (k6 v9) (Branch (IsTrue v9) k2 k1)) |
| 57 (InvokeMethod v2 < v8 k6)) | 57 (InvokeMethod v2 < v8 k6)) |
| 58 (InvokeContinuation k0 v1)) | 58 (InvokeContinuation k0 v1)) |
| 59 """; | 59 """; |
| 60 | 60 |
| 61 // The 'inner loop' IR represents the following source code: | 61 // The 'inner loop' IR represents the following source code: |
| 62 // | 62 // |
| 63 // void main() { | 63 // void main() { |
| 64 // int j = 42; | 64 // int j = 42; |
| 65 // for (int i = 0; i < 2; i++) { | 65 // for (int i = 0; i < 2; i++) { |
| 66 // for (int k = 0; k < 2; k++) { | 66 // for (int k = 0; k < 2; k++) { |
| 67 // print(i.toString()); | 67 // print(i.toString()); |
| 68 // } | 68 // } |
| 69 // } | 69 // } |
| 70 // print(j.toString()); | 70 // print(j.toString()); |
| 71 // } | 71 // } |
| 72 // | 72 // |
| 73 // This test case ensures that iterative optimization works: first, v8 and v9 | 73 // This test case ensures that iterative optimization works: first, v8 and v9 |
| 74 // are removed from k5, and only then can k0 be optimized as well. | 74 // are removed from k5, and only then can k0 be optimized as well. |
| 75 | 75 |
| 76 const String INNER_LOOP_IN = """ | 76 const String INNER_LOOP_IN = """ |
| 77 (FunctionDefinition main () return () | 77 (FunctionDefinition main () return () |
| 78 (LetPrim v0 (Constant IntConstant(42))) | 78 (LetPrim v0 (Constant (Int 42))) |
| 79 (LetPrim v1 (Constant IntConstant(0))) | 79 (LetPrim v1 (Constant (Int 0))) |
| 80 (LetCont* (k0 v2 v3) | 80 (LetCont* (k0 v2 v3) |
| 81 (LetCont (k1) | 81 (LetCont (k1) |
| 82 (LetCont (k2 v4) | 82 (LetCont (k2 v4) |
| 83 (LetCont (k3 v5) (LetPrim v6 (Constant NullConstant)) | 83 (LetCont (k3 v5) (LetPrim v6 (Constant (Null))) |
| 84 (InvokeContinuation return v6)) | 84 (InvokeContinuation return v6)) |
| 85 (InvokeStatic print v4 k3)) | 85 (InvokeStatic print v4 k3)) |
| 86 (InvokeMethod v2 toString k2)) | 86 (InvokeMethod v2 toString k2)) |
| 87 (LetCont (k4) (LetPrim v7 (Constant IntConstant(0))) | 87 (LetCont (k4) (LetPrim v7 (Constant (Int 0))) |
| 88 (LetCont* (k5 v8 v9 v10) | 88 (LetCont* (k5 v8 v9 v10) |
| 89 (LetCont (k6) (LetPrim v11 (Constant IntConstant(1))) | 89 (LetCont (k6) (LetPrim v11 (Constant (Int 1))) |
| 90 (LetCont (k7 v12) (InvokeContinuation* k0 v8 v12)) | 90 (LetCont (k7 v12) (InvokeContinuation* k0 v8 v12)) |
| 91 (InvokeMethod v9 + v11 k7)) | 91 (InvokeMethod v9 + v11 k7)) |
| 92 (LetCont (k8) | 92 (LetCont (k8) |
| 93 (LetCont (k9 v13) | 93 (LetCont (k9 v13) |
| 94 (LetCont (k10 v14) (LetPrim v15 (Constant IntConstant(1))) | 94 (LetCont (k10 v14) (LetPrim v15 (Constant (Int 1))) |
| 95 (LetCont (k11 v16) | 95 (LetCont (k11 v16) |
| 96 (InvokeContinuation* k5 v8 v9 v16)) | 96 (InvokeContinuation* k5 v8 v9 v16)) |
| 97 (InvokeMethod v10 + v15 k11)) | 97 (InvokeMethod v10 + v15 k11)) |
| 98 (InvokeStatic print v13 k10)) | 98 (InvokeStatic print v13 k10)) |
| 99 (InvokeMethod v9 toString k9)) | 99 (InvokeMethod v9 toString k9)) |
| 100 (LetPrim v17 (Constant IntConstant(2))) | 100 (LetPrim v17 (Constant (Int 2))) |
| 101 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) | 101 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) |
| 102 (InvokeMethod v10 < v17 k12)) | 102 (InvokeMethod v10 < v17 k12)) |
| 103 (InvokeContinuation k5 v2 v3 v7)) | 103 (InvokeContinuation k5 v2 v3 v7)) |
| 104 (LetPrim v19 (Constant IntConstant(2))) | 104 (LetPrim v19 (Constant (Int 2))) |
| 105 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) | 105 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) |
| 106 (InvokeMethod v3 < v19 k13)) | 106 (InvokeMethod v3 < v19 k13)) |
| 107 (InvokeContinuation k0 v0 v1)) | 107 (InvokeContinuation k0 v0 v1)) |
| 108 """; | 108 """; |
| 109 | 109 |
| 110 const String INNER_LOOP_OUT = """ | 110 const String INNER_LOOP_OUT = """ |
| 111 (FunctionDefinition main () return () | 111 (FunctionDefinition main () return () |
| 112 (LetPrim v0 (Constant IntConstant(42))) | 112 (LetPrim v0 (Constant (Int 42))) |
| 113 (LetPrim v1 (Constant IntConstant(0))) | 113 (LetPrim v1 (Constant (Int 0))) |
| 114 (LetCont* (k0 v2) | 114 (LetCont* (k0 v2) |
| 115 (LetCont (k1) | 115 (LetCont (k1) |
| 116 (LetCont (k2 v3) | 116 (LetCont (k2 v3) |
| 117 (LetCont (k3 v4) (LetPrim v5 (Constant NullConstant)) | 117 (LetCont (k3 v4) (LetPrim v5 (Constant (Null))) |
| 118 (InvokeContinuation return v5)) | 118 (InvokeContinuation return v5)) |
| 119 (InvokeStatic print v3 k3)) | 119 (InvokeStatic print v3 k3)) |
| 120 (InvokeMethod v0 toString k2)) | 120 (InvokeMethod v0 toString k2)) |
| 121 (LetCont (k4) (LetPrim v6 (Constant IntConstant(0))) | 121 (LetCont (k4) (LetPrim v6 (Constant (Int 0))) |
| 122 (LetCont* (k5 v7) | 122 (LetCont* (k5 v7) |
| 123 (LetCont (k6) (LetPrim v8 (Constant IntConstant(1))) | 123 (LetCont (k6) (LetPrim v8 (Constant (Int 1))) |
| 124 (LetCont (k7 v9) (InvokeContinuation* k0 v9)) | 124 (LetCont (k7 v9) (InvokeContinuation* k0 v9)) |
| 125 (InvokeMethod v2 + v8 k7)) | 125 (InvokeMethod v2 + v8 k7)) |
| 126 (LetCont (k8) | 126 (LetCont (k8) |
| 127 (LetCont (k9 v10) | 127 (LetCont (k9 v10) |
| 128 (LetCont (k10 v11) (LetPrim v12 (Constant IntConstant(1))) | 128 (LetCont (k10 v11) (LetPrim v12 (Constant (Int 1))) |
| 129 (LetCont (k11 v13) | 129 (LetCont (k11 v13) |
| 130 (InvokeContinuation* k5 v13)) | 130 (InvokeContinuation* k5 v13)) |
| 131 (InvokeMethod v7 + v12 k11)) | 131 (InvokeMethod v7 + v12 k11)) |
| 132 (InvokeStatic print v10 k10)) | 132 (InvokeStatic print v10 k10)) |
| 133 (InvokeMethod v2 toString k9)) | 133 (InvokeMethod v2 toString k9)) |
| 134 (LetPrim v14 (Constant IntConstant(2))) | 134 (LetPrim v14 (Constant (Int 2))) |
| 135 (LetCont (k12 v15) (Branch (IsTrue v15) k8 k6)) | 135 (LetCont (k12 v15) (Branch (IsTrue v15) k8 k6)) |
| 136 (InvokeMethod v7 < v14 k12)) | 136 (InvokeMethod v7 < v14 k12)) |
| 137 (InvokeContinuation k5 v6)) | 137 (InvokeContinuation k5 v6)) |
| 138 (LetPrim v16 (Constant IntConstant(2))) | 138 (LetPrim v16 (Constant (Int 2))) |
| 139 (LetCont (k13 v17) (Branch (IsTrue v17) k4 k1)) | 139 (LetCont (k13 v17) (Branch (IsTrue v17) k4 k1)) |
| 140 (InvokeMethod v2 < v16 k13)) | 140 (InvokeMethod v2 < v16 k13)) |
| 141 (InvokeContinuation k0 v1)) | 141 (InvokeContinuation k0 v1)) |
| 142 """; | 142 """; |
| 143 | 143 |
| 144 // There are no redundant phis in the 'basic loop' IR, and this test ensures | 144 // There are no redundant phis in the 'basic loop' IR, and this test ensures |
| 145 // simply that the optimization does not alter the IR. It represents the | 145 // simply that the optimization does not alter the IR. It represents the |
| 146 // following program: | 146 // following program: |
| 147 // | 147 // |
| 148 // void main() { | 148 // void main() { |
| 149 // for (int i = 0; i < 2; i++) { | 149 // for (int i = 0; i < 2; i++) { |
| 150 // print(i.toString()); | 150 // print(i.toString()); |
| 151 // } | 151 // } |
| 152 // } | 152 // } |
| 153 | 153 |
| 154 String BASIC_LOOP_IN = """ | 154 String BASIC_LOOP_IN = """ |
| 155 (FunctionDefinition main () return () | 155 (FunctionDefinition main () return () |
| 156 (LetPrim v0 (Constant IntConstant(0))) | 156 (LetPrim v0 (Constant (Int 0))) |
| 157 (LetCont* (k0 v1) | 157 (LetCont* (k0 v1) |
| 158 (LetCont (k1) (LetPrim v2 (Constant NullConstant)) | 158 (LetCont (k1) (LetPrim v2 (Constant (Null))) |
| 159 (InvokeContinuation return v2)) | 159 (InvokeContinuation return v2)) |
| 160 (LetCont (k2) | 160 (LetCont (k2) |
| 161 (LetCont (k3 v3) | 161 (LetCont (k3 v3) |
| 162 (LetCont (k4 v4) (LetPrim v5 (Constant IntConstant(1))) | 162 (LetCont (k4 v4) (LetPrim v5 (Constant (Int 1))) |
| 163 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) | 163 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) |
| 164 (InvokeMethod v1 + v5 k5)) | 164 (InvokeMethod v1 + v5 k5)) |
| 165 (InvokeStatic print v3 k4)) | 165 (InvokeStatic print v3 k4)) |
| 166 (InvokeMethod v1 toString k3)) | 166 (InvokeMethod v1 toString k3)) |
| 167 (LetPrim v7 (Constant IntConstant(2))) | 167 (LetPrim v7 (Constant (Int 2))) |
| 168 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) | 168 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) |
| 169 (InvokeMethod v1 < v7 k6)) | 169 (InvokeMethod v1 < v7 k6)) |
| 170 (InvokeContinuation k0 v0)) | 170 (InvokeContinuation k0 v0)) |
| 171 """; | 171 """; |
| 172 | 172 |
| 173 String BASIC_LOOP_OUT = BASIC_LOOP_IN; | 173 String BASIC_LOOP_OUT = BASIC_LOOP_IN; |
| 174 | 174 |
| 175 // Ensures that proper scoping is preserved, i.e. that the optimized | 175 // Ensures that proper scoping is preserved, i.e. that the optimized |
| 176 // continuation body does reference out of scope primitives. | 176 // continuation body does reference out of scope primitives. |
| 177 // IR written by hand since this case is currently not being generated. | 177 // IR written by hand since this case is currently not being generated. |
| 178 | 178 |
| 179 String SCOPING_IN = """ | 179 String SCOPING_IN = """ |
| 180 (FunctionDefinition main () return () | 180 (FunctionDefinition main () return () |
| 181 (LetCont (k0 v1) | 181 (LetCont (k0 v1) |
| 182 (InvokeStatic print v1 return)) | 182 (InvokeStatic print v1 return)) |
| 183 (LetPrim v0 (Constant IntConstant(0))) | 183 (LetPrim v0 (Constant (Int 0))) |
| 184 (LetPrim v2 (Constant NullConstant)) | 184 (LetPrim v2 (Constant (Null))) |
| 185 (InvokeContinuation k0 v0)) | 185 (InvokeContinuation k0 v0)) |
| 186 """; | 186 """; |
| 187 | 187 |
| 188 String SCOPING_OUT = """ | 188 String SCOPING_OUT = """ |
| 189 (FunctionDefinition main () return () | 189 (FunctionDefinition main () return () |
| 190 (LetPrim v0 (Constant IntConstant(0))) | 190 (LetPrim v0 (Constant (Int 0))) |
| 191 (LetCont (k0) | 191 (LetCont (k0) |
| 192 (InvokeStatic print v0 return)) | 192 (InvokeStatic print v0 return)) |
| 193 (LetPrim v1 (Constant NullConstant)) | 193 (LetPrim v1 (Constant (Null))) |
| 194 (InvokeContinuation k0 )) | 194 (InvokeContinuation k0 )) |
| 195 """; | 195 """; |
| 196 | 196 |
| 197 // Ensures that continuations which are never invoked are not optimized. | 197 // Ensures that continuations which are never invoked are not optimized. |
| 198 // IR written by hand. | 198 // IR written by hand. |
| 199 | 199 |
| 200 String NEVER_INVOKED_IN = """ | 200 String NEVER_INVOKED_IN = """ |
| 201 (FunctionDefinition main () return () | 201 (FunctionDefinition main () return () |
| 202 (LetPrim v0 (Constant IntConstant(0))) | 202 (LetPrim v0 (Constant (Int 0))) |
| 203 (LetCont (k0 v1) | 203 (LetCont (k0 v1) |
| 204 (InvokeStatic print v1 return)) | 204 (InvokeStatic print v1 return)) |
| 205 (InvokeContinuation return v0)) | 205 (InvokeContinuation return v0)) |
| 206 """; | 206 """; |
| 207 | 207 |
| 208 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; | 208 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; |
| 209 | 209 |
| 210 /// Normalizes whitespace by replacing all whitespace sequences by a single | 210 /// Normalizes whitespace by replacing all whitespace sequences by a single |
| 211 /// space and trimming leading and trailing whitespace. | 211 /// space and trimming leading and trailing whitespace. |
| 212 String normalizeSExpr(String input) { | 212 String normalizeSExpr(String input) { |
| (...skipping 16 matching lines...) Expand all Loading... |
| 229 Expect.equals(expected, actual, "Actual:\n$actual"); | 229 Expect.equals(expected, actual, "Actual:\n$actual"); |
| 230 } | 230 } |
| 231 | 231 |
| 232 void main() { | 232 void main() { |
| 233 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); | 233 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); |
| 234 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); | 234 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); |
| 235 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); | 235 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); |
| 236 testRedundantPhi(SCOPING_IN, SCOPING_OUT); | 236 testRedundantPhi(SCOPING_IN, SCOPING_OUT); |
| 237 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); | 237 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); |
| 238 } | 238 } |
| OLD | NEW |