| 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) (LetPrim v0 (Constant IntConstant(42))) | 22 (FunctionDefinition main () return () |
| 23 (LetPrim v0 (Constant IntConstant(42))) |
| 23 (LetPrim v1 (Constant IntConstant(0))) | 24 (LetPrim v1 (Constant IntConstant(0))) |
| 24 (LetCont* (k0 v2 v3) | 25 (LetCont* (k0 v2 v3) |
| 25 (LetCont (k1) (LetPrim v4 (Constant NullConstant)) | 26 (LetCont (k1) (LetPrim v4 (Constant NullConstant)) |
| 26 (InvokeContinuation return v4)) | 27 (InvokeContinuation return v4)) |
| 27 (LetCont (k2) | 28 (LetCont (k2) |
| 28 (LetCont (k3 v5) | 29 (LetCont (k3 v5) |
| 29 (LetCont (k4 v6) (LetPrim v7 (Constant IntConstant(1))) | 30 (LetCont (k4 v6) (LetPrim v7 (Constant IntConstant(1))) |
| 30 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) | 31 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) |
| 31 (InvokeMethod v3 + v7 k5)) | 32 (InvokeMethod v3 + v7 k5)) |
| 32 (InvokeStatic print v5 k4)) | 33 (InvokeStatic print v5 k4)) |
| 33 (InvokeMethod v2 toString k3)) | 34 (InvokeMethod v2 toString k3)) |
| 34 (LetPrim v9 (Constant IntConstant(2))) | 35 (LetPrim v9 (Constant IntConstant(2))) |
| 35 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) | 36 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) |
| 36 (InvokeMethod v3 < v9 k6)) | 37 (InvokeMethod v3 < v9 k6)) |
| 37 (InvokeContinuation k0 v0 v1)) | 38 (InvokeContinuation k0 v0 v1)) |
| 38 """; | 39 """; |
| 39 | 40 |
| 40 String READ_IN_LOOP_OUT = """ | 41 String READ_IN_LOOP_OUT = """ |
| 41 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(42))) | 42 (FunctionDefinition main () return () |
| 43 (LetPrim v0 (Constant IntConstant(42))) |
| 42 (LetPrim v1 (Constant IntConstant(0))) | 44 (LetPrim v1 (Constant IntConstant(0))) |
| 43 (LetCont* (k0 v2) | 45 (LetCont* (k0 v2) |
| 44 (LetCont (k1) (LetPrim v3 (Constant NullConstant)) | 46 (LetCont (k1) (LetPrim v3 (Constant NullConstant)) |
| 45 (InvokeContinuation return v3)) | 47 (InvokeContinuation return v3)) |
| 46 (LetCont (k2) | 48 (LetCont (k2) |
| 47 (LetCont (k3 v4) | 49 (LetCont (k3 v4) |
| 48 (LetCont (k4 v5) (LetPrim v6 (Constant IntConstant(1))) | 50 (LetCont (k4 v5) (LetPrim v6 (Constant IntConstant(1))) |
| 49 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) | 51 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) |
| 50 (InvokeMethod v2 + v6 k5)) | 52 (InvokeMethod v2 + v6 k5)) |
| 51 (InvokeStatic print v4 k4)) | 53 (InvokeStatic print v4 k4)) |
| (...skipping 13 matching lines...) Expand all Loading... |
| 65 // print(i.toString()); | 67 // print(i.toString()); |
| 66 // } | 68 // } |
| 67 // } | 69 // } |
| 68 // print(j.toString()); | 70 // print(j.toString()); |
| 69 // } | 71 // } |
| 70 // | 72 // |
| 71 // 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 |
| 72 // 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. |
| 73 | 75 |
| 74 const String INNER_LOOP_IN = """ | 76 const String INNER_LOOP_IN = """ |
| 75 (FunctionDefinition main (return) (LetPrim v0 (Constant IntConstant(42))) | 77 (FunctionDefinition main () return () |
| 78 (LetPrim v0 (Constant IntConstant(42))) |
| 76 (LetPrim v1 (Constant IntConstant(0))) | 79 (LetPrim v1 (Constant IntConstant(0))) |
| 77 (LetCont* (k0 v2 v3) | 80 (LetCont* (k0 v2 v3) |
| 78 (LetCont (k1) | 81 (LetCont (k1) |
| 79 (LetCont (k2 v4) | 82 (LetCont (k2 v4) |
| 80 (LetCont (k3 v5) (LetPrim v6 (Constant NullConstant)) | 83 (LetCont (k3 v5) (LetPrim v6 (Constant NullConstant)) |
| 81 (InvokeContinuation return v6)) | 84 (InvokeContinuation return v6)) |
| 82 (InvokeStatic print v4 k3)) | 85 (InvokeStatic print v4 k3)) |
| 83 (InvokeMethod v2 toString k2)) | 86 (InvokeMethod v2 toString k2)) |
| 84 (LetCont (k4) (LetPrim v7 (Constant IntConstant(0))) | 87 (LetCont (k4) (LetPrim v7 (Constant IntConstant(0))) |
| 85 (LetCont* (k5 v8 v9 v10) | 88 (LetCont* (k5 v8 v9 v10) |
| (...skipping 12 matching lines...) Expand all Loading... |
| 98 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) | 101 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) |
| 99 (InvokeMethod v10 < v17 k12)) | 102 (InvokeMethod v10 < v17 k12)) |
| 100 (InvokeContinuation k5 v2 v3 v7)) | 103 (InvokeContinuation k5 v2 v3 v7)) |
| 101 (LetPrim v19 (Constant IntConstant(2))) | 104 (LetPrim v19 (Constant IntConstant(2))) |
| 102 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) | 105 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) |
| 103 (InvokeMethod v3 < v19 k13)) | 106 (InvokeMethod v3 < v19 k13)) |
| 104 (InvokeContinuation k0 v0 v1)) | 107 (InvokeContinuation k0 v0 v1)) |
| 105 """; | 108 """; |
| 106 | 109 |
| 107 const String INNER_LOOP_OUT = """ | 110 const String INNER_LOOP_OUT = """ |
| 108 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(42))) | 111 (FunctionDefinition main () return () |
| 112 (LetPrim v0 (Constant IntConstant(42))) |
| 109 (LetPrim v1 (Constant IntConstant(0))) | 113 (LetPrim v1 (Constant IntConstant(0))) |
| 110 (LetCont* (k0 v2) | 114 (LetCont* (k0 v2) |
| 111 (LetCont (k1) | 115 (LetCont (k1) |
| 112 (LetCont (k2 v3) | 116 (LetCont (k2 v3) |
| 113 (LetCont (k3 v4) (LetPrim v5 (Constant NullConstant)) | 117 (LetCont (k3 v4) (LetPrim v5 (Constant NullConstant)) |
| 114 (InvokeContinuation return v5)) | 118 (InvokeContinuation return v5)) |
| 115 (InvokeStatic print v3 k3)) | 119 (InvokeStatic print v3 k3)) |
| 116 (InvokeMethod v0 toString k2)) | 120 (InvokeMethod v0 toString k2)) |
| 117 (LetCont (k4) (LetPrim v6 (Constant IntConstant(0))) | 121 (LetCont (k4) (LetPrim v6 (Constant IntConstant(0))) |
| 118 (LetCont* (k5 v7) | 122 (LetCont* (k5 v7) |
| (...skipping 22 matching lines...) Expand all Loading... |
| 141 // 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 |
| 142 // following program: | 146 // following program: |
| 143 // | 147 // |
| 144 // void main() { | 148 // void main() { |
| 145 // for (int i = 0; i < 2; i++) { | 149 // for (int i = 0; i < 2; i++) { |
| 146 // print(i.toString()); | 150 // print(i.toString()); |
| 147 // } | 151 // } |
| 148 // } | 152 // } |
| 149 | 153 |
| 150 String BASIC_LOOP_IN = """ | 154 String BASIC_LOOP_IN = """ |
| 151 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(0))) | 155 (FunctionDefinition main () return () |
| 156 (LetPrim v0 (Constant IntConstant(0))) |
| 152 (LetCont* (k0 v1) | 157 (LetCont* (k0 v1) |
| 153 (LetCont (k1) (LetPrim v2 (Constant NullConstant)) | 158 (LetCont (k1) (LetPrim v2 (Constant NullConstant)) |
| 154 (InvokeContinuation return v2)) | 159 (InvokeContinuation return v2)) |
| 155 (LetCont (k2) | 160 (LetCont (k2) |
| 156 (LetCont (k3 v3) | 161 (LetCont (k3 v3) |
| 157 (LetCont (k4 v4) (LetPrim v5 (Constant IntConstant(1))) | 162 (LetCont (k4 v4) (LetPrim v5 (Constant IntConstant(1))) |
| 158 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) | 163 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) |
| 159 (InvokeMethod v1 + v5 k5)) | 164 (InvokeMethod v1 + v5 k5)) |
| 160 (InvokeStatic print v3 k4)) | 165 (InvokeStatic print v3 k4)) |
| 161 (InvokeMethod v1 toString k3)) | 166 (InvokeMethod v1 toString k3)) |
| 162 (LetPrim v7 (Constant IntConstant(2))) | 167 (LetPrim v7 (Constant IntConstant(2))) |
| 163 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) | 168 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) |
| 164 (InvokeMethod v1 < v7 k6)) | 169 (InvokeMethod v1 < v7 k6)) |
| 165 (InvokeContinuation k0 v0)) | 170 (InvokeContinuation k0 v0)) |
| 166 """; | 171 """; |
| 167 | 172 |
| 168 String BASIC_LOOP_OUT = BASIC_LOOP_IN; | 173 String BASIC_LOOP_OUT = BASIC_LOOP_IN; |
| 169 | 174 |
| 170 // Ensures that proper scoping is preserved, i.e. that the optimized | 175 // Ensures that proper scoping is preserved, i.e. that the optimized |
| 171 // continuation body does reference out of scope primitives. | 176 // continuation body does reference out of scope primitives. |
| 172 // 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. |
| 173 | 178 |
| 174 String SCOPING_IN = """ | 179 String SCOPING_IN = """ |
| 175 (FunctionDefinition main ( return) | 180 (FunctionDefinition main () return () |
| 176 (LetCont (k0 v1) | 181 (LetCont (k0 v1) |
| 177 (InvokeStatic print v1 return)) | 182 (InvokeStatic print v1 return)) |
| 178 (LetPrim v0 (Constant IntConstant(0))) | 183 (LetPrim v0 (Constant IntConstant(0))) |
| 179 (LetPrim v2 (Constant NullConstant)) | 184 (LetPrim v2 (Constant NullConstant)) |
| 180 (InvokeContinuation k0 v0)) | 185 (InvokeContinuation k0 v0)) |
| 181 """; | 186 """; |
| 182 | 187 |
| 183 String SCOPING_OUT = """ | 188 String SCOPING_OUT = """ |
| 184 (FunctionDefinition main ( return) | 189 (FunctionDefinition main () return () |
| 185 (LetPrim v0 (Constant IntConstant(0))) | 190 (LetPrim v0 (Constant IntConstant(0))) |
| 186 (LetCont (k0) | 191 (LetCont (k0) |
| 187 (InvokeStatic print v0 return)) | 192 (InvokeStatic print v0 return)) |
| 188 (LetPrim v1 (Constant NullConstant)) | 193 (LetPrim v1 (Constant NullConstant)) |
| 189 (InvokeContinuation k0 )) | 194 (InvokeContinuation k0 )) |
| 190 """; | 195 """; |
| 191 | 196 |
| 192 // Ensures that continuations which are never invoked are not optimized. | 197 // Ensures that continuations which are never invoked are not optimized. |
| 193 // IR written by hand. | 198 // IR written by hand. |
| 194 | 199 |
| 195 String NEVER_INVOKED_IN = """ | 200 String NEVER_INVOKED_IN = """ |
| 196 (FunctionDefinition main ( return) | 201 (FunctionDefinition main () return () |
| 197 (LetPrim v0 (Constant IntConstant(0))) | 202 (LetPrim v0 (Constant IntConstant(0))) |
| 198 (LetCont (k0 v1) | 203 (LetCont (k0 v1) |
| 199 (InvokeStatic print v1 return)) | 204 (InvokeStatic print v1 return)) |
| 200 (InvokeContinuation return v0)) | 205 (InvokeContinuation return v0)) |
| 201 """; | 206 """; |
| 202 | 207 |
| 203 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; | 208 String NEVER_INVOKED_OUT = NEVER_INVOKED_IN; |
| 204 | 209 |
| 205 /// Normalizes whitespace by replacing all whitespace sequences by a single | 210 /// Normalizes whitespace by replacing all whitespace sequences by a single |
| 206 /// space and trimming leading and trailing whitespace. | 211 /// space and trimming leading and trailing whitespace. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 224 Expect.equals(expected, actual, "Actual:\n$actual"); | 229 Expect.equals(expected, actual, "Actual:\n$actual"); |
| 225 } | 230 } |
| 226 | 231 |
| 227 void main() { | 232 void main() { |
| 228 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); | 233 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); |
| 229 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); | 234 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); |
| 230 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); | 235 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); |
| 231 testRedundantPhi(SCOPING_IN, SCOPING_OUT); | 236 testRedundantPhi(SCOPING_IN, SCOPING_OUT); |
| 232 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); | 237 testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT); |
| 233 } | 238 } |
| OLD | NEW |