On Sun, Sep 1, 2024 at 5:20 PM Filip Kastl <fka...@suse.cz> wrote:
>
> (I'm Cc-ing Diego since he originally contributed the VRP pass and Jeff
> because
> I've seen him in git blame on many lines of vr-values.cc around the place I
> would like to make modifications)
>
> Hello,
>
> In this RFC I'd like to propose the following: When the value range statement
> simplification machinery encounters a switch with a default case that never
> executes, it should mark the default case with __builtin_unreachable instead
> of
> removing the default case. I think that should be the "canonical"
> representation of switches with this property.
>
> In terms of changes made to GCC code, this would be a small patch.
>
> I'd like to hear other people's opinions on this. Perhaps there are
> implications of this change or some other issues with the idea which I don't
> see.
>
>
> Initial example
> ===============
>
> Consider this C code
>
> switch (v & 3) {
> case 0: return 0;
> case 1: return 1;
> case 2: return 2;
> case 3: return 3;
> default: __builtin_unreachable();
> }
>
> Currently, when early vrp is processing this code
> (vr-values.cc:simplify_switch_using_ranges), it sees that the index expression
> can only have values [0,3]. Since the numbered cases cover this range
> entirely, vrp decides to transform the switch so that it only has these 4
> numbered cases and removes the default case. Because GIMPLE switches have to
> have a default, vrp converts case 0 to the default case. The switch then
> looks
> like this
>
> switch (v & 3) {
> default: return 0;
> case 1: return 1;
> case 2: return 2;
> case 3: return 3;
> }
>
> However, I think it would be better if the default case with
> __builtin_unreachable remained. I think it conveys more information to the
> passes running after vrp.
There isn't any extra info that's not also on the switch expression, no?
> What would this solve
> =====================
>
> Notice that the initial example switch doesn't do anything. It is just an
> identity mapping. The example is actually taken from PR112687. The PR shows
> that currently GCC (at least in some cases) fails to optimize similar identity
> switches. Currently the initial example looks like this at the end of the
> GIMPLE pipeline:
>
> int unopt (int v)
> {
> int _1;
> int _2;
> unsigned int _6;
> unsigned int _7;
>
> <bb 2>
> _1 = v_3(D) & 3;
> _6 = (unsigned int) _1;
> _7 = _6 + 4294967295;
> if (_7 <= 2)
> goto <bb 4>;
> else
> goto <bb 3>;
>
> <bb 3>
>
> <bb 4>
> # _2 = PHI <_1(2), 0(3)>
> return _2;
>
> }
>
> While it could look like this:
>
> int unopt (int v)
> {
> int _1;
>
> <bb 2>
> _1 = v_2(D) & 3;
> return _1;
>
> }
>
> Here is another example of similar code that currently doesn't get
> optimized...
>
> int unopt(int v)
> {
> switch (v & 3) {
> case 0: return 0;
> case 1: return 2;
> case 2: return 4;
> case 3: return 6;
> default: return -1;
> }
> }
>
> ...and could get optimized into something like this if VRP marked the default
> case as unreachable.
>
> int opt(int v)
> {
> return (v & 3) * 2;
> }
>
> I have originally thought about solving this problem in the switch conversion
> pass. However, I think that would require basically detecting that the "take
> away the default case" transformation happened and then reversing it. That
> seems pretty messy to me. Also, as I already mentioned, I think that the
> canonical representation of this kind of switches should be some
> representation
> that marks the default case as unreachable (with __builtin_unreachable or
> somehow else).
But can you not simply look at the switch expression range to derive the same
knowledge as with the unreachable in default?
The reason we always have a default is that it nicely fits with the
requirement of
expanding the switch as binary tree or as jump table. With default: being
unreachable but present the expansion code would need to go extra lengths
creating the same optimal code? So you'd trade simpler code in one place
for more complicated code in another?
Thanks,
Richard.
>
> How I'd do this
> ===============
>
> I'm attaching a work-in-progress patch to this RFC.
>
> I'm aware that in the final version it would be good to also modify the code
> surrounding the blob that I insert in the patch. For example,
> cleanup_edges_and_switches() contains code dealing with the situation when the
> default case gets removed, which is a situation that never happens with my
> patch applied.
>
> I'll appreciate comments on if I should place the blob of code creating the
> __builtin_unreachable somewhere else in the file. I'll also appreciate any
> other comments on the patch.
>
>
> Cheers,
> Filip Kastl
>
>
> P.S. While writing this I realized that in this case...
>
> int unopt(int v)
> {
> switch (v & 3) {
> default: return 0;
> case 1: return 1;
> case 2: return 2;
> case 3: return 3;
> }
> }
>
> ...GCC fails to optimize the switch even with my patch applied. This is
> because here VRP sees a default case that actually gets executed sometimes and
> leaves the default case be. We could make the following change to remedy
> this:
> Whenever VRP encounters a default that only corresponds to one possible value
> of the index expression of the switch, it could create a numbered case
> corresponding to this value and mark the default case as unreachable.
>
>
> -- 8< --
>
>
> diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
> index cf273a3fc62..b297e782b09 100644
> --- a/gcc/vr-values.cc
> +++ b/gcc/vr-values.cc
> @@ -1368,6 +1368,32 @@ simplify_using_ranges::simplify_switch_using_ranges
> (gswitch *stmt)
> else
> return false;
>
> + if (!take_default)
> + {
> + basic_block default_bb = gimple_switch_default_bb (cfun, stmt);
> + if (!gimple_seq_unreachable_p (bb_seq (default_bb)))
> + {
> + /* Add bb with __builtin_unreachable and make default point to
> + it. */
> + basic_block switch_bb = gimple_bb (stmt);
> + basic_block new_bb = create_empty_bb (switch_bb);
> + new_bb->loop_father = switch_bb->loop_father;
> + e = gimple_switch_default_edge (cfun, stmt);
> + redirect_edge_succ (e, new_bb);
> + gimple_stmt_iterator gsi = gsi_start_bb (new_bb);
> + gimple *stmt_unreachable =
> + gimple_build_builtin_unreachable (UNKNOWN_LOCATION);
> + gsi_insert_after (&gsi, stmt_unreachable, GSI_NEW_STMT);
> + tree label_unreachable = gimple_block_label (new_bb);
> + tree default_case_label = gimple_switch_default_label (stmt);
> + CASE_LABEL (default_case_label) = label_unreachable;
> + if (dom_info_available_p (CDI_DOMINATORS))
> + set_immediate_dominator (CDI_DOMINATORS, new_bb, switch_bb);
> +
> + }
> + take_default = true;
> + }
> +
> n = gimple_switch_num_labels (stmt);
>
> /* We can truncate the case label ranges that partially overlap with OP's
