Re: [PATCH] call mark_dfs_back_edges() before testing EDGE_DFS_BACK [PR104761]

[Jeff Law <jeffreyalaw@gmail.com>]

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