Re: [PATCH] -Warray-bounds: Fix false positive in some "switch" stmts (PR tree-optimization/83510)

[Richard Biener]

On Fri, Jan 19, 2018 at 12:36 AM, David Malcolm  wrote:
> PR tree-optimization/83510 reports that r255649 (for
> PR tree-optimization/83312) introduced a false positive for
> -Warray-bounds for array accesses within certain switch statements:
> those for which value-ranges allow more than one case to be reachable,
> but for which one or more of the VR-unreachable cases contain
> out-of-range array accesses.
>
> In the reproducer, after the switch in f is inlined into g, we have 3 cases
> for the switch (case 9, case 10-19, and default), within a loop that
> ranges from 0..9.
>
> With both the old and new code, vr_values::simplify_switch_using_ranges clears
> the EDGE_EXECUTABLE flag on the edge to the "case 10-19" block.  This
> happens during the dom walk within the substitute_and_fold_engine.
>
> With the old code, the clearing of that EDGE_EXECUTABLE flag led to the
>   /* Skip blocks that were found to be unreachable.  */
> code in the old implementation of vrp_prop::check_all_array_refs skipping
> the "case 10-19" block.
>
> With the new code, we have a second dom walk, and that dom_walker's ctor
> sets all edges to be EDGE_EXECUTABLE, losing that information.
>
> Then, dom_walker::before_dom_children (here, the subclass'
> check_array_bounds_dom_walker::before_dom_children) can return one edge, if
> there's a unique successor edge, and dom_walker::walk filters the dom walk
> to just that edge.
>
> Here we have two VR-valid edges (case 9 and default), and an VR-invalid
> successor edge (case 10-19).  There's no *unique* valid successor edge,
> and hence taken_edge is NULL, and the filtering in dom_walker::walk
> doesn't fire.
>
> Hence we've lost the filtering of the "case 10-19" BB, hence the false
> positive.
>
> The issue is that we have two dom walks: first within vr_values'
> substitute_and_fold_dom_walker (which has skip_unreachable_blocks == false),
> then another within vrp_prop::check_all_array_refs (with
> skip_unreachable_blocks == true).
>
> Each has different "knowledge" about ruling out edges due to value-ranges,
> but we aren't combining that information.  The former "knows" about
> out-edges at a particular control construct (e.g. at a switch), the latter
> "knows" about dominance, but only about unique successors (hence the
> problem when two out of three switch cases are valid).
>
> This patch combines the information by preserving the EDGE_EXECUTABLE
> flags from the first dom walk, and using it in the second dom walk,
> potentially rejecting additional edges.
>
> Doing so fixes the false positive.
>
> I attempted an alternative fix, merging the two dom walks into one, but
> that led to crashes in identify_jump_threads, so I went with this, as
> a less invasive fix.
>
> Successfully bootstrapped on x86_64-pc-linux-gnu.
> OK for trunk?

Ok, but I think you need to update the domwalk construction in
graphite-scop-detection.c as well - did you test w/o graphite?

grep might be your friend...

Thanks,
Richard.

> gcc/ChangeLog:
> PR tree-optimization/83510
> * domwalk.c (set_all_edges_as_executable): New function.
> (dom_walker::dom_walker): Add new param "preserve_flags".  Move
> setup of edge flags to set_all_edges_as_executable and guard it
> with !preserve_flags.
> * domwalk.h (dom_walker::dom_walker): Add new param
> "preserve_flags", defaulting to false.
> (set_all_edges_as_executable): New decl.
> * tree-vrp.c
> (check_array_bounds_dom_walker::check_array_bounds_dom_walker):
> Pass "true" for new param of dom_walker's ctor.
> (vrp_prop::vrp_finalize): Call set_all_edges_as_executable
> if check_all_array_refs will be called.
>
> gcc/testsuite/ChangeLog:
> PR tree-optimization/83510
> * gcc.c-torture/compile/pr83510.c: New test case.
> ---
>  gcc/domwalk.c |  30 +++--
>  gcc/domwalk.h |  11 ++
>  gcc/testsuite/gcc.c-torture/compile/pr83510.c | 172 
> ++
>  gcc/tree-vrp.c|  21 +++-
>  4 files changed, 224 insertions(+), 10 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr83510.c
>
> diff --git a/gcc/domwalk.c b/gcc/domwalk.c
> index 102a293..988ff71 100644
> --- a/gcc/domwalk.c
> +++ b/gcc/domwalk.c
> @@ -169,12 +169,29 @@ sort_bbs_postorder (basic_block *bbs, int n)
>  qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
>  }
>
> +/* Set EDGE_EXECUTABLE on every edge within FN's CFG.  */
> +
> +void
> +set_all_edges_as_executable (function *fn)
> +{
> +  basic_block bb;
> +  FOR_ALL_BB_FN (bb, fn)
> +{
> +  edge_iterator ei;
> +  edge e;
> +  FOR_EACH_EDGE (e, ei, bb->succs)
> +   e->flags |= EDGE_EXECUTABLE;
> +}
> +}
> +
>  /* Constructor for a dom walker.
>
> If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
> -   EDGE_EXECUTABLE on every edge in the CFG. */
> +  

[PATCH] -Warray-bounds: Fix false positive in some "switch" stmts (PR tree-optimization/83510)

[David Malcolm]

PR tree-optimization/83510 reports that r255649 (for
PR tree-optimization/83312) introduced a false positive for
-Warray-bounds for array accesses within certain switch statements:
those for which value-ranges allow more than one case to be reachable,
but for which one or more of the VR-unreachable cases contain
out-of-range array accesses.

In the reproducer, after the switch in f is inlined into g, we have 3 cases
for the switch (case 9, case 10-19, and default), within a loop that
ranges from 0..9.

With both the old and new code, vr_values::simplify_switch_using_ranges clears
the EDGE_EXECUTABLE flag on the edge to the "case 10-19" block.  This
happens during the dom walk within the substitute_and_fold_engine.

With the old code, the clearing of that EDGE_EXECUTABLE flag led to the
  /* Skip blocks that were found to be unreachable.  */
code in the old implementation of vrp_prop::check_all_array_refs skipping
the "case 10-19" block.

With the new code, we have a second dom walk, and that dom_walker's ctor
sets all edges to be EDGE_EXECUTABLE, losing that information.

Then, dom_walker::before_dom_children (here, the subclass'
check_array_bounds_dom_walker::before_dom_children) can return one edge, if
there's a unique successor edge, and dom_walker::walk filters the dom walk
to just that edge.

Here we have two VR-valid edges (case 9 and default), and an VR-invalid
successor edge (case 10-19).  There's no *unique* valid successor edge,
and hence taken_edge is NULL, and the filtering in dom_walker::walk
doesn't fire.

Hence we've lost the filtering of the "case 10-19" BB, hence the false
positive.

The issue is that we have two dom walks: first within vr_values'
substitute_and_fold_dom_walker (which has skip_unreachable_blocks == false),
then another within vrp_prop::check_all_array_refs (with
skip_unreachable_blocks == true).

Each has different "knowledge" about ruling out edges due to value-ranges,
but we aren't combining that information.  The former "knows" about
out-edges at a particular control construct (e.g. at a switch), the latter
"knows" about dominance, but only about unique successors (hence the
problem when two out of three switch cases are valid).

This patch combines the information by preserving the EDGE_EXECUTABLE
flags from the first dom walk, and using it in the second dom walk,
potentially rejecting additional edges.

Doing so fixes the false positive.

I attempted an alternative fix, merging the two dom walks into one, but
that led to crashes in identify_jump_threads, so I went with this, as
a less invasive fix.

Successfully bootstrapped on x86_64-pc-linux-gnu.
OK for trunk?

gcc/ChangeLog:
PR tree-optimization/83510
* domwalk.c (set_all_edges_as_executable): New function.
(dom_walker::dom_walker): Add new param "preserve_flags".  Move
setup of edge flags to set_all_edges_as_executable and guard it
with !preserve_flags.
* domwalk.h (dom_walker::dom_walker): Add new param
"preserve_flags", defaulting to false.
(set_all_edges_as_executable): New decl.
* tree-vrp.c
(check_array_bounds_dom_walker::check_array_bounds_dom_walker):
Pass "true" for new param of dom_walker's ctor.
(vrp_prop::vrp_finalize): Call set_all_edges_as_executable
if check_all_array_refs will be called.

gcc/testsuite/ChangeLog:
PR tree-optimization/83510
* gcc.c-torture/compile/pr83510.c: New test case.
---
 gcc/domwalk.c |  30 +++--
 gcc/domwalk.h |  11 ++
 gcc/testsuite/gcc.c-torture/compile/pr83510.c | 172 ++
 gcc/tree-vrp.c|  21 +++-
 4 files changed, 224 insertions(+), 10 deletions(-)
 create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr83510.c

diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index 102a293..988ff71 100644
--- a/gcc/domwalk.c
+++ b/gcc/domwalk.c
@@ -169,12 +169,29 @@ sort_bbs_postorder (basic_block *bbs, int n)
 qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
 }
 
+/* Set EDGE_EXECUTABLE on every edge within FN's CFG.  */
+
+void
+set_all_edges_as_executable (function *fn)
+{
+  basic_block bb;
+  FOR_ALL_BB_FN (bb, fn)
+{
+  edge_iterator ei;
+  edge e;
+  FOR_EACH_EDGE (e, ei, bb->succs)
+   e->flags |= EDGE_EXECUTABLE;
+}
+}
+
 /* Constructor for a dom walker.
 
If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
-   EDGE_EXECUTABLE on every edge in the CFG. */
+   EDGE_EXECUTABLE on every edge in the CFG, unless
+   PRESERVE_FLAGS is true. */
 dom_walker::dom_walker (cdi_direction direction,
bool skip_unreachable_blocks,
+   bool preserve_flags,
int *bb_index_to_rpo)
   : m_dom_direction (direction),
 m_skip_unreachable_blocks (skip_unreachable_blocks),
@@ -200,14 +217,9 @@ dom_walker::dom_walker (cdi_direction direction,
   if