aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2017-10-18 15:03:22 +0200
committerBjörn Gustavsson <[email protected]>2017-10-26 12:05:17 +0200
commit5f9777512b71e464188398e3e1ece231f7ec4d16 (patch)
tree482259112840f4d720ff6af9fd52a88f01d9b70d
parent56455ce5b80087cd661ac3343f96c5a3df2f9f9c (diff)
downloadotp-5f9777512b71e464188398e3e1ece231f7ec4d16.tar.gz
otp-5f9777512b71e464188398e3e1ece231f7ec4d16.tar.bz2
otp-5f9777512b71e464188398e3e1ece231f7ec4d16.zip
Add some internal documentation about cerl_clauses
I recently tried to add some additional optimizations for matching of maps, but found out that the inliner will need some updates to be able to handle those optimizations. Add lib/compiler/internal_doc/cerl-notes.md to document what I've learned.
-rw-r--r--lib/compiler/internal_doc/cerl-notes.md75
-rw-r--r--lib/compiler/src/cerl_clauses.erl2
2 files changed, 77 insertions, 0 deletions
diff --git a/lib/compiler/internal_doc/cerl-notes.md b/lib/compiler/internal_doc/cerl-notes.md
new file mode 100644
index 0000000000..705fe8f42d
--- /dev/null
+++ b/lib/compiler/internal_doc/cerl-notes.md
@@ -0,0 +1,75 @@
+Some notes on the cerl modules
+==============================
+
+Maps in cerl_clauses:match/3
+----------------------------
+
+Not much optimization is done for maps in `cerl_clauses:match/3`.
+
+The reason is that the inliner (`cerl_inline`) was not designed for
+data types that depend on variables bound in the enclosing environment
+(for example, the keys for maps). If we attempt to extend the
+optimizations for maps similar to the optimizations for the other data
+types, the inliner will crash for certain code. Here is an example of
+code that would crash the inliner:
+
+ t() ->
+ f(key).
+
+ f(K) ->
+ case #{K => value} of
+ #{key := V} -> V
+ end.
+
+The reason for the crash is that the inliner works in several
+passes and calls `cerl_clauses:match/3` twice. The inliner will
+assume that the same result will be returned both times, but
+for this example different bindings will be returned.
+
+Here is the rough outline of what happens:
+
+* The first time `cerl_clauses:match/3` will be asked to match the
+pattern `#{K := V}` against `#{key => value}`. It cannot say more
+than that the pattern *may* match.
+
+* Now the inliner will add the bindings to body of the clause (which
+is simply `V`). In this case, the bindings are still empty, so
+nothing is added.
+
+* The inliner will now do some substitutions and renaming. The
+variable `K` will be replaced with `key`.
+
+* The next time `cerl_clauses:match/3` is called, it will be asked to
+match the pattern `#{key := V}` against `#{key => value#}`. In this
+case, there will be a match and the bindings can be extended with
+`{V,value}`.
+
+* The inliner will see that the entire case can be removed. Only
+the body for the clause needs to be kept.
+
+Thus, after inlining the function `t/0` will look like this:
+
+ t() ->
+ V.
+
+The problem here is that the inliner assumed that the bindings from
+the first and second call to `cer_clauses:match/3` would be the same.
+It used the empty bindings from the first call for the body.
+
+The correct way would be to add the bindings from the second call:
+
+ t() ->
+ let V = value in V.
+
+### How to fix this ###
+
+The inliner will need to call `cerl_clauses:match/3` after doing
+all substitutions and renaming. It is not clear to me how difficult
+that would be. I assume that the inliner is written the way it is
+for a good reason. That means that switching the order things are
+done would lead to correctness and/or performance problems.
+
+### What must also be done to fix this ###
+
+`cerl_inline:make_template/3` must be extended to create a template
+for maps. That is relatively straightforward.
diff --git a/lib/compiler/src/cerl_clauses.erl b/lib/compiler/src/cerl_clauses.erl
index 7d6518c3c6..fa5104c01b 100644
--- a/lib/compiler/src/cerl_clauses.erl
+++ b/lib/compiler/src/cerl_clauses.erl
@@ -353,6 +353,8 @@ match(P, E, Bs) ->
map ->
%% The most we can do is to say "definitely no match" if a
%% map pattern is matched against non-map data.
+ %% (Note: See the document internal_doc/cerl-notes.md for
+ %% information why we don't try to do more here.)
case E of
any ->
{false, Bs};