Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

better propagation of boolean values through the program #48154

Closed
mraleph opened this issue Jan 17, 2022 · 1 comment
Closed

better propagation of boolean values through the program #48154

mraleph opened this issue Jan 17, 2022 · 1 comment
Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. type-performance Issue relates to performance or code size vm-aot-code-size Related to improvements in AOT code size vm-tfa

Comments

@mraleph
Copy link
Member

mraleph commented Jan 17, 2022

Right now we have some support for propagating constant boolean values through the program:

  • Simple unreachable code elimination is capable of folding some patterns (like false && ... into false)
  • TFA is capable of propagating boolean constants

However these passes have some unpredictable short comings and can surprise developers:

  • TFA does not attempt to evaluate logical expressions so in f() => true; g() => f(); h() => f() && g() g() will be inferred to return true but h() will not
  • Unreachable code elimination short-circuits false && ... => false but does not attempt to rewrite ... && false into let t = ... in false.

We should consider making these more predictable.

/cc @alexmarkov

@mraleph mraleph added the area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. label Jan 17, 2022
@alexmarkov
Copy link
Contributor

A few random thoughts:

  • We also do constant folding in TFA tree shaker (using the values propagated by TFA) and in the VM's local optimizations, so the 2nd pattern should be optimized anyway.
  • Adding constant folding of logical expressions to TFA will make TFA summaries larger, increasing memory usage and potentially slowing the analysis and compilation time. We need to have a serious reason to do so (such as a real-world case where this optimization would actually help).
  • Transformation foo && false into let t = foo in false is only valid with sound null safety (without sound null safety foo should be checked for null).

@mraleph Do you have a real-world example where the lack of the constant propagation / folding in these cases causes suboptimal code and affects performance or code size?

@alexmarkov alexmarkov added vm-tfa type-performance Issue relates to performance or code size vm-aot-code-size Related to improvements in AOT code size labels Jan 19, 2022
copybara-service bot pushed a commit that referenced this issue May 22, 2023
This change improves type flow analysis by adding conditional data
flow. Now each statement in the data flow summary can have an optional
condition. If a condition is present, then the statement is applied
only if its condition is not a 'false' constant. The condition may
become false as a result of whole-program type and constant
propagation (constant value is an optional property of a concrete
type).

Conditions in the data flow summary are populated from conditions in
the 'if' statements and conditional expressions. Conditions are
propagated down the control flow while building the summary.
For example:

  if (x) { return foo(); }
  bar();

Call 'foo()' is guarded by condition 'x' and 'bar()' is guarded by
condition '!x'.

Also, a bunch of unary and binary operations are added in order to
represent logical expressions, comparisons with null, 'is' tests and
conditional moves.

This change makes TFA much more sensitive to the control flow.

In order to offset increase in the compilation time due to the
additional condition and operations in the data flow summary,
the following is done:
* Types corresponding to bool constants are canonicalized; condition
  checking and logical operations are performed using fast identical
  checks.
* Fast identical checks are also added to union and intersection of
  types.
* Added more sophisticated simplifications of Join statements.

Along with reduced analysis due to skipped data flow statements with
false conditions, these improvements result in the slightly reduced
compilation time.

AOT compilation time on large Flutter apps (only AOT step 2 / TFA):
App 1: Before: 65.448s After: 62.893s (-3.9%)
App 2: Before: 55.067s After: 52.192s (-5.2%)

AOT snapshot size of large Flutter apps (Flutter release mode, arm64):
App 1: Before: 32910316 After: 32599936 (-0.9%)
App 2: Before: 34464544 After: 34092907 (-1.0%)
Flutter gallery: -1.9%

Performance on micro-benchmark from #51630 in AOT mode:
Before: 0.405839
After: 0.172886 (2.3x faster than before, still slower than JIT)

TEST=pkg/vm/testcases/transformations/type_flow/transformer/regress_47509.dart
TEST=pkg/vm/testcases/transformations/type_flow/transformer/regress_51630.dart

Issue: #51630
Fixes #48154
Fixes #47509

Change-Id: I29baf2933972adf83fd58be5ec25be8c30665c01
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/300700
Reviewed-by: Martin Kustermann <kustermann@google.com>
Reviewed-by: Ömer Ağacan <omersa@google.com>
Reviewed-by: Slava Egorov <vegorov@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. type-performance Issue relates to performance or code size vm-aot-code-size Related to improvements in AOT code size vm-tfa
Projects
None yet
Development

No branches or pull requests

2 participants