Re: [PATCH] Improve forward jump threading of switch statements (PR18046)

[Jeff Law]

On 07/28/2016 09:46 PM, Patrick Palka wrote:

This patch improves the forward jump threader's ability to thread
GIMPLE_SWITCHes by making the VRP simplification callback attempt to
determine which case label will be taken.

For example, if the index operand of a switch has a value range ~[5,6]
along some edge and the switch statement has no "case 5" or "case 6"
label then this patch recognizes such a scenario as an opportunity for
threading through the switch and to the switch's default bb.

This improvement is necessary for the code in comment #1 of PR18046 to
get threaded.  There we have (in the VRP2 dump):

    bar ()
    {
      int i.0_1;
      int i.0_2;
      int pretmp_8;
      int prephitmp_9;
      int i.0_10;

      <bb 2>:
      i.0_1 = i;
      switch (i.0_1) <default: <L12>, case 0: <L0>>

    <L12>:
      i.0_10 = ASSERT_EXPR <i.0_1, i.0_1 != 0>;
      goto <bb 4> (<L2>);  // <-- this can be threaded to <L6>

    <L0>:
      i.0_2 = ASSERT_EXPR <i.0_1, i.0_1 == 0>;
      foo ();
      pretmp_8 = i;

      # prephitmp_9 = PHI <i.0_10(7), pretmp_8(3)>
    <L2>:
      switch (prephitmp_9) <default: <L6>, case 0: <L4>>

    <L4>:
      foo ();

    <L6>:
      return;

    }

The FSM threader can't thread the default edge of the 1st switch through
to the default edge of the 2nd switch because i.0_1 doesn't have a known
constant value along that path -- it could have any non-zero value.  For
this scenario and others like it, it is necessary to consider value
ranges.

During bootstrap this simplification triggered about 1000 times in
total.  It's not an impressive amount but the simplification itself is
cheap.

Bootstrap + regtest in progress on x86_64-pc-linux-gnu.  Does this look
OK to commit if there are no new regressions?

gcc/ChangeLog:

        PR tree-optimization/18046
        * tree-ssa-threadedge.c: Include cfganal.h.
        (simplify_control_statement_condition): If simplifying a
        GIMPLE_SWITCH, replace the index operand of the GIMPLE_SWITCH
        with the dominating ASSERT_EXPR before handing it off to VRP.
        Mention that a CASE_LABEL_EXPR may be returned.
        (thread_around_empty_blocks): Adjust to handle
        simplify_control_statement_condition() returning a
        CASE_LABEL_EXPR.
        (thread_through_normal_block): Likewise.
        * tree-vrp.c (simplify_stmt_for_jump_threading): Simplify
        a switch statement by trying to determine which case label
        will be taken.

gcc/testsuite/ChangeLog:

        PR tree-optimization/18046
        * gcc.dg/tree-ssa/vrp105.c: New test.
        * gcc.dg/tree-ssa/vrp106.c: New test.

OK.

Thanks for your patience,
jeff