On Mon, Jan 22, 2018 at 9:05 PM, David Malcolm <dmalc...@redhat.com> wrote:
> On Fri, 2018-01-19 at 09:45 +0100, Richard Biener wrote:
>> On Fri, Jan 19, 2018 at 12:36 AM, David Malcolm <dmalc...@redhat.com>
>> 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®rtested 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®rtested 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 (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.
> * tree-ssa-sccvn.c (sccvn_dom_walker::sccvn_dom_walker): Likewise.
> * tree-vrp.c
> (check_array_bounds_dom_walker::check_array_bounds_dom_walker):
> Likewise, but converting it to REACHABLE_BLOCKS_PRESERVING_FLAGS.
> (vrp_dom_walker::vrp_dom_walker): Likewise, but converting it to
> REACHABLE_BLOCKS.
> (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 | 49 +++++---
> gcc/domwalk.h | 42 +++++--
> gcc/graphite-scop-detection.c | 2 +-
> gcc/testsuite/gcc.c-torture/compile/pr83510.c | 172
> ++++++++++++++++++++++++++
> gcc/tree-ssa-dom.c | 2 +-
> gcc/tree-ssa-sccvn.c | 2 +-
> gcc/tree-vrp.c | 21 +++-
> 7 files changed, 259 insertions(+), 31 deletions(-)
> create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr83510.c
>
> diff --git a/gcc/domwalk.c b/gcc/domwalk.c
> index 64304a6..0161761 100644
> --- a/gcc/domwalk.c
> +++ b/gcc/domwalk.c
> @@ -169,15 +169,28 @@ sort_bbs_postorder (basic_block *bbs, int n)
> qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
> }
>
> -/* Constructor for a dom walker.
> +/* 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. */
> dom_walker::dom_walker (cdi_direction direction,
> - bool skip_unreachable_blocks,
> + enum reachability reachability,
> int *bb_index_to_rpo)
> : m_dom_direction (direction),
> - m_skip_unreachable_blocks (skip_unreachable_blocks),
> + m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
> m_user_bb_to_rpo (bb_index_to_rpo != NULL),
> m_unreachable_dom (NULL),
> m_bb_to_rpo (bb_index_to_rpo)
> @@ -195,18 +208,22 @@ dom_walker::dom_walker (cdi_direction direction,
> free (postorder);
> }
>
> - /* If we are not skipping unreachable blocks, then there is nothing
> - further to do. */
> - if (!m_skip_unreachable_blocks)
> - return;
> -
> - basic_block bb;
> - FOR_ALL_BB_FN (bb, cfun)
> + /* Set up edge flags if need be. */
> + switch (reachability)
> {
> - edge_iterator ei;
> - edge e;
> - FOR_EACH_EDGE (e, ei, bb->succs)
> - e->flags |= EDGE_EXECUTABLE;
> + default:
> + gcc_unreachable ();
> + case ALL_BLOCKS:
> + /* No need to touch edge flags. */
> + break;
> +
> + case REACHABLE_BLOCKS:
> + set_all_edges_as_executable (cfun);
> + break;
> +
> + case REACHABLE_BLOCKS_PRESERVING_FLAGS:
> + /* Preserve the edge flags. */
> + break;
> }
> }
>
> diff --git a/gcc/domwalk.h b/gcc/domwalk.h
> index 39dd11e..2e8290f 100644
> --- a/gcc/domwalk.h
> +++ b/gcc/domwalk.h
> @@ -32,17 +32,37 @@ class dom_walker
> public:
> static const edge STOP;
>
> - /* Use SKIP_UNREACHABLE_BLOCKS = true when your client can discover
> - that some edges are not executable.
> -
> - If a client can discover that a COND, SWITCH or GOTO has a static
> - target in the before_dom_children callback, the taken edge should
> - be returned. The generic walker will clear EDGE_EXECUTABLE on all
> - edges it can determine are not executable.
> -
> - You can provide a mapping of basic-block index to RPO if you
> + /* An enum for determining whether the dom walk should be constrained to
> + blocks reachable by executable edges. */
> +
> + enum reachability
> + {
> + /* Walk all blocks within the CFG. */
> + ALL_BLOCKS,
> +
> + /* Use REACHABLE_BLOCKS when your subclass can discover that some edges
> + are not executable.
> +
> + If a subclass can discover that a COND, SWITCH or GOTO has a static
> + target in the before_dom_children callback, the taken edge should
> + be returned. The generic walker will clear EDGE_EXECUTABLE on all
> + edges it can determine are not executable.
> +
> + With REACHABLE_BLOCKS, EDGE_EXECUTABLE will be set on every edge in
> + the dom_walker ctor; the flag will then be cleared on edges that are
> + determined to be not executable. */
> + REACHABLE_BLOCKS,
> +
> + /* Identical to REACHABLE_BLOCKS, but the initial state of
> EDGE_EXECUTABLE
> + will instead be preserved in the ctor, allowing for information about
> + non-executable edges to be merged in from an earlier analysis (and
> + potentially for additional edges to be marked as non-executable). */
> + REACHABLE_BLOCKS_PRESERVING_FLAGS
> + };
> +
> + /* You can provide a mapping of basic-block index to RPO if you
> have that readily available or you do multiple walks. */
> - dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false,
> + dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS,
> int *bb_index_to_rpo = NULL);
>
> ~dom_walker ();
> @@ -87,4 +107,6 @@ private:
>
> };
>
> +extern void set_all_edges_as_executable (function *fn);
> +
> #endif
> diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
> index 6f407e1..e8b8b3a 100644
> --- a/gcc/graphite-scop-detection.c
> +++ b/gcc/graphite-scop-detection.c
> @@ -1424,7 +1424,7 @@ private:
> };
> }
> gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
> - : dom_walker (direction, false, bb_to_rpo), scop (scop)
> + : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
> {
> }
>
> diff --git a/gcc/testsuite/gcc.c-torture/compile/pr83510.c
> b/gcc/testsuite/gcc.c-torture/compile/pr83510.c
> new file mode 100644
> index 0000000..907dd80
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/compile/pr83510.c
> @@ -0,0 +1,172 @@
> +/* Various examples of safe array access for which -Warray-bounds
> + shouldn't issue a warning at any optimization level
> + (PR tree-optimization/83510). */
> +
> +/* { dg-options "-Warray-bounds" } */
> +
> +extern int get_flag (void);
> +
> +unsigned int arr[10];
> +
> +struct xyz {
> + unsigned int a0;
> +};
> +
> +extern void wfm(struct xyz *, int, unsigned int);
> +
> +static unsigned int f(struct xyz * ctx, unsigned int number)
> +{
> + switch (number) {
> + case 0x9:
> + return ctx->a0;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + return arr[number - 0xa];
> + }
> + return 0;
> +}
> +
> +int g(struct xyz * ctx) {
> + int i;
> +
> + for (i = 0; i < 10; i++) {
> + wfm(ctx, i, f(ctx, i));
> + }
> +
> + return 0;
> +}
> +
> +static unsigned int f_signed(struct xyz * ctx, int number)
> +{
> + switch (number) {
> + case 0x9:
> + return ctx->a0;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + return arr[number];
> + }
> + return 0;
> +}
> +
> +int g_signed(struct xyz * ctx) {
> + int i;
> +
> + for (i = 0; i < 10; i++) {
> + wfm(ctx, i, f(ctx, i));
> + }
> +
> + return 0;
> +}
> +
> +void test_2 (struct xyz * ctx)
> +{
> + int i;
> +
> + for (i = 0; i < 10; i++) {
> + if (get_flag ())
> + wfm(ctx, i, f(ctx, i));
> + }
> +}
> +
> +void test_2_signed (struct xyz * ctx)
> +{
> + int i;
> +
> + for (i = 0; i < 10; i++) {
> + if (get_flag ())
> + wfm(ctx, i, f_signed(ctx, i));
> + }
> +}
> +
> +void test_3 (struct xyz * ctx)
> +{
> + unsigned int i;
> +
> + for (i = 0; i < 10; i++) {
> + switch (i) {
> + case 0x9:
> + wfm(ctx, i, ctx->a0);
> + break;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + if (get_flag ())
> + wfm(ctx, i, arr[i - 0xa]);
> + break;
> + }
> + }
> +}
> +
> +void test_3_signed (struct xyz * ctx)
> +{
> + int i;
> +
> + for (i = 0; i < 10; i++) {
> + switch (i) {
> + case 0x9:
> + wfm(ctx, i, ctx->a0);
> + break;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + if (get_flag ())
> + wfm(ctx, i, arr[i]);
> + break;
> + }
> + }
> +}
> +
> +void test_4 (struct xyz * ctx)
> +{
> + unsigned int i, j;
> +
> + for (i = 0; i < 10; i++) {
> + switch (i) {
> + case 0x9:
> + wfm(ctx, i, ctx->a0);
> + break;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + for (j = 0; j < 5; j++)
> + wfm(ctx, i, arr[i - 0xa]);
> + break;
> + }
> + }
> +}
> +void test_4_signed (struct xyz * ctx)
> +{
> + int i, j;
> +
> + for (i = 0; i < 10; i++) {
> + switch (i) {
> + case 0x9:
> + wfm(ctx, i, ctx->a0);
> + break;
> + case 0xA: case 0xB:
> + case 0xC: case 0xD: case 0xE: case 0xF:
> + case 0x10: case 0x11: case 0x12: case 0x13:
> + for (j = 0; j < 5; j++)
> + wfm(ctx, i, arr[i]);
> + break;
> + }
> + }
> +}
> +
> +void test_5 (struct xyz * ctx)
> +{
> + unsigned int i;
> + for (i = 10; i < 20; i++) {
> + wfm(ctx, i, arr[i - 10]);
> + }
> +}
> +
> +void test_5_signed (struct xyz * ctx)
> +{
> + int i;
> + for (i = 10; i < 20; i++) {
> + wfm(ctx, i, arr[i - 10]);
> + }
> +}
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index a6eaed5..2b37166 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -574,7 +574,7 @@ public:
> class const_and_copies *const_and_copies,
> class avail_exprs_stack *avail_exprs_stack,
> gcond *dummy_cond)
> - : dom_walker (direction, true),
> + : dom_walker (direction, REACHABLE_BLOCKS),
> m_const_and_copies (const_and_copies),
> m_avail_exprs_stack (avail_exprs_stack),
> m_dummy_cond (dummy_cond) { }
> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
> index 7158bb0..9844bbb 100644
> --- a/gcc/tree-ssa-sccvn.c
> +++ b/gcc/tree-ssa-sccvn.c
> @@ -4769,7 +4769,7 @@ class sccvn_dom_walker : public dom_walker
> {
> public:
> sccvn_dom_walker ()
> - : dom_walker (CDI_DOMINATORS, true), cond_stack (0) {}
> + : dom_walker (CDI_DOMINATORS, REACHABLE_BLOCKS), cond_stack (0) {}
>
> virtual edge before_dom_children (basic_block);
> virtual void after_dom_children (basic_block);
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 3294bde..3af81f7 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5029,7 +5029,12 @@ class check_array_bounds_dom_walker : public dom_walker
> {
> public:
> check_array_bounds_dom_walker (vrp_prop *prop)
> - : dom_walker (CDI_DOMINATORS, true), m_prop (prop) {}
> + : dom_walker (CDI_DOMINATORS,
> + /* Discover non-executable edges, preserving EDGE_EXECUTABLE
> + flags, so that we can merge in information on
> + non-executable edges from vrp_folder . */
> + REACHABLE_BLOCKS_PRESERVING_FLAGS),
> + m_prop (prop) {}
> ~check_array_bounds_dom_walker () {}
>
> edge before_dom_children (basic_block) FINAL OVERRIDE;
> @@ -6645,7 +6650,7 @@ public:
> vrp_dom_walker (cdi_direction direction,
> class const_and_copies *const_and_copies,
> class avail_exprs_stack *avail_exprs_stack)
> - : dom_walker (direction, true),
> + : dom_walker (direction, REACHABLE_BLOCKS),
> m_const_and_copies (const_and_copies),
> m_avail_exprs_stack (avail_exprs_stack),
> m_dummy_cond (NULL) {}
> @@ -6835,6 +6840,18 @@ vrp_prop::vrp_finalize (bool warn_array_bounds_p)
> wi::to_wide (vr->max));
> }
>
> + /* If we're checking array refs, we want to merge information on
> + the executability of each edge between vrp_folder and the
> + check_array_bounds_dom_walker: each can clear the
> + EDGE_EXECUTABLE flag on edges, in different ways.
> +
> + Hence, if we're going to call check_all_array_refs, set
> + the flag on every edge now, rather than in
> + check_array_bounds_dom_walker's ctor; vrp_folder may clear
> + it from some edges. */
> + if (warn_array_bounds && warn_array_bounds_p)
> + set_all_edges_as_executable (cfun);
> +
> class vrp_folder vrp_folder;
> vrp_folder.vr_values = &vr_values;
> vrp_folder.substitute_and_fold ();
> --
> 1.8.5.3
>
