Index: tests/compiler/dart2js/backend_dart/opt_shrinking_test.dart |
diff --git a/tests/compiler/dart2js/backend_dart/opt_shrinking_test.dart b/tests/compiler/dart2js/backend_dart/opt_shrinking_test.dart |
deleted file mode 100644 |
index 906a6cf7b089885a54cd653af78b929a0ff8aed7..0000000000000000000000000000000000000000 |
--- a/tests/compiler/dart2js/backend_dart/opt_shrinking_test.dart |
+++ /dev/null |
@@ -1,331 +0,0 @@ |
-// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
-// for details. All rights reserved. Use of this source code is governed by a |
-// BSD-style license that can be found in the LICENSE file. |
- |
-import 'sexpr_unstringifier.dart'; |
-import "package:expect/expect.dart"; |
-import 'package:compiler/src/cps_ir/cps_ir_nodes.dart'; |
-import 'package:compiler/src/cps_ir/cps_ir_nodes_sexpr.dart'; |
-import 'package:compiler/src/cps_ir/optimizers.dart'; |
- |
-// The tests in this file that ensure shrinking reductions work as expected. |
-// Reductions and their corresponding names are taken from |
-// 'Compiling with Continuations, Continued' by Andrew Kennedy. |
- |
-// Basic dead-val: letprim x = V in K -> K (x not free in K). |
-// |
-// int main() { |
-// int i = 42; |
-// return 0; |
-// } |
- |
-String DEAD_VAL_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 42))) |
- (LetPrim (v1 (Constant (Int 0))) |
- (InvokeContinuation return (v1))))) |
-"""; |
-String DEAD_VAL_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (InvokeContinuation return (v0)))) |
-"""; |
- |
-// Iterative dead-val. No optimizations possible since the continuation to |
-// InvokeMethod must have one argument, even if it is unused. |
-// |
-// int main() { |
-// int i = 42; |
-// int j = i + 1; |
-// return 0; |
-// } |
- |
-String ITERATIVE_DEAD_VAL1_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 42))) |
- (LetPrim (v1 (Constant (Int 1))) |
- (LetCont ((k0 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeMethod v0 + (v1) k0))))) |
-"""; |
-String ITERATIVE_DEAD_VAL1_OUT = ITERATIVE_DEAD_VAL1_IN; |
- |
-// Iterative dead-val. IR written by hand. |
- |
-String ITERATIVE_DEAD_VAL2_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 42))) |
- (LetPrim (v1 |
- (CreateFunction |
- (FunctionDefinition f () (i) return |
- (InvokeContinuation return (v0))))) |
- (LetPrim (v2 (Constant (Int 0))) |
- (InvokeContinuation return (v2)))))) |
-"""; |
-String ITERATIVE_DEAD_VAL2_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (InvokeContinuation return (v0)))) |
-"""; |
- |
-// Basic dead-cont: letcont k x = L in K -> K (k not free in K). |
-// IR written by hand. |
- |
-String DEAD_CONT_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v4 (Constant (Int 0))) |
- (LetCont ((k0 (v0) |
- (InvokeConstructor List () return))) |
- (LetCont ((k1 (v1) |
- (LetCont ((k2 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v4) k2)))) |
- (InvokeStatic print (v4) k1))))) |
-"""; |
-String DEAD_CONT_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((k0 (v1) |
- (LetCont ((k1 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v0) k1)))) |
- (InvokeStatic print (v0) k0)))) |
-"""; |
- |
-// Iterative dead-cont. IR written by hand. |
- |
-String ITERATIVE_DEAD_CONT_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v4 (Constant (Int 0))) |
- (LetCont ((k0 (v0) |
- (InvokeConstructor List () return))) |
- (LetCont ((k3 (v5) |
- (InvokeContinuation k0 (v5)))) |
- (LetCont ((k1 (v1) |
- (LetCont ((k2 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v4) k2)))) |
- (InvokeStatic print (v4) k1)))))) |
-"""; |
-String ITERATIVE_DEAD_CONT_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((k0 (v1) |
- (LetCont ((k1 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v0) k1)))) |
- (InvokeStatic print (v0) k0)))) |
-"""; |
- |
-// Beta-cont-lin: letcont k x = K in C[k y] -> C[K[y/x]] (k not free in C). |
-// IR written by hand. |
- |
-String BETA_CONT_LIN_IN = """ |
-(FunctionDefinition main () () return |
- (LetCont ((k0 (v0) |
- (LetCont ((k1 (v1) |
- (LetCont ((k2 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v0) k2)))) |
- (InvokeStatic print (v0) k1)))) |
- (LetPrim (v4 (Constant (Int 0))) |
- (InvokeContinuation k0 (v4))))) |
-"""; |
-String BETA_CONT_LIN_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((k0 (v1) |
- (LetCont ((k1 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v0) k1)))) |
- (InvokeStatic print (v0) k0)))) |
-"""; |
- |
-// Beta-cont-lin with recursive continuation. IR written by hand. |
- |
-String RECURSIVE_BETA_CONT_LIN_IN = """ |
-(FunctionDefinition main () () return |
- (LetCont ((rec k0 (v0) |
- (InvokeContinuation rec k0 (v0)))) |
- (LetPrim (v1 (Constant (Int 0))) |
- (InvokeContinuation k0 (v1))))) |
-"""; |
-String RECURSIVE_BETA_CONT_LIN_OUT = RECURSIVE_BETA_CONT_LIN_IN; |
- |
-// Beta-cont-lin used inside body. IR written by hand. |
- |
-String USED_BETA_CONT_LIN_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((k0 (v1) |
- (LetCont ((k1 (v2) |
- (LetCont ((k2 (v3) |
- (LetPrim (v4 (Constant (Int 0))) |
- (InvokeContinuation return (v4))))) |
- (InvokeStatic print (v1) k2)))) |
- (InvokeStatic print (v1) k1)))) |
- (LetPrim (v5 |
- (CreateFunction |
- (FunctionDefinition f () () return |
- (InvokeContinuation return (v1))))) |
- (InvokeContinuation k0 (v0)))))) |
-"""; |
-String USED_BETA_CONT_LIN_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((k0 (v1) |
- (LetCont ((k1 (v2) |
- (LetPrim (v3 (Constant (Int 0))) |
- (InvokeContinuation return (v3))))) |
- (InvokeStatic print (v0) k1)))) |
- (InvokeStatic print (v0) k0)))) |
-"""; |
- |
-// Eta-cont: letcont k x = j x in K -> K[j/k]. |
-// IR written by hand. |
-// |
-// This test is incorrectly named: with the current implementation, there is no |
-// eta reduction. Instead, dead-parameter, beta-cont-lin, and dead-val |
-// reductions are performed, which in turn creates a second beta-cont-lin |
-// reduction. |
-// |
-// TODO(kmillikin): To test continuation eta reduction, use eta redexes that are |
-// not overlapping beta redexes. |
-String ETA_CONT_IN = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (LetCont ((rec k0 (v1) |
- (InvokeContinuation return (v0)))) |
- (LetCont ((k1 (v2) |
- (InvokeContinuation k0 (v2)))) |
- (LetPrim (v3 |
- (CreateFunction |
- (FunctionDefinition f () () return |
- (InvokeContinuation k0 (v0))))) |
- (InvokeContinuation k1 (v0))))))) |
-"""; |
-String ETA_CONT_OUT = """ |
-(FunctionDefinition main () () return |
- (LetPrim (v0 (Constant (Int 0))) |
- (InvokeContinuation return (v0)))) |
-"""; |
- |
-// Dead-parameter: |
-// letcont k x = E0 in E1 -> letcont k () = E0 in E1, |
-// if x does not occur free in E0. |
- |
-// Parameter v1 is unused in k0. |
-String DEAD_PARAMETER_IN = """ |
-(FunctionDefinition main () (x) return |
- (LetCont ((k0 (v0 v1 v2) |
- (InvokeStatic foo (v0 v2) return))) |
- (LetCont ((k1 () |
- (LetPrim (v3 (Constant (Int 0))) |
- (LetPrim (v4 (Constant (Int 1))) |
- (LetPrim (v5 (Constant (Int 2))) |
- (InvokeContinuation k0 (v3 v4 v5)))))) |
- (k2 () |
- (LetPrim (v6 (Constant (Int 3))) |
- (LetPrim (v7 (Constant (Int 4))) |
- (LetPrim (v8 (Constant (Int 5))) |
- (InvokeContinuation k0 (v6 v7 v8))))))) |
- (Branch (IsTrue x) k1 k2)))) |
-"""; |
-String DEAD_PARAMETER_OUT = """ |
-(FunctionDefinition main () (x) return |
- (LetCont ((k0 (v0 v1) |
- (InvokeStatic foo (v0 v1) return))) |
- (LetCont ((k1 () |
- (LetPrim (v2 (Constant (Int 0))) |
- (LetPrim (v3 (Constant (Int 2))) |
- (InvokeContinuation k0 (v2 v3))))) |
- (k2 () |
- (LetPrim (v4 (Constant (Int 3))) |
- (LetPrim (v5 (Constant (Int 5))) |
- (InvokeContinuation k0 (v4 v5)))))) |
- (Branch (IsTrue x) k1 k2)))) |
-"""; |
- |
-// Create an eta-cont redex: |
-// Dead parameter reductions can create an eta-cont redex by removing unused |
-// continuation parameters and thus creating the eta redex. |
-String CREATE_ETA_CONT_IN = """ |
-(FunctionDefinition main () (x) return |
- (LetCont ((rec loop (v0) |
- (InvokeContinuation rec loop (v0)))) |
- (LetCont ((created (v1 v2 v3) |
- (InvokeContinuation loop (v2)))) |
- (LetCont ((then () |
- (LetPrim (v4 (Constant (Int 0))) |
- (LetPrim (v5 (Constant (Int 1))) |
- (LetPrim (v6 (Constant (Int 2))) |
- (InvokeContinuation created (v4 v5 v6)))))) |
- (else () |
- (LetPrim (v6 (Constant (Int 3))) |
- (LetPrim (v7 (Constant (Int 4))) |
- (LetPrim (v8 (Constant (Int 5))) |
- (InvokeContinuation created (v6 v7 v8))))))) |
- (Branch (IsTrue x) then else))))) |
-"""; |
-String CREATE_ETA_CONT_OUT = """ |
-(FunctionDefinition main () (x) return |
- (LetCont ((rec k0 (v0) |
- (InvokeContinuation rec k0 (v0)))) |
- (LetCont ((k1 () |
- (LetPrim (v1 (Constant (Int 1))) |
- (InvokeContinuation k0 (v1)))) |
- (k2 () |
- (LetPrim (v2 (Constant (Int 4))) |
- (InvokeContinuation k0 (v2))))) |
- (Branch (IsTrue x) k1 k2)))) |
-"""; |
- |
- |
- |
-// Beta-fun-lin and eta-fun might not apply to us, since |
-// a. in (InvokeMethod v0 call k0), v0 might carry state, and |
-// b. there is no way to generate static nested functions that we could |
-// use InvokeStatic on. |
- |
-/// Normalizes whitespace by replacing all whitespace sequences by a single |
-/// space and trimming leading and trailing whitespace. |
-String normalizeSExpr(String input) { |
- return input.replaceAll(new RegExp(r'[ \n\t]+'), ' ').trim(); |
-} |
- |
-/// Parses the given input IR, runs an optimization pass over it, and compares |
-/// the stringification of the result against the expected output. |
-void testShrinkingReducer(String input, String expectedOutput) { |
- final unstringifier = new SExpressionUnstringifier(); |
- final stringifier = new SExpressionStringifier(); |
- final optimizer = new ShrinkingReducer(); |
- |
- FunctionDefinition f = unstringifier.unstringify(input); |
- optimizer.rewrite(f); |
- |
- String expected = normalizeSExpr(expectedOutput); |
- String actual = normalizeSExpr(stringifier.visit(f)); |
- |
- Expect.equals(expected, actual); |
-} |
- |
-void main() { |
- testShrinkingReducer(DEAD_VAL_IN, DEAD_VAL_OUT); |
- testShrinkingReducer(ITERATIVE_DEAD_VAL1_IN, ITERATIVE_DEAD_VAL1_OUT); |
- testShrinkingReducer(ITERATIVE_DEAD_VAL2_IN, ITERATIVE_DEAD_VAL2_OUT); |
- testShrinkingReducer(DEAD_CONT_IN, DEAD_CONT_OUT); |
- testShrinkingReducer(ITERATIVE_DEAD_CONT_IN, ITERATIVE_DEAD_CONT_OUT); |
- testShrinkingReducer(BETA_CONT_LIN_IN, BETA_CONT_LIN_OUT); |
- testShrinkingReducer(RECURSIVE_BETA_CONT_LIN_IN, RECURSIVE_BETA_CONT_LIN_OUT); |
- testShrinkingReducer(USED_BETA_CONT_LIN_IN, USED_BETA_CONT_LIN_OUT); |
- testShrinkingReducer(ETA_CONT_IN, ETA_CONT_OUT); |
- testShrinkingReducer(DEAD_PARAMETER_IN, DEAD_PARAMETER_OUT); |
- testShrinkingReducer(CREATE_ETA_CONT_IN, CREATE_ETA_CONT_OUT); |
-} |