| 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/implementation/cps_ir/cps_ir_nodes.dart'; | 7 import 'package:compiler/implementation/cps_ir/cps_ir_nodes.dart'; |
| 8 import 'package:compiler/implementation/cps_ir/cps_ir_nodes_sexpr.dart'; | 8 import 'package:compiler/implementation/cps_ir/cps_ir_nodes_sexpr.dart'; |
| 9 import 'package:compiler/implementation/cps_ir/optimizers.dart'; | 9 import 'package:compiler/implementation/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 42)) | 22 (FunctionDefinition main (return) (LetPrim v0 (Constant IntConstant(42))) |
| 23 (LetPrim v1 (Constant 0)) | 23 (LetPrim v1 (Constant IntConstant(0))) |
| 24 (LetCont* (k0 v2 v3) | 24 (LetCont* (k0 v2 v3) |
| 25 (LetCont (k1) (LetPrim v4 (Constant null)) | 25 (LetCont (k1) (LetPrim v4 (Constant NullConstant)) |
| 26 (InvokeContinuation return v4)) | 26 (InvokeContinuation return v4)) |
| 27 (LetCont (k2) | 27 (LetCont (k2) |
| 28 (LetCont (k3 v5) | 28 (LetCont (k3 v5) |
| 29 (LetCont (k4 v6) (LetPrim v7 (Constant 1)) | 29 (LetCont (k4 v6) (LetPrim v7 (Constant IntConstant(1))) |
| 30 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) | 30 (LetCont (k5 v8) (InvokeContinuation* k0 v2 v8)) |
| 31 (InvokeMethod v3 + v7 k5)) | 31 (InvokeMethod v3 + v7 k5)) |
| 32 (InvokeStatic print v5 k4)) | 32 (InvokeStatic print v5 k4)) |
| 33 (InvokeMethod v2 toString k3)) | 33 (InvokeMethod v2 toString k3)) |
| 34 (LetPrim v9 (Constant 2)) | 34 (LetPrim v9 (Constant IntConstant(2))) |
| 35 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) | 35 (LetCont (k6 v10) (Branch (IsTrue v10) k2 k1)) |
| 36 (InvokeMethod v3 < v9 k6)) | 36 (InvokeMethod v3 < v9 k6)) |
| 37 (InvokeContinuation k0 v0 v1)) | 37 (InvokeContinuation k0 v0 v1)) |
| 38 """; | 38 """; |
| 39 | 39 |
| 40 String READ_IN_LOOP_OUT = """ | 40 String READ_IN_LOOP_OUT = """ |
| 41 (FunctionDefinition main ( return) (LetPrim v0 (Constant 42)) | 41 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(42))) |
| 42 (LetPrim v1 (Constant 0)) | 42 (LetPrim v1 (Constant IntConstant(0))) |
| 43 (LetCont* (k0 v2) | 43 (LetCont* (k0 v2) |
| 44 (LetCont (k1) (LetPrim v3 (Constant null)) | 44 (LetCont (k1) (LetPrim v3 (Constant NullConstant)) |
| 45 (InvokeContinuation return v3)) | 45 (InvokeContinuation return v3)) |
| 46 (LetCont (k2) | 46 (LetCont (k2) |
| 47 (LetCont (k3 v4) | 47 (LetCont (k3 v4) |
| 48 (LetCont (k4 v5) (LetPrim v6 (Constant 1)) | 48 (LetCont (k4 v5) (LetPrim v6 (Constant IntConstant(1))) |
| 49 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) | 49 (LetCont (k5 v7) (InvokeContinuation* k0 v7)) |
| 50 (InvokeMethod v2 + v6 k5)) | 50 (InvokeMethod v2 + v6 k5)) |
| 51 (InvokeStatic print v4 k4)) | 51 (InvokeStatic print v4 k4)) |
| 52 (InvokeMethod v0 toString k3)) | 52 (InvokeMethod v0 toString k3)) |
| 53 (LetPrim v8 (Constant 2)) | 53 (LetPrim v8 (Constant IntConstant(2))) |
| 54 (LetCont (k6 v9) (Branch (IsTrue v9) k2 k1)) | 54 (LetCont (k6 v9) (Branch (IsTrue v9) k2 k1)) |
| 55 (InvokeMethod v2 < v8 k6)) | 55 (InvokeMethod v2 < v8 k6)) |
| 56 (InvokeContinuation k0 v1)) | 56 (InvokeContinuation k0 v1)) |
| 57 """; | 57 """; |
| 58 | 58 |
| 59 // The 'inner loop' IR represents the following source code: | 59 // The 'inner loop' IR represents the following source code: |
| 60 // | 60 // |
| 61 // void main() { | 61 // void main() { |
| 62 // int j = 42; | 62 // int j = 42; |
| 63 // for (int i = 0; i < 2; i++) { | 63 // for (int i = 0; i < 2; i++) { |
| 64 // for (int k = 0; k < 2; k++) { | 64 // for (int k = 0; k < 2; k++) { |
| 65 // print(i.toString()); | 65 // print(i.toString()); |
| 66 // } | 66 // } |
| 67 // } | 67 // } |
| 68 // print(j.toString()); | 68 // print(j.toString()); |
| 69 // } | 69 // } |
| 70 // | 70 // |
| 71 // This test case ensures that iterative optimization works: first, v8 and v9 | 71 // 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. | 72 // are removed from k5, and only then can k0 be optimized as well. |
| 73 | 73 |
| 74 const String INNER_LOOP_IN = """ | 74 const String INNER_LOOP_IN = """ |
| 75 (FunctionDefinition main (return) (LetPrim v0 (Constant 42)) | 75 (FunctionDefinition main (return) (LetPrim v0 (Constant IntConstant(42))) |
| 76 (LetPrim v1 (Constant 0)) | 76 (LetPrim v1 (Constant IntConstant(0))) |
| 77 (LetCont* (k0 v2 v3) | 77 (LetCont* (k0 v2 v3) |
| 78 (LetCont (k1) | 78 (LetCont (k1) |
| 79 (LetCont (k2 v4) | 79 (LetCont (k2 v4) |
| 80 (LetCont (k3 v5) (LetPrim v6 (Constant null)) | 80 (LetCont (k3 v5) (LetPrim v6 (Constant NullConstant)) |
| 81 (InvokeContinuation return v6)) | 81 (InvokeContinuation return v6)) |
| 82 (InvokeStatic print v4 k3)) | 82 (InvokeStatic print v4 k3)) |
| 83 (InvokeMethod v2 toString k2)) | 83 (InvokeMethod v2 toString k2)) |
| 84 (LetCont (k4) (LetPrim v7 (Constant 0)) | 84 (LetCont (k4) (LetPrim v7 (Constant IntConstant(0))) |
| 85 (LetCont* (k5 v8 v9 v10) | 85 (LetCont* (k5 v8 v9 v10) |
| 86 (LetCont (k6) (LetPrim v11 (Constant 1)) | 86 (LetCont (k6) (LetPrim v11 (Constant IntConstant(1))) |
| 87 (LetCont (k7 v12) (InvokeContinuation* k0 v8 v12)) | 87 (LetCont (k7 v12) (InvokeContinuation* k0 v8 v12)) |
| 88 (InvokeMethod v9 + v11 k7)) | 88 (InvokeMethod v9 + v11 k7)) |
| 89 (LetCont (k8) | 89 (LetCont (k8) |
| 90 (LetCont (k9 v13) | 90 (LetCont (k9 v13) |
| 91 (LetCont (k10 v14) (LetPrim v15 (Constant 1)) | 91 (LetCont (k10 v14) (LetPrim v15 (Constant IntConstant(1))) |
| 92 (LetCont (k11 v16) | 92 (LetCont (k11 v16) |
| 93 (InvokeContinuation* k5 v8 v9 v16)) | 93 (InvokeContinuation* k5 v8 v9 v16)) |
| 94 (InvokeMethod v10 + v15 k11)) | 94 (InvokeMethod v10 + v15 k11)) |
| 95 (InvokeStatic print v13 k10)) | 95 (InvokeStatic print v13 k10)) |
| 96 (InvokeMethod v9 toString k9)) | 96 (InvokeMethod v9 toString k9)) |
| 97 (LetPrim v17 (Constant 2)) | 97 (LetPrim v17 (Constant IntConstant(2))) |
| 98 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) | 98 (LetCont (k12 v18) (Branch (IsTrue v18) k8 k6)) |
| 99 (InvokeMethod v10 < v17 k12)) | 99 (InvokeMethod v10 < v17 k12)) |
| 100 (InvokeContinuation k5 v2 v3 v7)) | 100 (InvokeContinuation k5 v2 v3 v7)) |
| 101 (LetPrim v19 (Constant 2)) | 101 (LetPrim v19 (Constant IntConstant(2))) |
| 102 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) | 102 (LetCont (k13 v20) (Branch (IsTrue v20) k4 k1)) |
| 103 (InvokeMethod v3 < v19 k13)) | 103 (InvokeMethod v3 < v19 k13)) |
| 104 (InvokeContinuation k0 v0 v1)) | 104 (InvokeContinuation k0 v0 v1)) |
| 105 """; | 105 """; |
| 106 | 106 |
| 107 const String INNER_LOOP_OUT = """ | 107 const String INNER_LOOP_OUT = """ |
| 108 (FunctionDefinition main ( return) (LetPrim v0 (Constant 42)) | 108 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(42))) |
| 109 (LetPrim v1 (Constant 0)) | 109 (LetPrim v1 (Constant IntConstant(0))) |
| 110 (LetCont* (k0 v2) | 110 (LetCont* (k0 v2) |
| 111 (LetCont (k1) | 111 (LetCont (k1) |
| 112 (LetCont (k2 v3) | 112 (LetCont (k2 v3) |
| 113 (LetCont (k3 v4) (LetPrim v5 (Constant null)) | 113 (LetCont (k3 v4) (LetPrim v5 (Constant NullConstant)) |
| 114 (InvokeContinuation return v5)) | 114 (InvokeContinuation return v5)) |
| 115 (InvokeStatic print v3 k3)) | 115 (InvokeStatic print v3 k3)) |
| 116 (InvokeMethod v0 toString k2)) | 116 (InvokeMethod v0 toString k2)) |
| 117 (LetCont (k4) (LetPrim v6 (Constant 0)) | 117 (LetCont (k4) (LetPrim v6 (Constant IntConstant(0))) |
| 118 (LetCont* (k5 v7) | 118 (LetCont* (k5 v7) |
| 119 (LetCont (k6) (LetPrim v8 (Constant 1)) | 119 (LetCont (k6) (LetPrim v8 (Constant IntConstant(1))) |
| 120 (LetCont (k7 v9) (InvokeContinuation* k0 v9)) | 120 (LetCont (k7 v9) (InvokeContinuation* k0 v9)) |
| 121 (InvokeMethod v2 + v8 k7)) | 121 (InvokeMethod v2 + v8 k7)) |
| 122 (LetCont (k8) | 122 (LetCont (k8) |
| 123 (LetCont (k9 v10) | 123 (LetCont (k9 v10) |
| 124 (LetCont (k10 v11) (LetPrim v12 (Constant 1)) | 124 (LetCont (k10 v11) (LetPrim v12 (Constant IntConstant(1))) |
| 125 (LetCont (k11 v13) | 125 (LetCont (k11 v13) |
| 126 (InvokeContinuation* k5 v13)) | 126 (InvokeContinuation* k5 v13)) |
| 127 (InvokeMethod v7 + v12 k11)) | 127 (InvokeMethod v7 + v12 k11)) |
| 128 (InvokeStatic print v10 k10)) | 128 (InvokeStatic print v10 k10)) |
| 129 (InvokeMethod v2 toString k9)) | 129 (InvokeMethod v2 toString k9)) |
| 130 (LetPrim v14 (Constant 2)) | 130 (LetPrim v14 (Constant IntConstant(2))) |
| 131 (LetCont (k12 v15) (Branch (IsTrue v15) k8 k6)) | 131 (LetCont (k12 v15) (Branch (IsTrue v15) k8 k6)) |
| 132 (InvokeMethod v7 < v14 k12)) | 132 (InvokeMethod v7 < v14 k12)) |
| 133 (InvokeContinuation k5 v6)) | 133 (InvokeContinuation k5 v6)) |
| 134 (LetPrim v16 (Constant 2)) | 134 (LetPrim v16 (Constant IntConstant(2))) |
| 135 (LetCont (k13 v17) (Branch (IsTrue v17) k4 k1)) | 135 (LetCont (k13 v17) (Branch (IsTrue v17) k4 k1)) |
| 136 (InvokeMethod v2 < v16 k13)) | 136 (InvokeMethod v2 < v16 k13)) |
| 137 (InvokeContinuation k0 v1)) | 137 (InvokeContinuation k0 v1)) |
| 138 """; | 138 """; |
| 139 | 139 |
| 140 // There are no redundant phis in the 'basic loop' IR, and this test ensures | 140 // There are no redundant phis in the 'basic loop' IR, and this test ensures |
| 141 // simply that the optimization does not alter the IR. It represents the | 141 // simply that the optimization does not alter the IR. It represents the |
| 142 // following program: | 142 // following program: |
| 143 // | 143 // |
| 144 // void main() { | 144 // void main() { |
| 145 // for (int i = 0; i < 2; i++) { | 145 // for (int i = 0; i < 2; i++) { |
| 146 // print(i.toString()); | 146 // print(i.toString()); |
| 147 // } | 147 // } |
| 148 // } | 148 // } |
| 149 | 149 |
| 150 String BASIC_LOOP_IN = """ | 150 String BASIC_LOOP_IN = """ |
| 151 (FunctionDefinition main ( return) (LetPrim v0 (Constant 0)) | 151 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(0))) |
| 152 (LetCont* (k0 v1) | 152 (LetCont* (k0 v1) |
| 153 (LetCont (k1) (LetPrim v2 (Constant null)) | 153 (LetCont (k1) (LetPrim v2 (Constant NullConstant)) |
| 154 (InvokeContinuation return v2)) | 154 (InvokeContinuation return v2)) |
| 155 (LetCont (k2) | 155 (LetCont (k2) |
| 156 (LetCont (k3 v3) | 156 (LetCont (k3 v3) |
| 157 (LetCont (k4 v4) (LetPrim v5 (Constant 1)) | 157 (LetCont (k4 v4) (LetPrim v5 (Constant IntConstant(1))) |
| 158 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) | 158 (LetCont (k5 v6) (InvokeContinuation* k0 v6)) |
| 159 (InvokeMethod v1 + v5 k5)) | 159 (InvokeMethod v1 + v5 k5)) |
| 160 (InvokeStatic print v3 k4)) | 160 (InvokeStatic print v3 k4)) |
| 161 (InvokeMethod v1 toString k3)) | 161 (InvokeMethod v1 toString k3)) |
| 162 (LetPrim v7 (Constant 2)) | 162 (LetPrim v7 (Constant IntConstant(2))) |
| 163 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) | 163 (LetCont (k6 v8) (Branch (IsTrue v8) k2 k1)) |
| 164 (InvokeMethod v1 < v7 k6)) | 164 (InvokeMethod v1 < v7 k6)) |
| 165 (InvokeContinuation k0 v0)) | 165 (InvokeContinuation k0 v0)) |
| 166 """; | 166 """; |
| 167 | 167 |
| 168 String BASIC_LOOP_OUT = BASIC_LOOP_IN; | 168 String BASIC_LOOP_OUT = BASIC_LOOP_IN; |
| 169 | 169 |
| 170 // Ensures that proper scoping is preserved, i.e. that the optimized | 170 // Ensures that proper scoping is preserved, i.e. that the optimized |
| 171 // continuation body does reference out of scope primitives. | 171 // continuation body does reference out of scope primitives. |
| 172 // IR written by hand since this case is currently not being generated. | 172 // IR written by hand since this case is currently not being generated. |
| 173 | 173 |
| 174 String SCOPING_IN = """ | 174 String SCOPING_IN = """ |
| 175 (FunctionDefinition main ( return) | 175 (FunctionDefinition main ( return) |
| 176 (LetCont (k0 v1) | 176 (LetCont (k0 v1) |
| 177 (InvokeStatic print v1 return)) | 177 (InvokeStatic print v1 return)) |
| 178 (LetPrim v0 (Constant 0)) | 178 (LetPrim v0 (Constant IntConstant(0))) |
| 179 (LetPrim v2 (Constant null)) | 179 (LetPrim v2 (Constant NullConstant)) |
| 180 (InvokeContinuation k0 v0)) | 180 (InvokeContinuation k0 v0)) |
| 181 """; | 181 """; |
| 182 | 182 |
| 183 String SCOPING_OUT = """ | 183 String SCOPING_OUT = """ |
| 184 (FunctionDefinition main ( return) | 184 (FunctionDefinition main ( return) |
| 185 (LetPrim v0 (Constant 0)) | 185 (LetPrim v0 (Constant IntConstant(0))) |
| 186 (LetCont (k0) | 186 (LetCont (k0) |
| 187 (InvokeStatic print v0 return)) | 187 (InvokeStatic print v0 return)) |
| 188 (LetPrim v1 (Constant null)) | 188 (LetPrim v1 (Constant NullConstant)) |
| 189 (InvokeContinuation k0 )) | 189 (InvokeContinuation k0 )) |
| 190 """; | 190 """; |
| 191 | 191 |
| 192 // Ensures that continuations which are never invoked are not optimized. | 192 // Ensures that continuations which are never invoked are not optimized. |
| 193 // IR written by hand. | 193 // IR written by hand. |
| 194 | 194 |
| 195 String NEVER_INVOKED1_IN = """ | 195 String NEVER_INVOKED1_IN = """ |
| 196 (FunctionDefinition main ( return) | 196 (FunctionDefinition main ( return) |
| 197 (LetPrim v0 (Constant 0)) | 197 (LetPrim v0 (Constant IntConstant(0))) |
| 198 (LetCont (k0 v1) | 198 (LetCont (k0 v1) |
| 199 (InvokeStatic print v1 return)) | 199 (InvokeStatic print v1 return)) |
| 200 (InvokeContinuation return v0)) | 200 (InvokeContinuation return v0)) |
| 201 """; | 201 """; |
| 202 | 202 |
| 203 String NEVER_INVOKED1_OUT = NEVER_INVOKED1_IN; | 203 String NEVER_INVOKED1_OUT = NEVER_INVOKED1_IN; |
| 204 | 204 |
| 205 // As in the previous test, except with the added wrinkle of higher order | 205 // As in the previous test, except with the added wrinkle of higher order |
| 206 // continuations. | 206 // continuations. |
| 207 | 207 |
| (...skipping 30 matching lines...) Expand all Loading... |
| 238 final unstringifier = new SExpressionUnstringifier(); | 238 final unstringifier = new SExpressionUnstringifier(); |
| 239 final stringifier = new SExpressionStringifier(); | 239 final stringifier = new SExpressionStringifier(); |
| 240 final optimizer = new RedundantPhiEliminator(); | 240 final optimizer = new RedundantPhiEliminator(); |
| 241 | 241 |
| 242 FunctionDefinition f = unstringifier.unstringify(input); | 242 FunctionDefinition f = unstringifier.unstringify(input); |
| 243 optimizer.rewrite(f); | 243 optimizer.rewrite(f); |
| 244 | 244 |
| 245 String expected = normalizeSExpr(expectedOutput); | 245 String expected = normalizeSExpr(expectedOutput); |
| 246 String actual = normalizeSExpr(stringifier.visit(f)); | 246 String actual = normalizeSExpr(stringifier.visit(f)); |
| 247 | 247 |
| 248 Expect.equals(expected, actual); | 248 Expect.equals(expected, actual, "Actual:\n$actual"); |
| 249 } | 249 } |
| 250 | 250 |
| 251 void main() { | 251 void main() { |
| 252 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); | 252 testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT); |
| 253 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); | 253 testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT); |
| 254 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); | 254 testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT); |
| 255 testRedundantPhi(SCOPING_IN, SCOPING_OUT); | 255 testRedundantPhi(SCOPING_IN, SCOPING_OUT); |
| 256 testRedundantPhi(NEVER_INVOKED1_IN, NEVER_INVOKED1_OUT); | 256 testRedundantPhi(NEVER_INVOKED1_IN, NEVER_INVOKED1_OUT); |
| 257 testRedundantPhi(NEVER_INVOKED2_IN, NEVER_INVOKED2_OUT); | 257 testRedundantPhi(NEVER_INVOKED2_IN, NEVER_INVOKED2_OUT); |
| 258 testRedundantPhi(AS_ARG_IN, AS_ARG_OUT); | 258 testRedundantPhi(AS_ARG_IN, AS_ARG_OUT); |
| 259 } | 259 } |
| OLD | NEW |