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?
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. */
> + 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 (!m_skip_unreachable_blocks)
> return;
>
> - basic_block bb;
> - FOR_ALL_BB_FN (bb, cfun)
> - {
> - edge_iterator ei;
> - edge e;
> - FOR_EACH_EDGE (e, ei, bb->succs)
> - e->flags |= EDGE_EXECUTABLE;
> - }
> + /* By default, set EDGE_EXECUTABLE on every edge within the CFG. */
> + if (!preserve_flags)
> + set_all_edges_as_executable (cfun);
> }
>
> /* Destructor. */
> diff --git a/gcc/domwalk.h b/gcc/domwalk.h
> index c7e3450..52ba7f6 100644
> --- a/gcc/domwalk.h
> +++ b/gcc/domwalk.h
> @@ -39,10 +39,19 @@ public:
> 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.
> +
> + If SKIP_UNREACHABLE_BLOCKS is true, then by default 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. If
> + PRESERVE_FLAGS is true, then 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).
>
> 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,
> + bool preserve_flags = false,
> int *bb_index_to_rpo = NULL);
>
> ~dom_walker ();
> @@ -87,4 +96,6 @@ private:
>
> };
>
> +extern void set_all_edges_as_executable (function *fn);
> +
> #endif
> 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-vrp.c b/gcc/tree-vrp.c
> index 27f7c37..9f26a65 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -5027,7 +5027,14 @@ 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... */
> + true, /* skip_unreachable_blocks */
> + /* ...preserving EDGE_EXECUTABLE flags, so that we can
> + merge in information on non-executable edges from
> + vrp_folder . */
> + true /* preserve_flags */),
> + m_prop (prop) {}
> ~check_array_bounds_dom_walker () {}
>
> edge before_dom_children (basic_block) FINAL OVERRIDE;
> @@ -6833,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
>
