| // 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); |
| } |
