diff options
| author | Björn Gustavsson <[email protected]> | 2019-03-01 07:28:37 +0100 |
|---|---|---|
| committer | Björn Gustavsson <[email protected]> | 2019-03-01 12:55:31 +0100 |
| commit | 42603e488ba2d66857d3deff4c6ec4fa6befd833 (patch) | |
| tree | 868ec1d4742aa0a8c9c0549336e20bf7905ea36d /lib/compiler | |
| 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/compiler')
| -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). |