| 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 (Int 42))) | 23 (LetPrim (v0 (Constant (Int 42))) |
| 24 (LetPrim (v1 (Constant (Int 0))) | 24 (LetPrim (v1 (Constant (Int 0))) |
| 25 (LetCont | 25 (LetCont |
| 26 ((rec k0 (v2 v3) | 26 ((rec k0 (v2 v3) |
| 27 (LetCont | 27 (LetCont |
| 28 ((k1 () | 28 ((k1 () |
| 29 (LetPrim (v4 (Constant (Null))) | 29 (LetPrim (v4 (Constant (Null))) |
| 30 (InvokeContinuation return (v4)))) | 30 (InvokeContinuation return (v4)))) |
| 31 (k2 () | 31 (k2 () |
| 32 (LetCont | 32 (LetCont |
| 33 ((k3 (v5) | 33 ((k3 (v5) |
| 34 (LetCont | 34 (LetCont |
| 35 ((k4 (v6) | 35 ((k4 (v6) |
| 36 (LetPrim (v7 (Constant (Int 1))) | 36 (LetPrim (v7 (Constant (Int 1))) |
| 37 (LetCont | 37 (LetCont |
| 38 ((k5 (v8) | 38 ((k5 (v8) |
| 39 (InvokeContinuation rec k0 (v2 v8)))) | 39 (InvokeContinuation rec k0 (v2 v8)))) |
| 40 (InvokeMethod v3 + (v7) k5))))) | 40 (InvokeMethod v3 + (v7) k5))))) |
| 41 (InvokeStatic print (v5) k4)))) | 41 (InvokeStatic print (v5) k4)))) |
| 42 (InvokeMethod v2 toString () k3)))) | 42 (InvokeMethod v2 toString () k3)))) |
| 43 (LetPrim (v9 (Constant (Int 2))) | 43 (LetPrim (v9 (Constant (Int 2))) |
| 44 (LetCont | 44 (LetCont |
| 45 ((k6 (v10) | 45 ((k6 (v10) |
| 46 (Branch (IsTrue v10) k2 k1))) | 46 (Branch (IsTrue v10) k2 k1))) |
| 47 (InvokeMethod v3 < (v9) k6)))))) | 47 (InvokeMethod v3 < (v9) k6)))))) |
| 48 (InvokeContinuation k0 (v0 v1)))))) | 48 (InvokeContinuation k0 (v0 v1)))))) |
| 49 """; | 49 """; |
| 50 | 50 |
| 51 String READ_IN_LOOP_OUT = """ | 51 String READ_IN_LOOP_OUT = """ |
| 52 (FunctionDefinition main () return | 52 (FunctionDefinition main () () return |
| 53 (LetPrim (v0 (Constant (Int 42))) | 53 (LetPrim (v0 (Constant (Int 42))) |
| 54 (LetPrim (v1 (Constant (Int 0))) | 54 (LetPrim (v1 (Constant (Int 0))) |
| 55 (LetCont | 55 (LetCont |
| 56 ((rec k0 (v2) | 56 ((rec k0 (v2) |
| 57 (LetCont | 57 (LetCont |
| 58 ((k1 () | 58 ((k1 () |
| 59 (LetPrim (v3 (Constant (Null))) | 59 (LetPrim (v3 (Constant (Null))) |
| 60 (InvokeContinuation return (v3)))) | 60 (InvokeContinuation return (v3)))) |
| 61 (k2 () | 61 (k2 () |
| 62 (LetCont | 62 (LetCont |
| (...skipping 24 matching lines...) Expand all Loading... |
| 87 // print(i.toString()); | 87 // print(i.toString()); |
| 88 // } | 88 // } |
| 89 // } | 89 // } |
| 90 // print(j.toString()); | 90 // print(j.toString()); |
| 91 // } | 91 // } |
| 92 // | 92 // |
| 93 // This test case ensures that iterative optimization works: first, v8 and v9 | 93 // This test case ensures that iterative optimization works: first, v8 and v9 |
| 94 // are removed from k5, and only then can k0 be optimized as well. | 94 // are removed from k5, and only then can k0 be optimized as well. |
| 95 | 95 |
| 96 const String INNER_LOOP_IN = """ | 96 const String INNER_LOOP_IN = """ |
| 97 (FunctionDefinition main () return | 97 (FunctionDefinition main () () return |
| 98 (LetPrim (v0 (Constant (Int 42))) | 98 (LetPrim (v0 (Constant (Int 42))) |
| 99 (LetPrim (v1 (Constant (Int 0))) | 99 (LetPrim (v1 (Constant (Int 0))) |
| 100 (LetCont | 100 (LetCont |
| 101 ((rec k0 (v2 v3) | 101 ((rec k0 (v2 v3) |
| 102 (LetCont | 102 (LetCont |
| 103 ((k1 () | 103 ((k1 () |
| 104 (LetCont | 104 (LetCont |
| 105 ((k2 (v4) | 105 ((k2 (v4) |
| 106 (LetCont | 106 (LetCont |
| 107 ((k3 (v5) | 107 ((k3 (v5) |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 140 (InvokeContinuation k5 (v2 v3 v7)))))) | 140 (InvokeContinuation k5 (v2 v3 v7)))))) |
| 141 (LetPrim (v19 (Constant (Int 2))) | 141 (LetPrim (v19 (Constant (Int 2))) |
| 142 (LetCont | 142 (LetCont |
| 143 ((k13 (v20) | 143 ((k13 (v20) |
| 144 (Branch (IsTrue v20) k4 k1))) | 144 (Branch (IsTrue v20) k4 k1))) |
| 145 (InvokeMethod v3 < (v19) k13)))))) | 145 (InvokeMethod v3 < (v19) k13)))))) |
| 146 (InvokeContinuation k0 (v0 v1)))))) | 146 (InvokeContinuation k0 (v0 v1)))))) |
| 147 """; | 147 """; |
| 148 | 148 |
| 149 const String INNER_LOOP_OUT = """ | 149 const String INNER_LOOP_OUT = """ |
| 150 (FunctionDefinition main () return | 150 (FunctionDefinition main () () return |
| 151 (LetPrim (v0 (Constant (Int 42))) | 151 (LetPrim (v0 (Constant (Int 42))) |
| 152 (LetPrim (v1 (Constant (Int 0))) | 152 (LetPrim (v1 (Constant (Int 0))) |
| 153 (LetCont | 153 (LetCont |
| 154 ((rec k0 (v2) | 154 ((rec k0 (v2) |
| 155 (LetCont | 155 (LetCont |
| 156 ((k1 () | 156 ((k1 () |
| 157 (LetCont | 157 (LetCont |
| 158 ((k2 (v3) | 158 ((k2 (v3) |
| 159 (LetCont | 159 (LetCont |
| 160 ((k3 (v4) | 160 ((k3 (v4) |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 203 // simply that the optimization does not alter the IR. It represents the | 203 // simply that the optimization does not alter the IR. It represents the |
| 204 // following program: | 204 // following program: |
| 205 // | 205 // |
| 206 // void main() { | 206 // void main() { |
| 207 // for (int i = 0; i < 2; i++) { | 207 // for (int i = 0; i < 2; i++) { |
| 208 // print(i.toString()); | 208 // print(i.toString()); |
| 209 // } | 209 // } |
| 210 // } | 210 // } |
| 211 | 211 |
| 212 String BASIC_LOOP_IN = """ | 212 String BASIC_LOOP_IN = """ |
| 213 (FunctionDefinition main () return | 213 (FunctionDefinition main () () return |
| 214 (LetPrim (v0 (Constant (Int 0))) | 214 (LetPrim (v0 (Constant (Int 0))) |
| 215 (LetCont | 215 (LetCont |
| 216 ((rec k0 (v1) | 216 ((rec k0 (v1) |
| 217 (LetCont | 217 (LetCont |
| 218 ((k1 () | 218 ((k1 () |
| 219 (LetPrim (v2 (Constant (Null))) | 219 (LetPrim (v2 (Constant (Null))) |
| 220 (InvokeContinuation return (v2)))) | 220 (InvokeContinuation return (v2)))) |
| 221 (k2 () | 221 (k2 () |
| 222 (LetCont | 222 (LetCont |
| 223 ((k3 (v3) | 223 ((k3 (v3) |
| (...skipping 14 matching lines...) Expand all Loading... |
| 238 (InvokeContinuation k0 (v0))))) | 238 (InvokeContinuation k0 (v0))))) |
| 239 """; | 239 """; |
| 240 | 240 |
| 241 String BASIC_LOOP_OUT = BASIC_LOOP_IN; | 241 String BASIC_LOOP_OUT = BASIC_LOOP_IN; |
| 242 | 242 |
| 243 // Ensures that proper scoping is preserved, i.e. that the optimized | 243 // Ensures that proper scoping is preserved, i.e. that the optimized |
| 244 // continuation body does reference out of scope primitives. | 244 // continuation body does reference out of scope primitives. |
| 245 // IR written by hand since this case is currently not being generated. | 245 // IR written by hand since this case is currently not being generated. |
| 246 | 246 |
| 247 String SCOPING_IN = """ | 247 String SCOPING_IN = """ |
| 248 (FunctionDefinition main () return | 248 (FunctionDefinition main () () return |
| 249 (LetCont | 249 (LetCont |
| 250 ((k0 (v1) | 250 ((k0 (v1) |
| 251 (InvokeStatic print (v1) return))) | 251 (InvokeStatic print (v1) return))) |
| 252 (LetPrim (v0 (Constant (Int 0))) | 252 (LetPrim (v0 (Constant (Int 0))) |
| 253 (LetPrim (v2 (Constant (Null))) | 253 (LetPrim (v2 (Constant (Null))) |
| 254 (InvokeContinuation k0 (v0)))))) | 254 (InvokeContinuation k0 (v0)))))) |
| 255 """; | 255 """; |
| 256 | 256 |
| 257 String SCOPING_OUT = """ | 257 String SCOPING_OUT = """ |
| 258 (FunctionDefinition main () return | 258 (FunctionDefinition main () () return |
| 259 (LetPrim (v0 (Constant (Int 0))) | 259 (LetPrim (v0 (Constant (Int 0))) |
| 260 (LetCont | 260 (LetCont |
| 261 ((k0 () | 261 ((k0 () |
| 262 (InvokeStatic print (v0) return))) | 262 (InvokeStatic print (v0) return))) |
| 263 (LetPrim (v1 (Constant (Null))) | 263 (LetPrim (v1 (Constant (Null))) |
| 264 (InvokeContinuation k0 ()))))) | 264 (InvokeContinuation k0 ()))))) |
| 265 """; | 265 """; |
| 266 | 266 |
| 267 // Ensures that continuations which are never invoked are not optimized. | 267 // Ensures that continuations which are never invoked are not optimized. |
| 268 // IR written by hand. | 268 // IR written by hand. |
| 269 | 269 |
| 270 String NEVER_INVOKED_IN = """ | 270 String NEVER_INVOKED_IN = """ |
| 271 (FunctionDefinition main () return | 271 (FunctionDefinition main () () return |
| 272 (LetPrim (v0 (Constant (Int 0))) | 272 (LetPrim (v0 (Constant (Int 0))) |
| 273 (LetCont | 273 (LetCont |
| 274 ((k0 (v1) | 274 ((k0 (v1) |
| 275 (InvokeStatic print (v1) return))) | 275 (InvokeStatic print (v1) return))) |
| 276 (InvokeContinuation return (v0))))) | 276 (InvokeContinuation return (v0))))) |
| 277 """; | 277 """; |
| 278 | 278 |
| 279 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; | 279 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; |
| 280 | 280 |
| 281 /// Normalizes whitespace by replacing all whitespace sequences by a single | 281 /// Normalizes whitespace by replacing all whitespace sequences by a single |
| (...skipping 18 matching lines...) Expand all Loading... |
| 300 Expect.equals(expected, actual, "Actual:\n$actual"); | 300 Expect.equals(expected, actual, "Actual:\n$actual"); |
| 301 } | 301 } |
| 302 | 302 |
| 303 void main() { | 303 void main() { |
| 304 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); | 304 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); |
| 305 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); | 305 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); |
| 306 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); | 306 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); |
| 307 testRedundantPhi(SCOPING_IN, SCOPING_OUT); | 307 testRedundantPhi(SCOPING_IN, SCOPING_OUT); |
| 308 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); | 308 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); |
| 309 } | 309 } |
| OLD | NEW |