This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Teach VRP to truncate the case ranges of a switch
On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
> 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.
Is this always an improvement? I can see that it can simplify things,
eliminate dead code etc, but could it make evaluating the switch less
efficient?
Consider e.g.
void
test (char ch)
{
if (ch > 17)
return;
switch (ch)
{
case 0:
foo (); break;
case 1 .. 255:
bar (); break;
}
}
which (assuming this could survive this far in this form) previously
could be implemented as a simple "if (ch == 0)" but with this would get
simplified to:
void
test (char ch)
{
if (ch > 17)
return;
switch (ch)
{
case 0:
foo (); break;
case 1 .. 17:
bar (); break;
}
}
which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
Sorry if this is a silly qn.
Dave
> 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
> >