[PATCH] Teach VRP to truncate the case ranges of a switch

Richard Biener richard.guenther@gmail.com
Wed Aug 3 13:48:00 GMT 2016


On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> VRP currently has functionality to eliminate case labels that lie
> completely outside of the switch operand's value range.  This patch
> complements this functionality by teaching VRP to also truncate the case
> label ranges that partially overlap with the operand's value range.
>
> Bootstrapped and regtested on x86_64-pc-linux-gnu.  Does this look like
> a reasonable optimization?  Admittedly, its effect will almost always be
> negligible except in cases where a case label range spans a large number
> of values which is a pretty rare thing.  The optimization triggered
> about 250 times during bootstrap.

I think it's most useful when the range collapses to a single value.

Ok.

Thanks,
Richard.

> gcc/ChangeLog:
>
>         * tree-vrp.c (simplify_switch_using_ranges): Try to truncate
>         the case label ranges that partially overlap with OP's value
>         range.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/vrp107.c: New test.
>         * gcc.dg/tree-ssa/vrp108.c: New test.
>         * gcc.dg/tree-ssa/vrp109.c: New test.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/vrp107.c | 25 +++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/vrp108.c | 25 +++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/vrp109.c | 65 +++++++++++++++++++++++++++
>  gcc/tree-vrp.c                         | 80 +++++++++++++++++++++++++++++++++-
>  4 files changed, 194 insertions(+), 1 deletion(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
> new file mode 100644
> index 0000000..b74f031
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
> @@ -0,0 +1,25 @@
> +/* { dg-options "-O2 -fdump-tree-vrp1" }  */
> +/* { dg-final { scan-tree-dump "case 2:" "vrp1" } }  */
> +/* { dg-final { scan-tree-dump "case 7 ... 8:" "vrp1" } }  */
> +
> +extern void foo (void);
> +extern void bar (void);
> +extern void baz (void);
> +
> +void
> +test (int i)
> +{
> +  if (i >= 2 && i <= 8)
> +  switch (i)
> +    {
> +    case 1: /* Redundant label.  */
> +    case 2:
> +      bar ();
> +      break;
> +    case 7:
> +    case 8:
> +    case 9: /* Redundant label.  */
> +      baz ();
> +      break;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
> new file mode 100644
> index 0000000..49dbfb5
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
> @@ -0,0 +1,25 @@
> +/* { dg-options "-O2 -fdump-tree-vrp1" }  */
> +/* { dg-final { scan-tree-dump "case 1:" "vrp1" } }  */
> +/* { dg-final { scan-tree-dump "case 9:" "vrp1" } }  */
> +
> +extern void foo (void);
> +extern void bar (void);
> +extern void baz (void);
> +
> +void
> +test (int i)
> +{
> +  if (i < 2 || i > 8)
> +  switch (i)
> +    {
> +    case 1:
> +    case 2: /* Redundant label.  */
> +      bar ();
> +      break;
> +    case 7: /* Redundant label.  */
> +    case 8: /* Redundant label.  */
> +    case 9:
> +      baz ();
> +      break;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
> new file mode 100644
> index 0000000..86299a9
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
> @@ -0,0 +1,65 @@
> +/* { dg-options "-O2 -fdump-tree-vrp1" }  */
> +/* { dg-final { scan-tree-dump "case 9 ... 10:" "vrp1" } }  */
> +/* { dg-final { scan-tree-dump "case 17 ... 18:" "vrp1" } }  */
> +/* { dg-final { scan-tree-dump "case 27 ... 30:" "vrp1" } }  */
> +
> +extern void foo (void);
> +extern void bar (void);
> +
> +void
> +test1 (int i)
> +{
> +  if (i != 7 && i != 8)
> +    switch (i)
> +      {
> +      case 1:
> +      case 2:
> +        foo ();
> +        break;
> +      case 7: /* Redundant label.  */
> +      case 8: /* Redundant label.  */
> +      case 9:
> +      case 10:
> +        bar ();
> +        break;
> +      }
> +}
> +
> +void
> +test3 (int i)
> +{
> +  if (i != 19 && i != 20)
> +    switch (i)
> +      {
> +      case 1:
> +      case 2:
> +        foo ();
> +        break;
> +      case 17:
> +      case 18:
> +      case 19: /* Redundant label.  */
> +      case 20: /* Redundant label.  */
> +        bar ();
> +        break;
> +      }
> +}
> +
> +void
> +test2 (int i)
> +{
> +  if (i != 28 && i != 29)
> +    switch (i)
> +      {
> +      case 1:
> +      case 2:
> +        foo ();
> +        break;
> +      /* No redundancy.  */
> +      case 27:
> +      case 28:
> +      case 29:
> +      case 30:
> +        bar ();
> +        break;
> +      }
> +}
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index cb316b0..b654b1b 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -9586,7 +9586,7 @@ static bool
>  simplify_switch_using_ranges (gswitch *stmt)
>  {
>    tree op = gimple_switch_index (stmt);
> -  value_range *vr;
> +  value_range *vr = NULL;
>    bool take_default;
>    edge e;
>    edge_iterator ei;
> @@ -9626,6 +9626,84 @@ simplify_switch_using_ranges (gswitch *stmt)
>
>    n = gimple_switch_num_labels (stmt);
>
> +  /* We can truncate the case label ranges that partially overlap with OP's
> +     value range.  */
> +  size_t min_idx = 1, max_idx = 0;
> +  if (vr != NULL)
> +    find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
> +  if (min_idx <= max_idx)
> +    {
> +      tree min_label = gimple_switch_label (stmt, min_idx);
> +      tree max_label = gimple_switch_label (stmt, max_idx);
> +
> +      if (vr->type == VR_RANGE)
> +       {
> +         /* If OP's value range is [2,8] and the low label range is
> +            0 ... 3, truncate the label's range to 2 .. 3.  */
> +         if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
> +             && CASE_HIGH (min_label) != NULL_TREE
> +             && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
> +           CASE_LOW (min_label) = vr->min;
> +
> +         /* If OP's value range is [2,8] and the high label range is
> +            7 ... 10, truncate the label's range to 7 .. 8.  */
> +         if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
> +             && CASE_HIGH (max_label) != NULL_TREE
> +             && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
> +           CASE_HIGH (max_label) = vr->max;
> +       }
> +      else if (vr->type == VR_ANTI_RANGE)
> +       {
> +         tree one_cst = build_one_cst (TREE_TYPE (op));
> +
> +         if (min_label == max_label)
> +           {
> +             /* If OP's value range is ~[7,8] and the label's range is
> +                7 ... 10, truncate the label's range to 9 ... 10.  */
> +             if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) == 0
> +                 && CASE_HIGH (min_label) != NULL_TREE
> +                 && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) > 0)
> +               CASE_LOW (min_label)
> +                 = int_const_binop (PLUS_EXPR, vr->max, one_cst);
> +
> +             /* If OP's value range is ~[7,8] and the label's range is
> +                5 ... 8, truncate the label's range to 5 ... 6.  */
> +             if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
> +                 && CASE_HIGH (min_label) != NULL_TREE
> +                 && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) == 0)
> +               CASE_HIGH (min_label)
> +                 = int_const_binop (MINUS_EXPR, vr->min, one_cst);
> +           }
> +         else
> +           {
> +             /* If OP's value range is ~[2,8] and the low label range is
> +                0 ... 3, truncate the label's range to 0 ... 1.  */
> +             if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
> +                 && CASE_HIGH (min_label) != NULL_TREE
> +                 && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
> +               CASE_HIGH (min_label)
> +                 = int_const_binop (MINUS_EXPR, vr->min, one_cst);
> +
> +             /* If OP's value range is ~[2,8] and the high label range is
> +                7 ... 10, truncate the label's range to 9 ... 10.  */
> +             if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
> +                 && CASE_HIGH (max_label) != NULL_TREE
> +                 && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
> +               CASE_LOW (max_label)
> +                 = int_const_binop (PLUS_EXPR, vr->max, one_cst);
> +           }
> +       }
> +
> +         /* Canonicalize singleton case ranges.  */
> +         if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
> +           CASE_HIGH (min_label) = NULL_TREE;
> +         if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
> +           CASE_HIGH (max_label) = NULL_TREE;
> +    }
> +
> +  /* We can also eliminate case labels that lie completely outside OP's value
> +     range.  */
> +
>    /* Bail out if this is just all edges taken.  */
>    if (i == 1
>        && j == n - 1
> --
> 2.9.2.564.g4d4f0b7
>



More information about the Gcc-patches mailing list