(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.
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).
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
