call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]

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.

The attached patch adds a call to the warning pass to initialize
the bit.  Tested on x86_64-linux.

Martin

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

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

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

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
>

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

On 3/2/22 19:15, Martin Sebor 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.
> 
> The attached patch adds a call to the warning pass to initialize
> the bit.  Tested on x86_64-linux.

OK on Monday if no other comments.

Jason