| Message ID | 20230418103326.54716139CC@imap2.suse-dmz.suse.de |
|---|---|
| State | New |
| Headers | show |
| Series | tree-optimization/109539 - restrict PHI handling in access diagnostics | expand |
On Tue, Apr 18, 2023 at 12:33:25PM +0200, Richard Biener wrote: > Access diagnostics visits the SSA def-use chains to diagnose things like > dangling pointer uses. When that runs into PHIs it tries to prove > all incoming pointers of which one is the currently visited use are > related to decide whether to keep looking for the PHI def uses. > That turns out to be overly optimistic and thus costly. The following > scraps the existing handling for simply requiring that we eventually > visit all incoming pointers of the PHI during the def-use chain > analysis and only then process uses of the PHI def. > > Note this handles backedges of natural loops optimistically, diagnosing > the first iteration. There's gcc.dg/Wuse-after-free-2.c containing > a testcase requiring this. > > I've bootstrapped and tested a version without the backedge handling > (regressing that single test), currently bootstrapping and testing > the version below. > > OK for trunk and branch if that succeeds? > > Thanks, > Richard. > > PR tree-optimization/109539 > * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses): > Re-implement pointer relatedness for PHIs. > --- > gcc/gimple-ssa-warn-access.cc | 47 ++++++++++++++++++++++++++++------- > 1 file changed, 38 insertions(+), 9 deletions(-) > > diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc > index d0d2148c872..1034161d478 100644 > --- a/gcc/gimple-ssa-warn-access.cc > +++ b/gcc/gimple-ssa-warn-access.cc > @@ -4175,6 +4175,7 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > > auto_vec<tree> pointers; > pointers.safe_push (ptr); > + hash_map<tree, int> phi_map; Shouldn't this be hash_map<tree, int> *phi_map = NULL; instead and allocate/delete it only if we run into any PHIs? Or is it so likely we find some PHIs that it isn't worth it? Or shouldn't we have hash_map variant which doesn't actually do costly construction and has some method to construct it on demand later? Talking about this, shouldn't pointers be auto_vec<tree, N> for some reasonable N and pointers.quick_push (ptr) instead of safe_push? > /* Starting with PTR, iterate over POINTERS added by the loop, and > either warn for their uses in basic blocks dominated by the STMT > @@ -4241,19 +4242,47 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > tree_code code = gimple_cond_code (cond); > equality = code == EQ_EXPR || code == NE_EXPR; > } > - else if (gimple_code (use_stmt) == GIMPLE_PHI) > + else if (gphi *phi = dyn_cast <gphi *> (use_stmt)) > { > /* Only add a PHI result to POINTERS if all its > - operands are related to PTR, otherwise continue. */ > - tree lhs = gimple_phi_result (use_stmt); > - if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry)) > - continue; > - > - if (TREE_CODE (lhs) == SSA_NAME) > + operands are related to PTR, otherwise continue. The > + PHI result is related once we've reached all arguments > + through this iteration. That also means any invariant > + argument will make the PHI not related. For arguments > + flowing over natural loop backedges we are optimistic > + (and diagnose the first iteration). */ > + tree lhs = gimple_phi_result (phi); > + bool existed_p; > + int &related = phi_map.get_or_insert (lhs, &existed_p); > + if (!existed_p) > { > - pointers.safe_push (lhs); > - continue; > + related = gimple_phi_num_args (phi) - 1; > + for (unsigned j = 0; j < gimple_phi_num_args (phi); ++j) > + { > + if ((unsigned) phi_arg_index_from_use (use_p) == j) > + continue; > + tree arg = gimple_phi_arg_def (phi, j); > + edge e = gimple_phi_arg_edge (phi, j); > + basic_block arg_bb; > + if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest) > + /* Make sure we are not forward visiting a > + backedge argument. */ > + && (TREE_CODE (arg) != SSA_NAME > + || (!SSA_NAME_IS_DEFAULT_DEF (arg) > + && ((arg_bb > + = gimple_bb (SSA_NAME_DEF_STMT (arg))) > + != e->dest) > + && !dominated_by_p (CDI_DOMINATORS, > + e->dest, arg_bb)))) > + related--; > + } > } > + else > + related--; > + > + if (related == 0) > + pointers.safe_push (lhs); > + continue; > } > > /* Warn if USE_STMT is dominated by the deallocation STMT. Otherwise LGTM. Jakub
On Tue, 18 Apr 2023, Jakub Jelinek wrote: > On Tue, Apr 18, 2023 at 12:33:25PM +0200, Richard Biener wrote: > > Access diagnostics visits the SSA def-use chains to diagnose things like > > dangling pointer uses. When that runs into PHIs it tries to prove > > all incoming pointers of which one is the currently visited use are > > related to decide whether to keep looking for the PHI def uses. > > That turns out to be overly optimistic and thus costly. The following > > scraps the existing handling for simply requiring that we eventually > > visit all incoming pointers of the PHI during the def-use chain > > analysis and only then process uses of the PHI def. > > > > Note this handles backedges of natural loops optimistically, diagnosing > > the first iteration. There's gcc.dg/Wuse-after-free-2.c containing > > a testcase requiring this. > > > > I've bootstrapped and tested a version without the backedge handling > > (regressing that single test), currently bootstrapping and testing > > the version below. > > > > OK for trunk and branch if that succeeds? > > > > Thanks, > > Richard. > > > > PR tree-optimization/109539 > > * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses): > > Re-implement pointer relatedness for PHIs. > > --- > > gcc/gimple-ssa-warn-access.cc | 47 ++++++++++++++++++++++++++++------- > > 1 file changed, 38 insertions(+), 9 deletions(-) > > > > diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc > > index d0d2148c872..1034161d478 100644 > > --- a/gcc/gimple-ssa-warn-access.cc > > +++ b/gcc/gimple-ssa-warn-access.cc > > @@ -4175,6 +4175,7 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > > > > auto_vec<tree> pointers; > > pointers.safe_push (ptr); > > + hash_map<tree, int> phi_map; > > Shouldn't this be > hash_map<tree, int> *phi_map = NULL; > instead and allocate/delete it only if we run into any PHIs? > Or is it so likely we find some PHIs that it isn't worth it? > Or shouldn't we have hash_map variant which doesn't actually do costly > construction and has some method to construct it on demand later? Good point, adjusted. Not sure how likely it is we run into PHIs. > Talking about this, shouldn't pointers be auto_vec<tree, N> for some > reasonable N and pointers.quick_push (ptr) instead of safe_push? Done as well, but we can only use quick_push for the initial one. Re-testing as follows. Richard. From 8f8f88430d8d51844149c1c9e13bea385d375008 Mon Sep 17 00:00:00 2001 From: Richard Biener <rguenther@suse.de> Date: Tue, 18 Apr 2023 11:49:48 +0200 Subject: [PATCH] tree-optimization/109539 - restrict PHI handling in access diagnostics To: gcc-patches@gcc.gnu.org Access diagnostics visits the SSA def-use chains to diagnose things like dangling pointer uses. When that runs into PHIs it tries to prove all incoming pointers of which one is the currently visited use are related to decide whether to keep looking for the PHI def uses. That turns out to be overly optimistic and thus costly. The following scraps the existing handling for simply requiring that we eventually visit all incoming pointers of the PHI during the def-use chain analysis and only then process uses of the PHI def. Note this handles backedges of natural loops optimistically, diagnosing the first iteration. There's gcc.dg/Wuse-after-free-2.c containing a testcase requiring this. PR tree-optimization/109539 * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses): Re-implement pointer relatedness for PHIs. --- gcc/gimple-ssa-warn-access.cc | 56 ++++++++++++++++++++++++++++------- 1 file changed, 45 insertions(+), 11 deletions(-) diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc index d0d2148c872..48e85e9cab5 100644 --- a/gcc/gimple-ssa-warn-access.cc +++ b/gcc/gimple-ssa-warn-access.cc @@ -4173,8 +4173,9 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, auto_bitmap visited; - auto_vec<tree> pointers; - pointers.safe_push (ptr); + auto_vec<tree, 8> pointers; + pointers.quick_push (ptr); + hash_map<tree, int> *phi_map = nullptr; /* Starting with PTR, iterate over POINTERS added by the loop, and either warn for their uses in basic blocks dominated by the STMT @@ -4241,19 +4242,49 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, tree_code code = gimple_cond_code (cond); equality = code == EQ_EXPR || code == NE_EXPR; } - else if (gimple_code (use_stmt) == GIMPLE_PHI) + else if (gphi *phi = dyn_cast <gphi *> (use_stmt)) { /* Only add a PHI result to POINTERS if all its - operands are related to PTR, otherwise continue. */ - tree lhs = gimple_phi_result (use_stmt); - if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry)) - continue; - - if (TREE_CODE (lhs) == SSA_NAME) + operands are related to PTR, otherwise continue. The + PHI result is related once we've reached all arguments + through this iteration. That also means any invariant + argument will make the PHI not related. For arguments + flowing over natural loop backedges we are optimistic + (and diagnose the first iteration). */ + tree lhs = gimple_phi_result (phi); + if (!phi_map) + phi_map = new hash_map<tree, int>; + bool existed_p; + int &related = phi_map->get_or_insert (lhs, &existed_p); + if (!existed_p) { - pointers.safe_push (lhs); - continue; + related = gimple_phi_num_args (phi) - 1; + for (unsigned j = 0; j < gimple_phi_num_args (phi); ++j) + { + if ((unsigned) phi_arg_index_from_use (use_p) == j) + continue; + tree arg = gimple_phi_arg_def (phi, j); + edge e = gimple_phi_arg_edge (phi, j); + basic_block arg_bb; + if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest) + /* Make sure we are not forward visiting a + backedge argument. */ + && (TREE_CODE (arg) != SSA_NAME + || (!SSA_NAME_IS_DEFAULT_DEF (arg) + && ((arg_bb + = gimple_bb (SSA_NAME_DEF_STMT (arg))) + != e->dest) + && !dominated_by_p (CDI_DOMINATORS, + e->dest, arg_bb)))) + related--; + } } + else + related--; + + if (related == 0) + pointers.safe_push (lhs); + continue; } /* Warn if USE_STMT is dominated by the deallocation STMT. @@ -4292,6 +4323,9 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, } } } + + if (phi_map) + delete phi_map; } /* Check call STMT for invalid accesses. */
On Tue, 18 Apr 2023, Richard Biener wrote: > On Tue, 18 Apr 2023, Jakub Jelinek wrote: > > > On Tue, Apr 18, 2023 at 12:33:25PM +0200, Richard Biener wrote: > > > Access diagnostics visits the SSA def-use chains to diagnose things like > > > dangling pointer uses. When that runs into PHIs it tries to prove > > > all incoming pointers of which one is the currently visited use are > > > related to decide whether to keep looking for the PHI def uses. > > > That turns out to be overly optimistic and thus costly. The following > > > scraps the existing handling for simply requiring that we eventually > > > visit all incoming pointers of the PHI during the def-use chain > > > analysis and only then process uses of the PHI def. > > > > > > Note this handles backedges of natural loops optimistically, diagnosing > > > the first iteration. There's gcc.dg/Wuse-after-free-2.c containing > > > a testcase requiring this. > > > > > > I've bootstrapped and tested a version without the backedge handling > > > (regressing that single test), currently bootstrapping and testing > > > the version below. > > > > > > OK for trunk and branch if that succeeds? > > > > > > Thanks, > > > Richard. > > > > > > PR tree-optimization/109539 > > > * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses): > > > Re-implement pointer relatedness for PHIs. > > > --- > > > gcc/gimple-ssa-warn-access.cc | 47 ++++++++++++++++++++++++++++------- > > > 1 file changed, 38 insertions(+), 9 deletions(-) > > > > > > diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc > > > index d0d2148c872..1034161d478 100644 > > > --- a/gcc/gimple-ssa-warn-access.cc > > > +++ b/gcc/gimple-ssa-warn-access.cc > > > @@ -4175,6 +4175,7 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > > > > > > auto_vec<tree> pointers; > > > pointers.safe_push (ptr); > > > + hash_map<tree, int> phi_map; > > > > Shouldn't this be > > hash_map<tree, int> *phi_map = NULL; > > instead and allocate/delete it only if we run into any PHIs? > > Or is it so likely we find some PHIs that it isn't worth it? > > Or shouldn't we have hash_map variant which doesn't actually do costly > > construction and has some method to construct it on demand later? > > Good point, adjusted. Not sure how likely it is we run into PHIs. > > > Talking about this, shouldn't pointers be auto_vec<tree, N> for some > > reasonable N and pointers.quick_push (ptr) instead of safe_push? > > Done as well, but we can only use quick_push for the initial one. > > Re-testing as follows. And now pushed to trunk and branch. Richard. > Richard. > > From 8f8f88430d8d51844149c1c9e13bea385d375008 Mon Sep 17 00:00:00 2001 > From: Richard Biener <rguenther@suse.de> > Date: Tue, 18 Apr 2023 11:49:48 +0200 > Subject: [PATCH] tree-optimization/109539 - restrict PHI handling in access > diagnostics > To: gcc-patches@gcc.gnu.org > > Access diagnostics visits the SSA def-use chains to diagnose things like > dangling pointer uses. When that runs into PHIs it tries to prove > all incoming pointers of which one is the currently visited use are > related to decide whether to keep looking for the PHI def uses. > That turns out to be overly optimistic and thus costly. The following > scraps the existing handling for simply requiring that we eventually > visit all incoming pointers of the PHI during the def-use chain > analysis and only then process uses of the PHI def. > > Note this handles backedges of natural loops optimistically, diagnosing > the first iteration. There's gcc.dg/Wuse-after-free-2.c containing > a testcase requiring this. > > PR tree-optimization/109539 > * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses): > Re-implement pointer relatedness for PHIs. > --- > gcc/gimple-ssa-warn-access.cc | 56 ++++++++++++++++++++++++++++------- > 1 file changed, 45 insertions(+), 11 deletions(-) > > diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc > index d0d2148c872..48e85e9cab5 100644 > --- a/gcc/gimple-ssa-warn-access.cc > +++ b/gcc/gimple-ssa-warn-access.cc > @@ -4173,8 +4173,9 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > > auto_bitmap visited; > > - auto_vec<tree> pointers; > - pointers.safe_push (ptr); > + auto_vec<tree, 8> pointers; > + pointers.quick_push (ptr); > + hash_map<tree, int> *phi_map = nullptr; > > /* Starting with PTR, iterate over POINTERS added by the loop, and > either warn for their uses in basic blocks dominated by the STMT > @@ -4241,19 +4242,49 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > tree_code code = gimple_cond_code (cond); > equality = code == EQ_EXPR || code == NE_EXPR; > } > - else if (gimple_code (use_stmt) == GIMPLE_PHI) > + else if (gphi *phi = dyn_cast <gphi *> (use_stmt)) > { > /* Only add a PHI result to POINTERS if all its > - operands are related to PTR, otherwise continue. */ > - tree lhs = gimple_phi_result (use_stmt); > - if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry)) > - continue; > - > - if (TREE_CODE (lhs) == SSA_NAME) > + operands are related to PTR, otherwise continue. The > + PHI result is related once we've reached all arguments > + through this iteration. That also means any invariant > + argument will make the PHI not related. For arguments > + flowing over natural loop backedges we are optimistic > + (and diagnose the first iteration). */ > + tree lhs = gimple_phi_result (phi); > + if (!phi_map) > + phi_map = new hash_map<tree, int>; > + bool existed_p; > + int &related = phi_map->get_or_insert (lhs, &existed_p); > + if (!existed_p) > { > - pointers.safe_push (lhs); > - continue; > + related = gimple_phi_num_args (phi) - 1; > + for (unsigned j = 0; j < gimple_phi_num_args (phi); ++j) > + { > + if ((unsigned) phi_arg_index_from_use (use_p) == j) > + continue; > + tree arg = gimple_phi_arg_def (phi, j); > + edge e = gimple_phi_arg_edge (phi, j); > + basic_block arg_bb; > + if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest) > + /* Make sure we are not forward visiting a > + backedge argument. */ > + && (TREE_CODE (arg) != SSA_NAME > + || (!SSA_NAME_IS_DEFAULT_DEF (arg) > + && ((arg_bb > + = gimple_bb (SSA_NAME_DEF_STMT (arg))) > + != e->dest) > + && !dominated_by_p (CDI_DOMINATORS, > + e->dest, arg_bb)))) > + related--; > + } > } > + else > + related--; > + > + if (related == 0) > + pointers.safe_push (lhs); > + continue; > } > > /* Warn if USE_STMT is dominated by the deallocation STMT. > @@ -4292,6 +4323,9 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, > } > } > } > + > + if (phi_map) > + delete phi_map; > } > > /* Check call STMT for invalid accesses. */ >
diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc index d0d2148c872..1034161d478 100644 --- a/gcc/gimple-ssa-warn-access.cc +++ b/gcc/gimple-ssa-warn-access.cc @@ -4175,6 +4175,7 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, auto_vec<tree> pointers; pointers.safe_push (ptr); + hash_map<tree, int> phi_map; /* Starting with PTR, iterate over POINTERS added by the loop, and either warn for their uses in basic blocks dominated by the STMT @@ -4241,19 +4242,47 @@ pass_waccess::check_pointer_uses (gimple *stmt, tree ptr, tree_code code = gimple_cond_code (cond); equality = code == EQ_EXPR || code == NE_EXPR; } - else if (gimple_code (use_stmt) == GIMPLE_PHI) + else if (gphi *phi = dyn_cast <gphi *> (use_stmt)) { /* Only add a PHI result to POINTERS if all its - operands are related to PTR, otherwise continue. */ - tree lhs = gimple_phi_result (use_stmt); - if (!pointers_related_p (stmt, lhs, ptr, m_ptr_qry)) - continue; - - if (TREE_CODE (lhs) == SSA_NAME) + operands are related to PTR, otherwise continue. The + PHI result is related once we've reached all arguments + through this iteration. That also means any invariant + argument will make the PHI not related. For arguments + flowing over natural loop backedges we are optimistic + (and diagnose the first iteration). */ + tree lhs = gimple_phi_result (phi); + bool existed_p; + int &related = phi_map.get_or_insert (lhs, &existed_p); + if (!existed_p) { - pointers.safe_push (lhs); - continue; + related = gimple_phi_num_args (phi) - 1; + for (unsigned j = 0; j < gimple_phi_num_args (phi); ++j) + { + if ((unsigned) phi_arg_index_from_use (use_p) == j) + continue; + tree arg = gimple_phi_arg_def (phi, j); + edge e = gimple_phi_arg_edge (phi, j); + basic_block arg_bb; + if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest) + /* Make sure we are not forward visiting a + backedge argument. */ + && (TREE_CODE (arg) != SSA_NAME + || (!SSA_NAME_IS_DEFAULT_DEF (arg) + && ((arg_bb + = gimple_bb (SSA_NAME_DEF_STMT (arg))) + != e->dest) + && !dominated_by_p (CDI_DOMINATORS, + e->dest, arg_bb)))) + related--; + } } + else + related--; + + if (related == 0) + pointers.safe_push (lhs); + continue; } /* Warn if USE_STMT is dominated by the deallocation STMT.