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

[Richard Biener]

On Mon, Jan 22, 2018 at 9:05 PM, David Malcolm  wrote:
> On Fri, 2018-01-19 at 09:45 +0100, Richard Biener wrote:
>> 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?
>
> Thanks.  I did test with graphite enabled; the use of default args meant I
> didn't have to touch that code.
>
> That said, I've become unhappy the two bool params (both defaulting
> to false) for dom_walker's ctor, especially given that they're
> really a tristate.
>
> So here's an alternative version of the patch, which, rather than adding
> a new bool, instead introduces a 3-valued enum to explicitly capture the valid
> possibilities.  Also, having it as an enum rather than booleans makes the
> meaning clearer, and makes the places that override the default more obvious.

Ah, much nicer indeed.

> (This version of the patch *did* require touching that graphite file).
>
>> grep might be your friend...
>
> (and indeed, with an enum, it's even more grep-friendly)
>
> Successfully bootstrapped on x86_64-pc-linux-gnu (with graphite).
> OK for trunk?
> (or did you prefer the earlier patch?)

Ok.

Thanks,
Richard.

>> Thanks,
>> Richard.
>
> [...snip...]
>
>
> gcc/ChangeLog:
> PR tree-optimization/83510
> * domwalk.c (set_all_edges_as_executable): New function.
> (dom_walker::dom_walker): Convert bool param
> "skip_unreachable_blocks" to enum reachability.  Move setup of
> edge flags to set_all_edges_as_executable and only do it when
> reachability is REACHABLE_BLOCKS.
> * domwalk.h (enum dom_walker::reachability): New enum.
> (dom_walker::dom_walker): Convert bool param
> "skip_unreachable_blocks" to enum reachability.
> (set_all_edges_as_executable): New decl.
> * graphite-scop-detection.c  

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

[David Malcolm]

On Fri, 2018-01-19 at 09:45 +0100, Richard Biener wrote:
> 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?

Thanks.  I did test with graphite enabled; the use of default args meant I
didn't have to touch that code.

That said, I've become unhappy the two bool params (both defaulting
to false) for dom_walker's ctor, especially given that they're
really a tristate.

So here's an alternative version of the patch, which, rather than adding
a new bool, instead introduces a 3-valued enum to explicitly capture the valid
possibilities.  Also, having it as an enum rather than booleans makes the
meaning clearer, and makes the places that override the default more obvious.

(This version of the patch *did* require touching that graphite file).

> grep might be your friend...

(and indeed, with an enum, it's even more grep-friendly)

Successfully bootstrapped on x86_64-pc-linux-gnu (with graphite).
OK for trunk?
(or did you prefer the earlier patch?)

> Thanks,
> Richard.

[...snip...]


gcc/ChangeLog:
PR tree-optimization/83510
* domwalk.c (set_all_edges_as_executable): New function.
(dom_walker::dom_walker): Convert bool param
"skip_unreachable_blocks" to enum reachability.  Move setup of
edge flags to set_all_edges_as_executable and only do it when
reachability is REACHABLE_BLOCKS.
* domwalk.h (enum dom_walker::reachability): New enum.
(dom_walker::dom_walker): Convert bool param
"skip_unreachable_blocks" to enum reachability.
(set_all_edges_as_executable): New decl.
* graphite-scop-detection.c  (gather_bbs::gather_bbs): Convert
from false for "skip_unreachable_blocks" to ALL_BLOCKS for
"reachability".
* tree-ssa-dom.c (dom_opt_dom_walker::dom_opt_dom_walker): Likewise,
but converting true to REACHABLE_BLOCKS.
*