[PATCH] Teach VRP to register assertions along default switch labels (PR 18046)

[Patrick Palka]

On Fri, 22 Jul 2016, Patrick Palka wrote:

> This patch teaches VRP to register along a default switch label
> assertions that corresponds to the anti range of each case label.
> 
> Does this look OK to commit after bootstrap + regtest on
> x86_64-pc-linux-gnu?

Forgot the changelog:

gcc/ChangeLog:

	PR tree-optimization/18046
	* tree-vrp.c (find_switch_asserts): Register edge assertions
	for the default label which correspond to the anti-ranges
	of each non-case label.

gcc/testsuite/ChangeLog:

	PR tree-optimization/18046
	* gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5.
	* gcc.dg/tree-ssa/vrp103.c: New test.
	* gcc.dg/tree-ssa/vrp104.c: New test.

> ---
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c |  2 +-
>  gcc/testsuite/gcc.dg/tree-ssa/vrp103.c           | 30 ++++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c           | 32 +++++++++++++++++++
>  gcc/tree-vrp.c                                   | 39 ++++++++++++++++++++++--
>  4 files changed, 100 insertions(+), 3 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
> 
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
> index 5ec4687..551fbac 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
> @@ -1,7 +1,7 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread2-details" } */
>  /* { dg-final { scan-tree-dump-times "FSM" 3 "thread1" } } */
> -/* { dg-final { scan-tree-dump-times "FSM" 4 "thread2" } } */
> +/* { dg-final { scan-tree-dump-times "FSM" 5 "thread2" } } */
>  
>  int sum0, sum1, sum2, sum3;
>  int foo (char *s, char **ret)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
> new file mode 100644
> index 0000000..eea98bb
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
> @@ -0,0 +1,30 @@
> +/* PR tree-optimization/18046  */
> +/* { dg-options "-O2 -fdump-tree-vrp" }  */
> +/* { dg-final { scan-tree-dump-times "baz \\(0\\);" 4 "vrp1" } }  */
> +
> +void foo ();
> +void bar ();
> +void baz (int);
> +
> +void
> +test (int i)
> +{
> +  switch (i)
> +    {
> +    case 1:
> +    case 2:
> +    case 3:
> +      foo ();
> +      break;
> +    case 5:
> +      bar ();
> +      break;
> +    default:
> +      /* These tests should be folded to 0, resulting in 4 calls to bar (0).  */
> +      baz (i == 1);
> +      baz (i == 2);
> +      baz (i == 3);
> +      baz (i == 5);
> +      break;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
> new file mode 100644
> index 0000000..6410847
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
> @@ -0,0 +1,32 @@
> +/* PR tree-optimization/18046  */
> +/* { dg-options "-O2 -fdump-tree-optimized" }  */
> +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } }  */
> +
> +void foo ();
> +void bar ();
> +
> +void
> +test (int i)
> +{
> +  switch (i)
> +    {
> +    case 1:
> +      foo ();
> +      break;
> +    case 2:
> +      bar ();
> +      break;
> +    default:
> +      break;
> +    }
> +
> +  /* This switch should be gone after threading/VRP.  */
> +  switch (i)
> +    {
> +    case 1:
> +      foo ();
> +      break;
> +    default:
> +      break;
> +    }
> +}
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 06364b7..32a4de3 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5917,6 +5917,7 @@ find_switch_asserts (basic_block bb, gswitch *last)
>        ci[idx].expr = gimple_switch_label (last, idx);
>        ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
>      }
> +  edge default_edge = find_edge (bb, ci[0].bb);
>    qsort (ci, n, sizeof (struct case_info), compare_case_labels);
>  
>    for (idx = 0; idx < n; ++idx)
> @@ -5945,8 +5946,8 @@ find_switch_asserts (basic_block bb, gswitch *last)
>  	    max = CASE_LOW (ci[idx].expr);
>  	}
>  
> -      /* Nothing to do if the range includes the default label until we
> -	 can register anti-ranges.  */
> +      /* Can't extract a useful assertion out of a range that includes the
> +         default label.  */
>        if (min == NULL_TREE)
>  	continue;
>  
> @@ -5963,6 +5964,40 @@ find_switch_asserts (basic_block bb, gswitch *last)
>  				  fold_convert (TREE_TYPE (op), max));
>      }
>  
> +  /* For each case label, register along the default label an assertion that
> +     corresponds to the anti-range of that label.  */
> +  for (idx = 0; idx < n; ++idx)
> +    {
> +      tree min, max;
> +      tree cl = ci[idx].expr;
> +
> +      min = CASE_LOW (cl);
> +      max = CASE_HIGH (cl);
> +
> +      if (min == NULL_TREE)
> +	continue;
> +
> +      if (max == NULL_TREE)
> +	{
> +	  /* Register the assertion OP != MIN.  */
> +	  min = fold_convert (TREE_TYPE (op), min);
> +	  register_edge_assert_for (op, default_edge, bsi, NE_EXPR, op, min);
> +	}
> +      else
> +	{
> +	  /* Register the assertion (unsigned)OP - MIN > (MAX - MIN),
> +	     which will give OP the anti-range ~[MIN,MAX].  */
> +	  tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op);
> +	  min = fold_convert (TREE_TYPE (uop), min);
> +	  max = fold_convert (TREE_TYPE (uop), max);
> +
> +	  tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min);
> +	  tree rhs = int_const_binop (MINUS_EXPR, max, min);
> +	  register_new_assert_for (op, lhs, GT_EXPR, rhs,
> +				   NULL, default_edge, bsi);
> +	}
> +    }
> +
>    XDELETEVEC (ci);
>  }
>  
> -- 
> 2.9.2.413.g76d2a70
> 
>