diff options
author | Björn Gustavsson <bjorn@erlang.org> | 2019-03-01 07:28:37 +0100 |
---|---|---|
committer | Björn Gustavsson <bjorn@erlang.org> | 2019-03-01 12:55:31 +0100 |
commit | 42603e488ba2d66857d3deff4c6ec4fa6befd833 (patch) | |
tree | 868ec1d4742aa0a8c9c0549336e20bf7905ea36d /lib | |
parent | 87b942b68f3e8821348da6c7c4f0d352b0d4d950 (diff) | |
download | otp-42603e488ba2d66857d3deff4c6ec4fa6befd833.tar.gz otp-42603e488ba2d66857d3deff4c6ec4fa6befd833.tar.bz2 otp-42603e488ba2d66857d3deff4c6ec4fa6befd833.zip |
Add a comment about the time complexity of beam_ssa_dead
Diffstat (limited to 'lib')
-rw-r--r-- | lib/compiler/src/beam_ssa_dead.erl | 10 |
1 files changed, 10 insertions, 0 deletions
diff --git a/lib/compiler/src/beam_ssa_dead.erl b/lib/compiler/src/beam_ssa_dead.erl index 088d90b405..bb43a550ae 100644 --- a/lib/compiler/src/beam_ssa_dead.erl +++ b/lib/compiler/src/beam_ssa_dead.erl @@ -88,6 +88,16 @@ shortcut_opt(#st{bs=Blocks}=St) -> %% opportunities for optimizations compared to post order. (Based on %% running scripts/diffable with both PO and RPO and looking at %% the diff.) + %% + %% Unfortunately, processing the blocks in reverse post order + %% potentially makes the time complexity quadratic or even cubic if + %% the ordset of unset variables grows large, instead of + %% linear for post order processing. We try to still get reasonable + %% compilation times by optimizations that will keep the constant + %% factor as low as possible, and we try to avoid the cubic time + %% complexity by trying to keep the set of unset variables as small + %% as possible. + Ls = beam_ssa:rpo(Blocks), shortcut_opt(Ls, #{}, St). |