[Bug tree-optimization/94779] Bad optimization of simple switch

["marxin at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94779

--- Comment #14 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #12)
> So, for start I think we should do:
> 1) query->range_of_expr (m_index_range, m_index_expr, swtch)
>    where query is address of gimple_ranger passed down from the caller
>    to figure out range of the index expression; case labels without
> CASE_HIGH for
>    which m_index_range.contains_p (CASE_LOW (case)) is false can be ignored
>    for the optimization (well, handled the way it is better for the
> optimization)
>    For CASE_HIGH labels, similarly query if the range overlaps the index
> range.
>    Note, I don't remember exactly in which way the types of the index
> expression
>    and of the case labels can differ, I believe all case labels have to have
> the
>    same type, so probably for the computation of the range if it has
> different
>    type from the case label ones, it needs to call something that would
> emulate
>    the effect of conversion to that type (or vice versa?)
>    CCing Andrew for the range stuff

Ok, I've just taken look at what EVRP pass does before SWITCHCONV pass is
called.
I see that EVRP can properly prune dead cases of a switch, but it's not
perfect:

int f1(unsigned x)
{
    if (x == 2 || x == 3 || x >= 5)
      __builtin_unreachable ();
    switch (x)
    {
      case 0: return 1;
      case 1: return 2;
      case 2: return 3;
      case 3 ... 8: return 4;
    }
}

after VRP we end up with:
  switch (x_6(D)) <default: <L8> [INV], case 1: <L3> [INV], case 2: <L4> [INV],
case 3 ... 4: <L5> [INV]>

but case '3' is not pruned here. Similarly, I can imagine the following
reduction:

    if (x >= 4 && x <= 9)
      __builtin_unreachable ();
    switch (x)
    {
      case 0: return 1;
      case 1: return 2;
      case 2: return 3;
      case 3 ... 10: return 4;
    }

is not simplified to:
  switch (x_3(D)) <default: <L6> [INV], case 0: <L8> [INV], case 1: <L3> [INV],
case 2: <L4> [INV], case 3 ... 10: <L5> [INV]>

but I would expect:
  switch (x_3(D)) <default: <L6> [INV], case 0: <L8> [INV], case 1: <L3> [INV],
case 2: <L4> [INV], case 3: <L5>, case 10: <L5> [INV]>

Btw, EVRP knows the information:
4->8      x_3(D) :      unsigned int [11, +INF]
4->9      x_3(D) :      unsigned int [0, 0]
4->5      x_3(D) :      unsigned int [1, 1]
4->6      x_3(D) :      unsigned int [2, 2]
4->7      x_3(D) :      unsigned int [3, 3][10, 10]

The question is whether we want to make the transformation by EVRP?

> 2) similarly, cases that refer to blocks which have EDGE_COUNT (bb->succs)
> == 0
>    && gimple_seq_unreachable_p (bb_seq (bb)) should be treated again like
> cases
>    one shouldn't need to care about

I've got a patch candidate for this.

> 3) to handle the #c0 testcase in C (C++ already adds __builtin_unreachable),
>    handle also the case where case refers to block which has EDGE_COUNT
> (bb->succs) and ends in GIMPLE_RETURN without expression in a function that
>    returns integral or pointer value (for simplicity) and has no statements
>    other than debug stmts or clobber stmts before it.  Note, this case can't
> be
>    treated completely like a UB case, there is no UB in C unless the caller
>    checks the return value, but it could be handled conditionally, as long as
>    the code we emit for that doesn't invoke UB in the function, we really
> don't 
>    care about the value we return to the caller.  So e.g. if we are
> considering
>    a linear function and other case labels return that linear value and some
>    return unspecified value, just use the linear function to cover those too.

Likewise here, it's smart to return a random value for C when there's a missing
return value.

> 4) to be able to optimize the int f1(unsigned x) { if (x >= 3)
> __builtin_unreachable();
>    switch (x) { case 0: return 1; case 1: return 2; case 2: return 3; } }
>    testcase, we should for consideration virtually undo the evrp optimization
>    which removed the case 0: and replaced it with default: - here the handled
>    cases (that should include the really handled ones and ones that and the
>    UB ones (if the case is outside of range or __builtin_unreachable) cover
>    everything but one case, assume the default label is that for that single
>    case rather than handling anything else; similarly, if the whole range
>    is covered, ignore the default label

This seems to me like a strange EVRP transformation :/