| // 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 'dart:async'; |
| import '../mock_compiler.dart'; |
| import 'sexpr_unstringifier.dart'; |
| import 'package:async_helper/async_helper.dart'; |
| import "package:expect/expect.dart"; |
| import 'package:compiler/src/cps_ir/cps_ir_nodes_sexpr.dart'; |
| import 'package:compiler/src/cps_ir/optimizers.dart'; |
| import 'package:compiler/src/dart2jslib.dart' as dart2js; |
| |
| // The tests in this file that ensure that sparse constant propagation on the |
| // CPS IR works as expected. |
| |
| // CP1 represents the following incoming dart code: |
| // |
| // int main() { |
| // int i = 1; |
| // int j; |
| // if (i == 1) { |
| // j = 2; |
| // } else { |
| // j = 3; |
| // } |
| // return j; |
| // } |
| |
| String CP1_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 1))) |
| (LetCont |
| ((k0 (v2) |
| (LetCont |
| ((k1 () |
| (LetPrim (v3 (Constant (Int 2))) |
| (InvokeContinuation return (v3)))) |
| (k2 () |
| (LetPrim (v4 (Constant (Int 3))) |
| (InvokeContinuation return (v4))))) |
| (Branch (IsTrue v2) k1 k2)))) |
| (InvokeMethod v0 == (v1) k0))))) |
| """; |
| String CP1_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 1))) |
| (LetCont |
| ((k0 (v2) |
| (LetCont |
| ((k1 () |
| (LetPrim (v3 (Constant (Int 2))) |
| (InvokeContinuation return (v3)))) |
| (k2 () |
| (LetPrim (v4 (Constant (Int 3))) |
| (InvokeContinuation return (v4))))) |
| (InvokeContinuation k1 ())))) |
| (LetPrim (v5 (Constant (Bool true))) |
| (InvokeContinuation k0 (v5))))))) |
| """; |
| |
| // CP2 represents the following incoming dart code: |
| // |
| // int main() { |
| // int i = 1; |
| // while (true) { |
| // if (false || false) { |
| // return i; |
| // } |
| // if (true && i == 1) { |
| // return i; |
| // } |
| // } |
| // return 42; |
| // } |
| |
| String CP2_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetCont |
| ((rec k0 () |
| (LetCont |
| ((k1 () |
| (LetPrim (v1 (Constant (Int 42))) |
| (InvokeContinuation return (v1)))) |
| (k2 () |
| (LetPrim (v2 (Constant (Bool false))) |
| (LetCont |
| ((k3 (v3) |
| (LetCont |
| ((k4 () |
| (InvokeContinuation return (v0))) |
| (k5 () |
| (LetPrim (v4 (Constant (Bool true))) |
| (LetCont |
| ((k6 (v5) |
| (LetCont |
| ((k7 () |
| (InvokeContinuation return (v0))) |
| (k8 () |
| (InvokeContinuation rec k0 ()))) |
| (Branch (IsTrue v5) k7 k8)))) |
| (LetCont |
| ((k9 () |
| (LetPrim (v6 (Constant (Int 1))) |
| (LetCont |
| ((k10 (v7) |
| (LetCont |
| ((k11 () |
| (LetPrim (v8 (Constant (Bool true))) |
| (InvokeContinuation k6 (v8)))) |
| (k12 () |
| (LetPrim (v9 (Constant (Bool false))) |
| (InvokeContinuation k6 (v9))))) |
| (Branch (IsTrue v7) k11 k12)))) |
| (InvokeMethod v0 == (v6) k10)))) |
| (k13 () |
| (LetPrim (v10 (Constant (Bool false))) |
| (InvokeContinuation k6 (v10))))) |
| (Branch (IsTrue v4) k9 k13)))))) |
| (Branch (IsTrue v3) k4 k5)))) |
| (LetCont |
| ((k14 () |
| (LetPrim (v11 (Constant (Bool true))) |
| (InvokeContinuation k3 (v11)))) |
| (k15 () |
| (LetPrim (v12 (Constant (Bool false))) |
| (LetCont |
| ((k16 () |
| (LetPrim (v13 (Constant (Bool true))) |
| (InvokeContinuation k3 (v13)))) |
| (k17 () |
| (LetPrim (v14 (Constant (Bool false))) |
| (InvokeContinuation k3 (v14))))) |
| (Branch (IsTrue v12) k16 k17))))) |
| (Branch (IsTrue v2) k14 k15)))))) |
| (LetPrim (v15 (Constant (Bool true))) |
| (Branch (IsTrue v15) k2 k1))))) |
| (InvokeContinuation k0 ())))) |
| """; |
| String CP2_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetCont |
| ((rec k0 () |
| (LetCont |
| ((k1 () |
| (LetPrim (v1 (Constant (Int 42))) |
| (InvokeContinuation return (v1)))) |
| (k2 () |
| (LetPrim (v2 (Constant (Bool false))) |
| (LetCont |
| ((k3 (v3) |
| (LetCont |
| ((k4 () |
| (InvokeContinuation return (v0))) |
| (k5 () |
| (LetPrim (v4 (Constant (Bool true))) |
| (LetCont |
| ((k6 (v5) |
| (LetCont |
| ((k7 () |
| (InvokeContinuation return (v0))) |
| (k8 () |
| (InvokeContinuation rec k0 ()))) |
| (InvokeContinuation k7 ())))) |
| (LetCont |
| ((k9 () |
| (LetPrim (v6 (Constant (Int 1))) |
| (LetCont |
| ((k10 (v7) |
| (LetCont |
| ((k11 () |
| (LetPrim (v8 (Constant (Bool true))) |
| (InvokeContinuation k6 (v8)))) |
| (k12 () |
| (LetPrim (v9 (Constant (Bool false))) |
| (InvokeContinuation k6 (v9))))) |
| (InvokeContinuation k11 ())))) |
| (LetPrim (v10 (Constant (Bool true))) |
| (InvokeContinuation k10 (v10)))))) |
| (k13 () |
| (LetPrim (v11 (Constant (Bool false))) |
| (InvokeContinuation k6 (v11))))) |
| (InvokeContinuation k9 ())))))) |
| (InvokeContinuation k5 ())))) |
| (LetCont |
| ((k14 () |
| (LetPrim (v12 (Constant (Bool true))) |
| (InvokeContinuation k3 (v12)))) |
| (k15 () |
| (LetPrim (v13 (Constant (Bool false))) |
| (LetCont |
| ((k16 () |
| (LetPrim (v14 (Constant (Bool true))) |
| (InvokeContinuation k3 (v14)))) |
| (k17 () |
| (LetPrim (v15 (Constant (Bool false))) |
| (InvokeContinuation k3 (v15))))) |
| (InvokeContinuation k17 ()))))) |
| (InvokeContinuation k15 ())))))) |
| (LetPrim (v16 (Constant (Bool true))) |
| (InvokeContinuation k2 ()))))) |
| (InvokeContinuation k0 ())))) |
| """; |
| |
| // CP3 represents the following incoming dart code: |
| // |
| // int main() { |
| // int i = 1; |
| // i = f(); |
| // if (i == 1) { |
| // return 42; |
| // } |
| // return i; |
| // } |
| |
| String CP3_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetCont |
| ((k0 (v1) |
| (LetPrim (v2 (Constant (Int 1))) |
| (LetCont |
| ((k1 (v3) |
| (LetCont |
| ((k2 () |
| (LetPrim (v4 (Constant (Int 42))) |
| (InvokeContinuation return (v4)))) |
| (k3 () |
| (InvokeContinuation return (v1)))) |
| (Branch (IsTrue v3) k2 k3)))) |
| (InvokeMethod v1 == (v2) k1))))) |
| (InvokeStatic f () k0)))) |
| """; |
| String CP3_OUT = CP3_IN; |
| |
| // Addition. |
| |
| String CP4_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 2))) |
| (LetCont |
| ((k0 (v2) |
| (InvokeContinuation return (v2)))) |
| (InvokeMethod v0 + (v1) k0))))) |
| """; |
| String CP4_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 2))) |
| (LetCont |
| ((k0 (v2) |
| (InvokeContinuation return (v2)))) |
| (LetPrim (v3 (Constant (Int 3))) |
| (InvokeContinuation k0 (v3))))))) |
| """; |
| |
| // Array access operator (no optimization). |
| |
| String CP5_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 2))) |
| (LetCont |
| ((k0 (v2) |
| (InvokeContinuation return (v2)))) |
| (InvokeMethod v0 [] (v1) k0))))) |
| """; |
| String CP5_OUT = CP5_IN; |
| |
| // Division by 0. |
| |
| String CP6_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 0))) |
| (LetCont |
| ((k0 (v2) |
| (InvokeContinuation return (v2)))) |
| (InvokeMethod v0 / (v1) k0))))) |
| """; |
| String CP6_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 0))) |
| (LetCont |
| ((k0 (v2) |
| (InvokeContinuation return (v2)))) |
| (LetPrim (v3 (Constant (Double Infinity))) |
| (InvokeContinuation k0 (v3))))))) |
| """; |
| |
| // Concatenate strings. |
| |
| String CP7_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (String "b"))) |
| (LetPrim (v1 (Constant (String "d"))) |
| (LetPrim (v2 (Constant (String "a"))) |
| (LetPrim (v3 (Constant (String "c"))) |
| (LetPrim (v4 (Constant (String ""))) |
| (LetCont |
| ((k0 (v5) |
| (LetCont |
| ((k1 (v6) |
| (InvokeContinuation return (v6)))) |
| (InvokeMethod v5 length () k1)))) |
| (ConcatenateStrings (v2 v0 v3 v1 v4) k0)))))))) |
| """; |
| String CP7_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (String "b"))) |
| (LetPrim (v1 (Constant (String "d"))) |
| (LetPrim (v2 (Constant (String "a"))) |
| (LetPrim (v3 (Constant (String "c"))) |
| (LetPrim (v4 (Constant (String ""))) |
| (LetCont |
| ((k0 (v5) |
| (LetCont |
| ((k1 (v6) |
| (InvokeContinuation return (v6)))) |
| (InvokeMethod v5 length () k1)))) |
| (LetPrim (v7 (Constant (String "abcd"))) |
| (InvokeContinuation k0 (v7)))))))))) |
| """; |
| |
| // TODO(jgruber): We can't test is-check optimization because the unstringifier |
| // does not recreate accurate types for the TypeOperator node. |
| |
| // Simple branch removal. |
| |
| String CP8_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 1))) |
| (LetCont |
| ((k0 (v2) |
| (LetCont |
| ((k1 () |
| (LetPrim (v3 (Constant (Int 42))) |
| (InvokeContinuation return (v3)))) |
| (k2 () |
| (InvokeContinuation return (v0)))) |
| (Branch (IsTrue v2) k1 k2)))) |
| (InvokeMethod v0 == (v1) k0))))) |
| """; |
| String CP8_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetPrim (v1 (Constant (Int 1))) |
| (LetCont |
| ((k0 (v2) |
| (LetCont |
| ((k1 () |
| (LetPrim (v3 (Constant (Int 42))) |
| (InvokeContinuation return (v3)))) |
| (k2 () |
| (InvokeContinuation return (v0)))) |
| (InvokeContinuation k1 ())))) |
| (LetPrim (v4 (Constant (Bool true))) |
| (InvokeContinuation k0 (v4))))))) |
| """; |
| |
| // While loop. |
| |
| String CP9_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetCont |
| ((rec k0 (v1) |
| (LetCont |
| ((k1 () |
| (InvokeContinuation return (v1))) |
| (k2 () |
| (LetPrim (v2 (Constant (Int 1))) |
| (LetCont |
| ((k3 (v3) |
| (LetCont |
| ((k4 (v4) |
| (LetCont |
| ((k5 () |
| (LetPrim (v5 (Constant (Int 42))) |
| (InvokeContinuation return (v5)))) |
| (k6 () |
| (LetPrim (v6 (Constant (Int 1))) |
| (LetCont |
| ((k7 (v7) |
| (InvokeContinuation rec k0 (v7)))) |
| (InvokeMethod v1 + (v6) k7))))) |
| (Branch (IsTrue v4) k5 k6)))) |
| (LetCont |
| ((k8 () |
| (LetPrim (v8 (Constant (Bool false))) |
| (InvokeContinuation k4 (v8)))) |
| (k9 () |
| (LetPrim (v9 (Constant (Bool true))) |
| (InvokeContinuation k4 (v9))))) |
| (Branch (IsTrue v3) k8 k9))))) |
| (InvokeMethod v1 == (v2) k3))))) |
| (LetPrim (v10 (Constant (Bool true))) |
| (Branch (IsTrue v10) k2 k1))))) |
| (InvokeContinuation k0 (v0))))) |
| """; |
| String CP9_OUT = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 1))) |
| (LetCont |
| ((rec k0 (v1) |
| (LetCont |
| ((k1 () |
| (InvokeContinuation return (v1))) |
| (k2 () |
| (LetPrim (v2 (Constant (Int 1))) |
| (LetCont |
| ((k3 (v3) |
| (LetCont |
| ((k4 (v4) |
| (LetCont |
| ((k5 () |
| (LetPrim (v5 (Constant (Int 42))) |
| (InvokeContinuation return (v5)))) |
| (k6 () |
| (LetPrim (v6 (Constant (Int 1))) |
| (LetCont |
| ((k7 (v7) |
| (InvokeContinuation rec k0 (v7)))) |
| (InvokeMethod v1 + (v6) k7))))) |
| (Branch (IsTrue v4) k5 k6)))) |
| (LetCont |
| ((k8 () |
| (LetPrim (v8 (Constant (Bool false))) |
| (InvokeContinuation k4 (v8)))) |
| (k9 () |
| (LetPrim (v9 (Constant (Bool true))) |
| (InvokeContinuation k4 (v9))))) |
| (Branch (IsTrue v3) k8 k9))))) |
| (InvokeMethod v1 == (v2) k3))))) |
| (LetPrim (v10 (Constant (Bool true))) |
| (InvokeContinuation k2 ()))))) |
| (InvokeContinuation k0 (v0))))) |
| """; |
| |
| // While loop, from: |
| // |
| // int main() { |
| // for (int i = 0; i < 2; i++) { |
| // print(42 + i); |
| // } |
| // } |
| |
| String CP10_IN = """ |
| (FunctionDefinition main () () return |
| (LetPrim (v0 (Constant (Int 0))) |
| (LetCont |
| ((rec k0 (v1) |
| (LetCont |
| ((k1 () |
| (LetPrim (v2 (Constant (Null))) |
| (InvokeContinuation return (v2)))) |
| (k2 () |
| (LetPrim (v3 (Constant (Int 42))) |
| (LetCont |
| ((k3 (v4) |
| (LetCont |
| ((k4 (v5) |
| (LetPrim (v6 (Constant (Int 1))) |
| (LetCont |
| ((k5 (v7) |
| (InvokeContinuation rec k0 (v7)))) |
| (InvokeMethod v1 + (v6) k5))))) |
| (InvokeStatic print (v4) k4)))) |
| (InvokeMethod v3 + (v1) k3))))) |
| (LetPrim (v8 (Constant (Int 2))) |
| (LetCont |
| ((k6 (v9) |
| (Branch (IsTrue v9) k2 k1))) |
| (InvokeMethod v1 < (v8) k6)))))) |
| (InvokeContinuation k0 (v0))))) |
| """; |
| String CP10_OUT = CP10_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 an optimization pass over it, and compares |
| /// the stringification of the result against the expected output. |
| Future testConstantPropagator(String input, String expectedOutput) { |
| final compiler = new MockCompiler.internal( |
| emitJavaScript: false, |
| enableMinification: false); |
| return compiler.init().then((_) { |
| final unstringifier = new SExpressionUnstringifier(); |
| final stringifier = new SExpressionStringifier(); |
| final optimizer = new TypePropagator( |
| compiler.types, |
| dart2js.DART_CONSTANT_SYSTEM, |
| new UnitTypeSystem(), |
| compiler.internalError); |
| |
| final f = unstringifier.unstringify(input); |
| optimizer.rewrite(f); |
| |
| String expected = normalizeSExpr(expectedOutput); |
| String actual = normalizeSExpr(stringifier.visit(f)); |
| |
| Expect.equals(expected, actual); |
| }); |
| } |
| |
| void main() { |
| asyncTest(() => testConstantPropagator(CP1_IN, CP1_OUT)); |
| asyncTest(() => testConstantPropagator(CP2_IN, CP2_OUT)); |
| asyncTest(() => testConstantPropagator(CP3_IN, CP3_OUT)); |
| asyncTest(() => testConstantPropagator(CP4_IN, CP4_OUT)); |
| asyncTest(() => testConstantPropagator(CP5_IN, CP5_OUT)); |
| asyncTest(() => testConstantPropagator(CP6_IN, CP6_OUT)); |
| asyncTest(() => testConstantPropagator(CP7_IN, CP7_OUT)); |
| asyncTest(() => testConstantPropagator(CP8_IN, CP8_OUT)); |
| asyncTest(() => testConstantPropagator(CP9_IN, CP9_OUT)); |
| asyncTest(() => testConstantPropagator(CP10_IN, CP10_OUT)); |
| } |
