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