Re: [PATCH] vrp: remove rendundant has_single_use tests

[Richard Biener]

On Thu, Apr 21, 2016 at 2:47 AM, Patrick Palka  wrote:
> On Wed, Apr 20, 2016 at 6:45 PM, Patrick Palka  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.

Re: [PATCH] vrp: remove rendundant has_single_use tests

[Richard Biener]

On Thu, Apr 21, 2016 at 12:45 AM, Patrick Palka  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 

Re: [PATCH] vrp: remove rendundant has_single_use tests

[Patrick Palka]

On Wed, Apr 20, 2016 at 6:45 PM, Patrick Palka  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?

[PATCH] vrp: remove rendundant has_single_use tests

[Patrick Palka]

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(-)

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)
- &&