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 >