Implement shrinking reductions in CPS IR

tests/compiler/dart2js/backend_dart/opt_shrinking_test.dart

+// 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/implementation/cps_ir/cps_ir_nodes.dart';
+import 'package:compiler/implementation/cps_ir/cps_ir_nodes_sexpr.dart';
+import 'package:compiler/implementation/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 42))
+  (LetPrim v1 (Constant 0)) (InvokeContinuation return v1))
+""";
+String DEAD_VAL_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 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 42))
+  (LetPrim v1 (Constant 1))
+  (LetCont (k0 v2) (LetPrim v3 (Constant 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 42))
+  (LetPrim v1
+    (CreateFunction
+      (FunctionDefinition f (i return)
+        (InvokeContinuation return v0))))
+  (LetPrim v2 (Constant 0))
+  (InvokeContinuation return v2))
+""";
+String ITERATIVE_DEAD_VAL2_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 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 0))
+  (LetCont (k0 v0) (InvokeConstructor List return))
+  (LetCont (k1 v1)
+    (LetCont (k2 v2) (LetPrim v3 (Constant 0))
+      (InvokeContinuation return v3))
+    (InvokeStatic print v4 k2))
+  (InvokeStatic print v4 k1))
+""";
+String DEAD_CONT_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 0))
+  (LetCont (k0 v1)
+    (LetCont (k1 v2) (LetPrim v3 (Constant 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 0))
+  (LetCont (k0 v0) (InvokeConstructor List return))
+  (LetCont (k3 v5) (InvokeContinuation k0 v5))
+  (LetCont (k1 v1) 
+    (LetCont (k2 v2) (LetPrim v3 (Constant 0))
+      (InvokeContinuation return v3))
+    (InvokeStatic print v4 k2))
+  (InvokeStatic print v4 k1))
+""";
+String ITERATIVE_DEAD_CONT_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 0))
+  (LetCont (k0 v1) 
+    (LetCont (k1 v2) (LetPrim v3 (Constant 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 0))
+        (InvokeContinuation return v3))
+      (InvokeStatic print v0 k2))
+    (InvokeStatic print v0 k1))
+  (LetPrim v4 (Constant 0))
+  (InvokeContinuation k0 v4))
+""";
+String BETA_CONT_LIN_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 0))
+  (LetCont (k0 v1)
+    (LetCont (k1 v2) (LetPrim v3 (Constant 0))
+      (InvokeContinuation return v3))
+    (InvokeStatic print v0 k1))
+  (InvokeStatic print v0 k0))
+""";
+
+// Beta-cont-lin with continuation passed as arg in invoke. IR written by hand.
+
+String ARG_BETA_CONT_LIN_IN = """
+(FunctionDefinition main ( return)
+  (LetCont (k0 v0)
+    (LetPrim v1 (Constant 0))
+    (InvokeStatic print v1 return))
+  (InvokeContinuation return k0))
+""";
+String ARG_BETA_CONT_LIN_OUT = ARG_BETA_CONT_LIN_IN;
+
+// Beta-cont-lin with recursive continuation. IR written by hand.
+
+String RECURSIVE_BETA_CONT_LIN_IN = """
+(FunctionDefinition main ( return)
+  (LetCont* (k0 v0)
+    (InvokeContinuation* k0 v0))
+  (LetPrim v1 (Constant 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)
+  (LetCont (k0 v0)
+    (LetCont (k1 v1)
+      (LetCont (k2 v2) (LetPrim v3 (Constant 0))
+        (InvokeContinuation return v3))
+      (InvokeStatic print v0 k2))
+    (InvokeStatic print v0 k1))
+    (LetPrim v4
+      (CreateFunction
+        (FunctionDefinition f ( return)
+          (InvokeContinuation return k0))))
+  (InvokeContinuation k0 v4))
+""";
+String USED_BETA_CONT_LIN_OUT = USED_BETA_CONT_LIN_IN;
+
+// Eta-cont: letcont k x = j x in K -> K[j/k].
+// IR written by hand.
+
+String ETA_CONT_IN = """
+(FunctionDefinition main ( return)
+  (LetPrim v3 (Constant 0))
+  (LetCont* (k1 v1) (InvokeContinuation return v3))
+  (LetCont (k0 v0) (InvokeContinuation k1 v0))
+  (LetPrim v4
+    (CreateFunction
+      (FunctionDefinition f ( return)
+        (InvokeContinuation k1 k0))))
+  (InvokeContinuation k0 v3))
+""";
+String ETA_CONT_OUT = """
+(FunctionDefinition main ( return)
+  (LetPrim v0 (Constant 0))
+  (LetCont* (k0 v1) (InvokeContinuation return v0))
+  (InvokeContinuation k0 v0))
+""";
+
+// 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(ARG_BETA_CONT_LIN_IN, ARG_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);
+}