OLD | NEW |
| (Empty) |
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 | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 import 'dart:async'; | |
6 import '../mock_compiler.dart'; | |
7 import 'sexpr_unstringifier.dart'; | |
8 import 'package:async_helper/async_helper.dart'; | |
9 import "package:expect/expect.dart"; | |
10 import 'package:compiler/src/cps_ir/cps_ir_nodes_sexpr.dart'; | |
11 import 'package:compiler/src/cps_ir/optimizers.dart'; | |
12 import 'package:compiler/src/constant_system_dart.dart'; | |
13 | |
14 // The tests in this file that ensure that sparse constant propagation on the | |
15 // CPS IR works as expected. | |
16 | |
17 // CP1 represents the following incoming dart code: | |
18 // | |
19 // int main() { | |
20 // int i = 1; | |
21 // int j; | |
22 // if (i == 1) { | |
23 // j = 2; | |
24 // } else { | |
25 // j = 3; | |
26 // } | |
27 // return j; | |
28 // } | |
29 | |
30 String CP1_IN = """ | |
31 (FunctionDefinition main () () return | |
32 (LetPrim (v0 (Constant (Int 1))) | |
33 (LetPrim (v1 (Constant (Int 1))) | |
34 (LetCont | |
35 ((k0 (v2) | |
36 (LetCont | |
37 ((k1 () | |
38 (LetPrim (v3 (Constant (Int 2))) | |
39 (InvokeContinuation return (v3)))) | |
40 (k2 () | |
41 (LetPrim (v4 (Constant (Int 3))) | |
42 (InvokeContinuation return (v4))))) | |
43 (Branch (IsTrue v2) k1 k2)))) | |
44 (InvokeMethod v0 == (v1) k0))))) | |
45 """; | |
46 String CP1_OUT = """ | |
47 (FunctionDefinition main () () return | |
48 (LetPrim (v0 (Constant (Int 1))) | |
49 (LetPrim (v1 (Constant (Int 1))) | |
50 (LetCont | |
51 ((k0 (v2) | |
52 (LetCont | |
53 ((k1 () | |
54 (LetPrim (v3 (Constant (Int 2))) | |
55 (InvokeContinuation return (v3)))) | |
56 (k2 () | |
57 (LetPrim (v4 (Constant (Int 3))) | |
58 (InvokeContinuation return (v4))))) | |
59 (InvokeContinuation k1 ())))) | |
60 (LetPrim (v5 (Constant (Bool true))) | |
61 (InvokeContinuation k0 (v5))))))) | |
62 """; | |
63 | |
64 // CP2 represents the following incoming dart code: | |
65 // | |
66 // int main() { | |
67 // int i = 1; | |
68 // while (true) { | |
69 // if (false || false) { | |
70 // return i; | |
71 // } | |
72 // if (true && i == 1) { | |
73 // return i; | |
74 // } | |
75 // } | |
76 // return 42; | |
77 // } | |
78 | |
79 String CP2_IN = """ | |
80 (FunctionDefinition main () () return | |
81 (LetPrim (v0 (Constant (Int 1))) | |
82 (LetCont | |
83 ((rec k0 () | |
84 (LetCont | |
85 ((k1 () | |
86 (LetPrim (v1 (Constant (Int 42))) | |
87 (InvokeContinuation return (v1)))) | |
88 (k2 () | |
89 (LetPrim (v2 (Constant (Bool false))) | |
90 (LetCont | |
91 ((k3 (v3) | |
92 (LetCont | |
93 ((k4 () | |
94 (InvokeContinuation return (v0))) | |
95 (k5 () | |
96 (LetPrim (v4 (Constant (Bool true))) | |
97 (LetCont | |
98 ((k6 (v5) | |
99 (LetCont | |
100 ((k7 () | |
101 (InvokeContinuation return (v0
))) | |
102 (k8 () | |
103 (InvokeContinuation rec k0 ())
)) | |
104 (Branch (IsTrue v5) k7 k8)))) | |
105 (LetCont | |
106 ((k9 () | |
107 (LetPrim (v6 (Constant (Int 1))) | |
108 (LetCont | |
109 ((k10 (v7) | |
110 (LetCont | |
111 ((k11 () | |
112 (LetPrim (v8 (Const
ant (Bool true))) | |
113 (InvokeContinuati
on k6 (v8)))) | |
114 (k12 () | |
115 (LetPrim (v9 (Const
ant (Bool false))) | |
116 (InvokeContinuati
on k6 (v9))))) | |
117 (Branch (IsTrue v7) k11
k12)))) | |
118 (InvokeMethod v0 == (v6) k10)))
) | |
119 (k13 () | |
120 (LetPrim (v10 (Constant (Bool false
))) | |
121 (InvokeContinuation k6 (v10))))) | |
122 (Branch (IsTrue v4) k9 k13)))))) | |
123 (Branch (IsTrue v3) k4 k5)))) | |
124 (LetCont | |
125 ((k14 () | |
126 (LetPrim (v11 (Constant (Bool true))) | |
127 (InvokeContinuation k3 (v11)))) | |
128 (k15 () | |
129 (LetPrim (v12 (Constant (Bool false))) | |
130 (LetCont | |
131 ((k16 () | |
132 (LetPrim (v13 (Constant (Bool true))) | |
133 (InvokeContinuation k3 (v13)))) | |
134 (k17 () | |
135 (LetPrim (v14 (Constant (Bool false))) | |
136 (InvokeContinuation k3 (v14))))) | |
137 (Branch (IsTrue v12) k16 k17))))) | |
138 (Branch (IsTrue v2) k14 k15)))))) | |
139 (LetPrim (v15 (Constant (Bool true))) | |
140 (Branch (IsTrue v15) k2 k1))))) | |
141 (InvokeContinuation k0 ())))) | |
142 """; | |
143 String CP2_OUT = """ | |
144 (FunctionDefinition main () () return | |
145 (LetPrim (v0 (Constant (Int 1))) | |
146 (LetCont | |
147 ((rec k0 () | |
148 (LetCont | |
149 ((k1 () | |
150 (LetPrim (v1 (Constant (Int 42))) | |
151 (InvokeContinuation return (v1)))) | |
152 (k2 () | |
153 (LetPrim (v2 (Constant (Bool false))) | |
154 (LetCont | |
155 ((k3 (v3) | |
156 (LetCont | |
157 ((k4 () | |
158 (InvokeContinuation return (v0))) | |
159 (k5 () | |
160 (LetPrim (v4 (Constant (Bool true))) | |
161 (LetCont | |
162 ((k6 (v5) | |
163 (LetCont | |
164 ((k7 () | |
165 (InvokeContinuation return (v0
))) | |
166 (k8 () | |
167 (InvokeContinuation rec k0 ())
)) | |
168 (InvokeContinuation k7 ())))) | |
169 (LetCont | |
170 ((k9 () | |
171 (LetPrim (v6 (Constant (Int 1))) | |
172 (LetCont | |
173 ((k10 (v7) | |
174 (LetCont | |
175 ((k11 () | |
176 (LetPrim (v8 (Const
ant (Bool true))) | |
177 (InvokeContinuati
on k6 (v8)))) | |
178 (k12 () | |
179 (LetPrim (v9 (Const
ant (Bool false))) | |
180 (InvokeContinuati
on k6 (v9))))) | |
181 (InvokeContinuation k11
())))) | |
182 (LetPrim (v10 (Constant (Bool t
rue))) | |
183 (InvokeContinuation k10 (v10)
))))) | |
184 (k13 () | |
185 (LetPrim (v11 (Constant (Bool false
))) | |
186 (InvokeContinuation k6 (v11))))) | |
187 (InvokeContinuation k9 ())))))) | |
188 (InvokeContinuation k5 ())))) | |
189 (LetCont | |
190 ((k14 () | |
191 (LetPrim (v12 (Constant (Bool true))) | |
192 (InvokeContinuation k3 (v12)))) | |
193 (k15 () | |
194 (LetPrim (v13 (Constant (Bool false))) | |
195 (LetCont | |
196 ((k16 () | |
197 (LetPrim (v14 (Constant (Bool true))) | |
198 (InvokeContinuation k3 (v14)))) | |
199 (k17 () | |
200 (LetPrim (v15 (Constant (Bool false))) | |
201 (InvokeContinuation k3 (v15))))) | |
202 (InvokeContinuation k17 ()))))) | |
203 (InvokeContinuation k15 ())))))) | |
204 (LetPrim (v16 (Constant (Bool true))) | |
205 (InvokeContinuation k2 ()))))) | |
206 (InvokeContinuation k0 ())))) | |
207 """; | |
208 | |
209 // CP3 represents the following incoming dart code: | |
210 // | |
211 // int main() { | |
212 // int i = 1; | |
213 // i = f(); | |
214 // if (i == 1) { | |
215 // return 42; | |
216 // } | |
217 // return i; | |
218 // } | |
219 | |
220 String CP3_IN = """ | |
221 (FunctionDefinition main () () return | |
222 (LetPrim (v0 (Constant (Int 1))) | |
223 (LetCont | |
224 ((k0 (v1) | |
225 (LetPrim (v2 (Constant (Int 1))) | |
226 (LetCont | |
227 ((k1 (v3) | |
228 (LetCont | |
229 ((k2 () | |
230 (LetPrim (v4 (Constant (Int 42))) | |
231 (InvokeContinuation return (v4)))) | |
232 (k3 () | |
233 (InvokeContinuation return (v1)))) | |
234 (Branch (IsTrue v3) k2 k3)))) | |
235 (InvokeMethod v1 == (v2) k1))))) | |
236 (InvokeStatic f () k0)))) | |
237 """; | |
238 String CP3_OUT = CP3_IN; | |
239 | |
240 // Addition. | |
241 | |
242 String CP4_IN = """ | |
243 (FunctionDefinition main () () return | |
244 (LetPrim (v0 (Constant (Int 1))) | |
245 (LetPrim (v1 (Constant (Int 2))) | |
246 (LetCont | |
247 ((k0 (v2) | |
248 (InvokeContinuation return (v2)))) | |
249 (InvokeMethod v0 + (v1) k0))))) | |
250 """; | |
251 String CP4_OUT = """ | |
252 (FunctionDefinition main () () return | |
253 (LetPrim (v0 (Constant (Int 1))) | |
254 (LetPrim (v1 (Constant (Int 2))) | |
255 (LetCont | |
256 ((k0 (v2) | |
257 (InvokeContinuation return (v2)))) | |
258 (LetPrim (v3 (Constant (Int 3))) | |
259 (InvokeContinuation k0 (v3))))))) | |
260 """; | |
261 | |
262 // Array access operator (no optimization). | |
263 | |
264 String CP5_IN = """ | |
265 (FunctionDefinition main () () return | |
266 (LetPrim (v0 (Constant (Int 1))) | |
267 (LetPrim (v1 (Constant (Int 2))) | |
268 (LetCont | |
269 ((k0 (v2) | |
270 (InvokeContinuation return (v2)))) | |
271 (InvokeMethod v0 [] (v1) k0))))) | |
272 """; | |
273 String CP5_OUT = CP5_IN; | |
274 | |
275 // Division by 0. | |
276 | |
277 String CP6_IN = """ | |
278 (FunctionDefinition main () () return | |
279 (LetPrim (v0 (Constant (Int 1))) | |
280 (LetPrim (v1 (Constant (Int 0))) | |
281 (LetCont | |
282 ((k0 (v2) | |
283 (InvokeContinuation return (v2)))) | |
284 (InvokeMethod v0 / (v1) k0))))) | |
285 """; | |
286 String CP6_OUT = """ | |
287 (FunctionDefinition main () () return | |
288 (LetPrim (v0 (Constant (Int 1))) | |
289 (LetPrim (v1 (Constant (Int 0))) | |
290 (LetCont | |
291 ((k0 (v2) | |
292 (InvokeContinuation return (v2)))) | |
293 (LetPrim (v3 (Constant (Double Infinity))) | |
294 (InvokeContinuation k0 (v3))))))) | |
295 """; | |
296 | |
297 // Concatenate strings. | |
298 | |
299 String CP7_IN = """ | |
300 (FunctionDefinition main () () return | |
301 (LetPrim (v0 (Constant (String "b"))) | |
302 (LetPrim (v1 (Constant (String "d"))) | |
303 (LetPrim (v2 (Constant (String "a"))) | |
304 (LetPrim (v3 (Constant (String "c"))) | |
305 (LetPrim (v4 (Constant (String ""))) | |
306 (LetCont | |
307 ((k0 (v5) | |
308 (LetCont | |
309 ((k1 (v6) | |
310 (InvokeContinuation return (v6)))) | |
311 (InvokeMethod v5 length () k1)))) | |
312 (ConcatenateStrings (v2 v0 v3 v1 v4) k0)))))))) | |
313 """; | |
314 String CP7_OUT = """ | |
315 (FunctionDefinition main () () return | |
316 (LetPrim (v0 (Constant (String "b"))) | |
317 (LetPrim (v1 (Constant (String "d"))) | |
318 (LetPrim (v2 (Constant (String "a"))) | |
319 (LetPrim (v3 (Constant (String "c"))) | |
320 (LetPrim (v4 (Constant (String ""))) | |
321 (LetCont | |
322 ((k0 (v5) | |
323 (LetCont | |
324 ((k1 (v6) | |
325 (InvokeContinuation return (v6)))) | |
326 (InvokeMethod v5 length () k1)))) | |
327 (LetPrim (v7 (Constant (String "abcd"))) | |
328 (InvokeContinuation k0 (v7)))))))))) | |
329 """; | |
330 | |
331 // TODO(jgruber): We can't test is-check optimization because the unstringifier | |
332 // does not recreate accurate types for the TypeOperator node. | |
333 | |
334 // Simple branch removal. | |
335 | |
336 String CP8_IN = """ | |
337 (FunctionDefinition main () () return | |
338 (LetPrim (v0 (Constant (Int 1))) | |
339 (LetPrim (v1 (Constant (Int 1))) | |
340 (LetCont | |
341 ((k0 (v2) | |
342 (LetCont | |
343 ((k1 () | |
344 (LetPrim (v3 (Constant (Int 42))) | |
345 (InvokeContinuation return (v3)))) | |
346 (k2 () | |
347 (InvokeContinuation return (v0)))) | |
348 (Branch (IsTrue v2) k1 k2)))) | |
349 (InvokeMethod v0 == (v1) k0))))) | |
350 """; | |
351 String CP8_OUT = """ | |
352 (FunctionDefinition main () () return | |
353 (LetPrim (v0 (Constant (Int 1))) | |
354 (LetPrim (v1 (Constant (Int 1))) | |
355 (LetCont | |
356 ((k0 (v2) | |
357 (LetCont | |
358 ((k1 () | |
359 (LetPrim (v3 (Constant (Int 42))) | |
360 (InvokeContinuation return (v3)))) | |
361 (k2 () | |
362 (InvokeContinuation return (v0)))) | |
363 (InvokeContinuation k1 ())))) | |
364 (LetPrim (v4 (Constant (Bool true))) | |
365 (InvokeContinuation k0 (v4))))))) | |
366 """; | |
367 | |
368 // While loop. | |
369 | |
370 String CP9_IN = """ | |
371 (FunctionDefinition main () () return | |
372 (LetPrim (v0 (Constant (Int 1))) | |
373 (LetCont | |
374 ((rec k0 (v1) | |
375 (LetCont | |
376 ((k1 () | |
377 (InvokeContinuation return (v1))) | |
378 (k2 () | |
379 (LetPrim (v2 (Constant (Int 1))) | |
380 (LetCont | |
381 ((k3 (v3) | |
382 (LetCont | |
383 ((k4 (v4) | |
384 (LetCont | |
385 ((k5 () | |
386 (LetPrim (v5 (Constant (Int 42))) | |
387 (InvokeContinuation return (v5)))) | |
388 (k6 () | |
389 (LetPrim (v6 (Constant (Int 1))) | |
390 (LetCont | |
391 ((k7 (v7) | |
392 (InvokeContinuation rec k0 (v7
)))) | |
393 (InvokeMethod v1 + (v6) k7))))) | |
394 (Branch (IsTrue v4) k5 k6)))) | |
395 (LetCont | |
396 ((k8 () | |
397 (LetPrim (v8 (Constant (Bool false))) | |
398 (InvokeContinuation k4 (v8)))) | |
399 (k9 () | |
400 (LetPrim (v9 (Constant (Bool true))) | |
401 (InvokeContinuation k4 (v9))))) | |
402 (Branch (IsTrue v3) k8 k9))))) | |
403 (InvokeMethod v1 == (v2) k3))))) | |
404 (LetPrim (v10 (Constant (Bool true))) | |
405 (Branch (IsTrue v10) k2 k1))))) | |
406 (InvokeContinuation k0 (v0))))) | |
407 """; | |
408 String CP9_OUT = """ | |
409 (FunctionDefinition main () () return | |
410 (LetPrim (v0 (Constant (Int 1))) | |
411 (LetCont | |
412 ((rec k0 (v1) | |
413 (LetCont | |
414 ((k1 () | |
415 (InvokeContinuation return (v1))) | |
416 (k2 () | |
417 (LetPrim (v2 (Constant (Int 1))) | |
418 (LetCont | |
419 ((k3 (v3) | |
420 (LetCont | |
421 ((k4 (v4) | |
422 (LetCont | |
423 ((k5 () | |
424 (LetPrim (v5 (Constant (Int 42))) | |
425 (InvokeContinuation return (v5)))) | |
426 (k6 () | |
427 (LetPrim (v6 (Constant (Int 1))) | |
428 (LetCont | |
429 ((k7 (v7) | |
430 (InvokeContinuation rec k0 (v7)
))) | |
431 (InvokeMethod v1 + (v6) k7))))) | |
432 (Branch (IsTrue v4) k5 k6)))) | |
433 (LetCont | |
434 ((k8 () | |
435 (LetPrim (v8 (Constant (Bool false))) | |
436 (InvokeContinuation k4 (v8)))) | |
437 (k9 () | |
438 (LetPrim (v9 (Constant (Bool true))) | |
439 (InvokeContinuation k4 (v9))))) | |
440 (Branch (IsTrue v3) k8 k9))))) | |
441 (InvokeMethod v1 == (v2) k3))))) | |
442 (LetPrim (v10 (Constant (Bool true))) | |
443 (InvokeContinuation k2 ()))))) | |
444 (InvokeContinuation k0 (v0))))) | |
445 """; | |
446 | |
447 // While loop, from: | |
448 // | |
449 // int main() { | |
450 // for (int i = 0; i < 2; i++) { | |
451 // print(42 + i); | |
452 // } | |
453 // } | |
454 | |
455 String CP10_IN = """ | |
456 (FunctionDefinition main () () return | |
457 (LetPrim (v0 (Constant (Int 0))) | |
458 (LetCont | |
459 ((rec k0 (v1) | |
460 (LetCont | |
461 ((k1 () | |
462 (LetPrim (v2 (Constant (Null))) | |
463 (InvokeContinuation return (v2)))) | |
464 (k2 () | |
465 (LetPrim (v3 (Constant (Int 42))) | |
466 (LetCont | |
467 ((k3 (v4) | |
468 (LetCont | |
469 ((k4 (v5) | |
470 (LetPrim (v6 (Constant (Int 1))) | |
471 (LetCont | |
472 ((k5 (v7) | |
473 (InvokeContinuation rec k0 (v7)))) | |
474 (InvokeMethod v1 + (v6) k5))))) | |
475 (InvokeStatic print (v4) k4)))) | |
476 (InvokeMethod v3 + (v1) k3))))) | |
477 (LetPrim (v8 (Constant (Int 2))) | |
478 (LetCont | |
479 ((k6 (v9) | |
480 (Branch (IsTrue v9) k2 k1))) | |
481 (InvokeMethod v1 < (v8) k6)))))) | |
482 (InvokeContinuation k0 (v0))))) | |
483 """; | |
484 String CP10_OUT = CP10_IN; | |
485 | |
486 /// Normalizes whitespace by replacing all whitespace sequences by a single | |
487 /// space and trimming leading and trailing whitespace. | |
488 String normalizeSExpr(String input) { | |
489 return input.replaceAll(new RegExp(r'[ \n\t]+'), ' ').trim(); | |
490 } | |
491 | |
492 /// Parses the given input IR, runs an optimization pass over it, and compares | |
493 /// the stringification of the result against the expected output. | |
494 Future testConstantPropagator(String input, String expectedOutput) { | |
495 final compiler = new MockCompiler.internal( | |
496 emitJavaScript: false, | |
497 enableMinification: false); | |
498 return compiler.init().then((_) { | |
499 final unstringifier = new SExpressionUnstringifier(); | |
500 final stringifier = new SExpressionStringifier(); | |
501 final optimizer = new TypePropagator( | |
502 compiler.types, | |
503 DART_CONSTANT_SYSTEM, | |
504 new UnitTypeSystem(), | |
505 compiler.internalError); | |
506 | |
507 final f = unstringifier.unstringify(input); | |
508 optimizer.rewrite(f); | |
509 | |
510 String expected = normalizeSExpr(expectedOutput); | |
511 String actual = normalizeSExpr(stringifier.visit(f)); | |
512 | |
513 Expect.equals(expected, actual); | |
514 }); | |
515 } | |
516 | |
517 void main() { | |
518 asyncTest(() => testConstantPropagator(CP1_IN, CP1_OUT)); | |
519 asyncTest(() => testConstantPropagator(CP2_IN, CP2_OUT)); | |
520 asyncTest(() => testConstantPropagator(CP3_IN, CP3_OUT)); | |
521 asyncTest(() => testConstantPropagator(CP4_IN, CP4_OUT)); | |
522 asyncTest(() => testConstantPropagator(CP5_IN, CP5_OUT)); | |
523 asyncTest(() => testConstantPropagator(CP6_IN, CP6_OUT)); | |
524 asyncTest(() => testConstantPropagator(CP7_IN, CP7_OUT)); | |
525 asyncTest(() => testConstantPropagator(CP8_IN, CP8_OUT)); | |
526 asyncTest(() => testConstantPropagator(CP9_IN, CP9_OUT)); | |
527 asyncTest(() => testConstantPropagator(CP10_IN, CP10_OUT)); | |
528 } | |
OLD | NEW |