setelement/3 causes unexpected mutation in nested tuples #9014

intarga · 2024-11-03T16:55:30Z

Describe the bug
As I understand from the documentation, setelement/3 can mutate tuples in place as an optimisation, but this optimisation should only be applied where it doesn't affect the behaviour of the function. I.e any mutation should never be visible to the user.

However, when using setelement/3 on a tuple inside another tuple, it always mutates the tuple, changing the behaviour of the program.

To Reproduce

-type state() :: {state, counter()}.
-type counter() :: {counter, integer()}.

-spec inc_counter(counter()) -> counter().
inc_counter(Counter) ->
    CounterValue = erlang:element(2, Counter),
    erlang:setelement(2, Counter, CounterValue + 1).

-spec wibble(state()) -> counter().
wibble(State) ->
    inc_counter(erlang:element(2, State)),
    inc_counter(erlang:element(2, State)),
    inc_counter(erlang:element(2, State)),
    inc_counter(erlang:element(2, State)),
    inc_counter(erlang:element(2, State)),

    Counter = erlang:element(2, State),
    CounterValue = erlang:element(2, Counter),
    case CounterValue >= 1 of
        true ->
            Counter;
        false ->
            NewCounter = inc_counter(Counter),
            NewState = erlang:setelement(2, State, NewCounter),
            wibble(NewState)
    end.

main() ->
    {counter, 5} = wibble({state, {counter, 0}}).

Expected behavior
This program should crash. The first 5 calls to inc_counter in wibble should do nothing, wibble should return {counter, 1} and main should crash.

Instead, the first 5 calls mutate the counter tuple in place, and wibble returns {counter, 5}

Affected versions
I've verified this with:

Erlang/OTP 27 from Homebrew on macOS 14.6.1, arm64

Someone else has corroborated it with:

Erlang 27.1.2, NixOS unstable, x86_64, built from nixpkgs:60d0038

The text was updated successfully, but these errors were encountered:

frej · 2024-11-04T09:30:17Z

This is definitely a bug. Running erlc with +no_ssa_opt_destructive_update for the affected module will allow you work around the bug until I have a fix available.

inoas · 2024-11-04T15:00:23Z

AFAIU elixir folks are also affected because they also wrap erlang:element and erlang:setelement:

https://github.com/elixir-lang/elixir/blob/v1.17.3/lib/elixir/lib/kernel.ex#L1886-L1903

frej · 2024-11-05T06:48:34Z

AFAIU elixir folks are also affected because they also wrap erlang:element

The error only occurs when CSE does not unify all extracts from one tuple and the lifetime of the variables containing the extracted elements are non-overlapping. In that case the alias analysis fails to detect aliasing and then the destructive update pass thinks it is safe to modify the tuple in-place.

@intarga

Correct an omission in the alias analysis which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would think that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times within a function and create a database which, given a variable, allows for looking up variables storing later extractions of the same element. The database is used during liveness calculations to artificially extend the liveness of the first extracted value to overlap with at least one of the later extractions to ensure that aliasing of tuple elements are not missed. Thanks to @intarga at Github for finding this bug. Closes erlang#9014

@intarga

Correct an omission in the alias analysis pass which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would decide that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times in a function. Normally the CSE pass ensures that this is only done once, but sometimes it decides that it is more efficient to keep the tuple around and extract the element again. This interacts badly with the alias analysis which takes care to minimize the database it keeps about aliasing status to variables that are live, and can therefore in rare cases fail to detect aliasing. Instead of complicating and slowing down the main alias analysis, we do a once over on all functions and detect when the same field is extracted twice and store the afflicted variables in a set. During the main alias analysis pass we consult the set and forcibly alias the variable when it is defined. Thanks to @intarga for finding this bug. Closes erlang#9014

@intarga

Correct an omission in the alias analysis pass which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would decide that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times in a function. Normally the CSE pass ensures that this is only done once, but sometimes it decides that it is more efficient to keep the tuple around and extract the element again. This interacts badly with the alias analysis which takes care to minimize the database it keeps about aliasing status to variables that are live, and can therefore in rare cases fail to detect aliasing. Instead of complicating and slowing down the main alias analysis, we do a once over on all functions and detect when the same field is extracted twice and store the afflicted variables in a set. During the main alias analysis pass we consult the set and forcibly alias the variable when it is defined. Thanks to @intarga for finding this bug. Closes erlang#9014

@intarga

Correct an omission in the alias analysis pass which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would decide that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times in a function. Normally the CSE pass ensures that this is only done once, but sometimes it decides that it is more efficient to keep the tuple around and extract the element again. This interacts badly with the alias analysis which takes care to minimize the database it keeps about aliasing status to variables that are live, and can therefore in rare cases fail to detect aliasing. Instead of complicating and slowing down the main alias analysis, we do a once over on all functions and detect when the same field is extracted twice and store the afflicted variables in a set. During the main alias analysis pass we consult the set and forcibly alias the variable when it is defined. Thanks to @intarga for finding this bug. Closes erlang#9014

@intarga

Correct an omission in the alias analysis pass which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would decide that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times in a function. Normally the CSE pass ensures that this is only done once, but sometimes it decides that it is more efficient to keep the tuple around and extract the element again. This interacts badly with the alias analysis which takes care to minimize the database it keeps about aliasing status to variables that are live, and can therefore in rare cases fail to detect aliasing. Instead of complicating and slowing down the main alias analysis, we do a once over on all functions and detect when the same field is extracted twice and store the afflicted variables in a set. During the main alias analysis pass we consult the set and forcibly alias the variable when it is defined. Thanks to @intarga for finding this bug. Closes erlang#9014

frej · 2024-11-06T09:21:39Z

#9024 contains a fix for this problem.

@intarga

Correct an omission in the alias analysis pass which could make it fail to detect aliasing of a tuple element if the same element was extracted more than once in a function. If we had code looking like this: function `bad`:`foo`(_0) { 0: _1 = get_tuple_element _0, `1` _2 = call (`bar`/1), _1 ... 1: _3 = get_tuple_element _0, `1` The alias analysis would decide that _1 died with the call to bar/1 and thus prune _1 from the sharing state database when leaving block 0 and thus fail to detect the aliasing of element 1 in _0. This in turn could allow bar/1 to destructively update elements of its argument, which is not safe. This omission is corrected by detecting when the same element is extracted from a tuple multiple times in a function. Normally the CSE pass ensures that this is only done once, but sometimes it decides that it is more efficient to keep the tuple around and extract the element again. This interacts badly with the alias analysis which takes care to minimize the database it keeps about aliasing status to variables that are live, and can therefore in rare cases fail to detect aliasing. Instead of complicating and slowing down the main alias analysis, we do a once over on all functions and detect when the same field is extracted twice and store the afflicted variables in a set. During the main alias analysis pass we consult the set and forcibly alias the variable when it is defined. Thanks to @intarga for finding this bug. Closes erlang#9014

intarga added the bug Issue is reported as a bug label Nov 3, 2024

intarga mentioned this issue Nov 3, 2024

Unexpected mutation from record update on a subrecord gleam-lang/gleam#3781

Closed

bjorng added the team:VM Assigned to OTP team VM label Nov 4, 2024

frej mentioned this issue Nov 6, 2024

compiler alias analysis: Correctly handle repeated tuple extractions #9024

Merged

garazdawi assigned frej Nov 11, 2024

bjorng closed this as completed in cd87fed Nov 11, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

setelement/3 causes unexpected mutation in nested tuples #9014

setelement/3 causes unexpected mutation in nested tuples #9014

intarga commented Nov 3, 2024

frej commented Nov 4, 2024

inoas commented Nov 4, 2024

frej commented Nov 5, 2024

frej commented Nov 6, 2024

setelement/3 causes unexpected mutation in nested tuples #9014

setelement/3 causes unexpected mutation in nested tuples #9014

Comments

intarga commented Nov 3, 2024

frej commented Nov 4, 2024

inoas commented Nov 4, 2024

frej commented Nov 5, 2024

frej commented Nov 6, 2024