| 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 tests in this file that ensure shrinking reductions work as expected. | 11 // The tests in this file that ensure shrinking reductions work as expected. |
| 12 // Reductions and their corresponding names are taken from | 12 // Reductions and their corresponding names are taken from |
| 13 // 'Compiling with Continuations, Continued' by Andrew Kennedy. | 13 // 'Compiling with Continuations, Continued' by Andrew Kennedy. |
| 14 | 14 |
| 15 // Basic dead-val: letprim x = V in K -> K (x not free in K). | 15 // Basic dead-val: letprim x = V in K -> K (x not free in K). |
| 16 // | 16 // |
| 17 // int main() { | 17 // int main() { |
| 18 // int i = 42; | 18 // int i = 42; |
| 19 // return 0; | 19 // return 0; |
| 20 // } | 20 // } |
| 21 | 21 |
| 22 String DEAD_VAL_IN = """ | 22 String DEAD_VAL_IN = """ |
| 23 (FunctionDefinition main ( return) (LetPrim v0 (Constant 42)) | 23 (FunctionDefinition main ( return) (LetPrim v0 (Constant IntConstant(42))) |
| 24 (LetPrim v1 (Constant 0)) (InvokeContinuation return v1)) | 24 (LetPrim v1 (Constant IntConstant(0))) (InvokeContinuation return v1)) |
| 25 """; | 25 """; |
| 26 String DEAD_VAL_OUT = """ | 26 String DEAD_VAL_OUT = """ |
| 27 (FunctionDefinition main ( return) | 27 (FunctionDefinition main ( return) |
| 28 (LetPrim v0 (Constant 0)) (InvokeContinuation return v0)) | 28 (LetPrim v0 (Constant IntConstant(0))) (InvokeContinuation return v0)) |
| 29 """; | 29 """; |
| 30 | 30 |
| 31 // Iterative dead-val. No optimizations possible since the continuation to | 31 // Iterative dead-val. No optimizations possible since the continuation to |
| 32 // InvokeMethod must have one argument, even if it is unused. | 32 // InvokeMethod must have one argument, even if it is unused. |
| 33 // | 33 // |
| 34 // int main() { | 34 // int main() { |
| 35 // int i = 42; | 35 // int i = 42; |
| 36 // int j = i + 1; | 36 // int j = i + 1; |
| 37 // return 0; | 37 // return 0; |
| 38 // } | 38 // } |
| 39 | 39 |
| 40 String ITERATIVE_DEAD_VAL1_IN = """ | 40 String ITERATIVE_DEAD_VAL1_IN = """ |
| 41 (FunctionDefinition main ( return) | 41 (FunctionDefinition main ( return) |
| 42 (LetPrim v0 (Constant 42)) | 42 (LetPrim v0 (Constant IntConstant(42))) |
| 43 (LetPrim v1 (Constant 1)) | 43 (LetPrim v1 (Constant IntConstant(1))) |
| 44 (LetCont (k0 v2) (LetPrim v3 (Constant 0)) | 44 (LetCont (k0 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 45 (InvokeContinuation return v3)) | 45 (InvokeContinuation return v3)) |
| 46 (InvokeMethod v0 + v1 k0)) | 46 (InvokeMethod v0 + v1 k0)) |
| 47 """; | 47 """; |
| 48 String ITERATIVE_DEAD_VAL1_OUT = ITERATIVE_DEAD_VAL1_IN; | 48 String ITERATIVE_DEAD_VAL1_OUT = ITERATIVE_DEAD_VAL1_IN; |
| 49 | 49 |
| 50 // Iterative dead-val. IR written by hand. | 50 // Iterative dead-val. IR written by hand. |
| 51 | 51 |
| 52 String ITERATIVE_DEAD_VAL2_IN = """ | 52 String ITERATIVE_DEAD_VAL2_IN = """ |
| 53 (FunctionDefinition main ( return) | 53 (FunctionDefinition main ( return) |
| 54 (LetPrim v0 (Constant 42)) | 54 (LetPrim v0 (Constant IntConstant(42))) |
| 55 (LetPrim v1 | 55 (LetPrim v1 |
| 56 (CreateFunction | 56 (CreateFunction |
| 57 (FunctionDefinition f (i return) | 57 (FunctionDefinition f (i return) |
| 58 (InvokeContinuation return v0)))) | 58 (InvokeContinuation return v0)))) |
| 59 (LetPrim v2 (Constant 0)) | 59 (LetPrim v2 (Constant IntConstant(0))) |
| 60 (InvokeContinuation return v2)) | 60 (InvokeContinuation return v2)) |
| 61 """; | 61 """; |
| 62 String ITERATIVE_DEAD_VAL2_OUT = """ | 62 String ITERATIVE_DEAD_VAL2_OUT = """ |
| 63 (FunctionDefinition main ( return) | 63 (FunctionDefinition main ( return) |
| 64 (LetPrim v0 (Constant 0)) | 64 (LetPrim v0 (Constant IntConstant(0))) |
| 65 (InvokeContinuation return v0)) | 65 (InvokeContinuation return v0)) |
| 66 """; | 66 """; |
| 67 | 67 |
| 68 // Basic dead-cont: letcont k x = L in K -> K (k not free in K). | 68 // Basic dead-cont: letcont k x = L in K -> K (k not free in K). |
| 69 // IR written by hand. | 69 // IR written by hand. |
| 70 | 70 |
| 71 String DEAD_CONT_IN = """ | 71 String DEAD_CONT_IN = """ |
| 72 (FunctionDefinition main ( return) | 72 (FunctionDefinition main ( return) |
| 73 (LetPrim v4 (Constant 0)) | 73 (LetPrim v4 (Constant IntConstant(0))) |
| 74 (LetCont (k0 v0) (InvokeConstructor List return)) | 74 (LetCont (k0 v0) (InvokeConstructor List return)) |
| 75 (LetCont (k1 v1) | 75 (LetCont (k1 v1) |
| 76 (LetCont (k2 v2) (LetPrim v3 (Constant 0)) | 76 (LetCont (k2 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 77 (InvokeContinuation return v3)) | 77 (InvokeContinuation return v3)) |
| 78 (InvokeStatic print v4 k2)) | 78 (InvokeStatic print v4 k2)) |
| 79 (InvokeStatic print v4 k1)) | 79 (InvokeStatic print v4 k1)) |
| 80 """; | 80 """; |
| 81 String DEAD_CONT_OUT = """ | 81 String DEAD_CONT_OUT = """ |
| 82 (FunctionDefinition main ( return) | 82 (FunctionDefinition main ( return) |
| 83 (LetPrim v0 (Constant 0)) | 83 (LetPrim v0 (Constant IntConstant(0))) |
| 84 (LetCont (k0 v1) | 84 (LetCont (k0 v1) |
| 85 (LetCont (k1 v2) (LetPrim v3 (Constant 0)) | 85 (LetCont (k1 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 86 (InvokeContinuation return v3)) | 86 (InvokeContinuation return v3)) |
| 87 (InvokeStatic print v0 k1)) | 87 (InvokeStatic print v0 k1)) |
| 88 (InvokeStatic print v0 k0)) | 88 (InvokeStatic print v0 k0)) |
| 89 """; | 89 """; |
| 90 | 90 |
| 91 // Iterative dead-cont. IR written by hand. | 91 // Iterative dead-cont. IR written by hand. |
| 92 | 92 |
| 93 String ITERATIVE_DEAD_CONT_IN = """ | 93 String ITERATIVE_DEAD_CONT_IN = """ |
| 94 (FunctionDefinition main ( return) | 94 (FunctionDefinition main ( return) |
| 95 (LetPrim v4 (Constant 0)) | 95 (LetPrim v4 (Constant IntConstant(0))) |
| 96 (LetCont (k0 v0) (InvokeConstructor List return)) | 96 (LetCont (k0 v0) (InvokeConstructor List return)) |
| 97 (LetCont (k3 v5) (InvokeContinuation k0 v5)) | 97 (LetCont (k3 v5) (InvokeContinuation k0 v5)) |
| 98 (LetCont (k1 v1) | 98 (LetCont (k1 v1) |
| 99 (LetCont (k2 v2) (LetPrim v3 (Constant 0)) | 99 (LetCont (k2 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 100 (InvokeContinuation return v3)) | 100 (InvokeContinuation return v3)) |
| 101 (InvokeStatic print v4 k2)) | 101 (InvokeStatic print v4 k2)) |
| 102 (InvokeStatic print v4 k1)) | 102 (InvokeStatic print v4 k1)) |
| 103 """; | 103 """; |
| 104 String ITERATIVE_DEAD_CONT_OUT = """ | 104 String ITERATIVE_DEAD_CONT_OUT = """ |
| 105 (FunctionDefinition main ( return) | 105 (FunctionDefinition main ( return) |
| 106 (LetPrim v0 (Constant 0)) | 106 (LetPrim v0 (Constant IntConstant(0))) |
| 107 (LetCont (k0 v1) | 107 (LetCont (k0 v1) |
| 108 (LetCont (k1 v2) (LetPrim v3 (Constant 0)) | 108 (LetCont (k1 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 109 (InvokeContinuation return v3)) | 109 (InvokeContinuation return v3)) |
| 110 (InvokeStatic print v0 k1)) | 110 (InvokeStatic print v0 k1)) |
| 111 (InvokeStatic print v0 k0)) | 111 (InvokeStatic print v0 k0)) |
| 112 """; | 112 """; |
| 113 | 113 |
| 114 // Beta-cont-lin: letcont k x = K in C[k y] -> C[K[y/x]] (k not free in C). | 114 // Beta-cont-lin: letcont k x = K in C[k y] -> C[K[y/x]] (k not free in C). |
| 115 // IR written by hand. | 115 // IR written by hand. |
| 116 | 116 |
| 117 String BETA_CONT_LIN_IN = """ | 117 String BETA_CONT_LIN_IN = """ |
| 118 (FunctionDefinition main ( return) | 118 (FunctionDefinition main ( return) |
| 119 (LetCont (k0 v0) | 119 (LetCont (k0 v0) |
| 120 (LetCont (k1 v1) | 120 (LetCont (k1 v1) |
| 121 (LetCont (k2 v2) (LetPrim v3 (Constant 0)) | 121 (LetCont (k2 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 122 (InvokeContinuation return v3)) | 122 (InvokeContinuation return v3)) |
| 123 (InvokeStatic print v0 k2)) | 123 (InvokeStatic print v0 k2)) |
| 124 (InvokeStatic print v0 k1)) | 124 (InvokeStatic print v0 k1)) |
| 125 (LetPrim v4 (Constant 0)) | 125 (LetPrim v4 (Constant IntConstant(0))) |
| 126 (InvokeContinuation k0 v4)) | 126 (InvokeContinuation k0 v4)) |
| 127 """; | 127 """; |
| 128 String BETA_CONT_LIN_OUT = """ | 128 String BETA_CONT_LIN_OUT = """ |
| 129 (FunctionDefinition main ( return) | 129 (FunctionDefinition main ( return) |
| 130 (LetPrim v0 (Constant 0)) | 130 (LetPrim v0 (Constant IntConstant(0))) |
| 131 (LetCont (k0 v1) | 131 (LetCont (k0 v1) |
| 132 (LetCont (k1 v2) (LetPrim v3 (Constant 0)) | 132 (LetCont (k1 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 133 (InvokeContinuation return v3)) | 133 (InvokeContinuation return v3)) |
| 134 (InvokeStatic print v0 k1)) | 134 (InvokeStatic print v0 k1)) |
| 135 (InvokeStatic print v0 k0)) | 135 (InvokeStatic print v0 k0)) |
| 136 """; | 136 """; |
| 137 | 137 |
| 138 // Beta-cont-lin with continuation passed as arg in invoke. IR written by hand. | 138 // Beta-cont-lin with continuation passed as arg in invoke. IR written by hand. |
| 139 | 139 |
| 140 String ARG_BETA_CONT_LIN_IN = """ | 140 String ARG_BETA_CONT_LIN_IN = """ |
| 141 (FunctionDefinition main ( return) | 141 (FunctionDefinition main ( return) |
| 142 (LetCont (k0 v0) | 142 (LetCont (k0 v0) |
| 143 (LetPrim v1 (Constant 0)) | 143 (LetPrim v1 (Constant IntConstant(0))) |
| 144 (InvokeStatic print v1 return)) | 144 (InvokeStatic print v1 return)) |
| 145 (InvokeContinuation return k0)) | 145 (InvokeContinuation return k0)) |
| 146 """; | 146 """; |
| 147 String ARG_BETA_CONT_LIN_OUT = ARG_BETA_CONT_LIN_IN; | 147 String ARG_BETA_CONT_LIN_OUT = ARG_BETA_CONT_LIN_IN; |
| 148 | 148 |
| 149 // Beta-cont-lin with recursive continuation. IR written by hand. | 149 // Beta-cont-lin with recursive continuation. IR written by hand. |
| 150 | 150 |
| 151 String RECURSIVE_BETA_CONT_LIN_IN = """ | 151 String RECURSIVE_BETA_CONT_LIN_IN = """ |
| 152 (FunctionDefinition main ( return) | 152 (FunctionDefinition main ( return) |
| 153 (LetCont* (k0 v0) | 153 (LetCont* (k0 v0) |
| 154 (InvokeContinuation* k0 v0)) | 154 (InvokeContinuation* k0 v0)) |
| 155 (LetPrim v1 (Constant 0)) | 155 (LetPrim v1 (Constant IntConstant(0))) |
| 156 (InvokeContinuation k0 v1)) | 156 (InvokeContinuation k0 v1)) |
| 157 """; | 157 """; |
| 158 String RECURSIVE_BETA_CONT_LIN_OUT = RECURSIVE_BETA_CONT_LIN_IN; | 158 String RECURSIVE_BETA_CONT_LIN_OUT = RECURSIVE_BETA_CONT_LIN_IN; |
| 159 | 159 |
| 160 // Beta-cont-lin used inside body. IR written by hand. | 160 // Beta-cont-lin used inside body. IR written by hand. |
| 161 | 161 |
| 162 String USED_BETA_CONT_LIN_IN = """ | 162 String USED_BETA_CONT_LIN_IN = """ |
| 163 (FunctionDefinition main ( return) | 163 (FunctionDefinition main ( return) |
| 164 (LetCont (k0 v0) | 164 (LetCont (k0 v0) |
| 165 (LetCont (k1 v1) | 165 (LetCont (k1 v1) |
| 166 (LetCont (k2 v2) (LetPrim v3 (Constant 0)) | 166 (LetCont (k2 v2) (LetPrim v3 (Constant IntConstant(0))) |
| 167 (InvokeContinuation return v3)) | 167 (InvokeContinuation return v3)) |
| 168 (InvokeStatic print v0 k2)) | 168 (InvokeStatic print v0 k2)) |
| 169 (InvokeStatic print v0 k1)) | 169 (InvokeStatic print v0 k1)) |
| 170 (LetPrim v4 | 170 (LetPrim v4 |
| 171 (CreateFunction | 171 (CreateFunction |
| 172 (FunctionDefinition f ( return) | 172 (FunctionDefinition f ( return) |
| 173 (InvokeContinuation return k0)))) | 173 (InvokeContinuation return k0)))) |
| 174 (InvokeContinuation k0 v4)) | 174 (InvokeContinuation k0 v4)) |
| 175 """; | 175 """; |
| 176 String USED_BETA_CONT_LIN_OUT = USED_BETA_CONT_LIN_IN; | 176 String USED_BETA_CONT_LIN_OUT = USED_BETA_CONT_LIN_IN; |
| 177 | 177 |
| 178 // Eta-cont: letcont k x = j x in K -> K[j/k]. | 178 // Eta-cont: letcont k x = j x in K -> K[j/k]. |
| 179 // IR written by hand. | 179 // IR written by hand. |
| 180 | 180 |
| 181 String ETA_CONT_IN = """ | 181 String ETA_CONT_IN = """ |
| 182 (FunctionDefinition main ( return) | 182 (FunctionDefinition main ( return) |
| 183 (LetPrim v3 (Constant 0)) | 183 (LetPrim v3 (Constant IntConstant(0))) |
| 184 (LetCont* (k1 v1) (InvokeContinuation return v3)) | 184 (LetCont* (k1 v1) (InvokeContinuation return v3)) |
| 185 (LetCont (k0 v0) (InvokeContinuation k1 v0)) | 185 (LetCont (k0 v0) (InvokeContinuation k1 v0)) |
| 186 (LetPrim v4 | 186 (LetPrim v4 |
| 187 (CreateFunction | 187 (CreateFunction |
| 188 (FunctionDefinition f ( return) | 188 (FunctionDefinition f ( return) |
| 189 (InvokeContinuation k1 k0)))) | 189 (InvokeContinuation k1 k0)))) |
| 190 (InvokeContinuation k0 v3)) | 190 (InvokeContinuation k0 v3)) |
| 191 """; | 191 """; |
| 192 String ETA_CONT_OUT = """ | 192 String ETA_CONT_OUT = """ |
| 193 (FunctionDefinition main ( return) | 193 (FunctionDefinition main ( return) |
| 194 (LetPrim v0 (Constant 0)) | 194 (LetPrim v0 (Constant IntConstant(0))) |
| 195 (LetCont (k0 v1) (InvokeContinuation return v0)) | 195 (LetCont (k0 v1) (InvokeContinuation return v0)) |
| 196 (InvokeContinuation k0 v0)) | 196 (InvokeContinuation k0 v0)) |
| 197 """; | 197 """; |
| 198 | 198 |
| 199 // Beta-fun-lin and eta-fun might not apply to us, since | 199 // Beta-fun-lin and eta-fun might not apply to us, since |
| 200 // a. in (InvokeMethod v0 call k0), v0 might carry state, and | 200 // a. in (InvokeMethod v0 call k0), v0 might carry state, and |
| 201 // b. there is no way to generate static nested functions that we could | 201 // b. there is no way to generate static nested functions that we could |
| 202 // use InvokeStatic on. | 202 // use InvokeStatic on. |
| 203 | 203 |
| 204 /// Normalizes whitespace by replacing all whitespace sequences by a single | 204 /// Normalizes whitespace by replacing all whitespace sequences by a single |
| (...skipping 23 matching lines...) Expand all Loading... |
| 228 testShrinkingReducer(ITERATIVE_DEAD_VAL1_IN, ITERATIVE_DEAD_VAL1_OUT); | 228 testShrinkingReducer(ITERATIVE_DEAD_VAL1_IN, ITERATIVE_DEAD_VAL1_OUT); |
| 229 testShrinkingReducer(ITERATIVE_DEAD_VAL2_IN, ITERATIVE_DEAD_VAL2_OUT); | 229 testShrinkingReducer(ITERATIVE_DEAD_VAL2_IN, ITERATIVE_DEAD_VAL2_OUT); |
| 230 testShrinkingReducer(DEAD_CONT_IN, DEAD_CONT_OUT); | 230 testShrinkingReducer(DEAD_CONT_IN, DEAD_CONT_OUT); |
| 231 testShrinkingReducer(ITERATIVE_DEAD_CONT_IN, ITERATIVE_DEAD_CONT_OUT); | 231 testShrinkingReducer(ITERATIVE_DEAD_CONT_IN, ITERATIVE_DEAD_CONT_OUT); |
| 232 testShrinkingReducer(BETA_CONT_LIN_IN, BETA_CONT_LIN_OUT); | 232 testShrinkingReducer(BETA_CONT_LIN_IN, BETA_CONT_LIN_OUT); |
| 233 testShrinkingReducer(ARG_BETA_CONT_LIN_IN, ARG_BETA_CONT_LIN_OUT); | 233 testShrinkingReducer(ARG_BETA_CONT_LIN_IN, ARG_BETA_CONT_LIN_OUT); |
| 234 testShrinkingReducer(RECURSIVE_BETA_CONT_LIN_IN, RECURSIVE_BETA_CONT_LIN_OUT); | 234 testShrinkingReducer(RECURSIVE_BETA_CONT_LIN_IN, RECURSIVE_BETA_CONT_LIN_OUT); |
| 235 testShrinkingReducer(USED_BETA_CONT_LIN_IN, USED_BETA_CONT_LIN_OUT); | 235 testShrinkingReducer(USED_BETA_CONT_LIN_IN, USED_BETA_CONT_LIN_OUT); |
| 236 testShrinkingReducer(ETA_CONT_IN, ETA_CONT_OUT); | 236 testShrinkingReducer(ETA_CONT_IN, ETA_CONT_OUT); |
| 237 } | 237 } |
| OLD | NEW |