[PATCH] Improve jump threading using VRP information

[Richard Biener]

On Thu, Jun 27, 2013 at 6:29 AM, Jeff Law <law@redhat.com> wrote:
>
> Just something else I saw while analyzing dumps from an unrelated set of
> changes.
>
> It's relatively common to see sequences like this:
>
>   # parent_1 = PHI <parent_7(3), parent_6(D)(4), parent_6(D)(5)>
>   _11 = single_tree_10(D) != 0;
>   _12 = parent_1 == 0B;
>   _13 = _11 & _12;
>   if (_13 != 0)
>     goto <bb 8>;
>   else
>     goto <bb 7>;
>
> Where VRP can deduce that the value of parent_6 has a nonzero value on one
> (or more) of the paths reaching this block (because those paths dereference
> parent_6).
>
> Obviously when VRP knows parent_6 is nonzero, then we know the current block
> will always transfer control to BB 7.
>
> Or something like this:
>
>  <bb 6>:
>   # prephitmp_49 = PHI <1(4), pretmp_48(5)>
>   prev_line.31_6 = prev_line;
>   _8 = prev_line.31_6 != line_7(D);
>   line_differs_9 = (unsigned char) _8;
>   _10 = prephitmp_49 | line_differs_9;
>   if (_10 != 0)
>     goto <bb 8>;
>   else
>     goto <bb 7>;
>
>
> We may not know the exact value of _10, but VRP can determine that when BB6
> is reached from BB4 that BB6 will always transfer control to BB8.
>
>
> I never coded up the bits to utilize VRP information to simplify statements
> for threading except for COND_EXPRs.  It wasn't clear how often it would be
> useful, thus I took the easy way out.  This picks up a hundred or so
> additional threading opportunities in my testfiles.  Not huge, but worth it
> IMHO.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
>
> OK for trunk?

Ok if it still applies.

Thanks,
Richard.

>
>
>
>         * tree-vrp.c (simplify_stmt_for_jump_threading): Try to
>         simplify assignments too.  If the RHS collapses to a singleton
>         range, then return the value for the range.
>
>         * gcc.dg/tree-ssa/ssa-vrp-thread-1.c: New test.
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c
> new file mode 100644
> index 0000000..9d9473e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-vrp-thread-1.c
> @@ -0,0 +1,31 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
> +
> +
> +struct basic_block_def;
> +typedef struct basic_block_def *basic_block;
> +enum gimple_code
> +{
> +  LAST_AND_UNUSED_GIMPLE_CODE
> +};
> +struct omp_region
> +{
> +  struct omp_region *outer;
> +  basic_block cont;
> +};
> +void
> +build_omp_regions_1 (basic_block bb, struct omp_region *parent,
> +                    unsigned char single_tree, enum gimple_code code)
> +{
> +  if (code == 25)
> +    parent = parent->outer;
> +  else if (code == 42)
> +    parent->cont = bb;
> +  if (single_tree && !parent)
> +    return;
> +  oof ();
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Threaded" 1 "vrp1" }  } */
> +/* { dg-final { cleanup-tree-dump "vrp1" } } */
> +
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index ec7ef8f..683a3db 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -9109,15 +9109,27 @@ static vec<tree> equiv_stack;
>  static tree
>  simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
>  {
> -  /* We only use VRP information to simplify conditionals.  This is
> -     overly conservative, but it's unclear if doing more would be
> -     worth the compile time cost.  */
> -  if (gimple_code (stmt) != GIMPLE_COND)
> -    return NULL;
> +  if (gimple_code (stmt) == GIMPLE_COND)
> +    return vrp_evaluate_conditional (gimple_cond_code (stmt),
> +                                    gimple_cond_lhs (stmt),
> +                                    gimple_cond_rhs (stmt), within_stmt);
> +
> +  if (gimple_code (stmt) == GIMPLE_ASSIGN)
> +    {
> +      value_range_t new_vr = VR_INITIALIZER;
> +      tree lhs = gimple_assign_lhs (stmt);
> +
> +      if (TREE_CODE (lhs) == SSA_NAME
> +         && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +             || POINTER_TYPE_P (TREE_TYPE (lhs))))
> +       {
> +         extract_range_from_assignment (&new_vr, stmt);
> +         if (range_int_cst_singleton_p (&new_vr))
> +           return new_vr.min;
> +       }
> +    }
>
> -  return vrp_evaluate_conditional (gimple_cond_code (stmt),
> -                                  gimple_cond_lhs (stmt),
> -                                  gimple_cond_rhs (stmt), within_stmt);
> +  return NULL_TREE;
>  }
>
>  /* Blocks which have more than one predecessor and more than
>