Re: [PATCH 2/2] Simplify and extend VRP edge-assertion code

[Richard Biener <richard dot guenther at gmail dot com>]

On Tue, Nov 11, 2014 at 4:52 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> This patch refactors the VRP edge-assertion code to make it always
> traverse SSA-name definitions in order to find suitable edge assertions
> to insert.  Currently SSA-name definitions get traversed only when the
> LHS of the original conditional is a bitwise AND or OR operation which
> seems like a strange restriction.  We should always try to traverse
> the SSA-name definitions inside the conditional, in particular for
> conditionals with the form:
>
>   int p = x COMP y;
>   if (p != 0) -- edge assertion: x COMP y

Of course this specific case should have been simplified to

 if (x COMP y)

if that comparison cannot trap and -fnon-call-exceptions is in effect.

> To achieve this the patch merges the mutually recursive functions
> register_edge_assert_for_1() and register_edge_assert_for_2() into a
> single recursive function, register_edge_assert_for_1().  In doing so,
> code duplication can be reduced and at the same time the more general
> logic allows VRP to detect more useful edge assertions.
>
> The recursion of the function register_edge_assert_for_1() is bounded by
> a new 'limit' argument which is arbitrarily set to 4 so that at most 4
> levels of SSA-name definitions will be traversed per conditional.
> (Incidentally this hard recursion limit makes the related fix for PR
> 57685 unnecessary.)
>
> A test in uninit-pred-9_b.c now has to be marked xfail because in it VRP
> (correctly) transforms the statement
>
>   # prephitmp_35 = PHI <pretmp_9(8), _28(10)>
>   into
>   # prephitmp_35 = PHI <pretmp_9(8), 1(10)>
>
> and the uninit pass doesn't properly handle such PHIs containing a
> constant value as one of its arguments -- so a bogus uninit warning is
> now emitted.

Did you try fixing that?  It seems to me a constant should be easy
to handle?

> Full bootstrap + regtesting on x86_64-unknown-linux-gnu is in progress.
> Is it OK to commit if testing finishes with no new regressions?

Ok.

Thanks,
Richard.

> 2014-11-11  Patrick Palka  <patrick@parcs.ath.cx>
>
> gcc/
>         * tree-vrp.c (extract_code_and_val_from_cond_with_ops): Ensure
>         that NAME always equals COND_OP0 or COND_OP1.
>         (register_edge_assert_for, register_edge_assert_for_1,
>         register_edge_assert_for_2): Refactor and consolidate
>         edge-assertion logic into ...
>         (register_edge_assert_for_2): ... here.  Add LIMIT parameter.
>         Rename to ...
>         (register_edge_assert_for_1): ... this.
>
> gcc/testsuite/
>         * gcc.dg/vrp-1.c: New testcase.
>         * gcc.dg/vrp-2.c: New testcase.
>         * gcc.dg/uninit-pred-9_b.c: xfail test on line 24.
> ---
>  gcc/testsuite/gcc.dg/uninit-pred-9_b.c |   2 +-
>  gcc/testsuite/gcc.dg/vrp-1.c           |  31 ++++
>  gcc/testsuite/gcc.dg/vrp-2.c           |  78 ++++++++++
>  gcc/tree-vrp.c                         | 261 +++++++++++++++------------------
>  4 files changed, 231 insertions(+), 141 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/vrp-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/vrp-2.c
>
> diff --git a/gcc/testsuite/gcc.dg/uninit-pred-9_b.c b/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
> index d9ae75e..555ec20 100644
> --- a/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
> +++ b/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
> @@ -21,7 +21,7 @@ int foo (int n, int l, int m, int r)
>        blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
>
>    if ( (n <= 8) &&  (m < 99)  && (r < 19) )
> -      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
> +      blah(v); /* { dg-bogus "uninitialized" "bogus warning" { xfail *-*-* } } */
>
>    return 0;
>  }
> diff --git a/gcc/testsuite/gcc.dg/vrp-1.c b/gcc/testsuite/gcc.dg/vrp-1.c
> new file mode 100644
> index 0000000..df5334e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vrp-1.c
> @@ -0,0 +1,31 @@
> +/* { dg-options "-O2" } */
> +
> +void runtime_error (void) __attribute__ ((noreturn));
> +void compiletime_error (void) __attribute__ ((noreturn, error ("")));
> +
> +static void
> +compiletime_check_equals_1 (int *x, int y)
> +{
> +  int __p = *x != y;
> +  if (__builtin_constant_p (__p) && __p)
> +    compiletime_error ();
> +  if (__p)
> +    runtime_error ();
> +}
> +
> +static void
> +compiletime_check_equals_2 (int *x, int y)
> +{
> +  int __p = *x != y;
> +  if (__builtin_constant_p (__p) && __p)
> +    compiletime_error (); /* { dg-error "call to" } */
> +  if (__p)
> +    runtime_error ();
> +}
> +
> +void
> +foo (int *x)
> +{
> +  compiletime_check_equals_1 (x, 5);
> +  compiletime_check_equals_2 (x, 10);
> +}
> diff --git a/gcc/testsuite/gcc.dg/vrp-2.c b/gcc/testsuite/gcc.dg/vrp-2.c
> new file mode 100644
> index 0000000..5757c2f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vrp-2.c
> @@ -0,0 +1,78 @@
> +/* { dg-options "-O2" } */
> +
> +void runtime_error (void) __attribute__ ((noreturn));
> +void compiletime_error (void) __attribute__ ((noreturn, error ("")));
> +
> +void dummy (int x);
> +
> +void
> +bar (int x, int y, int z)
> +{
> +  int p = ~(x & y & z) == 37;
> +  if (p)
> +    {
> +      if (!x || !y || !z)
> +       compiletime_error (); /* { dg-bogus "call to" } */
> +    }
> +}
> +
> +void
> +baz (int x)
> +{
> +  int y = ~x;
> +  int p = y == 37;
> +  dummy (y);
> +  dummy (p);
> +  if (p)
> +    {
> +      int q = x != ~37;
> +      dummy (q);
> +      if (q)
> +       compiletime_error (); /* { dg-bogus "call to" } */
> +    }
> +}
> +
> +void
> +blah_1 (char x)
> +{
> +  int y = x;
> +  int p = y == 10;
> +  dummy (p);
> +  if (p)
> +    {
> +      int q = x != 10;
> +      dummy (q);
> +      if (q)
> +       compiletime_error (); /* { dg-bogus "call to" } */
> +    }
> +}
> +
> +void
> +blah_2 (int x)
> +{
> +  char y = x;
> +  int p = y != 100;
> +  dummy (y);
> +  dummy (p);
> +  if (p)
> +    {
> +      int q = x == 100;
> +      dummy (q);
> +      if (q)
> +       compiletime_error (); /* { dg-bogus "call to" } */
> +    }
> +}
> +
> +void
> +blah_3 (int x, int y)
> +{
> +  int p = x > y;
> +  dummy (p);
> +  if (p)
> +    {
> +      int q = x <= y;
> +      dummy (q);
> +      if (q)
> +       compiletime_error (); /* { dg-bogus "call to" } */
> +    }
> +}
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index f0a4382..f1b5839 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4896,9 +4896,14 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
>    enum tree_code comp_code;
>    tree val;
>
> -  /* Otherwise, we have a comparison of the form NAME COMP VAL
> -     or VAL COMP NAME.  */
> -  if (name == cond_op1)
> +  if (name == cond_op0)
> +    {
> +      /* The comparison is of the form NAME COMP VAL, so the
> +        comparison code remains unchanged.  */
> +      comp_code = cond_code;
> +      val = cond_op1;
> +    }
> +  else if (name == cond_op1)
>      {
>        /* If the predicate is of the form VAL COMP NAME, flip
>          COMP around because we need to register NAME as the
> @@ -4907,12 +4912,7 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
>        val = cond_op0;
>      }
>    else
> -    {
> -      /* The comparison is of the form NAME COMP VAL, so the
> -        comparison code remains unchanged.  */
> -      comp_code = cond_code;
> -      val = cond_op1;
> -    }
> +    gcc_unreachable ();
>
>    /* Invert the comparison code as necessary.  */
>    if (invert)
> @@ -4976,16 +4976,31 @@ masked_increment (const wide_int &val_in, const wide_int &mask,
>  }
>
>  /* Try to register an edge assertion for SSA name NAME on edge E for
> -   the condition COND contributing to the conditional jump pointed to by BSI.
> +   the condition COND (composed of COND_CODE, COND_OP0 and COND_OP1)
> +   contributing to the conditional jump pointed to by BSI.
> +
> +   Further, try to recursively register edge assertions for the SSA names in
> +   the defining statements of COND's operands.  This recursion is limited by
> +   LIMIT.
> +
>     Invert the condition COND if INVERT is true.  */
>
>  static void
> -register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
> -                           enum tree_code cond_code,
> +register_edge_assert_for_1 (tree name, edge e, gimple_stmt_iterator bsi,
> +                           unsigned int limit, enum tree_code cond_code,
>                             tree cond_op0, tree cond_op1, bool invert)
>  {
>    tree val;
> -  enum tree_code comp_code;
> +  enum tree_code comp_code, def_rhs_code;
> +  gimple def_stmt;
> +
> +  if (limit == 0 || TREE_CODE (name) != SSA_NAME)
> +    return;
> +
> +  /* Do not attempt to infer anything in names that flow through
> +     abnormal edges.  */
> +  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
> +    return;
>
>    if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
>                                                 cond_op0,
> @@ -5512,92 +5527,116 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>             }
>         }
>      }
> -}
>
> -/* OP is an operand of a truth value expression which is known to have
> -   a particular value.  Register any asserts for OP and for any
> -   operands in OP's defining statement.
>
> -   If CODE is EQ_EXPR, then we want to register OP is zero (false),
> -   if CODE is NE_EXPR, then we want to register OP is nonzero (true).   */
> +  /* If COND is effectively an equality test of an SSA_NAME against
> +     the value zero or one, then we may be able to assert values
> +     for SSA_NAMEs which flow into COND.  */
>
> -static void
> -register_edge_assert_for_1 (tree op, enum tree_code code,
> -                           edge e, gimple_stmt_iterator bsi)
> -{
> -  gimple op_def;
> -  tree val;
> -  enum tree_code rhs_code;
> -
> -  /* We only care about SSA_NAMEs.  */
> -  if (TREE_CODE (op) != SSA_NAME)
> +  def_stmt = SSA_NAME_DEF_STMT (name);
> +  if (!is_gimple_assign (def_stmt))
>      return;
>
> -  /* We know that OP will have a zero or nonzero value.  If OP is used
> -     more than once go ahead and register an assert for OP.  */
> -  if (live_on_edge (e, op)
> -      && !has_single_use (op))
> -    {
> -      val = build_int_cst (TREE_TYPE (op), 0);
> -      register_new_assert_for (op, op, code, val, NULL, e, bsi);
> -    }
> +  def_rhs_code = gimple_assign_rhs_code (def_stmt);
>
> -  /* Now look at how OP is set.  If it's set from a comparison,
> -     a truth operation or some bit operations, then we may be able
> -     to register information about the operands of that assignment.  */
> -  op_def = SSA_NAME_DEF_STMT (op);
> -  if (gimple_code (op_def) != GIMPLE_ASSIGN)
> -    return;
> +  /* In the case of NAME != 0 or NAME == C (where C != 0), for BIT_AND_EXPR
> +     defining statement of NAME we can assert that both operands of the
> +     BIT_AND_EXPR have nonzero value.  */
> +  if (def_rhs_code == BIT_AND_EXPR
> +      && ((comp_code == NE_EXPR && integer_zerop (val))
> +         || (comp_code == EQ_EXPR && TREE_CODE (val) == INTEGER_CST
> +             && integer_nonzerop (val))))
> +    {
> +      tree op0 = gimple_assign_rhs1 (def_stmt);
> +      tree op1 = gimple_assign_rhs2 (def_stmt);
> +      tree zero = build_zero_cst (TREE_TYPE (val));
>
> -  rhs_code = gimple_assign_rhs_code (op_def);
> +      register_edge_assert_for_1 (op0, e, bsi, limit - 1,
> +                                 NE_EXPR, op0, zero, false);
> +      register_edge_assert_for_1 (op1, e, bsi, limit - 1,
> +                                 NE_EXPR, op1, zero, false);
> +    }
>
> -  if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
> +  /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
> +     statement of NAME we can assert that both operands of the BIT_IOR_EXPR
> +     have value zero.  */
> +  if (def_rhs_code == BIT_IOR_EXPR
> +      && ((comp_code == EQ_EXPR && integer_zerop (val))
> +         || (comp_code == NE_EXPR && integer_onep (val)
> +             && TYPE_PRECISION (TREE_TYPE (name)) == 1)))
>      {
> -      bool invert = (code == EQ_EXPR ? true : false);
> -      tree op0 = gimple_assign_rhs1 (op_def);
> -      tree op1 = gimple_assign_rhs2 (op_def);
> +      tree op0 = gimple_assign_rhs1 (def_stmt);
> +      tree op1 = gimple_assign_rhs2 (def_stmt);
> +      tree zero = build_zero_cst (TREE_TYPE (val));
>
> -      if (TREE_CODE (op0) == SSA_NAME)
> -        register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1, invert);
> -      if (TREE_CODE (op1) == SSA_NAME)
> -        register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1, invert);
> +      register_edge_assert_for_1 (op0, e, bsi, limit - 1,
> +                                 EQ_EXPR, op0, zero, false);
> +      register_edge_assert_for_1 (op1, e, bsi, limit - 1,
> +                                 EQ_EXPR, op1, zero, false);
>      }
> -  else if ((code == NE_EXPR
> -           && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
> -          || (code == EQ_EXPR
> -              && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
> +
> +  if (def_rhs_code == BIT_NOT_EXPR
> +      && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
> +      && TREE_CODE (val) == INTEGER_CST)
>      {
> -      /* Recurse on each operand.  */
> -      tree op0 = gimple_assign_rhs1 (op_def);
> -      tree op1 = gimple_assign_rhs2 (op_def);
> -      if (TREE_CODE (op0) == SSA_NAME
> -         && has_single_use (op0))
> -       register_edge_assert_for_1 (op0, code, e, bsi);
> -      if (TREE_CODE (op1) == SSA_NAME
> -         && has_single_use (op1))
> -       register_edge_assert_for_1 (op1, code, e, bsi);
> +      /* Recurse, inverting VAL.  */
> +      tree rhs = gimple_assign_rhs1 (def_stmt);
> +      tree new_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (val), val);
> +      register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
> +                                 comp_code, rhs, new_val, false);
>      }
> -  else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
> -          && TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1)
> +
> +  /* In the case of NAME == [01] or NAME != [01], if NAME's defining statement
> +     is a TCC_COMPARISON then we can assert the defining statement itself or
> +     its negation.  */
> +  if (TREE_CODE_CLASS (def_rhs_code)  == tcc_comparison
> +      && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
> +      && (integer_zerop (val) || integer_onep (val)))
>      {
> -      /* Recurse, flipping CODE.  */
> -      code = invert_tree_comparison (code, false);
> -      register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
> +      tree op0 = gimple_assign_rhs1 (def_stmt);
> +      tree op1 = gimple_assign_rhs2 (def_stmt);
> +      bool invert = false;
> +
> +      if ((comp_code == EQ_EXPR && integer_zerop (val))
> +         || (comp_code == NE_EXPR && integer_onep (val)))
> +       invert = true;
> +
> +      register_edge_assert_for_1 (op0, e, bsi, limit - 1,
> +                                 def_rhs_code, op0, op1, invert);
> +      register_edge_assert_for_1 (op1, e, bsi, limit - 1,
> +                                 def_rhs_code, op0, op1, invert);
>      }
> -  else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
> +
> +  if (def_rhs_code == SSA_NAME)
>      {
>        /* Recurse through the copy.  */
> -      register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
> +      tree rhs = gimple_assign_rhs1 (def_stmt);
> +      register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
> +                                 comp_code, rhs, val, false);
>      }
> -  else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
> +
> +  if (CONVERT_EXPR_CODE_P (def_rhs_code)
> +      && TREE_CODE (val) == INTEGER_CST)
>      {
> -      /* Recurse through the type conversion, unless it is a narrowing
> -        conversion or conversion from non-integral type.  */
> -      tree rhs = gimple_assign_rhs1 (op_def);
> +      /* Recurse through the type conversion if possible.  */
> +      tree rhs = gimple_assign_rhs1 (def_stmt);
> +
>        if (INTEGRAL_TYPE_P (TREE_TYPE (rhs))
> -         && (TYPE_PRECISION (TREE_TYPE (rhs))
> -             <= TYPE_PRECISION (TREE_TYPE (op))))
> -       register_edge_assert_for_1 (rhs, code, e, bsi);
> +             /* If NAME is a widening conversion then from the condition
> +                (NAME = (T)RHS) == VAL we can extract RHS == VAL.  */
> +         && ((comp_code == EQ_EXPR
> +              && TYPE_PRECISION (TREE_TYPE (name))
> +                 >= TYPE_PRECISION (TREE_TYPE (rhs)))
> +             /* If NAME is a narrowing conversion then from the condition
> +                (NAME = (T)RHS) != VAL we can extract RHS != VAL.  */
> +             || (comp_code == NE_EXPR
> +                 && TYPE_PRECISION (TREE_TYPE (name))
> +                    <= TYPE_PRECISION (TREE_TYPE (rhs)))))
> +       {
> +         tree new_val = fold_convert (TREE_TYPE (rhs), val);
> +         register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
> +                                     comp_code, rhs, new_val, false);
> +       }
>      }
>  }
>
> @@ -5610,69 +5649,11 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
>                           enum tree_code cond_code, tree cond_op0,
>                           tree cond_op1)
>  {
> -  tree val;
> -  enum tree_code comp_code;
> +  const int MAX_TRAVERSAL_DEPTH = 4;
>    bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
>
> -  /* Do not attempt to infer anything in names that flow through
> -     abnormal edges.  */
> -  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
> -    return;
> -
> -  if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
> -                                               cond_op0, cond_op1,
> -                                               is_else_edge,
> -                                               &comp_code, &val))
> -    return;
> -
> -  /* Register ASSERT_EXPRs for name.  */
> -  register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
> -                             cond_op1, is_else_edge);
> -
> -
> -  /* If COND is effectively an equality test of an SSA_NAME against
> -     the value zero or one, then we may be able to assert values
> -     for SSA_NAMEs which flow into COND.  */
> -
> -  /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
> -     statement of NAME we can assert both operands of the BIT_AND_EXPR
> -     have nonzero value.  */
> -  if (((comp_code == EQ_EXPR && integer_onep (val))
> -       || (comp_code == NE_EXPR && integer_zerop (val))))
> -    {
> -      gimple def_stmt = SSA_NAME_DEF_STMT (name);
> -
> -      if (is_gimple_assign (def_stmt)
> -         && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
> -       {
> -         tree op0 = gimple_assign_rhs1 (def_stmt);
> -         tree op1 = gimple_assign_rhs2 (def_stmt);
> -         register_edge_assert_for_1 (op0, NE_EXPR, e, si);
> -         register_edge_assert_for_1 (op1, NE_EXPR, e, si);
> -       }
> -    }
> -
> -  /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
> -     statement of NAME we can assert both operands of the BIT_IOR_EXPR
> -     have zero value.  */
> -  if (((comp_code == EQ_EXPR && integer_zerop (val))
> -       || (comp_code == NE_EXPR && integer_onep (val))))
> -    {
> -      gimple def_stmt = SSA_NAME_DEF_STMT (name);
> -
> -      /* For BIT_IOR_EXPR only if NAME == 0 both operands have
> -        necessarily zero value, or if type-precision is one.  */
> -      if (is_gimple_assign (def_stmt)
> -         && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
> -             && (TYPE_PRECISION (TREE_TYPE (name)) == 1
> -                 || comp_code == EQ_EXPR)))
> -       {
> -         tree op0 = gimple_assign_rhs1 (def_stmt);
> -         tree op1 = gimple_assign_rhs2 (def_stmt);
> -         register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
> -         register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
> -       }
> -    }
> +  register_edge_assert_for_1 (name, e, si, MAX_TRAVERSAL_DEPTH, cond_code,
> +                             cond_op0, cond_op1, is_else_edge);
>  }
>
>
> --
> 2.2.0.rc1.16.g6066a7e
>