Re: [PATCH] analyzer: call off a superseding when diagnostics are unrelated [PR110830]

[David Malcolm <dmalcolm@redhat.com>]

On Fri, 2023-09-01 at 21:59 +0200, priour.be@gmail.com wrote:
> From: benjamin priour <vultkayn@gcc.gnu.org>
> 
> Hi,
> 
> Patch succesfully regstrapped off trunk
> 7f2ed06ddc825e8a4e0edfd1d66b5156e6dc1d34
> on x86_64-linux-gnu.
> 
> Is it OK for trunk ?
> 
> Thanks,
> Benjamin.
> 

[...snip...]

>  
> +/* Walk up the two paths to each of their common conditional
> +   branching.  At each branching, make sure both diagnostics'
> +   paths branched similarly.  If there is at least one where
> +   both paths go down a different outcome, then the paths
> +   are incompatible and this function returns FALSE.
> +   Otherwise return TRUE.
> +
> +   Incompatible paths:
> +
> +       <cond Y>
> +       /      \
> +      /        \
> +    true      false
> +     |          |
> +    ...        ...
> +     |          |
> +    ...       stmt x
> +     |
> +   stmt x
> +
> +   Both LHS_PATH and RHS_PATH final enodes should be
> +   over the same gimple statement.  */
> +
> +static bool
> +compatible_epath_p (const exploded_path *lhs_path,
> +                   const exploded_path *rhs_path)
> +{
> +  gcc_assert (lhs_path);
> +  gcc_assert (rhs_path);
> +  int i;
> +  const exploded_edge *outer_eedge;
> +  FOR_EACH_VEC_ELT_REVERSE (lhs_path->m_edges, i, outer_eedge)
> +    {
> +      const superedge *outer_sedge = outer_eedge->m_sedge;
> +      if (!outer_sedge || !outer_eedge->m_src)
> +       continue;
> +      const program_point &outer_src_point = outer_eedge->m_src->get_point ();
> +      switch (outer_src_point.get_kind ())
> +       {
> +         case PK_AFTER_SUPERNODE:
> +           if (const cfg_superedge *cfg_outer_sedge
> +               = outer_sedge->dyn_cast_cfg_superedge ())
> +             {
> +               int j;
> +               const exploded_edge *inner_eedge;
> +               FOR_EACH_VEC_ELT_REVERSE (rhs_path->m_edges, j, inner_eedge)
> +                 {
> +                   const superedge *inner_sedge = inner_eedge->m_sedge;
> +                   if (!inner_sedge || !inner_eedge->m_src)
> +                     continue;
> +                   const program_point &inner_src_point
> +                     = inner_eedge->m_src->get_point ();
> +                   switch (inner_src_point.get_kind ())
> +                     {
> +                       case PK_AFTER_SUPERNODE:
> +                         if (inner_src_point.get_stmt ()
> +                             != outer_src_point.get_stmt ())
> +                           continue;
> +                         if (const cfg_superedge *cfg_inner_sedge
> +                             = inner_sedge->dyn_cast_cfg_superedge ())
> +                           {
> +                             if (cfg_inner_sedge->true_value_p ()
> +                                 != cfg_outer_sedge->true_value_p ())
> +                               return false;
> +                           }
> +                         break;
> +                       default:
> +                         break;
> +                     }
> +                 }
> +             }
> +           break;
> +
> +         default:
> +           break;
> +       }
> +    }
> +    return true;
> +}

[...snip...]

Thanks for the patch.  I think the high-level idea is good, but I'm not
sure the implementation is correct:

- it is O(n^2), where n is the length of exploded_path.
- it walks backwards through the LHS path, and for each eedge from a
PK_AFTER_SUPERNODE it walks backwards from the end of the RHS epath; it
only looks at the "true" flag on CFG edges.  I think this works for
simple cases, but the way it restarts the rhs_path iteration from the
end of the rhs_path each time "feels" incorrect.

An eedge from a PK_AFTER_SUPERNODE is presumably just an eedge that has
a non-NULL m_sedge i.e. an exploded edge relating to an edge in the
supergraph.  Rather than looking at flags, can we simply compare
superedge pointers?  For example, if we care that we followed the
"true" path of a conditional in both lhs and rhs epaths, we can look to
see if both have an eedge where the superedge is the cfg_superedge
wrapping the CFG "true" edge i.e. I think we can simply compare the
superedge pointers.

Or is there some detail here that I'm misunderstanding?

I *think* it's possible to implement it in O(n) with something like
this:  (warning: untested code follows!)

  /* For compatibility, there should effectively be the same
     vector of superedges followed in both epaths.
     Walk backwards through each epath, looking at the superedges.  */
  // FIXME: really?  Benjamin, have I understood this correctly?

  gcc_assert (lhs_path->length () > 0);
  gcc_assert (rhs_path->length () > 0);

  int lhs_idx = lhs_path->length () - 1;
  int rhs_idx = rhs_path->length () - 1;

  while (lhs_idx >= 0 && rhs_idx >= 0)
    {
      /* Find next LHS superedge, if any.  */
      while (lhs_idx >= 0)
        {
	  const exploded_edge *lhs_eedge = lhs_path->m_edges[lhs_idx];
	  if (lhs_eedge->m_sedge)
	    break;
	  else
	    lhs_idx--;
	}

      /* Find next RHS superedge, if any.  */
      while (rhs_idx >= 0)
        {
	  const exploded_edge *rhs_eedge = rhs_path->m_edges[rhs_idx];
	  if (rhs_eedge->m_sedge)
	    break;
	  else
	    rhs_idx--;
	}

      const exploded_edge *lhs_eedge
        (lhs_idx >= 0 ? lhs_path->m_edges[lhs_idx] : nullptr);
      const exploded_edge *rhs_eedge
        (rhs_idx >= 0 ? rhs_path->m_edges[rhs_idx] : nullptr);

      if (lhs_eedge && rhs_edge)
        {
	  /* If we followed different superedges, the paths are
	     not compatible.  */
	  if (lhs_eedge->m_sedge != rhs_eedge->m_sedge)
	    return false;

          /* Otherwise, we found an (LHS, RHS) pair of eedges
             both relating to the same superedge.  */
           lhs_idx--;
           rhs_idx--;
           continue;
        }
      else if (lhs_eedge == nullptr && rhs_eedge == nullptr)
        {
	  /* Finished traversing both epaths; they are compatible.  */
	  return true;
        }

      /* Otherwise, one epath ran out of superedges before the other;
         they are not compatible.  */
      return false;
    }

Does that make any sense, or have I misunderstood?

Thanks
Dave