On Thu, Jul 28, 2016 at 11:46 PM, Patrick Palka <patr...@parcs.ath.cx> 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.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/vrp105.c | 37 +++++++++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/vrp106.c | 27 +++++++++++++++
> gcc/tree-ssa-threadedge.c | 40 ++++++++++++++++++----
> gcc/tree-vrp.c | 61
> ++++++++++++++++++++++++++++++++++
> 4 files changed, 159 insertions(+), 6 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> new file mode 100644
> index 0000000..7cdd4dd
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> @@ -0,0 +1,37 @@
> +/* PR tree-optimization/18046 */
> +/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
> +/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp2" } } */
> +/* In the 2nd VRP pass (after PRE) we expect to thread the default label of
> the
> + 1st switch straight to that of the 2nd switch. */
> +
> +extern void foo (void);
> +extern void bar (void);
> +
> +extern int i;
> +void
> +test (void)
> +{
> + switch (i)
> + {
> + case 0:
> + foo ();
> + break;
> + case 1:
> + bar ();
> + break;
> + default:
> + break;
> + }
> +
> + switch (i)
> + {
> + case 0:
> + foo ();
> + break;
> + case 1:
> + bar ();
> + break;
> + default:
> + break;
> + }
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
> new file mode 100644
> index 0000000..e2e48d8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
> @@ -0,0 +1,27 @@
> +/* PR tree-optimization/18046 */
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
> +/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp1" } } */
> +/* During VRP we expect to thread the true arm of the conditional through
> the switch
> + and to the BB that corresponds to the 7 ... 9 case label. */
> +extern void foo (void);
> +extern void bar (void);
> +extern void baz (void);
> +
> +void
> +test (int i)
> +{
> + if (i >= 7 && i <= 8)
> + foo ();
> +
> + switch (i)
> + {
> + case 1:
> + bar ();
> + break;
> + case 7:
> + case 8:
> + case 9:
> + baz ();
> + break;
> + }
> +}
> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index de671b9..170e456 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa-threadedge.h"
> #include "tree-ssa-dom.h"
> #include "gimple-fold.h"
> +#include "cfganal.h"
>
> /* To avoid code explosion due to jump threading, we limit the
> number of statements we are going to copy. This variable
> @@ -390,7 +391,8 @@ static tree simplify_control_stmt_condition_1 (edge,
> gimple *,
> a condition using pass specific information.
>
> Return the simplified condition or NULL if simplification could
> - not be performed.
> + not be performed. When simplifying a GIMPLE_SWITCH, we may return
> + the CASE_LABEL_EXPR that will be taken.
>
> The available expression table is referenced via AVAIL_EXPRS_STACK. */
>
> @@ -513,7 +515,21 @@ simplify_control_stmt_condition (edge e,
> /* If we haven't simplified to an invariant yet, then use the
> pass specific callback to try and simplify it further. */
> if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
> - cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
> + {
> + if (handle_dominating_asserts && code == GIMPLE_SWITCH)
> + {
> + /* Replace the index operand of the GIMPLE_SWITCH with the
> + dominating ASSERT_EXPR before handing it off to VRP. If
> + simplification is possible, the simplified value will be a
> + CASE_LABEL_EXPR of the label that is proven to be taken. */
> + gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
> + gimple_switch_set_index (dummy_switch, cached_lhs);
> + cached_lhs = (*simplify) (dummy_switch, stmt,
> avail_exprs_stack);
> + ggc_free (dummy_switch);
> + }
> + else
> + cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
> + }
>
> /* We couldn't find an invariant. But, callers of this
> function may be able to do something useful with the
> @@ -938,9 +954,14 @@ thread_around_empty_blocks (edge taken_edge,
> /* If the condition can be statically computed and we have not already
> visited the destination edge, then add the taken edge to our thread
> path. */
> - if (cond && is_gimple_min_invariant (cond))
> + if (cond != NULL_TREE
> + && (is_gimple_min_invariant (cond)
> + || TREE_CODE (cond) == CASE_LABEL_EXPR))
> {
> - taken_edge = find_taken_edge (bb, cond);
> + if (TREE_CODE (cond) == CASE_LABEL_EXPR)
> + taken_edge = find_edge (bb, label_to_block (CASE_LABEL (cond)));
> + else
> + taken_edge = find_taken_edge (bb, cond);
>
> if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
> return false;
> @@ -1069,9 +1090,16 @@ thread_through_normal_block (edge e,
> if (!cond)
> return 0;
>
> - if (is_gimple_min_invariant (cond))
> + if (is_gimple_min_invariant (cond)
> + || TREE_CODE (cond) == CASE_LABEL_EXPR)
> {
> - edge taken_edge = find_taken_edge (e->dest, cond);
> + edge taken_edge;
> + if (TREE_CODE (cond) == CASE_LABEL_EXPR)
> + taken_edge = find_edge (e->dest,
> + label_to_block (CASE_LABEL (cond)));
> + else
> + taken_edge = find_taken_edge (e->dest, cond);
> +
> basic_block dest = (taken_edge ? taken_edge->dest : NULL);
>
> /* DEST could be NULL for a computed jump to an absolute
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 41c870f..cb316b0 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -10092,6 +10092,67 @@ simplify_stmt_for_jump_threading (gimple *stmt,
> gimple *within_stmt,
> gimple_cond_rhs (cond_stmt),
> within_stmt);
>
> + /* We simplify a switch statement by trying to determine which case label
> + will be taken. If we are successful then we return the corresponding
> + CASE_LABEL_EXPR. */
> + if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
> + {
> + tree op = gimple_switch_index (switch_stmt);
> + if (TREE_CODE (op) != SSA_NAME)
> + return NULL_TREE;
> +
> + value_range *vr = get_value_range (op);
> + if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
> + || symbolic_range_p (vr))
> + return NULL_TREE;
> +
> + if (vr->type == VR_RANGE)
> + {
> + size_t i, j;
> + /* Get the range of labels that contain a part of the operand's
> + value range. */
> + find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
> +
> + /* Is there only one such label? */
> + if (i == j)
> + {
> + tree label = gimple_switch_label (switch_stmt, i);
> +
> + /* The i'th label will be taken only if the value range of the
> + operand is entirely within the bounds of this label. */
> + if (CASE_HIGH (label) != NULL_TREE
> + ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
> + && tree_int_cst_compare (CASE_HIGH (label), vr->max) >=
> 0)
> + : (tree_int_cst_equal (CASE_LOW (label), vr->min)
> + && tree_int_cst_equal (vr->min, vr->max)))
> + return label;
> + }
> +
> + /* If there are no such labels then the default label will be
> + taken. */
> + if (i > j)
> + return gimple_switch_label (switch_stmt, 0);
> + }
> +
> + if (vr->type == VR_ANTI_RANGE)
> + {
> + unsigned n = gimple_switch_num_labels (switch_stmt);
> + tree min_label = gimple_switch_label (switch_stmt, 1);
> + tree max_label = gimple_switch_label (switch_stmt, n - 1);
> +
> + /* The default label will be taken only if the anti-range of the
> + operand is entirely outside the bounds of all the (non-default)
> + case labels. */
> + if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
> + && (CASE_HIGH (max_label) != NULL_TREE
> + ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
> + : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >=
> 0))
> + return gimple_switch_label (switch_stmt, 0);
> + }
> +
> + return NULL_TREE;
> + }
> +
> if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
> {
> value_range new_vr = VR_INITIALIZER;
> --
> 2.9.2.512.gd7cab81
>
Ping.
