* Re: [PATCH] call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]
2022-03-03 8:01 ` Jakub Jelinek
@ 2022-03-03 9:26 ` Richard Biener
2022-03-03 17:56 ` Jeff Law
2022-03-04 0:08 ` Martin Sebor
2 siblings, 0 replies; 9+ messages in thread
From: Richard Biener @ 2022-03-03 9:26 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jeff Law, Martin Sebor, gcc-patches
> Am 03.03.2022 um 09:02 schrieb Jakub Jelinek via Gcc-patches <gcc-patches@gcc.gnu.org>:
>
> On Wed, Mar 02, 2022 at 04:15:09PM -0700, Martin Sebor via Gcc-patches wrote:
>> The -Wdangling-pointer code tests the EDGE_DFS_BACK but the pass never
>> calls the mark_dfs_back_edges() function that initializes the bit (I
>> didn't know about it). As a result the bit is not set when expected,
>> which can cause false positives under the right conditions.
>
> Not a review because I also had to look up what computes EDGE_DFS_BACK,
> so I don't feel the right person to ack the patch.
The patch looks OK. The questions below might be all valid but they can be addressed with followup changes.
Richard.
> So, just a few questions.
>
> The code in question is:
> auto gsi = gsi_for_stmt (use_stmt);
>
> auto_bitmap visited;
>
> /* A use statement in the last basic block in a function or one that
> falls through to it is after any other prior clobber of the used
> variable unless it's followed by a clobber of the same variable. */
> basic_block bb = use_bb;
> while (bb != inval_bb
> && single_succ_p (bb)
> && !(single_succ_edge (bb)->flags & (EDGE_EH|EDGE_DFS_BACK)))
> {
> if (!bitmap_set_bit (visited, bb->index))
> /* Avoid cycles. */
> return true;
>
> for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
> {
> gimple *stmt = gsi_stmt (gsi);
> if (gimple_clobber_p (stmt))
> {
> if (clobvar == gimple_assign_lhs (stmt))
> /* The use is followed by a clobber. */
> return false;
> }
> }
>
> bb = single_succ (bb);
> gsi = gsi_start_bb (bb);
> }
>
> 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
> following a non-local goto forced edge from a noreturn call
> to a non-local label (if there is just one) doesn't seem
> right to me
> 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
> reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
> check as well as the visited bitmap (and having them use
> very different answers, if EDGE_DFS_BACK is seen, the function
> will return false, if visited bitmap has a bb, it will return true)?
> Can't the visited bitmap go away?
> 3) I'm concerned about compile time with the above, consider you have
> 1000000 use_stmts and 1000000 corresponding inv_stmts and in each
> case you enter this loop and go through a series of very large basic
> blocks that don't clobber those stmts; shouldn't it bail out
> (return false) after walking some param
> controlled number of non-debug stmts (say 1000 by default)?
> There is an early exit if
> if (dominated_by_p (CDI_DOMINATORS, use_bb, inval_bb))
> return true;
> (I admit I haven't read the code what happens if there is more than
> one clobber for the same variable)
>
>> The attached patch adds a call to the warning pass to initialize
>> the bit. Tested on x86_64-linux.
>>
>> Martin
>
>> Call mark_dfs_back_edges before testing EDGE_DFS_BACK [PR104761].
>>
>> Resolves:
>> PR middle-end/104761 - bogus -Wdangling-pointer with cleanup and infinite loop
>>
>> gcc/ChangeLog:
>>
>> PR middle-end/104761
>> * gimple-ssa-warn-access.cc (pass_waccess::execute): Call
>> mark_dfs_back_edges.
>>
>> gcc/testsuite/ChangeLog:
>>
>> PR middle-end/104761
>> * g++.dg/warn/Wdangling-pointer-4.C: New test.
>> * gcc.dg/Wdangling-pointer-4.c: New test.
>>
>> diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
>> index b7cdad517b3..b519712d76e 100644
>> --- a/gcc/gimple-ssa-warn-access.cc
>> +++ b/gcc/gimple-ssa-warn-access.cc
>> @@ -47,7 +47,7 @@
>> #include "tree-object-size.h"
>> #include "tree-ssa-strlen.h"
>> #include "calls.h"
>> -#include "cfgloop.h"
>> +#include "cfganal.h"
>> #include "intl.h"
>> #include "gimple-range.h"
>> #include "stringpool.h"
>> @@ -4710,6 +4710,9 @@ pass_waccess::execute (function *fun)
>> calculate_dominance_info (CDI_DOMINATORS);
>> calculate_dominance_info (CDI_POST_DOMINATORS);
>>
>> + /* Set or clear EDGE_DFS_BACK bits on back edges. */
>> + mark_dfs_back_edges (fun);
>> +
>> /* Create a new ranger instance and associate it with FUN. */
>> m_ptr_qry.rvals = enable_ranger (fun);
>> m_func = fun;
>
> Jakub
>
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [PATCH] call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]
2022-03-03 8:01 ` Jakub Jelinek
2022-03-03 9:26 ` Richard Biener
@ 2022-03-03 17:56 ` Jeff Law
2022-03-04 0:08 ` Martin Sebor
2 siblings, 0 replies; 9+ messages in thread
From: Jeff Law @ 2022-03-03 17:56 UTC (permalink / raw)
To: Jakub Jelinek, Richard Biener, Martin Sebor; +Cc: gcc-patches
On 3/3/2022 1:01 AM, Jakub Jelinek wrote:
> On Wed, Mar 02, 2022 at 04:15:09PM -0700, Martin Sebor via Gcc-patches wrote:
>> The -Wdangling-pointer code tests the EDGE_DFS_BACK but the pass never
>> calls the mark_dfs_back_edges() function that initializes the bit (I
>> didn't know about it). As a result the bit is not set when expected,
>> which can cause false positives under the right conditions.
> Not a review because I also had to look up what computes EDGE_DFS_BACK,
> so I don't feel the right person to ack the patch.
>
> So, just a few questions.
>
> The code in question is:
> auto gsi = gsi_for_stmt (use_stmt);
>
> auto_bitmap visited;
>
> /* A use statement in the last basic block in a function or one that
> falls through to it is after any other prior clobber of the used
> variable unless it's followed by a clobber of the same variable. */
> basic_block bb = use_bb;
> while (bb != inval_bb
> && single_succ_p (bb)
> && !(single_succ_edge (bb)->flags & (EDGE_EH|EDGE_DFS_BACK)))
> {
> if (!bitmap_set_bit (visited, bb->index))
> /* Avoid cycles. */
> return true;
>
> for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
> {
> gimple *stmt = gsi_stmt (gsi);
> if (gimple_clobber_p (stmt))
> {
> if (clobvar == gimple_assign_lhs (stmt))
> /* The use is followed by a clobber. */
> return false;
> }
> }
>
> bb = single_succ (bb);
> gsi = gsi_start_bb (bb);
> }
>
> 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
> following a non-local goto forced edge from a noreturn call
> to a non-local label (if there is just one) doesn't seem
> right to me
I think so.
> 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
> reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
> check as well as the visited bitmap (and having them use
> very different answers, if EDGE_DFS_BACK is seen, the function
> will return false, if visited bitmap has a bb, it will return true)?
> Can't the visited bitmap go away?
I would think so. Given how this code is written, I don't see any way
other than cycles to visit a BB more than once and with backedges
marked, there shouldn't be a way to get into a cycle if we ignore backedges.
> 3) I'm concerned about compile time with the above, consider you have
> 1000000 use_stmts and 1000000 corresponding inv_stmts and in each
> case you enter this loop and go through a series of very large basic
> blocks that don't clobber those stmts; shouldn't it bail out
> (return false) after walking some param
> controlled number of non-debug stmts (say 1000 by default)?
> There is an early exit if
> if (dominated_by_p (CDI_DOMINATORS, use_bb, inval_bb))
> return true;
> (I admit I haven't read the code what happens if there is more than
> one clobber for the same variable)
I'll let Martin comment on the time complexity question
I think #1 and #2 can be addressed as followups.
jeff
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [PATCH] call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]
2022-03-03 8:01 ` Jakub Jelinek
2022-03-03 9:26 ` Richard Biener
2022-03-03 17:56 ` Jeff Law
@ 2022-03-04 0:08 ` Martin Sebor
2022-03-04 13:58 ` Jakub Jelinek
2 siblings, 1 reply; 9+ messages in thread
From: Martin Sebor @ 2022-03-04 0:08 UTC (permalink / raw)
To: Jakub Jelinek, Richard Biener, Jeff Law; +Cc: gcc-patches
On 3/3/22 01:01, Jakub Jelinek wrote:
> On Wed, Mar 02, 2022 at 04:15:09PM -0700, Martin Sebor via Gcc-patches wrote:
>> The -Wdangling-pointer code tests the EDGE_DFS_BACK but the pass never
>> calls the mark_dfs_back_edges() function that initializes the bit (I
>> didn't know about it). As a result the bit is not set when expected,
>> which can cause false positives under the right conditions.
>
> Not a review because I also had to look up what computes EDGE_DFS_BACK,
> so I don't feel the right person to ack the patch.
>
> So, just a few questions.
>
> The code in question is:
> auto gsi = gsi_for_stmt (use_stmt);
>
> auto_bitmap visited;
>
> /* A use statement in the last basic block in a function or one that
> falls through to it is after any other prior clobber of the used
> variable unless it's followed by a clobber of the same variable. */
> basic_block bb = use_bb;
> while (bb != inval_bb
> && single_succ_p (bb)
> && !(single_succ_edge (bb)->flags & (EDGE_EH|EDGE_DFS_BACK)))
> {
> if (!bitmap_set_bit (visited, bb->index))
> /* Avoid cycles. */
> return true;
>
> for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
> {
> gimple *stmt = gsi_stmt (gsi);
> if (gimple_clobber_p (stmt))
> {
> if (clobvar == gimple_assign_lhs (stmt))
> /* The use is followed by a clobber. */
> return false;
> }
> }
>
> bb = single_succ (bb);
> gsi = gsi_start_bb (bb);
> }
>
> 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
> following a non-local goto forced edge from a noreturn call
> to a non-local label (if there is just one) doesn't seem
> right to me
Possibly yes. I can add it but I don't have a lot of experience with
these bits so if you can suggest a test case to exercise this that
would be helpful.
> 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
> reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
> check as well as the visited bitmap (and having them use
> very different answers, if EDGE_DFS_BACK is seen, the function
> will return false, if visited bitmap has a bb, it will return true)?
> Can't the visited bitmap go away?
Possibly. As I said above, I don't have enough experience with these
bits to make (and test) the changes quickly, or enough bandwidth to
come up to speed on them. Please feel free to make these improvements.
> 3) I'm concerned about compile time with the above, consider you have
> 1000000 use_stmts and 1000000 corresponding inv_stmts and in each
> case you enter this loop and go through a series of very large basic
> blocks that don't clobber those stmts; shouldn't it bail out
> (return false) after walking some param
> controlled number of non-debug stmts (say 1000 by default)?
> There is an early exit if
> if (dominated_by_p (CDI_DOMINATORS, use_bb, inval_bb))
> return true;
> (I admit I haven't read the code what happens if there is more than
> one clobber for the same variable)
I tend to agree that the loop is less than optimal. But before
imposing another arbitrary limit my preference would be to see if
it could be made more efficient. Without thinking about it too hard,
it seems that with some efficient lookup table a single traversal
per function should be sufficient. The first time through populate
the table with the clobbered variables along the path from use_bb
and each subsequent time just look up clobvar in the table.
But I have to use up the rest of my 2021 PTO next week before I lose
it and I don't expect to have the cycles to work on this anytime soon.
Martin
>
>> The attached patch adds a call to the warning pass to initialize
>> the bit. Tested on x86_64-linux.
>>
>> Martin
>
>> Call mark_dfs_back_edges before testing EDGE_DFS_BACK [PR104761].
>>
>> Resolves:
>> PR middle-end/104761 - bogus -Wdangling-pointer with cleanup and infinite loop
>>
>> gcc/ChangeLog:
>>
>> PR middle-end/104761
>> * gimple-ssa-warn-access.cc (pass_waccess::execute): Call
>> mark_dfs_back_edges.
>>
>> gcc/testsuite/ChangeLog:
>>
>> PR middle-end/104761
>> * g++.dg/warn/Wdangling-pointer-4.C: New test.
>> * gcc.dg/Wdangling-pointer-4.c: New test.
>>
>> diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
>> index b7cdad517b3..b519712d76e 100644
>> --- a/gcc/gimple-ssa-warn-access.cc
>> +++ b/gcc/gimple-ssa-warn-access.cc
>> @@ -47,7 +47,7 @@
>> #include "tree-object-size.h"
>> #include "tree-ssa-strlen.h"
>> #include "calls.h"
>> -#include "cfgloop.h"
>> +#include "cfganal.h"
>> #include "intl.h"
>> #include "gimple-range.h"
>> #include "stringpool.h"
>> @@ -4710,6 +4710,9 @@ pass_waccess::execute (function *fun)
>> calculate_dominance_info (CDI_DOMINATORS);
>> calculate_dominance_info (CDI_POST_DOMINATORS);
>>
>> + /* Set or clear EDGE_DFS_BACK bits on back edges. */
>> + mark_dfs_back_edges (fun);
>> +
>> /* Create a new ranger instance and associate it with FUN. */
>> m_ptr_qry.rvals = enable_ranger (fun);
>> m_func = fun;
>
> Jakub
>
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [PATCH] call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]
2022-03-04 0:08 ` Martin Sebor
@ 2022-03-04 13:58 ` Jakub Jelinek
2022-03-05 8:08 ` [PATCH] waccess: Remove visited bitmap and stop on EDGE_ABNORMAL Jakub Jelinek
0 siblings, 1 reply; 9+ messages in thread
From: Jakub Jelinek @ 2022-03-04 13:58 UTC (permalink / raw)
To: Martin Sebor; +Cc: Richard Biener, Jeff Law, gcc-patches
On Thu, Mar 03, 2022 at 05:08:30PM -0700, Martin Sebor wrote:
> > 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
> > following a non-local goto forced edge from a noreturn call
> > to a non-local label (if there is just one) doesn't seem
> > right to me
>
> Possibly yes. I can add it but I don't have a lot of experience with
> these bits so if you can suggest a test case to exercise this that
> would be helpful.
Something like:
void
foo (void)
{
__label__ l;
__attribute__((noreturn)) void bar (int x) { if (x) goto l; __builtin_trap (); }
bar (0);
l:;
}
shows a single EDGE_ABNORMAL from the bar call.
But it would need tweaking for the ptr use and clobber.
> > 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
> > reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
> > check as well as the visited bitmap (and having them use
> > very different answers, if EDGE_DFS_BACK is seen, the function
> > will return false, if visited bitmap has a bb, it will return true)?
> > Can't the visited bitmap go away?
>
> Possibly. As I said above, I don't have enough experience with these
> bits to make (and test) the changes quickly, or enough bandwidth to
> come up to speed on them. Please feel free to make these improvements.
I'll change that if it passes testing.
Jakub
^ permalink raw reply [flat|nested] 9+ messages in thread* [PATCH] waccess: Remove visited bitmap and stop on EDGE_ABNORMAL
2022-03-04 13:58 ` Jakub Jelinek
@ 2022-03-05 8:08 ` Jakub Jelinek
2022-03-05 10:28 ` Richard Biener
0 siblings, 1 reply; 9+ messages in thread
From: Jakub Jelinek @ 2022-03-05 8:08 UTC (permalink / raw)
To: Richard Biener, Jeff Law; +Cc: gcc-patches, Martin Sebor
On Fri, Mar 04, 2022 at 02:58:37PM +0100, Jakub Jelinek via Gcc-patches wrote:
> On Thu, Mar 03, 2022 at 05:08:30PM -0700, Martin Sebor wrote:
> > > 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
> > > following a non-local goto forced edge from a noreturn call
> > > to a non-local label (if there is just one) doesn't seem
> > > right to me
> >
> > Possibly yes. I can add it but I don't have a lot of experience with
> > these bits so if you can suggest a test case to exercise this that
> > would be helpful.
>
> Something like:
> void
> foo (void)
> {
> __label__ l;
> __attribute__((noreturn)) void bar (int x) { if (x) goto l; __builtin_trap (); }
> bar (0);
> l:;
> }
> shows a single EDGE_ABNORMAL from the bar call.
> But it would need tweaking for the ptr use and clobber.
>
> > > 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
> > > reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
> > > check as well as the visited bitmap (and having them use
> > > very different answers, if EDGE_DFS_BACK is seen, the function
> > > will return false, if visited bitmap has a bb, it will return true)?
> > > Can't the visited bitmap go away?
> >
> > Possibly. As I said above, I don't have enough experience with these
> > bits to make (and test) the changes quickly, or enough bandwidth to
> > come up to speed on them. Please feel free to make these improvements.
>
> I'll change that if it passes testing.
Here is a patch to do both. I don't think we really need to have a testcase
for the EDGE_ABNORMAL case (Martin, feel free to add it later), abnormal
edges simply aren't normal control flow and what exactly it means varies.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2022-03-05 Jakub Jelinek <jakub@redhat.com>
* gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p): Remove
visited bitmap and its use. Also punt on EDGE_ABNORMAL edges.
--- gcc/gimple-ssa-warn-access.cc.jj 2022-03-03 22:09:22.073800776 +0100
+++ gcc/gimple-ssa-warn-access.cc 2022-03-04 19:21:18.840416075 +0100
@@ -3812,20 +3812,15 @@ pass_waccess::use_after_inval_p (gimple
/* Proceed only when looking for uses of dangling pointers. */
auto gsi = gsi_for_stmt (use_stmt);
- auto_bitmap visited;
-
/* A use statement in the last basic block in a function or one that
falls through to it is after any other prior clobber of the used
variable unless it's followed by a clobber of the same variable. */
basic_block bb = use_bb;
while (bb != inval_bb
&& single_succ_p (bb)
- && !(single_succ_edge (bb)->flags & (EDGE_EH|EDGE_DFS_BACK)))
+ && !(single_succ_edge (bb)->flags
+ & (EDGE_EH | EDGE_ABNORMAL | EDGE_DFS_BACK)))
{
- if (!bitmap_set_bit (visited, bb->index))
- /* Avoid cycles. */
- return true;
-
for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
{
gimple *stmt = gsi_stmt (gsi);
Jakub
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [PATCH] waccess: Remove visited bitmap and stop on EDGE_ABNORMAL
2022-03-05 8:08 ` [PATCH] waccess: Remove visited bitmap and stop on EDGE_ABNORMAL Jakub Jelinek
@ 2022-03-05 10:28 ` Richard Biener
0 siblings, 0 replies; 9+ messages in thread
From: Richard Biener @ 2022-03-05 10:28 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jeff Law, gcc-patches, Martin Sebor
> Am 05.03.2022 um 09:08 schrieb Jakub Jelinek via Gcc-patches <gcc-patches@gcc.gnu.org>:
>
> On Fri, Mar 04, 2022 at 02:58:37PM +0100, Jakub Jelinek via Gcc-patches wrote:
>> On Thu, Mar 03, 2022 at 05:08:30PM -0700, Martin Sebor wrote:
>>>> 1) shouldn't it give up for EDGE_ABNORMAL too? I mean, e.g.
>>>> following a non-local goto forced edge from a noreturn call
>>>> to a non-local label (if there is just one) doesn't seem
>>>> right to me
>>>
>>> Possibly yes. I can add it but I don't have a lot of experience with
>>> these bits so if you can suggest a test case to exercise this that
>>> would be helpful.
>>
>> Something like:
>> void
>> foo (void)
>> {
>> __label__ l;
>> __attribute__((noreturn)) void bar (int x) { if (x) goto l; __builtin_trap (); }
>> bar (0);
>> l:;
>> }
>> shows a single EDGE_ABNORMAL from the bar call.
>> But it would need tweaking for the ptr use and clobber.
>>
>>>> 2) if EDGE_DFS_BACK is computed and 1) is done, is there any
>>>> reason why you need 2 levels of protection, i.e. the EDGE_DFS_BACK
>>>> check as well as the visited bitmap (and having them use
>>>> very different answers, if EDGE_DFS_BACK is seen, the function
>>>> will return false, if visited bitmap has a bb, it will return true)?
>>>> Can't the visited bitmap go away?
>>>
>>> Possibly. As I said above, I don't have enough experience with these
>>> bits to make (and test) the changes quickly, or enough bandwidth to
>>> come up to speed on them. Please feel free to make these improvements.
>>
>> I'll change that if it passes testing.
>
> Here is a patch to do both. I don't think we really need to have a testcase
> for the EDGE_ABNORMAL case (Martin, feel free to add it later), abnormal
> edges simply aren't normal control flow and what exactly it means varies.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok.
Thanks,
Richard
> 2022-03-05 Jakub Jelinek <jakub@redhat.com>
>
> * gimple-ssa-warn-access.cc (pass_waccess::use_after_inval_p): Remove
> visited bitmap and its use. Also punt on EDGE_ABNORMAL edges.
>
> --- gcc/gimple-ssa-warn-access.cc.jj 2022-03-03 22:09:22.073800776 +0100
> +++ gcc/gimple-ssa-warn-access.cc 2022-03-04 19:21:18.840416075 +0100
> @@ -3812,20 +3812,15 @@ pass_waccess::use_after_inval_p (gimple
> /* Proceed only when looking for uses of dangling pointers. */
> auto gsi = gsi_for_stmt (use_stmt);
>
> - auto_bitmap visited;
> -
> /* A use statement in the last basic block in a function or one that
> falls through to it is after any other prior clobber of the used
> variable unless it's followed by a clobber of the same variable. */
> basic_block bb = use_bb;
> while (bb != inval_bb
> && single_succ_p (bb)
> - && !(single_succ_edge (bb)->flags & (EDGE_EH|EDGE_DFS_BACK)))
> + && !(single_succ_edge (bb)->flags
> + & (EDGE_EH | EDGE_ABNORMAL | EDGE_DFS_BACK)))
> {
> - if (!bitmap_set_bit (visited, bb->index))
> - /* Avoid cycles. */
> - return true;
> -
> for (; !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
> {
> gimple *stmt = gsi_stmt (gsi);
>
>
> Jakub
>
^ permalink raw reply [flat|nested] 9+ messages in thread