vrp: remove rendundant has_single_use tests

During assert-location discovery, if an SSA name is live according to
live_on_edge() on some outgoing edge E, then the SSA name definitely has
at least two uses: the use on the outgoing edge, and the use in some BB
dominating E->src from which the SSA_NAME and the potential assertion
was discovered.  These two uses can't be the same because the liveness
array is populated on-the-fly in reverse postorder so the latter use
which dominates BB couldn't have yet contributed to the liveness bitmap.

So AFAICT it's not necessary to check live_on_edge() as well as
!has_single_use() since the former check will imply the latter.  So this
patch removes these redundant calls to has_single_use() (and alse
replaces the use of has_single_use() in find_assert_locations_1 with a
liveness bitmap test which should be cheaper and more accurate).

I bootstrapped and regtested this change on x86_64-pc-linux-gnu.  I also
confirmed that the number of calls made to register_new_assert_for
before and after the patch remains the same during compilation of
libstdc++ and during compilation of gimple-match.c and when running the
tree-ssa.exp testsuite.  Does this look OK to commit?

gcc/ChangeLog:

	* tree-vrp.c (register_edge_assert_for_2): Remove redundant
	has_single_use() tests.
	(register_edge_assert_for_1): Likewise.
	(find_assert_locations_1): Check the liveness bitmap instead of
	calling has_single_use().
---
 gcc/tree-vrp.c | 29 ++++++++++-------------------
 1 file changed, 10 insertions(+), 19 deletions(-)

On Wed, Apr 20, 2016 at 6:45 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> During assert-location discovery, if an SSA name is live according to
> live_on_edge() on some outgoing edge E, then the SSA name definitely has
> at least two uses: the use on the outgoing edge, and the use in some BB
> dominating E->src from which the SSA_NAME and the potential assertion
> was discovered.  These two uses can't be the same because the liveness
> array is populated on-the-fly in reverse postorder so the latter use
> which dominates BB couldn't have yet contributed to the liveness bitmap.
>
> So AFAICT it's not necessary to check live_on_edge() as well as
> !has_single_use() since the former check will imply the latter.  So this
> patch removes these redundant calls to has_single_use() (and alse
> replaces the use of has_single_use() in find_assert_locations_1 with a
> liveness bitmap test which should be cheaper and more accurate).
>
> I bootstrapped and regtested this change on x86_64-pc-linux-gnu.  I also
> confirmed that the number of calls made to register_new_assert_for
> before and after the patch remains the same during compilation of
> libstdc++ and during compilation of gimple-match.c and when running the
> tree-ssa.exp testsuite.  Does this look OK to commit?
>
> gcc/ChangeLog:
>
>         * tree-vrp.c (register_edge_assert_for_2): Remove redundant
>         has_single_use() tests.
>         (register_edge_assert_for_1): Likewise.
>         (find_assert_locations_1): Check the liveness bitmap instead of
>         calling has_single_use().

By the way, would it be reasonable to cache/precompute the number of
non-debug uses each ssa name has so that has_single_use, has_zero_uses
etc are much cheaper?

On Thu, Apr 21, 2016 at 12:45 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> During assert-location discovery, if an SSA name is live according to
> live_on_edge() on some outgoing edge E, then the SSA name definitely has
> at least two uses: the use on the outgoing edge, and the use in some BB
> dominating E->src from which the SSA_NAME and the potential assertion
> was discovered.  These two uses can't be the same because the liveness
> array is populated on-the-fly in reverse postorder so the latter use
> which dominates BB couldn't have yet contributed to the liveness bitmap.
>
> So AFAICT it's not necessary to check live_on_edge() as well as
> !has_single_use() since the former check will imply the latter.  So this
> patch removes these redundant calls to has_single_use() (and alse
> replaces the use of has_single_use() in find_assert_locations_1 with a
> liveness bitmap test which should be cheaper and more accurate).
>
> I bootstrapped and regtested this change on x86_64-pc-linux-gnu.  I also
> confirmed that the number of calls made to register_new_assert_for
> before and after the patch remains the same during compilation of
> libstdc++ and during compilation of gimple-match.c and when running the
> tree-ssa.exp testsuite.  Does this look OK to commit?

Ok.

Thanks,
Richard.

> gcc/ChangeLog:
>
>         * tree-vrp.c (register_edge_assert_for_2): Remove redundant
>         has_single_use() tests.
>         (register_edge_assert_for_1): Likewise.
>         (find_assert_locations_1): Check the liveness bitmap instead of
>         calling has_single_use().
> ---
>  gcc/tree-vrp.c | 29 ++++++++++-------------------
>  1 file changed, 10 insertions(+), 19 deletions(-)
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index bbdf9ce..3cb470b 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5145,8 +5145,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>
>    /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
>       reachable from E.  */
> -  if (live_on_edge (e, name)
> -      && !has_single_use (name))
> +  if (live_on_edge (e, name))
>      register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
>
>    /* In the case of NAME <= CST and NAME being defined as
> @@ -5188,8 +5187,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>           && (cst2 == NULL_TREE
>               || TREE_CODE (cst2) == INTEGER_CST)
>           && INTEGRAL_TYPE_P (TREE_TYPE (name3))
> -         && live_on_edge (e, name3)
> -         && !has_single_use (name3))
> +         && live_on_edge (e, name3))
>         {
>           tree tmp;
>
> @@ -5215,8 +5213,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>           && TREE_CODE (name2) == SSA_NAME
>           && TREE_CODE (cst2) == INTEGER_CST
>           && INTEGRAL_TYPE_P (TREE_TYPE (name2))
> -         && live_on_edge (e, name2)
> -         && !has_single_use (name2))
> +         && live_on_edge (e, name2))
>         {
>           tree tmp;
>
> @@ -5319,8 +5316,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>           tree op1 = gimple_assign_rhs2 (def_stmt);
>           if (TREE_CODE (op0) == SSA_NAME
>               && TREE_CODE (op1) == INTEGER_CST
> -             && live_on_edge (e, op0)
> -             && !has_single_use (op0))
> +             && live_on_edge (e, op0))
>             {
>               enum tree_code reverse_op = (rhs_code == PLUS_EXPR
>                                            ? MINUS_EXPR : PLUS_EXPR);
> @@ -5346,8 +5342,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>               && (comp_code == LE_EXPR || comp_code == GT_EXPR
>                   || !tree_int_cst_equal (val,
>                                           TYPE_MIN_VALUE (TREE_TYPE (val))))
> -             && live_on_edge (e, name2)
> -             && !has_single_use (name2))
> +             && live_on_edge (e, name2))
>             {
>               tree tmp, cst;
>               enum tree_code new_comp_code = comp_code;
> @@ -5392,8 +5387,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>               && INTEGRAL_TYPE_P (TREE_TYPE (name2))
>               && IN_RANGE (tree_to_uhwi (cst2), 1, prec - 1)
>               && prec == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (val)))
> -             && live_on_edge (e, name2)
> -             && !has_single_use (name2))
> +             && live_on_edge (e, name2))
>             {
>               mask = wi::mask (tree_to_uhwi (cst2), false, prec);
>               val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2);
> @@ -5498,12 +5492,10 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>                       || !INTEGRAL_TYPE_P (TREE_TYPE (names[1]))
>                       || (TYPE_PRECISION (TREE_TYPE (name2))
>                           != TYPE_PRECISION (TREE_TYPE (names[1])))
> -                     || !live_on_edge (e, names[1])
> -                     || has_single_use (names[1]))
> +                     || !live_on_edge (e, names[1]))
>                     names[1] = NULL_TREE;
>                 }
> -             if (live_on_edge (e, name2)
> -                 && !has_single_use (name2))
> +             if (live_on_edge (e, name2))
>                 names[0] = name2;
>             }
>         }
> @@ -5724,8 +5716,7 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
>
>    /* 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))
> +  if (live_on_edge (e, op))
>      {
>        val = build_int_cst (TREE_TYPE (op), 0);
>        register_new_assert_for (op, op, code, val, NULL, e, bsi);
> @@ -6158,7 +6149,7 @@ find_assert_locations_1 (basic_block bb, sbitmap live)
>                       /* Note we want to register the assert for the
>                          operand of the NOP_EXPR after SI, not after the
>                          conversion.  */
> -                     if (! has_single_use (t))
> +                     if (bitmap_bit_p (live, SSA_NAME_VERSION (t)))
>                         register_new_assert_for (t, t, comp_code, value,
>                                                  bb, NULL, si);
>                     }
> --
> 2.8.1.231.g95ac767
>

On Thu, Apr 21, 2016 at 2:47 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> On Wed, Apr 20, 2016 at 6:45 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> During assert-location discovery, if an SSA name is live according to
>> live_on_edge() on some outgoing edge E, then the SSA name definitely has
>> at least two uses: the use on the outgoing edge, and the use in some BB
>> dominating E->src from which the SSA_NAME and the potential assertion
>> was discovered.  These two uses can't be the same because the liveness
>> array is populated on-the-fly in reverse postorder so the latter use
>> which dominates BB couldn't have yet contributed to the liveness bitmap.
>>
>> So AFAICT it's not necessary to check live_on_edge() as well as
>> !has_single_use() since the former check will imply the latter.  So this
>> patch removes these redundant calls to has_single_use() (and alse
>> replaces the use of has_single_use() in find_assert_locations_1 with a
>> liveness bitmap test which should be cheaper and more accurate).
>>
>> I bootstrapped and regtested this change on x86_64-pc-linux-gnu.  I also
>> confirmed that the number of calls made to register_new_assert_for
>> before and after the patch remains the same during compilation of
>> libstdc++ and during compilation of gimple-match.c and when running the
>> tree-ssa.exp testsuite.  Does this look OK to commit?
>>
>> gcc/ChangeLog:
>>
>>         * tree-vrp.c (register_edge_assert_for_2): Remove redundant
>>         has_single_use() tests.
>>         (register_edge_assert_for_1): Likewise.
>>         (find_assert_locations_1): Check the liveness bitmap instead of
>>         calling has_single_use().
>
> By the way, would it be reasonable to cache/precompute the number of
> non-debug uses each ssa name has so that has_single_use, has_zero_uses
> etc are much cheaper?

Not sure whether that's good (think of the need to update this plus the
storage required for it).  Maybe keep the immediate use list in order
{ real uses, debug uses }?
(thus do inserting at head/tail depending on use stmt case)

Richard.