Message ID | 1461192328-25630-1-git-send-email-patrick@parcs.ath.cx |
---|---|
State | New |
Headers | show |
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.
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); }