// 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 'read in loop' IR tests the most basic case of redundant phi removal
// and represents the following source code:
//
// void main() {
//   int j = 42;
//   for (int i = 0; i < 2; i++) {
//     print(j.toString());
//   }
// }

String READ_IN_LOOP_IN = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 42)))
    (LetPrim (v1 (Constant (Int 0)))
      (LetCont
          ((rec k0 (v2 v3)
             (LetCont
                 ((k1 ()
                    (LetPrim (v4 (Constant (Null)))
                      (InvokeContinuation return (v4))))
                  (k2 ()
                    (LetCont
                        ((k3 (v5)
                           (LetCont
                               ((k4 (v6)
                                  (LetPrim (v7 (Constant (Int 1)))
                                    (LetCont
                                        ((k5 (v8)
                                           (InvokeContinuation rec k0 (v2 v8))))
                                      (InvokeMethod v3 + (v7) k5)))))
                             (InvokeStatic print (v5) k4))))
                      (InvokeMethod v2 toString () k3))))
               (LetPrim (v9 (Constant (Int 2)))
                 (LetCont
                     ((k6 (v10)
                        (Branch (IsTrue v10) k2 k1)))
                   (InvokeMethod v3 < (v9) k6))))))
        (InvokeContinuation k0 (v0 v1))))))
""";

String READ_IN_LOOP_OUT = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 42)))
    (LetPrim (v1 (Constant (Int 0)))
      (LetCont
          ((rec k0 (v2)
             (LetCont
                 ((k1 ()
                    (LetPrim (v3 (Constant (Null)))
                      (InvokeContinuation return (v3))))
                  (k2 ()
                    (LetCont
                        ((k3 (v4)
                           (LetCont
                               ((k4 (v5)
                                  (LetPrim (v6 (Constant (Int 1)))
                                    (LetCont
                                        ((k5 (v7)
                                           (InvokeContinuation rec k0 (v7))))
                                      (InvokeMethod v2 + (v6) k5)))))
                             (InvokeStatic print (v4) k4))))
                      (InvokeMethod v0 toString () k3))))
               (LetPrim (v8 (Constant (Int 2)))
                 (LetCont
                     ((k6 (v9)
                        (Branch (IsTrue v9) k2 k1)))
                   (InvokeMethod v2 < (v8) k6))))))
        (InvokeContinuation k0 (v1))))))
""";

// The 'inner loop' IR represents the following source code:
//
// void main() {
//   int j = 42;
//   for (int i = 0; i < 2; i++) {
//     for (int k = 0; k < 2; k++) {
//       print(i.toString());
//     }
//   }
//   print(j.toString());
// }
//
// This test case ensures that iterative optimization works: first, v8 and v9
// are removed from k5, and only then can k0 be optimized as well.

const String INNER_LOOP_IN = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 42)))
    (LetPrim (v1 (Constant (Int 0)))
      (LetCont
          ((rec k0 (v2 v3)
             (LetCont
                 ((k1 ()
                    (LetCont
                        ((k2 (v4)
                           (LetCont
                               ((k3 (v5)
                                  (LetPrim (v6 (Constant (Null)))
                                    (InvokeContinuation return (v6)))))
                             (InvokeStatic print (v4) k3))))
                      (InvokeMethod v2 toString () k2)))
                  (k4 ()
                    (LetPrim (v7 (Constant (Int 0)))
                      (LetCont
                          ((rec k5 (v8 v9 v10)
                             (LetCont
                                 ((k6 ()
                                    (LetPrim (v11 (Constant (Int 1)))
                                      (LetCont
                                          ((k7 (v12)
                                             (InvokeContinuation rec k0 (v8 v12))))
                                        (InvokeMethod v9 + (v11) k7))))
                                  (k8 ()
                                    (LetCont
                                        ((k9 (v13)
                                           (LetCont
                                               ((k10 (v14)
                                                  (LetPrim (v15 (Constant (Int 1)))
                                                    (LetCont
                                                        ((k11 (v16)
                                                           (InvokeContinuation rec k5 (v8 v9 v16))))
                                                      (InvokeMethod v10 + (v15) k11)))))
                                             (InvokeStatic print (v13) k10))))
                                      (InvokeMethod v9 toString () k9))))
                               (LetPrim (v17 (Constant (Int 2)))
                                 (LetCont
                                     ((k12 (v18)
                                        (Branch (IsTrue v18) k8 k6)))
                                   (InvokeMethod v10 < (v17) k12))))))
                        (InvokeContinuation k5 (v2 v3 v7))))))
               (LetPrim (v19 (Constant (Int 2)))
                 (LetCont
                     ((k13 (v20)
                        (Branch (IsTrue v20) k4 k1)))
                   (InvokeMethod v3 < (v19) k13))))))
        (InvokeContinuation k0 (v0 v1))))))
""";

const String INNER_LOOP_OUT = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 42)))
    (LetPrim (v1 (Constant (Int 0)))
      (LetCont
          ((rec k0 (v2)
             (LetCont
                 ((k1 ()
                    (LetCont
                        ((k2 (v3)
                           (LetCont
                               ((k3 (v4)
                                  (LetPrim (v5 (Constant (Null)))
                                    (InvokeContinuation return (v5)))))
                             (InvokeStatic print (v3) k3))))
                      (InvokeMethod v0 toString () k2)))
                  (k4 ()
                    (LetPrim (v6 (Constant (Int 0)))
                      (LetCont
                          ((rec k5 (v7)
                             (LetCont
                                 ((k6 ()
                                    (LetPrim (v8 (Constant (Int 1)))
                                      (LetCont
                                          ((k7 (v9)
                                             (InvokeContinuation rec k0 (v9))))
                                        (InvokeMethod v2 + (v8) k7))))
                                  (k8 ()
                                    (LetCont
                                        ((k9 (v10)
                                           (LetCont
                                               ((k10 (v11)
                                                  (LetPrim (v12 (Constant (Int 1)))
                                                    (LetCont
                                                        ((k11 (v13)
                                                           (InvokeContinuation rec k5 (v13))))
                                                      (InvokeMethod v7 + (v12) k11)))))
                                             (InvokeStatic print (v10) k10))))
                                      (InvokeMethod v2 toString () k9))))
                               (LetPrim (v14 (Constant (Int 2)))
                                 (LetCont
                                     ((k12 (v15)
                                        (Branch (IsTrue v15) k8 k6)))
                                   (InvokeMethod v7 < (v14) k12))))))
                        (InvokeContinuation k5 (v6))))))
               (LetPrim (v16 (Constant (Int 2)))
                 (LetCont
                     ((k13 (v17)
                        (Branch (IsTrue v17) k4 k1)))
                   (InvokeMethod v2 < (v16) k13))))))
        (InvokeContinuation k0 (v1))))))
""";

// There are no redundant phis in the 'basic loop' IR, and this test ensures
// simply that the optimization does not alter the IR. It represents the
// following program:
//
// void main() {
//   for (int i = 0; i < 2; i++) {
//     print(i.toString());
//   }
// }

String BASIC_LOOP_IN = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 0)))
    (LetCont
       ((rec k0 (v1)
          (LetCont
              ((k1 ()
                 (LetPrim (v2 (Constant (Null)))
                   (InvokeContinuation return (v2))))
               (k2 ()
                 (LetCont
                     ((k3 (v3)
                        (LetCont
                            ((k4 (v4)
                               (LetPrim (v5 (Constant (Int 1)))
                                 (LetCont
                                     ((k5 (v6)
                                        (InvokeContinuation rec k0 (v6))))
                                   (InvokeMethod v1 + (v5) k5)))))
                          (InvokeStatic print (v3) k4))))
                   (InvokeMethod v1 toString () k3))))
            (LetPrim (v7 (Constant (Int 2)))
              (LetCont
                  ((k6 (v8)
                     (Branch (IsTrue v8) k2 k1)))
                (InvokeMethod v1 < (v7) k6))))))
      (InvokeContinuation k0 (v0)))))
""";

String BASIC_LOOP_OUT = BASIC_LOOP_IN;

// Ensures that proper scoping is preserved, i.e. that the optimized
// continuation body does reference out of scope primitives.
// IR written by hand since this case is currently not being generated.

String SCOPING_IN = """
(FunctionDefinition main () return ()
  (LetCont
      ((k0 (v1)
         (InvokeStatic print (v1) return)))
    (LetPrim (v0 (Constant (Int 0)))
      (LetPrim (v2 (Constant (Null)))
        (InvokeContinuation k0 (v0))))))
""";

String SCOPING_OUT = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 0)))
    (LetCont
        ((k0 ()
           (InvokeStatic print (v0) return)))
      (LetPrim (v1 (Constant (Null)))
        (InvokeContinuation k0 ())))))
""";

// Ensures that continuations which are never invoked are not optimized.
// IR written by hand.

String NEVER_INVOKED_IN = """
(FunctionDefinition main () return ()
  (LetPrim (v0 (Constant (Int 0)))
    (LetCont
        ((k0 (v1)
           (InvokeStatic print (v1) return)))
      (InvokeContinuation return (v0)))))
""";

String NEVER_INVOKED_OUT = NEVER_INVOKED_IN;

/// 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 a redundant phi pass over it, and compares
/// the stringification of the result against the expected output.
void testRedundantPhi(String input, String expectedOutput) {
  final unstringifier = new SExpressionUnstringifier();
  final stringifier   = new SExpressionStringifier();
  final optimizer     = new RedundantPhiEliminator();

  FunctionDefinition f = unstringifier.unstringify(input);
  optimizer.rewrite(f);

  String expected = normalizeSExpr(expectedOutput);
  String actual   = normalizeSExpr(stringifier.visit(f));

  Expect.equals(expected, actual, "Actual:\n$actual");
}

void main() {
  testRedundantPhi(READ_IN_LOOP_IN, READ_IN_LOOP_OUT);
  testRedundantPhi(INNER_LOOP_IN, INNER_LOOP_OUT);
  testRedundantPhi(BASIC_LOOP_IN, BASIC_LOOP_OUT);
  testRedundantPhi(SCOPING_IN, SCOPING_OUT);
  testRedundantPhi(NEVER_INVOKED_IN, NEVER_INVOKED_OUT);
}