From 42603e488ba2d66857d3deff4c6ec4fa6befd833 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 1 Mar 2019 07:28:37 +0100 Subject: Add a comment about the time complexity of beam_ssa_dead --- lib/compiler/src/beam_ssa_dead.erl | 10 ++++++++++ 1 file changed, 10 insertions(+) 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). -- cgit v1.2.3